概率图模型

Posted on Edited on In Views: Symbols count in article: 6.5k Reading time ≈ 6 mins.

CRF & MRF

I. Introduction

​ 本文是早期被挂在Github🔗: Enigmatisms/Algorithm Plus上的一篇学习总结。写这篇学习笔记的时候博客还没有诞生，也刚刚熟练掌握Typora。本文相当于是考古post，虽然古老，但我发现当年的我学习热情也还是挺高的，这篇笔记可以说是写得不错的一个概率图模型入门文章了（开始自夸，尽管UGM部分没写完）。

​ 可能我最近还是要重新学一下概率图模型:

一个概率图模型，上面的所有结点构成了所有随机变量的联合分布。需要表达的就是联合分布。--早期HQY的理解

​ 之前应该只是清楚了其中的一些概念，但是并没有产生深入的理解，比如MRF与置信传播的原理以及具体的应用方式等等（虽然已经是很老的传统方法了）。方法老归老，思想本质有启发意义就是好的。

II. DGM

2.1 DGM 中三种典型结构的理解

​ DGM(Directed Graph Model)。又叫贝叶斯网络。

graph LR

A[A Intelligence]-->B[B GPA]
A-->C[C Innovative prop.]

2.1.1 结构一 Tail to Tail (单父，多子)

  • 当观测到A，B与C之间独立（不存在关系，没有可以有信息推断）
  • 没有观测到A，B，C之前可以有隐含的关系，不独立

举个例子：

  • A智力，B成绩，C创新力。当不知道A时，我们可以隐含地推定，当一个人成绩高，说明他创新能力高的概率很大（概率推断），反之亦然
  • 而如果GPA，创新力只受到智力一个因素的影响时，已知A，那么GPA和创新力就毫无关系了。因为这两个因素B,C已经确定了，再进行概率推断已经没有意义了（信息量为0）.如果这个例子不好理解，那么还有一个例子：
  • A 今天下雨，B明天下雨，C今天地面湿。其中，A（下雨）有80%可能导致积水（C），20%可能导致不积水（\(\overline C\)），50%下雨（B）。那么A未知时，地面湿时（假设C发生），可以反推A是否发生，再反推B是否发生，反过来也一样。
  • 但是如果A发生了，那么C与B只与A当前事实有关，已经不会受到来自B或者C的推断影响了！（影响消除）。
  • A的观测会导致B,C的相互独立（信息的互不影响性）

2.1.2 结构二 Head to Tail （典型的因果关系）

graph LR

A[A Diffculty]-->B[B Grade]
B-->C[C Recommendation]

B为关键结点。当：

  • B没有被观测，A和C是可以有推断关系（信息关联性）的，不独立
  • B被观测：A与C独立，A已经不影响C的发生了

可以用马尔可夫链的想法来理解！历史事件的无后效性！当 当前不确定时，由于历史状态可以确定当前状态，那么相当于历史可以影响未来（下一状态）。而当前状态已知的话，历史信息已经不起作用力，下一状态完全由当前状态决定。

例子：

  • 不知道成绩的情况下，如果考试的难度大，那么每个人在考好的情况下获得推荐的概率都大。
  • 但是知道了成绩的话，收益就和风险没关系了。你考得好就能获得推荐，考不好就不行。

2.1.3 结构三 Head to Head （汇点）

graph LR

A[A Difficulty]-->C[C Grade]
B[B Intelligence]-->C

C为关键节点。当：

  • C没有被观测：那么A和B互相不影响（因为缺少信息判断A与B的相互影响性），结果未知，原因互相产生的影响不可知。条件独立
  • C被观测到：A与B存在联系的结果，可以A->B推断或者反之。

例子：

  • 考试成绩不清楚的时候，每个人的智力 / 考试难度两者之间如果也未知，知道其中一个也推不出另一个来。
  • 但是如果已知成绩，比如：成绩普遍很好。那么由B，比如某个人的智力不行，但是成绩好，可以推定A（难度低），反之，如果成绩普遍很差，由B（高智力），可以推知A（难度高）。

