马尔科夫随机场(MRF)

之前一直听说过MRF的大名，但是一直没有了解过。最近在看论文的时候，经常遇到这个专业术语，就专门对这个概念学习一下。声明下面内容主要参考了这篇文章——马尔科夫随机场(MRF)在图像处理中的应用-图像分割、纹理迁移，加了一些个人见解。

马尔科夫随机场，英文名称Markov Random Field，简写为MRF。

基础概念

条件概率和贝叶斯定理

条件概率常用来解决逆问题，也就是已知结果反推原因。

经典的贝叶斯定理公式如下：

$P(B|A)=\frac{P(A|B)P(B)}{P(A)}$

首先，需要明确的是，在上面的式子中$A$是结果，$B$是原因。这个公式经常用来求解已经结果$A$反推原因$B$的概率，这是无法直接观测的问题。用公式描述是：

已知$P(A|B)$和$P(B)$，可计算得到$P(A)=\sum_i^n P(A|B_i)p(B_i)$，要求$P(B|A)$。

我们一般称$P(原因)$即$P(B)$是先验概率，$P(原因|结果)$即$P(B|A)$为后验概率，相应的为先验分布和后验分布。

随机游走

随机游走是一个典型的随机过程，就和丢骰子走步数一样。但这里可以简单分为两种可能，假设抛掷一个硬币，正面我们就向上走一步，反面我们就向下走一步。则向上走和向下走的概率都是50%。

$X_0=0 \\ X_t=X_{t-1}+Z_t \ \ , Z_t=1,-1$

下图就是一些具体的观测值：

随机游走有两个特点要特点注意：

每次行动时，下一步的动作和前几步动作没有关系，和前几步的动作都没关系，也就是说无法通过当前的状态去推断未来的状态
因为每一步和周围周围的行动都没有关系，所以无论上方的图折线如何变化，其发生的概率都是一样的(反射原理)

假如在$t=9$时将折线翻转，如下所示，这种情况发生的概率和之前是一样的。

无向图和有向图模型

概率图模型（Probabilistic Graphical Model, PGM），简称图模型。图模型一般用来表示随机变量之间的相互作用。把随机变量引入到图中，图中每一个点是实际图中的像素点，每个像素点通过“边”来连接。

根据图是有向的还是无向的，可以将图的模式分为两大类：

概率无向图模型(probabilistic undirected graphical model)又称为马尔科夫随机场(Markov Random Field)，或者马尔科夫网络
有向图模型通常被称为信念网络(belief network)或者贝叶斯网络(Bayesian network)

有向图每个边都是有方向的，箭头所指的方向表示了这个随机变量的概率分布点，比如一个节点a到节点b的一个箭头表明了节点b的概率由a所决定。

例如假设有一个接力赛，Alice的完成时间为$t_0$，Bob的完成时间为$t_1$，而Carol的完成时间为$t_2$。和之前说的一样，$t_2$取决于$t_1$，而$t_1$取决于$t_0$，而$t_2$间接依赖于$t_0$。

/TIM截图20180618213431.jpg)

也就是说Carol的完成时间和Bob有关系和Alice也有关系，是单方向依赖的。

/TIM截图20180618213652.jpg)

对于本文说的马尔科夫随机场是无向图模型，也就是两个点之前并没有明确的前后以及方向关系，虽然两个点之前存在相互作用，但是这个作用仅仅在附近的点与点之间，与更远处的点或者最前面的点并没有关系。

/TIM截图20180618213803.jpg)

用公式表示就是：

$P\{X_{n+1}=i_{n+1}|X_0=i_0,...,X_n=i_n\}=P\{X_{n+1}=i_{n+1}|X_n=i_n\}$

就称$\{X_n, n \in T\}$为马尔科夫过程。该随机过程的统计特性完全由条件概率决定。

下面就对它进行详细介绍。

马尔科夫随机场

马尔科夫随机场的特点是两点之间的因果关系没有明确的方向。举一个例子，这个例子来自于A friendly introduction to Bayes Theorem and Hidden Markov Models

这个例子是很经典的天气心情假设。假设有一个人叫Bob，他的心情会受到天气的影响。在天气比较晴朗的时候有极大的可能是高兴的，而在下雨的时候有一定可能是郁闷的。而现在我们要做的就是根据Bob的心情情况来猜测当前的天气信息。

这个就是典型的已知结果(Bob的心情)去推导原因(天气情况)。

