章节总览
强化学习:从基础到策略优化 / 12 · 正文
原目录

围绕马尔可夫性质串起马尔可夫链、HMM、MDP、POMDP、MCMC 及它们的关系。

Markov 家族算法系统教程:从马尔可夫性质到 MDP、HMM 与 MCMC

本文系统整理马尔可夫性质、马尔可夫链、隐马尔可夫模型(HMM)、马尔可夫决策过程(MDP)、部分可观测 MDP(POMDP)、马尔可夫链蒙特卡洛(MCMC)的核心概念、公式推导与相互关系。每个数学符号首次出现时均标注读音和定义。


目录


一、马尔可夫性质与马尔可夫链

"Markov"(马尔可夫,读音 /ˈmɑːrkɒf/,得名于俄罗斯数学家安德烈·马尔可夫,Andrey Andreyevich Markov,1856—1922)这个名字在机器学习、强化学习、自然语言处理、概率推断中反复出现。所有以"Markov"命名的算法,都共享一个最核心的假设——马尔可夫性质(Markov Property)。

1.1 马尔可夫性质

马尔可夫性质(Markov Property,读音 /ˈmɑːrkɒv ˈprɒpəti/)的定义是:给定当前状态,未来与过去条件独立。用数学语言表达:

P(st+1∣st,st−1,…,s0)=P(st+1∣st)P(s_{t+1} \mid s_t, s_{t-1}, \dots, s_0) = P(s_{t+1} \mid s_t)

式中:

  • PP(读音 /piː/,probability 的缩写,表示概率)表示概率。
  • sts_t(读音 /ɛs tiː/,表示第 tt 个时间步的状态,ss 是 state 的缩写)表示第 tt 步的状态。
  • st+1s_{t+1} 表示第 t+1t+1 步的状态。
  • s0s_0(读音 /ɛs ˈzɪəroʊ/)表示初始状态。
  • 竖线 ∣\mid 表示"给定"或"条件于"(conditional on)。
  • 省略号表示更早的历史状态。

该式的含义是:在已知完整历史(s0s_0 到 sts_t)的条件下,下一状态 st+1s_{t+1} 的概率分布,等于只知道当前状态 sts_t 时的概率分布。换句话说,未来只依赖于现在,不依赖于过去。当前状态 sts_t 已经包含了预测未来所需的全部信息,更早的历史是冗余的。

直觉理解: 想象一个棋盘游戏,棋子下一步能走到哪里,只取决于它现在在哪个格子,不取决于它之前是怎么走到这个格子的。这就是马尔可夫性质——"现在"已经是"过去"的充分统计量。

需要注意的是,马尔可夫性质是一个建模假设,不是客观真理。现实中很多过程并不严格满足马尔可夫性质(比如股票价格不仅依赖今天的价格,还依赖历史趋势),但我们常常通过"扩充状态定义"来让它近似满足。例如在强化学习中,如果原始观察不满足马尔可夫性,可以把最近几帧的观察拼接起来作为状态,这就是"帧堆叠"(frame stacking)技术。

1.2 离散时间马尔可夫链

离散时间马尔可夫链(Discrete-Time Markov Chain,简称 DTMC,读音 /dɪˈskriːt taɪm ˈmɑːrkɒv tʃeɪn/)是满足马尔可夫性质的、状态在离散时间步上演化的随机过程。它是整个 Markov 家族中最简单、最基础的模型。

定义

一个离散时间马尔可夫链由以下要素定义:

  • 状态空间 SS(读音 /ɛs/,大写,表示所有可能状态的集合):系统可以处于的所有状态的集合。可以是有限的(如天气状态 {晴, 阴, 雨}),也可以是无限的(如整数集)。

  • 初始分布 π0\pi_0(读音 /paɪ ˈzɪəroʊ/,希腊字母 pi,表示初始时刻各状态的概率分布):t=0t=0 时系统处于各状态的概率,定义为:

    π0(s)=P(s0=s)\pi_0(s) = P(s_0 = s)

    其中 ss 表示某个具体状态,s0s_0 表示初始时刻的状态随机变量。

  • 状态转移矩阵 PP(读音 /piː/,大写,表示状态转移概率矩阵):一个 ∣S∣×∣S∣|S| \times |S| 的方阵(行数和列数都等于状态数),用来完整描述马尔可夫链的转移规则。矩阵中每个元素 PijP_{ij}(读音 /piː aɪ dʒeɪ/)表示"从状态 ii 出发,下一步转移到状态 jj"的概率。

状态转移矩阵 PP 的精确定义为:

Pij=P(st+1=j∣st=i),∀i,j∈SP_{ij} = P(s_{t+1} = j \mid s_t = i), \quad \forall i, j \in S

式中:

  • PijP_{ij} 是矩阵第 ii 行第 jj 列的元素。行索引 ii 是"当前状态"(从哪来),列索引 jj 是"下一状态"(到哪去)。这个方向很重要,记反了会导致整个计算错误。
  • ∀\forall(读音 /ˌfɔːr ˈɔːl/,全称 for all,表示"对于所有的")是全称量词。
  • i,j∈Si, j \in S 表示 ii 和 jj 都是状态空间 SS 中的状态。

用一个具体例子理解矩阵结构:

假设状态空间 S={晴,阴,雨}S = \{晴, 阴, 雨\}(3 个状态),那么状态转移矩阵是一个 3×33 \times 3 的方阵:

P=[P晴,晴P晴,阴P晴,雨P阴,晴P阴,阴P阴,雨P雨,晴P雨,阴P雨,雨]P = \begin{bmatrix} P_{晴,晴} & P_{晴,阴} & P_{晴,雨} \\ P_{阴,晴} & P_{阴,阴} & P_{阴,雨} \\ P_{雨,晴} & P_{雨,阴} & P_{雨,雨} \end{bmatrix}

  • 第一行(i=晴i=晴):今天是晴天时,明天分别是晴、阴、雨的概率。
  • 第二行(i=阴i=阴):今天是阴天时,明天分别是晴、阴、雨的概率。
  • 第三行(i=雨i=雨):今天是雨天时,明天分别是晴、阴、雨的概率。
  • 第一列(j=晴j=晴):从任意状态转移到晴天的概率(按行分别看)。

代入具体数值:

