概率图模型

一、概率图模型

1. 考虑三个随机变量 $a,b,c$ ，其联合概率分布为：

   $$P(a,b,c)=P(c\mid a,b)P(a,b)=P(c\mid a,b)P(b\mid a)P(a)$$

   • 对每个随机变量引入一个节点，然后为每个节点关联上式右侧对应的条件概率。

   • 对于每个条件概率分布，在图中添加一个链接（箭头）：箭头的起点是条件概率的条件代表的结点。

     对于因子 $P(a)$ ，因为它不是条件概率，因此没有输入的链接。

   • 如果存在一个从结点 $a$ 到结点 $b$ 的链接，则称结点 $a$ 是结点 $b$ 的父节点，结点 $b$ 是结点 $a$ 的子节点。

   • 可以看到，上式的左侧关于随机变量 $a,b,c$ 是对称的，但是右侧不是。

     实际上通过对 $P(a,b,c)$ 的分解，隐式的选择了一个特定的顺序（即 $a,b,c$ ）。如果选择一个不同的顺序，则得到一个不同的分解方式，因此也就得到一个不同的图的表现形式。

   

2. 对于 $K$ 个随机变量的联合概率分布，有：

   $$P(X_1,X_2,\cdots,X_K)=P(X_K\mid X_1,X_2,\cdots,X_{K-1})\cdots P(X_2\mid X_1)P(X_1)$$

   • 它对应于一个具有 $K$ 个结点的有向图。

     • 每个结点对应于公式右侧的一个条件概率分布。
     • 每个结点的输入链接包含了所有的编号低于它的结点。

   • 这个有向图是全链接的，因为每对结点之间都存在一个链接。

     实际应用中，真正有意义的信息是图中的链接的缺失，因为：

     • 全链接的计算量太大。
     • 链接的缺失代表了某些随机变量之间的不相关或者条件不相关。

   • 设节点 $X_i$ 的父节点集合为 $\Psi_{X_i}$，则所有随机变量的联合概率分布为：

     $$P(X_1,X_2,\cdots,X_K)=\prod_{k=1}^KP(X_k\mid \Psi_{X_k})$$

3. 前面讨论的是：每个结点对应于一个变量。可以很容易的推广到每个结点代表一个变量的集合（或者关联到一个向量）的情形。

   可以证明：如果上式右侧的每一个条件概率分布都是归一化的，则这个表示方法整体总是归一化的。

4. 概率图模型probabilistic graphical model 就是一类用图来表达随机变量相关关系的概率模型：

   • 用一个结点表示一个或者一组随机变量。
   • 结点之间的边表示变量间的概率相关关系。

   概率图描述了：联合概率分布在所有随机变量上能够分解为一组因子的乘积的形式，而每个因子只依赖于随机变量的一个子集。

5. 根据边的性质不同，概率图模型可以大致分为两类：

   • 使用有向无环图表示随机变量间的依赖关系，称作有向图模型或者贝叶斯网络Bayesian network。

     有向图对于表达随机变量之间的因果关系很有用。

   • 使用无向图表示随机变量间的相关关系，称作无向图模型或者马尔可夫网络Markov network 。

     无向图对于表达随机变量之间的软限制比较有用。

6. 概率图模型的优点：

   • 提供了一个简单的方式将概率模型的结构可视化。
   • 通过观察图形，可以更深刻的认识模型的性质，包括条件独立性。
   • 高级模型的推断和学习过程中的复杂计算可以利用图计算来表达，图隐式的承载了背后的数学表达式。

二、贝叶斯网络

1. 贝叶斯网络Bayesian network借助于有向无环图来刻画特征之间的依赖关系，并使用条件概率表Conditional Probability Table:CPT来描述特征的联合概率分布。

   这里每个特征代表一个随机变量，特征的具体取值就是随机变量的采样值。

2.1 条件独立性

