Skip to content

下面继续 Lecture 4 和 Lecture 5 的完整逻辑链。这里开始,课程真正进入 HMM 的“三大核心问题”:

问题本质对应算法
Inference这个句子出现的概率是多少?Forward / Backward
Prediction / Decoding最可能的隐藏状态序列是什么?Viterbi
Learning如何从数据学习 HMM 参数?MLE / EM / Baum-Welch

Lecture 3 只是“建模”: 你已经有了 HMM。

Lecture 4-5 才是真正“让 HMM 工作起来”。

整个逻辑主线是:

text
HMM 建模
  ↓
如何计算句子概率?
  ↓
暴力枚举不可行
  ↓
Dynamic Programming
  ↓
Forward / Backward
  ↓
如何找最优隐藏路径?
  ↓
Structured Prediction
  ↓
Viterbi Decoding
  ↓
如果 hidden states 不知道怎么办?
  ↓
EM / Baum-Welch

下面按“问题驱动”的方式讲。


Part I:Inference —— 如何计算一句话出现的概率? ​

Lecture 4 的核心任务是:

给定:

以及固定 HMM 参数:

求:

即:

“这个 HMM 生成这个句子的概率是多少?”


1. 为什么 inference 很难? ​

根据全概率公式:

这里:

符号含义
observed words
hidden tag sequence
某条隐藏路径与句子的联合概率

问题是:

hidden states 不可见。

所以必须:

把所有可能 tag sequences 全部求和。


1.1 暴力枚举的复杂度 ​

若:

  • 句长为
  • tag 数量为

则可能的 hidden sequence 数量:

因为每个位置都可能是 个 tag 之一。

因此暴力求和复杂度:

指数爆炸。

这就是 inference 的核心困难。


2. 方法论演进:为什么 Dynamic Programming 能救场? ​

这是 Lecture 4 最重要的思想。

Forward algorithm 本质不是“HMM 技巧”。

它本质上是:

Dynamic Programming on chain structures。


2.1 为什么可以 DP? ​

因为 HMM 满足:

Markov assumption:

以及 emission independence:

因此:

过去的信息可以被“压缩”到当前状态。

这意味着:

未来不需要知道完整历史。

只需要知道:

当前在哪个 hidden state。


3. Forward Algorithm:核心思想 ​

3.1 定义 Forward Probability ​

定义:

表示:

“看到前 个词,并且当前 hidden state 是 的联合概率。”

这是整个算法最核心的定义。


3.2 Forward 的物理意义 ​

Forward algorithm 是:

“历史累计器(history tracer)”。

课件明确写了:

recall the past

即:

汇总了:

所有可能路径到达 的概率。

注意:

不是最优路径。

是:

所有路径求和。

这是 inference。

不是 decoding。

这一点非常关键。


4. Base Case ​

当:

只有一个状态。

因此:

其中:

符号含义
starting probability
state 发射词 的概率

含义:

“从 state 开始,并生成第一个词。”


5. Recursive Case:真正的 DP ​

5.1 Forward recursion ​

核心递推:

这是 Lecture 4 的核心公式。


6. Forward 公式的深层直觉 ​

这个式子必须真正理解。


6.1 从哪里来? ​

当前在:

那么前一步一定来自某个:

所以:

必须枚举所有 predecessor states。


6.2 每项的含义 ​

第一项 ​

表示:

“所有到达 state 的历史概率总和”。

这是 cached solution。


第二项 ​

表示:

从 转移到 。


第三项 ​

表示:

当前 state 生成当前 observation。


6.3 为什么是求和? ​

因为 inference 关心:

所有可能 hidden paths。

不是最优路径。

所以:

不是:

这正是它和 Viterbi 的本质区别。


7. Forward 的最终结果 ​

最终:

即:

最后时刻所有 hidden states 的概率和。

因为:

句子可能以任意 hidden state 结束。


8. 时间复杂度为什么降了? ​

暴力:

DP 后:

每一步:

  • 当前 state:
  • 前驱 state:

所以:

总共 步:

这就是:

Dynamic Programming 的巨大威力。


9. Backward Algorithm ​

Forward 是:

从过去推未来。

Backward 是:

从未来推过去。


9.1 定义 ​

定义:

表示:

“已知当前位置 state 是 ,未来剩余 observations 出现的概率。”

课件称之为:

fortune teller。

predict the future。


10. Backward recursion ​

核心公式:


10.1 为什么这个公式成立? ​

当前位置:

下一步可能到:

所以:

必须枚举所有未来状态。

每项:

项含义
转移到下一状态
下一状态生成下一词
后续未来概率

11. Backward initialization ​

终止条件:

因为:

句尾后没有 future observations。

空序列概率定义为 1。


12. Forward vs Backward 的本质区别 ​

Algorithm含义聚合什么
Forward从起点累计到当前所有过去路径
Backward从当前累计到终点所有未来路径
Viterbi最优路径最大概率路径