P=[0.70.20.10.30.40.30.20.40.4]P = \begin{bmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.4 & 0.4 \end{bmatrix}

读作:今天晴→明天晴 70%、阴 20%、雨 10%;今天阴→明天晴 30%、阴 40%、雨 30%;今天雨→明天晴 20%、阴 40%、雨 40%。

状态转移矩阵有两个基本性质:

  1. 非负性:Pij≥0P_{ij} \geq 0,对所有 i,ji, j 成立。概率不能为负。
  2. 行和为 1:∑j∈SPij=1\sum_{j \in S} P_{ij} = 1,对所有 ii 成立。为什么是行和为 1 而不是列和为 1? 因为每一行代表"从同一个当前状态 ii 出发",下一步必然要转移到某个状态(包括留在原状态),所以所有可能的下一状态的概率加起来必须等于 1。例如上面矩阵的第一行:0.7+0.2+0.1=10.7 + 0.2 + 0.1 = 1。而列不要求和为 1,因为不同行到达同一列的概率之间没有约束关系。

齐次与非齐次马尔可夫链

如果转移概率 P(st+1=j∣st=i)P(s_{t+1}=j \mid s_t=i) 不随时间 tt 变化(即 PijP_{ij} 在所有时间步都相同),则称为齐次马尔可夫链(Time-Homogeneous Markov Chain,读音 /taɪm ˌhoʊmoʊˈdʒiːniəs/)。本文讨论的默认都是齐次马尔可夫链。

如果转移概率随时间变化(Pij(t)P_{ij}^{(t)} 在不同时间步有不同的值),则称为非齐次马尔可夫链(Time-Inhomogeneous Markov Chain)。

n 步转移概率

从状态 ii 出发,经过 nn(读音 /ɛn/,表示步数,正整数)步后到达状态 jj 的概率,称为 nn 步转移概率,记为 Pij(n)P_{ij}^{(n)}(读音 /piː aɪ dʒeɪ/)。

一个重要的结论是:nn 步转移矩阵等于一步转移矩阵的 nn 次方:

P(n)=PnP^{(n)} = P^n

式中:

  • P(n)P^{(n)}(读音 /piː/)是 nn 步转移矩阵。
  • PnP^n(读音 /piː/)表示一步转移矩阵 PP 自乘 nn 次。

这个结论来自查普曼-科尔莫戈罗夫方程(Chapman-Kolmogorov Equation,读音 /ˈtʃæpmən kɒlˈmɒɡərɒf ɪˈkweɪʒən/):

Pij(m+n)=∑k∈SPik(m)Pkj(n)P_{ij}^{(m+n)} = \sum_{k \in S} P_{ik}^{(m)} P_{kj}^{(n)}

式中:

  • Pij(m+n)P_{ij}^{(m+n)} 是从 ii 经过 m+nm+n 步到 jj 的概率。
  • 求和符号 Σ\Sigma(读音 /ˈsɪɡmə/,希腊字母 sigma 的大写,表示求和)对所有中间状态 kk 求和。
  • Pik(m)P_{ik}^{(m)} 是从 ii 经过 mm 步到中间状态 kk 的概率。
  • Pkj(n)P_{kj}^{(n)} 是从 kk 经过 nn 步到 jj 的概率。

该式的含义是:从 ii 到 jj 经过 m+nm+n 步,可以分解为"先从 ii 经过 mm 步到某个中间状态 kk,再从 kk 经过 nn 步到 jj",对所有可能的中间状态 kk 求和。这正是矩阵乘法的定义。

查普曼-科尔莫戈罗夫方程的完整证明:

第一步:从定义出发。 m+nm+n 步转移概率的定义是:

Pij(m+n)=P(sm+n=j∣s0=i)P_{ij}^{(m+n)} = P(s_{m+n} = j \mid s_0 = i)

式中: sm+ns_{m+n} 表示第 m+nm+n 步的状态,s0s_0 表示初始状态。该式的含义是:已知初始状态为 ii,经过 m+nm+n 步后状态为 jj 的概率。

第二步:用全概率公式引入中间状态。 在第 mm 步时,系统一定处于状态空间中的某个状态 kk。根据全概率公式(Law of Total Probability,读音 /lɔː əv ˈtoʊtl ˌprɒbəˈbɪləti/),可以对所有可能的中间状态 kk 做分解:

P(sm+n=j∣s0=i)=∑k∈SP(sm+n=j, sm=k∣s0=i)P(s_{m+n}=j \mid s_0=i) = \sum_{k \in S} P(s_{m+n}=j,\ s_m=k \mid s_0=i)

全概率公式是什么: 全概率公式的基本思想是:如果一组事件 B1,B2,…,BnB_1, B_2, \dots, B_n 构成样本空间的一个划分(partition,读音 /pɑːrˈtɪʃən/,即这些事件两两互斥且它们的并集覆盖所有可能),那么任意事件 AA 的概率可以拆成"在每个 BkB_k 发生时 AA 发生的概率"之和:

P(A)=∑k=1nP(A∩Bk)=∑k=1nP(A∣Bk)⋅P(Bk)P(A) = \sum_{k=1}^{n} P(A \cap B_k) = \sum_{k=1}^{n} P(A \mid B_k) \cdot P(B_k)

式中: ∩\cap(读音 /ɪnˈtɜːrˈsekʃən/,交集符号,表示"且")表示两个事件同时发生;P(A∣Bk)P(A \mid B_k) 是在 BkB_k 发生时 AA 发生的条件概率;P(Bk)P(B_k) 是 BkB_k 发生的概率。直觉理解:要算 AA 发生的总概率,就把"每条可能路径上 AA 发生的概率"加起来。

这里为什么能用: 在第 mm 步,系统的状态 sms_m 只能取状态空间 SS 中的一个值,而且必然取其中一个值。因此事件 {sm=k}\{s_m = k\}(对所有 k∈Sk \in S)构成了一个划分——它们两两互斥(不能同时处于两个状态)且覆盖全部可能(必然处于某个状态)。所以可以用全概率公式对所有中间状态 kk 求和。

式中: 逗号 ,, 表示"且"(同时发生),即 sm+n=js_{m+n}=j 和 sm=ks_m=k 同时成立;求和对所有可能的中间状态 kk 进行。全概率公式的直觉是:"从 i 到 j 走 m+n 步"这件事,必然经过第 m 步的某个状态 k,把所有可能的 k 的路径概率加起来就是总概率。

第三步:用条件概率乘法法则展开。 根据条件概率的乘法法则 P(A,B∣C)=P(A∣B,C)⋅P(B∣C)P(A,B \mid C) = P(A \mid B,C) \cdot P(B \mid C),上式中的联合条件概率可以拆成两步:

P(sm+n=j, sm=k∣s0=i)=P(sm+n=j∣sm=k, s0=i)⋅P(sm=k∣s0=i)P(s_{m+n}=j,\ s_m=k \mid s_0=i) = P(s_{m+n}=j \mid s_m=k,\ s_0=i) \cdot P(s_m=k \mid s_0=i)

式中: 第一项是"已知第 m 步在 k 且初始在 i,第 m+n 步到 j"的概率;第二项是"已知初始在 i,第 m 步到 k"的概率。

第四步:用马尔可夫性简化第一项。 马尔可夫性告诉我们:下一个状态只依赖于当前状态,与更早的历史无关。所以:

P(sm+n=j∣sm=k, s0=i)=P(sm+n=j∣sm=k)P(s_{m+n}=j \mid s_m=k,\ s_0=i) = P(s_{m+n}=j \mid s_m=k)

式中: 等式左边条件里有 s0=is_0=i(历史),右边去掉了它——因为马尔可夫性说历史不影响未来,给定当前状态 sm=ks_m=k 就够了。而右边恰好就是从 kk 经过 nn 步到 jj 的概率 Pkj(n)P_{kj}^{(n)}(因为齐次链中转移概率不随时间变,第 m 步到第 m+n 步就是 n 步)。

第五步:识别第二项。 P(sm=k∣s0=i)P(s_m=k \mid s_0=i) 就是从 ii 经过 mm 步到 kk 的概率,即 Pik(m)P_{ik}^{(m)}。

第六步:汇总得到结论。 把以上各步代回:

Pij(m+n)=∑k∈SPik(m)⋅Pkj(n)P_{ij}^{(m+n)} = \sum_{k \in S} P_{ik}^{(m)} \cdot P_{kj}^{(n)}

为什么这等于矩阵乘法 P(m)⋅P(n)P^{(m)} \cdot P^{(n)}:

回顾矩阵乘法的元素定义:对于两个矩阵 AA 和 BB,它们的乘积 C=A⋅BC = A \cdot B 的第 ii 行第 jj 列元素为:

Cij=(A⋅B)ij=∑kAik⋅BkjC_{ij} = (A \cdot B)_{ij} = \sum_{k} A_{ik} \cdot B_{kj}

式中: AikA_{ik} 是矩阵 AA 的第 ii 行第 kk 列元素;BkjB_{kj} 是矩阵 BB 的第 kk 行第 jj 列元素;求和对所有中间索引 kk 进行。直觉理解:结果矩阵的每个元素,等于"左边矩阵的第 i 行"与"右边矩阵的第 j 列"对应位置相乘再相加。

现在把查普曼-科尔莫戈罗夫方程的右边与矩阵乘法定义对比:

∑k∈SPik(m)⏟Aik⋅Pkj(n)⏟Bkj=(P(m)⋅P(n))ij\sum_{k \in S} \underbrace{P_{ik}^{(m)}}_{A_{ik}} \cdot \underbrace{P_{kj}^{(n)}}_{B_{kj}} = (P^{(m)} \cdot P^{(n)})_{ij}

式中: 把 P(m)P^{(m)} 看作矩阵 AA,把 P(n)P^{(n)} 看作矩阵 BB,则 Pik(m)P_{ik}^{(m)} 就是 AikA_{ik}(P(m)P^{(m)} 的第 ii 行第 kk 列),Pkj(n)P_{kj}^{(n)} 就是 BkjB_{kj}(P(n)P^{(n)} 的第 kk 行第 jj 列)。两者的结构与矩阵乘法的元素定义完全一致。

因为这个等式对所有 i,j∈Si, j \in S 都成立(不只是某一个格子),所以整个矩阵相等:

P(m+n)=P(m)⋅P(n)P^{(m+n)} = P^{(m)} \cdot P^{(n)}

用一个具体例子验证: 假设状态空间只有 2 个状态 {1,2}\{1, 2\},则:

(P(m)⋅P(n))12=P11(m)P12(n)+P12(m)P22(n)(P^{(m)} \cdot P^{(n)})_{12} = P_{11}^{(m)} P_{12}^{(n)} + P_{12}^{(m)} P_{22}^{(n)}

这恰好就是"从 1 出发,先经 m 步到中间状态 1 或 2,再经 n 步到 2"的所有路径概率之和,与查普曼-科尔莫戈罗夫方程完全一致。

进而,令 m=1m=1 反复应用,得到 P(n)=PnP^{(n)} = P^n(一步转移矩阵自乘 n 次)。

证毕。

状态转移图示例

以一个简单的天气模型为例。状态空间 S={晴,阴,雨}S = \{晴, 阴, 雨\},状态转移矩阵为:

从 \ 到 晴 阴 雨
晴 0.7 0.2 0.1
阴 0.3 0.4 0.3
雨 0.2 0.4 0.4

这个矩阵的含义是:如果今天是晴天,明天有 70% 概率还是晴天,20% 概率阴天,10% 概率雨天。每一行的和都是 1。

0.70.20.10.30.40.30.20.40.4晴阴雨
查看图示结构
stateDiagram-v2
    [*] --> 晴
    晴 --> 晴: 0.7
    晴 --> 阴: 0.2
    晴 --> 雨: 0.1
    阴 --> 晴: 0.3
    阴 --> 阴: 0.4
    阴 --> 雨: 0.3
    雨 --> 晴: 0.2
    雨 --> 阴: 0.4
    雨 --> 雨: 0.4

1.3 马尔可夫链的状态分类

理解马尔可夫链的长期行为,需要对状态进行分类。

常返态与瞬态

  • 常返态(Recurrent State,读音 /rɪˈkɜːrənt steɪt/):从该状态出发,最终一定能回到该状态(概率为 1)。常返态会被无限次访问。
  • 瞬态(Transient State,读音 /trænˈzɪʃən steɪt/):从该状态出发,有大于 0 的概率永远不回来。瞬态只会被访问有限次。

周期与非周期

状态 ii 的周期(Period,读音 /ˈpɪəriəd/)d(i)d(i) 定义为所有满足 Pii(n)>0P_{ii}^{(n)} > 0 的 nn 的最大公约数。如果 d(i)=1d(i) = 1,称该状态为非周期(Aperiodic,读音 /ˌeɪpɪriˈɒdɪk/)的;如果 d(i)>1d(i) > 1,称为周期(Periodic)的。

逐部分拆解这个定义:

  1. Pii(n)P_{ii}^{(n)} 是什么? 这是 nn 步转移概率的特例:从状态 ii 出发,经过 nn 步后回到状态 ii 的概率。Pii(n)>0P_{ii}^{(n)} > 0 意味着"走 nn 步是有可能回到 ii 的"。

  2. "所有满足 Pii(n)>0P_{ii}^{(n)} > 0 的 nn"是什么? 把所有"能回到 ii"的步数收集起来,形成一个集合。比如:如果走 2 步能回来、走 4 步能回来、走 6 步能回来……这个集合就是 {2,4,6,8,… }\{2, 4, 6, 8, \dots\}。

  3. 最大公约数(Greatest Common Divisor,简称 gcd,读音 /ˈɡriːtɪst ˈkɒmən dɪˈvaɪzər/)是什么? 一组正整数的最大公约数,是能同时整除这组数中每一个数的最大正整数。比如 gcd(6, 9, 12) = 3,因为 3 能同时整除 6、9、12,而比 3 大的数(如 6)不能整除 9。

把三部分合起来: 周期 d(i)d(i) 就是"所有能回到 ii 的步数"的最大公约数。它衡量的是:回到 ii 这件事,是否存在一个固定的"节奏"或"间隔"。

具体例子:

  • 例 1(周期为 2): 假设状态 ii 只能在偶数步回到自身——走 2 步能回、4 步能回、6 步能回,但走 1、3、5 等奇数步不可能回来。那么"能回来的步数集合"是 {2,4,6,8,… }\{2, 4, 6, 8, \dots\},gcd = 2,所以 d(i)=2d(i) = 2。直觉:这个状态有"隔一步才能回来"的节奏。

  • 例 2(非周期,周期为 1): 假设状态 ii 走 2 步能回、走 3 步也能回。那么"能回来的步数集合"包含 2 和 3,gcd(2, 3) = 1,所以 d(i)=1d(i) = 1。一旦 2 和 3 都能回来,那么 4=2+2、5=2+3、6=3+3……所有更大的数都能回来,gcd 仍然是 1。直觉:这个状态没有固定节奏,随时可能回来。

  • 例 3(周期为 3): 假设状态 ii 只能在 3 的倍数步回到自身——3 步、6 步、9 步……集合是 {3,6,9,… }\{3, 6, 9, \dots\},gcd = 3,所以 d(i)=3d(i) = 3。

为什么周期重要? 马尔可夫链收敛到平稳分布的一个关键条件是不可约 + 非周期(加上正常返)。如果链是周期的(d>1d > 1),状态分布会在不同的"相位"之间循环振荡,不会收敛到一个稳定分布。比如周期为 2 的链,奇数步和偶数步的分布可能不同,永远在两个分布之间来回跳。

吸收态

吸收态(Absorbing State,读音 /əbˈzɔːrbɪŋ steɪt/):满足 Pii=1P_{ii} = 1 的状态。一旦进入吸收态,就永远不会离开。例如"游戏结束"状态就是吸收态。

不可约与遍历

不可约(Irreducible,读音 /ˌɪrɪˈduːsəbl/):从任意状态出发,都能到达任意其他状态(对所有 i,ji,j,存在 nn 使得 Pij(n)>0P_{ij}^{(n)} > 0)。整个状态空间是一个连通的整体,不存在"走不出去的封闭子区域"。

为什么需要不可约: 如果链是可约的(reducible),状态空间会分裂成多个互不连通的"类",每个类可能有自己的平稳分布,导致平稳分布不唯一。比如状态空间分成 {A,B} 和 {C,D} 两个互不连通的区域,从 A 出发永远到不了 C,那么整个链就没有一个统一的平稳分布。

常返(Recurrent,读音 /rɪˈkɜːrənt/):从该状态出发,最终一定能回到该状态(返回概率为 1)。常返态会被无限次访问。与之相对的是瞬态(Transient,读音 /trænˈzɪʃənt/):从该状态出发,有大于 0 的概率永远不回来,瞬态只会被访问有限次。

为什么需要常返: 如果状态是瞬态的,链跑着跑着就可能"离开"这个状态再也不回来,那么这个状态在长期运行中被访问的频率为 0,平稳分布中它的概率就是 0。只有常返态才会在长期中被持续访问,才有非零的平稳概率。

非周期(Aperiodic,读音 /ˌeɪpɪriˈɒdɪk/):状态的周期 d(i)=1d(i)=1,即返回该状态的步数没有固定的公共间隔。与之相对的是周期(Periodic):返回步数存在大于 1 的公共间隔(如只能在偶数步返回)。

为什么需要非周期: 如果链是周期的(d>1d>1),状态分布会在不同的"相位"之间循环振荡,不会收敛到一个稳定分布。比如周期为 2 的链,奇数步和偶数步的分布可能不同,永远在两个分布之间来回跳,没有极限。

三个条件合在一起 = 遍历: 一个不可约 + 非周期 + 常返的马尔可夫链称为遍历的(Ergodic,读音 /ɜːrˈɡɒdɪk/)。这三个条件各自排除了一种"坏情况":

条件 排除的坏情况 缺少时的后果
不可约 状态空间分裂成多个互不连通的类 平稳分布不唯一
常返 状态跑出去就不回来 该状态长期访问频率为 0
非周期 返回有固定节奏 分布振荡不收敛

三个条件同时满足时,链具有以下良好性质:

  1. 平稳分布唯一:只有一个 π\pi 满足 π=πP\pi = \pi P。
  2. 收敛性:从任意初始分布出发,经过足够多步后都会收敛到 π\pi(即遍历定理 lim⁡n→∞Pij(n)=π(j)\lim_{n\to\infty} P_{ij}^{(n)} = \pi(j) 成立)。
  3. 遍历性(时间平均 = 空间平均):沿着一条足够长的链计算的时间平均,等于在平稳分布下计算的空间平均。即 lim⁡T→∞1T∑t=1Tf(st)=Eπ[f(s)]\lim_{T\to\infty} \frac{1}{T}\sum_{t=1}^T f(s_t) = \mathbb{E}_\pi[f(s)](E\mathbb{E} 读音 /iː/,数学期望符号,expectation 的缩写)。这是 MCMC 采样方法的理论基础——跑一条链采集样本,样本均值就能逼近目标分布下的期望。

遍历性的详细解释与推导:

什么是时间平均: 你跑一条马尔可夫链,比如模拟天气,跑了 TT 天,记录每天的天气 s1,s2,…,sTs_1, s_2, \dots, s_T。然后对某个函数 ff(比如"晴天记 1,其他记 0")计算这 TT 天的平均值:

时间平均=1T∑t=1Tf(st)\text{时间平均} = \frac{1}{T}\sum_{t=1}^{T} f(s_t)

这是沿着时间轴算出来的平均值。如果 f(s)=1{s=晴}f(s)=\mathbb{1}\{s=晴\}(指示函数,晴天为 1 否则为 0),时间平均就是"这 TT 天里晴天的比例"。

什么是空间平均: 不跑链,直接用平稳分布 π\pi 来算函数 ff 的数学期望。Eπ[f(s)]\mathbb{E}_\pi[f(s)] 就是数学期望,下标 π\pi 表示"在分布 π\pi 下"求期望(普通的 E[X]\mathbb{E}[X] 默认在某个分布下,这里明确标出是 π\pi)。计算方式就是每个状态的概率乘以该状态下 ff 的值,全部加起来:

空间平均=Eπ[f(s)]=∑s∈Sπ(s)⋅f(s)\text{空间平均} = \mathbb{E}_\pi[f(s)] = \sum_{s \in S} \pi(s) \cdot f(s)

用天气例子具体算一遍:π=(0.476,0.361,0.163)\pi=(0.476, 0.361, 0.163) 对应(晴、阴、雨),ff 是"晴天记1、其他记0":

Eπ[f(s)]=0.476×1+0.361×0+0.163×0=0.476\mathbb{E}_\pi[f(s)] = 0.476 \times 1 + 0.361 \times 0 + 0.163 \times 0 = 0.476

"空间平均"的通俗理解: 想象你不跑链,而是直接"按分布 π\pi 独立抽很多次天气"——每次都按 47.6%晴、36.1%阴、16.3%雨 来抽,抽 10000 次完全独立的天气,然后算晴天比例。这个比例就是空间平均,它会趋近于 0.476。"空间"指的是状态空间——不是沿着时间轴一步步走,而是直接在所有可能状态上按分布加权平均。

两种平均的对比:

时间平均 空间平均
怎么来的 跑一条链,走 10000 步,统计晴天比例 按 π\pi 独立抽 10000 次,统计晴天比例
样本关系 相邻天相关(今天晴→明天大概率晴) 每次抽取完全独立
极限值 →0.476\to 0.476 →0.476\to 0.476

遍历性说的就是:这两种做法得到的结果一样。 哪怕时间平均的样本是相关的(马尔可夫链相邻状态不独立),只要链足够长,最终结果和独立采样的空间平均相同。这就是为什么 MCMC 能用——虽然链上的样本不独立,但跑够久之后,样本均值依然能逼近真实期望。

为什么时间平均等于空间平均(推导思路):

第一步:对于常返态 ii,定义返回时间 Ti=min⁡{t>0:st=i}T_i = \min\{t>0: s_t=i\}(从 ii 出发到下一次回到 ii 的时间)。常返性保证 TiT_i 有限(概率为 1)。

第二步:一个基本结论是:状态 ii 的长期访问频率等于返回时间期望的倒数:

lim⁡T→∞前 T 步中访问 i 的次数T=1E[Ti]\lim_{T\to\infty} \frac{\text{前 } T \text{ 步中访问 } i \text{ 的次数}}{T} = \frac{1}{\mathbb{E}[T_i]}

直觉理解:如果平均每 10 步回一次 ii(E[Ti]=10\mathbb{E}[T_i]=10),那么长期来看每 10 步就有 1 步在 ii,访问频率就是 1/10=0.11/10=0.1。

第三步:对于不可约链,所有状态的访问频率加起来为 1,构成一个分布。令 π(i)=1/E[Ti]∑j∈S1/E[Tj]\pi(i) = \frac{1/\mathbb{E}[T_i]}{\sum_{j \in S} 1/\mathbb{E}[T_j]},可以证明这个 π\pi 满足 π=πP\pi = \pi P(平稳分布条件),因此它就是平稳分布。

第四步:时间平均可以按访问频率展开:

1T∑t=1Tf(st)=∑i∈S访问 i 的次数T⋅f(i)→T→∞∑i∈Sπ(i)f(i)=Eπ[f(s)]\frac{1}{T}\sum_{t=1}^{T} f(s_t) = \sum_{i \in S} \frac{\text{访问 } i \text{ 的次数}}{T} \cdot f(i) \xrightarrow{T\to\infty} \sum_{i \in S} \pi(i) f(i) = \mathbb{E}_\pi[f(s)]

式中: 第一步把时间平均按"每个状态被访问了多少次"重新分组;第二步取极限,访问频率收敛到平稳分布 π(i)\pi(i);最后一步就是空间平均的定义。

用天气的具体数值验证: 平稳分布 π=(0.476,0.361,0.163)\pi=(0.476, 0.361, 0.163)。跑一条链 10000 天,统计晴天比例,大约会得到 47.6%;而空间平均 Eπ[1{s=晴}]=π(晴)=0.476\mathbb{E}_\pi[\mathbb{1}\{s=晴\}] = \pi(晴)=0.476。两者相等。

对 MCMC 的意义: 很多时候我们想算 Eπ[f(s)]\mathbb{E}_\pi[f(s)],但 π\pi 是一个复杂分布(如贝叶斯后验),直接解析计算不可能。遍历性告诉我们:不用直接算分布,只要构造一条平稳分布等于 π\pi 的马尔可夫链,跑足够长时间,用样本均值 1T∑f(st)\frac{1}{T}\sum f(s_t) 就能逼近这个期望。 这就是 MCMC 的核心思想。

1.4 平稳分布与细致平衡

平稳分布

先理解什么是"状态分布": 在马尔可夫链的第 tt 步,系统可能处于状态空间中的任意一个状态。用一个概率分布 πt\pi_t(读音 /paɪ/,下标 tt 表示第 tt 步的分布)来描述"此时系统处于各个状态的概率"。πt\pi_t 是一个行向量,其中 πt(i)\pi_t(i) 表示第 tt 步系统处于状态 ii 的概率。

例如天气模型中,πt=(0.5,0.3,0.2)\pi_t = (0.5, 0.3, 0.2) 表示"今天有 50% 概率晴、30% 概率阴、20% 概率雨"。

状态分布如何随时间演化: 已知第 tt 步的分布 πt\pi_t,第 t+1t+1 步的分布可以通过转移矩阵计算:

πt+1(j)=∑i∈Sπt(i)⋅Pij\pi_{t+1}(j) = \sum_{i \in S} \pi_t(i) \cdot P_{ij}

式中: πt+1(j)\pi_{t+1}(j) 是第 t+1t+1 步处于状态 jj 的概率;πt(i)\pi_t(i) 是第 tt 步处于状态 ii 的概率;PijP_{ij} 是从 ii 转移到 jj 的概率。直觉理解:要算"明天是晴天的概率",就要把"今天每种天气的概率 × 该天气转移到晴天的概率"全部加起来。写成矩阵形式就是 πt+1=πtP\pi_{t+1} = \pi_t P。

平稳分布的定义: 如果存在一个分布 π\pi,使得用它乘以转移矩阵后得到的还是它自己——即经过一步转移后分布不变——那么 π\pi 就称为这个马尔可夫链的平稳分布(Stationary Distribution,读音 /ˈsteɪʃəneri ˌdɪstrɪˈbjuːʃən/):

π=πP\pi = \pi P

展开成元素形式就是:

π(j)=∑i∈Sπ(i)Pij,∀j∈S\pi(j) = \sum_{i \in S} \pi(i) P_{ij}, \quad \forall j \in S

式中: π(j)\pi(j) 是平稳分布中状态 jj 的概率;π(i)\pi(i) 是状态 ii 的概率;PijP_{ij} 是从 ii 到 jj 的转移概率。该式的含义是:处于状态 jj 的"总流入概率"(从所有其他状态 ii 转移到 jj 的概率之和)等于当前处于 jj 的概率——流入等于流出,分布达到动态平衡。

用具体数值例子理解收敛: 还是用天气模型,转移矩阵为:

P=[0.70.20.10.30.40.30.20.40.4]P = \begin{bmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.4 & 0.4 \end{bmatrix}

假设初始分布 π0=(1,0,0)\pi_0 = (1, 0, 0)(今天确定是晴天),逐步演化:

  • π1=π0P=(0.7,0.2,0.1)\pi_1 = \pi_0 P = (0.7, 0.2, 0.1)(明天:晴 70%、阴 20%、雨 10%)
  • π2=π1P=(0.57,0.30,0.13)\pi_2 = \pi_1 P = (0.57, 0.30, 0.13)(后天:晴 57%、阴 30%、雨 13%)
  • π3=π2P=(0.518,0.336,0.146)\pi_3 = \pi_2 P = (0.518, 0.336, 0.146)
  • π4=(0.495,0.350,0.155)\pi_4 = (0.495, 0.350, 0.155)
  • π5=(0.485,0.356,0.159)\pi_5 = (0.485, 0.356, 0.159)
  • ...
  • 最终收敛到 π≈(0.476,0.361,0.163)\pi \approx (0.476, 0.361, 0.163)

可以验证:πP=(0.476,0.361,0.163)×P=(0.476,0.361,0.163)=π\pi P = (0.476, 0.361, 0.163) \times P = (0.476, 0.361, 0.163) = \pi,确实满足平稳分布条件。

"收敛到平稳分布"是什么意思: 对于遍历(不可约 + 非周期 + 常返)的马尔可夫链,无论初始分布 π0\pi_0 是什么(哪怕今天 100% 是晴天,或 100% 是雨天),经过足够多步后,状态分布都会趋近于同一个平稳分布 π\pi。用数学语言表达就是遍历定理(Ergodic Theorem):

lim⁡n→∞Pij(n)=π(j)\lim_{n \to \infty} P_{ij}^{(n)} = \pi(j)

式中: lim⁡\lim(读音 /ˈlɪmɪt/,limit 的缩写,表示极限)n→∞n \to \infty 表示 nn 趋向于无穷大;Pij(n)P_{ij}^{(n)} 是从 ii 出发经过 nn 步到 jj 的概率(一个具体数值,不是整个矩阵)。该式的含义是:无论从哪个状态 ii 出发,经过足够多步后,到达状态 jj 的概率都会收敛到平稳分布 π(j)\pi(j)——初始状态的影响被"遗忘"了。

注意 π(j)\pi(j) 是一个概率值,不是整个分布: π\pi 是整个平稳分布(一个行向量),而 π(j)\pi(j) 是这个向量中状态 jj 对应的那个概率值。公式 π(j)=∑i∈Sπ(i)Pij\pi(j) = \sum_{i \in S} \pi(i) P_{ij} 对每个 j∈Sj \in S 都成立,是平稳分布的元素级定义。

用数值例子直观理解"遗忘初始状态": 还是用天气模型,看从不同初始状态出发,经过 nn 步后到达"晴"的概率 Pi,晴(n)P_{i,晴}^{(n)}:

初始状态 ii n=1n=1 n=2n=2 n=5n=5 n=10n=10 n=100n=100
晴 0.700 0.570 0.485 0.477 ≈0.476
阴 0.300 0.450 0.473 0.476 ≈0.476
雨 0.200 0.420 0.468 0.476 ≈0.476

可以看到:n=1n=1 时不同起点差别很大(0.7 vs 0.3 vs 0.2),n=5n=5 时已经很接近,n=100n=100 时无论从哪出发都是 ≈0.476。这个 0.476 就是 π(晴)\pi(晴)。

矩阵极限形式: 因为对所有 ii 都有 lim⁡n→∞Pij(n)=π(j)\lim_{n\to\infty} P_{ij}^{(n)} = \pi(j),所以 nn 步转移矩阵 P(n)P^{(n)} 的每一行在极限时都变成了同一个行向量 π\pi:

P(n)→n→∞[π(1)π(2)…π(∣S∣)π(1)π(2)…π(∣S∣)⋮⋮⋱⋮π(1)π(2)…π(∣S∣)]P^{(n)} \xrightarrow{n \to \infty} \begin{bmatrix} \pi(1) & \pi(2) & \dots & \pi(|S|) \\ \pi(1) & \pi(2) & \dots & \pi(|S|) \\ \vdots & \vdots & \ddots & \vdots \\ \pi(1) & \pi(2) & \dots & \pi(|S|) \end{bmatrix}

所有行完全相同——这就是"初始状态被遗忘"的矩阵表达。

这就是为什么 MCMC(第五章)可以通过采样来逼近目标分布:构造一个平稳分布等于目标分布的马尔可夫链,跑足够多步后采集的样本就近似服从目标分布。

细致平衡

细致平衡(Detailed Balance,读音 /dɪˈteɪld bəˈlæns/)是平稳分布的一个充分条件(但不是必要条件)。如果存在一个分布 π\pi 满足:

π(i)Pij=π(j)Pji,∀i,j∈S\pi(i) P_{ij} = \pi(j) P_{ji}, \quad \forall i, j \in S

逐部分解释这个公式:

  • π(i)\pi(i):平稳分布中状态 ii 的概率(即"系统处于 ii 的概率")。
  • PijP_{ij}:从 ii 转移到 jj 的概率。
  • π(i)Pij\pi(i) P_{ij}:从 ii 流向 jj 的概率流(probability flux,读音 /ˌprɒbəˈbɪləti flʌks/)。直觉理解:如果有 1000 个独立运行的链,其中大约 π(i)×1000\pi(i) \times 1000 个处于状态 ii,其中又有 PijP_{ij} 比例会转移到 jj,所以单位时间内从 ii 到 jj 的"流量"就是 π(i)Pij\pi(i) P_{ij}。
  • π(j)Pji\pi(j) P_{ji}:从 jj 流向 ii 的概率流。
  • ∀i,j∈S\forall i,j \in S:对任意两个状态 ii 和 jj 都成立。

公式的含义: 对于任意一对状态 ii 和 jj,从 ii 流向 jj 的流量等于从 jj 流向 ii 的流量——双向流量相等。这比平稳分布条件(π=πP\pi = \pi P,只要求每个状态的总流入等于总流出)更强:平稳分布只要求"每个状态的净流入为零",而细致平衡要求"每一对状态之间的双向流量都相等"。

为什么细致平衡能推出平稳分布(推导): 对细致平衡公式两边同时对 ii 求和:

∑i∈Sπ(i)Pij=∑i∈Sπ(j)Pji\sum_{i \in S} \pi(i) P_{ij} = \sum_{i \in S} \pi(j) P_{ji}

右边 π(j)\pi(j) 与求和变量 ii 无关,可以提出来:

∑i∈Sπ(i)Pij=π(j)∑i∈SPji\sum_{i \in S} \pi(i) P_{ij} = \pi(j) \sum_{i \in S} P_{ji}

而转移矩阵的行和为 1(∑i∈SPji=1\sum_{i \in S} P_{ji} = 1,从 jj 出发转移到所有状态的概率之和为 1),所以:

关于 PjiP_{ji} 和求和变量的说明: PjiP_{ji} 是转移矩阵第 jj 行第 ii 列的元素,表示从状态 jj 转移到状态 ii 的概率(第一个下标是"从哪来"/行,第二个下标是"到哪去"/列)。这里的求和变量是 ii,所以 ∑iPji\sum_i P_{ji} 是把第 jj 行的所有元素加起来。用天气模型举例,j=晴j=晴 时:∑iP晴,i=P晴,晴+P晴,阴+P晴,雨=0.7+0.2+0.1=1\sum_i P_{晴,i} = P_{晴,晴}+P_{晴,阴}+P_{晴,雨}=0.7+0.2+0.1=1。

注意:求和变量 ii 是哑变量(dummy variable,读音 /ˈdʌmi ˈveəriəbl/),只是一个"计数器",可以换成任何未使用的字母(如 kk)而不改变结果,即 ∑iPji=∑kPjk\sum_i P_{ji} = \sum_k P_{jk}。但不能换成 jj,因为 jj 在公式中已经是固定的目标状态(自由变量),换成 jj 会导致含义改变(∑jPjj\sum_j P_{jj} 变成了"对所有状态求自转移概率之和",完全不同)。

∑i∈Sπ(i)Pij=π(j)\sum_{i \in S} \pi(i) P_{ij} = \pi(j)

这恰好就是平稳分布的元素级定义 π(j)=∑iπ(i)Pij\pi(j) = \sum_i \pi(i) P_{ij}。因此细致平衡成立时,π\pi 一定是平稳分布。

为什么是充分条件但不是必要条件: 细致平衡比平稳分布更强。平稳分布只要求每个状态的总流入等于总流出(可以存在"环流",比如 A→B→C→AA \to B \to C \to A 的循环流量,每对状态之间双向流量不等,但每个状态的净流入仍为零)。而细致平衡要求每对状态之间双向流量都相等,排除了环流的存在。所以:满足细致平衡 → 一定是平稳分布;但是平稳分布 → 不一定满足细致平衡。

用天气模型验证: 平稳分布 π=(0.476,0.361,0.163)\pi=(0.476, 0.361, 0.163),检查"晴"和"阴"之间:

  • 正向流量:π(晴)P晴,阴=0.476×0.2=0.0952\pi(晴) P_{晴,阴} = 0.476 \times 0.2 = 0.0952
  • 反向流量:π(阴)P阴,晴=0.361×0.3=0.1083\pi(阴) P_{阴,晴} = 0.361 \times 0.3 = 0.1083

两者不相等,说明这个天气模型的平稳分布不满足细致平衡(存在环流),但它仍然是平稳分布。这就是"充分但不必要"的具体例子。

对 MCMC 的意义: 细致平衡是 MCMC 方法(如 Metropolis-Hastings、Gibbs 采样)的核心设计原则。我们想要从目标分布 π\pi 中采样,但直接采样很难。于是我们反过来设计转移矩阵 PP,使得 PP 满足细致平衡 π(i)Pij=π(j)Pji\pi(i)P_{ij} = \pi(j)P_{ji}。这样构造出的马尔可夫链,其平稳分布就恰好是我们想要的 π\pi,跑足够多步后采集的样本就近似服从 π\pi。


二、隐马尔可夫模型(HMM)

隐马尔可夫模型(Hidden Markov Model,简称 HMM,读音 /ˈhɪdn ˈmɑːrkɒv ˈmɒdl/)是马尔可夫链的扩展:系统的真实状态是隐藏的(不可直接观测),我们只能观测到由隐藏状态产生的观测(Observation)。HMM 在语音识别、自然语言处理(词性标注、命名实体识别)、生物信息学(基因序列分析)等领域有广泛应用。

2.1 HMM 的定义

先从一个具体例子理解什么是"隐": 假设你想知道每天的天气(晴/雨),但你看不到外面的天气(比如被关在房间里),你只能观察到室友每天的活动(散步/购物/打扫)。根据常识:

  • 晴天时,室友更可能去散步
  • 雨天时,室友更可能在家打扫

这里天气是隐藏状态(你看不到),活动是观测(你能看到)。HMM 就是用来描述"隐藏状态如何转移、隐藏状态如何产生观测"的模型。

观测层(你看得到)隐藏层(你看不到)第一天天气第二天天气第三天天气第一天活动第二天活动第三天活动
查看图示结构
graph LR
    subgraph 隐藏层(你看不到)
        q1[第一天天气] --> q2[第二天天气] --> q3[第三天天气]
    end
    subgraph 观测层(你看得到)
        o1[第一天活动] --> o2[第二天活动] --> o3[第三天活动]
    end
    q1 --> o1
    q2 --> o2
    q3 --> o3

上层天气之间按马尔可夫链转移(今天晴→明天大概率晴),每个天气产生一个活动观测(晴→大概率散步)。你只能看到下层的活动序列,需要通过它来推断上层的天气。

HMM 的五元组定义:

一个 HMM 由以下五个部分定义:

  1. 隐藏状态空间 S={s1,s2,…,sN}S = \{s_1, s_2, \dots, s_N\}(读音 /ɛs/):所有可能的隐藏状态的集合。例子中 S={晴,雨}S = \{晴, 雨\},N=2N=2。NN(读音 /ɛn/)是隐藏状态的数量。隐藏状态之间满足马尔可夫性质(下一状态只依赖当前状态)。

  2. 观测空间 V={v1,v2,…,vM}V = \{v_1, v_2, \dots, v_M\}(读音 /viː/):所有可能的观测值的集合。例子中 V={散步,购物,打扫}V = \{散步, 购物, 打扫\},M=3M=3。MM(读音 /ɛm/)是观测值的数量。

  3. 初始状态分布 π={π1,π2,…,πN}\pi = \{\pi_1, \pi_2, \dots, \pi_N\}(读音 /paɪ/):第一天(t=1t=1)处于各隐藏状态的概率。例子中 π=(0.6,0.4)\pi = (0.6, 0.4) 表示第一天 60% 概率晴、40% 概率雨。

  4. 状态转移矩阵 A={aij}A = \{a_{ij}\}(读音 /eɪ/):隐藏状态之间的转移概率。aija_{ij} 表示从隐藏状态 sis_i 转移到 sjs_j 的概率。例子中: A=[a晴,晴a晴,雨a雨,晴a雨,雨]=[0.70.30.40.6]A = \begin{bmatrix} a_{晴,晴} & a_{晴,雨} \\ a_{雨,晴} & a_{雨,雨} \end{bmatrix} = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} 即今天晴→明天晴 70%、雨 30%;今天雨→明天晴 40%、雨 60%。

  5. 观测概率矩阵 B={bj(ot)}B = \{b_j(o_t)\}(读音 /biː/):在隐藏状态 sjs_j 下产生观测 oto_t 的概率。例子中: B=[b晴(散步)b晴(购物)b晴(打扫)b雨(散步)b雨(购物)b雨(打扫)]=[0.60.30.10.10.40.5]B = \begin{bmatrix} b_{晴}(散步) & b_{晴}(购物) & b_{晴}(打扫) \\ b_{雨}(散步) & b_{雨}(购物) & b_{雨}(打扫) \end{bmatrix} = \begin{bmatrix} 0.6 & 0.3 & 0.1 \\ 0.1 & 0.4 & 0.5 \end{bmatrix} 即晴天时 60% 散步、30% 购物、10% 打扫;雨天时 10% 散步、40% 购物、50% 打扫。

三个概率矩阵的精确定义公式:

初始状态分布:

πi=P(q1=si)\pi_i = P(q_1 = s_i)

式中: πi\pi_i 是初始时刻(第 1 步)处于隐藏状态 sis_i 的概率;qtq_t(读音 /kjuː tiː/)表示第 tt 步的隐藏状态(qq 是 hidden state 的常用符号)。

下标区分: 公式中 πi\pi_i 和 sis_i 的下标 ii 是状态索引(表示第几个状态,如 i=1i=1 是晴、i=2i=2 是雨),而 q1q_1 的下标 11 是时间步索引(表示第 1 天/第 1 步)。两者是完全不同的维度:ii 在遍历所有状态,11 固定指初始时刻。代入具体值:i=1i=1 时 π1=P(q1=s1)=P(第一天是晴)=0.6\pi_1 = P(q_1 = s_1) = P(\text{第一天是晴}) = 0.6;i=2i=2 时 π2=P(q1=s2)=P(第一天是雨)=0.4\pi_2 = P(q_1 = s_2) = P(\text{第一天是雨}) = 0.4。

状态转移概率:

aij=P(qt+1=sj∣qt=si)a_{ij} = P(q_{t+1} = s_j \mid q_t = s_i)

式中: aija_{ij} 是从隐藏状态 sis_i 转移到 sjs_j 的概率;竖线 ∣\mid 表示"条件于"(已知当前状态是 sis_i)。这和第一章马尔可夫链的转移概率 PijP_{ij} 是同一个东西,只是 HMM 中习惯用 aija_{ij} 表示。

观测概率:

bj(ot)=P(ot∣qt=sj)b_j(o_t) = P(o_t \mid q_t = s_j)

式中: bj(ot)b_j(o_t) 是在隐藏状态 sjs_j 下产生观测 oto_t 的概率;oto_t(读音 /oʊ tiː/,oo 是 observation 的缩写)是第 tt 步的观测值。该式的含义是:已知第 tt 步的隐藏状态是 sjs_j,观测到 oto_t 的概率是多少。

因此,一个 HMM 通常记为 λ=(A,B,π)\lambda = (A, B, \pi)(读音 /ˈlæmdə/,希腊字母 lambda,这里作为 HMM 全部参数的整体代号)。知道了 AA、BB、π\pi 这三个矩阵,就完全确定了一个 HMM。

2.2 HMM 的两个基本假设

HMM 建立在两个假设之上:

  1. 马尔可夫假设(Markov Assumption):隐藏状态序列满足马尔可夫性质,即下一隐藏状态只依赖于当前隐藏状态。
  2. 输出独立性假设(Output Independence Assumption):第 tt 步的观测 oto_t 只依赖于第 tt 步的隐藏状态 qtq_t,与其他隐藏状态和观测无关。
观测层隐藏层q₁ 隐藏状态q₂ 隐藏状态q₃ 隐藏状态... 隐藏状态o₁ 观测o₂ 观测o₃ 观测... 观测
查看图示结构
graph LR
    subgraph 隐藏层
        q1[q₁ 隐藏状态] --> q2[q₂ 隐藏状态] --> q3[q₃ 隐藏状态] --> q4[... 隐藏状态]
    end
    subgraph 观测层
        o1[o₁ 观测] --> o2[o₂ 观测] --> o3[o₃ 观测] --> o4[... 观测]
    end
    q1 --> o1
    q2 --> o2
    q3 --> o3
    q4 --> o4

上图展示了 HMM 的结构:上层是隐藏的马尔可夫链(状态之间有转移),下层是观测序列(每个观测只由对应时刻的隐藏状态生成)。隐藏状态之间的箭头表示状态转移 AA,隐藏状态到观测的箭头表示观测概率 BB。

2.3 HMM 的三个基本问题

HMM 的理论和应用围绕三个基本问题展开:

问题 名称 描述 求解算法
问题一 评估问题 给定模型 λ=(A,B,π)\lambda=(A,B,\pi) 和观测序列 OO,计算观测序列出现的概率 前向算法 / 后向算法
问题二 解码问题 给定模型 λ\lambda 和观测序列 OO,找到最可能产生该观测的隐藏状态序列 Viterbi 算法
问题三 学习问题 给定观测序列 OO,估计模型参数 λ=(A,B,π)\lambda=(A,B,\pi) 使概率最大 Baum-Welch 算法(EM)

问题一:评估问题与前向算法

给定观测序列 O=(o1,o2,…,oT)O = (o_1, o_2, \dots, o_T)(读音 /oʊ/,TT 是序列长度),计算 P(O∣λ)P(O \mid \lambda)。

最朴素的方法是枚举所有可能的隐藏状态序列 Q=(q1,…,qT)Q = (q_1, \dots, q_T),计算联合概率再求和:

P(O∣λ)=∑q1,...,qTπq1bq1(o1)aq1q2bq2(o2)⋯aqT−1qTbqT(oT)P(O \mid \lambda) = \sum_{q_1,...,q_T} \pi_{q_1} b_{q_1}(o_1) a_{q_1 q_2} b_{q_2}(o_2) \cdots a_{q_{T-1} q_T} b_{q_T}(o_T)

式中:

  • πq1\pi_{q_1} 是初始状态 q1q_1 的概率。
  • bqt(ot)b_{q_t}(o_t) 是在状态 qtq_t 下产生观测 oto_t 的概率。
  • aqtqt+1a_{q_t q_{t+1}} 是从 qtq_t 转移到 qt+1q_{t+1} 的概率。

这个求和有 NTN^T 项(NN 个状态、TT 个时间步的所有组合),计算量随 TT 指数增长,不可行。

前向算法(Forward Algorithm,读音 /ˈfɔːrwərd ˈælɡərɪðəm/)通过动态规划将复杂度降到 O(N2T)O(N^2 T)。定义前向变量(Forward Variable):

αt(i)=P(o1,o2,…,ot,qt=si∣λ)\alpha_t(i) = P(o_1, o_2, \dots, o_t, q_t = s_i \mid \lambda)

式中:

  • αt(i)\alpha_t(i)(读音 /ˈælfə tiː/,α\alpha 是希腊字母 alpha,读音 /ˈælfə/)表示"前 tt 步的观测为 o1o_1 到 oto_t,且第 tt 步处于隐藏状态 sis_i"的联合概率。

前向算法的递推过程:

  1. 初始化(t=1t=1):对所有 ii,初始状态概率乘以产生第一个观测的概率,即

    α1(i)=πi⋅bi(o1)\alpha_1(i) = \pi_i \cdot b_i(o_1)

  2. 递推(t=1,2,…,T−1t = 1, 2, \dots, T-1):

αt+1(j)=[∑i=1Nαt(i)aij]bj(ot+1)\alpha_{t+1}(j) = \left[\sum_{i=1}^{N} \alpha_t(i) a_{ij}\right] b_j(o_{t+1})

式中:

  • 方括号内的求和表示"从所有可能的前一状态 ii 转移到 jj"的概率之和。
  • 然后乘以在状态 jj 下产生观测 ot+1o_{t+1} 的概率。

这个递推利用了马尔可夫性质:到达 jj 的所有路径的概率可以合并。

  1. 终止:对最后一步所有可能的隐藏状态求和,得到观测序列的概率:

    P(O∣λ)=∑i=1NαT(i)P(O \mid \lambda) = \sum_{i=1}^{N} \alpha_T(i)

类似地,后向算法(Backward Algorithm)定义后向变量 βt(i)\beta_t(i)(读音 /ˈbeɪtə tiː/,β\beta 是希腊字母 beta,读音 /ˈbeɪtə/),从后往前递推:

βt(i)=P(ot+1,ot+2,…,oT∣qt=si,λ)\beta_t(i) = P(o_{t+1}, o_{t+2}, \dots, o_T \mid q_t = s_i, \lambda)

前向和后向变量结合起来,可以用于 Baum-Welch 学习算法。

问题二:解码问题与 Viterbi 算法

给定观测序列 OO,找到最可能的隐藏状态序列 Q∗=arg⁡max⁡QP(Q∣O,λ)Q^* = \arg\max_Q P(Q \mid O, \lambda)(读音 /kjuː stɑːr/,argmax 表示"使后面的函数取最大值的自变量")。

Viterbi 算法(读音 /vɪˈtɜːrbi ˈælɡərɪðəm/,得名于工程师安德鲁·维特比,Andrew Viterbi)同样使用动态规划,但不是求和,而是取最大值。定义Viterbi 变量:

δt(i)=max⁡q1,...,qt−1P(q1,…,qt−1,qt=si,o1,…,ot∣λ)\delta_t(i) = \max_{q_1,...,q_{t-1}} P(q_1, \dots, q_{t-1}, q_t=s_i, o_1, \dots, o_t \mid \lambda)

式中:

  • δt(i)\delta_t(i)(读音 /ˈdɛltə tiː/,δ\delta 是希腊字母 delta,读音 /ˈdɛltə/)表示"前 tt 步观测为 o1o_1 到 oto_t,且第 tt 步处于状态 sis_i"的所有路径中的最大概率。
  • max⁡\max(读音 /mæks/,maximum 的缩写,表示取最大值)对所有可能的前 t−1t-1 步状态序列取最大。

Viterbi 递推:

  1. 初始化:对所有 ii,计算初始 Viterbi 变量和路径指针:

    δ1(i)=πi⋅bi(o1),ψ1(i)=0\delta_1(i) = \pi_i \cdot b_i(o_1), \quad \psi_1(i) = 0

    其中 ψ\psi(读音 /psaɪ/,希腊字母 psi)用于回溯最优路径。

  2. 递推(t=2,…,Tt = 2, \dots, T):

δt(j)=max⁡i[δt−1(i)aij]⋅bj(ot)\delta_t(j) = \max_{i} [\delta_{t-1}(i) a_{ij}] \cdot b_j(o_t)

ψt(j)=arg⁡max⁡i[δt−1(i)aij]\psi_t(j) = \arg\max_i [\delta_{t-1}(i) a_{ij}]

式中:

  • δt(j)\delta_t(j) 是到达状态 jj 的最大概率。
  • ψt(j)\psi_t(j) 记录了"到达 jj 的最优路径中,前一步是哪个状态 ii",用于最后回溯。
  1. 终止:最优路径的终点为

    qT∗=arg⁡max⁡iδT(i)q_T^* = \arg\max_i \delta_T(i)

  2. 回溯:从 t=T−1t = T-1 到 11,逐步回溯得到完整的最优隐藏状态序列:

    qt∗=ψt+1(qt+1∗)q_t^* = \psi_{t+1}(q_{t+1}^*)

Viterbi 算法在语音识别中用于从声学特征序列解码出音素序列,在词性标注中用于从单词序列解码出词性序列。

问题三:学习问题与 Baum-Welch 算法

给定观测序列 OO,估计模型参数 λ=(A,B,π)\lambda=(A,B,\pi) 使 P(O∣λ)P(O \mid \lambda) 最大。这是一个无监督学习问题——隐藏状态是未知的,只有观测可见。

Baum-Welch 算法(读音 /baʊm wɛltʃ ˈælɡərɪðəm/,得名于 Leonard E. Baum 和 Lloyd R. Welch)是 EM 算法(Expectation-Maximization,期望最大化算法,读音 /ɪkˌspekˈteɪʃən ˌmæksɪmɪˈzeɪʃən/)在 HMM 上的特例。

定义两个辅助变量:

  • γt(i)\gamma_t(i)(读音 /ˈɡæmə tiː/,γ\gamma 是希腊字母 gamma,读音 /ˈɡæmə/):给定观测序列 OO,第 tt 步处于状态 sis_i 的后验概率。
  • ξt(i,j)\xi_t(i,j)(读音 /ksaɪ tiː/,ξ\xi 是希腊字母 xi,读音 /ksaɪ/):给定观测序列 OO,第 tt 步处于状态 sis_i 且第 t+1t+1 步处于状态 sjs_j 的后验概率。

它们的计算公式为:

γt(i)=P(qt=si∣O,λ)=αt(i)βt(i)P(O∣λ)\gamma_t(i) = P(q_t = s_i \mid O, \lambda) = \frac{\alpha_t(i)\beta_t(i)}{P(O \mid \lambda)}

ξt(i,j)=αt(i) aij bj(ot+1) βt+1(j)P(O∣λ)\xi_t(i,j) = \frac{\alpha_t(i)\, a_{ij}\, b_j(o_{t+1})\, \beta_{t+1}(j)}{P(O \mid \lambda)}

Baum-Welch 的参数更新公式:

πˉi=γ1(i)\bar{\pi}_i = \gamma_1(i)

aˉij=∑t=1T−1ξt(i,j)∑t=1T−1γt(i)\bar{a}_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)}

