第10章：隐马尔可夫模型（Hidden Markov Model）

一、导读

10.1 本章学习目标

第10章介绍隐马尔可夫模型（HMM）——描述时序数据的重要概率模型。HMM假设系统在一个隐藏的马尔可夫链上运行，每个状态产生一个可观测的输出。HMM在语音识别、自然语言处理、生物信息学等领域有着广泛的应用。

本章的核心学习目标包括：

理解HMM的两个基本假设：齐次马尔可夫性和观测独立性
掌握HMM的三个参数：初始概率π、状态转移概率A、观测概率B
掌握HMM的三个基本问题：概率计算（前向/后向算法）、学习（Baum-Welch）、预测（Viterbi）
理解前向算法和后向算法：如何高效计算观测序列的概率？
掌握Viterbi算法：如何找到最可能的状态序列？
实现HMM的核心算法

10.2 为什么本章如此重要

HMM是序列建模的基石。在深度学习兴起之前，HMM是语音识别的主流方法。即使在今天，HMM的基本思想——隐状态产生观测——仍然是许多序列模型的核心。

HMM还引入了动态规划在概率模型中的应用。前向算法、后向算法和Viterbi算法都利用了动态规划来避免指数级的计算。这种思想在后续的CRF、RNN等模型中继续发挥重要作用。

10.3 核心问题引导

在阅读本章时，请带着以下问题思考：

HMM的两个基本假设是什么？它们为什么重要？

HMM的三个基本问题分别是什么？各自解决什么实际问题？

直接计算观测序列概率的复杂度是多少？前向算法如何将复杂度降低？

Viterbi算法的核心思想是什么？它与动态规划有什么关系？

Baum-Welch算法（EM在HMM中的应用）如何估计HMM的参数？

HMM在实际中有哪些应用？

二、核心概念详解

10.1 HMM的定义

10.1.1 两个基本假设

齐次马尔可夫性：隐藏状态序列满足一阶马尔可夫性质，即当前状态只依赖于前一个状态：

P(q_t | q_1, ..., q_{t-1}) = P(q_t | q_{t-1})

观测独立性：当前观测只依赖于当前状态：

P(o_t | q_1, ..., q_T, o_1, ..., o_T) = P(o_t | q_t)

10.1.2 三个参数

HMM由三个参数定义：λ = (A, B, π)

状态转移概率矩阵 A：a_{ij} = P(q_{t+1} = S_j | q_t = S_i)
观测概率矩阵 B：b_j(k) = P(o_t = v_k | q_t = S_j)
初始状态概率 π：π_i = P(q_1 = S_i)

python

import numpy as np

# HMM示例：天气预测
# 隐藏状态：晴天(S1)、雨天(S2)
# 观测：散步(v1)、购物(v2)、打扫(v3)

states = ['晴天', '雨天']
observations = ['散步', '购物', '打扫']

# 初始概率
pi = np.array([0.6, 0.4])  # 第一天60%晴天，40%雨天

# 状态转移概率
A = np.array([
    [0.7, 0.3],  # 晴天→晴天0.7, 晴天→雨天0.3
    [0.4, 0.6],  # 雨天→晴天0.4, 雨天→雨天0.6
])

# 观测概率
B = np.array([
    [0.6, 0.3, 0.1],  # 晴天时：散步0.6, 购物0.3, 打扫0.1
    [0.1, 0.4, 0.5],  # 雨天时：散步0.1, 购物0.4, 打扫0.5
])

print("HMM参数:")
print(f"初始概率 π = {pi}")
print(f"状态转移矩阵 A:\n{A}")
print(f"观测概率矩阵 B:\n{B}")

10.2 问题1：概率计算

给定模型 λ 和观测序列 O = (o_1, ..., o_T)，计算 P(O|λ)。

10.2.1 暴力计算的复杂度

直接枚举所有可能的状态序列，复杂度为 O(N^T)，其中 N 是状态数，T 是序列长度。当 T 较大时不可行。

10.2.2 前向算法