根据上面的贝叶斯定理，要想知道 P(原因|结果)，需要知道 P(原因) 和 P(结果|原因)。所以对一段时间的天气和Bob的心情变化进行统计。

15天中10天是晴天（某一天是晴天的概率为10/15=2/3）
15天中5天是阴天（某一天是晴天的概率为5/15=1/3）
昨天是晴天，今天是晴天的概率为0.8
昨天是阴天，今天是晴天的概率是0.2
昨天是阴天，今天是阴天的概率是0.6
昨天是阴天，今天是晴天的概率是0.4

另外，根据Bob在这些天的心情情况，可以分别总结出晴天阴天Bob的心情好坏概率。

天气为晴天，Bob心情好的概率是0.8
天气为晴天，Bob心情坏的概率是0.2
天气为阴天，Bob心情好的概率是0.4
天气为阴天，Bob心情坏的概率是0.6

至此，我们所需的全部概率计算完毕。根据这些概率即可搭建一个HMM(Hidden Mardov Model)因马尔科夫模型。

要说到HMM首先要说马尔科夫链。

马尔科夫链

在这个例子中，马尔科夫链即上图中晴天(B)和阴天(A)的转换公式：

/markov_chain_1.gif)

如图所示，A和B两种状态(B代表晴天A代表阴天)，有四种可能的转移概率(transition probabilities)，分别是 A->A、A->B、B->B、B->A。将这几个概率描述出来如下图右面所示($P(A|A)$表示晴天到晴天的概率为0.8)，另外右边概率转移矩阵的每一行概率加起来都为1。

通过这个天气的马尔科夫链，我们就可以模拟出接下来的天气情况（S代表Sunny晴天，R代表rainy雨天）：

当然这仅仅是简单的马尔科夫链，如果是复杂的马尔科夫链，如下所示，右边是这个马尔科夫链的转移矩阵，每一行的概率值加起来为1。

以上动图来源于Markov Chains。

个人总结：马尔科夫链可以看成是单变量的随机过程。

HHM隐马尔可夫模型

说完马尔科夫链，接着说HHM隐马尔可夫模型。首先看前面的图：

我们知道，上面的晴天和阴天的转换公式为我们之前说到的马尔科夫链（单变量随机过程）。但现在问题是，要通过观察Bob的心情来推测今天的天气。也就是说，上面的天气变化（晴天与阴天之间的变化）是随机变化，Bob的心情（由天气导致的心情变化）也是随机变化，整个的过程就是所谓的双重随机过程。

在这个例子中，Bob的心情是已知的，称为Observations；而天气情况是未知的，称为 hidden States。上面图中天气与天气之间互相转换（the probability of going from one in and state to another）的概率称为transition probabilities。上图中，由天气得到人心情的概率（the probability that that the observations are emitted from the hidden States）称为emission probabilities。

首先，来看第一个问题：若已知Bob的心情高兴，则天气是晴天和阴天的概率为多大？

这个问题是很明显的由结果（心情）导原因（天气）的问题，很明显需要使用前面介绍的贝叶斯公式来求解。具体过程为：

$P(阴|心情好)=\frac{P(心情好|阴)P(阴)}{P(心情好)}=\frac{2/5 \times 1/3}{P(心情好)} \\ P(晴|心情好)=\frac{P(心情好|晴)P(晴)}{P(心情好)}=\frac{4/5 \times 2/3}{P(心情好)}$

虽然这里$P(心情好)$不知道，但是可以知道$P(阴|心情好)$比上$P(晴|心情好)$为$1:4$，所以可以知道：

$P(阴|心情好)=0.2 \\ P(晴|心情好)=0.8$

接着来看第二个问题：若已知Bob连着几天的心情，如何得到这几天的天气情况？

比如，有一个星期Bob的心情如下图第一行所示，那么仅仅依据天气与Bob心情的关系概率去判断天气情况是下面第二行的情况。但是这样剧烈的天气变化情况一点都不符合常理。真实的情况是若昨天是晴天则明天很大可能是晴天，而昨天是雨天明天很大可能是雨天。

那么要想得到相对真实的预测，不仅需要考虑Bob的心情（Observations），还要考虑到天气情况（hidden States）变化的转移。

具体先看一个简单的例子，假设已知Bob连着两天的心情是高兴、不高兴，那么这两天天气依次为晴天、晴天的概率是多少呢？

