统计机器学习13：隐马尔可夫模型(HMM)¶

本页统计信息

本页约 3087 个字, 预计阅读时间 10 分钟。
本页总阅读量次

这一部分内容很大程度上参考了李航老师的《统计学习方法》这一本书中的

模型的定义¶

隐马尔可夫模型(Hidden Markov Model, HMM)是一种描述由隐藏的马尔可夫链生成观测序列的模型，这里的序列可以是时间序列，也可以文本序列等等，一个马尔可夫链可以生成一个随机状态的序列，而这些状态被隐藏不能直接观察(因此称为隐状态)，但是每个状态以一定的概率表现出若干种可能的观测结果，隐马尔可夫模型就是用来描述和建模这类问题的。

我们假设所有可能的隐状态构成的集合是$Q=(q_1,q_2,\dots,q_N)$，而所有可能观测到结果的集合是$V=(v_1,v_2,\dots,v_M)$，即一共有N种隐状态和M种不同的观测结果。同时我们假设要研究的序列长度为T，其隐状态和观测结果序列分别是$I=(i_1,i_2,\dots,i_T),O=(o_1,o_2,\dots,o_T)$

同时各个状态之间会以一定的概率进行转移(HMM假设一个状态只依赖于前一个状态，即隐马尔可夫模型中只存在一阶马尔可夫链)，而每个状态又以一定的概率生成各种不同的观测结果，我们假设状态转移矩阵$A=[a_{ij}]_{N\times N}$，观测概率矩阵$B=[b_j(k)]_{N\times M}$,其中： $$ a_{ij}=P(i_{i+1}=q_j|i_t=q_i),\quad b_j(k)=P(o_t=v_k|i_t=q_j) $$ 另外用$\pi=(\pi_i)$来表示初始概率向量，表示序列初始的时候处于各个可能状态的概率。

状态转移矩阵A和初始概率向量确定了隐藏的马尔可夫链，而观测概率矩阵确定了如何从状态生成观测，因此三者可以共同确定一个马尔可夫模型，可以用三要素$\lambda=(A,B,\pi)$来表示一个隐马尔可夫模型，同时隐马尔可夫模型还有如下假设：

隐藏的马尔可夫链在任何时刻的状态只依赖于前一个位置的状态
任何时候观测到的结果只和当前的状态有关，和其他时刻的状态以及观测到的结果无关

隐马尔可夫模型可以解决这样几种问题：

根据已知的HMM来计算某个序列O出现的概率
根据观测到的序列O来估计模型的各个参数$\lambda$使得该模型下观测到该序列的概率$P(O|\lambda)$最大，换句话说就是极大似然估计
对于给定的HMM和观测序列O，求出最有可能的状态序列I，这实际上就是一个解码问题

概率计算：前向和后向算法¶

第一个任务是计算给定模型$\lambda$条件下某个序列O出现的概率，很明显我们可以用条件概率的公式计算，先考虑所有可能的状态序列，再对所有可能的状态序列产生观测序列O的概率进行求和，即： $$ P(O|\lambda)=\sum_I P(O,I|\lambda)P(I|\lambda) $$ 而状态序列$I=(i_1,i_2,\dots,i_T)$在模型中出现是： $$ P(I|\lambda)=\pi_{i_1}\prod_{j=1}^{T-1}a_{i_ji_{j+1}} $$ 而对于固定的状态序列I出现观测序列O的概率是： $$ P(O|I,\lambda)=\prod_{j=1}^Tb_{i_j}(o_j) $$

前向算法¶

前向算法是给定HMM，并且定义到t时刻为止的序列为$o_1,o_2,\dots,o_t$且当前隐状态为$q_i$的概率记为： $$ \alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_t|\lambda) $$ 前向算法提供了一种动态规划的方式来一个个计算$\alpha_t(i)$，对于t+1时刻，如果当前的隐状态是$q_i$那么这一事件发生的概率也就是$\alpha_{t+1}(i)$，而这一情况可以有不同的t时刻的情况转化而来，t时刻所有可能的情况$\alpha_t(j)$可以有$a_{ji}$的概率转化成$\alpha_{t+1}(i)$，而状态$q_i$表现出观测状态$o_{t+1}$的概率就是$b_i(o_{t+1})$，因此$\alpha_{t+1}(i)$可以表示为： $$ \alpha_{t+1}(i)=\left[\sum_{j=1}^N\alpha_t(j)a_{ji}\right]b_i(o_{t+1}) $$ 最终要计算的$P(O|\lambda)$可以表示为T时刻所有可能的隐状态表现出$o_T$的概率之和，即：

