隐马尔科夫模型

引言

隐马尔可夫模型是关于时许序列的概率模型。是由一个隐藏的马尔科夫链随机生成不可观测的状态序列，然后由状态序列生成一个观测序列的过程。

每个状态生成一个观测，同时每个状态会转移到下一个状态。因此马尔科夫过程有两个关键的序列，一个是状态序列，一个是观测序列。

上图就是一个标准的马尔科夫过程的观测输出以及状态转移过程。

隐马尔科夫模型由初始概率分布，转移状态矩阵概率分布，观测状态概率矩阵确定。

假设我们的状态集合为$Q = \left \{ q_1,...,q_N \right\}$

观测集合为$V = \left \{ v_1,...,v_M \right\}$

上面的两个集合是观测和状态的取值集合。

假设我们的markov过程的状态序列为$I = (i_1,...,i_T)$

观测序列为$O = ( o_1,...,o_T)$

我们可以写出状态的转移矩阵$A = [a_{ij}]_{N*N}$,其中$a_{ij} = P(i_{t+1} = q_j | i_{t} = q_i )$,

也就是从$t$时间点状态$i$转移到$t+1$时间点状态$j$的概率。

我们也可以写出观测矩阵$B = [b_{j}(k)]_{N*M}$,其中$b_{j}(k) = P(o_{t} = v_k | i_{t} = q_j )$,

也就是从$t$时间点状态$j$的观测值为$v_k$的概率。

再加上我们的初始概率$\pi = (\pi_i)$,其中$\pi_i = P(i_1=q_i)$

因此本质上我们的markov过程受如下的参数控制：

$$\lambda = (\pi,A,B)$$

隐markov过程需要满足的假设条件

1） 齐次马尔科夫假设

即$P(i_t | i_{t-1},o_{t-1},...,i_1,o_1) = P(i_t | i_{t-1})$

也就是$t$时刻的状态只决定于$t-1$时刻的状态，跟其他时刻的状态以及观测无关。

2） 观测独立性假设

即$P(o_t | i_T,o_T,i_{T-1},o_{T-1},...,i_1,o_1) = P(o_t | i_{t})$

也就是某一时刻的观测只与这一时刻的状态有关，跟其他时刻的状态以及观测无关。

不满足这两个朴素的假设条件，后面的一切推导都是错误的。

隐马尔可夫模型的三个基础问题

1） 概率计算

即给定参数$\lambda = (\pi,A,B)$和观测$O = \left \{ o_1,...,o_T \right\}$，计算$P(O|\lambda)$，即某一观测序列出现的概率问题。

2） 学习问题

即已知$O = \left \{ o_1,...,o_T \right\}$，估计参数$\lambda = (\pi,A,B)$，即参数估计问题。

3） 预测问题

已知$\lambda = (\pi,A,B)$和观测$O = \left \{ o_1,...,o_T \right\}$，求使$P(I|O)$最大的状态序列，也就是能得到当前观测的最可能的状态序列。

下面我们就这三个问题，一个一个的解决

概率计算问题

概率计算就是计算$P(O|\lambda)$，给定了$\lambda = (\pi,A,B)$，这个计算就是一个简单的算数问题。那么我们来看下直接计算：

直接计算

首先第一步，计算状态序列为$I = ( i_1,...,i_T)$时的概率为：

$$P(I|\lambda) = \pi_{i_1}a_{i_1i_2}a_{i_2i_3}...a_{i_{T-1}i_T}$$

当状态序列为$I = ( i_1,...,i_T)$时，观测序列为$O = ( o_1,...,o_T)$时的概率为：

$$P(O | I, \lambda) = b_{i_1}(o_1) b_{i_2}(o_2) ... b_{i_T}(o_T)$$

根据条件概率，可以得到：

$$P(O, I | \lambda) = \pi_{i_1} b_{i_1}(o_1) a_{i_1i_2} b_{i_2}(o_2) ... a_{i_{T-1}i_T} b_{i_T}(o_T)$$