1. 一个贝叶斯网 $\mathcal B$ 由结构 $\mathcal G$ 和参数 $\Theta$ 两部分组成，即 $\mathcal B=(\mathcal G,\Theta)$ ：

   • 网络结构 $\mathcal G$ 是一个有向无环图，其中每个结点对应于一个特征。

     若两个特征之间有直接依赖关系，则他们用一条边相连。

   • 参数 $\Theta$ 定量描述特征间的这种依赖关系。设特征 $X_i$ 在 $\mathcal G$ 中父节点的集合为 $\Psi_{X_i}$， 则 $\Theta$ 包含了该特征的条件概率表：

   $$\theta_{X_i\mid \Psi_{X_i}}=P(X_i\mid \Psi_{X_i})$$

2. 贝叶斯网结构有效地表达了特征间的条件独立性。

   给定父节点集，贝叶斯网络假设每个特征与它的非后裔结点表达的特征是相互独立的。于是有：

   $$P(\mathbb X)=P(X_1,X_2,\cdots,X_n)=\prod_{i=1}^{n}P(X_i\mid \Psi_{X_i})=\prod_{i=1}^{n}\theta_{X_i\mid \Psi_{X_i}}$$

   推导过程：

   $$P(\mathbb X)=P(X_1,X_2,\cdots,X_n)=P(X_1\mid X_2,\cdots,X_n)P(X_2,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2\mid X_3,\cdots,X_n)P(X_3,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2\mid \Psi_{X_2})P(X_3,\cdots,X_n)=\cdots$$

3. 贝叶斯网络中三个结点之间典型依赖关系如下图：

   

   • 同父结构：给定父节点 $X_1$ 的取值， 则 $X_2$ 与 $X_3$ 条件独立，即：
     
   $$P(X_2,X_3\mid X_1)=P(X_2\mid X_1)P(X_3\mid X_1)$$

   • 顺序结构：给定中间节点 $X_1$ 的取值， 则 $X_2$ 与 $X_3$ 条件独立，即：
     

     $$P(X_2,X_3\mid X_1)=P(X_2\mid X_1)P(X_3\mid X_1)$$

     即：在 $X_1$ 给定的条件下， $X_2,X_3$ 之间被阻断。因此它们关于 $X_1$ 条件独立。

   • V 型结构：给定子节点 $X_1$ 的取值，则 $X_2$ 与 $X_3$ 必定不是条件独立的。即： $P(X_2,X_3\mid X_1)\ne P(X_2\mid X_1)P(X_3\mid X_1)$ 。

     事实上 $X_2$ 与 $X_3$ 是独立的（但不是条件独立的），即 $P(X_2,X_3)=P(X_2)P(X_3)$ 。

4. 为了分析有向图中节点之间的条件独立性，可以使用有向分离技术：

   • 找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无向边。
   • 将所有的有向边改成无向边。

   这样产生的无向图称作道德图moral graph。父节点相连的过程称作道德化moralization。基于道德图能直观、迅速的找到结点之间的条件独立性。

2.2 网络的学习

1. 贝叶斯网络的学习可以分为参数学习和结构学习两部分

   • 参数学习比较简单。只需要通过对训练样本“计数”，估计出每个结点的条件概率表即可。

     但是前提是必须知道网络结构。

   • 结构学习比较复杂，结构学习被证明是NP难问题。

2. 贝叶斯网络的结构学习通常采用评分搜索 来求解。

   • 先定义一个评分函数，以此评估贝叶斯网络与训练数据的契合程度。然后基于这个评分函数寻找结构最优的贝叶斯网。

   • 最常用的评分函数基于信息论准则：将结构学习问题视作一个数据压缩任务。

     • 学习的目标是找到一个能以最短编码长度描述训练集数据集的模型。这就是最小描述长度 Minimal Description Length:MDL准则。
     • 此时的编码长度包括了：描述模型自身所需要的字节长度，和使用该模型描述数据所需要的字节长度。

