確率伝播法とその応用

目次 (2023/8/17 ver.0.02)

1番目のタブが選択された！

1.What's New

確率伝播アルゴリズム(belief propagation algorithm)とは

ベイジアンネットにおいて、確率変数の事後確率を効率的に計算するアルゴリズム
  • 確率伝搬法 (Belief Propagation. BP) と呼ばれる手法が工学や統計物理など様々な分野で注目されている.
  • これは複数の確率変数の結合 (同時) 密度関数から各確率変数の周辺事後分布を効率的に求めるための手法であり, 1980 年代に人工知能の分野で「J. Pea,rl」によって提案された のが最初とされている.
  • 確率伝搬法では, 密度関数をベイジアンネットワークやファクターグラフなどのグラフで記述し, そのグラフ上での局所的なメッセージの交換及び処理を行うことで大域的な確率推論を行う.
  • グラフが木構造のときにのみ厳密解が得られるが, ループが存在する場合にも多くの応用例において良好な結果が得られることが経験的に知られている.
  • また,興味深いことは様々な分野でこれまでに提案され用いられている多くの手法が, 確率伝搬法と同じ原理で説明されることである.
  • 例えば, 以下のような例は、確率伝搬法を用いて説明することが出来る.
    • シャノン限界に迫る符号として注目されているターボ符号や低密度パリティ検査 (Low-Density Parity Check,LDPC) 符号などの復号法
    • 隠れマルコフモデルに対する前向き後ろ向き (BahlCocke-Jelinek-Raviv, BCJR) アルゴリズム
    • カルマンフィルタ
    • 高速フーリエ変換
  • 本稿では, ファクターグラフ上の sum-product アルゴリズム及びベイジアンネットワーク上での Pearl のBP アルゴリズムについて説明することで, 確率伝搬法の基本的な考え方およびその原理を解説する.
  • さらに, 誤り訂正符号の最大事後確率復号アルゴリズムや高速フーリエ変換 (fast Fourier transform, FFT) アルゴリズムなどが確率伝搬法を用いて説明できることを示すことで確率伝搬法の応用例についても紹介する.

2.確率伝搬法

本稿で取り扱う確率伝搬法は効率的に確率推論問題を解くための手法である.

そこでまず、ここで考える確率推論問題の定式化を行ない, 分配法則に基づく確率伝搬法の計算原理について説明する

もくじ

2.1 確率推論問題と確率伝搬法の原理

確率推論問題とは
  • 「$X_{1},\ldots ,X_{N}$」をランダム変数とし. その結合 (同時) 密度関数を

    • $\Large \displaystyle p(x_{1},\ldots,x_{N}) \equiv Pr\{X_{1}=x_{1}, \ldots, X_{N}=x_{N}\}$

  • と定義する. このとき本稿で考える確率推論問題は次のように定義される.
  • 【確率推論問題】: ランダム変数「$X_{1},\ldots ,X_{N}$」のうち、「$X_{m+1},\ldots,X_{N}$」の観測値「$a_{m+1},,\ldots,a_{N}$」が与えられた時、 非観測値の周辺確率

    • $\Large \displaystyle Pr(X_i=a|X_{m+1}=a_{m+1},\ldots,X_{N}=a_{N})\ \ \ \ i=1,\ldots,m\ \ \ \ (2)$

  • を計算すること。
  • (2) を直接計算して $x_{1}$ を評価しようとすると

    • $\Large \displaystyle Pr(X_1=a|X_{m+1}=a_{m+1},\ldots,X_{N})=\alpha\sum_{x_2,\ldots, x_m}p(a,x_2,\ldots,x_m,a_{m+1},\ldots,a_N)$

  • となるが(「$\alpha$」は規格化定数), 各「$X_i$」が「$q$」通りの値を取り得る場合およそ「$q^{m-1}$」回の演算が必要となり,「$m$」について指数オーダーの計算量となる.
  • このことは, 「$m$」が大きい問題 (例えば誤り訂正符号の復号問題では数千) では, (2) を直接評価することが困難であることを意味する.
  • そこで結合密度関数を分解することを考える.
  • ベイズ則を繰り返し用いることで, 結合密度関数は一般に

    • $\Large \displaystyle p(x_1,\ldots,x_N)=p(x_1)p(x_2,\ldots,x_N|x_1)$

    $\Large \displaystyle =p(x_1)p(x_2|x_1)p(x_3,\ldots,x_N|x_1,x_2)$

    $\Large \displaystyle \ \ \ \ \ \vdots$

    $\Large \displaystyle =p(x_1)p(x_2|x_1)p(x_3|x_1, x_2)\ldots p(x_N|x_1,x_2,\ldots,x_{N-1})\ \ \ \ (3)$

  • のように書くことができる.
  • これだけでは当然計算量の削減に繋がらないが, ここで注意すべき重要な点は
  • 「多くの工学的な応用において (3) の条件付き分布の条件は必ずしも全てが有効ではない (考慮すべきランダム変数の中に独立なのものも存在する)」
  • ということである.
  • この性質を利用することで, 周辺事後確率計算の演算量を削減することができる.
  • 5つのランダム変数「$x_1, \ldots,x_{5}$」 の結合密度関数を考え、以下が、それぞれ、独立であるとすると
    • 「$x_{2}$」と「$x_{4}$」
    • 「$x_{3}$」と「$x_{1}$」及び「$x_{2}$」
    • 「$x_{5}$」と「$x_1$」及び「$x_{2}$」及び「$x_{3}$」

    $\Large \displaystyle p(x_1,x_2,x_3,x_4,x_5)$

    $\Large =\displaystyle p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)p(x_4|x_1,x_2,x_3)p(x_5|x_1,x_2,x_3,x_4)$

    $\Large =\displaystyle p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)p(x_4|x_1,x_3)p(x_5|x_4)$