对所有可能的状态求和，可以得到：

$$P(O | \lambda) = \sum_I P(O, I | \lambda) = \sum_{i_{1},...,i_{T}} \pi_{i_1} b_{i_1}(o_1) a_{i_1i_2} b_{i_2}(o_2) ... a_{i_{T-1}i_T} b_{i_T}(o_T)$$

这样计算是可以的，但是这个计算量太大了，是$O(TN^T)$阶的。

因此引入了前向算法和后向算法。这两个算法能有效的降低计算复杂度。

前向算法

首先定义前向概率：

$$\alpha_t(i) = P(o_1,...,o_t, i_t = q_i|\lambda)$$

前向概率表示时刻$t$，部分观测序列为$o_1,...,o_t$, 且时刻$t$状态为$q_i$的概率

前向算法：

初始值：$\alpha_1(i) = P(o_1, i_1 = q_i|\lambda) = \pi_ib_i(o_1)$

递推：$\alpha_{t+1}(i) = P(o_1,...,o_t,o_{t+1}, i_{t+1} = q_i|\lambda) = [\sum_{j=1}^N \alpha_t(j)a_{ji}] b_i(o_{t+1})$

终止：$\alpha_T(i) = P(o_1,...,o_T, i_T = q_i|\lambda)$

$$P(O|\lambda) = \sum_{i=1}^N \alpha_T(i)$$

因此前向算法的本质就是计算前向概率，然后将其递推到全局

后向算法

首先定义后向概率

$$\beta_t(i) = P(o_{t+1},...,o_T | i_t = q_i, \lambda)$$

后向算法：

初始： $\beta_T(i) = 1$

递推： 对于$t = T-1, T-2,...,1$

$$\beta_t(i) = P(o_{t+1},...,o_T | i_t = q_i, \lambda) = \sum_{j=1}^N a_{ij} b_j(o_{t+1})\beta_{t+1}(j)$$

终止：$P(O|\lambda) = \sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)$

后向算法的递推图示：

前向后向概率表示

利用前向后向概率可以得到：

$$P(O|\lambda) = \sum_{i=1}^N \sum_{j=1}^N \alpha_t(i) a_{ij} b_{j}(o_{t+1})\beta_{t+1}(j)$$

推导如下：

$$\alpha_t(i) = P(o_1,...,o_t, i_t = q_i|\lambda)$$ $$\beta_t(i) = P(o_{t+1},...,o_T | i_t = q_i, \lambda)$$

则$\alpha_t(i) a_{ij}$表示观测为$o_1,...,o_t$，状态由$q_i$转到$q_j$的概率

则$\alpha_t(i) a_{ij} b_j(o_{t+1})$表示观测为$o_1,...,o_t,o_{t+1}$，状态由$q_i$转到$q_j$的概率

则则$\alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)$ 表示观测为$o_1,...,o_t,...,o_{T}$，状态由$q_i$转到$q_j$的概率

对状态$i$和状态$j$求和，就可以得到$P(O|\lambda)$

前向后向概率的几个特殊的统计值

1. 定义给定参数$O, \lambda$的情况下，时刻$t$处于状态$q_i$的概率为:

$$\gamma_t(i) =P(i_t = q_i|O, \lambda)$$

则：

$$\gamma_t(i) =P(i_t = q_i|O, \lambda) = \frac{P(i_t = q_i, O| \lambda)}{P(O|\lambda)}$$

由前向概率和后向概率

$$\alpha_t(i) = P(o_1,...,o_t, i_t = q_i|\lambda)$$ $$\beta_t(i) = P(o_{t+1},...,o_T | i_t = q_i, \lambda)$$

可以得到：