3. 给定训练集 $\mathbb D=\{(\mathbf {\vec x}_1,y_1),(\mathbf {\vec x}_2,y_2),\cdots,(\mathbf {\vec x}_N,y_N)\}$，贝叶斯网络 $\mathcal B=(\mathcal G,\Theta)$ 在 $\mathbb D$ 上的评分函数定义为：

   $$score(\mathcal B\mid \mathbb D)=f(\theta) |\mathcal B|-L(\mathcal B\mid \mathbb D)$$

   其中： $f(\theta)$ 表示描述每个参数 $\theta$ 所需的字节数； $|\mathcal B|$ 是贝叶斯网络的参数个数；
   

   $$L(\mathcal B\mid\mathbb D)=\sum_{i=1}^{N}\log P(\mathbf {\vec x}_i)$$

   是贝叶斯网 $\mathcal B$ 的对数似然。因此：

   • 第一项 $f(\theta) |\mathcal B|$ 是计算编码贝叶斯网络 $\mathcal B$ 所需要的字节数。
   • 第二项 $-\sum_{i=1}^{N}\log P(\mathbf {\vec x}_i)$ 是计算 $\mathcal B$ 所对应的概率分布 $P$ 需要多少字节来描述 $\mathbb D$ 。

4. 现在结构学习任务转换为一个优化任务，即寻找一个贝叶斯网络 $\mathcal B$ 使评分函数 $score(\mathcal B\mid \mathbb D)$ 最小。

   问题是，从所有可能的网络结构空间中搜索最优贝叶斯网络结构是个NP难问题，难以快速求解。

   有两种方法可以在有限时间内求得近似解：

   • 贪心算法。如从某个网络结构出发，每次调整一条边，直到评分函数不再降低为止。
   • 增加约束。通过给网络结构增加约束来缩小搜索空间，如将网络结构限定为树形结构等。

5. 贝叶斯网络训练好之后就能够用来进行未知样本的预测。

   最理想的是直接根据贝叶斯网络定义的联合概率分布来精确计算后验概率，但问题是这样的“精确推断”已经被证明是NP难的。

   此时需要借助“近似推断”，通过降低精度要求从而在有限时间内求得近似解，常用的近似推断为吉布斯采样(Gibbs sampling)。

三、马尔可夫随机场

1. 根据前面的介绍，有向图模型可以将一组变量上的联合概率分布分解为局部条件概率分布的乘积。无向图模型也可以表示一个分解形式。

   马尔可夫随机场Markov Random Field:MRF是一种著名的无向图模型。

2. 现实任务中，可能只知道两个变量之间存在相关关系，但是并不知道具体怎样相关，也就无法得到变量之间的依赖关系。

   • 贝叶斯网络需要知道变量之间的依赖关系，从而对依赖关系（即条件概率）建模。

   • 马尔科夫随机场并不需要知道变量之间的依赖关系。它通过变量之间的联合概率分布来直接描述变量之间的关系。

     如： $X_1,X_2$ 两个变量的联合概率分布为：

     $X_1,X_2$	$P(X_1,X_2)$
     $X_1=0,X_2=0$	1000
     $X_1=0,X_2=1$	10
     $X_1=1,X_2=0$	20
     $X_1=1,X_2=1$	2000

     则这个分布表示：$X_1$ 和 $X_2$ 取值相同的概率很大。

   • 事实上这里的 $P(\cdot)$ 就是后面介绍的势函数。

     • 它们的总和不一定为 1 。即：这个表格并未定义一个概率分布，它只是告诉我们某些配置具有更高的可能性。
     • 它们并没有条件关系，它涉及到变量的联合分布的比例。

3. 马尔可夫随机场可以应用于图像问题中。

   • 每个像素都表示成一个节点，相邻像素之间相互影响。
   • 像素之间并不存在因果关系，它们之间的作用是对称的。因此使用无向图概率模型，而不是有向图概率模型。

3.1 马尔科夫性

1. 对结点 $A,B,C$ ，若去掉结点 $C$ 之后 $A,B$ 分属于两个联通分支，则称结点 $A,B$ 关于结点 $C$ 条件独立，记作 $A \perp B \mid C$ 。

   这一概念可以推广到集合。

2. 分离集separating set：如下图所示，若从结点集 A中的结点到结点集B中的结点都必须经过结点集C中的结点，则称结点集A和结点集B被结点集C分离，C称作分离集。

   

3. 马尔可夫随机场有三个马尔可夫性定义：

   • 全局马尔科夫性。
   • 局部马尔科夫性。
   • 成对马尔科夫性。

