TAP平切場近似による誤り訂正符号の復号化(多体問題としての情報処理-統計力学と情報科学の接点-,研究会報告)

Abstract

統計モデルを用いた情報処理では最適性が理論的に示されながらもその計算量的複雑さのために実用化に至っていないアルゴリズムが少なからず存在する。他方、統計力学では専ら厳密計算が絶望的な大自由度のボルツマン分布を相手にしてきたため数多くの近似計算法を高度に発達させてきた。ならば、それらの近似計算法を計算が困難な情報処理の問題に活用することはできないだろうか?本稿では、厳密計算が困難な情報処理の一例である誤り訂正符号の復号化問題に対してスピングラスの平均場理論で開発されたTAP平均場近似が高性能な近似解法となることを示す。なお、本報告はAston大学David Saad氏、東工大総理工村山立入氏との共同研究の結果に基づいている。