马尔可夫模型到条件随机场，再结合深度学习

发表于 2017-04-06 更新于 2023-10-16

先了解了一下生成模型与判别模型

隐马尔可夫模型

隐马尔可夫模型（HMM）属于生成模型。

组成：两个集合，两个序列，两个矩阵。

这些内容构成了隐马尔可夫模型的整体概念，具体问题中，有的是已知的，有的是未知的，这个模型就是通过已知量建模，进而推算未知量。

两个集合

状态集合：比如有N个装着黑白两色小球的盒子，当前在第i个盒子就称为状态qi，状态集合Q={q1, q2,...,qN}。

观测集合：对一个状态，可以有多种观测结果，从一个盒子里拿出一个球，这个球的颜色是观测值，就可能是黑色或白色，观测集合V={v1, v2, ..., vM}，对于黑白小球这个例子，M=2。

两个序列

状态序列：这个序列可以看作一个时间序列，比如每分钟选一个盒子，当然可以不是时间序列，只是举例子方便些。那一小时就会有一个长度为60的序列，每个元素即对应那一分钟选的盒子编号。状态序列I=(i1, i2, ..., iT)，这里一小时的例子中T=60。

观测序列：对应状态序列的观测值，假设实实在在地做了一次实验，选了60次盒子，拿了60次小球，记录了这60次小球的颜色，观测序列O=(o1, o2, ..., oT)。

两个矩阵

状态转移矩阵： \(A=[a_{ij}]_{N\times N}\) 即假设“当前状态”是qi（盒子qi），下一分钟转移到状态qj（选盒子qj）的概率是aij。这里当然和模型名字中的“马尔可夫”挂钩了，马尔可夫过程就是未来的状态只依赖现在的条件，不依赖于过去，于是由状态转移矩阵和当前状态即可以知道下一个状态的概率，不需要管上一个状态了。

观测概率矩阵： \(B=[b_{j}(k)]_{N\times M}\) 状态qj条件下得到观测vk的概率，比如盒子qj有4个黑球，6个白球，\(b_{j}(白)\) 就是拿出一个球是白球的概率呗（0.6）。

盒子与黑白球的例子不算太完美，让人不太习惯的就是怎么选下一个盒子还带“转移概率”的。强行这么理解吧，感觉天气的栗子举起来更难下口。

模型表示

最开始还没选盒子的时候，总需要有个起始变量。初始状态概率向量 \(\pi=(\pi_{i})\) 即最开始的时候，进入状态qi的概率。有初始状态向量 \(\pi\) ，状态转移矩阵 \(A\) ，观测概率矩阵 \(B\) ，这个模型就可以像一个“自动机”一样跑起来了，可以不断按模型产生状态和观测值。所以隐马尔可夫模型 \(\lambda\) 可以用三元符号表示： \[ \lambda = (A, B, \pi) \]

\(A, B, \pi\) 称为马尔可夫模型三要素。

三个基本问题

概率计算，给定 \(\lambda=(A, B, \pi)\) 和观测序列 O，计算概率 \(P(O|\lambda)\) ，就是已知模型，求能得到特定个观测序列的概率。对这个问题，直接计算的话要枚举所有状态，是指数级的，不可行。而前向法和后向法一个是正推一个是倒推，步步为营递推即可得到结果。
学习问题，给定O，估计模型 \(\lambda=(A, B, \pi)\) ，即估算 \(A, B, \pi\) 。监督学习方法需要训练数据，人工标注代价很高，有时会利用非监督学习方法——Baum-welch算法（也就是EM算法）。
预测问题，也称为解码问题，已知模型 \(\lambda=(A, B, \pi)\) 给定观测序列 O，求最可能的状态序列 I。近似算法计算简单，有一定的适用范围，不过有可能有实际不发生的部分，即存在转移概率为0的状态。维比特算法用动态规划求概率最大路径，一条路径对应一个状态序列。

具体算法这里不细说，可参考《统计学习方法》。

马尔可夫随机场

三个马尔可夫性

Markov random field (MRF) 也就是概率无向图模型（probabilistic undirected graphical model）。

一个无向图记作G=(V,E)，顶点V表示随机变量Y，边E表示随机变量间的概率依赖关系，则图G表示概率分布P(Y)。