4. 全局马尔可夫性global Markov property：给定两个变量子集和它们的分离集，则这两个变量子集关于分离集条件独立。

   如上图，令结点集A、B、C对应的变量集分别为 $\mathbb X_A,\mathbb X_B,\mathbb X_C$， 则 $\mathbb X_A$ 和 $\mathbb X_B$ 在给定 $\mathbb X_C$ 的条件下独立，记作：$\mathbb X_A \perp \mathbb X_B \mid \mathbb X_C$ 。

5. 局部马尔可夫性local Markov property：给定某变量的邻接变量，则该变量与其他变量（既不是该变量本身，也不是邻接变量）关于邻接变量条件独立。

   即：令 $\mathbb V$ 为图的结点集， $n(v)$ 为结点 $v$ 在图上的邻接结点， $n^{*}(v)=n(v) \bigcup \{v\}$ ，则有：

   $$\mathbb X_{v} \perp \mathbb X_{\mathbb V-n^{*}(v)} \mid \mathbb X_{n(v)}$$

   这是根据全局马尔可夫性推导而来

   

6. 成对马尔可夫性pairwise Markov property：给定两个非邻接变量，则这两个变量关于其他变量（即不是这两个变量的任何其他变量）条件独立。

   即：令 $\mathbb V$ 为图的结点集，令 $\mathbb E$ 为图的边集。对图中的两个结点 $u,v$，若 $(u,v) \notin \mathbb E$ , 则有：

   $$\mathbb X_{u} \perp \mathbb X_{v} \mid \mathbb X_{\mathbb V-\{u,v\}}$$

   这也是根据全局马尔可夫性推导而来

   

3.2 极大团

1. 考虑两个结点 $X_i,X_j$，如果它们之间不存在链接，则给定图中其他所有结点，那么这两个结点一定是条件独立的

   • 因为这两个结点之间没有直接的路径，并且所有其他路径都通过了观测的结点。

   • 该条件独立性表示为：

     $$P(X_i,X_j\mid \mathbb X-\{X_i,X_j\})=P(X_i\mid \mathbb X-\{X_i,X_j\})P(X_j\mid\mathbb X-\{X_i,X_j\})$$

   • 对于联合概率分布的分解，则一定要让 $X_i,X_j$ 不能出现在同一个因子中，从而让属于这个图的所有可能的概率分布都满足条件独立性质。

2. 这里引入团的概念：

   • 对于图中结点的一个子集，如果其中任意两个结点之间都有边连接，则称该结点子集为一个团clique。即：团中的结点集合是全连接的。

   • 若在一个团中加入团外的任何一个结点都不再形成团，则称该团为极大团maximal clique 。

     即：极大团就是不能被其他团所包含的团。

   • 显然，每个结点至少出现在一个极大团中。

     如下图所示

     • 所有的团有： $\{X_1,X_2\},\{X_2,X_3\},\{X_3,X_4\},\{X_4,X_2\},\{X_1,X_3\},\{X_1,X_2,X_3\},\{X_2,X_3,X_4\}$
     • 极大团有：$\{X_1,X_2,X_3\},\{X_2,X_3,X_4\}$

     

3. 可以将联合概率分布分解的因子定义为团中变量的函数，也称作势函数。

   它是定义在随机变量子集上的非负实函数，主要用于定义概率分布函数。

4. 在马尔可夫随机场中，多个变量之间的联合概率分布能够基于团分解为多个因子的乘积，每个因子仅和一个团相关。

   对于 $n$ 个随机变量 $\mathbb X=\{X_1,X_2,\cdots,X_n\}$ ，所有团构成的集合为 $\mathcal C$ ， 与团 $\mathbb Q\in \mathcal C$ 对应的变量集合记作 $\mathbb X_\mathbb Q$ ，则联合概率 $P(\mathbb X)$ 定义为：

   $$P(\mathbb X)=\frac 1Z \prod_{\mathbb Q\in \mathcal C} \psi_\mathbb Q(\mathbb X_\mathbb Q)$$

   其中：

   • 所有团构成了整个概率图（团包含了结点和连接）， 任意两个团之间不互相包含（但是可以相交）。
   • $\psi_\mathbb Q$ 为与团 $\mathbb Q$ 对应的势函数，用于对 团 $\mathbb Q$ 中的变量关系进行建模。
   • $Z=\sum_{\mathbb X}\prod_{\mathbb Q\in \mathcal C} \psi_\mathbb Q(\mathbb X_\mathbb Q)$ 为规范化因子，确保 $P(\mathbb X)$ 满足概率的定义。
   • 实际应用中，$Z$ 的精确计算非常困难。但是很多任务往往并不需要获得 $Z$ 的精确值。