bˉj(vk)=∑t=1Tγt(j)⋅1(ot=vk)∑t=1Tγt(j)\bar{b}_j(v_k) = \frac{\sum_{t=1}^{T} \gamma_t(j) \cdot \mathbf{1}(o_t = v_k)}{\sum_{t=1}^{T} \gamma_t(j)}

式中:

  • πˉi\bar{\pi}_i:π\pi(读音 /paɪ/,希腊字母 pi)上方加横线表示"更新后的值",下标 ii(读音 /aɪ/)表示第 ii 个状态。整体表示更新后的初始状态概率,等于第一步处于状态 ii 的后验概率。
  • aˉij\bar{a}_{ij}:aa(读音 /eɪ/)上方加横线表示"更新后的值",下标 ijij(读音 /aɪ dʒeɪ/)表示从状态 ii 到状态 jj。整体表示更新后的转移概率,等于"从 ii 到 jj 的期望次数"除以"处于 ii 的期望次数"。
  • bˉj(vk)\bar{b}_j(v_k):bb(读音 /biː/)上方加横线表示"更新后的值",下标 jj(读音 /dʒeɪ/)表示状态 jj,括号内 vkv_k(读音 /viː keɪ/)表示第 kk 个观测值。整体表示更新后的观测概率,等于"在状态 jj 下产生观测 vkv_k 的期望次数"除以"处于 jj 的期望次数"。
  • 1(ot=vk)\mathbf{1}(o_t = v_k)(读音 /ˌɪndɪˈkeɪtər ˈfʌŋkʃən/,粗体 1 是指示函数,当条件成立时为 1,否则为 0)。