成对马尔可夫性：

设u和v是无向图G中任意两个没有边连接的结点，对应随机变量 \(Y_{u}\) 和 \(Y_{v}\) ，其他所有节点为O，对应随机变量组 \(Y_{O}\)，给定 \(Y_{O}\) 条件下随机变量 \(Y_{u}\) 和 \(Y_{v}\) 条件独立，即： \[ P(Y_{u}, Y_{v}|Y_{O})=P(Y_{u}|Y_{O})P(Y_{v}|Y_{O}) \]

u、v不相连，其他变量又已知了，则u、v之间概率自然互不影响

局部马尔可夫性：

设集合W是与结点v有边连接的所有结点，O是除v、W以外的其他节点，给定 \(Y_{W}\) 情况下 \(Y_{v}\) 与 \(Y_{O}\) 独立。 >同理，只是把上面的u变成集合O了

全局马尔可夫性：

结点集合A，B是无向图G中被结点集合C分开的任意结点集合，给定 \(Y_{C}\) 条件下 \(Y_{A}\) 和 \(Y_{B}\) 条件独立。

1
2
3

O---A---C---B
    | \ |   | \
    A---C---B---O

如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合概率分布为马尔可夫随机场（MRF）或概率无向图模型。

求概率分布

团与最大团：无向图G中一个结点子集C，若C中任意两个结点都有边连接，则C是一个团。如果无法在C中增加G中的结点并保持团的性质，则C是最大团（maximal clique）。

马尔可夫随机场因子分解：将图模型的联合概率分布表示为最大团上的随机变量函数乘积形式，称为因子分解。 \[ P(Y)=\frac{1}{Z}\prod\limits_{C} \Psi_{C}(Y_{C}) \] Z是归一化因子： \[ Z=\sum_{Y}\prod\limits_{C} \Psi_{C}(Y_{C}) \] 要保证P(Y)构成一个概率分布，即所有情况的概率的和（积分）得是1，所以要有这个归一化因子。函数 \(\prod\limits_{C}\) 称为势函数（potential function），这里要求势函数是严格正的，通常定义为指数函数： \[ \Psi_{C}(Y_{C})=e^{-E(Y_{C})} \] C是无向图的最大团， \(Y_{C}\) 是C的结点对应的随机变量， \(\Psi_{C}(Y_{C})\) 是C上定义的严格正函数，乘积是在无向图所有最大团上进行的。

吉布斯分布

吉布斯分布(Gibbs)在随机场的知识中总是伴随马尔可夫随机场出现，搞得人一头雾水。今天来把它掰扯清楚。

在统计力学与数学中，玻尔兹曼分布（或称吉布斯分布）是系统中的粒子在各种可能微观量子态的概率分布、概率测度或频度分布。在数学上，玻尔兹曼函数更广义的形式为吉布斯测度。在统计学与机器学习中又被称为对数-线性模型。——维基百科

玻尔兹曼分布是状态能量与系统温度的函数，给出了粒子处于特定状态下的概率。其具有以下形式： \[ p_{i} = \frac{e^{-\varepsilon_{i}/kT}}{\sum_{j=1}^{M}e^{-\varepsilon_{j}/kT}} \] 其中 \(p_{i}\) 是量子态 i 的概率， \(\varepsilon\) 为量子态 i 的能量， k 为玻尔兹曼常量， T 为系统温度， M 为系统可具有的量子态数目。

扯得好像有点远，但是注意观察对比前面的马尔可夫随机场因子分解，就是那个最大团随机变量函数乘积，势函数、归一化因子Z，和这里的分子分母形式很像。

看到这里，我觉得不指望对这个分布有什么感性认识了，只能强行这么看（理性认识...）：符合这个公式（描述了一个概率分布）的分布，就叫做吉布斯分布，而马尔可夫随机场的概率分布可以描述为最大团随机变量函数乘积形式，这个形式与吉布斯分布不谋而合，Hammersley Clifford Theorem 提到马尔可夫随机场和吉布斯分布是一致的（原文说的是“吉布斯随机场满足每一个马尔可夫性质”）。

这就是吉布斯分布，好像并没有掰扯很清楚，不过上这么多年学过来，不少东西都是强行认识的，比如小时候第一次认识惯性定律的时候那感觉。。。

