Skip to content

WARNING

🧪 Beta公测版本提示:教程主体已完成,正在优化细节,欢迎大家提Issue反馈问题或建议。

ml11 隐马尔可夫模型 — demo.py 代码详解 ​

Download demo.py

运行方式 ​

bash
cd docs/ml/advanced/hmm/code
python demo.py

代码逐段详解 ​

复现提示:已修正观测词表索引,旧 ml11-04-pos-trellis.png 的最后一个词可能错标为 the,正确应为 mat。图片尚未重新运行生成。

第1步:HMM 类与前向算法 ​

python
class HMM:
    def __init__(self, A, B, pi):
        self.A = np.array(A)    # 转移矩阵: P(Z_{t+1}=j | Z_t=i)
        self.B = np.array(B)    # 发射矩阵: P(X_t=o | Z_t=i)
        self.pi = np.array(pi)  # 初始分布: P(Z_1=i)

HMM 的三个参数对应三个概率分布:初始状态分布 π(N 维向量)、状态转移矩阵 A(N×N)、发射概率矩阵 B(N×M)。

前向算法(带缩放) ​

python
def forward(self, observations):
    alphas = np.zeros((T, self.N))
    c = np.zeros(T)

    # 初始化: α_1(i) = π_i · B[i, x_1]
    for i in range(self.N):
        alphas[0, i] = self.pi[i] * self.B[i, observations[0]]
    c[0] = alphas[0].sum()
    if c[0] > 0:
        alphas[0] /= c[0]  # 缩放防止下溢

    # 递推: α_t(j) = [Σ_i α_{t-1}(i) · A[i, j]] · B[j, x_t]
    for t in range(1, T):
        for j in range(self.N):
            alphas[t, j] = np.dot(alphas[t-1, :], self.A[:, j]) * self.B[j, observations[t]]
        c[t] = alphas[t].sum()
        if c[t] > 0:
            alphas[t] /= c[t]

    with np.errstate(divide='ignore'):
        log_prob = np.sum(np.log(c))  # 零概率对应 -inf

为什么需要缩放(Scaling)? 当序列长度 T 较大时,αt(i) 的值会急剧变小(每个因子 ≤1,连乘 T 次)。不加缩放的 αT 可能下溢到 0。缩放的技巧是每步除以 ct=∑iαt(i),使得每步的 α~t 之和为 1。观测概率的对数可以通过缩放因子恢复:log⁡P(X|λ)=∑t=1Tlog⁡ct。

为什么这有效? 设 α~t=αt/(∏s=1tcs),则 ∏s=1Tcs=∑iαT(i)=P(X|λ),取对数即为 ∑log⁡ct。

第2步:Viterbi 算法 ​

python
def viterbi(self, observations):
    # 零概率保留为 -inf,不给不可能的路径添加伪概率
    with np.errstate(divide='ignore'):
        log_pi, log_A, log_B = np.log(self.pi), np.log(self.A), np.log(self.B)
    deltas[0, i] = log_pi[i] + log_B[i, o1]

    for t in range(1, T):
        for j in range(self.N):
            candidates = deltas[t-1, :] + log_A[:, j]
            best_i = np.argmax(candidates)
            deltas[t, j] = candidates[best_i] + log_B[j, ot]
            psi[t, j] = best_i  # 回溯指针

Viterbi 与前向算法的关键区别:max 代替 sum。这一步体现了不同的目标——前向算法问"所有路径的总概率是多少",Viterbi 问"哪一条路径最可能"。

对数空间中使用加法律(log⁡(ab)=log⁡a+log⁡b)替代乘法律,数值更稳定。特殊地,max 操作在 log 空间保持不变。

回溯:

python
best_path[T-1] = best_final_state
for t in range(T-2, -1, -1):
    best_path[t] = psi[t+1, best_path[t+1]]

从最后时刻的最优状态出发,利用 ψt(j) 存储的回溯指针,逆向重构整个最优路径。这就是经典的动态规划回溯技术。

第3步:POS 标注格子图可视化 ​

格子的 x 轴是时间(观测序列),y 轴是隐藏状态。两个热度图对比了:

  • 左图(缩放后的 Forward α):展示 P(Zt∣X1:t),即给定截至当前观测的过滤概率;它不是利用完整序列的平滑后验
  • 右图(Viterbi δ + 路径):展示了最优路径的构建过程——蓝色箭头连接最优序列

第4步:马尔可夫链转移图 ​

展示了三个状态的天气马尔可夫链(Sunny/Cloudy/Rainy),箭头粗细正比于转移概率。通过迭代 π(n+1)=π(n)A 或求解 πA=π 得到平稳分布。

第5步:转移矩阵对状态序列的影响 ​

对比两种极端的转移矩阵:

  • 平滑转移:高自转移概率(0.7),状态倾向保持稳定
  • 尖峰转移:偏好循环结构(S1→S2→S3→S1),其他转移仍有非零概率

Viterbi 路径同时受转移概率与发射概率影响;低概率转移仍可能被选中,只有概率严格为零的路径不可能被选中。若整个观测序列概率为零,演示代码明确报错,不返回虚假的“最佳路径”。

关键概念速查表 ​

概念数学形式代码位置关键说明
前向 ααt(j)=[∑αt−1aij]bj(xt)HMM.forward()动态规划 O(N^2 T)
缩放α~t=αt/ctc[t] 归一化防止概率下溢
Viterbi δδt(j)=maxi[δt−1aij]bj(xt)HMM.viterbi()max 代替 sum
回溯 ψψt(j)=arg⁡maxi[δt−1(i)aij]psi[t, j]记录最优前驱
平稳分布π=πAnp.linalg.eig(A.T)链的平衡状态
log 空间log⁡(ab)=log⁡a+log⁡bnp.log(...)数值稳定替代乘法律

源码位置 ​

clone 后打开(相对仓库根目录):

docs/ml/advanced/hmm/code/demo.py