\[ P(O|\lambda)=\sum_{i=1}^N\alpha_{t+1}(i)=\sum_{i=1}^N\left[\sum_{j=1}^N\alpha_t(j)a_{ji}\right]b_i(o_{t+1}) \]

很显然前向算法就是用动态规划简化了HMM中的概率计算问题，我们很容易根据初始值$\alpha_1(i)=\pi_i b_i(o_1)$来计算。

后向算法¶

后向算法定义在t时刻隐状态为$q_i$的条件下，从t+1到T时刻的观测序列为$(o_{t+1},o_{t+2},\dots,o_T)$的概率为： $$ \beta_t(i)=P(o_{t+1},o_{t+2},\dots,o_T|\lambda, i_t=q_i) $$ 然后就可以从$\beta_T(i)=1$开始逐步向前计算，我们发现每个$\beta_t(i)$都有一定的概率转化成不同的$\beta_{t+1}(j)$，而每个t+1时刻的隐状态j又可以以一定的概率转化成观测结果$o_{t+1}$，可以得到： $$ \beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j) $$ 后向算法实际上就是一种反推，我们可以将要求的结果$P(o|\lambda)$表示为t=1的时候所有的可能性的和：

\[ P(O|\lambda )=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)=\sum_{i=1}^N\sum_{j=1}^N\alpha_{t}(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j) \]

还可以将前向后向概率进行结合来计算$P(O|\lambda)$

一些关键量的计算¶

利用前向概率和后向概率可以计算一些关键的统计量(后面会用到)，比如计算在给定模型$\lambda$和观测序列O的条件下，某个时刻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)}{\sum_{j=1}^N P(i_t=q_j,O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)} $$ 这也很好解释，因为在给定了模型的情况下，观测到序列O并且t时刻的状态是$q_i$的概率等价于，t时刻是状态i并且前t个时刻观察到的序列是$o_1,o_2,\dots,o_t$以及给定t时刻状态i后面观察到$o_{t+1},\dots,o_T$两件事情同时发生的概率，也就是对应的前向后向概率的乘积。

同样地我们可以来计算给定模型$\lambda$和观测序列O的条件下，某个时刻t处于状态$q_i$而t+1时刻处于状态$q_j$的概率，记为： $$ \xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|\lambda, O) $$ 我们发现：

\[ \begin{align} \xi_t(i,j)&=P(i_t=q_i,i_{t+1}=q_{j}|\lambda, O)=\frac{P(i_t=q_i,i_{t+1}=q_j|O)}{P(O|\lambda)}\\ &=\frac{P(i_t=q_i,i_{t+1}=q_j|O)}{\sum_{i=1}^N\sum_{j=1}^N P(i_t=q_i,i_{t+1}=q_j|O)}\\ &=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)} \end{align} \]

这是因为在给定观测序列O的条件下t和t+1时刻状态分别是$q_i,q_j$的概率等价于给定模型的条件下，t时刻状态为$t_i$且观测序列为$o_1,o_2,\dots,o_t$，之后状态转移到$q_j$并观测到$o_{t+1}$，然后在已知t+1时刻状态为$q_j$的情况下观测到$o_{t+1},\dots,o_T$这几件事情同时发生的概率。

模型学习算法¶

监督学习¶

如果说我们观测到了一系列长度相同的观测序列$O_1,O_2,\dots ,O_S$和对应的隐状态序列$I_1,I_2,\dots,I_S$，那么这个时候问题就变成了一个监督学习的问题，就比较容易可以求解了，我们可以使用极大似然法直接估计出隐马尔可夫模型的参数$\lambda =(A,B,\pi)$