5. 在上述 $P(\mathbb X)$ 计算公式中，团的数量会非常多。如：所有相互连接的两个结点都会构成一个团。这意味着有非常多的乘积项。

   注意到：若团 $\mathbb Q$ 不是极大团，则它必被一个极大团 $\mathbb Q^{*}$ 所包含。此时有： $\mathbb X_\mathbb Q \subseteq \mathbb X_{\mathbb Q^{*}}$ 。

   于是： 随机变量集合 $\mathbb X_\mathbb Q$内部随机变量之间的关系不仅体现在势函数 $\psi_\mathbb Q$ 中，也体现在势函数 $\psi_{\mathbb Q^{*}}$ 中（这是根据势函数的定义得到的结论）。

   于是： 联合概率 $P(\mathbb X)$ 可以基于极大团来定义。假定所有极大团构成的集合为 $\mathcal C^{*}$， 则有Hammersley-Clifford 定理：

   $$P(\mathbb X)=\frac {1}{Z^{*}} \prod_{\mathbb Q\in \mathcal C^{*}} \psi_\mathbb Q(\mathbb X_\mathbb Q)$$

   其中：$Z^{*}=\sum_{\mathbb X}\prod_{\mathbb Q\in \mathcal C^{*}} \psi_\mathbb Q(\mathbb X_\mathbb Q)$ 为规范化因子，确保 $P(\mathbb X)$ 满足概率的定义 。

6. 通常贝叶斯网络可以将因子定义成表格形态，而马尔可夫随机场将因子定义为势函数。因为马尔可夫随机场无法将因子表格化。

   假设有 $n$ 个随机变量 $X_1,X_2,\cdots,X_n$ ，它们的取值都是 $\{0,1\}$ 。假设马尔可夫随机场中它们是全连接的，则其联合概率分布需要 $O(2^n)$ 个参数。

   如果表达成表格形态，横轴表示连接的一个端点、纵轴表示连接的另一个端点，则需要 $O(n^2)$ 个参数。当 $n$ 较大的时候， $O(n^2) \lt O(2^n)$ ，因此表格无法完全描述马尔可夫随机场的参数。

