马尔可夫链与Transformer的理论联系

概述

深度学习模型与经典概率论之间存在着深刻的联系。2024-2025年的研究表明，Transformer架构与马尔可夫链（Markov Chain）之间存在天然的理论联系。¹²

本专题将探讨这些联系，包括：

• Transformer如何有效建模马尔可夫数据
• 固定深度Transformer的表达能力
• 上下文学习的马尔可夫链视角

---

马尔可夫数据建模

马尔可夫数据的定义

定义（$k$阶马尔可夫数据）：设 $\{X_t\}$ 为取值于有限字母表 $\Sigma$ 的随机序列。若对任意 $t>k$：

$$P(X_t=x_t\mid X_{t-1},X_{t-2},\dots )=P(X_t=x_t\mid X_{t-1},\dots ,X_{t-k})$$

则称 $\{X_t\}$ 为**$k$阶马尔可夫链**，产生的数据称为**$k$阶马尔可夫数据**。

马尔可夫阶与复杂度

马尔可夫阶 $k$ 衡量数据中的记忆深度：

阶数 $k$	数据类型	示例
0	i.i.d.	独立抛硬币
1	一阶马尔可夫	天气模型
2	二阶马尔可夫	语法结构
>2	高阶马尔可夫	复杂自然语言

关键观察：高阶马尔可夫数据需要更大的记忆容量来建模。

---

Transformer在马尔可夫数据上的表现

核心定理

定理（Transformer与马尔可夫数据）：对于任意阶数为 $k$ 的马尔可夫数据，存在一个固定深度的Transformer能够准确建模该数据。

形式化表述：设 ${\mathcal{D}}_k$ 为所有 $k$ 阶马尔可夫数据构成的分布族。则存在常数 $L$（依赖于 $k$），使得深度为 $L$ 的Transformer可以任意好地近似 ${\mathcal{D}}_k$ 中的任意分布。

理论直觉

这一结果的直觉来自以下观察：

1. 局部记忆建模：每个注意力头可以捕获相邻token间的转移概率
2. 层级组合：多层堆叠可以组合局部信息为全局状态表示
3. 固定深度充足：不需要随数据复杂度增加深度

与传统RNN的对比

架构	深度需求	并行性	长期依赖
RNN	需要足够深度	低	受梯度消失限制
LSTM/GRU	中等深度	低	有所改善
Transformer	固定深度	高	显式建模

---

固定深度Transformer的理论保证

表达能力下界

定理（表达能力下界）：对于大小为 $n$ 的状态空间和阶数为 $k$ 的马尔可夫数据，深度为 $O(k)$ 的Transformer可以表达任意 $k$ 阶马尔可夫链。

证明思路：

1. 状态编码：使用位置嵌入编码历史状态 $X_{t-1},\dots ,X_{t-k}$
2. 转移矩阵计算：通过注意力机制计算条件分布 $P(X_t\mid X_{t-1:k})$
3. 采样输出：使用softmax输出层进行采样

深度-宽度权衡

在实际应用中，Transformer的深度和宽度存在权衡：

$$\text{表达能力}\propto \text{depth}\times \text{width}$$

对于固定的参数预算：

• 深而窄：更好地建模长依赖，但每层容量有限
• 浅而宽：更好地建模局部模式，但依赖建模受限

---

上下文学习的马尔可夫视角

上下文学习的定义

上下文学习（In-Context Learning, ICL）是大型语言模型的核心能力：在不更新参数的情况下，仅通过输入中的示例来学习新任务。

形式化：给定提示 $P=(x_1,y_1),(x_2,y_2),\dots ,(x_k,y_k),x_{k+1}$，模型预测 $y_{k+1}$。

马尔可夫链估计视角

2025年的研究表明，上下文学习可以被解释为马尔可夫链参数的在线估计。³

核心思想：

1. 上下文作为观测序列：提示中的示例 $(x_i,y_i)$ 构成观测序列
2. 任务参数作为隐状态：真正的任务参数（如下一个词的分布）是隐状态
3. ICL作为推断：模型执行某种贝叶斯推断来估计隐状态