以上这三种有向图结构，可以方便进行条件独立判定以及信息关联性的快速区分，判定两个随机变量之间是否存在关联时可以应用。联系例子即可。

  • 每个节点：都是一个随机变量，一般未知，需要从信息中推断
  • 每个有向弧：都是条件概率。A发生时，C存在概率发生，则A->C有弧。

2.2 条件独立与马尔可夫链

条件独立： \[ \begin{equation} P(X,Y|Z)=P(X|Z)P(Y|Z) \end{equation} \] ​ 在Z发生的情况下，X，Y同时发生的概率为分别概率的积。可以写成另一种形式： \[ \begin{equation} P(X|Y,Z)=\frac{P(X,Y,Z)}{P(Y,Z)}=\frac{P(X,Y|Z)P(Z)}{P(Y|Z)P(Z)}=\frac{P(X,Y|Z)}{P(Y|Z)}=P(X|Z) \end{equation} \] ​ 这最能直接说明条件独立的意义：给定条件Y,Z，若X,Y条件独立，Y条件不影响X事件，可以直接从条件中删除。而CRF中的有向边表征了条件概率，对应地，结点间关系（以上三种模式）表征了条件独立性。

​ 如果两个结点之间的中间结点已经完全确定，已经没有 不通过中间已经观测结点 的直连路径或者间接路径了，此时两个结点条件独立。而条件独立可以用于理解Markov链： \[ \begin{equation} P(x_t)=P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)...P(x_t|x_1,x_2,...x_{t-1}) \end{equation} \] ​ 这个是普通的链式法则。而由于一阶马尔可夫假设：历史不影响未来，过去的状态与未来条件独立。那么可以简化链式法则为： \[ \begin{equation} P(x_t)=P(x_1)P(x_2|x_1)P(x_3|x_2)...P(x_t|x_{t-1})=P(x_1)\prod_{i=1}^tP(x_{i}|x_{i-1}) \end{equation} \] ​ 这可以大大简化运算以及储存难度。

2.3 使用例子理解DGM / 马尔可夫毯

朴素贝叶斯就是个很典型的DGM例子。朴素（naive）就naive在：

基于特征条件独立假设的分类器。

​ 特征条件独立这个假设很强了，一般做不到。但是在DGM中可以表示为：

graph TB

A[Label]-->B[Feature 1]
A-->C[Feature 2]
A-->D[Feature 3]
A-->E[...]

​ 给定Label后，所有的Features毫无关联（Tail to Tail 结构）。

2.3.1 马尔可夫毯

​ 马尔可夫毯说的是这样一个集合：集合\(\Pi(t)\)表征了，当我们对集合\(\Pi(t)\)内的所有随机变量进行观测，那么会导致结点t与剩下的结点之间完全条件独立（啊，被孤立了，相当于\(\Pi(t)\)把t墙了）。例子：

graph LR

A(1)-->B(2)
A-->C(3)
B-->D(5)
C-->D
B-->E(4)
C-->F(6)
E-->G(7)
D-->F
D-->G
F-->G

​ 那么对于结点5，其马尔可夫毯为？

  • 首先2，3给定之后，由于2，3为5的父结点，2，3的观测导致5与1的独立
  • 此后是5与4的独立：有赖于2的给定。
  • 观测本身会导致被观测变量与其父节点或者子结点独立！不确定性消除。故5建立6，7的观测，6，7要给定。
  • 但是给定了7，在5，7，4形成了一个Head to Head 结构。会导致5和4的不独立，那么需要给定4以消除不确定性的方式终结。
  • 最后的毯子是：\({\{2,3,4,6,7\}}\)

2.3.2 DGM到底能干什么

​ 多个变量错综复杂的因果关系，相互有影响。一个变量的改变可能导致整个网络（说到网络就会形成一个高维结构了，之所以是高维，指的是这个图可能不是平面图，不一定表达的就是二维关系）内部的变量发生连锁变化。那么为了解决有条件独立 / 条件概率联系起来的多个网络变量，需要使用这个方法。