Baum-Welch 交替执行 E 步(用当前参数计算 γ\gamma 和 ξ\xi)和 M 步(用 γ\gamma 和 ξ\xi 更新参数),直到收敛。它保证 P(O∣λ)P(O \mid \lambda) 单调不减,但可能收敛到局部最优。

2.4 HMM 的应用与局限

经典应用:

  • 语音识别:隐藏状态是音素,观测是声学特征。
  • 词性标注(POS Tagging):隐藏状态是词性(名词、动词等),观测是单词。
  • 命名实体识别(NER):隐藏状态是实体标签(B-PER、I-LOC 等),观测是单词。
  • 基因序列分析:隐藏状态是基因区域类型,观测是 DNA 碱基。

局限性:

  • 输出独立性假设太强:实际中观测不仅依赖当前隐藏状态,还可能依赖上下文。
  • 马尔可夫假设限制了长程依赖的建模能力。
  • 这些局限导致 HMM 在很多 NLP 任务中被循环神经网络(RNN)、Transformer 等模型取代,但 HMM 的思想(隐变量 + 动态规划)仍然是概率图模型的基础。

三、马尔可夫决策过程(MDP)

马尔可夫决策过程(Markov Decision Process,简称 MDP,读音 /ˈmɑːrkɒv dɪˈsɪʒən ˈprɒsɛs/)是马尔可夫链的进一步扩展:在状态转移中引入了动作(Action)和奖励(Reward),是强化学习的标准数学框架。GRPO、PPO 等强化学习算法都是在 MDP 框架下定义的。

