浅谈概率图模型(二)：无向图模型

admin管理员组

文章数量:1530518

文章目录

• 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(θ)1​c∈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(θ)1​exp(−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》
《统计学方法，李航》

本文标签： 模型浅谈概率