確率伝搬法
類似のアルゴリズムとしては一般にビタビアルゴリズムが挙げられる。ビタビアルゴリズムはmax-productあるいはmin-sumアルゴリズムとしても知られており、関連するモデルの最大化問題を解く。具体的には、このアルゴリズムは周辺分布を求めるのではなく、大域的関数を最大化される値 x {\displaystyle \mathbf {x} } を求める。これは確率的に尤も起こりうる値を選択することと等価であり、arg max記号を用いて定義できる:
arg  max x g ( x ) . {\displaystyle \arg \max _{\mathbf {x} }g(\mathbf {x} ).}
この問題の解法としては確率伝搬法とほぼ等価であり、和の記号を最大値に置き換えるだけでよい。
グラフィカルモデル上での周辺化や最大化のような推定問題は、厳密解や相対誤差以下の近似解を得ようとした場合においてNP困難な問題である。正確には、上で定義された周辺化の問題は#P完全であり、最大化はNP完全である。
計算が完了した後、各々のノードの周辺分布は隣接している因子ノードからのメッセージの積に比例する:
p X v ( x v ) ∝ ∏ u ∈ N ( v ) μ u → v ( x v ) . {\displaystyle p_{X_{v}}(x_{v})\propto \prod _{u\in N(v)}\mu _{u\to v}(x_{v}).}
同様に、ある因子に属している変数の集合の周辺分布は、変数からのメッセージとその因子の積に比例する:
p X u ( x u ) ∝ f u ( x u ) ∏ v ∈ N ( u ) μ v → u ( x u ) . {\displaystyle p_{X_{u}}(\mathbf {x} _{u})\propto f_{u}(\mathbf {x} _{u})\prod _{v\in N(u)}\mu _{v\to u}(x_{u}).}
これらの計算は数学的帰納法によって証明できる。