3.1 MDP 的定义

一个 MDP 由以下五元组定义:

  • 状态空间 SS(读音 /ɛs/,大写):所有可能状态的集合。
  • 动作空间 AA(读音 /eɪ/,大写):智能体可以执行的所有动作的集合。
  • 状态转移函数 P(s′∣s,a)P(s' \mid s,a)(读音 /piː/):在状态 ss 执行动作 aa 后,转移到状态 s′s'(读音 /ɛs praɪm/,表示下一状态)的概率。
  • 奖励函数 R(s,a)R(s,a)(读音 /ɑːr/):在状态 ss 执行动作 aa 后获得的即时奖励(期望奖励)。
  • 折扣因子 γ\gamma(读音 /ˈɡæmə/,希腊字母 gamma,取值 0≤γ≤10 \leq \gamma \leq 1):衡量未来奖励的当前价值。

MDP 与马尔可夫链的关键区别:马尔可夫链的状态转移是被动的(PijP_{ij} 固定),而 MDP 的状态转移依赖于智能体选择的动作(P(s′∣s,a)P(s' \mid s,a))。智能体通过选择动作来影响状态演化的方向,目标是最大化累积奖励。

3.2 策略、回报与价值函数

策略

策略(Policy)π(a∣s)\pi(a \mid s)(读音 /paɪ/)定义了智能体在每个状态下选择每个动作的概率分布:

π(a∣s)=P(at=a∣st=s)\pi(a \mid s) = P(a_t = a \mid s_t = s)

式中:

  • π(a∣s)\pi(a \mid s) 是在状态 ss 下选择动作 aa 的概率。

策略分为两类:

  • 确定性策略(Deterministic Policy):每个状态只对应一个确定的动作,即 a=π(s)a = \pi(s)。
  • 随机性策略(Stochastic Policy):每个状态对应一个动作概率分布,智能体从中采样,即 a∼π(⋅∣s)a \sim \pi(\cdot \mid s)。大语言模型的强化学习中使用的都是随机性策略。

强化学习的目标就是找到一个最优策略 π∗\pi^*,使得累积奖励的期望最大。

回报

从时间步 tt 开始的折扣回报(Discounted Return)定义为:

Gt=rt+γrt+1+γ2rt+2+⋯=∑k=0∞γkrt+kG_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}

式中:

  • GtG_t(读音 /dʒiː tiː/)是从第 tt 步开始的折扣回报。
  • rt+kr_{t+k} 是第 t+kt+k 步的即时奖励。
  • γk\gamma^k 是折扣因子的 kk 次方。
  • Σ\Sigma 从 k=0k=0 到 ∞\infty 表示对未来所有步求和。

γ\gamma 越接近 1,智能体越有远见(重视长期奖励);γ\gamma 越接近 0,越短视(只看眼前奖励)。

状态价值函数

状态价值函数(State Value Function)Vπ(s)V^\pi(s)(读音 /viː/):在遵循策略 π\pi 的前提下,从状态 ss 出发能获得的期望折扣回报。

Vπ(s)=Eπ[Gt∣st=s]V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]

式中:

  • Eπ\mathbb{E}_\pi:E\mathbb{E}(读音 /iː/,数学期望符号,expectation 的缩写)下标 π\pi(读音 /paɪ/,希腊字母 pi,表示策略),整体表示在策略 π\pi 诱导的分布下求期望。

Vπ(s)V^\pi(s) 回答的问题是:"如果我现在在状态 ss,并且一直按策略 π\pi 行动,平均能拿多少分?"

动作价值函数

动作价值函数(Action Value Function)Qπ(s,a)Q^\pi(s,a)(读音 /kjuː/):在状态 ss 下先执行动作 aa,之后遵循策略 π\pi,能获得的期望折扣回报。

Qπ(s,a)=Eπ[Gt∣st=s,at=a]Q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid s_t = s, a_t = a]