势函数

说起来这个势函数也是强行定义的么，追求感性认识的我找了一圈也没见有人解释一下这个东西为啥叫势函数。

暂时这么理解吧：最大团两两连接，即团内结点两两之间都能直接影响到对方，那么这个团得到某种观察状态就是结点们直接“达成共识”的结果，这个结果的可能性是可以直接计算的。而全局得到一个什么结果，就需要一些“中间人”去协商，因为团内不是所有结点都能直接和别的团的结点“讨论”，全局结果是一个“协商”的结果，互相之间有直接关系的小团体（最大团）对最终结果有一个趋势，这个就是势函数，而全局的结果是各个小团体的趋势互相妥协的结果。

条件随机场

条件随机场（conditional random field, CRF）是给定随机变量X条件下，另一组随机变量Y的马尔可夫随机场。

定义中并没有要求X和Y具有相同的结构，现实中一般假设X和Y有相同的图结构。

线性链条件随机场

1
2
3

Y1---Y2---...---Yi--...---Yn
↑    ↑          ↑         ↑
X1   X2         Xi        Xn

\[ P(Y_{i}|X, Y_{1},...,Y_{i-1},Y_{i+1},...,Y_{n})=P(Y_{i}|X,Y_{i-1},Y_{i+1}) \] 上式满足马尔可夫性，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。 \(Y_{i}\) 只与相连的 \(Y_{i-1}\) 、 \(Y_{i+1}\) 相关，但是多了个 \(X\) 的条件，且可以看到与隐马尔可夫模型的不同，隐马尔可夫链是顺序的链，每个状态只与“上一个”状态相关，而线性链条件随机场是无向图，每个状态与直接相连的状态相关（上一个和下一个），且有一个额外的条件X。

线性链条件随机场基本问题

概率计算问题：给定条件随机场P(Y|X)，输入序列x，输出序列y，计算条件概率 \(P(Y_{i}=y_{i}|x)\) ， \(P(Y_{i-1}=y_{i-1},Y_{i}=y_{i}|x)\) 以及相应的数学期望。
学习算法。

此部分非本篇博文重点，不再详述，《统计学习方法》也讲的很清晰。

CRF图像分割

把图像每个像素当作条件随机场的一个结点，相邻像素连边，结点集合为Y，在这个基础上，加一个和每个像素一一对应的条件X，条件X就是实际看到的图像，要求的Y是分割结果标签，参考前面的线性链条件随机场，就是把一维的链变成二维的图像，Y的每个像素与相邻像素相连，X的每个像素一一对应与Y连一条边，如图：

于是就是各个资料都说的两个式子了：按前面说的吉布斯分布，差不多就是每四个像素一个最大团 \[ P(Y=y|X)=\frac{1}{Z(X)}e^{-E(y|X)} \] 标签能量表示为 \[ E(y) = \sum_{i}\Psi_{u}(y_{i}) + \sum_{i<j}\Psi_{p}(y_{i}, y_{j}) \] \(\Psi_{u}\) 是一元能量项，表示像素i分类为标签yi的能量， \(\Psi_{p}\) 是二元能量向，表示像素 i、j同时分类为 yi、yj的能量，最小化能量总和就是最可能的分割结果。

能量项可以有不同的定义方式，在求解过程、计算结果等方面都会有不同的影响。

CRF与深度学习

按原始定义来说，一般是先用神经网络输出之后，再用CRF进一步处理，两部分是分开的。而我们都更偏爱端到端直接训练的方法，精确度也会有所提高。CRF可以被表示成RNN的结构，和其他的神经网络结合在一起，实现端到端的同时训练。

这里可以有感性认识，就不放公式了，我自己也没搞太懂。

前面的标签能量E表示为一元能量项加二元能量项，二元能量项定义为若干个高斯函数的和，高斯函数又由若干表达式组成，概率函数P不方便直接计算，又对式子做了些许改变，可以多次迭代来近似。对分解后的公式分成若干步骤，每次迭代就是若干步的连接，而分解出来的每一步可以由卷积来计算，归一化的步骤可以由Softmax来计算，这样就通过一个RNN网络来迭代逼近P了，相关证明保证迭代的快速收敛。