線形計画法に基づいたファクターグラフ上の推論アルゴリズムに関する一考察

摘要

グラフィカルモデル上の確率推論の問題は，符号理論·画像処理·音声認識などの様々な工学上の問題に現れ重要である．近年，確率推論の応用の1つである誤り訂正符号の復号問題に対して，線形計画法に基づいた復号アルゴリズムに関する研究が盛hに行われている．誤り訂正符号の復号問題をファクターグラフにより表現すると，グラフ中に含まれる関数は，指示関数とそれ以外の関数（非指示関数）に分類される．特に指示関数は複数の変数ノードに接続し，非指示関数は単一の変数ノードのみに接続している．一般的な確率推論の問題をファクターグラフとして表現した場合，複数の変数ノードと接続する非指示関数がファクターグラフに含まれる場合がある．本研究では，このような問題に対して，線形計画法に基づいた推論アルゴリズムを構築することを目的とする．