前向算法利用动态规划将复杂度降低到 O(N²·T)。

定义前向变量：α_t(i) = P(o_1, ..., o_t, q_t = S_i | λ)

递推：

α_1(i) = π_i * b_i(o_1)
α_{t+1}(i) = [Σ_j α_t(j) * a_{ji}] * b_i(o_{t+1})
P(O|λ) = Σ_i α_T(i)

python

import numpy as np

def forward_algorithm(obs, pi, A, B):
    """前向算法"""
    T = len(obs)
    N = len(pi)
    
    # 初始化
    alpha = np.zeros((T, N))
    alpha[0] = pi * B[:, obs[0]]
    
    # 递推
    for t in range(1, T):
        for i in range(N):
            alpha[t, i] = np.sum(alpha[t-1] * A[:, i]) * B[i, obs[t]]
    
    # 终止
    prob = np.sum(alpha[T-1])
    return prob, alpha

# 测试
obs = [0, 1, 2]  # 散步, 购物, 打扫
prob, alpha = forward_algorithm(obs, pi, A, B)
print(f"观测序列 [散步, 购物, 打扫] 的概率: {prob:.6f}")

10.2.3 后向算法

定义后向变量：β_t(i) = P(o_{t+1}, ..., o_T | q_t = S_i, λ)

递推：

β_T(i) = 1
β_t(i) = Σ_j a_{ij} * b_j(o_{t+1}) * β_{t+1}(j)
P(O|λ) = Σ_i π_i * b_i(o_1) * β_1(i)

python

import numpy as np

def backward_algorithm(obs, pi, A, B):
    """后向算法"""
    T = len(obs)
    N = len(pi)
    
    # 初始化
    beta = np.zeros((T, N))
    beta[T-1] = 1
    
    # 递推
    for t in range(T-2, -1, -1):
        for i in range(N):
            beta[t, i] = np.sum(A[i] * B[:, obs[t+1]] * beta[t+1])
    
    # 终止
    prob = np.sum(pi * B[:, obs[0]] * beta[0])
    return prob, beta

# 验证
prob_back, beta = backward_algorithm(obs, pi, A, B)
print(f"后向算法计算的概率: {prob_back:.6f}")
print(f"前向和后向结果一致: {abs(prob - prob_back) < 1e-10}")

10.3 问题2：学习问题（Baum-Welch算法）

给定观测序列 O，估计模型参数 λ = (A, B, π)，使 P(O|λ) 最大。

Baum-Welch算法是EM算法在HMM中的具体应用。

10.3.1 E步

计算两个关键概率：

状态占用概率：γ_t(i) = P(q_t = S_i | O, λ) = α_t(i) * β_t(i) / P(O|λ)

状态转移概率：ξ_t(i,j) = P(q_t = S_i, q_{t+1} = S_j | O, λ)

10.3.2 M步

更新参数：

π_i = γ_1(i)
a_{ij} = Σ_t ξ_t(i,j) / Σ_t γ_t(i)
b_j(k) = Σ_{t:o_t=v_k} γ_t(j) / Σ_t γ_t(j)

python

import numpy as np

def baum_welch(obs, N, n_iter=50):
    """Baum-Welch算法（HMM的EM）"""
    T = len(obs)
    V = max(obs) + 1  # 观测值种类数
    
    # 随机初始化
    np.random.seed(42)
    pi = np.random.dirichlet(np.ones(N))
    A = np.random.dirichlet(np.ones(N), size=N)
    B = np.random.dirichlet(np.ones(V), size=N)
    
    log_likelihoods = []
    
    for iteration in range(n_iter):
        # E步：前向-后向
        _, alpha = forward_algorithm(obs, pi, A, B)
        _, beta = backward_algorithm(obs, pi, A, B)
        
        prob_obs = np.sum(alpha[T-1])
        log_likelihoods.append(np.log(prob_obs + 1e-300))
        
        # 计算γ和ξ
        gamma = alpha * beta / (prob_obs + 1e-300)
        
        xi = np.zeros((T-1, N, N))
        for t in range(T-1):
            for i in range(N):
                for j in range(N):
                    xi[t, i, j] = (alpha[t, i] * A[i, j] * 
                                   B[j, obs[t+1]] * beta[t+1, j])
            xi[t] /= (np.sum(xi[t]) + 1e-300)
        
        # M步：更新参数
        pi = gamma[0]
        
        for i in range(N):
            for j in range(N):
                A[i, j] = np.sum(xi[:, i, j]) / (np.sum(gamma[:-1, i]) + 1e-300)
        
        for j in range(N):
            for k in range(V):
                mask = [1 if o == k else 0 for o in obs]
                B[j, k] = np.sum(gamma[:, j] * mask) / (np.sum(gamma[:, j]) + 1e-300)
    
    return pi, A, B, log_likelihoods

