置信传播（Belief Propagation）与链式有向图模型前向后向算法——CVMLI Prince读书随笔第11章
这本书把置信传播算法讲的非常清楚。所以这里mark一下。以下阅读请先知道链式有向图前后向算法的原理。
前向后向算法记链式有向图隐变量为w1....Nw_{1.... N}w1....N，已知的观测值为x1...Nx_{1...N}x1...N.
其中，前向函数fn(wn)=P(x1...n,wn)f_n(w_n)=P(x_{1...n}, w_n)fn(wn)=P(x1...n,wn)，后向函数bn(wn)=P(xn+1...N∣wn)b_n(w_n) = P(x_{n+1...N}|w_n)bn(wn)=P(xn+1...N∣wn). 进而：
P(wn∣x1...N)∝P(wn,x1...n)P(xxn+1...N∣wn)=fn(wn)bn(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)
前向后向算法是置信传播的一个特例，fn,bnf_n,b_nfn,bn被视为传达关于变量信息。
和积算法是一种置信传播算法，可以很容易地从链式模型扩展到树模型。该算法在因子图上进行。因子图属于二部图(Bipartite Graph)。存在两类节点：
变量节点所代表的变量是函数节点的自变量。同类节点之间没有边直接相连。
和积算法分两个过程，前向过程通过图分发信息，后向过程对信息进行校验。每一条边准确连接到一个变量节点，“消息”在变量的域上定义。
有三种类型的消息：
从一个未观测变量zpz_pzp到一个函数节点gqg_qgq，消息为：
mzp→gq=∏r∈ne[p]\qmgr→zp(1)
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]ne[p]是zpz_pzp的邻居节点集合。
从未观测变量传到函数的消息是该变量的所有其他邻居传来消息的点乘，是其他置信度的组合。
从一个已观测变量zp=zp∗z_p=z_p^*zp=zp∗到一个函数节点gqg_qgq，消息为：
mzp→gq=δ(zp∗)(2)
m_{z_p \rightarrow g_q} = \delta(z_p^*) \tag{2}
mzp→gq=δ(zp∗)(2)
从观测变量到函数的消息是该变量观测值的置信度。
从函数节点gpg_pgp到接收变量zqz_qzq，消息为：
mgp→zq=∑ne[p]\qgp(ne[p])∏r∈ne[p]\qmzr→gp(3)
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)
需要该函数节点的其他邻居节点传来的置信度，并用函数gpg_pgp转换为zqz_qzq的置信度
最后，节点zpz_pzp的边缘分布可用所有同时从前向过程和后向过程传入的消息乘积
P(zp)∝∏r∈ne[p]mgr→zp(4)
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)
mx1→g1=δ(x1∗) m_{x_1\rightarrow g_1} = \delta (x_1^*) mx1→g1=δ(x1∗) 对于mg1→w1m_{g_1\rightarrow w_1}mg1→w1，使用规则3
mg1→w1=∫P(x1∣w1)δ(x1∗)dx1=P(x1=x1∗∣w1) 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) 对于mw1→g1,2m_{w_1\rightarrow g_{1,2}}mw1→g1,2，使用规则1
mw1→g1,2=P(x1=x1∗∣w1) m_{w_1\rightarrow g_{1,2}} = P(x_1=x_1^*|w_1) mw1→g1,2=P(x1=x1∗∣w1) 对于mg1,2→w2m_{g_{1,2}\rightarrow w_{2}}mg1,2→w2，使用规则3
mg1,2→w2=∑w1P(w2∣w1)P(x1=x1∗∣w1) 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)
对于mx2→g2m_{x_2\rightarrow g_2}mx2→g2和mg2→w2m_{g_2\rightarrow w_2}mg2→w2与上述第1、2条类似
对于mw2→g2,3m_{w_2 \rightarrow g_{2, 3}}mw2→g2,3，使用规则1mw2→g2,3=P(x2=x2∗∣w2)∑w1P(w2∣w1)P(x1=x1∗∣w1) 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)
注意，mwn→gn,n+1m_{w_n \rightarrow g_{n, n+1}}mwn→gn,n+1即fn(wn)=P(x1...n,wn)f_n(w_n)=P(x_{1...n, w_n})fn(wn)=P(x1...n,wn) 反向过程
mwN→gN,N−1=P(xN=xN∗∣wN)
m_{w_N \rightarrow g_{N, N-1}}=P(x_N=x_N^*|w_N)
mwN→gN,N−1=P(xN=xN∗∣wN)
mgN,N−1→wN−1=∑wNP(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 = x_N^*|w_N)
mgN,N−1→wN−1=wN∑P(wN∣wN−1)P(xN=xN∗∣wN)
通常情况下有
mgn,n−1→wn−1=∑wnP(wn∣wn−1)P(xn∣wn)mgn+1,n→wn=bn−1(wn−1)
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)，
P(wn∣x1...N)∝∏m∈ne[n]mgm→wn=mgn−1,n→wnmgn→wnmgn,n+1→wn=mwn→gn,n+1mgn,n+1→wn=fn(wn)bn(wn)
\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→wnmgn→wnmgn,n+1→wn=mwn→gn,n+1mgn,n+1→wn=fn(wn)bn(wn)
上式第3行利用了规则1。
对于该树模型，注意w2,w4,w5w_2, w_4, w_5w2,w4,w5之间的关系。
作者：叶萧不被占了吧
