文章目录
- 1.引入无向图
- 1.1有向图的困境
- 1.2有向图和无向图得粗略对比
- 2. 无向图的一些条件独立性质
- 2.1 全局马尔可夫性质(关键性质)
- 2.2 无向图的局部马尔科夫性质
- 2.3 成对马尔科夫性质
- 2.4 性质总结
- 3. 无向图模型的参数
- 3.1 无向图模型的一个弊端
- 3.2 解决方案
- 3.2.1 团与最大团的定义
- 3.2.2 势函数(potential function)
- 3.2.3 Hammersley-Clifford定理
- 4. 无向图模型和统计物理学之间的联系
- 参考文献
1.引入无向图
1.1有向图的困境
- 对于一些领域来说,有向图模型表现得就会很尴尬,例如在为图像建模时,我们肯定假设相邻像素的强度值是相关的,如果使用有向图模型,不但把相邻节点包含进来,还包含一些其他节点(Markov Blanket,参考深入理解概率图模型(一))。这就比较尴尬,这时候我们就要考虑无向图模型了,我们可以用一种图来说明以下:
1.2有向图和无向图得粗略对比
- 相比有向图,无向图得主要优点有是:无向图的边是对称的,这对某些领域,例如图像处理很有用
- 相比有向图,无向图的主要缺点是:
①这些参数的可解释性较差,模块化程度也较低;
②参数估计的计算成本更高
2. 无向图的一些条件独立性质
2.1 全局马尔可夫性质(关键性质)
- 对于节点集合A,B,C,当且仅当C把A、B进行分离时,A⊥B|C.
这句话意思就是说:把集合C中所有节点都去掉之后,A,B之间没有任何连接。
这个性质被称为无向图的全局马尔科夫性质(Global Markov Property for UGMs) - 举个栗子:
{
1
,
2
}
⊥
{
6
,
7
}
∣
{
3
,
4
,
5
}
\{ 1,2\} \bot \{ 6,7\} |\{ 3,4,5\}
{1,2}⊥{6,7}∣{3,4,5}
2.2 无向图的局部马尔科夫性质
- 在无向图中,一个节点的马尔可夫毯子(Markov Blanket)就是该节点的直接邻居,根据Markov Blanket的定义,我们有:
t ⊥ V \ c l ( t ) ∣ m b ( t ) t \bot V\backslash cl(t)|mb(t) t⊥V\cl(t)∣mb(t)
c l ( t ) ≜ m b ( t ) ∪ { t } cl(t) \triangleq mb(t) \cup \{ t\} cl(t)≜mb(t)∪{t}
2.3 成对马尔科夫性质
- 从局部马尔科夫性质我们可以推到出成对马尔科夫性质,他是这样定义的:
对于任意两个没有边连接的节点,给定剩下的节点,则这两个节点条件独立,即
s ⊥ t ∣ V \ { s , t } ⇔ G s t = 0 s \bot t|V\backslash \{ s,t\} \Leftrightarrow {G_{st}} = 0 s⊥t∣V\{s,t}⇔Gst=0
2.4 性质总结
- 很明显,全局马尔可夫(G)隐含局部马尔可夫,局部马尔可夫(L)隐含成对马尔可夫§。
- 可以证明,他们是等价的,即
G ⇔ L ⇔ P G \Leftrightarrow L \Leftrightarrow P G⇔L⇔P
3. 无向图模型的参数
3.1 无向图模型的一个弊端
- 尽管无向图模型的条件独立性质比(CI)有向图模型要简单的多,但是,在表示联合概率时,无向图就很逊色,这也是无向图的一个弊端。
3.2 解决方案
3.2.1 团与最大团的定义
- 无向图G中任何两个节点均有边连接的节点子集称为团(Clique)。若C是无向图G的一个团,并且不能再加进去任何一个G的节点使其成为一个更大的团,则称C为最大团(Maximual clique)
3.2.2 势函数(potential function)
- 我们在图G中的每一个最大团定义一个势函数,我们将最大团c的势函数表示为如下:
ψ c ( y c ∣ θ c ) {\psi _c}({y_c}|{\theta _c}) ψc(yc∣θc)
- 势函数可以为关于参数的任意非负函数。
- 从而我们将联合概率分布定义为:正比于所有团上势函数的乘积
3.2.3 Hammersley-Clifford定理
- 一个正的分布p(y) > 0 满足无向图G的条件独立性质当且仅当p可以被表示为因子的乘积,每一项因子为一个最大团上的势函数乘积,即
p
(
y
∣
θ
)
=
1
Z
(
θ
)
∏
c
∈
C
ψ
c
(
y
c
∣
θ
c
)
p(y|\theta ) = \frac{1}{{Z(\theta )}}\prod\limits_{c \in C} {{\psi _c}({y_c}|{\theta _c})}
p(y∣θ)=Z(θ)1c∈C∏ψc(yc∣θc)
其中,C是(最大)团的集合,Z(θ)是归一化因子也成为划分函数,定义如下:
Z ( θ ) ≜ ∑ x ∏ c ∈ C ψ c ( y c ∣ θ c ) Z(\theta ) \triangleq \sum\limits_x {\prod\limits_{c \in C} {{\psi _c}({y_c}|{\theta _c})} } Z(θ)≜x∑c∈C∏ψc(yc∣θc)
4. 无向图模型和统计物理学之间的联系
- 无向图模型和统计物理学有着很深的联系。具体地,有一个模型叫做吉布斯分布(Gibbs distribution),它可以被写成如下形式:
p
(
y
∣
θ
)
=
1
Z
(
θ
)
exp
(
−
∑
c
E
(
y
c
∣
θ
c
)
)
p(y|\theta ) = \frac{1}{{Z(\theta )}}\exp ( - \sum\limits_c {E({y_c}|{\theta _c})} )
p(y∣θ)=Z(θ)1exp(−c∑E(yc∣θc))
其中E(yc)>0,是关于团c中变量的一种能量,我们可以把这个模型转换为无向图模型(UGMs)通过定义势函数如下:
ψ
c
(
y
c
∣
θ
c
)
=
exp
(
−
∑
c
E
(
y
c
∣
θ
c
)
)
{\psi _c}({y_c}|{\theta _c}) = \exp ( - \sum\limits_c {E({y_c}|{\theta _c})} )
ψc(yc∣θc)=exp(−c∑E(yc∣θc))
我们看到高概率态对应于低能组态。这种模型经常被应用在物理学中(Ising Model)
- 有一点需要注意以下:我们可以自由地将参数化限制在图的边,而不是最大团,这个性质被称为逐对马尔可夫随机场(Pairwise MRFs)
p
(
y
∣
θ
)
∝
ψ
12
(
y
1
,
y
2
)
ψ
13
(
y
1
,
y
3
)
ψ
23
(
y
2
,
y
3
)
ψ
24
(
y
2
,
y
4
)
.
.
.
ψ
35
(
y
3
,
y
5
)
p(y|\theta ) \propto {\psi _{12}}({y_1},{y_2}){\psi _{13}}({y_1},{y_3}){\psi _{23}}({y_2},{y_3}){\psi _{24}}({y_2},{y_4})...{\psi _{35}}({y_3},{y_5})
p(y∣θ)∝ψ12(y1,y2)ψ13(y1,y3)ψ23(y2,y3)ψ24(y2,y4)...ψ35(y3,y5)
这种形式由于它的简单性被被广泛的应用,但它不作为联合概率的一般形式。
参考文献
《Machine Learning A Probability Perspective》
《统计学方法,李航》
更多推荐
浅谈概率图模型(二):无向图模型
发布评论