$$P(i_t = q_i, O| \lambda) = P(o_1,...,o_t,...,o_T, i_t = q_i|\lambda)$$ $$= P(o_1,...,o_t,...,o_T| i_t = q_i, \lambda) P( i_t = q_i| \lambda)$$ $$= P(o_1,...,o_t| i_t = q_i, \lambda) P(o_{t+1},...,o_T| i_t = q_i, \lambda) P( i_t = q_i| \lambda)$$ $$= P(o_1,...,o_t| i_t = q_i, \lambda)P( i_t = q_i| \lambda) P(o_{t+1},...,o_T| i_t = q_i, \lambda)$$ $$= P(o_1,...,o_t, i_t = q_i|\lambda) P(o_{t+1},...,o_T| i_t = q_i, \lambda)$$ $$= \alpha_t(i) \beta_t(i)$$

于是可以得到：

$$\gamma_t(i) =P(i_t = q_i|O, \lambda) = \frac{\alpha_t(i) \beta_t(i)}{\sum_j^N \alpha_t(j) \beta_t(j)}$$

1. 定义给定参数$O, \lambda$的情况下，时刻$t$处于状态$q_i$且时刻$t+1$处于状态$q_j$的概率为:

   $$\xi_t(i, j) = \frac{P(i_t = q_i,i_{t+1} = q_j, O|\lambda)}{P(O|\lambda)}$$

而：

$$P(i_t = q_i,i_{t+1} = q_j, O|\lambda)$$ $$= P(o_1,...,o_t,...,o_T| i_t = q_i, i_{t+1} = q_j, \lambda) P( i_t = q_i, i_{t+1} = q_j|\lambda)$$ $$= P(o_1,...,o_t,...,o_T| i_t = q_i, i_{t+1} = q_j, \lambda) P(i_{t+1} = q_j|i_t = q_i, \lambda) P(i_{t} = q_i| \lambda)$$ $$= P(o_1,...,o_t| i_t = q_i,i_{t+1} = q_j, \lambda) P(o_{t+1}| i_t = q_i, i_{t+1} = q_j,\lambda) P(o_{t+2},...,o_T| i_t = q_i, i_{t+1} = q_j,\lambda) P(i_{t+1} = q_j|i_t = q_i, \lambda) P(i_{t} = q_i| \lambda)$$ $$= P(o_1,...,o_t| i_t = q_i,i_{t+1} = q_j, \lambda) P(o_{t+1}| i_t = q_i, i_{t+1} = q_j,\lambda) P(o_{t+2},...,o_T| i_t = q_i, i_{t+1} = q_j,\lambda) a_{ij}P(i_{t} = q_i| \lambda)$$ $$= P(o_1,...,o_t| i_t = q_i, i_{t+1} = q_j, \lambda)P(i_{t} = q_i| \lambda) P(o_{t+1}| i_t = q_i, i_{t+1} = q_j,\lambda) P(o_{t+2},...,o_T| i_t = q_i, i_{t+1} = q_j,\lambda) a_{ij}$$ $$= P(o_1,...,o_t| i_t = q_i, i_{t+1} = q_j, \lambda)P(i_{t} = q_i| i_{t+1} = q_j, \lambda) P(o_{t+1}| i_t = q_i, i_{t+1} = q_j,\lambda) P(o_{t+2},...,o_T| i_t = q_i, i_{t+1} = q_j,\lambda) a_{ij}$$ $$= P(o_1,...,o_t, i_t = q_i| i_{t+1} = q_j, \lambda) P(o_{t+1}| i_t = q_i, i_{t+1} = q_j,\lambda) P(o_{t+2},...,o_T| i_t = q_i, i_{t+1} = q_j,\lambda) a_{ij}$$ $$= P(o_1,...,o_t, i_t = q_i| \lambda) P(o_{t+1}| i_t = q_i,\lambda) P(o_{t+2},...,o_T| i_{t+1} = q_j,\lambda) a_{ij}$$ $$= \alpha_t(i)b_j(o_{t+1}) \beta_t(j) a_{ij} = \alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_t(j)$$

所以有：