2.2 ファクターグラフ

ファクターグラフの接続ルール
  • 本稿で考える確率伝搬法のアルゴリズム (sum-product ブルゴリズム) は, ファクターグラフ上のメッセージパッシングアルゴリズムとして記述される.
  • ファクターグラフは多変数関数の因子分解を表す無向グラフであり, 2 種類のノードすなわち「関数ノード」と「変数ノード」からなる.
  • 変数の集合を「$X=\{x_{1}, x_{2}, \ldots, x_{n}\}$」とし、多変数関数が、

    • $\Large \displaystyle f(X)=f(x_1,\cdots,x_n)$

    $\Large \displaystyle =f_1(A_1)f_2(A_2)\cdots f_m(A_m)$

  • のように因子分解されるとする. ただし, 「$A_{1}, A_{2}\cdots, A_{m}$」は「$X$」の部分集合である.
  • このとき, 関数ノードと変数ノードは, それぞれローカル関数「$f_{i}(A_{i})$」と変数「$x_{j}$」に対応する.
  • そして,「$f_{i}(\lrcorner 4_{i})$」に対応する関数ノードと「$A_{i}$」に含まれる変数に対応する変数ノードとがエッジで接続されることによりグラフが構成される (図 1 参照) .

    • 図1 ファクターグラフの接続ルール
ファクターグラフの具体例（マルコフ連鎖モデル）
  • ファクターグラフの具体例としてマルコフ連鎖モデルを考えてみる.
  • マルコフ連鎖の結合密度関数は

    • $\Large \displaystyle p(x_1,x_2,\cdots,x_n)=p(x_1)p(x_2|x_1)p(x_3|x_2)\cdots p(x_{n}|x_{n-1})$

  • であるため, これを変数が 「$x_{1},$ $x_{2},$ $\ldots,$ $x_{n}$」の多変数関数とみなし, 「$p(x_{1})$」を「$f_{1}(x_{1})$」, 「$p(x_{i}.|x_{i-1})$」を「$f_{i}(x_{i-1}, x_{i}),\ i=2,\ldots,n$」 と対応づけることで結合密度関数は

    • $\Large \displaystyle p(x_1,x_2,\cdots,x_n)=f_1(x_1)f_2(x_1, x_2)f_3(x_2, x_3)\cdots f_n(x_{n-1}, x_n)$

  • と書ける. これよりマルコフ連鎖のファクターグラフは図2 のようになる.

    • 図2 ファクターグラフの例 (マルコフ連鎖)
ファクターグラフの具体例（その他）
  • 同様に考えて, 結合密度関数が

    • $\Large \displaystyle p(x_1,x_2,x_3,x4,x_5)=p(x_1)p(x_2|x_1)p(x_3|x_4)p(x_4|x_1)p(x_5|x_4)$

  • で与えられる場合は.

    • $\Large \displaystyle f(x_1,x_2,x_3,x4,x_5)=f_1(x_1)f_2(x_1,x_2)f_4(x_3,x_4)f_3(x_1, x_4)f_5(x_4, x_5)$

  • ととみなすことで, ファクターグラフは図 3 のようになる.

    • 図3 ファクターグラフの例（その他）

2.3 「sum-product」アルゴリズム

「sum-product」アルゴリズムとは
  • 「sum-product」アルゴリズムは、木構造をもつファクターグラフで表現された多変数関数

    • $\Large \displaystyle f(X)=f(x_1, x_2,\ldots, x_n)$

    $\Large \displaystyle =f_1(A_1)f_2(A_2)\ldots f_m(A_m)$

  • の周辺化関数

    • $\Large \displaystyle g_i(x_i)=\sum_{X\backslash x_i}f(X)$

  • をファクターグラフ上で分散的に計算するメッセージパッシングアルゴリズムである.
  • ただし, 「$X\backslash x_{i}$」は、変数「$x_{i}$」以外について周辺化することを意味する.
  • 以下では, ファクターグラフは木構造であるとし, ループが存在する場合については別途考察する.
  • 周辺化関数計算の手順は以下のようである:
    1. 「$f(X)=f(x_{1}, x_{2}, \ldots, x_{n})$」からファクターグラフを作成する
    2. 求めたい周辺化関数を「$g_{r}(x_{r})$」とするとき, 変数ノード「$x_{r}$ 」をルートとする木としてファクターグラフを描き直す
    3. 木の下側のノードから上のノードの順に次に説明する各ノードでの処理ルールに従って計算する
