【机器学习】隐马尔可夫模型

本文介绍了隐马尔可夫模型，首先介绍了隐马尔科夫模型定义，核心思想是引入了隐状态序列（引入隐状态是所有隐因子模型最巧妙的地方，如：隐因子分解，LDA），然后介绍了隐马尔科夫模型要解决的三个问题，1）在参数已知的情况下计算可观测序列的总概率，2）在给出观测序列数据时学习模型的参数，3）在参数已知的情况下通过维特比解码预测出所有产生可观测序列中概率最大的一条不可观测序列，即序列标注问题。

作者 | 文杰

编辑 | yuquanle

隐马尔可夫模型

A、隐马尔科夫模型定义

隐马尔科夫模型是一种时序的概率模型，描述由一个隐的马尔科夫链随机生成的不可观察的隐状态序列，在每一个隐状态下随机产生观察值构成一个可观测的随机序列。其中关键是状态序列是满足马尔科夫性质的，且可观测序列是由隐藏的状态序列以一定的概率随机生成。

在自然语言中文分词中，由于自然语言是有明显的上下文关系的，即当前字与其前后出现的字都是有关系的。为了表示前一个字对当前字的影响，我们用一个隐状态来表示前的语义状态，用在前一个状态下转移到发射出当前字的隐状态的概率表示前一个字对当前字的影响。整个来说就是把上下文字对字的影响转化成状态对状态的影响。而用发射概率来表示状态到字的关系。值得注意的是隐马尔可夫模型中：

即与之间独立作用。

隐马尔科夫模型由状态集，观测集，初始状态转移概率，状态转移概率，以及发射概率确定。

形式化定义为：

所有可能的隐藏状态集Q，所有可能的观察值集V，其中是可能的状态数，是可能的观察数。

假设是长度为的隐状态序列，是其对应的观测值序列。

是状态转移概率矩阵：

其中,表示第时刻在状态下转移到第时刻状态的概率。

是发射概率矩阵，在隐状态确定之后发射出观测状态的概率：

其中：

表示在状态下发射出的概率。

是初始状态的概率分布：

其中，表示在时刻状态为的概率。

由此，马尔科夫模型定义完成。至于为何这样定义，隐状态的意义是什么，就是模型的价值所在，如何理解隐状态也是一种个人体会。

有了隐马尔科夫模型，接下来看隐马尔科夫模型能做什么？

1、给定一个确定的隐马尔科夫模型（参数确定）和观察序列，计算在该参数下观察序列的输出概率 。

概率计算，由于观测序列的产生于隐状态是相关的，所以需要从隐状态的转移概率入手，通过发射概率间接的转化到观察序列。一般情况下该观测序列对应的隐状态序列有多个，把所有隐状态可能的序列结合观察序列求概率，再求和。

2、学习问题，已知观察序列，估计模型参数，使得在该模型下观测序列的概率最大。

学习问题，假设在不知道模型参数的情况下，而我们有大量的观察序列，那么这些大量的观察序列一定不是偶然是这样,而不是那样的。从概率的角度来讲，是这样，而不是那样的原因就是，是这样的概率大于是那样的概率。如果有大量的观察序列，那么其中必然隐藏了模型的信息。

3、预测问题，已知模型的参数和观察序列O，求解一条使得该观测序列概率最大的隐状态序列 。这样概率计算类似，只需要求最大的即可。

好了，对应上面的三个问题，分别有三个算法求解对应的问题。

1. 概率计算-前向后向算法
2. 参数学习-最大似然估计（有监督），Baum-Walch（无监督）
3. 预测-Viterbi算法

B、概率计算（观察序列的概率）

给定一个确定的隐马尔科夫模型（参数确定）和观察序列，计算在该参数下观察序列的输出概率 。最直接的方法是计算所有可能的概率，即：

其中，这个状态我们是看不见的，且没个时刻的取值都有中，由于隐状态与观察状态无关，其概率为：

由于的取值有种，但序列前后有一个相同的状态，所以整个的复杂度是。

而在参数和隐状态都确定的条件下，产生观察序列的概率为：

即整个时刻的发射概率的乘积。

因此在给定参数的条件下，产生观察序列的概率为:

算法的复杂度为。之所以算法的复杂度高是分别计算和，而忽略了序列之间的递推关系。

下面介绍隐马尔可夫概率计算问题中的前向-后向算法

前向概率：在给定模型的参数和观察序列下，表示时刻的前向概率（从时刻到时刻观察序列）:

由前向递推关系等于在所有可能的前一状态转移到当前状态（同时t时刻发射出观测值）的概率之和：

因此前向算法计算如下：

1. 初值：
2. 前向递推:
3. 求和：

后向概率：在给定模型的参数和观察序列下，表示时刻的后向概率（从时刻到时刻观察序列，）:

值得注意的是，后向概率表示序列从时刻到时刻的概率，所以

由后向递推关系等于所有可能的后一状态逆转移到当前状态（同时时刻发射出观测值）的概率之和

因此后向算法计算如下：

1)初值：

2)反向递推：

3)求和：

前向后向算法：

由上面的前向后向算法，固定时刻的状态，由前向后向算法有：

C、参数估计