$$\xi_t(i, j) = \frac{P(i_t = q_i,i_{t+1} = q_j, O|\lambda)}{P(O|\lambda)} = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_t(j) }{\sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_t(j)}$$

这里我们之所以这么费事的要推导出这两个概率，是为了后面的预测算法做铺垫，后面会用到

参数估计

监督学习

上面我们推导了概率计算问题，那么下面我们就要来面对一个很机器学习的问题了，参数估计。给定数据，估计分布，这个是统计机器学习的主要内容。

首先如果我们已经知道了状态序列，那么这个参数估计就好办多了，直接统计值就行了，这种属于监督学习。

如果已知状态序列和观测序列为$O = \left \{ (o_1,I_i),...,(o_T,I_T) \right\}$

则状态转移概率的估计：

$$\hat{a}_{ij} = \frac{A_{ij}}{\sum_{j=1}^N A_{ij}}$$

其中$A_{ij}$为时刻$t$处于状态$i$且时刻$t+1$转移到状态$j$的频数

则观测概率的估计：

$$\hat{b}_{j}(k) = \frac{B_{jk}}{\sum_{k=1}^M B_{jk}}$$

其中$B_{jk}$为状态$j$观测为$K$的频数。

可是现实生活中哪有这样好的事情，我们最长面对的情况是只拿得到观测，而拿不到状态，这时，我们看怎样处理

非监督学习

如果已知观测序列为$O = \left \{ o_1,...,o_T \right\}$，状态序列未知，估计参数。我们发现这正好是EM算法的能力啊，只要将状态$I$作为隐变量，就可以用EM算法来解决这个问题了。

首先，我们知道

$$P(O|\lambda) = \sum_I P(O,I|\lambda) = \sum_I P(O|I,\lambda)P(I|\lambda)$$

根据EM算法的步骤，首先我们需要写出完全数据的对数似然函数$logP(O,I|\lambda)$：

$$Q(\lambda, \bar{\lambda}) = E_I[logP(O,I|\lambda)|O,\bar{\lambda}] = \sum_I logP(O,I|\lambda)P(I|O,\bar{\lambda}) = \frac{\sum_I logP(O,I|\lambda)P(I,O|\bar{\lambda})}{P(O|\bar{\lambda})}$$

其中${P(O|\bar{\lambda})}$跟最优化$\lambda$无关，因此可以省略掉，因此完全函数可以写为：

$$Q(\lambda, \bar{\lambda}) = \sum_I logP(O,I|\lambda)P(I,O|\bar{\lambda})$$

而：

$$P(I,O|\bar{\lambda}) = \pi_{i_1} b_{i_1}(o_1) a_{i_1i_2} b_{i_2}(o_2) ... a_{i_{T-1}i_T} b_{i_T}(o_T)$$

因此$Q(\lambda, \bar{\lambda})$函数可以写为：

$$Q(\lambda, \bar{\lambda}) = \sum_I log \pi_{i_1} P(I,O|\bar{\lambda}) + \sum_I(\sum_{t=1}^{T-1} log a_{i_t i_{t+1}}) P(O,I|\bar{\lambda}) + \sum_I(\sum_{t=1}^{T} log b_{i_t}(o_t)) P(O,I|\bar{\lambda})$$

E步完成后，就该M步的了：
由于我们需要极大话的三个项，分别在上面的三个分式中，因此单独极大化上面的分式即可。

第一项：

$$\sum_I log \pi_{i_1} P(I,O|\bar{\lambda}) = \sum_1^N log\pi_iP(O,i_i=i|\bar(\lambda))$$

参数$\pi_i$满足的约束条件为$\sum_i^N \pi_i = 1$,因此利用拉格朗日乘子法，可以得到拉格朗日函数

$$\sum_1^N log\pi_iP(O,i_i=i|\bar{\lambda)} + \gamma(\sum_i^N \pi_i - 1)$$

对其求偏导并令其结果为0，可以得到：

