隐马尔可夫模型(HMM)是经典的概率图模型，通过隐藏状态序列与观测序列的联合建模，结合前向-后向算法与维特比算法解决分词、标注等序列问题。
1. 隐马尔可夫模型(HMM)
隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。
1.1 马尔可夫过程
马尔可夫过程（Markov process）是一类随机过程。每个状态的转移只依赖于之前的n个状态，这个过程被称为1个n阶的模型，其中n是影响转移状态的数目。最简单的马尔可夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态，这个也叫作马尔可夫性质。用数学表达式表示就是下面的样子：
假设这个模型的每个状态都只依赖于之前的状态，这个假设被称为马尔科夫假设，这个假设可以大大的简化这个问题。显然，这个假设可能是一个非常糟糕的假设，导致很多重要的信息都丢失了。
$$
P\left(X_{n+1} \mid X_{1}=x_{1}, X_{2}=x_{2}, \ldots, X_{n}=x_{n}\right)=P\left(X_{n+1}=x \mid X_{n}=x_{n}\right)
$$
假设天气服从马尔可夫链，
- 假如今天是晴天，明天变成阴天的概率是0.1
- 假如今天是晴天，明天任然是晴天的概率是0.9，和上一条概率之和为1，这也符合真实生活的情况。
| 晴 | 阴 | |
|---|---|---|
| 晴 | 0.9 | 0.5 |
| 阴 | 0.5 | 0.5 |
由上表我们可以得到马尔可夫链的状态转移矩阵：
$$
P=\left(\begin{array}{ll}0.9 & 0.1 \0.5 & 0.5\end{array}\right)
$$
因此，一阶马尔可夫过程定义了以下三个部分：
- 状态：晴天和阴天
- 初始向量：定义系统在时间为0的时候的状态的概率
- 状态转移矩阵：每种天气转换的概率
1.2 HMM模型的定义
隐马尔可夫模型描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程（李航 统计学习方法）。隐马尔可夫模型由初始状态分布，状态转移概率矩阵以及观测概率矩阵所确定。
假设Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即：状态集合
$$
\begin{aligned} & Q=\left{q_{1},q_{2},\ldots ,q_{N}\right} \quad \left| Q\right| =N \end{aligned}
$$
与观测集合
$$
\begin{aligned} & V=\left{v_{1},v_{2},\ldots ,v_{M}\right} \quad \left| V\right| =M \end{aligned}
$$
其中，N是可能的隐藏状态数，M是所有的可能的观察状态数。对于一个长度为 T 的序列， I 对应的状态序列, O是对应的观察序列，即：状态序列
$$
\begin{aligned} & I=\left{i_{1},i_{2},\ldots ,i_{t},\ldots,i_{T}\right} \quad i_{t}\in Q \quad \left(t=1,2,\ldots,T \right)\end{aligned}
$$
与观测序列
$$
\begin{aligned} & O=\left{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right} \quad o_{t}\in V \quad \left(t=1,2,\ldots,T \right)\end{aligned}
$$
隐马尔科夫模型基本假设：
齐次马尔科夫性假设：在任意时刻$t$的状态只依赖于时刻 $t-1$ 的状态。
$$
P\left(i_{t} \mid i_{t-1}, o_{t-1}, \ldots, i_{1}, o_{1}\right)=P\left(i_{t} \mid i_{t-1}\right) \quad(t=1,2, \ldots, T)
$$
状态转移矩阵 $\begin{aligned} & A=\left[a_{ij}\right]{N\times N} \end{aligned}$ 在 $t$ 时刻处于状态 $q_{i}$ 的条件下，在 $t+1$ 时刻转移到状态 $q_{j}$ 的概率
$$
\begin{aligned} & a_{ij}= P\left( i_{t+1}=q_{j}|i_{t}=q_{i}\right) \quad \left(i=1,2,\ldots,N \right) \quad \left(j=1,2,\ldots,M \right)\end{aligned}
$$
观测独立性假设：任意时刻 $t$ 的观测状态只依赖于时刻 $t$ 的隐藏状态。
$\begin{aligned} & P\left( o_{t}|i_{T},o_{T},i_{T-1},o_{T-1},\ldots,i_{t+1},o_{t+1},i_{t},i_{t-1},o_{t-1},\ldots,i_{1},o_{1}\right)=P\left(o_{t}|i_{t}\right) \quad \left(t=1,2,\ldots,T\right) \end{aligned}$
观测概率矩阵 $\begin{aligned} & B=\left[b_{j}\left(k\right)\right]{N\times M} \end{aligned}$在 $t$ 时刻处于状态 $q_{i}$ 的条件下，生成观测 $v_{k}$ 的概率
$\begin{aligned} & b_{j}\left(k\right)= P\left( o_{t}=v_{k}|i_{t}=q_{j}\right) \quad \left(k=1,2,\ldots,M \right) \quad \left(j=1,2,\ldots,N \right)\end{aligned}$
其中
初始概率向量$\begin{aligned} & \pi =\left( \pi {i}\right) \end{aligned}$在时刻 $t=1$处于状态 $q_{i}$ 的概率 $\begin{aligned} & \pi_{i} =P\left( i_{1}=q_{i}\right) \quad \left(i=1,2,\ldots,N \right) \end{aligned}$
隐马尔科夫模型可以表示为三元组 $\begin{aligned} & \lambda =\left( A,B.\pi \right) \end{aligned}$
- 将随机变量作为结点，若两个随机变量相关或者不独立，则将二者连接一条边；若给定若干随机变量，则形成一个有向图，即构成一个网络。
- 如果该网络是有向无环图，则这个网络称为贝叶斯网络。
- 如果这个图退化成线性链的方式，则得到马尔可夫模型；因为每个结点都是随机变量，将其看成各个时刻(或空间)的相关变化，以随机过程的视角，则可以看成是马尔可夫过程。
- 若上述网络是无向的，则是无向图模型，又称马尔可夫随机场或者马尔可夫网络。
- 如果在给定某些条件的前提下，研究这个马尔可夫随机场，则得到条件随机场。
- 如果使用条件随机场解决标注问题，并且进一步将条件随机场中的网络拓扑变成线性的，则得到线性链条件随机场。
1.3 HMM模型实例
下面用一个实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型，来源李航的《统计学习方法》。
假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：
| 盒子 | 1 | 2 | 3 |
|---|---|---|---|
| 红球数 | 5 | 4 | 7 |
| 白球数 | 5 | 6 | 3 |
按照下面的方法从盒子里抽球，开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列:
$$
O={红，白，红}
$$
状态集合：
$$
Q ={盒子1，盒子2，盒子3}， N=3
$$
初始分布状态：
$$
\Pi = (0.2,0.4,0.4)^T
$$
状态转移概率分布矩阵为：
$$
A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \ 0.3 & 0.5 & 0.2 \ 0.2 & 0.3 &0.5 \end{array} \right)
$$
观测状态概率矩阵为：
$$
B = \left( \begin{array} {ccc} 0.5 & 0.5 \ 0.4 & 0.6 \ 0.7 & 0.3 \end{array} \right)
$$
2 HMM模型的三个基本问题
- 评估观察序列概率。即给定模型$\lambda =\left( A,B,\pi \right)$和观察序列$O=\left{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right}$，计算在模型$\lambda$下观测序列$O$出现的概率$P\left(O| \lambda \right)$。这个问题的求解需要用到前向后向算法，这个问题是HMM模型三个问题中最简单的。
- 模型参数学习问题。即给定观测序列$O=\left{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right}$，估计模型$\lambda =\left( A,B,\pi \right)$的参数，使该模型下观测序列的条件概率$P\left(O| \lambda \right)$最大。这个问题的求解需要用到基于EM算法的鲍姆-韦尔奇算法， 这个问题是HMM模型三个问题中最复杂的。
- 预测问题，即解码问题。即给定模型$\lambda =\left( A,B,\pi \right)$和观测序列$O=\left{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right}$，求给定观测序列条件下，最可能出现的对应的状态序列，这个问题的求解需要用到基于动态规划的维特比算法，这个问题是HMM模型三个问题中复杂度居中的算法。
对应的三大问题解法：
- 前向算法(Forward Algorithm)、后向算法(Backward Algorithm)
- 鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)
- 维特比算法(Viterbi Algorithm)
2.1 前向后向算法评估观测序列概率
2.1.1 前向算法求观测概率
前向概率递推计算
前向算法本质上属于动态规划的算法，也就是要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。给定模型$\lambda$，时刻$t$部分观测序列为$o_{1},o_{2},\ldots ,o_{t}$且状态为$q_{i}$的概率$\begin{aligned} & \alpha {t}\left( i\right) =P\left(o_{1},o_{2},\ldots ,o_{t}, i_{t}=q_{i}| \lambda \right) \end{aligned}$称为前向概率。
前向概率递推计算
$\begin{aligned} & \alpha {t}\left( i\right) =P\left(o{1},o{2},\ldots ,o_{t}, i_{t}=q_{i}| \lambda \right)＝P\left(i_{t}=q_{i},o_{1}^t \right) \ & =\sum {j=1}^{N}P\left(i{t-1}=q_{j},i_{t}=q_{i},o_{1}^{t-1},o_{t}\right) \ & =\sum {j=1}^{N}P\left(i{t}=q_{i},o_{t}|i_{t-1}=q_{j},o_{1}^{t-1}\right)\cdot P\left(i_{t-1}=q_{j},o_{1}^{t-1} \right) \ & =\sum {j=1}^{N}P\left(i{t}=q_{i},o_{t}|i_{t-1}=q_{j}\right)\cdot \alpha_{t-1}\left( j\right)\ & =\sum {j=1}^{N}P\left(o{t}|i_{t}=q_{i},i_{t-1}=q_{j}\right)\cdot P\left(i_{t}=q_{i}|i_{t-1}=q_{j}\right)\cdot \alpha_{t-1}\left( j\right) \ & =\sum {j=1}^{N}b{i}\left(o{t}\right)\cdot a_{ji}\cdot \alpha {t-1}\left( j\right)\end{aligned}$
概率计算
$\begin{aligned} & P\left(O| \lambda \right) =P\left(o{1}^{T}| \lambda\right) = \sum_{i=1}^{N}P\left(o_{1}^{T},i_{T}=q_{i}\right) = \sum _{i=1}^{N}\alpha _{T}\left( i\right)\end{aligned}$
观测序列概率计算的前向算法：
● 输入：隐马尔科夫模型$\lambda=(A,B,\pi)$，观测序列$O=\left{o_{1},o_{2},\ldots ,o_{t},\ldots,o_{T}\right}$;
● 输出：观测序列概率$P\left(O| \lambda \right)$；
初值：$\begin{aligned} & \alpha_{1}\left( i\right)= \pi_{i}b_{i}\left(o_{1}\right) \quad \left(t=1,2,\ldots,N\right) \end{aligned}$
递推：对$t=1,2,\ldots,T-1$有$\begin{aligned} & \alpha_{t+1}\left( i\right) =\sum {j=1}^{N}b{i}\left(o_{t+1}\right)\cdot a_{ji}\cdot \alpha _{t}\left( j\right) \quad \left(t=1,2,\ldots,N\right) \end{aligned}$
终止：$\begin{aligned} & P\left(O| \lambda \right)= \sum _{j=1}^{N}\alpha _{T}\left( i\right)\end{aligned}$
2.1.2 前向算法求解实例
按照我们上一节的前向算法。首先计算时刻1三个状态的前向概率：
- 时刻1是红色球，隐藏状态是盒子1的概率为：$\alpha_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1$
- 隐藏状态是盒子2的概率为：$\alpha_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16$
- 隐藏状态是盒子3的概率为：$\alpha_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28$
现在开始递推，首先递推时刻2三个状态的前向概率：
时刻2是白色球，隐藏状态是盒子1的概率为：
$\alpha_2(1) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i1}\Big]b_1(o_2) = [0.10.5+0.160.3+0.28*0.2 ] \times 0.5 = 0.077$
隐藏状态是盒子2的概率为：
$\alpha_2(2) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i2}\Big]b_2(o_2) = [0.10.2+0.160.5+0.28*0.3 ] \times 0.6 = 0.1104$
隐藏状态是盒子3的概率为：
$\alpha_2(3) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i3}\Big]b_3(o_2) = [0.10.3+0.160.2+0.28*0.5 ] \times 0.3 = 0.0606$
继续递推，现在我们递推时刻3三个状态的前向概率：
时刻3是红色球，隐藏状态是盒子1的概率为：
$\alpha_3(1) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i1}\Big]b_1(o_3) = [0.0770.5+0.11040.3+0.0606*0.2 ] \times 0.5 = 0.04187$
隐藏状态是盒子2的概率为：
$\alpha_3(2) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i2}\Big]b_2(o_3) = [0.0770.2+0.11040.5+0.0606*0.3 ] \times 0.4 = 0.03551$
隐藏状态是盒子3的概率为：
$\alpha_3(3) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i3}\Big]b_3(o_3) = [0.0770.3+0.11040.2+0.0606*0.5 ] \times 0.7 = 0.05284$
最终我们求出观测序列:的概率为：$O={红，白，红}$的概率为：
$P(O|\lambda) = \sum\limits_{i=1}^3\alpha_3(i) = 0.13022$
2.1.3 后向算法求观测概率
后向概率递推计算
后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”。给定模型，时刻状态为的条件下，从时刻到时刻的部分观测序列为的概率称为后向概率。
后向概率递推计算$$
\begin{aligned} & \beta {t}\left( i\right) =P\left(o{t+1},o_{t+2},\ldots ,o_{T}| i_{t}=q_{i}, \lambda \right)＝P\left(o_{t+1}^T |i_{t}=q_{i}\right) \ & =\dfrac {P\left(o_{t+1}^{T}, i_{t}=q_{i}\right)} {P\left(i_{t}=q_{i}\right)}\ & =\dfrac {\sum_{j=1}^{N} P\left(o_{t+1}^{T},i_{t}=q_{i},i_{t+1}=q_{j}\right)}{P\left(i_{t}=q_{i}\right)}\ & =\sum_{j=1}^{N} \dfrac {P\left(o_{t+1}^{T}|i_{t}=q_{i},i_{t+1}=q_{j}\right) \cdot P\left(i_{t}=q_{i},i_{t+1}=q_{j} \right)}{P\left(i_{t}=q_{i}\right)} \ & = \sum_{j=1}^{N} P\left(o_{t+1}^{T}|i_{t+1}=q_{j}\right) \cdot \dfrac {P\left(i_{t+1}=q_{j}|i_{t}=q_{i}\right) \cdot P\left(i_{t}=q_{i} \right)}{P\left(i_{t}=q_{i} \right)} \ & = \sum_{j=1}^{N} P\left(o_{t+2}^{N},o_{t+1}|i_{t+1}=q_{j}\right) \cdot a_{ij} \ & = \sum_{j=1}^{N} P\left(o_{t+2}^{T}|i_{t+1}=q_{j}\right) \cdot P\left(o_{t+1}|i_{t+1}=q_{j}\right) \cdot a_{ij} \ & = \sum_{j=1}^{N} \beta_{t+1}\left(j\right) \cdot b_{j}\left(o_{t+1}\right) \cdot a_{ij}\end{aligned}
$$概率计算
$$
\begin{aligned} & P\left(O| \lambda \right) =P\left(o_{1}^{T}| \lambda\right) \ & = \sum_{i=1}^{N}P\left(o_{1}^{T},i_{1}=q_{i}\right)\ & = \sum_{i=1}^{N}P\left(i_{1}=q_{i}\right) \cdot P\left(o_{1}|i_{1}=q_{i}\right)\cdot P\left(o_{2}^{T}|i_{1}=q_{i}\right) \ & = \sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}\left(i\right)\end{aligned}
$$
观测序列概率计算的后向算法：
● 输入：隐马尔科夫模型$\lambda$，观测序列$O$;
● 输出：观测序列概率$P\left(O| \lambda \right)$；
- 初值：$\begin{aligned} & \beta_{T}\left( i\right)= 1 \quad \left(t=1,2,\ldots,N\right) \end{aligned}$；
- 递推：对$t=T-1,T-2,\ldots,1$有$\begin{aligned} & \beta_{t}\left( i\right) =\sum_{j=1}^{N} \beta_{t+1}\left(j\right) \cdot b_{j}\left(o_{t+1}\right) \cdot a_{ij} \quad \left(t=1,2,\ldots,N\right) \end{aligned}$；
- 终止
$\begin{aligned} & P\left(O| \lambda \right)= \sum_{j=1}^{N}\pi_{i} b_{i}\left(o_{1}\right)\beta _{1}\left( i\right) \end{aligned}$；
2.2 鲍姆-韦尔奇算法
2.2.1 鲍姆-韦尔奇原理
鲍姆-韦尔奇算法原理既然使用的就是EM算法的原理，那么我们需要在E步求出联合分布$P(O,I|λ)$
基于条件概率$P(I|O,\overline{\lambda})$的期望，其中$\overline{\lambda}$为当前的模型参数，然后再M步最大化这个期望，得到更新的模型参数λ。接着不停的进行EM迭代，直到模型参数的值收敛为止。
首先来看看E步，当前模型参数为$\overline{\lambda}$, 联合分布$P(O,I|λ)$基于条件概率$P(I|O,\overline{\lambda})$的期望表达式为：
$$
L(\lambda, \overline{\lambda}) = \sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)
$$
在M步，我们极大化上式，然后得到更新后的模型参数如下：
$$
\overline{\lambda} = arg;\max_{\lambda}\sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)
$$
通过不断的E步和M步的迭代，直到$\overline{\lambda}$收敛。下面我们来看看鲍姆-韦尔奇算法的推导过程。
2.2.2 鲍姆-韦尔奇算法推导
算法详细推导
Q函数是完全数据 $\begin{aligned} & \left( O, I \right) = \left(o_{1}, o_{2}, \cdots, o_{T}, i_{1}, i_{2}, \cdots, o_{T} \right)\end{aligned}$ 的对数似然函数$\begin{aligned} & \log P \left( O, I | \lambda \right) \end{aligned}$关于给定模型参数和观测变量的前提下对隐变量的条件概率分布的期望，即 $Q \left( \lambda, \overline{\lambda} \right)$ 函数：
$$
\begin{aligned} Q \left( \lambda, \overline{\lambda} \right) &= E_{I} \left[ \log P \left( O, I | \lambda \right) | O, \overline{\lambda} \right] = \sum_{I} \log P \left( O, I | \lambda \right) P \left( I | O, \overline{\lambda} \right) \&= \sum_{I} \log \dfrac{P \left( O, I | \lambda \right) P \left( O, I | \overline{\lambda} \right) }{P \left( O | \overline{\lambda} \right)}\end{aligned}
$$其中，$\overline{\lambda}$ 是隐马尔科夫模型参数的当前估计值，$\lambda$ 是隐马尔科夫模型参数。由于$P \left( O | \overline{\lambda} \right)$ 为常数因子，$\begin{aligned} & P \left( O, I | \lambda \right) = \pi_{i_{1}} b_{i_{1}} \left( o_{1} \right) a_{i_{1}i_{2}} b_{i_{2}} \left( o_{2} \right) \cdots a_{i_{T-1}i_{T}}b_{T}\left( o_{T} \right)\end{aligned}$，所以$Q \left( \lambda, \overline{\lambda} \right)$函数可以写成：
$\begin{aligned} & \lambda = \arg \max{Q \left( \lambda, \overline{\lambda} \right) }\Leftrightarrow \arg\max \sum_{I} \log P \left( O, I | \lambda \right) P \left( O, I | \overline{\lambda} \right)
\ & = \sum_{I} \log \pi_{i_{1}} P \left( O, I | \overline{\lambda} \right) + \sum_{I} \left( \sum_{t=1}^{T-1} \log a_{i_{t}i_{t+1}} \right) P \left( O, I | \overline{\lambda} \right) + \sum_{I} \left( \sum_{t=1}^{T} \log b_{i_{t}} \left( o_{t} \right) \right) P \left( O, I | \overline{\lambda} \right)\end{aligned}$下面对三项分别进行极大化：$$
\begin{aligned} & \max \sum_{I} \log \pi_{i_{1}} P \left( O, I | \overline{\lambda} \right) = \sum_{i=1}^{N} \log \pi_{i_{1}} P \left( O, i_{1}=i | \overline{\lambda} \right)
\ & s.t. \sum_{i=1}^{N} \pi_{i} = 1 \end{aligned}
$$构造拉格朗日函数，对其求偏导，令结果为0
$$
\begin{aligned} & \dfrac{\partial}{\partial \pi_{i}} \left[ \sum_{i=1}^{N} \log \pi_{i_{1}} P \left( O, i_{1}=i | \overline{\lambda} \right) + \gamma \left( \sum_{i=1}^{N} \pi_{i} - 1 \right) \right] = 0\end{aligned}
$$得
$$
\begin{aligned} & P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} = 0
\ & \sum_{i=1}^{N} \left[ P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} \right] = 0
\ & \sum_{i=1}^{N} P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \sum_{i=1}^{N} \pi_{i} = 0
\ & P \left( O | \overline{\lambda} \right) + \gamma = 0
\ & \gamma = - P \left( O | \overline{\lambda} \right)\end{aligned}
$$代入$P \left( O, i_{1} = i | \overline{\lambda} \right) + \gamma \pi_{i} = 0$，得
$$
\begin{aligned} & \pi_{i} = \dfrac{P \left( O, i_{1} = i | \overline{\lambda} \right)}{P \left( O | \overline{\lambda} \right)}
= \gamma_{1} \left( i \right) \end{aligned}
$$得
$$
\begin{aligned} \ & \max \sum_{I} \left( \sum_{t=1}^{T-1} \log a_{i_{t}i_{t+1}} \right) P \left( O, I | \overline{\lambda} \right) = \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{t=1}^{T-1} \log a_{ij} P \left( O, i_{t}=i, i_{t+1}=j | \overline{\lambda} \right)
\ & s.t. \sum_{j=1}^{N} a_{ij} = 1 \end{aligned}
$$$$
\begin{aligned} \ & a_{ij} = \dfrac{\sum_{t=1}^{T-1} P \left( O, i_{t}=i, i_{t+1}=j | \overline{\lambda} \right)}{\sum_{t=1}^{T-1} P \left( O, i_{t}=i | \overline{\lambda} \right)}
= \dfrac{\sum_{t=1}^{T-1} \xi_{t} \left( i,j \right) }{\sum_{t=1}^{T-1} \gamma_{t} \left( i \right)}\end{aligned}
$$得
$$
\begin{aligned} \ & \max \sum_{I} \left( \sum_{t=1}^{N} \log b_{i_{t}} \left( o_{t} \right) \right) P \left( O, I | \overline{\lambda} \right) = \sum_{j=1}^{N} \sum_{t=1}^{T} \log b_{j} \left( o_{t} \right) P \left( O, i_{t}=j | \overline{\lambda} \right)
\ & s.t. \sum_{k=1}^{M} b_{j} \left( k \right) = 1 \end{aligned}
$$$$
\begin{aligned} \ & b_{j} \left( k \right) = \dfrac{\sum_{t=1}^{T} P \left( O, i_{t}=j | \overline{\lambda} \right) I \left( o_{t} = v_{k} \right)}{\sum_{t=1}^{T} P \left( O, i_{t}=j | \overline{\lambda} \right)}
= \dfrac{ \sum_{t=1,o_{t}=v_{k}}^{T} \gamma_{t} \left( j \right)}{\sum_{t=1}^{T} \gamma_{t} \left( j \right)}\end{aligned}
$$
Baum-Welch算法：
● 输入：观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$
● 输出：隐马尔科夫模型参数
初始化：对$n=0$，选取$a_{ij}^{ \left( 0 \right) },b_{j} \left( k \right)^{\left( 0 \right)},\pi_{i}^{\left( 0 \right)}$，得到模型$\lambda^{\left( 0 \right)} = \left( a_{ij}^{ \left( 0 \right) },b_{j} \left( k \right)^{\left( 0 \right)},\pi_{i}^{\left( 0 \right)} \right)$
递推：对$n=1,2, \cdots,$$a_{ij}^{\left( n+1 \right)} = \dfrac{\sum_{t=1}^{T-1} \xi_{t} \left( i,j \right) }{\sum_{t=1}^{T-1} \gamma_{t} \left( i \right)},$$b_{j} \left( k \right)^{\left( n+1 \right)} = \dfrac{ \sum_{t=1,o_{t}=v_{k}}^{T} \gamma_{t} \left( j \right)}{\sum_{t=1}^{T} \gamma_{t} \left( j \right)},$$\pi_{i}^{\left( n+1 \right)} = \dfrac{P \left( O, i_{1} = i | \overline{\lambda} \right)}{P \left( O | \overline{\lambda} \right)},$其中，右端各值按观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$和模型$\lambda^{\left( n \right)} = \left( A^{\left( n \right)},B^{\left( n \right)},\pi^{\left( n \right)} \right)$计算。
终止：得到模型$\lambda^{\left( n＋1 \right)} = \left( A^{\left( n+1 \right)},B^{\left( n+1 \right)},\pi^{\left( n+1 \right)} \right)$，在时刻$t$状态为$i$的所有单个路径$\left( i_{1}, i_{2}, \cdots, i_{t} \right)$中概率最大值为
$\begin{aligned} \ & \delta_{t} \left( i \right) = \max_{i_{1}, i_{2}, \cdots, i_{t-1}} P \left(i_{t}=i, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1} | \lambda \right) \quad i = 1, 2, \cdots, N \end{aligned}$
2.3 维特比算法
2.3.1 维特比算法流程
维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。
维特比算法：
● 输入：模型$\lambda = \left( A, B, \pi \right)$和观测数据$O = \left( o_{1}, o_{2}, \cdots, o_{T} \right)$
● 输出：最优路径$I^{} = \left( i_{1}^{}, i_{2}^{}, \cdots, i_{T}^{} \right)$
- 初始化
$$
\begin{aligned} \ & \delta_{1} \left( i \right) = \pi_{i} b_{i} \left( o_{1} \right) \quad \quad \quad i = 1, 2, \cdots, N
\ & \psi_{1} \left( i \right) = 0 \end{aligned}
$$
递推：对$t=2,3, \cdots, T$有
$$
\begin{aligned} \ & \delta_{t} \left( i \right) = \max_{1 \leq j \leq N} \left[ \delta_{t-1} \left( j \right) a_{ji}\right] b_{i} \left( o_{t} \right)\quad \quad \quad i = 1, 2, \cdots, N
\ & \psi_{t} \left( i \right) = \arg \max_{1 \leq j \leq N} \left[ \delta_{t-1} \left( j \right) a_{ji} \right] \quad \quad \quad i = 1, 2, \cdots, N \end{aligned}
$$终止
$$
\begin{aligned} \ & P^{} = \max_{1 \leq j \leq N} \delta_{T} \left( i \right)
\ & i_{T}^{} = \arg \max_{1 \leq j \leq N} \left[ \delta_{T} \left( i \right) \right] \end{aligned}
$$最优路径回溯：对$t=T-1,T-2, \cdots, 1$有$\begin{aligned} i_{t}^{} = \psi_{t+1} \left( i_{t+1}^{} \right) \end{aligned}$，求得最优路径$I^{} = \left( i_{1}^{}, i_{2}^{}, \cdots, i_{T}^{} \right)$
2.3.2 维特比算法求解实例
按照我们上一节的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测状态为1：
$\delta_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1$；
$\delta_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16$；
$\delta_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28$；
$\Psi_1(1)=\Psi_1(2) =\Psi_1(3) =0$；
现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2：
$$
\delta_2(1) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j1}]b_1(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.5, 0.16 \times 0.3, 0.28\times 0.2] \times 0.5 = 0.028 \quad \Psi_2(1)=3
$$$$
\delta_2(2) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j2}]b_2(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.2, 0.16 \times 0.5, 0.28\times 0.3] \times 0.6 = 0.0504 \quad \Psi_2(2)=3
$$$$
\delta_2(3) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j3}]b_3(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.3, 0.16 \times 0.2, 0.28\times 0.5] \times 0.3 = 0.042 \quad \Psi_2(3)=3
$$继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1：
$$
\delta_3(1) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j1}]b_1(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.5, 0.0504 \times 0.3, 0.042\times 0.2] \times 0.5 = 0.00756 \quad \Psi_3(1)=2
$$$$
\delta_3(2) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j2}]b_2(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.2, 0.0504\times 0.5, 0.042\times 0.3] \times 0.4 = 0.01008 \quad \Psi_3(2)=2
$$$$
\delta_3(3) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j3}]b_3(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.3, 0.0504 \times 0.2, 0.042\times 0.5] \times 0.7 = 0.0147 \quad \Psi_3(3)=3
$$此时已经到最后的时刻，我们开始准备回溯。此时最大概率为$\delta_3(3)$，从而得到$i_3^* =3$； 由于$\Psi_3(3)=3$,所以$i_2^* =3$, 而又由于$\Psi_2(3)=3$,所以$i_1^* =3$。从而得到最终的最可能的隐藏状态序列为：(3,3,3)。
3 HMM模型的实现
对应的，HMM的三个要素可以解释为，初始状态分布就是每一个标注作为句子第一个字的标注的概率，状态转移概率矩阵就是由某一个标注转移到下一个标注的概率（设状态转移矩阵为$M$，那么若前一个词的标注为$tag_i$，则下一个词的标注为$tag_j$的概率为$M_{ij}$），观测概率矩阵就是指在某个标注下，生成某个词的概率。根据HMM的三个要素，我们可以定义如下的HMM模型:
1 | class HMM(object): |
定义模型之后，接下来的开始训练模型。HMM模型的训练过程对应隐马尔可夫模型的学习问题（李航 统计学习方法），实际上就是根据训练数据根据最大似然的方法估计模型的三个要素，即上文提到的初始状态分布、状态转移概率矩阵以及观测概率矩阵。举个例子帮助理解，在估计初始状态分布的时候，假如某个标记在数据集中作为句子第一个字的标记的次数为k，句子的总数为N，那么该标记作为句子第一个字的概率可以近似估计为k/N，很简单对吧，使用这种方法，我们近似估计HMM的三个要素，代码如下（出现过的函数将用省略号代替）：
1 | class HMM(object): |
模型训练完毕之后，要利用训练好的模型进行解码，就是对给定的模型未见过的句子，求句子中的每个字对应的标注，针对这个解码问题，我们使用的是维特比（viterbi）算法。
1 | class HMM(object): |
实体识别需要从文本中抽取两类信息，不同类型的实体本身token组合的信息（实体长啥样），以及实体出现的上下文信息（实体在哪里）一种解法就是通过序列标注把以上问题转化成每个字符的分类问题，label主要有两种其中BIO更常见些
● BIO：B标记实体的开始，I标记其余部分，非实体是O
● BMOES：B标记开始，E标记结束，中间是M，单字实体是S，非实体是O
序列标注模型经历了从HMM到MEMM再到CRF的更迭，让我们来简单对比下三个模型。
4 序列标注模型
例如在分词任务中，中文的句子“请问今天的天气怎么样？”就是可以被观测到的序列，而其分词的标记序列就是未知的状态序列“请问/今天/深圳/的/天气/怎么样/？”这种分词方式对应的标记序列为“BEBEBESBEBME”
标记序列：标签方案中通常都使用一些简短的英文字符[串]来编码。
标签列表如下，在分词任务中，通常用BMES标记。
B，即Begin，表示开始
M，即Mediate，表示中间
E，即End，表示结尾
S，即Single，表示单个字符
4.1 HMM
隐马尔可夫有向图模型，由观测序列和隐状态序列构成，在NER问题中观测序列就是输入句子，隐状态就是实体label，模型包含3个核心假设：
- 齐次马尔可夫性假设：当前实体label只和前一位置的label有关$P(s_{t}|s_{1,2,…t-1})=P(s_{t}|s_{t-1})$
- 不动性假设：转移概率矩阵和位置无关$P(s_i|s_{i-1})=P(s_j|s_{j-1})$
- 观测独立假设：观测只和当前位置隐状态有关$P(O_t|s_{1,2,…t-1},O_{1,2,…t-1})=P(O_t|s_t)$
用HMM来对NER问题建模需要把条件概率先转化为联合概率如下
$$
\begin{align}argmax P(s_1,…,s_T|O_1,…,O_T) &\propto argmax P(s_1,…,s_T,O_1,…,O_T)\&= argmax P(O_1,…,O_T|s_1,…,s_T)\cdot P(s_1,…,s_T)\&= argmax P(s_0)\cdot \prod_{i=1}^TP(s_t|s_{t-1})\cdot P(O_t|s_t)\end{align}
$$
以上也就得到了HMM需要求解的三个变量
- 初始状态$P(s_0)$：句子第一个label是B-PER/I-PER/…/O的概率
- 全局转移矩阵$P(s_t|s_{t-1})$：B-PER->I-PER, I-PER->B-LOC，实体label间的转移概率
- 输出概率$P(O_t|s_t)$：P(北｜B-LOC)已知状态输出是某一token的概率
预测过程，既对已知观测序列，求解最有可能的状态序列。直接求解长度为 T，label_size=N的序列是$O(N^T)$的复杂度，通常采用动态规划的Viterbi算法来把复杂度降低到$O(N^2T)$。
但是使用HMM来求解 NER 主要存在两个问题：
- 观测独立假设，每个输出（character）当然不只依赖隐状态（label）还会依赖上下文信息
- HMM作为生成模型要计算联合概率，如果要引入额外特征来描述观测，例如大小写前缀后缀，需要计算每个特征的likelihood，所以很难引入额外特征。同时模型拟和的是联合概率，和预测需要的P(S|O)条件概率存在不一致。
4.2 MEMM
HMM在序列标注中的优势是隐状态间的跳转，会有效提高实体预测label之间的一致性。让我们保留优点，放松观测独立的假设，再把生成模型换成判别模型，直接对P(S|O)进行建模我们就得到了MEMM最大熵马尔可夫模型。MEMM可以方便的引入任意特征来对观测数据进行描述，并且没有观测独立假设后实体标签可以依赖任意上下文信息。
最大熵模型是对数线性模型，即 logistic regression，每个step都是多分类问题，输入F是基于 t 和 t-1 时刻的状态以及观测序列X构建的特征函数，输出是t时刻各个状态的概率(sum=1局部正则化），以下Z是正则因子
$$
P(s_t|s_{t-1}, O) = \frac{1}{Z(s_{t-1},O)}exp(W^T \cdot F(s_t,s_{t-1},O))
$$
用MEMM求解给定观测下最优的标注序列如下
$$
\begin{align}& argmax P(s_1,…,s_T|O_1,…,O_T) \&=\prod_{i=1}^TP(s_t|s_{t-1},O_1,…O_T) \&=\prod_{i=1}^T\frac{1}{Z(s_{t-1},O)}exp(W^T \cdot F(s_t,s_{t-1},O)) \\end{align}
$$
但是使用MEMM来求解NER村咋如下问题：
- LabelBias: MEMM的局部正则化会导致预测时倾向于选择可转移状态更少的状态。很多博客都详细介绍了这个问题最大熵马尔可夫模型（MEMM）及其三个基本问题
4.3 CRF
!8d068995-7c92-4377-b74f-650cb9f924cf.png
保留MEMM判别模型，马尔可夫状态转移，以及每个状态都依赖完整上下文的优点，CRF直接在全局进行正则化，解决了label bias的问题。对比MEMM在每个step进行正则化得到概率，CRF是直接对 T 个step所有$N^T$个可能状态路径计算全局概率进行正则化，如下
$$
\begin{align}& argmax P(s_1,…,s_T|O_1,…,O_T) \&=\frac{1}{Z(x)} \prod_{i=1}^Texp(W^T \cdot F(s_i,s_{i-1},O))\&=\frac{1}{\sum_{N^T\text{个paths} }exp( \sum_{i=1}^T W^T \cdot F(s_i,s_{i-1},O))}exp( \sum_{i=1}^T W^T \cdot F(s_i,s_{i-1},O))\end{align}
$$
以上特征函数F可以进一步拆解成L个转移类特征和K个状态类特征之和
$$
W^T \cdot F(s_{i-1},s_i,O) = \sum_{k=1}^{K} w_k f_k(s_i,O) + \sum_{l=1}^{L} w_l f_l(s_i,s_{i-1},O)
$$
让我们来看下tensorflow中 tf.contrib.crf 的相关实现。其中转移特征函数是全局的转移矩阵，状态特征是最后一个layer输出的logit。解码同样是viterbi就不多说了，训练时loglikelihood的计算分为以下几步
计算真实序列的特征得分
● $binary_{score} =\sum_{\text{real path}} \text{transition probabitliy}$
● $unary_{score} =\sum_{\text{real path}} \text{logits}$
● $sequence_score = bianry_score + unary_score$计算用于正则化的全部路径得分：
log_normcrf_log_norm巧妙利用了矩阵计算把遍历所有路径$O(N^T)$的复杂度降低到了$O(N^2T)$, 每一步都是N*N的矩阵乘积运算在CrfForwardRnnCell中实现，细节可以去看李航大大的统计学习方法，简单来说就是定义矩阵M$$
\begin{align}M(s_{i-1},s_i|O) &= exp(W^T \cdot F(s_i,s_{i-1},O))\log(Z(x))&= log(s_1) + \sum_{i=2}^{T-1} M_i(X) +log(s_T)\\end{align}
$$输出crf_log_likelihood = sequence_score - log_norm
4.4. 模型对比
- EM算法是用于含有隐变量模型的极大似然估计或者极大后验估计，有两步组成：E步，求期望（expectation）；M步，求极大（maxmization）。本质上EM算法还是一个迭代算法，通过不断用上一代参数对隐变量的估计来对当前变量进行计算，直到收敛。注意：EM算法是对初值敏感的，而且EM是不断求解下界的极大化逼近求解对数似然函数的极大化的算法，也就是说EM算法不能保证找到全局最优值。对于EM的导出方法也应该掌握。
- 隐马尔可夫模型是用于标注问题的生成模型。有几个参数（π，A，B）：初始状态概率向量π，状态转移矩阵A，观测概率矩阵B。称为马尔科夫模型的三要素。马尔科夫三个基本问题：概率计算问题：给定模型和观测序列，计算模型下观测序列输出的概率。–> 前向后向算法学习问题：已知观测序列，估计模型参数，即用极大似然估计来估计参数。–> Baum-Welch(也就是EM算法)和极大似然估计。预测问题：已知模型和观测序列，求解对应的状态序列。–> 近似算法（贪心算法）和维比特算法（动态规划求最优路径）
- 条件随机场CRF，给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布密度。条件随机场假设输出变量构成马尔科夫随机场，而我们平时看到的大多是线性链条随机场，也就是由输入对输出进行预测的判别模型。求解方法为极大似然估计或正则化的极大似然估计。
- 之所以总把HMM和CRF进行比较，主要是因为CRF和HMM都利用了图的知识，但是CRF利用的是马尔科夫随机场（无向图），而HMM的基础是贝叶斯网络（有向图）。而且CRF也有：概率计算问题、学习问题和预测问题。大致计算方法和HMM类似，只不过不需要EM算法进行学习问题。
- HMM和CRF对比：其根本还是在于基本的理念不同，一个是生成模型，一个是判别模型，这也就导致了求解方式的不同。
5 参考资料
- HMM隐马尔可夫模型详解
- 隐马尔可夫模型（Hidden Markov Model）
- 统计学习方法，李航著，清华大学出版社
- HMM的Baum-Welch算法和Viterbi算法公式推导细节
- Bert-Bilstm-CRF基线模型详解&代码实现
