Loading... > 隐马尔科夫模型（Hidden Markov Model，HMM）是经典的机器学习模型，它在语言识别自然语言处理，等领域得到广泛的应用。虽然随着目前深度学习的崛起，尤其是RNN等神经网络序列模型的火热，HMM的地位有所下降。但是作为一个经典的模型，学习HMM，对提高我们分析问题和对问题建模的能力很有帮助的。 ## 1、什么问题可以用HMM 一般可以用HMM进行建模的问题都有两个重要特征： - 在一段时间内变化的`序列`，可能是时间序列，也可能是状态序列。如计算机中的指令序列，口语单词中的音素序列等。 - 问题中有两类数据，一类是可以观测到的，称为`观测序列`；另一类是不能观察到的，称为隐藏状态序列（`状态序列`）。 ## 2、HMM定义  首先，我们假设`Q`是所有可能的隐藏状态的集合，`V`是所有可能的观测状态的集合，即： $$ \begin{array}{c} Q = \{q_1,q_2,...,q_N\} & V=\{v_1,v_2,...,v_M\} \end{array} $$ 我们取总体中的一个样本，对于一个长度为T的序列，I对应状态序列，O对应观测序列，即 $$ \begin{array}{c} I = \{i_1,i_2,...,i_T\} & O=\{o_1,o_2,...,o_T\} \end{array} $$ HMM的两个前提： （1）齐次马尔科夫链假设，当前时刻的状态只依赖于它前一时刻的状态，当前状态不受未来状态影响。这样我们就可以定义隐藏状态的转移概率$a_{ij}$ $$ a_{ij}=P(i_{t+1}=q_j|i_t=q_i) $$ 进而$a_{ij}$可以组成状态转移矩阵$A$ $$ A= \left [ a_{ij} \right ] _{N\times N} $$ （2）观测独立性假设。任意时刻的观察状态只依赖于当前的隐藏状态，即$t$时刻隐藏状态为$q_j$，对应的观测值为$v_k$，定义$b_j(k)$满足： $$ b_j(k)=P(o_t=v_k|i_t=q_j) $$ 进而$b_j(k)$可以组成发射矩阵$B$: $$ B=\left [ a_{ij} \right ] _{N\times M} $$ 除了状态转移矩阵$A$和发射矩阵$B$，我们还需要定义在时刻$t=1$的隐藏状态初始概率分布分布$\pi$。因此，HMM模型可由一个三元组$\lambda$表示为： $$ \lambda=(\pi,A,B) $$ ## 3、HMM的三个问题 - `Evaluation`：评估观测序列概率。给出$\lambda$，和观测序列O，计算在已知模型参数$\lambda$的前提下，得到观测序列O的概率$P(O|\lambda)$。解决这个问题的方法是`前向后向算法`。 - `Decoding`：解码问题。给出$\lambda$，和观测序列O，求在确定观测序列的前提下，最可能出现的对应隐藏状态序列。这个问题需要用到`维特比算法`。 - `Learning`：模型参数学习问题。给定观测序列O，估计模型参数$\lambda$，使该模型下观测序列的条件概率$P(O|\lambda)$最大。这个问题的求解需要用到`基于EM算法的鲍姆-韦尔奇算法`。 ### 3.1 HMM前向算法流程（The Forward Procedure） > 输入：HMM模型$\lambda=(\pi, A, B)$，观测序列$O=\{o_1,o_2,...,o_T\}$ > > 输出：观测序列概率$P(O|\lambda)$ 首先定义前向变量$\alpha_t(i)$： $$ \alpha_t(i)=P(o_1o_2...o_t,q_t=i|\lambda) $$ 上式表示：在模型参数$\lambda$已知的条件下，在$t$时刻，当观测序列为$o_1o_2...o_t$并且$t$时刻状态为$i$时的概率。我们可以用以下步骤来求解$\alpha_t(i)$。 1. **Initialization** $$ \alpha_1(i)=\pi_i b_i(o_1) $$ 2. **Induction** $$ \alpha_{t+1}(j)=[\sum_{i=1}^{N}\alpha_t(i)a_{ij} ]b_j(o_{t+1}) $$ 3. **Termination** $$ P(O|\lambda)=\sum_{i=1}^{N}\alpha_T(i) $$ `Initialization Step`，计算时刻1的各个隐藏状态前向概率。 `The Induction Step`，递推时刻$2,3,...,T$时刻的前向概率（如图2）： `Termination Step`，计算最终结果。  ### 3.2 HMM后向算法流程 ### 3.3 维特比算法（The Viterbi Algorithm） > 输入：HMM模型$\lambda=(\pi, A, B)$，观测序列$O=\{o_1,o_2,...,o_T\}$ > > 输出：最可能的隐藏状态序列$I={i_1,i_2,...,i_T}$ 第一个局部状态是在时刻$t$隐藏状态为$i$所有可能的状态转移路径$i_1,i_2...i_t$中的概率最大值。记为$\delta _t(i)$ $$ \delta_t(i)=maxP(i_t=i_1i_2...i_{t-1}, o_1o_2...o_{t-1}|\lambda) $$ $\delta$的递推表达式： $$ \delta_{t+1}(i)=max[\delta_t(i)a_{ij}]\cdot b_j(o_{t+1}) $$ - **Initialization** $$ \delta_1(i)=\pi_ib_i(o_1) \\ \psi_1(i)=0 $$ - **Recursion** $$ \delta_t(j)=max[\delta_{t-1}a_{ij}]b_j(o_t) \\ \psi_t(i)=arg max[\delta_{t-1}(i)a_{ij}] $$ - **Termination** $$ P^*=max \delta_T(i) \\ i^*_T=argmax[\delta_T(i)] $$ - **Path backtracking** $$ i^*_t=\psi_{t+1}(i^*_{t+1}) $$ `Initialization`：初始化局部时刻1状态 `Recursion`：进行动态规划递推时刻$t=2,3,...,T$时刻的局部状态 `Termination`：计算时刻T最大的$\delta_T(i)$，即最可能隐藏状态序列出现的概率。 `Paht backtracking`，利用局部状态$\psi(i)$开始回溯，最终得到最有可能的隐藏状态序列$I^*=\{i^*_1,i^*_2,...,i^*_T\}$ ### 3.4 鲍姆-韦尔奇算法 ## 4、HMM实例讲解 举个例子，你女朋友每天下班之后，她会根据天气情况有相应的活动：要么是去商场购物，要么呆在家收拾房间。有时候你们会打电话，她会告诉我你这几天做了什么，而闲着没事的你呢，则要通过她的行为猜测这几天对应的天气最有可能是什么样子的。  根据以上描述，我们给出以下定义： 观察集合是： $$ V = \{Clean, Shopping\} $$ 隐藏状态集合是： $$ Q=\{Sun, Cloud, Rain\} $$ 初始状态分布为： $$ \pi=(0.2,0.4,0.4) $$ 状态转移矩阵为：  发射矩阵为：  观测序列为： $$ O=\{Clean, Shopping, Clean\} $$ ### 4.1 问题一（Evaluation） #### 4.1.1 HMM前向算法 已知整个模型，你女朋友告诉你，连续三天，她下班后做的事情分别是：`Clean`，`Shopping`，`Clean`。那么，根据模型，计算产生这些行为的概率是多少。 首先计算第一天（$t=1$）三个状态的前向概率。 > $\alpha_t(i)$代表第$t$天，当观测值为$o_t$时，隐藏状态为$i$的概率。为了简化表示，我使用1，2，3来替代隐藏状态`Sun`，`Cloud`，`Rain`。 第一天你女朋友在`Clean` - 天气是`Sun`的概率为： $$ \alpha_1(1)=\pi_1b_1(o_1)=0.2\times0.5=0.1 $$ - 天气是`Cloud`的概率为： $$ \alpha_1(2)=\pi b_2(o_1)=0.4\times0.4=0.16 $$ - 天气时`Rain`的概率为： $$ \alpha_1(3)=\pi b_3(o_1)=0.4\times 0.7=0.28 $$ 然后开始递推： > 递推时，画出使用如Figure2的前向图计算要比使用公式计算更直观，更加的那。 第二天（$t=2$），你女朋友去`Shopping`： - 天气时`Sun`的概率： $$ \alpha_2(1)=[\sum_{i=1}^{3}\alpha_1(i)a_{i1} ]b_1(o_2)=[0.1\times0.5+0.16\times0.3+0.28\times0.2]\times0.5=0.077 $$ - 天气是`Cloud`的概率为： $$ \alpha_2(2)=[\sum_{i=1}^{3}\alpha_1(i)a_{i2} ]b_2(o_2)=[0.1\times0.2+0.16\times0.5+0.28\times0.3]\times0.6=0.1104 $$ - 天气时`Rain`的概率为： $$ \alpha_2(3)=[\sum_{i=1}^{3}\alpha_1(i)a_{i3} ]b_3(o_2)=[0.1\times0.3+0.16\times0.2+0.28\times0.5]\times0.3=0.0606 $$ 第三天）—$t=3$—你女朋友在家`Clean`： - 天气时`Sun`的概率： $$ \alpha_3(1)=[\sum_{i=1}^{3}\alpha_2(i)a_{i1} ]b_1(o_3)=[0.077\times0.5+0.1104\times0.3+0.0606\times0.2]\times0.5=0.04187 $$ - 天气是`Cloud`的概率为： $$ \alpha_3(2)=[\sum_{i=1}^{3}\alpha_2(i)a_{i2} ]b_2(o_3)=[0.077\times0.2+0.1104\times0.5+0.0606\times0.3]\times0.4=0.03551 $$ - 天气时`Rain`的概率为： $$ \alpha_3(3)=[\sum_{i=1}^{3}\alpha_2(i)a_{i3} ]b_3(o_3)=[0.077\times0.3+0.1104\times0.2+0.0606\times0.5]\times0.7=0.05284 $$ 最终我们可以求出在已知模型参数和观测序列的前提下，得到该观测序列$O=\{Clean, Shopping, Clean\}$的概率为： $$ P(O|\lambda)=\sum_{i=1}^{3}\alpha_3(i)=0.13022 $$ #### 4.1.1 HMM后向算法 ### 4.2 问题二（Decoding） 已知整个模型，你女朋友告诉你，连续三天，她下班后做的事情分别是：`Clean`，`Shopping`，`Clean`。那么，是什么样的天气，让她在三天内最有可能做这三件事。 #### 维特比算法 按照上一节的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测值为$o_1$： $$ \delta_1(1)=\pi_1b_1(o_1)=0.2\times0.5=0.1 \\ \delta_1(2)=\pi_2b_2(o_1)=0.4\times0.4=0.16 \\ \delta_1(3)=\pi_3b_3(o_1)=0.4\times0.7=0.28 \\ \psi_1(1)=\psi_1(2)=\psi_1(3)=0 $$ 接下来递推三个隐藏状态在时刻2时对应的两个局部状态，此时观测值为$o_2$ $$ \delta_2(1)=max[\delta_1(j)a_{j1}]b_1(o_2)=max[0.1\times0.5,0.16\times0.3,0.28\times0.2]\times0.5=0.028 \\\psi_2(1)=3 \\ \delta_2(2)=max[\delta_1(j)a_{j2}]b_2(o_2)=max[0.1\times0.2,0.16\times0.5,0.28\times0.3]\times0.6=0.0504 \\\psi_2(2)=3 \\ \delta_2(3)=max[\delta_1(j)a_{j3}]b_3(o_2)=max[0.1\times0.3,0.16\times0.2,0.28\times0.5]\times0.3=0.042 \\\psi_2(3)=3 $$ 继续递推三个隐藏状态在$t=3$时刻对应的两个局部状态，此时观测值为$o_3$ $$ \delta_3(1)=max[\delta_2(j)a_{j1}]b_1(o_3)=max[0.028\times0.5,0.10504\times0.3,0.042\times0.2]\times0.5=0.00756 \\\psi_3(1)=2 \\ \delta_3(2)=max[\delta_2(j)a_{j2}]b_2(o_3)=max[0.028\times0.2,0.0504\times0.5,0.042\times0.3]\times0.4=0.01008 \\\psi_3(2)=2 \\ \delta_3(3)=max[\delta_2(j)a_{j3}]b_3(o_3)=max[0.028\times0.3,0.0504\times0.2,0.042\times0.5]\times0.7=0.0147 \\\psi_3(3)=3 $$ 此时我们回溯整个过程，选择P最大的$\delta_3(3)$，得到$i^*_3=\psi_3(3)=3$ 。 $i^*_2=\psi_3(i^*_3)=3$，$i^*_1=\psi_2(i^*_2)=3$。 得到最可能的隐藏状态序列为$\{3,3,3\}$。  ## 5、hmmlearn实践隐马尔可夫模型HMM > To Do 【1】[用hmmlearn学习隐马尔科夫模型HMM](https://www.cnblogs.com/pinard/p/7001397.html) 【2】[HMM求解三大问题的小例子](https://blog.csdn.net/yj13811596648/article/details/88867292) 【3】[hmmlearn](https://hmmlearn.readthedocs.io/en/latest/index.html) ## 6、参考资料 【1】[隐马尔科夫模型HMM（一）HMM模型](https://www.cnblogs.com/pinard/p/6945257.html) 【2】[隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率](https://www.cnblogs.com/pinard/p/6955871.html) 【3】[隐马尔科夫模型HMM（四）维特比算法解码隐藏状态序列](https://www.cnblogs.com/pinard/p/6991852.html) 【4】[如何用简单易懂的例子解释隐马尔可夫模型？](https://www.zhihu.com/question/20962240/answer/64187492) 【5】[GMM-HMM语音识别模型 原理篇](https://blog.csdn.net/abcjennifer/article/details/27346787) ## 7、HMM学习资料 【1】[HMM学习最佳范例](https://www.52nlp.cn/hmm%E5%AD%A6%E4%B9%A0%E6%9C%80%E4%BD%B3%E8%8C%83%E4%BE%8B%E5%85%A8%E6%96%87pdf%E6%96%87%E6%A1%A3%E5%8F%8A%E7%9B%B8%E5%85%B3%E6%96%87%E7%AB%A0%E7%B4%A2%E5%BC%95) 【2】[爱丁堡大学 ASR课程 slides](http://www.inf.ed.ac.uk/teaching/courses/asr/index-2021.html) Last modification：August 28th, 2022 at 05:29 pm © 允许规范转载