COMP5318 Week 11 马尔可夫模型与隐马尔可夫模型讲课总结

Posted on In , Word count in article: 1.2k Reading time ≈ 4 mins.
COMP5318 Week 11 讲课总结，整理马尔可夫链的定义与马尔可夫假设、转移矩阵与初始概率、用链式法则算状态序列概率； 隐马尔可夫模型的五个组成（隐状态、观测、转移矩阵 A、发射矩阵 E、初始分布 A0）与三大问题：评估（枚举法的 2TN^T 复杂度与 前向算法 N^2T）、解码（Viterbi 分数与回溯指针）、学习（EM / Baum-Welch）；天气-衣服例子的前向与 Viterbi 完整手算、 Tutorial 11 雨伞题、Practice Exam 的 HMM 大题，以及前向与 Viterbi 的对比和 HMM 的应用。

COMP5318 W11 考点速成：马尔可夫链与 HMM

用时约 15 分钟。必考：HMM 前向算法大题（PE1 Q34，10 分）、Viterbi 一步、三大问题对应三个算法、马尔可夫链路径概率。对应 PE1 Q26、Q27、Q34，PE2 Q26、Q27。

一、知识点

1. 马尔可夫链

  • 马尔可夫假设： ，只看前一个状态。
  • 转移矩阵 行 = 当前（from），列 = 下一（to），每行和为 1；可由领域知识或历史数据统计得到。
  • 一条序列的概率 ；多条路径到同一终点要相加。

2. HMM 组成

隐状态集合、观测序列 、转移矩阵 、初始分布 （）、发射矩阵 （ ）。模型 。状态看不到，只能通过观测推断。

3. 三大问题（必背）

flowchart LR
  Q{"题目问什么？"} -->|"观测序列的概率"| F["Forward：求和 Σ"]
  Q -->|"最可能的隐状态序列"| V["Viterbi：取最大 max + 回溯"]
  Q -->|"参数未知，要估计"| E["EM / Baum-Welch"]
问题 求什么 算法
Evaluation 评估 固定模型下观测序列的概率 Forward（求和）
Decoding 解码 最可能的整条隐状态路径 Viterbi（取最大 + 回溯）
Learning 学习 从观测序列估计 、、 EM（Baum-Welch）

4. Forward 算法

flowchart LR
  A1["t=1 状态 A<br/>A₀(A)·e_A(x₁)"] -->|"a_AA"| A2["t=2 状态 A<br/>e_A(x₂)·Σ"]
  B1["t=1 状态 B<br/>A₀(B)·e_B(x₁)"] -->|"a_BA"| A2
  A1 -->|"a_AB"| B2["t=2 状态 B<br/>e_B(x₂)·Σ"]
  B1 -->|"a_BB"| B2
  A2 --> P["P(X) = 最后一列求和"]
  B2 --> P

  • 是「前 个观测 且 时刻在状态 」的联合概率，不是归一化后验。
  • 复杂度 ；枚举所有路径是 。

5. Viterbi 算法

终止：最后一步取 ，再沿指针回溯。和 Forward 唯一的区别： 换成 。

易错： - 迭代用转移矩阵的列（所有到达 的边 ），别读成 。 - 发射概率乘在括号外，只乘一次。 - 解码看整条路径：第 1 步分数最高的状态不一定在最佳路径上。 - 中间结果保留足够精度，最后再四舍五入。

二、考点

  1. ★★★ Forward 两步手算（初始化 → 递推 → 求和）。
  2. ★★★ Viterbi 一步：候选前驱分数取 max，再乘发射概率。
  3. ★★★ 按问题选算法：问概率 → Forward；问最可能序列 → Viterbi；估参数 → EM。
  4. ★★ 马尔可夫链 步后在某状态的概率：枚举路径相加。

三、题目

Q1（PE1 Q34，10 分大题） 状态 A、B，观测 x、y，观测序列 (x, y)。 ， ； ， ， ， ；A→A 0.8，A→B 0.2，B→A 0.3，B→B 0.7。(a) 求 、；(b) 用 Forward 求 、、（四位小数）。

  1. 0.42， 0.06。
  2. 0.1416； 0.1008； 0.2424。

Q2（PE2 Q27） ， ； ， ；下一个观测在 B 的发射概率 0.5。求 。

候选 ， ，取 max： 0.070。（若是 Forward 则 。）

Q3（PE1 Q26） 固定 HMM 和观测序列，Viterbi 解决哪个任务？

找最可能的完整隐状态路径（解码）。

Q4（PE2 Q26） HMM 的转移和发射参数未知，要从观测序列估计，这是哪个任务？

模型学习（EM / Baum-Welch）。

Q5（PE1 Q27） 两状态马尔可夫链从 A 出发；A→A 0.6，A→B 0.4，B→A 0.3，B→B 0.7。恰好两步后在 B 的概率？

A→A→B ，A→B→B ，合计 0.52。

Q6（自拟） 用 Q1 的模型跑 Viterbi，最可能路径是什么？

（指针 A）； （指针 A）→ 终点 A，回溯 A → A, A。

Q7（T11 雨伞题） 隐状态 S、R、F， 。转移：S→(0.8, 0.05, 0.15)，R→(0.2, 0.6, 0.2)，F→(0.2, 0.3, 0.5)。发射（NA, U）：S (0.9, 0.1)，R (0.2, 0.8)，F (0.7, 0.3)。观测 NA、U，最可能的天气序列？

。 ； （指针 F）； 。 终点 R，回溯 F → Foggy, Rainy。第 1 天分数最高的 S 不在最佳路径上，因为 S→R 只有 0.05。

Q8（自拟） 马尔可夫链初始 ，sunny→sunny 0.8，sunny→cloudy 0.1，cloudy→rainy 0.2。求 。

0.0016。