经典机器学习算法-第二十一章HMM算法

EDUCATION AND TRAINING

一算法基本原理

1.1 马尔可夫模型

    在某段时间内，交通信号灯的颜色变化序列是：红色 - 黄色 - 绿色 - 红色。

    在某个星期天气的变化状态序列：晴朗 - 多云 - 雨天。

像交通信号灯一样，某一个状态只由前一个状态决定，这就是一个一阶马尔可夫模型。而像天气这样，天气状态间的转移仅依赖于前 n 天天气的状态，即状态间的转移仅依赖于前 n 个状态的过程。这个过程就称为n 阶马尔科夫模型。

    不通俗的讲，马尔可夫模型（Markovmodel）描述了一类重要的随机过程，随机过程又称随机函数，是随时间而随机变化的过程。

    存在一类重要的随机过程：如果一个系统有 N 个状态

随着时间的推移，该系统从某一状态转移到另一状态。如果用表示系统在时间 t 的状态变量，那么 t 时刻的状态取值为

(1<=j<=N)的概率取决于前 t-1 个时刻(1, 2, …, t-1)的状态，该概率为：

    假设一：如果在特定情况下，系统在时间 t 的状态只与其在时间 t-1 的状态相关，则该系统构成一个离散的一阶马尔可夫链：

    假设二：如果只考虑独立于时间 t 的随机过程，状态与时间无关，那么

    即：t 时刻状态的概率取决于前 t-1 个时刻(1, 2, …, t-1)的状态,且状态的转换与时间无关，则该随机过程就是马尔可夫模型。

1.2 隐马尔可夫模型

    在马尔可夫模型中，每个状态代表了一个可观察的事件，所以，马尔可夫模型有时又称作可视马尔可夫模型（visibleMarkovmodel，VMM），这在某种程度上限制了模型的适应性。

    对于盲人来说也许不能够直接获取到天气的观察情况，但是他可以通过触摸树叶通过树叶的干燥程度判断天气的状态。于是天气就是一个隐藏的状态，树叶的干燥程度是一个可观察的状态，于是我们就有了两组状态，一个是不可观察、隐藏的状态（天气），一个是可观察的状态（树叶），我们希望设计一种算法，在不能够直接观察天气的情况下，通过树叶和马尔可夫假设来预测天气。

    以此为例，一个一阶的马尔可夫过程描述：

    在隐马尔可夫模型（HMM）中，我们不知道模型具体的状态序列，只知道状态转移的概率，即模型的状态转换过程是不可观察的。

    因此，该模型是一个双重随机过程，包括模型的状态转换和特定状态下可观察事件的随机。

1.3 HMM 的组成

    例如，N 个袋子，每个袋子中有 M 种不同颜色的球。选择一个袋子，取出一个球，得到球的颜色。

状态数为 N(袋子的数量)

每个状态可能的符号数 M(不同颜色球的数目)

状态转移概率矩阵 (从一只袋子(状态 Si) 转向另一只袋子(状态 Sj ) 取球的概率)

    从状态 Sj 观察到某一特定符号 vk 的概率分布矩阵为(从第 j 个袋子中取出第 k 种颜色的球的概率)

初始状态的概率分布为：

一般将一个隐马尔可夫模型记为：

需要确定以下三方面内容（三要素）：

初始状态概率 π: 模型在初始时刻各状态出现的概率，通常记为

表示模型的初始状态Si概率.

    状态转移概率 A: 模型在各个状态间转换的概率，通常记为矩阵,表示在任意时刻 t，若状态为 Si，则在下一时刻状态为 Sj 的概率.

    输出观测概率 B: 模型根据当前状态获得各个观测值的概率通常记为矩阵。其中表示在任意时刻 t，若状态为Si则观测值Oi被获取的概率.

    相对于马尔可夫模型，隐马尔可夫只是多了一个各状态的观测概率

    给定隐马尔可夫模型 λ=[A，B，π]，它按如下过程产生观测序列{X1,X2，...,Xn}:

(1) 设置 t=1，并根据初始状态概率 π 选择初始状态

