確率伝搬法

確率伝搬法

確率伝搬法（belief propagation）は、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデルで用いられるメッセージ伝達アルゴリズムです。この手法は、観測されたノードの状態に基づいて、未観測のノードの周辺分布を計算することができます。確率伝搬法は、特に人工知能や情報理論の領域で幅広く利用されており、低密度パリティ検査符号やターボ符号などの応用でも成功を収めています。

用語の正確な表記

確率伝搬法について、一般には「伝搬」ではなく「伝播」が正しい表記だとされることがありますが、工学分野において「電波伝搬」といった表現が広く使われているため、「伝搬」という用語が使われてきた経緯があります。それに伴い、本稿でも「伝搬」を使うことにします。

歴史とアルゴリズムの拡張

このアルゴリズムは1982年にジューディア・パールによって提案され、最初は木構造に限定されていました。しかし、その後、一般的な構造のモデルに対する拡張が行われ、現在ではループを含む一般的なグラフ構造でも適用可能となっています。

周辺分布の計算例

例として、X = (Xv)を結合確率質量関数pを持つ離散確率変数の集合とした場合、単一のノードの周辺分布Xiを次のように表現できます。

$$
p_{X_{i}}(x_{i}) = ext{sum}_{ extbf{x}': x'_{i} = x_{i}} p( extbf{x}')
$$

しかし、確率変数が100個の二値変数である場合、その全体の組み合わせ数は約6.3e29となり、コンピュータで計算するのは非常に困難です。この時、確率伝搬法はグラフの構造を活用することで、計算を効率化します。

Sum-productアルゴリズム

確率伝搬法では、因子グラフ上でメッセージを伝搬させます。因子グラフは、変数Vと因子Uからなる2部グラフで、変数と因子間にはエッジが存在しています。このグラフを使用して結合確率質量関数を表現できます。

$$
p( extbf{x}) = ext{prod}_{u ext{ in } U} f_{u}( extbf{x}_{u})
$$

メッセージの伝搬には2種類があり、1つは変数ノードから因子ノードへのメッセージで、もう1つはその逆です。

変数ノードから因子ノードへのメッセージ

このメッセージは、隣接する因子ノードの積を取ることで計算されます。

$$

u_{v o u}(x_{v}) = ext{prod}_{u^ ext{ in } N(v) ackslash ext{u}}
u_{u^ o v}(x_{v})
$$

因子ノードから変数ノードへのメッセージ

このメッセージは、隣接する変数ノードからのメッセージの積をとりながら、対象変数以外のすべての変数に対して周辺化を行います。

$$

u_{u o v}(x_{v}) = ext{sum}_{ extbf{x}'_{u}: x'_{v} = x_{v}} f_{u}( extbf{x}'_{u}) ext{prod}_{v^ ext{ in } N(u) ackslash ext{v}}
u_{v^ o u}(x'_{v^*})
$$

このアルゴリズムによって、結合確率分布から周辺分布を計算する難易度が大幅に減少します。

木構造における厳密解

確率伝搬法の最も単純な形は、因子グラフが木構造の場合です。この場合、周辺分布の厳密解が計算可能で、木の根と葉を定義しながらメッセージの伝搬を行います。各ノードはエッジを介してメッセージを根ノードへと伝え、根から葉へ戻る過程で計算が完了します。

一般的なグラフへの適用

一般的なグラフでも、似たアルゴリズムを用いることができます。ループを含むため「loopy」信念伝搬（loopy belief propagation）と呼ばれることもあります。この場合、すべてのメッセージは初期化され、各反復ごとに更新されることになります。このアルゴリズムの収束性に関する条件は未解明ですが、単一のループを含む場合は収束が知られています。

類似アルゴリズムと計算複雑性

確率伝搬法に関連するアルゴリズムとして、ビタビアルゴリズムが存在します。これは、周辺分布の計算ではなく、最大化問題を解決します。確率伝搬法は、NP困難な問題に属し、計算には高度な手法が求められます。また、自由エネルギーとも関連があり、確率伝搬法の収束点は自由エネルギーの最小化点とも見ることができます。

結論

確率伝搬法は、特にグラフィカルモデルの分野で強力なツールとして広く活用されています。その効率性と応用の広さから、今後も研究や実用において重要な位置を占めることでしょう。

もう一度検索