2.3.3 有向图的概率表示

由条件概率的定义，联合概率可以由边缘 / 条件表示。在有向图中，由于有向图对条件概率进行建模（每一条边就是一个条件概率关系），那么使用有向图如何表示概率？举个例子：

graph LR

A((X1))-->B((X2))
B-->C((X3))
B-->D((X4))
C-->E((X5))
D-->E

​ 如果需要使用有向图关系表示\(\{x_1,x_2,x_3,x_4,x_5\}\)的联合概率分布，如何写出这个表达式？（给定顶层结点，也就是起源结点\(x_1\)的初始分布\(P(x_1)\)），则表达式为： \[ \begin{equation} P(x_1,x_2,x_3,x_4,x_5)=P(x_1)P(x_2|x_1)\rightarrow? \end{equation} \] ​ 之后，\(x_3\) \(x_4\)是乘法关系还是加法关系？首先可以肯定，接下来的概率表达式是\(P(x_4|x_2)\)与\(P(x_3|x_2)\)（由于\(x_2\)的存在，导致\(x_1\)，\(\{x_3,x_4\}\)条件独立），个人认为，此处\(x_5\)的产生是\(\{x_3,x_4\}\)共同作用的结果。比如说，考试：\(\{x_3,x_4\}\)分别表示难度以及学生智力，\(x_5\)为分数。产生分数必须要有前两个因素，故此处虽然是两个通路，但是仍然是乘法原则起作用（与事件）（可能隐含表达了，DGM中子结点需要所有父结点成立而产生） \[ \begin{equation} P(x_1,x_2,x_3,x_4,x_5)=P(x_1)P(x_2|x_1)P(x_3|x_2)P(x_4|x_2)P(x5|x_3,x_4) \end{equation} \] ​ 一个更加复杂的例子：

graph LR

A((X1))
B((X2))
C((X3))
D((X4))
E((X5))
F((X6))
G((X7))
A-->D
A-->E
B-->D
C-->D
C-->E
D-->F
D-->G
E-->G

​ 可以立即得到联合分布：（不仔细推了） \[ \begin{equation} P(x_1,...x_7)=P(x_1)P(x_2)P(x_3)P(x_4|x_1,x_2,x_3)P(x_5|x_1,x_3)P(x_6|x_4)P(x_7|x_4,x_5) \end{equation} \]

​ 这样的联合概率求解规律是可以推广的。

III. 无向图模型（UGM）

3.1 基本概念

​ 区别于有向图模型（DGM），无向图模型不是对因果关系进行建模。

​ 无向图和有向图的区别是什么？有向图表征了因果关系，并且连接有方向性，导致了处理图像这样的问题时，不方便进行建模。

graph LR

1-->4
2-->5
3-->6
1-->2
2-->3

4-->5

5-->6

4-->7
5-->8
6-->9
7-->8
8-->9

​ 可以看出，在对有向图进行建模时，如果要进行条件独立分析（比如我们要单独分析5与其他的结点的条件独立性）。需要寻找马尔可夫毯，那么在有向图中，除了\(\{2,4,6,8\}\)之外，实际上还有别的结点，而\(\{2,4,6,8\}\)是1阶邻域，在图像处理中比较常见求一阶邻域与中心点间的关系。而此处，要加入\(\{3,7\}\)结点（Head to Head，由于给定了8，5与7不再条件独立，需要给定7，3的话同理）。那么显然我们加入了奇怪的点，导致分析存在一些问题，并且与有向图网络的生成方向还存在关系。

​ 而使用无向图的话，由于结点之间是平等的，在无向图中的马尔可夫毯直接就是\(\{2,4,6,8\}\)。

​ 无向图中，存在三种独立性：

  1. 全局独立性（全局马尔可夫性）
graph LR

A((1))---B((2))
B---D((4))
A---C((3))
C---D
E((5))---A
D---F((6))