7. 全局马尔可夫性的一个证明：

   

   将上图简化为如下所示：

   

   • 最大团有两个：$\{\mathbb X_{A},\mathbb X_{C}\},\{\mathbb X_{B},\mathbb X_{C}\}$ ，因此联合概率为：

     $$P(\mathbb X_{A},\mathbb X_{B},\mathbb X_{C})=\frac 1Z\psi_{AC}(\mathbb X_{A},\mathbb X_{C})\psi_{BC}(\mathbb X_{B},\mathbb X_{C})$$

   • 基于条件概率的定义有：

     $$P(\mathbb X_{A},\mathbb X_{B}\mid \mathbb X_{C})=\frac{P(\mathbb X_{A},\mathbb X_{B},\mathbb X_{C})}{P(\mathbb X_{C})}$$

     根据：

     $$P(\mathbb X_{C})=\sum_{\mathbb X_{A}^{\prime}}\sum_{\mathbb X_{B}^{\prime}} P(\mathbb X_{A}^{\prime},\mathbb X_{B}^{\prime},\mathbb X_{C}) = \sum_{\mathbb X_{A}^{\prime}}\sum_{\mathbb X_{B}^{\prime}}\frac {1}{Z}\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C})\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C})$$

     将 $P(\mathbb X_{C})$ 和 $P(\mathbb X_{A},\mathbb X_{B},\mathbb X_{C})$ 代入，有：

     $$P(\mathbb X_{A},\mathbb X_{B}\mid \mathbb X_{C})=\frac{\psi_{AC}(\mathbb X_{A},\mathbb X_{C})\psi_{BC}(\mathbb X_{B},\mathbb X_{C}) }{\sum_{\mathbb X_{A}^{\prime}}\sum_{\mathbb X_{B}^{\prime}}\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C})\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C}) }\\ = \frac{\psi_{AC}(\mathbb X_{A},\mathbb X_{C})}{\sum_{\mathbb X_{A}^{\prime}}\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C})}\cdot \frac{\psi_{BC}(\mathbb X_{B},\mathbb X_{C}) }{\sum_{\mathbb X_{B}^{\prime}}\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C})}$$

   • 考虑 $P(\mathbb X_{A}\mid \mathbb X_{C})$：

   $$P(\mathbb X_{A}\mid \mathbb X_{C})=\frac{P(\mathbb X_{A},\mathbb X_{C})}{P(\mathbb X_{C})}=\frac{\sum_{\mathbb X_{B}^{\prime}} P(\mathbb X_{A},\mathbb X_{B}^{\prime},\mathbb X_{C})}{\sum_{\mathbb X_{A}^{\prime}}\sum_{\mathbb X_{B}^{\prime}} P(\mathbb X_{A}^{\prime},\mathbb X_{B}^{\prime},\mathbb X_{C})}\\ = \frac{\sum_{\mathbb X_{B}^{\prime}}\frac 1Z\psi_{AC}(\mathbb X_{A},\mathbb X_{C})\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C}) }{\sum_{\mathbb X_{A}^{\prime}}\sum_{\mathbb X_{B}^{\prime}} \frac 1Z\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C})\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C}) }\\ =\frac{\psi_{AC}(\mathbb X_{A},\mathbb X_{C})\sum_{\mathbb X_{B}^{\prime}}\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C}) }{\left(\sum_{\mathbb X_{A}^{\prime}}\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C}) \right)\left(\sum_{\mathbb X_{B}^{\prime}}\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C})\right)}\\ =\frac{\psi_{AC}(\mathbb X_{A},\mathbb X_{C})}{\sum_{\mathbb X_{A}^{\prime}}\psi_{AC}(\mathbb X_{A}^{\prime},\mathbb X_{C}) }$$
   • 同理，可以推导出：
   $$P(\mathbb X_{B}\mid \mathbb X_{C})=\frac{\psi_{BC}(\mathbb X_{B},\mathbb X_{C})}{\sum_{\mathbb X_{B}^{\prime}}\psi_{BC}(\mathbb X_{B}^{\prime},\mathbb X_{C}) }$$

   • 于是有：

     $$P(\mathbb X_{A},\mathbb X_{B}\mid \mathbb X_{C})=P(\mathbb X_{A}\mid \mathbb X_{C}) \cdot P(\mathbb X_{B}\mid \mathbb X_{C})$$

8. 有向图和无向图模型都将复杂的联合分布分解为多个因子的乘积：

   • 无向图模型的因子是势函数，需要全局归一化。

     优点是：势函数设计不受概率分布的约束，设计灵活。

   • 有向图模型的因子是概率分布，不需要全局归一化。

     优点是：训练相对高效。

3.3 势函数

1. 势函数 $\psi_\mathbb Q(\mathbb X_\mathbb Q)$ 的作用是刻画变量集 $\mathbb X_\mathbb Q$ 中变量之间的相关关系。

2. 与有向图的联合分布的因子不同，无向图中的势函数没有一个具体的概率意义。

   • 这可以使得势函数的选择具有更大的灵活性，但是也产生一个问题：对于具体任务来说，如何选择势函数。
   • 可以这样理解：将势函数看做一种度量：它表示局部变量的哪种配置优于其他配置。

3. 势函数必须是非负函数（确保概率非负），且在所偏好的变量取值上具有较大的函数值。 如：

   $$\psi_{AC}( X_A, X_C)=\begin{cases} 2.0,& \text{if}\quad X_A= X_C\\ 0.1,& \text{otherwise} \end{cases} \\ \psi_{BC}( X_B, X_C)=\begin{cases} 0.1,& \text{if}\quad X_B= X_C\\ 1.5,& \text{otherwise} \end{cases}$$
   • 该模型偏好变量 $X_A, X_C$ 拥有相同的取值；偏好 $X_B, X_C$ 拥有不同的取值。
   • 如果想获取较高的联合概率，则可以令 $X_A$ 和 $X_C$ 相同，且 $X_B$ 和 $X_C$ 不同。

