隐马尔可夫模型

介绍

HMM结构

状态序列 (上面那行x) 隐藏的马尔科夫链随机生成的状态序列，称为状态序列

观测序列 (下面那行y) 每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列

马尔科夫模型是关于时序的概率模型

隐状态可以转换但是观测状态之间不能互相转换，所以要由隐状态->观测状态和观测状态1->观测状态2

假设Q是所有可能的状态序列，V是所有可能的观测序列

$$Q=q_1,q_2,...,q_N$$$$V=v_1,v_2,...,v_M$$

假设有$N$个隐藏状态，$M$个观测状态

相关信息

好比每天的天气有晴天、阴天、雨天三种状态，而每天的天气又会影响人们的心情，人们的心情有开心、平静、两种状态，这样就有$N=3$个隐藏状态，$M=2$个观测状态

假设$I$是长度为$T$的状态序列，$O$是对应的观测序列。

假设$A$是状态转移概率矩阵，$B$是观测概率矩阵，$\pi$是初始状态概率向量。

HMM参数结构

相关信息

$A$是一个$N\times N$的矩阵，代表从一个状态转移到另一个状态的概率，$B$是一个$N\times M$的矩阵，代表从一个状态转移到一个观测的概率，$\pi$是一个$1\times N$的向量，代表初始状态的概率

---

$$A=[a_{ij}{]}_{N\times N}i,j=1,2,...,N$$

其中$a_{ij}$表示在时刻$t$处于状态$i$的条件下在时刻$t+1$转移到状态$j$的概率

$$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$$

---

$$B=[b_j(k){]}_{N\times M}j=1,2,...,N;k=1,2,...,M$$

其中$b_j(k)$表示在时刻$t$处于状态$j$的条件下生成观测$k$的概率

$$b_j(k)=P(o_t=v_k|i_t=q_j)$$

---

$$\pi =[{\pi }_i{]}_{1\times N}i=1,2,...,N$$

其中${\pi }_i$表示时刻$t=1$处于状态$i$的概率

$${\pi }_i=P(i_1=q_i)$$

隐马尔科夫模型由初始状态概率向量、状态转移概率矩阵A和观测概率矩阵B决定。$\pi$和A决定状态序列，B决定观测序列。因此，隐马尔科夫模型可以由三元符号表示，即：$\lambda =(\pi ,A,B)$。称为隐马尔科夫模型的三要素。

两个基本假设

1. 齐次马尔科夫性假设：假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关。即

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

2. 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他时刻的状态及观测无关。即

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

三个基本问题

1. 概率计算问题：给定模型$\lambda =(A,B,\pi )$和观测序列$O=o_1,o_2,...,o_T$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda )$
2. 学习问题：已知观测序列$O=o_1,o_2,...,o_T$，估计模型$\lambda =(A,B,\pi )$参数，使得在该模型下观测序列概率$P(O|\lambda )$最大
3. 预测问题：已知模型$\lambda =(A,B,\pi )$和观测序列$O=o_1,o_2,...,o_T$，求给定观测序列条件概率$P(I|O,\lambda )$最大的状态序列$I=i_1,i_2,...,i_T$

相关信息

问题一： 给定模型参数，人们心情的状态序列的概率
问题二： 给定人们心情的状态序列，估计模型参数
问题三： 给定模型参数和人们心情的状态序列，预测天气的序列

概率计算问题

在模型$\lambda =(A,B,\pi )$下，给定观测序列$O=o_1,o_2,...,o_T$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda )$

暴力求解

对于状态序列$I=(i_1,i_2,...,i_T)$的概率是:

$$P(I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-1}{i}_T}$$

对上面这种序列，产生的观测序列$O=(o_1,o_2,...,o_T)$的概率是:

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

I和O的联合概率是:

$$P(O,I|\lambda )=P(O|I,\lambda )P(I|\lambda )={\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_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_1{i}_2}{b}_{i_2}(o_2)...a_{i_{T-1}{i}_T}{b}_{i_T}(o_T)$$

