数学推导+纯Python实现机器学习算法24:HMM隐马尔可夫模型-技术圈

Python机器学习算法实现

Author：louwill

Machine Learning Lab

HMM（Hidden Markov Model）也就是隐马尔可夫模型，是一种由隐藏的马尔可夫链随机生成观测序列的过程，是另一种经典的概率图模型。本文在阐述HMM的基本定义和相关概念的基础上，引申出HMM的三个重要问题：估计算法、学习算法和预测算法问题，并给出相应的代码实现方式。

HMM的定义与相关概念

HMM是关于时序的概率模型，描述一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生随机序列的过程。其中隐藏的马尔可夫链随机生成的状态的序列称之为状态序列，每个状态产生的状态构成的序列，称之为观测序列。

HMM由初始状态概率向量，状态转移概率矩阵和观测概率矩阵决定，其中和决定状态序列，决定观测序列。所以，HMM可以用一个三元符号来表示：

设为所有可能的状态的集合，是所有可能的观测的集合：
，
其中是可能的状态数，是可能的观测数。

是长度为的状态序列，是对应的观测序列。
，

作为状态转移矩阵，可表达为：

其中：，是在时刻处于状态的条件下在时刻转移到状态的概率。

作为观测概率矩阵，可表达为：

其中：，是在时刻处于状态条件下生成的观测的概率。

文字和公式表述可能过于抽象，我们以一个具体的例子来看一下HMM。假设有4个盒子，每个盒子里面都要红白两种颜色的球，各个盒子里面的红白球颜色数量分布如下表所示。

摸球规则如下：首先从4个盒子里等概率的选择一个1个盒子，从这个盒子里随机摸一个球，记录颜色后放回。然后从当前盒子随机地转移到下一个盒子，转移规则如下：如果当前盒子为1，那么下一个盒子一定是2，如果当前盒子是2或者3，则分别以概率0.4和0.6转移到左边或者右边的盒子，如果当前的盒子是4，那么各以0.5的概率停留在4或者转移到3，确定了转移的盒子后，就从该盒子中随机摸取一个球记录其颜色并放回。将上述摸球试验独立重复进行5次，得到一个球的观测序列为：
红，红，白，白，红

我们按照HMM的三要素对该例子进行分析。在上述摸球过程中，我们只能观测到摸到的球的颜色，即可以观测到球的颜色序列；而观察不到球是从哪个盒子摸到的，即观测不到盒子的序列。所以，该例中状态序列即为盒子的序列，观测序列即为摸取到的球的颜色序列。具体如下所示。
状态序列：盒子，盒子，盒子，盒子，

观测序列：红，白，，状态序列和观测序列长度，初始概率分布，状态转移概率分布矩阵为：

观测概率矩阵为：

综上，我们可以归纳一个长度为的观测序列的生成过程如下：

按照初始状态分布产生状态
令
按照状态的观测概率分布生成
按照状态的状态转移概率分布产生状态，
令；如果，跳转到第三步否则过程终止。

根据该例我们可编写一个HMM观测序列生成过程的代码如下。

HMM的三个基本问题

跟CRF一样，HMM也有三个基本问题，分别是概率估计、学习问题和预测问题。

HMM的估计算法

HMM的概率估计问题，即在给定模型和观测序列，计算在模型下观测序列出现的概率。

跟CRF一样，HMM的概率估计方法依然是前向-后向算法。先来看前向算法。HMM定义前向概率如下：给定HMM模型，定义到时刻部分观测序列且状态为的概率为前向概率，记为：

可以看到前向概率是一个联合概率。通过该定义可以递推的计算前向概率及观测序列概率。在输入为HMM模型，观测序列和输出为观测序列概率的情形下，观测序列概率的前向算法表述如下：

初值：，
递推：对，有，
终止：

下面给出前向概率算法的具体推导过程。根据前向概率的定义，可以推导初值为：

其中表示有状态生成的观测概率，假设在时刻观测数据，则有：

且由前向概率定义可得：

根据上式，遍历的取值求和，可得的边际概率：

令，有:

上式推导中根据观测独立假设第一项可化简为：

第二项可根据齐次马尔可夫假设化简为：