# 测试
pi_est, A_est, B_est, lls = baum_welch(obs, N=2, n_iter=30)
print(f"学习到的初始概率: {pi_est}")
print(f"学习到的转移矩阵:\n{A_est}")
print(f"学习到的观测矩阵:\n{B_est}")

10.4 问题3：预测问题（Viterbi算法）

给定模型 λ 和观测序列 O，找到最可能的状态序列 Q = (q_1, ..., q_T*)。

10.4.1 Viterbi算法

Viterbi算法使用动态规划找到最优路径。

定义：δ_t(i) = max_{q_1,...,q_{t-1}} P(q_1,...,q_t=S_i, o_1,...,o_t | λ)

递推：

δ_1(i) = π_i * b_i(o_1)
δ_t(j) = max_i [δ_{t-1}(i) * a_{ij}] * b_j(o_t)

回溯：

q_T* = argmax_i δ_T(i)
q_t* = argmax_i [δ_t(i) * a_{i,q_{t+1}*}]

python

import numpy as np

def viterbi(obs, pi, A, B):
    """Viterbi算法"""
    T = len(obs)
    N = len(pi)
    
    # 初始化
    delta = np.zeros((T, N))
    psi = np.zeros((T, N), dtype=int)
    
    delta[0] = pi * B[:, obs[0]]
    
    # 递推
    for t in range(1, T):
        for j in range(N):
            probs = delta[t-1] * A[:, j]
            delta[t, j] = np.max(probs) * B[j, obs[t]]
            psi[t, j] = np.argmax(probs)
    
    # 回溯
    path = np.zeros(T, dtype=int)
    path[T-1] = np.argmax(delta[T-1])
    
    for t in range(T-2, -1, -1):
        path[t] = psi[t+1, path[t+1]]
    
    return path, np.max(delta[T-1])

# 测试
obs = [0, 1, 2]  # 散步, 购物, 打扫
path, prob = viterbi(obs, pi, A, B)

state_names = ['晴天', '雨天']
print(f"观测序列: 散步 → 购物 → 打扫")
print(f"最可能的状态序列: {' → '.join(state_names[s] for s in path)}")
print(f"最大概率: {prob:.6f}")

10.5 HMM的应用

HMM在许多领域有重要应用：

语音识别：状态对应音素，观测对应声学特征
词性标注：状态对应词性，观测对应词语
生物序列分析：状态对应基因结构，观测对应DNA序列
手势识别：状态对应手势阶段，观测对应传感器数据

python

import numpy as np