一般来讲，隐马尔可夫的参数估计问题分为两种，一种是有监督，一种是无监督的。有监督意味着给定的训练集中观测序列和隐状态序列，此时对应的参数估计问题就可以直接采用最大似然估计；无监督意味着给定的训练集中只有观测序列，此时需要采用EM算法思想，先假设参数，通过期望最大化来获得隐状态序列（硬划分隐状态序列对应到值，软化分隐状态序列对应到概率），然后根据隐状态序列来更新参数，不断迭代至收敛。

有监督(最大似然估计)：

转移概率表示从状态转移到状态的概率:

其中分子表示从状态转移到状态的次数，分母表示从状态转移到任意状态的次数。

发射概率表示在状态下发射出观测值的概率：

其中分子表示在状态下发射出观测值的次数，分母表示在状态下发射出任意状态的次数。

初始状态转移概率为样本中初始状态的概率：

其中分子表示初始状态是的次数，分母表示所有初始状态出现的次数。

无监督（Baum-Welch）：

隐马尔可夫模型中隐状态其实是一个隐变量，EM算法这类含有隐变量模型的通用求解算法，思路是初始化一个隐变量的概率分布，E步：期望最大化来更新样本的隐变量(值，概率)，M步：在隐变量确定的条件下更新隐变量的概率。

D、状态预测

已知模型的参数和观察序列O，求解一条使得该观测序列概率最大的隐状态序列 。这样概率计算类似，只需要求最大的即可。

维特比算法：维特比算法是一种动态规划算法来求解概率最大路径，也是一种求解最优路径问题。而最优路径中总存在这样一个特性：如果最优路径时刻通过结点，那么最优路径中从结点到最终结点的部分路径是所有可能从到路径中最优的（同时从到的路径也是最优的）。依据这一特性，我们可以从开始递推计算时刻下状态为的各种路径的最大概率，直至时刻状态为的最大概率。同时在递推的过程中，我们用一个变量来计住到达最优路径的上一个结点的状态。这样我们就首先确定了时刻的状态值。然后，根据到达该状态的上一个结点状态来递推到。

因此，我们需要引入两个变量，从时刻到时刻状态为的最优路径的概率值，并以此来递推下一时刻状态为的最优路径，即

同时为了记住到达该路径的上一节点的状态，定义如下变量：

有了上面的两个变量，我们就可以获得隐状态的最优路径：

1）初始化

2）递推，对

3）终止

4）最优路径回溯，

求得最优路径。

其中值得注意的是，是无用的，在前向递推到时刻获得最大概率的同时也获得了最优的最终状态，回溯的过程只需要从开始，不需要任何计算，因为中保存了到达当前最优路径状态的上一状态。

代码实战

A、隐马尔可夫模型

/** 
   HMM模型中三个基本问题，概率计算问题，学习参数问题，预测问题。
 针对这三个问题有HMM模型中的 
   1 前向后向算法 
   2 Baum-Welch算法 
   3 Veiterbi算法 
   下面的程序是上面三个算法的实现，考虑到用于分词，所以设计成读取文件的形式 
 但实际上中文分词算法中的学习参数问题并不采用Baum-Welch算法，而是采用监督学习算法中的极大似然估计， 
 所以Baum-Welch算法中读取的文件只是一个极少词的文件，用EM算法求解学习参数。
 所以在学习参数问题上写了两种学习算法，一Baum-Welch算法，二 极大似然估计 
 并采用统计学习方法一书中的例子进行验证Veiterbi算法的正确性。
 最后在另外一个文件中实现极大似然的HMM模型的中文分词 
   测试只考虑一个样本 
   **/ 
 
/** 
 统计学习方法p186例题测试VTB算法正确性 
 把Ntest文件中的字典长度看作观察序列可能值，上下文看作观察序列 
 隐藏状态在参数STATE设置，在字构词分词中STATE=4，测试本例时修改为STATE=3 
 **/ 
   void init_test() 
{ 
 double A[STATE][STATE]= {0.5,0.2,0.3, 
 0.3,0.5,0.2, 
 0.2,0.3,0.5 
 }; 
 double B[STATE][2]= {0.5,0.5, 
 0.4,0.6, 
 0.7,0.3 
 }; 
 double pi[STATE]= {0.2,0.4,0.4}; 
 int i,j; 
   for(i=0; i<STATE; i++) 
 { 
 for(j=0; j<STATE; j++) 
 { 
 hmm_pra.a[i][j]=A[i][j]; 
 } 
 } 
 for(i=0; i<STATE; i++) 
 { 
 for(j=0; j<hmm_pra.len; j++) 
 { 
 hmm_pra.b[i][j]=B[i][j]; 
 } 
 } 
 for(i=0; i<STATE; i++) 
 { 
 hmm_pra.pi[i]=pi[i]; 
 } 
 } 
int HMM() 
{ 
 DataStr data; 
 LoadDataStr(data,"data\\Ntest.txt");//加载训练集，亦为测试集，只考虑了一个样本 
 createOset(data);//建立词典 
 init_test(); 
 cout<<"-------------forwardBack-----------------"<<endl; 
 forwardBack(data); 
 cout<<"-------------Baum_Weach-----------------"<<endl; 
 Baum_Weach(data); 
 cout<<"-------------Viterbi-----------------"<<endl; 
 init_test(); 
 Viterbi_O(data); 
 return 0; 
 } 
 

The End