4. 通常使用指数函数来定义势函数：

   $$\psi_\mathbb Q(\mathbb X_\mathbb Q)=e^{-H_\mathbb Q(\mathbb X_\mathbb Q)}$$

   其中 $H_\mathbb Q(\mathbb X_\mathbb Q)$ 是一个定义在变量集 $\mathbb X_\mathbb Q$ 上的实值函数，称作能量函数。

   • 指数分布被称作玻尔兹曼分布。

   • 联合概率分布被定义为势函数的乘积，因此总能量可以通过将每个最大团中的能量相加得到。

     这就是采取指数函数的原因，指数将势函数的乘积转换为能量函数的相加。

5. $H_\mathbb Q(\mathbb X_\mathbb Q)$ 常见形式为：

   $$H_\mathbb Q(\mathbb X_\mathbb Q)=\sum_{u,v \in \mathbb Q,u\neq v} \alpha_{u,v}t_{u,v}(u,v)+\sum_{v \in \mathbb Q}\beta_vs_v(v)$$

   其中：

   • $\alpha_{u,v},\beta_v$ 表示系数； $t_{u,v}(u,v),s_v(v)$ 表示约束条件。
   • 上式第一项考虑每一对结点之间的关系；第二项考虑单个结点。

3.4 图像降噪应用

1. 马尔可夫随机场的一个应用是图像降噪。

   如下图所示，左侧图片为原始图像，右侧图片为添加了一定噪音（假设噪音比例不超过 10%） 的噪音图像。现在给定噪音图像，需要得到原始图像。

   

2. 设随机变量 $Y_i$ 表示噪音图像中的像素，随机变量 $X_i$ 表示原始图像中的像素。其中：

   • $i$ 代表图片上的每个位置。
   • $Y_i,X_i\in \{+1,-1\}$ 。当它们取 +1 时，表示黑色；取-1 时，表示白色。

3. 由于已知噪音图像，因此 $Y_i$ 的分布是已知的。原始图像未知，则 $X_i$ 的分布待求解。

   • 由于噪音图像是从原始图像添加噪音而来，因此我们认为：$Y_i$ 和 $X_i$ 具有较强的关联。

   • 由于原始图像中，每个像素和它周围的像素值比较接近，因此 $X_i$ 与它相邻的像素也存在较强的关联。

     因此我们假设：$X_i$ 只和它直接相邻的像素有联系（即：条件独立性质）。

   因此得到一个具备局部马尔可夫性质的概率图模型。模型中具有两类团：

   • 团 $\{X_i,Y_i\}$ ：原始图像的像素和噪音图像的像素。
   • 团 $\{X_i,X_j\}$：原始图像的像素和其直接相邻的像素。

   这两类团就是模型中的最大团。

   

4. 定义能量函数：

   • 对于团 $\{X_i,Y_i\}$ ，定义能量函数：$H_1(X_i,Y_i) =-\eta X_iY_i$。即：$X_i,Y_i$ 相同时，能量较低；$X_i,Y_i$ 不同时，能量较高。
   • 对于团 $\{X_i,X_j\}$ ，定义能量函数：$H_2(X_i,X_j) =-\beta X_iX_j$。即：$X_i,X_j$ 相同时，能量较低；$X_i,X_j$ 不同时，能量较高。
   • 另外对于团 $\{X_i,Y_i\}$ ， $\{X_i,X_j\}$ 这个整体，定义能量函数： $H_3(X_i)=hX_i$。 即： $X_i$ 较大时，能量较高；$X_i$ 较小时，能量较低。

   于是得到整体的能量函数为：

   $$H(\mathbb X,\mathbb Y)=h \sum_{i} X_i-\beta\sum_{(i,j) \in \mathbb E} X_iX_j -\eta \sum_{i}X_iY_i$$

   其中 $\mathbb E$ 为原始图像的相邻像素连接得到的边。

   考虑到 $P(\mathbb X,\mathbb Y)=\frac {1}{Z^{*}} e^{-H(\mathbb X,\mathbb Y)}$ ，根据最大似然准则，则模型优化目标是：

   $$\min_{X_i} H(\mathbb X,\mathbb Y) = \min_{X_i} h \sum_{i} X_i-\beta\sum_{(i,j) \in \mathbb E} X_iX_j -\eta \sum_{i}X_iY_i$$

