这本书把置信传播算法讲的非常清楚。所以这里mark一下。以下阅读请先知道链式有向图前后向算法的原理。

前向后向算法

记链式有向图隐变量为$w_{1.... N}$w1....N​，已知的观测值为$x_{1...N}$x1...N​.
其中，前向函数$f_n(w_n)=P(x_{1...n}, w_n)$fn​(wn​)=P(x1...n​,wn​)，后向函数$b_n(w_n) = P(x_{n+1...N}|w_n)$bn​(wn​)=P(xn+1...N​∣wn​). 进而：
$P(w_n|x_{1... N}) \propto P(w_n, x_{1...n})P(x_{x_{n+1...N}|w_n}) = f_n(w_n)b_n(w_n)$P(wn​∣x1...N​)∝P(wn​,x1...n​)P(xxn+1...N​∣wn​​)=fn​(wn​)bn​(wn​)

置信传播

前向后向算法是置信传播的一个特例，$f_n,b_n$fn​,bn​被视为传达关于变量信息。
和积算法是一种置信传播算法，可以很容易地从链式模型扩展到树模型。该算法在因子图上进行。因子图属于二部图(Bipartite Graph)。存在两类节点：

• 变量节点$z$z，如$w_i$wi​, $x_i$xi​
• 函数节点$g$g ，如有向图中$P(w_1|w_2, w_3)$P(w1​∣w2​,w3​)或无向图中$\phi(w_1, w_2, w_3$ϕ(w1​,w2​,w3​

变量节点所代表的变量是函数节点的自变量。同类节点之间没有边直接相连。
和积算法分两个过程，前向过程通过图分发信息，后向过程对信息进行校验。每一条边准确连接到一个变量节点，“消息”在变量的域上定义。
有三种类型的消息：

1. 从一个未观测变量$z_p$zp​到一个函数节点$g_q$gq​，消息为：
   $m_{z_p \rightarrow g_q} = \prod_{r \in ne[p] \backslash q} m_{g_r \rightarrow z_p} \tag{1}$mzp​→gq​​=r∈ne[p]\q∏​mgr​→zp​​(1)
   其中$ne[p]$ne[p]是$z_p$zp​的邻居节点集合。
   从未观测变量传到函数的消息是该变量的所有其他邻居传来消息的点乘，是其他置信度的组合。

2. 从一个已观测变量$z_p=z_p^*$zp​=zp∗​到一个函数节点$g_q$gq​，消息为：
   $m_{z_p \rightarrow g_q} = \delta(z_p^*) \tag{2}$mzp​→gq​​=δ(zp∗​)(2)
   从观测变量到函数的消息是该变量观测值的置信度。

3. 从函数节点$g_p$gp​到接收变量$z_q$zq​，消息为：
   $m_{g_p \rightarrow z_q} = \sum_{ne[p] \backslash q}g_p(ne[p]) \prod_{r\in ne[p] \backslash q}m_{z_r \rightarrow g_p} \tag{3}$mgp​→zq​​=ne[p]\q∑​gp​(ne[p])r∈ne[p]\q∏​mzr​→gp​​(3)
   需要该函数节点的其他邻居节点传来的置信度，并用函数$g_p$gp​转换为$z_q$zq​的置信度

最后，节点$z_p$zp​的边缘分布可用所有同时从前向过程和后向过程传入的消息乘积
$P(z_p) \propto \prod_{r \in ne[p]} m_{g_r \rightarrow z_p} \tag{4}$P(zp​)∝r∈ne[p]∏​mgr​→zp​​(4)

链式有向图

前向过程

• 对于$m_{x_1\rightarrow g_1}$mx1​→g1​​，使用规则2
  $m_{x_1\rightarrow g_1} = \delta (x_1^*)$mx1​→g1​​=δ(x1∗​)
• 对于$m_{g_1\rightarrow w_1}$mg1​→w1​​，使用规则3
  $m_{g_1\rightarrow w_1}=\int P(x_1|w_1)\delta(x_1^*) dx_1 = P(x_1 = x_1^*|w_1)$mg1​→w1​​=∫P(x1​∣w1​)δ(x1∗​)dx1​=P(x1​=x1∗​∣w1​)
• 对于$m_{w_1\rightarrow g_{1,2}}$mw1​→g1,2​​，使用规则1
  $m_{w_1\rightarrow g_{1,2}} = P(x_1=x_1^*|w_1)$mw1​→g1,2​​=P(x1​=x1∗​∣w1​)
• 对于$m_{g_{1,2}\rightarrow w_{2}}$mg1,2​→w2​​，使用规则3
  $m_{g_{1,2}\rightarrow w_{2}}=\sum_{w_1} P(w_2|w_1)P(x_1 = x_1^*|w_1)$mg1,2​→w2​​=w1​∑​P(w2​∣w1​)P(x1​=x1∗​∣w1​)

对于$m_{x_2\rightarrow g_2}$mx2​→g2​​和$m_{g_2\rightarrow w_2}$mg2​→w2​​与上述第1、2条类似

• 对于$m_{w_2 \rightarrow g_{2, 3}}$mw2​→g2,3​​，使用规则1
  $m_{w_2 \rightarrow g_{2, 3}}=P(x_2=x_2^*|w_2)\sum_{w_1} P(w_2|w_1)P(x_1=x_1^*|w_1)$mw2​→g2,3​​=P(x2​=x2∗​∣w2​)w1​∑​P(w2​∣w1​)P(x1​=x1∗​∣w1​)
  注意，$m_{w_n \rightarrow g_{n, n+1}}$mwn​→gn,n+1​​即$f_n(w_n)=P(x_{1...n, w_n})$fn​(wn​)=P(x1...n,wn​​)

反向过程

$m_{w_N \rightarrow g_{N, N-1}}=P(x_N=x_N^*|w_N)$mwN​→gN,N−1​​=P(xN​=xN∗​∣wN​)
$m_{g_{N, N-1} \rightarrow w_{N-1}}=\sum_{w_N} P(w_N|w_{N-1})P(x_N = x_N^*|w_N)$mgN,N−1​→wN−1​​=wN​∑​P(wN​∣wN−1​)P(xN​=xN∗​∣wN​)
通常情况下有
$m_{g_{n, n-1}\rightarrow w_{n-1}}=\sum_{w_n} P(w_n|w_{n-1})P(x_n|w_n)m_{g_{n+1,n} \rightarrow w_n} =b_{n-1}(w_{n-1})$mgn,n−1​→wn−1​​=wn​∑​P(wn​∣wn−1​)P(xn​∣wn​)mgn+1,n​→wn​​=bn−1​(wn−1​)

计算边缘

利用式(4)，
$\begin{aligned} P(w_n|x_{1...N}) & \propto \prod_{m \in ne[n]} m_{g_m \rightarrow w_n} \\ &=m_{g_{n-1, n}\rightarrow w_n} m_{g_{n}\rightarrow w_n}m_{g_{n, n+1}\rightarrow w_n} \\ &=m_{w_{n}\rightarrow g_{n, n+1}}m_{g_{n, n+1}\rightarrow w_n} \\ &= f_n(w_n)b_n(w_n) \end{aligned}$P(wn​∣x1...N​)​∝m∈ne[n]∏​mgm​→wn​​=mgn−1,n​→wn​​mgn​→wn​​mgn,n+1​→wn​​=mwn​→gn,n+1​​mgn,n+1​→wn​​=fn​(wn​)bn​(wn​)​
上式第3行利用了规则1。

树模型

对于该树模型，注意$w_2, w_4, w_5$w2​,w4​,w5​之间的关系。

无向图