其实，也就是要计算下图红框中所有事件同时发生的概率。在第一天，不知道前一天的天气如何，所以根据先验知识是第一天是晴天的概率为0.67，对应Bob心情好的概率为0.8；第二天已知了第一天是晴天，则第二天还是晴天的概率为0.8，对应的Bob心情不好的概率为0.2。所以整体事件全部发生的概率为

$(0.67*0.8) \times (0.8*0.2)=0.085$

同理可得到上图中各个情况一起发生的分别概率，取概率最大的情况即为根据Bob这两天的心情对连续两天的预测情况。

注意：这里有一个细节，上面在计算第一天是晴天概率时，直接使用的是先验概率，并没有使用到已知Bob心情天晴为晴天的条件概率。这是因为上面已经提到仅仅依靠Bob的心情去对天气进行预测是不可靠的，要加上天气状态转移概率一起预测。但是对于第一天，不知道前一天的天气情况，也就无从得知天气转移概率，所以直接使用先验概率更可靠一点。

接着再举一个例子，假设已知Bob连着三天的心情是高兴、不高兴、高兴，则三天依次晴天、雨天、晴天的概率为：

$(0.67*0.8) \times (0.2*0.6) \times (0.4*0.8) = 0.02048$

同理可以得到下图中各个天气组合与Bob心情同时发生的概率，红框中为最大可能发生的情况。也就是已知Bob的心情连着三天是高兴、不高兴、高兴，则这三天连着是晴天的概率最大。

由这两个例子，已知连着两天的心情，推算可能的天气需要计算四种情况；已知连着三天的心情，推算可能的天气需要计算八种情况；随着需要预测的天数增多，需要的运算量呈指数增长。那怎么解决呢？这需要借助Viterbi算法，采用动态规划的方法计算条件概率最大的那一条路。也有在Forward-Backward算法(Baum-Welch)来估计概率转移矩阵，当然这里就不详细讲述了。我这里只是稍微提一下Viterbi算法。

如下所示，假设最上面是已知Bob一个星期的心情，要预测对应这些天的天气情况。

先看第一天的情况。

晴天与Bob心情好同时发生的概率为$0.670.8=0.533$，阴天与Bob心情好同时发生的概率为$0.330.4=0.133$，所以对于第一天取概率最高路径——晴天，而舍去概率较低的路径——阴天（动态规划思想）。

接着来看第二天的情况。

Bob心情好与第二天是晴天同时发生的概率分为两种情况。第一种情况是第一天是晴天，对应的先验概率是0.533，所以这种情况发生的概率是$0.5330.80.8=0.341$。第二种情况是第一天是阴天，对应的先验概率是0.133，所以这种情况发生的概率是$0.1330.40.8=0.042$。对于Viterbi算法，前面提到第一天是阴天的情况已经被舍去了，所以Bob心情好与第二天是晴天同时发生的第二种情况也就不会出现在算法中。即Bob心情好与第二天晴天同时发生的概率是0.341。

同样的，Bob心情好与第二天是阴天同时发生的概率也分为两种情况。第一种情况是第一天是晴天，对应的先验概率是0.533，所以这种情况发生的概率是$0.5330.20.4=0.043$。第二种情况是第一天是阴天，对应的先验概率是0.133，所以这种情况发生的概率是$0.1330.60.4=0.031$。对于Viterbi算法，前面提到第一天是阴天的情况已经被舍去了，所以Bob心情好与第二天是阴天同时发生的第二种情况也就不会出现在算法中。即Bob心情好与第二天阴天同时发生的概率是0.043。

对于第二天，还是取概率最大的路线——第二天是晴天，舍去概率较低的路径——阴天（动态规划思想）。

按照这种动态规划的思想依次预测，挑选最有可能的路径如下所示。这个例子对应的代码可以在这里)找到。

关于这方面还有一些别的应用，如下图所示。在第一个应用中，Observations是Words，而Hidden States是Tags，问题是根据Word猜测它的Tag。在第二个应用中，Observations是机器人当前距离墙壁多远，而Hidden States是真实坐标，问题是根据机器人当前距离墙壁多远，预测真实坐标。

参考

马尔科夫随机场(MRF)在图像处理中的应用-图像分割、纹理迁移
 概率图模型
 读懂概率图：你需要从基本概念和参数估计开始
 一次性弄懂马尔可夫模型、隐马尔可夫模型、马尔可夫网络和条件随机场！(词性标注代码实现)