「sum-product」アルゴリズム (変数ノードでの処理)
  • 変数ノード「$x_k$」から関数ノード「$f_i$」へ送るメッセージは、以下のように計算される（図4）.

    • $\Large \displaystyle M_{x_k,f_k}(x_k)=\prod_{a\in N(x_k)\backslash f_i}M_{a,x_k}(x_k)$

  • ただし、「$N(x_k)$」は、変数ノード「$x_k$」に接続するノードの集合であり、「$M_{a,x_k}(x_k)$」は、 ノード「$a$」から「$x_k$」に届いたメッセージを表す。
  • また、「$x_k$」が葉のときは、

    • $\Large \displaystyle M_{x_k,f_k}(x_k)=1$


    図4 「sum-product」アルゴリズム (変数ノードでの処理)
「sum-product」アルゴリズム (関数ノードでの処理)

    • 図5 「sum-product」アルゴリズム (関数ノードでの処理)

3.確率伝播アルゴリズムとは

もくじ

3.1 確率伝播アルゴリズム(belief propagation algorithm)とは

ベイジアンネットにおいて、確率変数の事後確率を効率的に計算するアルゴリズム
  • 「伝播」は正しくは「でんぱ」と読むが「でんぱん」と誤読されることも多い。
  • 「伝搬」は誤読に起因する誤字。
  • 信念伝播アルゴリズムとも訳される。

3.2 原理

  • 掛け算の足し算に対する分配法則：

    • $\Large \displaystyle a(b+c)=ab+ac$

  • 左辺は演算２回だが右辺は演算３回

    • $\Large \displaystyle a\sum_{i=1}^n b_i=\sum_{i=1}^n ab_i$

  • 左辺は演算 n 回だが右辺は 2n-1 回。
  • 因子の「括り出し」を積極的に適用すれば、事後確率計算に必要な演算数を劇的に減らせる。
  • さらに、演算の中間結果の重複計算を避けることで、効率を上げている。

3.3 簡単なベイジアンネットの例

  • 簡単なネットワークならば、それ専用の確率伝播アルゴリズムの導出は難しくない。

    • $\Large \displaystyle \boxed{A}\longrightarrow\boxed{B}\longrightarrow\boxed{C}\longrightarrow\boxed{D}$

  • このネットワークを例に、「$D$」 の観測値が与えられた時の事後確率「$P(A|D), P(B|D), P(C|D)$」を計算するアルゴリズムを導出してみる。

    • $\Large \displaystyle P(A,B,C,D)=P(D|C)P(C|B)P(B|A)P(A)$

3.4 事後確率の計算式

  • 正規化定数「$\alpha=P(D)$」 とすると、事後確率「$P(C|D)$」は、以下のように計算できる。

    • $\Large \displaystyle P(C|D)=\frac{P(C,D)}{P(D)}=\frac{1}{\alpha}\sum_B \sum_A P(A,B,C,D)$

    $\Large \displaystyle =\frac{1}{\alpha}\sum_B \sum_A (P(D|C)P(C|B)P(B|A)P(A))$

  • 「$P(D|C)$」は、「$B、A$」に依存しないので「$\sum_A \sum_B$」の外に括り出せる。
  • また「$P(C|B)$」は、「A$」に依存しないので「$\sum_A$」の外に括り出せる。
    • $\Large \displaystyle P(C|D)=\frac{1}{\alpha}P(D|C)\{ \sum_B P(C|B)\sum_A P(B|A)P(A)\}$

  • 正規化定数「$\beta=P(C)$」 とすると、事後確率「$P(B|D)$」は、以下のように計算できる。

    • $\Large \displaystyle P(B|D)=\frac{P(B,D)}{P(D)}=\frac{1}{\beta}\sum_B \sum_A P(A,B,C,D)$

4.SwitchBotセンサー

4.1 参照URL

UUID:「cba20d00-224d-11e6-9fb8-0002a5d5c51b」

4.2 人感センサー

ServiceData
  • Byte0: 73
  • Byte1: 40
  • Byte2: 64
    • bit1: 1=人の動きを検知、0=人の動きを不検知
  • Byte3: 00
  • Byte4: 42
    • 動体を検出してからの時間（秒）
  • Byte5: 01
    • bit6: 明るい
    • bit7: 暗い

5.隠れマルコフモデル