def pos_tagging_example():
    """词性标注示例"""
    # 简化的词性标注HMM
    # 状态：名词(N)、动词(V)、形容词(A)
    # 观测：具体的词
    
    states = ['N', 'V', 'A']
    vocab = {'我': 0, '爱': 1, '美丽': 2, '的': 3, '世界': 4, '吃': 5, '苹果': 6}
    
    pi = np.array([0.3, 0.2, 0.5])  # 句首更可能是名词或形容词
    
    A = np.array([
        [0.1, 0.6, 0.1],  # N → N/V/A
        [0.5, 0.1, 0.2],  # V → N/V/A
        [0.6, 0.1, 0.1],  # A → N/V/A
    ])
    
    B = np.zeros((3, 7))
    B[0, 0] = 0.5  # N: 我
    B[0, 4] = 0.3  # N: 世界
    B[0, 6] = 0.2  # N: 苹果
    B[1, 1] = 0.5  # V: 爱
    B[1, 5] = 0.5  # V: 吃
    B[2, 2] = 0.7  # A: 美丽
    B[2, 3] = 0.3  # A: 的
    
    # 观测序列："我 爱 美丽 的 世界"
    obs_seq = [0, 1, 2, 3, 4]
    
    path, prob = viterbi(obs_seq, pi, A, B)
    words = ['我', '爱', '美丽', '的', '世界']
    
    print("词性标注示例:")
    for word, state in zip(words, [states[s] for s in path]):
        print(f"  {word} → {state}")

pos_tagging_example()

三、实战案例

3.1 前向算法的效率

python

import numpy as np
import time

def efficiency_comparison():
    """对比暴力计算和前向算法的效率"""
    N = 5   # 状态数
    T = 20  # 序列长度
    
    print(f"状态数 N={N}, 序列长度 T={T}")
    print(f"暴力计算需要枚举的状态序列数: {N**T:,}")
    print(f"前向算法的计算量: O(N²·T) = {N**2 * T:,}")
    print(f"加速比: {N**T / (N**2 * T):.0f}x")
    print(f"\n当T=100时，暴力计算需要 5^100 ≈ 10^69 次运算")
    print(f"前向算法只需要 5²×100 = 2500 次运算")

efficiency_comparison()

3.2 Viterbi算法的完整实现

python

import numpy as np

def viterbi_complete():
    """完整的Viterbi算法实现"""
    # 经典的"赌场"例子
    # 隐藏状态：公平骰子(F)、有偏骰子(L)
    # 观测：骰子的点数
    
    states = ['F', 'L']
    N = 2
    
    pi = np.array([0.5, 0.5])
    
    A = np.array([
        [0.9, 0.1],  # F → F/L
        [0.3, 0.7],  # L → F/L
    ])
    
    B = np.array([
        [1/6]*6,     # F: 均匀分布
        [1/10, 1/10, 1/10, 1/10, 1/4, 1/4],  # L: 偏向5和6
    ])
    
    # 观测序列
    obs = [1, 2, 5, 6, 3, 5, 6, 1, 2, 4]
    
    path, prob = viterbi(obs, pi, A, B)
    
    print("赌场例子 - Viterbi解码:")
    print(f"观测: {obs}")
    print(f"最可能的骰子序列: {''.join(states[s] for s in path)}")
    print(f"F=公平骰子, L=有偏骰子")

viterbi_complete()

四、本章小结

第10章介绍了隐马尔可夫模型：

HMM的两个假设：齐次马尔可夫性（状态转移只依赖前一状态）和观测独立性（观测只依赖当前状态）。

三个基本问题：概率计算（前向/后向算法）、学习（Baum-Welch/EM）、预测（Viterbi算法）。

前向算法：利用动态规划高效计算观测序列概率，复杂度 O(N²T)。

Viterbi算法：利用动态规划找到最可能的状态序列，复杂度 O(N²T)。

Baum-Welch算法：EM在HMM中的应用，交替E步（前向-后向计算）和M步（参数更新）。

HMM的核心启示是：动态规划是序列概率模型的关键计算工具。

五、思考与练习

思考题

HMM的两个假设在实际中是否成立？放松这些假设会怎样？

前向算法和后向算法各自计算了什么？它们如何结合使用？

Viterbi算法和前向算法有什么区别？为什么一个用max，一个用sum？

Baum-Welch算法为什么不能保证全局最优？如何缓解？

HMM在什么场景下比CRF更有优势？什么场景下CRF更好？

编程练习

实现前向算法和后向算法，验证两者计算的概率一致。

实现Viterbi算法，在天气预测例子上测试。

实现Baum-Welch算法，从观测数据中学习HMM参数。