Part II:Prediction —— 如何找最可能的 Hidden Sequence? ​

Lecture 5 进入第二个核心任务:

Decoding。


13. 为什么 inference 不够? ​

Forward 求的是:

即:

“这个句子整体概率多大”。

但 POS tagging 真正要的是:

即:

“最可能的 hidden tag sequence”。


14. Structured Prediction ​

课件强调:

POS tagging 不是 independent classification。

不能:

每个词单独预测。

因为:

局部最优不等于全局最优。


14.1 Running example ​

句子:

若逐词预测:

可能得到:

但:

“like” 的 tag 会影响:

前后词性的合理性。

这就是:

structured prediction。


15. Viterbi:Forward 的 max-version ​

这是 Lecture 5 最核心的一句话:

Forward:

Viterbi:


16. 定义 Viterbi Variable ​

定义:

含义:

“到达当前 state 的最佳路径概率”。

注意:

这里只保留:

最大路径。

而不是所有路径。


17. Viterbi recursion ​

核心递推:

这和 Forward 几乎一模一样:

AlgorithmOperator
Forward
Viterbi

这是整个课程最关键的统一视角。


18. 为什么只保留 max 是合法的? ​

因为:

如果一条路径不是当前 state 的最佳前缀。

它以后永远不可能变成全局最优。

这叫:

optimal substructure。

也是 dynamic programming 的核心。


19. Backpointer:为什么必须记录路径? ​

只记录:

只能知道:

概率值。

不知道:

路径怎么走。

所以需要:

表示:

当前最优 state 来自哪个 predecessor。


20. Backtracking ​

最后:

然后:

一路回溯。

最终恢复完整最优路径。


21. Viterbi vs Forward 的本质区别 ​

这是最容易混淆的地方。

算法求什么aggregation
Forward所有路径总概率sum
Viterbi单条最佳路径max

Forward:

“所有解释加起来有多可能”。

Viterbi:

“最好的解释是哪条”。


Part III:Learning —— 如何学习 HMM 参数? ​

现在进入第三个核心问题。


22. Supervised Learning:最简单情况 ​

如果训练数据有:

POS labels。

则:

直接 counting。


22.1 Transition MLE ​

其中:

符号含义
从 tag 到 tag 的转移次数
tag 出现总次数

22.2 Emission MLE ​

表示:

tag 发射 word 的频率。


23. 真正困难:Unsupervised Learning ​

现实中:

hidden states 不知道。

即:

没有 POS labels。

怎么办?


24. EM Algorithm:核心思想 ​

EM 是:

“猜标签 → 更新参数 → 再猜标签”。


25. E-step ​

利用当前参数:

估计 hidden variables 的概率。

即:

soft labels。


25.1 Soft transition counts ​

定义:

表示:

位置 上:

从 的概率。

不是硬标签。

而是概率。


25.2 Soft state counts ​

定义:

表示:

当前位置属于 state 的概率。


26. Forward-Backward 如何用于 EM? ​

关键公式:

极其重要。


26.1 直觉 ​

Forward:

解释过去。

Backward:

解释未来。

两者相乘:

解释整个句子。

因此:

当前位置属于某个 state 的 posterior:


27. M-step ​

有了 soft counts 后:

重新估计参数。


27.1 更新 transition ​

即:

“期望转移次数 / 期望总离开次数”。


27.2 更新 emission ​

即:

“期望发射次数 / 期望状态出现次数”。


28. Baum-Welch Algorithm ​

HMM 的 EM 版本:

叫:

Baum-Welch。

流程:

text
初始化参数
    ↓
Forward-Backward
    ↓
计算 γ 和 ξ
    ↓
更新 A,B,π
    ↓
重复直到收敛

29. EM 的局限性 ​

课件特别强调:

EM 只保证:

likelihood 单调增加。

不保证:

global optimum。

因此:

初始化很重要。

坏初始化可能陷入坏 local optimum。


30. 三节课的统一总结 ​

Lecture 3-5 其实构成了一个完整闭环:

Lecture核心问题核心算法
Lecture 3如何建模序列?HMM
Lecture 4如何计算序列概率?Forward / Backward
Lecture 5如何预测最优序列?Viterbi
Lecture 5如何学习参数?EM / Baum-Welch

它们共同构成:

经典统计 NLP 的完整框架。


31. 最重要的统一视角(非常关键) ​

这三种算法本质是:

同一个 DP 模板。


Forward ​

聚合:

所有路径。


Viterbi ​

聚合:

最佳路径。


Backward ​

聚合:

所有未来路径。


因此:

HMM 的本质其实是:

在 chain graphical model 上做 message passing。

这也是后面 Transformer / CRF / Beam Search / Seq2Seq 的理论源头。

Static academic notes built with VitePress and KaTeX.