​ 当我们删除结点\(\{2,3\}\)时，可知集合\(\{1,5\}\)以及\(\{4,6\}\)之间完全没有联系了。删除两个结点之间的连通性结点，产生两个连通支，则这两个连通支 独立。

  1. 局部独立性（局部马尔可夫性）
graph TB

a((1))
b((2))
c((3))
d((4))
e((5))
f((6))
g((7))
a---b
a---c
a---d
a---e
c---f
e---g
b---f
d---g

​ 可知，当我们把2，3，4，5删去之后，1结点与所有其他结点完全没有联系了。1被孤立了，因为其马尔可夫毯已经被删除了。那么，1与其他结点条件独立。写为表达式可以如下：

​ 设\(V_k\)为我们探索的结点，\(V_M\)为\(V_k\)的马尔可夫毯的节点集合，而\(V_S\)为\(V_i\in \{V\}/\{V_M\cup V_k\}\)，则可知： \[ \begin{equation} V_k\perp V_S|V_M \end{equation} \] ​ 即给定马尔可夫毯，则对应结点和除其本身以及马尔可夫毯结点之外的所有结点条件独立。

  1. 成对独立性（成对马尔可夫性）

​ u，v为两个没有直连边的结点。去掉u，v之外的其他点，u，v条件独立。

3.2 团块（Clique）的概念

​ 如果一个结点集合内，任意两个结点之间存在连边，那么称这是一个团（Clique）。

​ 最大团：在一个团C外部任意找一个结点，加入此团后都会破坏团的性质（此结点与至少一个结点之间不存在连边）。也即外部已经不能再加入结点使团变大了。

​ 无向图模型中一般会涉及到大量结点，那么要表示这些结点的联合概率就十分麻烦。可以使用最大团来进行描述，将 无向图中的联合概率分布表示为极大团的势函数（Potential Function）的积。也即： \[ \begin{equation} P(x)=\frac{1}{Z}\prod_{i=1}^n\psi_i(x_i) \end{equation} \] ​ 上式中，\(\psi_i(x)\)表示极大团\(x_i\)的势函数，而Z则是归一化因子，为了使\(P(x)\)满足概率的归一化性质。归一化因子又叫做：配分函数（Partition Function），但是如何进行计算呢？举个例子（例子来自CSDN，但是感觉讲的不太清楚，我自己理解一下：）

2021.11.15补充：当时还会看粪坑CSDN呢。PS：参考的文献都没有记录。

graph TB

A((x1))
B((x2))
C((x3))
D((x4))
E((x5))
A---B
A---C
B---C
C---D
C---E

​ 可知，图中存在三个极大团：\(\{x_1, x_2, x_3\}\)，\(\{x_3,x_5\}\)，\(\{x_3, x_4\}\) (注意一个结点可以存在于多个极大团中！)。那么整个联合概率分布可以写为： \[ \begin{equation} P(x_1, x_2, x_3,x_4,x_5)=\frac 1Z\psi_1(x_1,x_2,x_3)\psi_2(x_3,x_5)\psi_3(x_3,x_4) \end{equation} \] ​ 那么Z应如何计算？需要对每个结点进行遍历。下式为每个结点所在极大团的势函数： \[ \begin{align} & x_1:\psi_1(x_1,x_2,x_3)\\ & x_2:\psi_1(x_1,x_2,x_3)\\ & x_3:\psi_1(x_1,x_2,x_3)\psi_2(x_3,x_5)\psi_3(x_3,x_4)\\ & x_4:\psi_3(x_3,x_4)\\ & x_5:\psi_2(x_3,x_5) \end{align} \] ​ 对每个结点进行求和归一化。为什么要这么做？为什么是对每一个结点结点所在团的势函数？而不是求每一个结点对应的某一个其他函数进行累加求和？

2021.11.15 补充：诶？我最后在这里写了一个开放性思考题？应该是原来我没想清楚，但是最后也没去想。