这样的时间复杂度是$O(T{N}^T)$

前向算法

引入前向概率${\alpha }_t(i)$，表示时刻$t$处于状态$i$且观测到$o_1,o_2,...,o_t$的概率

$${\alpha }_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda )$$

这里用到了动态规划的思想

对于时刻$t=1$，有

$${\alpha }_1(i)={\pi }_i{b}_i(o_1)i=1,2,...,N$$

对于时刻$t=2,3,...,T$，有

$${\alpha }_{t+1}(i)=[\sum _{j=1}^N{\alpha }_t(j)a_{ji}]b_i(o_{t+1})i=1,2,...,N$$

$a_{ji}$表示在时刻$t$处于状态$j$的条件下在时刻$t+1$转移到状态$i$的概率
$b_i(o_{t+1})$表示在时刻$t+1$处于状态$i$的条件下生成观测$o_{t+1}$的概率

这里的意思是，对于时刻$t+1$，状态$i$的概率是由时刻$t$的所有状态$j$转移到状态$i$的概率乘以状态$i$生成观测$o_{t+1}$的概率

最终的观测序列概率是

$$P(O|\lambda )=\sum _{i=1}^N{\alpha }_T(i)$$

这样的时间复杂度是$O(T{N}^2)$

相关信息

对于每个${\alpha }_t(j)$，都要对$N$个状态$i$求和，因此每个${\alpha }_t(j)$的时间复杂度是$O(N)$
对于每个时间步，都需要计算$N$个${\alpha }_t(j)$
一共有$T-1$个时间步，所以总的时间复杂度是$O(T{N}^2)$

学习问题

Baun-Welch算法

相关信息

Baun-Welch算法是EM算法在隐马尔科夫模型中的应用 建议在看此部分之前先了解EM算法

已知观测序列$O=o_1,o_2,...,o_T$，估计模型$\lambda =(A,B,\pi )$参数，使得在该模型下观测序列概率$P(O|\lambda )$最大

$$\begin{gathered} P(O|\lambda )=\sum _{I}P(O,I|\lambda ) \\ =\sum _{I}P(O|I,\lambda )P(I|\lambda ) \\ =\sum _{i_1,...,i_T}{\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)...a_{i_{T-1}{i}_T}{b}_{i_T}(o_T) \end{gathered}$$

确定完全数据的对数似然函数

$$\begin{array}{rl}L(\lambda )& =\log P(O|\lambda )\\ & =\log \sum _{I}P(O,I|\lambda )\\ & =\log \sum _{I}P(O|I,\lambda )P(I|\lambda )\\ & =\log \sum _{i_1,...,i_T}{\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)...a_{i_{T-1}{i}_T}{b}_{i_T}(o_T)\end{array}$$

首先初始化参数，然后迭代以下两步直到收敛

E步：Q函数

$$\begin{array}{rl}Q(\lambda ,{\lambda }^{{}^{\prime }})& =E_{I|O,{\lambda }^{{}^{\prime }}}[\log P(O,I|\lambda )]\\ & =\sum _{I}P(I|O,{\lambda }^{{}^{\prime }})\log P(O,I|\lambda )\\ & =\sum _{I}P(I|O,{\lambda }^{{}^{\prime }})\log P(O|I,\lambda )P(I|\lambda )\\ & =\sum _{I}P(I|O,{\lambda }^{{}^{\prime }})\log [{\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)...a_{i_{T-1}{i}_T}{b}_{i_T}(o_T)]\\ & =\sum _I\log [{\pi }_{i_1}P(O,I)|{\lambda }^{{}^{\prime }}]+\sum _I(\sum _{t=1}^{T-1}\log a_{i_{t-1},i_t})P(I|O,{\lambda }^{{}^{\prime }})+\sum _I(\sum _{t=1}^{T-1}\log b_{i_t}(o_t))P(I|O,{\lambda }^{{}^{\prime }})\end{array}$$

其中，${\lambda }^{{}^{\prime }}$是模型参数的估计值（常量），$\lambda$是要极大化的参数

M步：极大化Q函数

