ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)」の解説
ガウシアン確率伝搬法は確率伝搬法アルゴリズムの別形であり、対象の分布がガウス分布である場合の確率伝搬法を指している。このようなモデルに対する解析は、初めにWeissとFreemanによって行われた。 まず、GaBPアルゴリズムでは以下の周辺化問題について解く: P ( x i ) = 1 Z ∫ j ≠ i exp ( − 1 / 2 x T A x + b T x ) d x j {\displaystyle P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-1/2x^{T}Ax+b^{T}x)\,dx_{j}} ここでZは正規化定数、Aは対称正定値行列(分散共分散の逆行列や精度行列としても知られている)、bはシフトベクトルとする。 このようなガウシアンモデルの下では、周辺分布の最大値を推定値とする問題はMAP推定問題と等価である: argmax x P ( x ) = 1 Z exp ( − 1 / 2 x T A x + b T x ) . {\displaystyle {\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-1/2x^{T}Ax+b^{T}x).} 同様に、このMAP推定問題は以下の二次形式の最小化問題と等価である: min x 1 / 2 x T A x − b T x . {\displaystyle {\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.} 最終的に、これは以下の線形方程式の解と等価である: A x = b . {\displaystyle Ax=b.} GaBPアルゴリズムの収束性は(一般的な確率伝搬法の場合と比較して)解析が容易であり、2種類の十分条件が知られている。一つはWeissが2000年に定式化した条件であり、Aが対角優位行列である場合に関して収束性が保証されている。二つめは2006年にJohnsonらが定式化した条件であり、行列のスペクトル半径が下式を満たしている場合に収束する。 ρ ( I − | D − 1 / 2 A D − 1 / 2 | ) < 1 {\displaystyle \rho (I-|D^{-1/2}AD^{-1/2}|)<1\,} ここで、D = diag(A)である。 GaBPアルゴリズムは線形代数の領域と関連がある。具体的には、GaBPアルゴリズムはAが情報行列でbがシフトベクトルである場合の線形方程式Ax=bを解くための反復アルゴリズムとして見ることができる。GaBPアルゴリズムの収束条件はヤコビ法の十分条件と等価であり、かつ、GaBPアルゴリズムの収束速度はヤコビ法、ガウス=ザイデル法、SOR法などといった古典的な反復手法よりも早いことが経験的に知られている。さらに、GaBPアルゴリズムは共役勾配法の条件下で発生する、計算上の問題に対して耐性があることが示されている。
※この「ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)」の解説は、「確率伝搬法」の解説の一部です。
「ガウシアン確率伝搬法(Gaussian Belief Propagation, GaBP)」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
- ガウシアン確率伝搬法のページへのリンク