(2) 根据状态值和输出观测概率 B 选择观测变量取值

(3) 根据状态值和状态转移矩阵 A 转移模型状态，即确定

1.4 三个问题

    一旦一个系统可以作为 HMM 被描述，就可以用来解决三个基本问题。

1.4.1 评估（Evaluation）

给定 HMM，即

，求某个观察序列的概率。

例如：给定一个天气的隐马尔可夫模型，包括第一天的天气概率分布，天气转移概率矩阵，特定天气下树叶的湿度概率分布。求第一天湿度为 1，第二天湿度为 2，第三天湿度为 3 的概率。

1.4.2 解码（ Decoding）

给定 HMM，即

，以及某个观察序列，求得天气的序列。

    例如：给定一个天气的隐马尔可夫模型，包括第一天的天气概率分布，天气转移概率矩阵，特定天气下树叶的湿度概率分布。并且已知第一天湿度为 1，第二天湿度为 2，第三天湿度为 3。求得这三天的天气情况。

即：发现“最优”状态序列能够“最好地解释”观察序列

1.4.3 学习（Learning）

给定一个观察序列，得到一个隐马尔可夫模型。

例如：已知第一天湿度为 1，第二天湿度为 2，第三天湿度为 求得一个天气的隐马尔可夫模型，包括第一天的天气，天气转移概率矩阵，特定天气下树叶的湿度概率分布。

二、Numpy解法

import numpy as np
### 定义HMM模型class HMM: def __init__(self, N, M, pi=None, A=None, B=None): # 可能的状态数 self.N = N # 可能的观测数 self.M = M # 初始状态概率向量 self.pi = pi # 状态转移概率矩阵 self.A = A # 观测概率矩阵 self.B = B
# 根据给定的概率分布随机返回数据 def rdistribution(self, dist): r = np.random.rand() for ix, p in enumerate(dist): if r < p: return ix r -= p
# 生成HMM观测序列 def generate(self, T): # 根据初始概率分布生成第一个状态 i = self.rdistribution(self.pi) # 生成第一个观测数据 o = self.rdistribution(self.B[i]) observed_data = [o] # 遍历生成剩下的状态和观测数据 for _ in range(T-1): i = self.rdistribution(self.A[i]) o = self.rdistribution(self.B[i]) observed_data.append(o) return observed_data

# 初始状态概率分布pi = np.array([0.25, 0.25, 0.25, 0.25])# 状态转移概率矩阵A = np.array([    [0,  1,  0, 0],    [0.4, 0, 0.6, 0],    [0, 0.4, 0, 0.6],[0, 0, 0.5, 0.5]])# 观测概率矩阵B = np.array([    [0.5, 0.5],    [0.6, 0.4],    [0.2, 0.8],    [0.3, 0.7]])# 可能的状态数和观测数N = 4M = 2# 创建HMM实例hmm = HMM(N, M, pi, A, B)# 生成观测序列print(hmm.generate(5))

### 前向算法计算条件概率def prob_calc(O): ''' 输入： O：观测序列 输出： alpha.sum()：条件概率 ''' # 初值 alpha = pi * B[:, O[0]] # 递推 for o in O[1:]: alpha_next = np.empty(4) for j in range(4): alpha_next[j] = np.sum(A[:,j] * alpha * B[j,o]) alpha = alpha_next return alpha.sum()
# 给定观测O = [1,0,1,0,0]print(prob_calc(O))

### 序列标注问题和维特比算法def viterbi_decode(O):    '''    输入：    O：观测序列    输出：    path：最优隐状态路径    '''        # 序列长度和初始观测    T, o = len(O), O[0]    # 初始化delta变量    delta = pi * B[:, o]    # 初始化varphi变量    varphi = np.zeros((T, 4), 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[:, O[i]]    # 终止    path[-1] = np.argmax(delta)    # 回溯最优路径    for i in range(T-1, 0, -1):        path[i-1] = varphi[i, path[i]]    return path
# 给定观测序列O = [1,0,1,1,0]# 输出最可能的隐状态序列print(viterbi_decode(O))