Qπ(s,a)Q^\pi(s,a) 回答的问题是:"如果我现在在状态 ss,先强制选动作 aa,之后按策略 π\pi 行动,平均能拿多少分?"QQ 函数比 VV 函数多了一个动作维度,因此可以直接用于选择动作(选 QQ 值最大的动作)。

优势函数

优势函数(Advantage Function)Aπ(s,a)A^\pi(s,a)(读音 /eɪ/):动作 aa 比"按策略 π\pi 随机选一个动作"平均好多少。

Aπ(s,a)=Qπ(s,a)−Vπ(s)A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)

优势函数是策略梯度方法(PPO、GRPO 等)的核心量:A>0A > 0 的动作应该增加概率,A<0A < 0 的动作应该降低概率。

3.3 贝尔曼方程

贝尔曼方程(Bellman Equation,读音 /ˈbɛlmən ɪˈkweɪʒən/,得名于数学家理查德·贝尔曼,Richard Bellman)是 MDP 理论的基石。它将价值函数分解为"即时奖励 + 下一状态价值"的递归形式。

贝尔曼期望方程

对于任意策略 π\pi,状态价值函数满足:

Vπ(s)=∑aπ(a∣s)[R(s,a)+γ∑s′P(s′∣s,a)Vπ(s′)]V^\pi(s) = \sum_{a} \pi(a \mid s) \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s') \right]

