Question

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

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

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

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

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

     如： $ MathJax-Element-153 $ 两个变量的联合概率分布为：

     $ MathJax-Element-153 $	$ MathJax-Element-154 $
     $ MathJax-Element-155 $	1000
     $ MathJax-Element-156 $	10
     $ MathJax-Element-157 $	20
     $ MathJax-Element-158 $	2000

     则这个分布表示： $ MathJax-Element-159 $ 和 $ MathJax-Element-160 $ 取值相同的概率很大。

   • 事实上这里的 $ MathJax-Element-161 $ 就是后面介绍的势函数。

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

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

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

3.1 马尔科夫性

1. 对结点 $ MathJax-Element-162 $ ，若去掉结点 $ MathJax-Element-166 $ 之后 $ MathJax-Element-165 $ 分属于两个联通分支，则称结点 $ MathJax-Element-165 $ 关于结点 $ MathJax-Element-166 $ 条件独立，记作 $ MathJax-Element-167 $ 。

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

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

   

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

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

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

   如上图，令结点集A、B、C对应的变量集分别为 $ MathJax-Element-168 $ ， 则 $ MathJax-Element-169 $ 和 $ MathJax-Element-170 $ 在给定 $ MathJax-Element-171 $ 的条件下独立，记作： $ MathJax-Element-172 $ 。

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

   即：令 $ MathJax-Element-177 $ 为图的结点集， $ MathJax-Element-274 $ 为结点 $ MathJax-Element-275 $ 在图上的邻接结点， $ MathJax-Element-176 $ ，则有：

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

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

   

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

   即：令 $ MathJax-Element-177 $ 为图的结点集，令 $ MathJax-Element-258 $ 为图的边集。对图中的两个结点 $ MathJax-Element-179 $ ，若 $ MathJax-Element-180 $ , 则有：

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

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

   

3.2 极大团

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

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

   • 该条件独立性表示为：

     $ 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\}) $

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

2. 这里引入团的概念：

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

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

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

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

     如下图所示

     • 所有的团有： $ MathJax-Element-183 $
     • 极大团有： $ MathJax-Element-184 $

     

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

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

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

   对于 $ MathJax-Element-345 $ 个随机变量 $ MathJax-Element-186 $ ，所有团构成的集合为 $ MathJax-Element-187 $ ， 与团 $ MathJax-Element-188 $ 对应的变量集合记作 $ MathJax-Element-229 $ ，则联合概率 $ MathJax-Element-208 $ 定义为：

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

   其中：

   • 所有团构成了整个概率图（团包含了结点和连接）， 任意两个团之间不互相包含（但是可以相交）。
   • $ MathJax-Element-203 $ 为与团 $ MathJax-Element-199 $ 对应的势函数，用于对 团 $ MathJax-Element-199 $ 中的变量关系进行建模。
   • $ MathJax-Element-194 $ 为规范化因子，确保 $ MathJax-Element-208 $ 满足概率的定义。
   • 实际应用中， $ MathJax-Element-620 $ 的精确计算非常困难。但是很多任务往往并不需要获得 $ MathJax-Element-620 $ 的精确值。

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

   注意到：若团 $ MathJax-Element-199 $ 不是极大团，则它必被一个极大团 $ MathJax-Element-200 $ 所包含。此时有： $ MathJax-Element-201 $ 。

   于是： 随机变量集合 $ MathJax-Element-229 $ 内部随机变量之间的关系不仅体现在势函数 $ MathJax-Element-203 $ 中，也体现在势函数 $ MathJax-Element-204 $ 中（这是根据势函数的定义得到的结论）。

   于是： 联合概率 $ MathJax-Element-208 $ 可以基于极大团来定义。假定所有极大团构成的集合为 $ MathJax-Element-206 $ ， 则有Hammersley-Clifford 定理：

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

   其中： $ MathJax-Element-207 $ 为规范化因子，确保 $ MathJax-Element-208 $ 满足概率的定义 。

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

   假设有 $ MathJax-Element-345 $ 个随机变量 $ MathJax-Element-210 $ ，它们的取值都是 $ MathJax-Element-676 $ 。假设马尔可夫随机场中它们是全连接的，则其联合概率分布需要 $ MathJax-Element-212 $ 个参数。

   如果表达成表格形态，横轴表示连接的一个端点、纵轴表示连接的另一个端点，则需要 $ MathJax-Element-213 $ 个参数。当 $ MathJax-Element-345 $ 较大的时候， $ MathJax-Element-215 $ ，因此表格无法完全描述马尔可夫随机场的参数。

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

   

   将上图简化为如下所示：

   

   • 最大团有两个： $ MathJax-Element-216 $ ，因此联合概率为：

     $ 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}) $

     将 $ MathJax-Element-217 $ 和 $ MathJax-Element-218 $ 代入，有：

     $ 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})} $

   • 考虑 $ MathJax-Element-219 $ ：

   $ 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. 势函数 $ MathJax-Element-220 $ 的作用是刻画变量集 $ MathJax-Element-229 $ 中变量之间的相关关系。

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} $
   • 该模型偏好变量 $ MathJax-Element-222 $ 拥有相同的取值；偏好 $ MathJax-Element-223 $ 拥有不同的取值。
   • 如果想获取较高的联合概率，则可以令 $ MathJax-Element-224 $ 和 $ MathJax-Element-225 $ 相同，且 $ MathJax-Element-226 $ 和 $ MathJax-Element-227 $ 不同。

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

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

   其中 $ MathJax-Element-230 $ 是一个定义在变量集 $ MathJax-Element-229 $ 上的实值函数，称作能量函数。

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

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

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