$${\lambda }^{{}^{\prime }}=\arg \underset{\lambda }{max}Q(\lambda ,{\lambda }^{{}^{\prime }})$$

使用拉格朗日乘子法，约束条件是 $\sum _{i=1}^N{b}_{jk}=$，对$\lambda$求导，得到$\lambda$的更新公式

$$\begin{array}{rl}{\pi }_i& =\frac{P(i_1=q_i|O,{\lambda }^{{}^{\prime }})}{\sum _{j=1}^{N}P(i_1=q_j|O,{\lambda }^{{}^{\prime }})}\\ & =\frac{{\gamma }_1(i)}{\sum _{j=1}^N{\gamma }_1(j)}\end{array}$$$$\begin{array}{rl}{a}_{ij}& =\frac{\sum _{t=1}^{T-1}{\xi }_t(i,j)}{\sum _{t=1}^{T-1}\sum _{j=1}^N{\xi }_t(i,j)}\\ & =\frac{\sum _{t=1}^{T-1}{\xi }_t(i,j)}{\sum _{t=1}^{T-1}{\gamma }_t(i)}\end{array}$$$$\begin{array}{rl}{b}_j(k)& =\frac{\sum _{t=1,o_t=v_k}^T{\gamma }_t(j)}{\sum _{t=1}^T{\gamma }_t(j)}\end{array}$$

其中，${\gamma }_t(i)$表示时刻$t$处于状态$i$的概率，${\xi }_t(i,j)$表示时刻$t$处于状态$i$且时刻$t+1$转移到状态$j$的概率

预测问题

维特比算法

已知模型$\lambda =(A,B,\pi )$和观测序列$O=o_1,o_2,...,o_T$，求给定观测序列条件概率$P(I|O,\lambda )$最大的状态序列$I=i_1,i_2,...,i_T$

这里用到了动态规划的思想，引入前向概率${\alpha }_t(i)$，表示时刻$t$处于状态$i$且观测到$o_1,o_2,...,o_t$的概率，如果已知${\alpha }_t(i)$，则可以递归地计算${\alpha }_{t+1}(i)$

最终的思想就是 构建路径，回溯查找

构建

首先定义两个变量，${\delta }_t(i)$和${\psi }_t(i)$，分别表示时刻$t$处于状态$i$的所有单个路径中概率最大值和在时刻$t$状态为$i$的所有单个路径中概率最大的 前一个状态（第t-1个节点）

也就是分别记录当前状态的最大概率和最大概率对应的前一个状态，前者是为了计算后面的最大概率，后者是为了回溯查找路径

初始化

$${\delta }_1(i)={\pi }_i{b}_i(o_1)$$$${\psi }_1(i)=0$$

递推

由变量$\delta$的递推公式

$${\delta }_{t+1}(i)=\underset{1\le j\le N}{max}[{\delta }_t(j)a_{ji}]b_i(o_{t+1})$$

由变量$\psi$的递推公式

$${\psi }_{t+1}(i)=\arg \underset{1\le j\le N}{max}[{\delta }_t(j)a_{ji}]$$

终止

$$P^{\ast }=\underset{1\le i\le N}{max}{\delta }_T(i)$$

其中，$P^{\ast }$是最大概率，${\delta }_T(i)$是时刻$T$处于状态$i$的所有单个路径中概率最大值

也就是最优路径的概率

$$i_T^{\ast }=\arg \underset{1\le i\le N}{max}{\delta }_T(i)$$

其中，$i_T^{\ast }$是时刻$T$处于状态$i$的所有单个路径中概率最大的状态

也就是最优路径的最后一个状态

回溯

$$i_t^{\ast }={\psi }_{t+1}(i_{t+1}^{\ast })$$

其中，$i_t^{\ast }$是时刻$t$处于状态$i$的所有单个路径中概率最大的状态

根据$\psi$和最优状态$i_T^{\ast }$，可以回溯得到最优路径

这样的时间复杂度是$O(T{N}^2)$

附录

Java Chen

统计学习方法-李航