Markov 家族算法系统教程:从马尔可夫性质到 MDP、HMM 与 MCMC
本文系统整理马尔可夫性质、马尔可夫链、隐马尔可夫模型(HMM)、马尔可夫决策过程(MDP)、部分可观测 MDP(POMDP)、马尔可夫链蒙特卡洛(MCMC)的核心概念、公式推导与相互关系。每个数学符号首次出现时均标注读音和定义。
目录
- 一、马尔可夫性质与马尔可夫链
- 二、隐马尔可夫模型(HMM)
- 三、马尔可夫决策过程(MDP)
- 四、部分可观测马尔可夫决策过程(POMDP)
- 五、马尔可夫链蒙特卡洛(MCMC)
- 六、Markov 家族算法关系图谱与总结
一、马尔可夫性质与马尔可夫链
"Markov"(马尔可夫,读音 /ˈmɑːrkɒf/,得名于俄罗斯数学家安德烈·马尔可夫,Andrey Andreyevich Markov,1856—1922)这个名字在机器学习、强化学习、自然语言处理、概率推断中反复出现。所有以"Markov"命名的算法,都共享一个最核心的假设——马尔可夫性质(Markov Property)。
1.1 马尔可夫性质
马尔可夫性质(Markov Property,读音 /ˈmɑːrkɒv ˈprɒpəti/)的定义是:给定当前状态,未来与过去条件独立。用数学语言表达:
式中:
- (读音 /piː/,probability 的缩写,表示概率)表示概率。
- (读音 /ɛs tiː/,表示第 个时间步的状态, 是 state 的缩写)表示第 步的状态。
- 表示第 步的状态。
- (读音 /ɛs ˈzɪəroʊ/)表示初始状态。
- 竖线 表示"给定"或"条件于"(conditional on)。
- 省略号表示更早的历史状态。
该式的含义是:在已知完整历史( 到 )的条件下,下一状态 的概率分布,等于只知道当前状态 时的概率分布。换句话说,未来只依赖于现在,不依赖于过去。当前状态 已经包含了预测未来所需的全部信息,更早的历史是冗余的。
直觉理解: 想象一个棋盘游戏,棋子下一步能走到哪里,只取决于它现在在哪个格子,不取决于它之前是怎么走到这个格子的。这就是马尔可夫性质——"现在"已经是"过去"的充分统计量。
需要注意的是,马尔可夫性质是一个建模假设,不是客观真理。现实中很多过程并不严格满足马尔可夫性质(比如股票价格不仅依赖今天的价格,还依赖历史趋势),但我们常常通过"扩充状态定义"来让它近似满足。例如在强化学习中,如果原始观察不满足马尔可夫性,可以把最近几帧的观察拼接起来作为状态,这就是"帧堆叠"(frame stacking)技术。
1.2 离散时间马尔可夫链
离散时间马尔可夫链(Discrete-Time Markov Chain,简称 DTMC,读音 /dɪˈskriːt taɪm ˈmɑːrkɒv tʃeɪn/)是满足马尔可夫性质的、状态在离散时间步上演化的随机过程。它是整个 Markov 家族中最简单、最基础的模型。
定义
一个离散时间马尔可夫链由以下要素定义:
-
状态空间 (读音 /ɛs/,大写,表示所有可能状态的集合):系统可以处于的所有状态的集合。可以是有限的(如天气状态 {晴, 阴, 雨}),也可以是无限的(如整数集)。
-
初始分布 (读音 /paɪ ˈzɪəroʊ/,希腊字母 pi,表示初始时刻各状态的概率分布): 时系统处于各状态的概率,定义为:
其中 表示某个具体状态, 表示初始时刻的状态随机变量。
-
状态转移矩阵 (读音 /piː/,大写,表示状态转移概率矩阵):一个 的方阵(行数和列数都等于状态数),用来完整描述马尔可夫链的转移规则。矩阵中每个元素 (读音 /piː aɪ dʒeɪ/)表示"从状态 出发,下一步转移到状态 "的概率。
状态转移矩阵 的精确定义为:
式中:
- 是矩阵第 行第 列的元素。行索引 是"当前状态"(从哪来),列索引 是"下一状态"(到哪去)。这个方向很重要,记反了会导致整个计算错误。
- (读音 /ˌfɔːr ˈɔːl/,全称 for all,表示"对于所有的")是全称量词。
- 表示 和 都是状态空间 中的状态。
用一个具体例子理解矩阵结构:
假设状态空间 (3 个状态),那么状态转移矩阵是一个 的方阵:
- 第一行():今天是晴天时,明天分别是晴、阴、雨的概率。
- 第二行():今天是阴天时,明天分别是晴、阴、雨的概率。
- 第三行():今天是雨天时,明天分别是晴、阴、雨的概率。
- 第一列():从任意状态转移到晴天的概率(按行分别看)。
代入具体数值:
读作:今天晴→明天晴 70%、阴 20%、雨 10%;今天阴→明天晴 30%、阴 40%、雨 30%;今天雨→明天晴 20%、阴 40%、雨 40%。
状态转移矩阵有两个基本性质:
- 非负性:,对所有 成立。概率不能为负。
- 行和为 1:,对所有 成立。为什么是行和为 1 而不是列和为 1? 因为每一行代表"从同一个当前状态 出发",下一步必然要转移到某个状态(包括留在原状态),所以所有可能的下一状态的概率加起来必须等于 1。例如上面矩阵的第一行:。而列不要求和为 1,因为不同行到达同一列的概率之间没有约束关系。
齐次与非齐次马尔可夫链
如果转移概率 不随时间 变化(即 在所有时间步都相同),则称为齐次马尔可夫链(Time-Homogeneous Markov Chain,读音 /taɪm ˌhoʊmoʊˈdʒiːniəs/)。本文讨论的默认都是齐次马尔可夫链。
如果转移概率随时间变化( 在不同时间步有不同的值),则称为非齐次马尔可夫链(Time-Inhomogeneous Markov Chain)。
n 步转移概率
从状态 出发,经过 (读音 /ɛn/,表示步数,正整数)步后到达状态 的概率,称为 步转移概率,记为 (读音 /piː aɪ dʒeɪ/)。
一个重要的结论是: 步转移矩阵等于一步转移矩阵的 次方:
式中:
- (读音 /piː/)是 步转移矩阵。
- (读音 /piː/)表示一步转移矩阵 自乘 次。
这个结论来自查普曼-科尔莫戈罗夫方程(Chapman-Kolmogorov Equation,读音 /ˈtʃæpmən kɒlˈmɒɡərɒf ɪˈkweɪʒən/):
式中:
- 是从 经过 步到 的概率。
- 求和符号 (读音 /ˈsɪɡmə/,希腊字母 sigma 的大写,表示求和)对所有中间状态 求和。
- 是从 经过 步到中间状态 的概率。
- 是从 经过 步到 的概率。
该式的含义是:从 到 经过 步,可以分解为"先从 经过 步到某个中间状态 ,再从 经过 步到 ",对所有可能的中间状态 求和。这正是矩阵乘法的定义。
查普曼-科尔莫戈罗夫方程的完整证明:
第一步:从定义出发。 步转移概率的定义是:
式中: 表示第 步的状态, 表示初始状态。该式的含义是:已知初始状态为 ,经过 步后状态为 的概率。
第二步:用全概率公式引入中间状态。 在第 步时,系统一定处于状态空间中的某个状态 。根据全概率公式(Law of Total Probability,读音 /lɔː əv ˈtoʊtl ˌprɒbəˈbɪləti/),可以对所有可能的中间状态 做分解:
全概率公式是什么: 全概率公式的基本思想是:如果一组事件 构成样本空间的一个划分(partition,读音 /pɑːrˈtɪʃən/,即这些事件两两互斥且它们的并集覆盖所有可能),那么任意事件 的概率可以拆成"在每个 发生时 发生的概率"之和:
式中: (读音 /ɪnˈtɜːrˈsekʃən/,交集符号,表示"且")表示两个事件同时发生; 是在 发生时 发生的条件概率; 是 发生的概率。直觉理解:要算 发生的总概率,就把"每条可能路径上 发生的概率"加起来。
这里为什么能用: 在第 步,系统的状态 只能取状态空间 中的一个值,而且必然取其中一个值。因此事件 (对所有 )构成了一个划分——它们两两互斥(不能同时处于两个状态)且覆盖全部可能(必然处于某个状态)。所以可以用全概率公式对所有中间状态 求和。
式中: 逗号 表示"且"(同时发生),即 和 同时成立;求和对所有可能的中间状态 进行。全概率公式的直觉是:"从 i 到 j 走 m+n 步"这件事,必然经过第 m 步的某个状态 k,把所有可能的 k 的路径概率加起来就是总概率。
第三步:用条件概率乘法法则展开。 根据条件概率的乘法法则 ,上式中的联合条件概率可以拆成两步:
式中: 第一项是"已知第 m 步在 k 且初始在 i,第 m+n 步到 j"的概率;第二项是"已知初始在 i,第 m 步到 k"的概率。
第四步:用马尔可夫性简化第一项。 马尔可夫性告诉我们:下一个状态只依赖于当前状态,与更早的历史无关。所以:
式中: 等式左边条件里有 (历史),右边去掉了它——因为马尔可夫性说历史不影响未来,给定当前状态 就够了。而右边恰好就是从 经过 步到 的概率 (因为齐次链中转移概率不随时间变,第 m 步到第 m+n 步就是 n 步)。
第五步:识别第二项。 就是从 经过 步到 的概率,即 。
第六步:汇总得到结论。 把以上各步代回:
为什么这等于矩阵乘法 :
回顾矩阵乘法的元素定义:对于两个矩阵 和 ,它们的乘积 的第 行第 列元素为:
式中: 是矩阵 的第 行第 列元素; 是矩阵 的第 行第 列元素;求和对所有中间索引 进行。直觉理解:结果矩阵的每个元素,等于"左边矩阵的第 i 行"与"右边矩阵的第 j 列"对应位置相乘再相加。
现在把查普曼-科尔莫戈罗夫方程的右边与矩阵乘法定义对比:
式中: 把 看作矩阵 ,把 看作矩阵 ,则 就是 ( 的第 行第 列), 就是 ( 的第 行第 列)。两者的结构与矩阵乘法的元素定义完全一致。
因为这个等式对所有 都成立(不只是某一个格子),所以整个矩阵相等:
用一个具体例子验证: 假设状态空间只有 2 个状态 ,则:
这恰好就是"从 1 出发,先经 m 步到中间状态 1 或 2,再经 n 步到 2"的所有路径概率之和,与查普曼-科尔莫戈罗夫方程完全一致。
进而,令 反复应用,得到 (一步转移矩阵自乘 n 次)。
证毕。
状态转移图示例
以一个简单的天气模型为例。状态空间 ,状态转移矩阵为:
| 从 \ 到 | 晴 | 阴 | 雨 |
|---|---|---|---|
| 晴 | 0.7 | 0.2 | 0.1 |
| 阴 | 0.3 | 0.4 | 0.3 |
| 雨 | 0.2 | 0.4 | 0.4 |
这个矩阵的含义是:如果今天是晴天,明天有 70% 概率还是晴天,20% 概率阴天,10% 概率雨天。每一行的和都是 1。
查看图示结构
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 的概率永远不回来。瞬态只会被访问有限次。
周期与非周期
状态 的周期(Period,读音 /ˈpɪəriəd/) 定义为所有满足 的 的最大公约数。如果 ,称该状态为非周期(Aperiodic,读音 /ˌeɪpɪriˈɒdɪk/)的;如果 ,称为周期(Periodic)的。
逐部分拆解这个定义:
-
是什么? 这是 步转移概率的特例:从状态 出发,经过 步后回到状态 的概率。 意味着"走 步是有可能回到 的"。
-
"所有满足 的 "是什么? 把所有"能回到 "的步数收集起来,形成一个集合。比如:如果走 2 步能回来、走 4 步能回来、走 6 步能回来……这个集合就是 。
-
最大公约数(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。
把三部分合起来: 周期 就是"所有能回到 的步数"的最大公约数。它衡量的是:回到 这件事,是否存在一个固定的"节奏"或"间隔"。
具体例子:
-
例 1(周期为 2): 假设状态 只能在偶数步回到自身——走 2 步能回、4 步能回、6 步能回,但走 1、3、5 等奇数步不可能回来。那么"能回来的步数集合"是 ,gcd = 2,所以 。直觉:这个状态有"隔一步才能回来"的节奏。
-
例 2(非周期,周期为 1): 假设状态 走 2 步能回、走 3 步也能回。那么"能回来的步数集合"包含 2 和 3,gcd(2, 3) = 1,所以 。一旦 2 和 3 都能回来,那么 4=2+2、5=2+3、6=3+3……所有更大的数都能回来,gcd 仍然是 1。直觉:这个状态没有固定节奏,随时可能回来。
-
例 3(周期为 3): 假设状态 只能在 3 的倍数步回到自身——3 步、6 步、9 步……集合是 ,gcd = 3,所以 。
为什么周期重要? 马尔可夫链收敛到平稳分布的一个关键条件是不可约 + 非周期(加上正常返)。如果链是周期的(),状态分布会在不同的"相位"之间循环振荡,不会收敛到一个稳定分布。比如周期为 2 的链,奇数步和偶数步的分布可能不同,永远在两个分布之间来回跳。
吸收态
吸收态(Absorbing State,读音 /əbˈzɔːrbɪŋ steɪt/):满足 的状态。一旦进入吸收态,就永远不会离开。例如"游戏结束"状态就是吸收态。
不可约与遍历
不可约(Irreducible,读音 /ˌɪrɪˈduːsəbl/):从任意状态出发,都能到达任意其他状态(对所有 ,存在 使得 )。整个状态空间是一个连通的整体,不存在"走不出去的封闭子区域"。
为什么需要不可约: 如果链是可约的(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/):状态的周期 ,即返回该状态的步数没有固定的公共间隔。与之相对的是周期(Periodic):返回步数存在大于 1 的公共间隔(如只能在偶数步返回)。
为什么需要非周期: 如果链是周期的(),状态分布会在不同的"相位"之间循环振荡,不会收敛到一个稳定分布。比如周期为 2 的链,奇数步和偶数步的分布可能不同,永远在两个分布之间来回跳,没有极限。
三个条件合在一起 = 遍历: 一个不可约 + 非周期 + 常返的马尔可夫链称为遍历的(Ergodic,读音 /ɜːrˈɡɒdɪk/)。这三个条件各自排除了一种"坏情况":
| 条件 | 排除的坏情况 | 缺少时的后果 |
|---|---|---|
| 不可约 | 状态空间分裂成多个互不连通的类 | 平稳分布不唯一 |
| 常返 | 状态跑出去就不回来 | 该状态长期访问频率为 0 |
| 非周期 | 返回有固定节奏 | 分布振荡不收敛 |
三个条件同时满足时,链具有以下良好性质:
- 平稳分布唯一:只有一个 满足 。
- 收敛性:从任意初始分布出发,经过足够多步后都会收敛到 (即遍历定理 成立)。
- 遍历性(时间平均 = 空间平均):沿着一条足够长的链计算的时间平均,等于在平稳分布下计算的空间平均。即 ( 读音 /iː/,数学期望符号,expectation 的缩写)。这是 MCMC 采样方法的理论基础——跑一条链采集样本,样本均值就能逼近目标分布下的期望。
遍历性的详细解释与推导:
什么是时间平均: 你跑一条马尔可夫链,比如模拟天气,跑了 天,记录每天的天气 。然后对某个函数 (比如"晴天记 1,其他记 0")计算这 天的平均值:
这是沿着时间轴算出来的平均值。如果 (指示函数,晴天为 1 否则为 0),时间平均就是"这 天里晴天的比例"。
什么是空间平均: 不跑链,直接用平稳分布 来算函数 的数学期望。 就是数学期望,下标 表示"在分布 下"求期望(普通的 默认在某个分布下,这里明确标出是 )。计算方式就是每个状态的概率乘以该状态下 的值,全部加起来:
用天气例子具体算一遍: 对应(晴、阴、雨), 是"晴天记1、其他记0":
"空间平均"的通俗理解: 想象你不跑链,而是直接"按分布 独立抽很多次天气"——每次都按 47.6%晴、36.1%阴、16.3%雨 来抽,抽 10000 次完全独立的天气,然后算晴天比例。这个比例就是空间平均,它会趋近于 0.476。"空间"指的是状态空间——不是沿着时间轴一步步走,而是直接在所有可能状态上按分布加权平均。
两种平均的对比:
| 时间平均 | 空间平均 | |
|---|---|---|
| 怎么来的 | 跑一条链,走 10000 步,统计晴天比例 | 按 独立抽 10000 次,统计晴天比例 |
| 样本关系 | 相邻天相关(今天晴→明天大概率晴) | 每次抽取完全独立 |
| 极限值 |
遍历性说的就是:这两种做法得到的结果一样。 哪怕时间平均的样本是相关的(马尔可夫链相邻状态不独立),只要链足够长,最终结果和独立采样的空间平均相同。这就是为什么 MCMC 能用——虽然链上的样本不独立,但跑够久之后,样本均值依然能逼近真实期望。
为什么时间平均等于空间平均(推导思路):
第一步:对于常返态 ,定义返回时间 (从 出发到下一次回到 的时间)。常返性保证 有限(概率为 1)。
第二步:一个基本结论是:状态 的长期访问频率等于返回时间期望的倒数:
直觉理解:如果平均每 10 步回一次 (),那么长期来看每 10 步就有 1 步在 ,访问频率就是 。
第三步:对于不可约链,所有状态的访问频率加起来为 1,构成一个分布。令 ,可以证明这个 满足 (平稳分布条件),因此它就是平稳分布。
第四步:时间平均可以按访问频率展开:
式中: 第一步把时间平均按"每个状态被访问了多少次"重新分组;第二步取极限,访问频率收敛到平稳分布 ;最后一步就是空间平均的定义。
用天气的具体数值验证: 平稳分布 。跑一条链 10000 天,统计晴天比例,大约会得到 47.6%;而空间平均 。两者相等。
对 MCMC 的意义: 很多时候我们想算 ,但 是一个复杂分布(如贝叶斯后验),直接解析计算不可能。遍历性告诉我们:不用直接算分布,只要构造一条平稳分布等于 的马尔可夫链,跑足够长时间,用样本均值 就能逼近这个期望。 这就是 MCMC 的核心思想。
1.4 平稳分布与细致平衡
平稳分布
先理解什么是"状态分布": 在马尔可夫链的第 步,系统可能处于状态空间中的任意一个状态。用一个概率分布 (读音 /paɪ/,下标 表示第 步的分布)来描述"此时系统处于各个状态的概率"。 是一个行向量,其中 表示第 步系统处于状态 的概率。
例如天气模型中, 表示"今天有 50% 概率晴、30% 概率阴、20% 概率雨"。
状态分布如何随时间演化: 已知第 步的分布 ,第 步的分布可以通过转移矩阵计算:
式中: 是第 步处于状态 的概率; 是第 步处于状态 的概率; 是从 转移到 的概率。直觉理解:要算"明天是晴天的概率",就要把"今天每种天气的概率 × 该天气转移到晴天的概率"全部加起来。写成矩阵形式就是 。
平稳分布的定义: 如果存在一个分布 ,使得用它乘以转移矩阵后得到的还是它自己——即经过一步转移后分布不变——那么 就称为这个马尔可夫链的平稳分布(Stationary Distribution,读音 /ˈsteɪʃəneri ˌdɪstrɪˈbjuːʃən/):
展开成元素形式就是:
式中: 是平稳分布中状态 的概率; 是状态 的概率; 是从 到 的转移概率。该式的含义是:处于状态 的"总流入概率"(从所有其他状态 转移到 的概率之和)等于当前处于 的概率——流入等于流出,分布达到动态平衡。
用具体数值例子理解收敛: 还是用天气模型,转移矩阵为:
假设初始分布 (今天确定是晴天),逐步演化:
- (明天:晴 70%、阴 20%、雨 10%)
- (后天:晴 57%、阴 30%、雨 13%)
- ...
- 最终收敛到
可以验证:,确实满足平稳分布条件。
"收敛到平稳分布"是什么意思: 对于遍历(不可约 + 非周期 + 常返)的马尔可夫链,无论初始分布 是什么(哪怕今天 100% 是晴天,或 100% 是雨天),经过足够多步后,状态分布都会趋近于同一个平稳分布 。用数学语言表达就是遍历定理(Ergodic Theorem):
式中: (读音 /ˈlɪmɪt/,limit 的缩写,表示极限) 表示 趋向于无穷大; 是从 出发经过 步到 的概率(一个具体数值,不是整个矩阵)。该式的含义是:无论从哪个状态 出发,经过足够多步后,到达状态 的概率都会收敛到平稳分布 ——初始状态的影响被"遗忘"了。
注意 是一个概率值,不是整个分布: 是整个平稳分布(一个行向量),而 是这个向量中状态 对应的那个概率值。公式 对每个 都成立,是平稳分布的元素级定义。
用数值例子直观理解"遗忘初始状态": 还是用天气模型,看从不同初始状态出发,经过 步后到达"晴"的概率 :
| 初始状态 | |||||
|---|---|---|---|---|---|
| 晴 | 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 |
可以看到: 时不同起点差别很大(0.7 vs 0.3 vs 0.2), 时已经很接近, 时无论从哪出发都是 ≈0.476。这个 0.476 就是 。
矩阵极限形式: 因为对所有 都有 ,所以 步转移矩阵 的每一行在极限时都变成了同一个行向量 :
所有行完全相同——这就是"初始状态被遗忘"的矩阵表达。
这就是为什么 MCMC(第五章)可以通过采样来逼近目标分布:构造一个平稳分布等于目标分布的马尔可夫链,跑足够多步后采集的样本就近似服从目标分布。
细致平衡
细致平衡(Detailed Balance,读音 /dɪˈteɪld bəˈlæns/)是平稳分布的一个充分条件(但不是必要条件)。如果存在一个分布 满足:
逐部分解释这个公式:
- :平稳分布中状态 的概率(即"系统处于 的概率")。
- :从 转移到 的概率。
- :从 流向 的概率流(probability flux,读音 /ˌprɒbəˈbɪləti flʌks/)。直觉理解:如果有 1000 个独立运行的链,其中大约 个处于状态 ,其中又有 比例会转移到 ,所以单位时间内从 到 的"流量"就是 。
- :从 流向 的概率流。
- :对任意两个状态 和 都成立。
公式的含义: 对于任意一对状态 和 ,从 流向 的流量等于从 流向 的流量——双向流量相等。这比平稳分布条件(,只要求每个状态的总流入等于总流出)更强:平稳分布只要求"每个状态的净流入为零",而细致平衡要求"每一对状态之间的双向流量都相等"。
为什么细致平衡能推出平稳分布(推导): 对细致平衡公式两边同时对 求和:
右边 与求和变量 无关,可以提出来:
而转移矩阵的行和为 1(,从 出发转移到所有状态的概率之和为 1),所以:
关于 和求和变量的说明: 是转移矩阵第 行第 列的元素,表示从状态 转移到状态 的概率(第一个下标是"从哪来"/行,第二个下标是"到哪去"/列)。这里的求和变量是 ,所以 是把第 行的所有元素加起来。用天气模型举例, 时:。
注意:求和变量 是哑变量(dummy variable,读音 /ˈdʌmi ˈveəriəbl/),只是一个"计数器",可以换成任何未使用的字母(如 )而不改变结果,即 。但不能换成 ,因为 在公式中已经是固定的目标状态(自由变量),换成 会导致含义改变( 变成了"对所有状态求自转移概率之和",完全不同)。
这恰好就是平稳分布的元素级定义 。因此细致平衡成立时, 一定是平稳分布。
为什么是充分条件但不是必要条件: 细致平衡比平稳分布更强。平稳分布只要求每个状态的总流入等于总流出(可以存在"环流",比如 的循环流量,每对状态之间双向流量不等,但每个状态的净流入仍为零)。而细致平衡要求每对状态之间双向流量都相等,排除了环流的存在。所以:满足细致平衡 → 一定是平稳分布;但是平稳分布 → 不一定满足细致平衡。
用天气模型验证: 平稳分布 ,检查"晴"和"阴"之间:
- 正向流量:
- 反向流量:
两者不相等,说明这个天气模型的平稳分布不满足细致平衡(存在环流),但它仍然是平稳分布。这就是"充分但不必要"的具体例子。
对 MCMC 的意义: 细致平衡是 MCMC 方法(如 Metropolis-Hastings、Gibbs 采样)的核心设计原则。我们想要从目标分布 中采样,但直接采样很难。于是我们反过来设计转移矩阵 ,使得 满足细致平衡 。这样构造出的马尔可夫链,其平稳分布就恰好是我们想要的 ,跑足够多步后采集的样本就近似服从 。
二、隐马尔可夫模型(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 由以下五个部分定义:
-
隐藏状态空间 (读音 /ɛs/):所有可能的隐藏状态的集合。例子中 ,。(读音 /ɛn/)是隐藏状态的数量。隐藏状态之间满足马尔可夫性质(下一状态只依赖当前状态)。
-
观测空间 (读音 /viː/):所有可能的观测值的集合。例子中 ,。(读音 /ɛm/)是观测值的数量。
-
初始状态分布 (读音 /paɪ/):第一天()处于各隐藏状态的概率。例子中 表示第一天 60% 概率晴、40% 概率雨。
-
状态转移矩阵 (读音 /eɪ/):隐藏状态之间的转移概率。 表示从隐藏状态 转移到 的概率。例子中: 即今天晴→明天晴 70%、雨 30%;今天雨→明天晴 40%、雨 60%。
-
观测概率矩阵 (读音 /biː/):在隐藏状态 下产生观测 的概率。例子中: 即晴天时 60% 散步、30% 购物、10% 打扫;雨天时 10% 散步、40% 购物、50% 打扫。
三个概率矩阵的精确定义公式:
初始状态分布:
式中: 是初始时刻(第 1 步)处于隐藏状态 的概率;(读音 /kjuː tiː/)表示第 步的隐藏状态( 是 hidden state 的常用符号)。
下标区分: 公式中 和 的下标 是状态索引(表示第几个状态,如 是晴、 是雨),而 的下标 是时间步索引(表示第 1 天/第 1 步)。两者是完全不同的维度: 在遍历所有状态, 固定指初始时刻。代入具体值: 时 ; 时 。
状态转移概率:
式中: 是从隐藏状态 转移到 的概率;竖线 表示"条件于"(已知当前状态是 )。这和第一章马尔可夫链的转移概率 是同一个东西,只是 HMM 中习惯用 表示。
观测概率:
式中: 是在隐藏状态 下产生观测 的概率;(读音 /oʊ tiː/, 是 observation 的缩写)是第 步的观测值。该式的含义是:已知第 步的隐藏状态是 ,观测到 的概率是多少。
因此,一个 HMM 通常记为 (读音 /ˈlæmdə/,希腊字母 lambda,这里作为 HMM 全部参数的整体代号)。知道了 、、 这三个矩阵,就完全确定了一个 HMM。
2.2 HMM 的两个基本假设
HMM 建立在两个假设之上:
- 马尔可夫假设(Markov Assumption):隐藏状态序列满足马尔可夫性质,即下一隐藏状态只依赖于当前隐藏状态。
- 输出独立性假设(Output Independence Assumption):第 步的观测 只依赖于第 步的隐藏状态 ,与其他隐藏状态和观测无关。
查看图示结构
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 的结构:上层是隐藏的马尔可夫链(状态之间有转移),下层是观测序列(每个观测只由对应时刻的隐藏状态生成)。隐藏状态之间的箭头表示状态转移 ,隐藏状态到观测的箭头表示观测概率 。
2.3 HMM 的三个基本问题
HMM 的理论和应用围绕三个基本问题展开:
| 问题 | 名称 | 描述 | 求解算法 |
|---|---|---|---|
| 问题一 | 评估问题 | 给定模型 和观测序列 ,计算观测序列出现的概率 | 前向算法 / 后向算法 |
| 问题二 | 解码问题 | 给定模型 和观测序列 ,找到最可能产生该观测的隐藏状态序列 | Viterbi 算法 |
| 问题三 | 学习问题 | 给定观测序列 ,估计模型参数 使概率最大 | Baum-Welch 算法(EM) |
问题一:评估问题与前向算法
给定观测序列 (读音 /oʊ/, 是序列长度),计算 。
最朴素的方法是枚举所有可能的隐藏状态序列 ,计算联合概率再求和:
式中:
- 是初始状态 的概率。
- 是在状态 下产生观测 的概率。
- 是从 转移到 的概率。
这个求和有 项( 个状态、 个时间步的所有组合),计算量随 指数增长,不可行。
前向算法(Forward Algorithm,读音 /ˈfɔːrwərd ˈælɡərɪðəm/)通过动态规划将复杂度降到 。定义前向变量(Forward Variable):
式中:
- (读音 /ˈælfə tiː/, 是希腊字母 alpha,读音 /ˈælfə/)表示"前 步的观测为 到 ,且第 步处于隐藏状态 "的联合概率。
前向算法的递推过程:
-
初始化():对所有 ,初始状态概率乘以产生第一个观测的概率,即
-
递推():
式中:
- 方括号内的求和表示"从所有可能的前一状态 转移到 "的概率之和。
- 然后乘以在状态 下产生观测 的概率。
这个递推利用了马尔可夫性质:到达 的所有路径的概率可以合并。
-
终止:对最后一步所有可能的隐藏状态求和,得到观测序列的概率:
类似地,后向算法(Backward Algorithm)定义后向变量 (读音 /ˈbeɪtə tiː/, 是希腊字母 beta,读音 /ˈbeɪtə/),从后往前递推:
前向和后向变量结合起来,可以用于 Baum-Welch 学习算法。
问题二:解码问题与 Viterbi 算法
给定观测序列 ,找到最可能的隐藏状态序列 (读音 /kjuː stɑːr/,argmax 表示"使后面的函数取最大值的自变量")。
Viterbi 算法(读音 /vɪˈtɜːrbi ˈælɡərɪðəm/,得名于工程师安德鲁·维特比,Andrew Viterbi)同样使用动态规划,但不是求和,而是取最大值。定义Viterbi 变量:
式中:
- (读音 /ˈdɛltə tiː/, 是希腊字母 delta,读音 /ˈdɛltə/)表示"前 步观测为 到 ,且第 步处于状态 "的所有路径中的最大概率。
- (读音 /mæks/,maximum 的缩写,表示取最大值)对所有可能的前 步状态序列取最大。
Viterbi 递推:
-
初始化:对所有 ,计算初始 Viterbi 变量和路径指针:
其中 (读音 /psaɪ/,希腊字母 psi)用于回溯最优路径。
-
递推():
式中:
- 是到达状态 的最大概率。
- 记录了"到达 的最优路径中,前一步是哪个状态 ",用于最后回溯。
-
终止:最优路径的终点为
-
回溯:从 到 ,逐步回溯得到完整的最优隐藏状态序列:
Viterbi 算法在语音识别中用于从声学特征序列解码出音素序列,在词性标注中用于从单词序列解码出词性序列。
问题三:学习问题与 Baum-Welch 算法
给定观测序列 ,估计模型参数 使 最大。这是一个无监督学习问题——隐藏状态是未知的,只有观测可见。
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 上的特例。
定义两个辅助变量:
- (读音 /ˈɡæmə tiː/, 是希腊字母 gamma,读音 /ˈɡæmə/):给定观测序列 ,第 步处于状态 的后验概率。
- (读音 /ksaɪ tiː/, 是希腊字母 xi,读音 /ksaɪ/):给定观测序列 ,第 步处于状态 且第 步处于状态 的后验概率。
它们的计算公式为:
Baum-Welch 的参数更新公式:
式中:
- :(读音 /paɪ/,希腊字母 pi)上方加横线表示"更新后的值",下标 (读音 /aɪ/)表示第 个状态。整体表示更新后的初始状态概率,等于第一步处于状态 的后验概率。
- :(读音 /eɪ/)上方加横线表示"更新后的值",下标 (读音 /aɪ dʒeɪ/)表示从状态 到状态 。整体表示更新后的转移概率,等于"从 到 的期望次数"除以"处于 的期望次数"。
- :(读音 /biː/)上方加横线表示"更新后的值",下标 (读音 /dʒeɪ/)表示状态 ,括号内 (读音 /viː keɪ/)表示第 个观测值。整体表示更新后的观测概率,等于"在状态 下产生观测 的期望次数"除以"处于 的期望次数"。
- (读音 /ˌɪndɪˈkeɪtər ˈfʌŋkʃən/,粗体 1 是指示函数,当条件成立时为 1,否则为 0)。
Baum-Welch 交替执行 E 步(用当前参数计算 和 )和 M 步(用 和 更新参数),直到收敛。它保证 单调不减,但可能收敛到局部最优。
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 由以下五元组定义:
- 状态空间 (读音 /ɛs/,大写):所有可能状态的集合。
- 动作空间 (读音 /eɪ/,大写):智能体可以执行的所有动作的集合。
- 状态转移函数 (读音 /piː/):在状态 执行动作 后,转移到状态 (读音 /ɛs praɪm/,表示下一状态)的概率。
- 奖励函数 (读音 /ɑːr/):在状态 执行动作 后获得的即时奖励(期望奖励)。
- 折扣因子 (读音 /ˈɡæmə/,希腊字母 gamma,取值 ):衡量未来奖励的当前价值。
MDP 与马尔可夫链的关键区别:马尔可夫链的状态转移是被动的( 固定),而 MDP 的状态转移依赖于智能体选择的动作()。智能体通过选择动作来影响状态演化的方向,目标是最大化累积奖励。
3.2 策略、回报与价值函数
策略
策略(Policy)(读音 /paɪ/)定义了智能体在每个状态下选择每个动作的概率分布:
式中:
- 是在状态 下选择动作 的概率。
策略分为两类:
- 确定性策略(Deterministic Policy):每个状态只对应一个确定的动作,即 。
- 随机性策略(Stochastic Policy):每个状态对应一个动作概率分布,智能体从中采样,即 。大语言模型的强化学习中使用的都是随机性策略。
强化学习的目标就是找到一个最优策略 ,使得累积奖励的期望最大。
回报
从时间步 开始的折扣回报(Discounted Return)定义为:
式中:
- (读音 /dʒiː tiː/)是从第 步开始的折扣回报。
- 是第 步的即时奖励。
- 是折扣因子的 次方。
- 从 到 表示对未来所有步求和。
越接近 1,智能体越有远见(重视长期奖励); 越接近 0,越短视(只看眼前奖励)。
状态价值函数
状态价值函数(State Value Function)(读音 /viː/):在遵循策略 的前提下,从状态 出发能获得的期望折扣回报。
式中:
- :(读音 /iː/,数学期望符号,expectation 的缩写)下标 (读音 /paɪ/,希腊字母 pi,表示策略),整体表示在策略 诱导的分布下求期望。
回答的问题是:"如果我现在在状态 ,并且一直按策略 行动,平均能拿多少分?"
动作价值函数
动作价值函数(Action Value Function)(读音 /kjuː/):在状态 下先执行动作 ,之后遵循策略 ,能获得的期望折扣回报。
回答的问题是:"如果我现在在状态 ,先强制选动作 ,之后按策略 行动,平均能拿多少分?" 函数比 函数多了一个动作维度,因此可以直接用于选择动作(选 值最大的动作)。
优势函数
优势函数(Advantage Function)(读音 /eɪ/):动作 比"按策略 随机选一个动作"平均好多少。
优势函数是策略梯度方法(PPO、GRPO 等)的核心量: 的动作应该增加概率, 的动作应该降低概率。
3.3 贝尔曼方程
贝尔曼方程(Bellman Equation,读音 /ˈbɛlmən ɪˈkweɪʒən/,得名于数学家理查德·贝尔曼,Richard Bellman)是 MDP 理论的基石。它将价值函数分解为"即时奖励 + 下一状态价值"的递归形式。
贝尔曼期望方程
对于任意策略 ,状态价值函数满足:
式中:
- 对所有可能的动作 求和(按策略 加权)。
- 方括号内是"执行动作 后的即时奖励 "加上"折扣后的下一状态期望价值"。
该式的含义是:状态 的价值等于"按策略选一个动作,拿到即时奖励,然后下一状态的价值按转移概率加权求和"。
类似地,动作价值函数的贝尔曼期望方程:
式中:
- (读音 /eɪ praɪm/,表示下一状态的动作)是下一状态 下选择的动作。
贝尔曼最优方程
最优策略 (读音 /paɪ stɑːr/)是使所有状态的价值都最大的策略。最优价值函数记为 和 。
最优价值函数满足贝尔曼最优方程:
式中:
- 表示对所有动作 取最大值。
该式的含义是:最优策略下,状态 的价值等于"选择能使即时奖励加下一状态价值最大的那个动作"。
有了 ,最优策略就是贪婪选择:在状态 下选择使 最大的动作 。
3.4 动态规划求解 MDP
当 MDP 的模型(转移函数 和奖励函数 )完全已知时,可以用动态规划(Dynamic Programming,简称 DP,读音 /daɪˈnæmɪk ˈproʊɡræmɪŋ/)精确求解。
策略迭代
策略迭代(Policy Iteration,读音 /ˈpɒləsi ˌɪtəˈreɪʃən/)交替执行两个步骤:
-
策略评估(Policy Evaluation):给定当前策略 ,计算 。通过迭代贝尔曼期望方程直到收敛:
-
策略提升(Policy Improvement):用 计算 ,然后贪婪地更新策略:
重复"评估→提升"直到策略不再变化。策略迭代保证收敛到最优策略,但每次策略评估都需要迭代到收敛,计算量大。
值迭代
值迭代(Value Iteration,读音 /ˈvæljuː ˌɪtəˈreɪʃən/)将策略评估和提升合并为一步,直接迭代贝尔曼最优方程:
值迭代不需要显式维护策略,每次迭代直接更新 。收敛后,通过下式提取最优策略:
值迭代通常比策略迭代更快,因为不需要每次都评估到收敛。
3.5 MDP 与强化学习算法的关系
动态规划要求 MDP 模型完全已知( 和 已知),但在很多实际问题中(包括 LLM 训练),我们不知道环境的转移函数和奖励函数的解析形式。这时就需要强化学习(Reinforcement Learning):智能体通过与环境交互采样,用样本估计价值函数或直接优化策略。
| 方法 | 是否需要模型 | 典型算法 |
|---|---|---|
| 动态规划(DP) | 需要( 和 已知) | 策略迭代、值迭代 |
| 基于价值的 RL | 不需要,用样本估计 | 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 的进一步扩展:智能体无法直接观测到完整的状态 ,只能观测到一个与状态相关的观测(Observation)。POMDP 是更贴近现实的决策模型,因为在大多数真实场景中,智能体只能感知环境的一部分。
4.1 POMDP 的定义
一个 POMDP 由以下七元组定义:
- 状态空间 (读音 /ɛs/):所有可能的真实状态的集合(智能体不可直接观测)。
- 动作空间 (读音 /eɪ/):所有可能动作的集合。
- 状态转移函数 (读音 /piː/):在状态 执行动作 后转移到 的概率。
- 奖励函数 (读音 /ɑːr/):在状态 执行动作 后获得的奖励。
- 观测空间 (读音 /oʊ/,大写):所有可能观测的集合。
- 观测函数 (读音 /zɛd/, 是 observation 的常用符号,因为 已被观测空间占用):在新状态 下(执行动作 后)观测到 的概率。
- 折扣因子 (读音 /ˈɡæmə/):未来奖励的折扣率。
POMDP 与 MDP 的关键区别:MDP 中智能体能直接看到状态 ;POMDP 中智能体只能看到观测 ,而观测可能是状态的噪声、部分或模糊版本。
4.2 信念状态
在 POMDP 中,由于无法直接观测状态,智能体需要维护一个对当前状态的概率分布,称为信念状态(Belief State,读音 /bɪˈliːf steɪt/):
式中:
- (读音 /biː/)是信念状态中状态 的概率。
- 条件部分是到目前为止的所有观测和动作历史。
信念状态 是一个概率分布,满足 。
信念状态可以通过贝叶斯更新(Bayesian Update,读音 /ˈbeɪziən ʌpˈdeɪt/)递推计算。当智能体执行动作 并观测到 后,新的信念状态为:
式中:
- (读音 /ˈiːtə/,希腊字母 eta,读音 /ˈiːtə/,是归一化常数,确保 的总和为 1)。
- 是在状态 下观测到 的概率。
- 是"在旧信念下执行动作 后到达 的预测概率"。
该式的含义是:先根据动作预测下一状态的分布,再根据新观测用贝叶斯公式修正。
关键洞察: 信念状态 满足马尔可夫性质!因为 只依赖于 、 和 ,不依赖于更早的历史。因此,POMDP 可以转化为一个在信念状态空间上的连续状态 MDP——这就是 POMDP 求解的基本思路。但信念状态空间是连续的(概率单纯形),求解比普通 MDP 困难得多。
4.3 POMDP 与 LLM Agent 的联系
LLM Agent(大语言模型智能体)的决策过程本质上就是一个 POMDP:
- 真实状态 :环境的完整状态(比如用户的真实意图、数据库的完整内容、代码执行环境的完整状态)。
- 观测 :LLM 能看到的信息(用户输入、工具返回结果、对话历史)。这些观测通常是不完整的。
- 动作 :LLM 可以执行的操作(生成文本、调用工具、查询数据库、执行代码)。
- 信念状态 :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
在概率推断中,我们常常需要从一个复杂的目标分布 (读音 /paɪ/,这里表示目标概率分布, 是随机变量)中采样,或者计算关于 的期望:
当 是高维、复杂、非标准化的分布时(比如贝叶斯后验分布),直接采样或数值积分都不可行。蒙特卡洛方法(Monte Carlo,读音 /ˌmɒnti ˈkɑːrloʊ/,得名于摩纳哥的赌城,因为随机采样与赌博类似)用样本平均来近似期望:
但问题是:如何从复杂的 中生成样本 ?MCMC 的回答是:构造一个马尔可夫链,使其平稳分布恰好是 ,然后运行这个马尔可夫链来采集样本。
5.2 MCMC 的基本原理
MCMC 的理论基础是第一章讲的遍历定理:对于一个遍历(不可约、非周期、常返)的马尔可夫链,从任意初始状态出发,经过足够多步后,状态分布会收敛到平稳分布 。而且,时间平均等于空间平均(遍历性):
式中:
- 是马尔可夫链第 步的状态。
- 是总步数。
因此,MCMC 的核心任务就是:设计一个转移核 ,使得其平稳分布为 。最常用的设计原则是细致平衡(Detailed Balance):
式中:
- 是从 流向 的概率流。
- 是反向流量。
如果细致平衡成立,那么 一定是平稳分布。
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)(读音 /kjuː/)来生成候选样本,然后用一个接受概率(Acceptance Probability)来决定是否接受候选。
算法步骤:
- 初始化:选择初始状态 。
- 提议:从提议分布 中采样一个候选状态 。
- 计算接受概率:
式中:
- (读音 /ˈælfə/)是接受概率。
- (民,取最小值)确保接受概率不超过 1。
- 是目标分布的比值(如果 是非标准化的,归一化常数会约掉,这是 MCMC 的一大优势——不需要知道归一化常数!)。
- 是提议分布的反向比值,用于修正提议分布的不对称性。
- 接受或拒绝:以概率 接受 (令 ),否则拒绝(令 )。
- 重复:回到步骤 2,直到收敛。
为什么这样设计满足细致平衡? 可以验证:,其中 。因此平稳分布就是 。
Metropolis 算法是 Metropolis-Hastings 的特例:当提议分布对称时(),接受概率简化为 。
5.4 Gibbs 采样
Gibbs 采样(读音 /ɡɪbz ˈsɑːmplɪŋ/,得名于物理学家 Josiah Willard Gibbs)是 Metropolis-Hastings 的一个特例,专门用于高维分布。它的核心思想是:每次只更新一个维度,其他维度保持不变,用该维度的条件分布作为提议分布。
对于 (读音 /diː/,表示维度数)维随机变量 ,Gibbs 采样的步骤:
- 初始化:。
- 对每个维度 :
式中:
- (读音 /paɪ/)是第 维的条件分布(Conditional Distribution),即在其他所有维度固定的情况下,第 维的概率分布。
- 上标 和 表示第 步和第 步的值——已经更新过的维度用新值,未更新的维度用旧值。
Gibbs 采样的接受概率恒为 1(因为条件分布作为提议分布恰好满足细致平衡),因此不需要拒绝步骤。但它要求能从条件分布中高效采样——这在某些模型中可行(如贝叶斯网络、主题模型 LDA),在另一些模型中不可行。
5.5 MCMC 的实践要点
- 烧入期(Burn-in Period,读音 /bɜːrn ɪn ˈpɪəriəd/):马尔可夫链从初始状态到收敛到平稳分布需要一段时间,这段时间的样本应该丢弃。通常丢弃前 10%–50% 的样本。
- 自相关性(Autocorrelation):相邻样本是相关的(因为是马尔可夫链),不是独立样本。可以通过稀疏采样(Thinning,每隔 步取一个样本)来降低相关性,但这会降低样本效率。
- 收敛诊断(Convergence Diagnosis):判断链是否收敛的方法,包括 Gelman-Rubin 统计量(多条链对比)、自相关图、迹图(Trace Plot)等。
- 混合速度(Mixing):马尔可夫链在状态空间中探索的速度。提议分布太窄会导致混合慢(局部探索),太宽会导致接受率低。需要调参。
5.6 MCMC 在机器学习中的应用
- 贝叶斯推断:从后验分布 (读音 /paɪ/, 是模型参数, 是数据)中采样,用于贝叶斯神经网络、高斯过程、主题模型(LDA)等。
- 扩散模型(Diffusion Models):去噪扩散概率模型(DDPM)的采样过程本质上是一个马尔可夫链——从噪声开始,逐步去噪生成数据。虽然不是标准的 MCMC(转移核是学习出来的),但马尔可夫链的思想是核心。
- 能量模型(Energy-Based Models):用 MCMC(如 Langevin 动力学,一种连续状态的 MCMC)从能量模型定义的分布中采样。
- 马尔可夫链 LLM:近期研究探索用马尔可夫链替代自回归生成,通过迭代修正来生成文本。
六、Markov 家族算法关系图谱与总结
6.1 家族关系图谱
所有 Markov 家族算法都共享马尔可夫性质,但在"是否有动作""是否可观测""是否用于采样"等维度上各有扩展。下图展示了它们之间的关系:
查看图示结构
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 家族算法以多种方式交织出现:
- RL 训练框架是 MDP:PPO、GRPO、DAPO、VAPO 等算法都在 MDP 框架下定义。状态是 prompt + 已生成的 token,动作是下一个 token,奖励是 verifier/judge 的评分。GRPO 的核心创新是用组内相对优势代替 MDP 中的价值网络。
- LLM Agent 是 POMDP:模型无法直接观测环境的完整状态,只能通过工具调用获得部分观测,需要维护信念状态(对话上下文)。
- 扩散模型采样是马尔可夫链:DDPM 的前向加噪和反向去噪都是马尔可夫链过程。
- 序列建模的马尔可夫假设:传统 n-gram 语言模型是马尔可夫链(下一个词只依赖前 n-1 个词)。Transformer 虽然理论上可以建模任意长程依赖,但在实践中也常被视为"近似马尔可夫"的生成过程。
- 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 的机器学习视角综述