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 © 允许规范转载