首先来估计状态转移概率，我们可以直接使用样本中所有从t时刻状态i转移到t+1时刻的状态j的频数$A_{ij}$来估计所有的状态转移概率： $$ a_{ij}=\frac{A_{ij}}{\sum_{j=1}^NA_{ij}} $$ 而观测概率$b_j(k)$也可以使用样本中所有状态为j并且观测结果为k的频数来估计： $$ b_j(k)=\frac{B_{jk}}{\sum_{i=1}^MB_{jk}} $$ 而初始状态直接使用样本中所有初始状态的分布情况作为估计即可。

EM算法¶

假设没有观测到隐状态序列，而只独立观察到了一系列观测序列$O_1,O_2,\dots ,O_S$，那么就需要用EM算法来估计模型的参数，即要用观测到的一系列序列来反向预测模型的参数和隐变量。

首先需要按照EM算法的步骤来求出Q函数：

\[ \begin{align} Q(\lambda|\bar \lambda)&=\sum_IP(O,I|\bar\lambda)\log P(O,I|\lambda )\\ &=\sum_IP(O,I|\bar\lambda)\log\left(\pi_{i_1}\prod_{t=1}^{T-1}a_{i_t,i_{t+i}}\prod_{t=1}^N b_{i_t} (o_t)\right)\\ &=\sum_IP(O,I|\bar\lambda)\log\pi_{i_1}+\sum_IP(O,I|\bar\lambda)\left(\sum_{t=1}^{T-1}\log a_{i_t,i_{t+1}}\right)+\sum_IP(O,I|\bar\lambda)(\sum_{t=1}^T\log b_{i_t}(o_t)) \end{align} \]

然后按照EM算法的步骤需要对Q函数求极大值，我们可以按照上面的推导，分成三部分分别用拉格朗日乘子法来求最大值，约束条件分别是：

\[ \sum_{i=1}\pi_i=1,\sum_{j=1}^Na_{ij}=1,\sum_{k=1}^Mb_j(k)=1 \]

最终求出的参数估计公式如下所示(中间拉格朗日乘子法的求解过程暂时省略)：

\[ a_{ij}^{(n+1)}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)} \]

\[ b_j(k)^{(n+1)}=\frac{\sum_{t=1,o_t=v_k}^{T}\gamma_t(i)}{\sum_{t=1}^{T}\gamma_t(i)} \]

\[ \pi_i^{(n+1)}=\gamma_1(i) \]

按照EM算法的步骤先确定初始值，再一次次迭代就可以完成模型参数的求解。

预测算法¶

HMM的预测算法就是要在给定模型参数和观测序列O的情况下，预测出出现可能性最高的状态序列I，用于预测的HMM也被叫做解码器。

近似算法¶

近似算法非常简单，就是根据每个时间点的观测结果来直接预测出当前时刻最有可能出现的状态$q_i$，根据前面的叙述也就是在每个时刻t找到$\max\gamma_t(i)$，因此我们可以将近似算法的目标表示成：

\[ i^*_t=\arg\max_{1\le i\le N}\gamma_t(i)=\arg\max_{1\le i\le N}\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}=\arg\max_{1\le i\le N}\alpha_t(i)\beta_t(i) \]

但是近似算法只是一种简单的近似，有的时候解出来的并不是最好结果，更有甚者可能解出来两个相邻位置的状态的转移概率可能是0，但是因为算法简单还有事一定的用处。

维特比算法¶

维特比算法是一种用动态规划来求解概率最大路径的，每一步都在当前时刻t和状态$q_j$的条件下找出下一个时刻t+1转移到状态$q_i$并表现出观测结果$o_{t+1}$的所有可能状态中发生概率最大的那个，即选择出：

\[ \delta_{t+1}(i)=\max_{1\le j\le N}\delta_t(j)a_{ji}b_i(o_{t+1}) \]

并可以用一定的方式来保留选择出的路径，这里的$\delta_t(i)$表示的是t时刻状态为i的路径的概率最大值。

颜色主题调整

评论区~

有用的话请给我个star或者follow我的账号!! 非常感谢!!
快来跟我聊天~