形式化框架

设 $\theta$ 为任务参数（如条件分布），$D=\{(x_1,y_1),\dots ,(x_k,y_k)\}$ 为上下文。ICL可以形式化为：

$$P(y_{k+1}\mid x_{k+1},D)=\int P(y_{k+1}\mid x_{k+1},\theta )P(\theta \mid D)d\theta$$

其中 $P(\theta \mid D)$ 是给定上下文后的后验分布。

关键发现

1. 贝叶斯最优性：在某些假设下，上下文学习等价于贝叶斯推断
2. 示例数量的作用：更多示例 $\Rightarrow$ 后验分布更集中 $\Rightarrow$ 预测更准确
3. 任务相似性：相似任务的上下文可以相互促进

---

大型语言模型作为马尔可夫链

生成过程的马尔可夫解释

语言模型的生成过程可以视为在token空间上的马尔可夫采样：

$$P(x_{t+1}\mid x_1,\dots ,x_t)=\text{Softmax}(f_{\theta }(x_1,\dots ,x_t))$$

这正是一阶马尔可夫假设：下一个token的条件分布只依赖于当前上下文。

转移矩阵的估计

给定语料 $\mathcal{C}$，语言模型学习估计转移矩阵：

$$\hat{P}(x_{t+1}=j\mid x_t=i)\approx \frac{\text{count}(i\to j)}{{\sum }_j\text{count}(i\to j)}$$

但由于Transformer可以建模长距离依赖，这个”转移”实际上是多步组合的结果。

高阶扩展

为了建模更复杂的语言结构，可以考虑高阶马尔可夫扩展：

• 二元模型（2-gram）：$P(x_{t+1}\mid x_t)$
• 三元模型（3-gram）：$P(x_{t+1}\mid x_t,x_{t-1})$
• Transformer：$P(x_{t+1}\mid x_1,\dots ,x_t)$

Transformer的优势在于可以自适应地决定有效的”阶数”。

---

注意力机制作为马尔可夫链

注意力机制与马尔可夫链的联系是理解Transformer的关键。详见 注意力机制的马尔可夫链理论。

关键结论回顾

1. 注意力矩阵 $\approx$ 转移矩阵：$A_{ij}$ 可以解释为从token $i$ 到token $j$ 的转移概率
2. TokenRank = 稳态分布：衡量token的全局重要性
3. 多层注意力 = 多步传播：$A^n$ 对应 $n$ 步马尔可夫转移

---

理论启示与实际应用

为什么Transformer有效

马尔可夫链视角提供了解释：

传统观点	马尔可夫视角
注意力捕获依赖	转移矩阵定义概率流
全局信息整合	稳态分布编码全局信息
并行计算高效	矩阵运算可并行化

架构设计启示

1. 深度选择：$O(k)$ 深度足以建模 $k$ 阶马尔可夫数据
2. 注意力头设计：多头注意力可以建模多种转移模式
3. 位置编码：影响转移矩阵的结构

实践建议

1. 序列长度：对于高阶依赖任务，需要足够长的上下文
2. 注意力模式：稀疏注意力可能足以建模马尔可夫结构
3. 训练策略：考虑马尔可夫数据增强

---

与NTK理论的联系

神经网络切向核（NTK）理论提供了另一种理解深度学习动力学的方式。详见 NTK理论深度解析。

联系与区别

方面	NTK理论	马尔可夫视角
分析层面	无限宽度极限	有限宽度
训练动态	核回归	概率推断
表征学习	特征演化	状态转移
表达能力	核函数类	概率分布类

两种视角互补：NTK关注训练动力学，马尔可夫视角关注序列建模能力。

---

参考文献

Footnotes

1. Transformers on Markov Data (2024). “Transformers on Markov Data: Constant Depth Suffices.” arXiv:2407.17686. ↩

2. Engel et al. (2025). “Attention (as Discrete-Time Markov) Chains.” arXiv:2507.17657. ↩

3. Markov Chain Estimation with In-Context Learning (2025). “Markov Chain Estimation with In-Context Learning.” arXiv:2508.03934. ↩