5. $ MathJax-Element-230 $ 常见形式为：

   $ 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) $

   其中：

   • $ MathJax-Element-231 $ 表示系数； $ MathJax-Element-232 $ 表示约束条件。
   • 上式第一项考虑每一对结点之间的关系；第二项考虑单个结点。

3.4 图像降噪应用

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

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

   

2. 设随机变量 $ MathJax-Element-672 $ 表示噪音图像中的像素，随机变量 $ MathJax-Element-302 $ 表示原始图像中的像素。其中：

   • $ MathJax-Element-673 $ 代表图片上的每个位置。
   • $ MathJax-Element-236 $ 。当它们取 +1 时，表示黑色；取-1 时，表示白色。

3. 由于已知噪音图像，因此 $ MathJax-Element-672 $ 的分布是已知的。原始图像未知，则 $ MathJax-Element-302 $ 的分布待求解。

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

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

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

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

   • 团 $ MathJax-Element-253 $ ：原始图像的像素和噪音图像的像素。
   • 团 $ MathJax-Element-254 $ ：原始图像的像素和其直接相邻的像素。

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

   

4. 定义能量函数：

   • 对于团 $ MathJax-Element-253 $ ，定义能量函数： $ MathJax-Element-246 $ 。即： $ MathJax-Element-248 $ 相同时，能量较低； $ MathJax-Element-248 $ 不同时，能量较高。
   • 对于团 $ MathJax-Element-254 $ ，定义能量函数： $ MathJax-Element-250 $ 。即： $ MathJax-Element-252 $ 相同时，能量较低； $ MathJax-Element-252 $ 不同时，能量较高。
   • 另外对于团 $ MathJax-Element-253 $ ， $ MathJax-Element-254 $ 这个整体，定义能量函数： $ MathJax-Element-255 $ 。 即： $ MathJax-Element-302 $ 较大时，能量较高； $ MathJax-Element-302 $ 较小时，能量较低。

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

   $ 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 $

   其中 $ MathJax-Element-258 $ 为原始图像的相邻像素连接得到的边。

   考虑到 $ MathJax-Element-259 $ ，根据最大似然准则，则模型优化目标是：

   $ \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. 对于能量函数最小化这个最优化问题，由于每个位置的 $ MathJax-Element-302 $ 都可以取2 个值 $ MathJax-Element-261 $ ，因此有 $ MathJax-Element-262 $ 种取值策略， $ MathJax-Element-485 $ 为原始图像的像素数量。如果 $ MathJax-Element-485 $ 较大，则参数的搜索空间非常巨大。

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