ベイズ推論とベイジアンネットワーク - waxwing_k @ ウィキ

ベイズ推論とベイジアンネットワーク

ベイズ則と周辺化

確率と推論

• 「観測結果からその原因を推定する」という操作が必要になる
• 通信における様々な問題も同様の種類の問題である
• 観測値からベイズ則（Bayes rule）を用いて原因の事後確率分布を計算するという形で推論を行う
• 確率（probability）は命題の尤もらしさを表す量
• 観測値から非観測値の事後確率（posterior probability）を計算する操作を推論（inference）と呼ぶ
• 確率計算の問題は二つに分けられる
  • "因→果"の方向に確率を計算する問題を順確率問題
  • "果→因"の方向に確率を計算する問題を逆確率問題 or機能的推論

確率の基本計算則

• 結合確率 (joint probaility)
• ベイズ則
• 周辺化

推論計算の例

最大事後確率復号法

事後確率分布

ブロック単位MAP復号法

• ブロック単位最大事後確率復号法(bockwise MAP decoding)は，与えられた受信語yに対してP(X|Y=y)の値を最大化するCの符号語を推定送信語とする復号法である
• 最尤復号法 (Maximum Likelihood Decoding; MLD)

シンボル単位MAP復号法

• シンボル単位事後確率分布 P(X_i|Y=y)

計算量の問題

• 前節での復号に必要とされる計算時間は指数時間となる

この計算量の問題を解決するには

1. 計算が容易になる，容易に近似できるような特殊な構造をもつ線形符号を利用する
2. すべての符号語を生成するよりも効率の良い復号アルゴリズムを利用する

上の条件1を満たすものが[[LDPC符号]]であり，条件2を満たすものが[[sum-product復号法]]である

周辺分布の効率良い計算手法

• ここで考える周辺分布とは，事後確率分布の不必要な変数，パラメータを周辺化により取り除いて得られる確率分布である
• 復号における計算量の問題わ和の計算が膨大になる点

積和計算と分配則

• 積和計算
• 分配則
• 分配則を用いると積和計算が減らせる

ベイジアンネットワーク

• ベイジアンネットワークは，結合分布における変数間の依存関係を表す非巡回有効グラフである
• 結合分布がうまく因数分解出来る構造を持っていれば，分配則を利用して結合分布の周辺化を実行できる

メッセージ交換に基づく周辺分布の計算

• 結合分布の周辺化をベイジアンネットワーク上でのメッセージパッシングアルゴリズムの形で見直してみる
• 各ノードは隣接したノードから送られてくる局所積和に基づいて研鑽して隣接した送り先ノードへ送る
• 変数Aを根 (root) とした変数Aの周辺分布計算の計算木と見ることもできる

ファクターグラフとsum-productアルゴリズム

• n変数関数の因子分解の構造をグラフ化したものがファクターグラフである

多変数関数の周辺化問題

ファクターグラフ

sum-productアルゴリズム

• 積操作 (product operation)
• 和操作 (sum operatin)
• sum-productアルゴリズムはループがある場合には，正確に計算できる保証はないが，周辺化関数の近似計算アルゴリズムとして利用できる

sum-productアルゴリズムに関する研究の流れ

• 隠れマルコフモデルに対する前向き後ろ向きアルゴリズム (BCJRアルゴリズム)
• Viterbiアルゴリズム
• ターボ復号法 (turbo decoding)
• ''belief propagation''
• カルマンフィルタ (Kalman filter)

文献案内

---

↑低密度パリティ検査符号とその復号法