式中:

  • ∑a\sum_a 对所有可能的动作 aa 求和(按策略 π\pi 加权)。
  • 方括号内是"执行动作 aa 后的即时奖励 R(s,a)R(s,a)"加上"折扣后的下一状态期望价值"。

该式的含义是:状态 ss 的价值等于"按策略选一个动作,拿到即时奖励,然后下一状态的价值按转移概率加权求和"。

类似地,动作价值函数的贝尔曼期望方程:

Qπ(s,a)=R(s,a)+γ∑s′P(s′∣s,a)∑a′π(a′∣s′)Qπ(s′,a′)Q^\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) \sum_{a'} \pi(a' \mid s') Q^\pi(s',a')

式中:

  • a′a'(读音 /eɪ praɪm/,表示下一状态的动作)是下一状态 s′s' 下选择的动作。

贝尔曼最优方程

最优策略 π∗\pi^*(读音 /paɪ stɑːr/)是使所有状态的价值都最大的策略。最优价值函数记为 V∗(s)=max⁡πVπ(s)V^*(s) = \max_\pi V^\pi(s) 和 Q∗(s,a)=max⁡πQπ(s,a)Q^*(s,a) = \max_\pi Q^\pi(s,a)。

最优价值函数满足贝尔曼最优方程:

V∗(s)=max⁡a[R(s,a)+γ∑s′P(s′∣s,a)V∗(s′)]V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s') \right]

式中:

  • max⁡a\max_a 表示对所有动作 aa 取最大值。

该式的含义是:最优策略下,状态 ss 的价值等于"选择能使即时奖励加下一状态价值最大的那个动作"。

Q∗(s,a)=R(s,a)+γ∑s′P(s′∣s,a)V∗(s′)Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s')

有了 Q∗Q^*,最优策略就是贪婪选择:在状态 ss 下选择使 Q∗(s,a)Q^*(s,a) 最大的动作 aa。

3.4 动态规划求解 MDP

当 MDP 的模型(转移函数 PP 和奖励函数 RR)完全已知时,可以用动态规划(Dynamic Programming,简称 DP,读音 /daɪˈnæmɪk ˈproʊɡræmɪŋ/)精确求解。

策略迭代

策略迭代(Policy Iteration,读音 /ˈpɒləsi ˌɪtəˈreɪʃən/)交替执行两个步骤:

  1. 策略评估(Policy Evaluation):给定当前策略 π\pi,计算 VπV^\pi。通过迭代贝尔曼期望方程直到收敛:

    Vk+1(s)=∑aπ(a∣s)[R(s,a)+γ∑s′P(s′∣s,a)Vk(s′)]V_{k+1}(s) = \sum_{a} \pi(a \mid s)\left[R(s,a) + \gamma\sum_{s'} P(s' \mid s,a) V_k(s')\right]

  2. 策略提升(Policy Improvement):用 VπV^\pi 计算 QπQ^\pi,然后贪婪地更新策略:

    πnew(s)=arg⁡max⁡aQπ(s,a)\pi_{new}(s) = \arg\max_a Q^\pi(s,a)

重复"评估→提升"直到策略不再变化。策略迭代保证收敛到最优策略,但每次策略评估都需要迭代到收敛,计算量大。

值迭代

值迭代(Value Iteration,读音 /ˈvæljuː ˌɪtəˈreɪʃən/)将策略评估和提升合并为一步,直接迭代贝尔曼最优方程:

Vk+1(s)=max⁡a[R(s,a)+γ∑s′P(s′∣s,a)Vk(s′)]V_{k+1}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V_k(s') \right]

值迭代不需要显式维护策略,每次迭代直接更新 VV。收敛后,通过下式提取最优策略:

π(s)=arg⁡max⁡a[R(s,a)+γ∑s′P(s′∣s,a)V(s′)]\pi(s) = \arg\max_a \left[ R(s,a) + \gamma\sum_{s'} P(s' \mid s,a) V(s') \right]

值迭代通常比策略迭代更快,因为不需要每次都评估到收敛。

3.5 MDP 与强化学习算法的关系

动态规划要求 MDP 模型完全已知(PP 和 RR 已知),但在很多实际问题中(包括 LLM 训练),我们不知道环境的转移函数和奖励函数的解析形式。这时就需要强化学习(Reinforcement Learning):智能体通过与环境交互采样,用样本估计价值函数或直接优化策略。

方法 是否需要模型 典型算法
动态规划(DP) 需要(PP 和 RR 已知) 策略迭代、值迭代
基于价值的 RL 不需要,用样本估计 QQ Q-Learning、DQN
基于策略的 RL 不需要,直接优化策略 REINFORCE、PPO、GRPO
Actor-Critic 不需要,同时学策略和价值 A2C、PPO(带 Critic)

GRPO 是基于策略的 RL 方法,它在 MDP 框架下运行,但做了一个关键简化:用组内相对优势代替价值网络估计的优势函数(详见 GRPO 教程第二章)。


四、部分可观测马尔可夫决策过程(POMDP)

部分可观测马尔可夫决策过程(Partially Observable Markov Decision Process,简称 POMDP,读音 /ˌpiː oʊ em diː ˈpiː/)是 MDP 的进一步扩展:智能体无法直接观测到完整的状态 sts_t,只能观测到一个与状态相关的观测(Observation)oto_t。POMDP 是更贴近现实的决策模型,因为在大多数真实场景中,智能体只能感知环境的一部分。

4.1 POMDP 的定义

一个 POMDP 由以下七元组定义:

  • 状态空间 SS(读音 /ɛs/):所有可能的真实状态的集合(智能体不可直接观测)。
  • 动作空间 AA(读音 /eɪ/):所有可能动作的集合。
  • 状态转移函数 P(s′∣s,a)P(s' \mid s,a)(读音 /piː/):在状态 ss 执行动作 aa 后转移到 s′s' 的概率。
  • 奖励函数 R(s,a)R(s,a)(读音 /ɑːr/):在状态 ss 执行动作 aa 后获得的奖励。
  • 观测空间 OO(读音 /oʊ/,大写):所有可能观测的集合。
  • 观测函数 Z(o∣s′,a)Z(o \mid s',a)(读音 /zɛd/,ZZ 是 observation 的常用符号,因为 OO 已被观测空间占用):在新状态 s′s' 下(执行动作 aa 后)观测到 oo 的概率。
  • 折扣因子 γ\gamma(读音 /ˈɡæmə/):未来奖励的折扣率。

POMDP 与 MDP 的关键区别:MDP 中智能体能直接看到状态 sts_t;POMDP 中智能体只能看到观测 oto_t,而观测可能是状态的噪声、部分或模糊版本。

4.2 信念状态

在 POMDP 中,由于无法直接观测状态,智能体需要维护一个对当前状态的概率分布,称为信念状态(Belief State,读音 /bɪˈliːf steɪt/):

b(s)=P(st=s∣o1,a1,o2,a2,…,ot)b(s) = P(s_t = s \mid o_1, a_1, o_2, a_2, \dots, o_t)

式中:

  • b(s)b(s)(读音 /biː/)是信念状态中状态 ss 的概率。
  • 条件部分是到目前为止的所有观测和动作历史。

信念状态 bb 是一个概率分布,满足 ∑s∈Sb(s)=1\sum_{s \in S} b(s) = 1。

信念状态可以通过贝叶斯更新(Bayesian Update,读音 /ˈbeɪziən ʌpˈdeɪt/)递推计算。当智能体执行动作 aa 并观测到 o′o' 后,新的信念状态为:

b′(s′)=η⋅Z(o′∣s′,a)∑s∈Sb(s)P(s′∣s,a)b'(s') = \eta \cdot Z(o' \mid s',a) \sum_{s \in S} b(s) P(s' \mid s,a)

式中:

  • η\eta(读音 /ˈiːtə/,希腊字母 eta,读音 /ˈiːtə/,是归一化常数,确保 b′b' 的总和为 1)。
  • Z(o′∣s′,a)Z(o' \mid s',a) 是在状态 s′s' 下观测到 o′o' 的概率。
  • ∑sb(s)P(s′∣s,a)\sum_s b(s)P(s' \mid s,a) 是"在旧信念下执行动作 aa 后到达 s′s' 的预测概率"。

该式的含义是:先根据动作预测下一状态的分布,再根据新观测用贝叶斯公式修正。

关键洞察: 信念状态 bb 满足马尔可夫性质!因为 b′b' 只依赖于 bb、aa 和 o′o',不依赖于更早的历史。因此,POMDP 可以转化为一个在信念状态空间上的连续状态 MDP——这就是 POMDP 求解的基本思路。但信念状态空间是连续的(概率单纯形),求解比普通 MDP 困难得多。

4.3 POMDP 与 LLM Agent 的联系

LLM Agent(大语言模型智能体)的决策过程本质上就是一个 POMDP:

  • 真实状态 ss:环境的完整状态(比如用户的真实意图、数据库的完整内容、代码执行环境的完整状态)。
  • 观测 oo:LLM 能看到的信息(用户输入、工具返回结果、对话历史)。这些观测通常是不完整的。
  • 动作 aa:LLM 可以执行的操作(生成文本、调用工具、查询数据库、执行代码)。
  • 信念状态 bb:LLM 对当前环境状态的概率估计,体现在对话上下文和内部表示中。

在 Base AI 的场景中,CodeAct(代码执行范式)就是一个典型的 POMDP:模型无法直接"看到"多维表格的完整内部状态,只能通过 SDK 查询获得部分观测,然后通过生成代码(动作)来操作环境。Auto-Thinking 中的模式选择(DIRECT/THINK_SHORT/REPLAN)本质上是在信念不确定性高时选择更深入的思考动作。


五、马尔可夫链蒙特卡洛(MCMC)

马尔可夫链蒙特卡洛(Markov Chain Monte Carlo,简称 MCMC,读音 /ˈmɑːrkɒv tʃeɪn ˌmɒnti ˈkɑːrloʊ/)是一类通过构造一个平稳分布等于目标分布的马尔可夫链,来从复杂概率分布中采样的方法。MCMC 是贝叶斯推断、统计物理、机器学习中最重要的采样方法之一。

5.1 为什么需要 MCMC

在概率推断中,我们常常需要从一个复杂的目标分布 π(x)\pi(x)(读音 /paɪ/,这里表示目标概率分布,xx 是随机变量)中采样,或者计算关于 π\pi 的期望:

Eπ[f(x)]=∫f(x)π(x)dx\mathbb{E}_{\pi}[f(x)] = \int f(x) \pi(x) dx

当 π(x)\pi(x) 是高维、复杂、非标准化的分布时(比如贝叶斯后验分布),直接采样或数值积分都不可行。蒙特卡洛方法(Monte Carlo,读音 /ˌmɒnti ˈkɑːrloʊ/,得名于摩纳哥的赌城,因为随机采样与赌博类似)用样本平均来近似期望:

Eπ[f(x)]≈1N∑i=1Nf(xi),xi∼π(x)\mathbb{E}_{\pi}[f(x)] \approx \frac{1}{N} \sum_{i=1}^{N} f(x_i), \quad x_i \sim \pi(x)

但问题是:如何从复杂的 π(x)\pi(x) 中生成样本 xix_i?MCMC 的回答是:构造一个马尔可夫链,使其平稳分布恰好是 π(x)\pi(x),然后运行这个马尔可夫链来采集样本。

5.2 MCMC 的基本原理

MCMC 的理论基础是第一章讲的遍历定理:对于一个遍历(不可约、非周期、常返)的马尔可夫链,从任意初始状态出发,经过足够多步后,状态分布会收敛到平稳分布 π\pi。而且,时间平均等于空间平均(遍历性):

lim⁡T→∞1T∑t=1Tf(xt)=Eπ[f(x)]\lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} f(x_t) = \mathbb{E}_{\pi}[f(x)]

式中:

  • xtx_t 是马尔可夫链第 tt 步的状态。
  • TT 是总步数。

因此,MCMC 的核心任务就是:设计一个转移核 P(x→x′)P(x \to x'),使得其平稳分布为 π(x)\pi(x)。最常用的设计原则是细致平衡(Detailed Balance):

π(x)P(x→x′)=π(x′)P(x′→x)\pi(x) P(x \to x') = \pi(x') P(x' \to x)

式中:

  • π(x)P(x→x′)\pi(x)P(x \to x') 是从 xx 流向 x′x' 的概率流。
  • π(x′)P(x′→x)\pi(x')P(x' \to x) 是反向流量。

如果细致平衡成立,那么 π\pi 一定是平稳分布。

5.3 Metropolis-Hastings 算法

Metropolis-Hastings 算法(读音 /ˌmɛtrəˈpɒlɪs ˈheɪstɪŋz ˈælɡərɪðəm/,得名于 Nicholas Metropolis 和 W.K. Hastings)是最通用的 MCMC 方法。它使用一个提议分布(Proposal Distribution)Q(x′∣x)Q(x' \mid x)(读音 /kjuː/)来生成候选样本,然后用一个接受概率(Acceptance Probability)来决定是否接受候选。

算法步骤:

  1. 初始化:选择初始状态 x0x_0。
  2. 提议:从提议分布 Q(x′∣xt)Q(x' \mid x_t) 中采样一个候选状态 x′x'。
  3. 计算接受概率:

α(xt,x′)=min⁡(1,π(x′)Q(xt∣x′)π(xt)Q(x′∣xt))\alpha(x_t, x') = \min\left(1, \frac{\pi(x') Q(x_t \mid x')}{\pi(x_t) Q(x' \mid x_t)}\right)

式中:

  • α(xt,x′)\alpha(x_t, x')(读音 /ˈælfə/)是接受概率。
  • min⁡(1,⋅)\min(1, \cdot)(民,取最小值)确保接受概率不超过 1。
  • π(x′)/π(xt)\pi(x')/\pi(x_t) 是目标分布的比值(如果 π\pi 是非标准化的,归一化常数会约掉,这是 MCMC 的一大优势——不需要知道归一化常数!)。
  • Q(xt∣x′)/Q(x′∣xt)Q(x_t \mid x')/Q(x' \mid x_t) 是提议分布的反向比值,用于修正提议分布的不对称性。
  1. 接受或拒绝:以概率 α\alpha 接受 x′x'(令 xt+1=x′x_{t+1} = x'),否则拒绝(令 xt+1=xtx_{t+1} = x_t)。
  2. 重复:回到步骤 2,直到收敛。

为什么这样设计满足细致平衡? 可以验证:π(x)P(x→x′)=π(x′)P(x′→x)\pi(x)P(x \to x') = \pi(x')P(x' \to x),其中 P(x→x′)=Q(x′∣x)⋅α(x,x′)P(x \to x') = Q(x' \mid x) \cdot \alpha(x,x')。因此平稳分布就是 π\pi。

Metropolis 算法是 Metropolis-Hastings 的特例:当提议分布对称时(Q(x′∣x)=Q(x∣x′)Q(x' \mid x) = Q(x \mid x')),接受概率简化为 α=min⁡(1,π(x′)/π(xt))\alpha = \min(1, \pi(x')/\pi(x_t))。

5.4 Gibbs 采样

Gibbs 采样(读音 /ɡɪbz ˈsɑːmplɪŋ/,得名于物理学家 Josiah Willard Gibbs)是 Metropolis-Hastings 的一个特例,专门用于高维分布。它的核心思想是:每次只更新一个维度,其他维度保持不变,用该维度的条件分布作为提议分布。

对于 DD(读音 /diː/,表示维度数)维随机变量 x=(x1,x2,…,xD)x = (x_1, x_2, \dots, x_D),Gibbs 采样的步骤:

  1. 初始化:x(0)=(x1(0),…,xD(0))x^{(0)} = (x_1^{(0)}, \dots, x_D^{(0)})。
  2. 对每个维度 d=1,2,…,Dd = 1, 2, \dots, D:

xd(t+1)∼π(xd∣x1(t+1),…,xd−1(t+1),xd+1(t),…,xD(t))x_d^{(t+1)} \sim \pi(x_d \mid x_1^{(t+1)}, \dots, x_{d-1}^{(t+1)}, x_{d+1}^{(t)}, \dots, x_D^{(t)})

式中:

  • π(xd∣其他维度)\pi(x_d \mid \text{其他维度})(读音 /paɪ/)是第 dd 维的条件分布(Conditional Distribution),即在其他所有维度固定的情况下,第 dd 维的概率分布。
  • 上标 (t)(t) 和 (t+1)(t+1) 表示第 tt 步和第 t+1t+1 步的值——已经更新过的维度用新值,未更新的维度用旧值。

Gibbs 采样的接受概率恒为 1(因为条件分布作为提议分布恰好满足细致平衡),因此不需要拒绝步骤。但它要求能从条件分布中高效采样——这在某些模型中可行(如贝叶斯网络、主题模型 LDA),在另一些模型中不可行。

5.5 MCMC 的实践要点

  • 烧入期(Burn-in Period,读音 /bɜːrn ɪn ˈpɪəriəd/):马尔可夫链从初始状态到收敛到平稳分布需要一段时间,这段时间的样本应该丢弃。通常丢弃前 10%–50% 的样本。
  • 自相关性(Autocorrelation):相邻样本是相关的(因为是马尔可夫链),不是独立样本。可以通过稀疏采样(Thinning,每隔 kk 步取一个样本)来降低相关性,但这会降低样本效率。
  • 收敛诊断(Convergence Diagnosis):判断链是否收敛的方法,包括 Gelman-Rubin 统计量(多条链对比)、自相关图、迹图(Trace Plot)等。
  • 混合速度(Mixing):马尔可夫链在状态空间中探索的速度。提议分布太窄会导致混合慢(局部探索),太宽会导致接受率低。需要调参。

5.6 MCMC 在机器学习中的应用

  • 贝叶斯推断:从后验分布 P(θ∣D)P(\theta \mid D)(读音 /paɪ/,θ\theta 是模型参数,DD 是数据)中采样,用于贝叶斯神经网络、高斯过程、主题模型(LDA)等。
  • 扩散模型(Diffusion Models):去噪扩散概率模型(DDPM)的采样过程本质上是一个马尔可夫链——从噪声开始,逐步去噪生成数据。虽然不是标准的 MCMC(转移核是学习出来的),但马尔可夫链的思想是核心。
  • 能量模型(Energy-Based Models):用 MCMC(如 Langevin 动力学,一种连续状态的 MCMC)从能量模型定义的分布中采样。
  • 马尔可夫链 LLM:近期研究探索用马尔可夫链替代自回归生成,通过迭代修正来生成文本。

六、Markov 家族算法关系图谱与总结

6.1 家族关系图谱

所有 Markov 家族算法都共享马尔可夫性质,但在"是否有动作""是否可观测""是否用于采样"等维度上各有扩展。下图展示了它们之间的关系:

马尔可夫性质Markov Property未来只依赖现在马尔可夫链Markov Chain状态随机转移马尔可夫决策过程MDP状态+动作+奖励隐马尔可夫模型HMM状态隐藏+观测部分可观测MDPPOMDP状态部分可观测马尔可夫链蒙特卡洛MCMC构造链来采样Metropolis-HastingsGibbs 采样强化学习PPO / GRPO /Q-LearningLLM AgentCodeAct /Auto-Thinking
查看图示结构
graph TD
    MP["马尔可夫性质<br/>Markov Property<br/>未来只依赖现在"] --> MC["马尔可夫链<br/>Markov Chain<br/>状态随机转移"]
    MP --> MDP["马尔可夫决策过程<br/>MDP<br/>状态+动作+奖励"]
    MC --> HMM["隐马尔可夫模型<br/>HMM<br/>状态隐藏+观测"]
    MDP --> POMDP["部分可观测 MDP<br/>POMDP<br/>状态部分可观测"]
    MC --> MCMC["马尔可夫链蒙特卡洛<br/>MCMC<br/>构造链来采样"]
    MCMC --> MH["Metropolis-Hastings"]
    MCMC --> Gibbs["Gibbs 采样"]
    MDP --> RL["强化学习<br/>PPO / GRPO / Q-Learning"]
    POMDP --> Agent["LLM Agent<br/>CodeAct / Auto-Thinking"]

6.2 各算法的核心对比

算法 是否有动作 状态是否可观测 核心目标 典型应用
马尔可夫链 无 完全可观测 建模状态随机演化 排队论、随机过程
HMM 无 隐藏(部分可观测) 从观测推断隐藏状态 语音识别、词性标注
MDP 有 完全可观测 找最优策略最大化奖励 强化学习理论框架
POMDP 有 部分可观测 在不确定下找最优策略 机器人、LLM Agent
MCMC 无(提议动作) 完全可观测 从复杂分布中采样 贝叶斯推断、扩散模型

6.3 在 LLM/RL 中的交织

在大语言模型的训练和推理中,Markov 家族算法以多种方式交织出现:

  1. RL 训练框架是 MDP:PPO、GRPO、DAPO、VAPO 等算法都在 MDP 框架下定义。状态是 prompt + 已生成的 token,动作是下一个 token,奖励是 verifier/judge 的评分。GRPO 的核心创新是用组内相对优势代替 MDP 中的价值网络。
  2. LLM Agent 是 POMDP:模型无法直接观测环境的完整状态,只能通过工具调用获得部分观测,需要维护信念状态(对话上下文)。
  3. 扩散模型采样是马尔可夫链:DDPM 的前向加噪和反向去噪都是马尔可夫链过程。
  4. 序列建模的马尔可夫假设:传统 n-gram 语言模型是马尔可夫链(下一个词只依赖前 n-1 个词)。Transformer 虽然理论上可以建模任意长程依赖,但在实践中也常被视为"近似马尔可夫"的生成过程。
  5. HMM 与序列标注:在 NLP 的序列标注任务(词性标注、命名实体识别)中,HMM 曾是主流方法,现在被 BiLSTM-CRF、Transformer 等取代,但其"隐状态 + 观测"的思想仍然是概率图模型的基础。

一句话总结: 马尔可夫性质是整个家族的共同基因:未来只依赖现在。马尔可夫链是最纯粹的形式;HMM 加了"隐藏状态";MDP 加了"动作和奖励";POMDP 加了"部分可观测";MCMC 反过来用马尔可夫链来做采样。在 LLM 时代,MDP 是 RL 训练的理论底座,POMDP 是 Agent 决策的真实模型,而马尔可夫链的思想则渗透在扩散模型和序列生成的方方面面。


参考资料

  • Sutton & Barto,《Reinforcement Learning: An Introduction》— MDP、DP、RL 的经典教材
  • Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition" — HMM 的经典综述
  • Andrieu et al., "An Introduction to MCMC for Machine Learning" — MCMC 的机器学习视角综述