最近工作中经常要用到HMM，所以专门来复习下，主要讲解的是HMM的Forward和Backward算法，以及参数估计算法。
HMM总览
HMM是一个时序的模型，每时每刻都有一个观测者（observation，下图中绿色点，我们已知的）和一个隐式变量（latent variable，下图中灰色点，我们未知的）。下图为一个HMM基本模型，每一条边都是有方向的，隐式变量可以理解为一个状态，每个状态下都会有一个可以观测到的值。横线表示了状态的转移，竖线表示了从状态到观测的生产过程。因此，HMM是一个有向的生成模型（生成观测者），当然也可以把HMM做成一个判别模型。
Forward/Backward算法
HMM中最参数估计使用的是Forward/Backward算法，解码使用的是Viterbi算法。首先来看一下Forward/Backward算法。
F/B算法的主要目的是计算给定观测值x时，其中某个给定的$z_k$的概率值是多少，即$P(z_k|x)$。Forward算法的目的是计算联合概率$P(z_k, x_{1:k})$，其中$x_1:k = (x_1, x_2, …, x_k)$。Backward算法的目的是计算条件概率$P(x_{k+1:n}|z_k)$。那么为什么要用Forward和Backward算法呢？事实上，我们估计HMM参数时，需要计算$P(z_k|x)$，而$P(z_k|x)$可以拆分成$P(z_k, x_{1:k})$和$P(x_{k+1:n}|z_k)$这两项，具体推导如下：
- 根据贝叶斯定理：$P(z_k|x) = P(z_k, x) / P(x)$，其中$P(x)$对任何$z_k$都是等同的，因此可以认为$P(z_k|x)$是正比于$P(z_k, x)$的。在进行计算时，要注意归一化，即$P(z_k|x) = P(z_k, x) / sum(P(z=j, x))$。
- 下面我们把$P(z_k, x)$拆分成Forward和Backward的形式
- 根据贝叶斯定理：$P(z_k, x) = P(x_{k+1:n}|z_k, x_{1:k}) * P(z_k, x_{1:k})$，其中第二项就是我们的Forward算法
- 我们看上式中第一项，发现跟Backward算法就差了一个$x_{1:k}$，由于$x_{1:k}$和$x_{k+1:n}$条件独立于$z_k$的（即$x_{1:k}$全部作用在$z_k$上，而不会对$x_{k+1:n}$产生影响）。因此$P(x_{k+1:n}|z_k, x_{1:k}) = P(x_{k+1:n}|z_k) * P(z_k, x_{1:k})$，其中$P(x_{k+1:n}|z_k)$就是Backward算法，$P(z_k, x_{1:k})$是Forward算法
Forward算法
Forward本质是一个动态规划算法，其目标是计算$P(z_k, x_{1:k})$。既然用动归，我们就要想清楚如何构造$P(z_k, x_{1:k})$的子问题。下面讲一下构造动归的具体思路：
- 我们想构造出：
- 为了引入$z_{k-1}$，考虑使用边缘化的性质：
- 继续推导可得出：
- 公式化简时使用了条件独立性，判断是否条件独立可以使用D-seperation方法
- 状态的初始化如下：
Backward算法
Backward算法就是Forward的相反方向，解决问题的思路也是一样的。其目标是计算$P(x_{k+1:n}|z_k)$，跟Forward一样，我们要把它拆分成更小的子问题，推导过程如下：
参数估计
HMM参数估计涉及到的参数包括：
- A：状态到状态的转移矩阵，假设状态有m个，则$A.shape = m * m$
- B：状态到观测值的发射矩阵，假设观测值为单词，且词表大小为V，则$B.shape = m * V$
- pi：初始状态值，$pi.shape = m * 1$
Complete情况
Complete case指的是每一个latent variable是知道的，如下图：
估计pi
统计每个状态初始出现的次数，如上图中有3个状态，次数分别为[2, 1, 0]，转换成概率为[2/3, 1/3, 0]。
估计状态转移概率A
统计状态间的转移瓷土，上图中的HMM统计如下：
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 2 | 1 | 2 |
| 2 | 1 | 2 | 1 |
| 3 | 0 | 2 | 1 |
转换成概率值：
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 2/5 | 1/5 | 2/5 |
| 2 | 1/4 | 2/4 | 1/4 |
| 3 | 0 | 2/3 | 1/3 |
估计发射概率B
统计每个状态下，看到观测值的数目，上图中HMM的统计如下：
| a | b | c | |
|---|---|---|---|
| 1 | 3 | 2 | 0 |
| 2 | 3 | 0 | 3 |
| 3 | 1 | 2 | 1 |
转换成概率值如下：
| a | b | c | |
|---|---|---|---|
| 1 | 3/5 | 2/5 | 0 |
| 2 | 1/2 | 0 | 1/2 |
| 3 | 1/4 | 1/2 | 1/4 |
Incomplete情况
Incomplete case指的是latent variable，即z，是不知道的。那么这种情况下怎么计算z呢？如果我们知道A、B、$\pi$这三个参数的话，就可以用Forward/Backward算法计算z的期望值，即$P(z_k|x)$，如下图中红色：
上图中红色部分，每个概率值我们可以认为是一个expectation count，也就是说在上图情况下，第1个状态出现了0.8词，第2个状态出现了0.1次，第3个状态出现了0.1次。
那么反过来，如果已知了z的期望值，通过上面统计的方式我们可以计算出参数值。我们可以用这个参数值，再去更新z的期望值，如此循环，直到收敛。一般情况下，我们是先初始化z，在通过z计算参数。
估计$\pi$
计算$P(z_1|x)$，比如对于$x_1$, $p(z_1=1|x) = 0.7$, $p(z_1=2|x) = 0.2$, $p(z_1=3|x) = 0.3$，这里的概率值我们认为是出现的次数就可以。如下图：
接着我们统计每个状态出现的总数：[0.7 + 0.4 + 0.6, 0.2 + 0.4 + 0.3, 0.1 + 0.2 + 0.1] = [1.7, 0.9, 0.4]，转变为概率为[1.7/3, 0.9/3, 0.4/3]。
估计状态转移概率A
A的估计跟语言模型很像。语言模型中，计算bigram概率$P(w_j|w_i)=c(w_i, w_j)/c(w_i)$，其中$c(w_i, w_j)$表示一种联合状态，即$w_i$、$w_j$共现的次数。
在HMM中，我们要计算的是$P(z_k=i, z_{k+1}=j|x)$，而这个值可以使用Forward/Backward计算出来：
- 先计算$P(z_k=1, z_{k+1}=1, x)$、$P(z_k=1, z_{k+1}=2, x)$…$P(z_k=m, z_{k+1}=m, x)$，这是一个$m * m$的矩阵
- $P(z_k=i, z_{k+1}=j|x)$是正比于$P(z_k=i, z_{k+1}=j, x)$的
- $P(z_k=i, z_{k+1}=j, x) = P(z_k=i, z_{k+1}=j, x_{1:k}, x_{k+1}, x_{k+2:n})$
- 根据D-separation（如下图），上式可以写成：$P(z_k, x_{1:k}) P(x_{k+2:n}|z_{k+1}) P(z_{k+1}|z_k) * P(x_{k+1}|z_{k+1})$，由此我们把联合概率转化成了条件概率
- 上式中$P(z_k, x_{1:k})$是Forward算式，$P(x_{k+2:n}|z_{k+1}) $是Backward算式，$P(z_{k+1}|z_k)$是状态转移，$P(x_{k+1}|z_{k+1})$是发射概率
举一个具体的例子（A_{12}、A_{13}同理，我们想得到的就是A_{ij}矩阵）：
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | … | 1.72/6 | (0.3+0.2+0.1+0.3+0.4+0.2+0.2+0.1+0.2+0.1+0.01+0.1)/(0.6+.5+0.6+0.7+0.6+0.5+0.4+0.3+0.6+0.3+0.5+0.1+0.3)=2.27/6 |
| 2 | … | … | … |
| 3 | … | … | … |
转换成概率值：
估计发射概率B
计算$P(z_k|x)$，如下图：
统计每个状态下，看到观测值的数目，上图中HMM的统计如下：
| a | b | c | |
|---|---|---|---|
| 1 | 0.6+0.4+0.1+0.3+0.3=1.7 | 2.9 | 1.6 |
| 2 | 1.7 | 2.3 | 0.7 |
| 3 | 1.6 | 1.8 | 0.7 |
转换成概率值如下：
| a | b | c | |
|---|---|---|---|
| 1 | 1.7/6.2 | 2.9/6.2 | 1.6/6.2 |
| 2 | 1.7/4.7 | 2.3/4.7 | 0.7/4.7 |
| 3 | 1.6/4.1 | 1.8/4.1 | 0.7/4.1 |