假设已知，在前向概率的定义的基础上，有：

将前述化简结果带上上式，可得：

后向概率算法同理可推导。基于前向-后向概率我们可计算HMM的一些延申概率和期望，这里略过。

HMM的学习算法

HMM的第二个关键问题就是学习问题。即已知观测序列，估计HMM模型的参数，使得在该模型下观测序列概率$P(O|\lambda)最大。

当训练数据集同时包含观测序列和对应的状态序列时，我们可以直接使用极大似然估计来估计HMM的模型参数。但大多数情况下，训练数据仅有观测序列而未给出对应的状态序列，这时我们将观测序列看作观测数据，状态序列看作不可观测的隐数据，此时的HMM模型实际上一个含有隐变量的概率模型：

由第22讲我们知道含有隐变量的概率模型可以通过EM算法来进行迭代求解。应用EM算法求解HMM模型参数也叫Baum-Welch算法。基于Baum-Welch算法求解HMM模型参数过程如下：

确定完全数据的对数似然函数
将观测数据写为，隐数据写为，完全数据可以写为。完全数据的对数似然函数为。
EM算法的E步：求函数

其中为HMM参数的当前估计值，是要极大化的HMM参数。
EM算法的M步：极大化函数求模型参数。

HMM的预测算法

HMM的预测问题也就是解码问题。即再已知模型和观测序列的情况下，求对给定观测序列条件概率P(I|O)最大的状态序列。即给定观测序列，求最有可能的对应的状态序列。

跟CRF预测算法一样，HMM的预测算法同样是一个求解最优路径问题，所以解码算法仍然是上一篇文章说到的维特比算法。关于维特比算法的通俗解释，参考上一篇CRF的讲解。基于维特比算法的HMM最优路径求解过程如下。

初始化：，，
递推。对:

，
终止：
最优路径回溯。对:

HMM的代码实现

完整的HMM需要实现的内容比较多。这里我们仅给出基于盒子摸球模型的HMM观测序列生成过程和维特比解码过程的参考实现方式。完整的算法笔者后续会在GitHub上给出。

基于4个盒子摸球的HMM模型的观测序列生成过程如下：

import numpy as np
# 根据给定的概率分布随机返回数据def get_data_with_distribution(dist):     r = np.random.rand()    for i, p in enumerate(dist):        if r < p:             return i        r -= p
def generate(T):    '''    根据给定的参数生成观测序列    T: 指定要生成数据的数量    '''    # 根据初始概率分布生成第一个状态    z = get_data_with_distribution(pi)     # 生成第一个观测数据    x = get_data_with_distribution(B[z])      result = [x]    # 遍历生成余下的状态和观测数据    for _ in range(T-1):                z = get_data_with_distribution(A[z])        x = get_data_with_distribution(B[z])        result.append(x)    return result
### 盒子和球相关的模型参数# 初始状态概率向量pi = np.array([0.25, 0.25, 0.25, 0.25])
# 状态转移概率矩阵A = np.array([    [0,  1,  0, 0],    [.4, 0, .6, 0],    [0, .4, 0, .6],    [0, 0, .5, .5]])
# 观测概率矩阵B = np.array([    [0.5, 0.5],    [0.3, 0.7],    [0.6, 0.4],    [0.8, 0.2]])
# 生成10个数据generate(10)

[0, 0, 0, 0, 0, 0, 1, 1, 0, 0]

在已知模型参数和观测序列的情况下，基于维特比算法的解码反推最有可能的隐状态序列：

def viterbi_decode(X):    T, x = len(X), X[0]    # 初始化    delta = pi * B[:,x]    varphi = np.zeros((T, N), dtype=int)    path = [0] * T    # 递推    for i in range(1, T):        delta = delta.reshape(-1,1)             tmp = delta * A        varphi[i,:] = np.argmax(tmp, axis=0)        delta = np.max(tmp, axis=0) * B[:,X[i]]    # 终止    path[-1] = np.argmax(delta)    # 最优路径回溯    for i in range(T-1,0,-1):        path[i-1] = varphi[i,path[i]]    return path
X = [1,0,1,0,0]N = 4print(viterbi_decode(X))