$$\frac{\partial }{\partial \pi_i} [\sum_1^N log\pi_iP(O,i_i=i|\bar{\lambda)} + \gamma(\sum_i^N \pi_i - 1)] = 0$$

得到：

$$P(O,i_i=i|\bar{\lambda}) + \gamma \pi_i =0$$

对i求和，可得：

$$\gamma = - P(O|\bar{\lambda})$$

带如到上式有：

$$\pi_i = \frac {P(O, i_1 = i|\bar{\lambda})}{P(O|\bar{\lambda})}$$

同理，可以得到另外两项的估计，如下所示：

$$a_{ij} = \frac {\sum_{t=1}^{T-1} P(O, i_t = i, i_{t+1} = j |\bar{\lambda})}{ \sum_{t=1}^{T-1} P(O, i_t =i|\bar{\lambda})}$$ $$b_{j}(k) = \frac {\sum_{t=1}^{T} P(O, i_t = j |\bar{\lambda})I(o_t = v_k)}{ \sum_{t=1}^{T} P(O, i_t =j|\bar{\lambda})}$$

如果引入我们之前的统计量

$$\gamma_t(i) =P(i_t = q_i|O, \lambda) = \frac{P(i_t = q_i, O| \lambda)}{P(O|\lambda)}$$ $$\xi_t(i, j) = \frac{P(i_t = q_i,i_{t+1} = q_j, O|\lambda)}{P(O|\lambda)}$$

那么参数估计可以写为：

$$a_{ij} = \frac {\sum_{t=1}^{T-1} \xi_t(i, j)}{ \sum_{t=1}^{T-1} \gamma_t(i)}$$ $$b_{j}(k) = \frac {\sum_{t=1,o_t = v_k}^{T} \gamma_t(j)}{ \sum_{t=1}^{T} \gamma_t(j)}$$ $$\pi_i = \gamma_1(i)$$

预测问题

近似算法

所谓近似算法，就是每个时刻选择最优可能出现的状态，将她作为这个时刻的结果。

给定$\lambda, O$，有

$$\gamma_t(i) = P(i_t=q_i|O,\lambda) = \frac{P(i_t = q_i, O| \lambda)}{P(O|\lambda)} = \frac{\alpha_t(i) \beta_t(i)}{\sum_j^N \alpha_t(j) \beta_t(j)}$$

则，每个时刻的最优可能的状态：

$$i_t^{*} = arg max_{1 \leq i \leq N} [\gamma_t(i)], t=1,2,..,T$$

进而得到状态序列$I^* = (i_1^*,...,i_T^{*})$

近似算法简单，易于计算，但是这个不是最优的结果。其实我们的预测算法本质上就是一个最优路径的问题，因此可以引入动态规划的原理来解决，这就是Viterbi算法

Viterbi算法

输入: $\lambda=(A,B,\pi)$和$O=(o_1,...,o_T)$

初始化：

计算$\delta_1(i) = \pi_i b_i(o_1), i=1,2,...,N$

$$\psi_1(i) = 0$$

更新参数

$$\delta_t(i) = max_{1 \leq j \leq N}[\delta_{t-1}(j)a_{ji}]b_i(o_t), i=1,2,...,N$$ $$\psi_t(i) = max_{1 \leq j \leq N}[\delta_{t-1}(j)a_{ji}], i=1,2,...,N$$

终止

$$P^* = max_{1 \leq i \leq N} (\delta_T(i))$$ $$i_T^* = arg max_{1 \leq i \leq N} (\delta_T(i))$$

最优路径回溯

对$t =T-1,T-2,...,1$

$$i_t^* = \psi_{t+1} (i_{t+1}^*)$$

总结

上面就是隐马尔可夫模型的三个基本问题以及相应的求解方式。本质上讲，隐马尔可夫模型比较简单，但是也比较常用，在分词，语音识别方面有着广泛的应用，不过由于深度学习横空出世，单纯的隐马尔科夫模型略显无奈啊。