求解边缘概率
p
(
x
a
)
=
∑
x
╲
x
α
p(\bf{x_a}) = \sum_{\bf{x \diagdown x_{\alpha}}}
p(xa)=x╲xα∑
求最大后验概率状态
X
∗
=
arg max
x
∈
χ
p
(
x
)
X^{*} = \argmax_{\bf{x}\in \chi} p(\bf{x})
X∗=x∈χargmaxp(x)
求归一化因子
Z
=
∑
x
∏
c
ϕ
c
(
x
c
)
Z = \sum_{\bf{x}} \prod_{c} \phi_c(\bf{x}_c)
Z=x∑c∏ϕc(xc)
概率推理是核心问题, 概率推理相当于模型求解;
通过从联合概率分布逐步消除变量, 来求解边缘概率
(就是最基础的 P ( A , B ) = ∑ C 、 D P ( A , B , C , D ) P(A, B)=\sum_{C、D}P(A,B,C,D) P(A,B)=∑C、DP(A,B,C,D) 的形式)
我们从例子来理解变量消元算法
考虑这样一个链式MRF
P ( E ) ∝ ∑ D ∑ C ∑ B ∑ A P ~ ( A , B , C , D , E ) = ∑ D ∑ C ∑ B ∑ A ϕ 1 ( A , B ) ϕ 2 ( B , C ) ϕ 3 ( C , D ) ϕ 4 ( D , E ) = ∑ D ∑ C ∑ B ϕ 2 ( B , C ) ϕ 3 ( C , D ) ϕ 4 ( D , E ) ( ∑ A ϕ 1 ( A , B ) ) 注意 = ∑ D ∑ C ∑ B ϕ 2 ( B , C ) ϕ 3 ( C , D ) ϕ 4 ( D , E ) τ 1 ( B ) = ∑ D ∑ C ϕ 3 ( C , D ) ϕ 4 ( D , E ) ∑ B ϕ 2 ( B , C ) τ 1 ( B ) = ⋯ = τ 4 ( E ) ⇒ 归 一 化 ⇒ 概 率 值 \begin{aligned} P(E) &\propto \sum_D \sum_C \sum_B \sum_A \tilde{P}(A,B,C,D,E)\\ &= \sum_D \sum_C \sum_B \sum_A \phi_1(A,B) \phi_2(B,C) \phi_3(C,D) \phi_4(D,E) \\ &= \sum_D \sum_C \sum_B \phi_2(B,C) \phi_3(C,D) \phi_4(D,E)(\sum_A \phi_1(A,B)) & \text {注意}\\ &= \sum_D \sum_C \sum_B \phi_2(B,C) \phi_3(C,D) \phi_4(D,E)\tau_1(B) \\ &= \sum_D \sum_C \phi_3(C,D) \phi_4(D,E) \sum_B \phi_2(B,C)\tau_1(B) \\ &= \cdots \\ &= \tau_4(E) \\ &\Rightarrow 归一化 \Rightarrow 概率值 \end{aligned} P(E)∝D∑C∑B∑A∑P~(A,B,C,D,E)=D∑C∑B∑A∑ϕ1(A,B)ϕ2(B,C)ϕ3(C,D)ϕ4(D,E)=D∑C∑B∑ϕ2(B,C)ϕ3(C,D)ϕ4(D,E)(A∑ϕ1(A,B))=D∑C∑B∑ϕ2(B,C)ϕ3(C,D)ϕ4(D,E)τ1(B)=D∑C∑ϕ3(C,D)ϕ4(D,E)B∑ϕ2(B,C)τ1(B)=⋯=τ4(E)⇒归一化⇒概率值注意
注意
考虑这样一个贝叶斯网络
消元顺序: C,D,I,H,G,S,L
P ( J ) = ∑ L , S , G , H , I , D , C ϕ C ( C ) ϕ D ( C , D ) ϕ I ( I ) ϕ G ( G , I , D ) ϕ S ( S , I ) ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) = ∑ L , S , G , H , I , D ϕ I ( I ) ϕ G ( G , I , D ) ϕ S ( S , I ) ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) ∑ C ϕ C ( C ) ϕ D ( C , D ) = ∑ L , S , G , H , I , D ϕ I ( I ) ϕ G ( G , I , D ) ϕ S ( S , I ) ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) τ 1 ( D ) = ∑ L , S , G , H , I ϕ I ( I ) ϕ S ( S , I ) ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) ∑ D ϕ G ( G , I , D ) τ 1 ( D ) = ∑ L , S , G , H , I ϕ I ( I ) ϕ S ( S , I ) ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) τ 2 ( G , I ) = ∑ L , S , G , H ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) ∑ I ϕ I ( I ) ϕ S ( S , I ) τ 2 ( G , I ) = ∑ L , S , G , H ϕ L ( L , G ) ϕ J ( J , L , S ) ϕ H ( H , G , J ) τ 3 ( G , S ) = ⋯ = τ 7 ( J ) ( 因 为 贝 叶 斯 网 络 中 的 势 函 数 就 是 条 件 概 率 , 无 需 归 一 化 , 所 以 t a u 7 ( J ) 就 是 P ( J ) \begin{aligned} P(J) &= \sum_{L,S,G,H,I,D,C} \phi_C(C)\phi_D(C,D)\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J) \\ &= \sum_{L,S,G,H,I,D}\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{C}\phi_C(C)\phi_D(C,D) \\ &= \sum_{L,S,G,H,I,D}\phi_I(I)\phi_G(G,I,D)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_1(D) \\ &= \sum_{L,S,G,H,I}\phi_I(I)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{D}\phi_G(G,I,D)\tau_1(D) \\ &= \sum_{L,S,G,H,I}\phi_I(I)\phi_S(S,I)\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_2(G,I) \\ &= \sum_{L,S,G,H}\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\sum_{I}\phi_I(I)\phi_S(S,I)\tau_2(G,I) \\ &= \sum_{L,S,G,H}\phi_L(L,G)\phi_J(J,L,S)\phi_H(H,G,J)\tau_3(G,S) \\ &= \cdots \\ &= \tau_7(J) {(因为贝叶斯网络中的势函数就是条件概率, 无需归一化, 所以tau_7(J)就是P(J)}\\ \end{aligned} P(J)=L,S,G,H,I,D,C∑ϕC(C)ϕD(C,D)ϕI(I)ϕG(G,I,D)ϕS(S,I)ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)=L,S,G,H,I,D∑ϕI(I)ϕG(G,I,D)ϕS(S,I)ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)C∑ϕC(C)ϕD(C,D)=L,S,G,H,I,D∑ϕI(I)ϕG(G,I,D)ϕS(S,I)ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)τ1(D)=L,S,G,H,I∑ϕI(I)ϕS(S,I)ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)D∑ϕG(G,I,D)τ1(D)=L,S,G,H,I∑ϕI(I)ϕS(S,I)ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)τ2(G,I)=L,S,G,H∑ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)I∑ϕI(I)ϕS(S,I)τ2(G,I)=L,S,G,H∑ϕL(L,G)ϕJ(J,L,S)ϕH(H,G,J)τ3(G,S)=⋯=τ7(J)(因为贝叶斯网络中的势函数就是条件概率,无需归一化,所以tau7(J)就是P(J)
C,D,I,H,G,S,L
步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
---|---|---|---|---|
1 | C | ϕ C ( C ) ϕ D ( C , D ) \phi_C(C)\phi_D(C,D) ϕC(C)ϕD(C,D) | C,D | τ 1 ( D ) \tau_1(D) τ1(D) |
2 | D | τ 1 ( D ) ϕ G ( G , I , D ) \tau_1(D)\phi_G(G,I,D) τ1(D)ϕG(G,I,D) | G,I,D | τ 2 ( G , I ) \tau_2(G,I) τ2(G,I) |
3 | I | τ 2 ( G , I ) ϕ I ( I ) ϕ S ( S , I ) \tau_2(G,I)\phi_I(I)\phi_S(S,I) τ2(G,I)ϕI(I)ϕS(S,I) | G,S,I | τ 3 ( G , S ) \tau_3(G,S) τ3(G,S) |
4 | H | ϕ H ( H , G , J ) \phi_H(H,G,J) ϕH(H,G,J) | H,G,J | τ 4 ( G , J ) \tau_4(G,J) τ4(G,J) |
5 | G | τ 3 ( G , S ) τ 4 ( G , J ) ϕ L ( L , G ) \tau_3(G,S)\tau_4(G,J)\phi_L(L,G) τ3(G,S)τ4(G,J)ϕL(L,G) | S,G,J,L | τ 5 ( S , L , J ) \tau_5(S,L,J) τ5(S,L,J) |
6 | S | τ 5 ( S , L , J ) ϕ J ( J , L , S ) \tau_5(S,L,J)\phi_J(J,L,S) τ5(S,L,J)ϕJ(J,L,S) | S,L,J | τ 6 ( L , J ) \tau_6(L,J) τ6(L,J) |
7 | L | τ 6 ( L , J ) \tau_6(L,J) τ6(L,J) | L,J | τ 7 ( J ) \tau_7(J) τ7(J) |
G,I,S,L,H,C,D
这里就不再写公式了, 直接用表格展示
步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
---|---|---|---|---|
1 | G | ϕ G ( G , I , D ) ϕ L ( L , G ) ϕ H ( H , G , J ) \phi_G(G,I,D)\phi_L(L,G)\phi_H(H,G,J) ϕG(G,I,D)ϕL(L,G)ϕH(H,G,J) | G,I,D,L,H,J | τ 1 ( I , D , L , H , J ) \tau_1(I,D,L,H,J) τ1(I,D,L,H,J) |
2 | I | ϕ I ( I ) ϕ S ( S , I ) τ 1 ( I , D , L , H , J ) \phi_I(I)\phi_S(S,I)\tau_1(I,D,L,H,J) ϕI(I)ϕS(S,I)τ1(I,D,L,H,J) | S,I,D,L,H,J | τ 2 ( D , L , S , H , J ) \tau_2(D,L,S,H,J) τ2(D,L,S,H,J) |
3 | S | ϕ J ( J , L , S ) τ 2 ( D , L , S , H , J ) \phi_J(J,L,S)\tau_2(D,L,S,H,J) ϕJ(J,L,S)τ2(D,L,S,H,J) | S,D,L,H,J | τ 3 ( D , L , H , J ) \tau_3(D,L,H,J) τ3(D,L,H,J) |
4 | L | τ 3 ( D , L , H , J ) \tau_3(D,L,H,J) τ3(D,L,H,J) | D,L,H,J | τ 4 ( D , H , J ) \tau_4(D,H,J) τ4(D,H,J) |
5 | H | τ 4 ( D , H , J ) \tau_4(D,H,J) τ4(D,H,J) | D,H,J | τ 5 ( D , J ) \tau_5(D,J) τ5(D,J) |
6 | C | τ 5 ( D , J ) ϕ C ( C ) ϕ D ( C , D ) \tau_5(D,J)\phi_C(C)\phi_D(C,D) τ5(D,J)ϕC(C)ϕD(C,D) | D,J,C | τ 6 ( D , J ) \tau_6(D,J) τ6(D,J) |
7 | D | τ 6 ( D , J ) \tau_6(D,J) τ6(D,J) | D,J | τ 7 ( J ) \tau_7(J) τ7(J) |
可以看到, 这种消元方法:在前面几步的时候运算量很大, 就有可能增加算法的复杂度, 但是具体增加还是减少要具体分析, 下面会分析算法复杂度;
算法
:变量消元法
S
u
m
−
P
r
o
d
u
c
t
−
V
E
(
Φ
,
Z
)
Sum-Product-VE(\Phi,Z)
Sum−Product−VE(Φ,Z)
/
i
n
p
u
t
:
Φ
为
因
子
集
,
Z
为
消
元
变
量
集
1
令
变
量
消
元
顺
序
为
Z
1
,
…
,
Z
k
2
f
o
r
i
=
1
…
k
Φ
←
S
u
m
−
P
r
o
d
u
c
t
−
E
l
i
m
i
n
a
t
e
−
V
a
r
(
Φ
,
Z
i
)
每次消一个元
3
r
e
t
u
r
n
∏
ϕ
∈
Φ
ϕ
\begin{aligned} &\qquad /input: \Phi为因子集, Z为消元变量集\\ &\mathbf{1} 令变量消元顺序为Z_1, \ldots, Z_k\\ &\mathbf{2} \quad for \quad i=1\ldots k \\ & \qquad\qquad \Phi \leftarrow Sum-Product-Eliminate-Var(\Phi, Z_i) &\text{每次消一个元}\\ &\mathbf{3} \quad return \prod_{\phi\in\Phi}\phi \end{aligned}
/input:Φ为因子集,Z为消元变量集1令变量消元顺序为Z1,…,Zk2fori=1…kΦ←Sum−Product−Eliminate−Var(Φ,Zi)3returnϕ∈Φ∏ϕ每次消一个元
S
u
m
−
P
r
o
d
u
c
t
−
E
l
i
m
i
n
a
t
e
−
V
a
r
(
Φ
,
Z
)
Sum-Product-Eliminate-Var(\Phi, Z)
Sum−Product−Eliminate−Var(Φ,Z)
/
i
n
p
u
t
:
Φ
为
因
子
集
,
Z
为
消
元
变
量
1
Φ
′
←
{
ϕ
∈
Φ
:
Z
∈
S
c
o
p
e
[
ϕ
]
}
从因子集中挑出与消元变量Z有关的因子
2
Φ
′
′
←
Φ
−
Φ
′
因子集做差:与消元变量Z无关的因子
3
ψ
←
∏
ϕ
∈
Φ
′
ϕ
对每种情况的势函数做连乘
4
τ
←
∑
Z
ψ
将所有情况加起来
5
r
e
t
u
r
n
Φ
′
′
∪
{
τ
}
返回消元后的因子集
\\ \begin{aligned} &\qquad /input: \Phi为因子集, Z为消元变量\\ &\mathbf{1} \Phi' \leftarrow \{\phi\in\Phi:Z\in Scope[\phi]\}& \text {从因子集中挑出与消元变量Z有关的因子}\\ &\mathbf{2} \Phi'' \leftarrow \Phi-\Phi'&\text{因子集做差:与消元变量Z无关的因子}\\ &\mathbf{3} \psi \leftarrow \prod_{\phi\in\Phi'}\phi &\text{对每种情况的势函数做连乘}\\ &\mathbf{4} \tau \leftarrow\sum_{Z}\psi &\text{将所有情况加起来}\\ &\mathbf{5} \quad return \;\Phi'' \cup \{\tau\}&\text{返回消元后的因子集} \end{aligned}
/input:Φ为因子集,Z为消元变量1Φ′←{ϕ∈Φ:Z∈Scope[ϕ]}2Φ′′←Φ−Φ′3ψ←ϕ∈Φ′∏ϕ4τ←Z∑ψ5returnΦ′′∪{τ}从因子集中挑出与消元变量Z有关的因子因子集做差:与消元变量Z无关的因子对每种情况的势函数做连乘将所有情况加起来返回消元后的因子集
团树传播算法和变量消元算法在本质上是一样的, 从不同角度出发;
变量消元算法把全局概率推理转化为局部因子之间的乘积和求和运算
; 团树传播算法先构造一个团树, 把概率推理计算转化为团树节点之间的消息传递, 消息传递本质上也是因子之间的乘积和求和运算;
问题: 既然是一样的, 为什么要创建一个这样的算法?
因为当实现变量消元算法的时候, 其实要构造图来进行变量消元, 而这个图经过优化之后就是团树传播算法;
对于给定的概率图模型, 因子集 Φ = { ϕ } \Phi = \{\phi\} Φ={ϕ},变量集为 χ \chi χ。聚类图是定义在概率图模型上的一个无向图, 每个节点 i i i是变量集的子集, 即 C i ⊆ χ C_i\subseteq\chi Ci⊆χ。 聚类图必须满足
族保持
, 即每个因子 ϕ \phi ϕ必须与一个节点 C i C_i Ci关联, 使得 S c o p e [ ϕ ] ⊆ C i Scope[\phi]\subseteq C_i Scope[ϕ]⊆Ci。 一对节点 C i C_i Ci和 C j C_j Cj之间的每条边与一个割集 S i , j S_{i,j} Si,j关联, 其中 S i , j ⊆ C i ∩ C j S_{i,j}\subseteq C_i\cap C_j Si,j⊆Ci∩Cj;
步骤 | 消元变量 | 涉及因子 | 涉及变量 | 新因子 |
---|---|---|---|---|
1 | C | ϕ C ( C ) ϕ D ( C , D ) \phi_C(C)\phi_D(C,D) ϕC(C)ϕD(C,D) | C,D | τ 1 ( D ) \tau_1(D) τ1(D) |
2 | D | τ 1 ( D ) ϕ G ( G , I , D ) \tau_1(D)\phi_G(G,I,D) τ1(D)ϕG(G,I,D) | G,I,D | τ 2 ( G , I ) \tau_2(G,I) τ2(G,I) |
3 | I | τ 2 ( G , I ) ϕ I ( I ) ϕ S ( S , I ) \tau_2(G,I)\phi_I(I)\phi_S(S,I) τ2(G,I)ϕI(I)ϕS(S,I) | G,S,I | τ 3 ( G , S ) \tau_3(G,S) τ3(G,S) |
4 | H | ϕ H ( H , G , J ) \phi_H(H,G,J) ϕH(H,G,J) | H,G,J | τ 4 ( G , J ) \tau_4(G,J) τ4(G,J) |
5 | G | τ 3 ( G , S ) τ 4 ( G , J ) ϕ L ( L , G ) \tau_3(G,S)\tau_4(G,J)\phi_L(L,G) τ3(G,S)τ4(G,J)ϕL(L,G) | S,G,J,L | τ 5 ( S , L , J ) \tau_5(S,L,J) τ5(S,L,J) |
6 | S | τ 5 ( S , L , J ) ϕ J ( J , L , S ) \tau_5(S,L,J)\phi_J(J,L,S) τ5(S,L,J)ϕJ(J,L,S) | S,L,J | τ 6 ( L , J ) \tau_6(L,J) τ6(L,J) |
7 | L | τ 6 ( L , J ) \tau_6(L,J) τ6(L,J) | L,J | τ 7 ( J ) \tau_7(J) τ7(J) |
由变量消元构造团树
注意:
节点1虽然看上去是C、D, 但是C、D本身没有含义, 节点其实是
ϕ
C
(
C
)
ϕ
D
(
C
,
D
)
\phi_C(C)\phi_D(C,D)
ϕC(C)ϕD(C,D)
每个节点 i i i是变量集的子集, 即 C i ⊆ χ C_i\subseteq\chi Ci⊆χ
对应回上图发现, 每个节点都是变量集 { C , D , I , H , G , S , L } \{C,D,I,H,G,S,L\} {C,D,I,H,G,S,L}的子集
即每个因子 ϕ \phi ϕ必须与一个节点 C i C_i Ci关联, 使得 S c o p e [ ϕ ] ⊆ C i Scope[\phi]\subseteq C_i Scope[ϕ]⊆Ci
以
3:G、I、S
为例, 因子 ϕ I ( I ) 、 ϕ S ( S , I ) \phi_I(I)、\phi_S(S,I) ϕI(I)、ϕS(S,I)与该节点关联
一对节点 C i C_i Ci和 C j C_j Cj之间的每条边与一个割集 S i , j S_{i,j} Si,j关联, 其中 S i , j ⊆ C i ∩ C j S_{i,j}\subseteq C_i\cap C_j Si,j⊆Ci∩Cj
以
1:C、D
和2:D、I、G
为例, 边是 D D D,而 D ⊆ { C 、 D } ∩ { D 、 I 、 G } D\subseteq \{C、D\}\cap \{D、I、G\} D⊆{C、D}∩{D、I、G}
回想变量消元法的过程, 如第一步:消去变量C, 那就对涉及C、D的因子做乘积求和, 然后C的信息就蕴含在新因子 τ 1 ( D ) \tau_1(D) τ1(D)中了;
那么后续第二步, 当想消去变量D的时候, 因为与变量C有关的那部分D的信息蕴含在
τ
1
(
D
)
\tau_1(D)
τ1(D)中了, 所以这个因子就作为一个消息传递到2:D、I、G
中;
关键还是要理解前面的注意
:
进而:
1:C、D
也可以属于2:D、I、G
(根据定义判断即可), 所以这个新因子就充当了消息传递的边出现;又因为:
性质1: 树状图, 在变量消元过程中, 每个中间因子被使用一次, 每个聚类图的节点传递一个消息给唯一的另一个节点, 因此整个变量消元的过程产生的聚类图为一个树状图(因为树的特点就是: N个点的树有N-1条边, 就是连接N个点的最小边数);
性质2: 族保持(每个因子 ϕ \phi ϕ必须与一个节点 C i C_i Ci关联, 使得 S c o p e [ ϕ ] ⊆ C i Scope[\phi]\subseteq C_i Scope[ϕ]⊆Ci), 概率图模型的每个因子必须出现在某个消元步骤, 所以满足族保持性质;
性质3:执行交叉性质(对于聚类图, 如果对于任意变量 X ∈ C i , X ∈ C j X\in C_i, X\in C_j X∈Ci,X∈Cj, 若 X X X也出现在两个节点之间唯一路径上的两个节点, 则该聚类图满足执行交叉性质)
团树
如果聚类图满足上述三个性质, 则聚类图定义为团树;
显然, 由变量消元法得到的聚类图为团树;
(算法)
团树传播算法
计算变量X的边缘概率
输入: 变量消元法的结果(包括消元顺序, 涉及变量, 涉及因子, 新因子)
输出: X的边缘概率
- 利用变量消元构造团树, 团树节点势函数初始化
- 选取变量X所在的节点作为根节点
- 计算叶子节点到根节点的消息
- 根节点的势函数乘以来自邻接点的消息
- 计算变量X所在节点的边缘概率
注意
之所以能把X作为根节点, 是因为树就是有这个特性, 树的任意一个节点都能作为根节点;
利用变量消元构造团树
团树节点势函数初始化
选取最右边那个空的节点作为根节点
计算叶节点到根节点的消息
δ
i
→
j
=
∑
C
i
−
S
i
,
j
∏
k
∈
(
N
b
C
r
−
{
j
}
)
δ
k
→
i
\delta_{i \rightarrow j} = \sum_{C_i-S_{i,j}}\prod_{k\in(Nb_{C_r}-\{j\})}\delta_{k \rightarrow i}
δi→j=Ci−Si,j∑k∈(NbCr−{j})∏δk→i
δ 1 → 2 ( D ) = ∑ C ψ 1 ( C 1 ) \delta_{1 \rightarrow 2}(D) = \sum_{C}\psi_1(C_1) δ1→2(D)=∑Cψ1(C1)
δ 2 → 3 ( G , I ) = ∑ D ψ 2 ( C 2 ) × δ 1 → 2 \delta_{2 \rightarrow 3}(G,I) = \sum_{D}\psi_2(C_2)\times\delta_{1 \rightarrow 2} δ2→3(G,I)=∑Dψ2(C2)×δ1→2
δ 3 → 5 ( G , S ) = ∑ I ψ 3 ( C 3 ) × δ 2 → 3 \delta_{3 \rightarrow 5}(G,S) = \sum_{I}\psi_3(C_3)\times\delta_{2 \rightarrow 3} δ3→5(G,S)=∑Iψ3(C3)×δ2→3
δ 4 → 5 ( G , J ) = ∑ H ψ 4 ( C 4 ) × δ 2 → 3 \delta_{4 \rightarrow 5}(G,J) = \sum_{H}\psi_4(C_4)\times\delta_{2 \rightarrow 3} δ4→5(G,J)=∑Hψ4(C4)×δ2→3
δ 5 → 6 ( J , S , L ) = ∑ G ψ 5 ( C 5 ) × δ 4 → 5 × δ 3 → 5 \delta_{5 \rightarrow 6}(J,S,L) = \sum_{G}\psi_5(C_5)\times\delta_{4 \rightarrow 5}\times\delta_{3 \rightarrow 5} δ5→6(J,S,L)=∑Gψ5(C5)×δ4→5×δ3→5
δ 6 → 7 ( J , L ) = ∑ S ψ 6 ( C 6 ) × δ 5 → 6 \delta_{6 \rightarrow 7}(J,L) = \sum_{S}\psi_6(C_6)\times\delta_{5 \rightarrow 6} δ6→7(J,L)=∑Sψ6(C6)×δ5→6
P ( J ) = ∑ L δ 5 → 6 P(J) = \sum_{L}\delta_{5 \rightarrow 6} P(J)=∑Lδ5→6
说白了就是变量消元法的程序实现罢了;
一种很自然的想法就是, 对所有节点作为根节点, 多次计算边缘概率;
但是有更好的方法, 基于树的特性:
画图来说明:
变量消元法与团树传播算法就是这样了, 继续下一章吧!pd的Machine Learning