5. 对于能量函数最小化这个最优化问题，由于每个位置的 $X_i$ 都可以取2 个值 $\{+1,-1\}$ ，因此有 $2^N$ 种取值策略，$N$ 为原始图像的像素数量。如果 $N$ 较大，则参数的搜索空间非常巨大。

   实际任务中通过 ICM 算法、模拟退火算法、或者graph cuts 算法来解决这个参数搜索问题。

四、条件随机场 CRF

1. 生成式概率图模型是直接对联合分布进行建模，如隐马尔可夫模型和马尔可夫随机场都是生成式模型。

   判别式概率图模型是对条件分布进行建模，如条件随机场Conditional Random Field:CRF。

2. 条件随机场试图对多个随机变量（它们代表标记序列）在给定观测序列的值之后的条件概率进行建模：

   令 $\mathbf X=\{ X_1, X_2,\cdots,X_n\}$ 为观测变量序列， $\mathbf Y=\{Y_1,Y_2,\cdots,Y_n\}$ 为对应的标记变量序列。条件随机场的目标是构建条件概率模型 $P(\mathbf Y \mid \mathbf X)$ 。

   即：已知观测变量序列的条件下，标记序列发生的概率。

3. 标记随机变量序列 $\mathbf Y$ 的成员之间可能具有某种结构：

   • 在自然语言处理的词性标注任务中，观测数据为单词序列，标记为对应的词性序列（即动词、名词等词性的序列），标记序列具有线性的序列结构。
   • 在自然语言处理的语法分析任务中，观测数据为单词序列，标记序列是语法树，标记序列具有树形结构。

4. 令 $\mathcal G=<\mathbb V,\mathbb E>$ 表示与观测变量序列 $\mathbf X$ 和标记变量序列 $\mathbf Y$ 对应的无向图， $Y_v$ 表示与结点 $v$ 对应的标记随机变量， $n(v)$ 表示结点 $v$ 的邻接结点集。若图 $\mathcal G$ 中结点对应的每个变量 $Y_v$ 都满足马尔可夫性，即：

   $$P(Y_v\mid \mathbf X,\mathbf Y_{\mathbb V-\{v\}})=P(Y_v \mid \mathbf X,Y_{n(v)})$$

   则 $(\mathbf Y,\mathbf X)$ 构成了一个条件随机场。

4.1 链式条件随机场

1. 理论上讲，图 $\mathcal G$ 可以具有任意结构，只要能表示标记变量之间的条件独立性关系即可。

   但在现实应用中，尤其是对标记序列建模时，最常用的是链式结构，即链式条件随机场chain-structured CRF。

   如果没有特殊说明，这里讨论是基于链式条件随机场。

   

2. 给定观测变量序列 $\mathbf X=\{ X_1, X_2,\cdots,X_n\}$ ，链式条件随机场主要包含两种关于标记变量的团：

   • 单个标记变量与 $\mathbf X$ 构成的团： $\{Y_i,\mathbf X\},i=1,2,\cdots,n$ 。
   • 相邻标记变量与 $\mathbf X$ 构成的团： $\{Y_{i-1},Y_i,\mathbf X\},i=2,\cdots,n$ 。

3. 与马尔可夫随机场定义联合概率的方式类似，条件随机场使用势函数和团来定义条件概率 $P(\mathbf Y\mid \mathbf X)$ 。

   采用指数势函数，并引入特征函数feature function，定义条件概率：

   $$P(\mathbf Y\mid \mathbf X)=\frac 1Z \exp\left(\sum_{j=1}^{K_1}\sum_{i=1}^{n-1}\lambda_jt_j(Y_i,Y_{i+1},\mathbf X,i)+\sum_{k=1}^{K_2}\sum_{i=1}^{n}\mu_ks_k(Y_i,\mathbf X,i)\right)$$

   其中：