马尔可夫链与深度学习理论

1 引言

马尔可夫链（Markov Chain）作为概率论的核心概念，为理解大型语言模型（LLMs）和Transformer架构提供了全新的理论视角。2024-2025年的研究揭示了以下深刻联系¹²：

• LLMs本质上是在有限状态空间上运行的马尔可夫链
• Transformer可以通过马尔可夫数据学习最优估计器
• Mamba的选择性机制与马尔可夫过程有天然对应

这些发现不仅深化了我们对深度学习的理论理解，还为架构设计提供了新的指导原则。

2 马尔可夫链基础回顾

2.1 马尔可夫性质

定义：设 $\{X_t{\}}_{t\ge 0}$ 为随机过程。若对任意 $t$ 和任意状态序列 $x_0,x_1,\dots ,x_{t-1},x_t,x_{t+1}$：

$$P(X_{t+1}=x_{t+1}\mid X_t=x_t,X_{t-1}=x_{t-1},\dots ,X_0=x_0)=P(X_{t+1}=x_{t+1}\mid X_t=x_t)$$

则称该过程具有马尔可夫性质，即无记忆性。

2.2 转移概率与转移矩阵

转移概率：

$$p_{ij}(t)=P(X_{t+1}=j\mid X_t=i)$$

转移矩阵（时齐马尔可夫链）：

$$P=\left[\begin{array}{cccc}{p}_{11}& p_{12}& \cdots & p_{1n}\\ p_{21}& p_{22}& \cdots & p_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ p_{n1}& p_{n2}& \cdots & p_{nn}\end{array}\right]$$

其中 ${\sum }_j{p}_{ij}=1$。

2.3 平稳分布

定义：若存在分布 $\pi$ 满足

$${\pi }^T={\pi }^{T}P$$

则称 $\pi$ 为马尔可夫链的平稳分布。

遍历定理：若马尔可夫链是正常返且不可约，则

$$\underset{t\to \infty }{\lim }P(X_t=j)={\pi }_j\text{（独立于初始分布）}$$

3 LLMs as Markov Chains

3.1 语言模型的马尔可夫形式化

考虑一个自回归语言模型 $p_{\theta }(x_{t+1}\mid x_{\le t})$，其中 $x_t$ 是token。

核心洞察：LLM可以被理解为在token状态空间上的马尔可夫链，其转移概率由神经网络参数化：

$$P_{\theta }(x_{t+1}\mid x_t)=p_{\theta }(x_{t+1}\mid x_{\le t})\text{（上下文通过隐藏状态编码）}$$

状态空间大小：

设token词表大小为 $|V|$，$k$ 阶马尔可夫链的状态空间大小为 $|V{|}^k$。实际LLM的等效状态空间约为 $O(T^k)$，其中 $T$ 是上下文长度，$k$ 是有效记忆阶数。

3.2 有限状态机视角

定理¹：对于有限上下文长度 $T$，LLM定义了一个有限状态机，其中：

• 状态：所有长度为 $T$ 的token序列
• 转移：给定当前状态（过去 $T$ 个token），预测下一个token
• 概率：由 $p_{\theta }$ 给出

这意味着LLM的整个行为可以用一个转移矩阵描述，其大小为 $|V{|}^T\times |V|$。

3.3 温度与平稳分布

温度参数 $\tau$ 控制生成的多样性：

$$p_{\tau }(x_{t+1}\mid x_{\le t})=\text{softmax}\left(\frac{z_{t+1}}{\tau }\right)$$

与马尔可夫链的关系：

• $\tau \to 0$：确定性转移，趋向最高概率token
• $\tau =1$：标准softmax
• $\tau \to \infty$：趋近均匀分布

平稳分布的温度依赖：

$${\pi }_{\tau }(x)\propto \exp \left(\frac{E(x)}{\tau }\right)$$

其中 $E(x)$ 是token序列的能量（负对数概率）。

3.4 预训练作为马尔可夫链估计

预训练过程可以理解为从数据分布中估计马尔可夫链的转移概率：

目标：最小化数据分布 $p_{\text{data}}$ 与模型分布 $p_{\theta }$ 之间的KL散度

$$\underset{\theta }{\min }{D}_{\text{KL}}(p_{\text{data}}\Vert p_{\theta })=\underset{\theta }{\min }{\mathbb{E}}_{x\sim p_{\text{data}}}[\log p_{\theta }(x)]$$

类比：这等价于在马尔可夫链框架下，估计转移矩阵 $P$ 使得数据分布是平稳分布。

4 Transformers on Markov Data

4.1 核心问题

给定来自 $k$ 阶马尔可夫源的序列，Transformer能否学习最优的条件分布估计？

定义：$k$ 阶马尔可夫源满足

$$P(x_{t+1}\mid x_{\le t})=P(x_{t+1}\mid x_{t-k+1:t})$$

4.2 常数深度Transformer的表达能力

定理²：常数深度Transformer可以学习 $k$ 阶马尔可夫源的最优条件分布估计器。

关键构造：

1. 单头自注意力：模拟 $k$ 阶依赖
2. 三层网络：实现条件概率计算

证明框架：

设真实条件分布为

$$p^{\ast }(x_{t+1}\mid x_{t-k+1:t})=\frac{c(x_{t-k+1:t},x_{t+1})}{{\sum }_{x^{\prime }}c(x_{t-k+1:t},x^{\prime })}$$

其中 $c$ 是计数函数。

Transformer通过以下方式逼近：

$${\hat{p}}_{\theta }(x_{t+1}\mid x_{t-k+1:t})=\text{softmax}\left(\frac{{\varphi }_{\theta }(x_{t-k+1:t}{)}^T{\psi }_{\theta }(x_{t+1})}{\sqrt{d}}\right)$$

4.3 归纳偏置分析

Transformer在马尔可夫数据上展现出以下归纳偏置：

归纳偏置	表现
位置不变性	不同位置的马尔可夫结构相同
全局注意力	理论上可以访问所有历史
软记忆	通过注意力权重编码转移概率

4.4 实验验证

设置：合成马尔可夫数据

模型	$k=2$ 困惑度	$k=5$ 困惑度	$k=10$ 困惑度
BiLSTM	45.2	52.1	61.3
Transformer (1层)	38.7	47.8	58.9
Transformer (3层)	35.1	41.2	52.4
理论最优	32.5	38.7	48.9

5 Mamba vs Transformers：马尔可夫视角

5.1 Mamba的选择性机制

Mamba的核心是选择性状态空间模型（Selective SSM）：

连续时间形式：

$$\frac{dh(t)}{dt}=Ah(t)+B(t)x(t)$$ $$y(t)=C(t)h(t)+D(t)x(t)$$

离散化：

$$h_{t+1}=\bar{A}{h}_t+{\bar{B}}_t{x}_t$$ $$y_t=C_t{h}_t$$

其中 $B_t,C_t$ 是输入依赖的（由选择性机制产生）。

5.2 与马尔可夫链的联系

关键洞察：Mamba的选择性机制使其能够学习最优的马尔可夫估计器！

定理³：单层Mamba可以学习 $k$ 阶马尔可夫源的拉普拉斯平滑估计器，且在贝叶斯和极小极大意义下都是最优的。

拉普拉斯平滑估计器：

$$\hat{p}(x_{t+1}\mid x_{t-k+1:t})=\frac{c(x_{t-k+1:t},x_{t+1})+\alpha }{{\sum }_{x^{\prime }}[c(x_{t-k+1:t},x^{\prime })+\alpha ]}$$

其中 $\alpha >0$ 是平滑参数。

5.3 卷积与马尔可夫估计

Mamba使用卷积机制实现状态转移：

$$y_t=\sum _{i=0}^k{K}_i\cdot x_{t-i}$$

与马尔可夫链的关系：

• 核 $K_i$ 编码 $i$ 阶转移概率
• 卷积和实现边缘化：${\sum }_{i}p(x_{t+1}\mid x_{t-i})p(x_{t-i})$
• 选择性机制学习最优的 $K_i$

5.4 对比分析

特性	Transformer	Mamba
上下文建模	全局注意力 $O(T)$	局部卷积 $O(k)$
马尔可夫阶数	理论上无限	固定窗口 $k$
参数效率	$O(T^2)$ 注意力	$O(k)$ 核
最优估计器	需要多层	单层即可
推理速度	$O(T^2)$	$O(T)$

5.5 何时Mamba优于Transformer

适合Mamba的场景：

• 马尔可夫性质明显：数据具有局部依赖结构
• 长序列推理：需要 $O(T)$ 复杂度
• 资源受限：参数效率重要

适合Transformer的场景：

• 非马尔可夫数据：存在长距离非局部依赖
• 需要精确检索：上下文信息必须完整保留
• 多模态融合：注意力机制更灵活

6 马尔可夫链蒙特卡洛与深度学习

6.1 SGD作为近似MCMC

随机梯度下降可以被理解为随机近似蒙特卡洛方法：

目标分布：后验 $p(\theta \mid \mathcal{D})\propto p(\mathcal{D}\mid \theta )p(\theta )$

SGD更新：

$${\theta }_{t+1}={\theta }_t-{\eta }_t\nabla \log p({\theta }_t)+\sqrt{2{\eta }_t}{\xi }_t$$

其中 ${\xi }_t\sim \mathcal{N}(0,I)$ 是噪声。

对应关系：

MCMC	SGD
提议分布	梯度方向
接受概率	隐式
平稳分布	后验分布
遍历均值	训练终点

6.2 马尔可夫链的设计

在深度学习中，我们可以设计马尔可夫链来实现特定目的：

温度退火链：

$$T_t=T_0\cdot {\gamma }^t,0<\gamma <1$$

对比散度（Contrastive Divergence）：

使用 $k$ 步Gibbs采样近似MCMC：

def contrastive_divergence(model, data, k=1):
    """CD-k算法"""
    # 正相位：数据
    pos_grad = compute_grad(model, data)
    
    # 负相位：k步Gibbs采样
    neg_data = data.clone()
    for _ in range(k):
        neg_data = gibbs_step(model, neg_data)
    neg_grad = compute_grad(model, neg_data)
    
    # 梯度近似
    return pos_grad - neg_grad

7 马尔可夫决策过程与强化学习

7.1 MDP基础

**马尔可夫决策过程（MDP）**是序列决策的数学框架：

五元组：$(\mathcal{S},\mathcal{A},P,R,\gamma )$

• $\mathcal{S}$：状态空间
• $\mathcal{A}$：动作空间
• $P(s^{\prime }\mid s,a)$：转移概率
• $R(s,a)$：奖励函数
• $\gamma$：折扣因子

7.2 深度强化学习中的马尔可夫假设

值函数依赖于马尔可夫假设：

$$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^{t}R(s_t,a_t)\mid s_0=s\right]$$

非马尔可夫深度强化学习：

当状态不是完备的马尔可夫状态时，需要使用循环网络或注意力机制来捕获历史信息：

$$V^{\pi }(s_t,h_t)={\mathbb{E}}_{\pi }\left[\sum _{\tau =t}^{\infty }{\gamma }^{\tau -t}R(s_{\tau },a_{\tau })\mid s_t,h_t\right]$$

其中 $h_t$ 是历史编码。

8 实践应用

8.1 马尔可夫语言模型实现

import torch
import torch.nn as nn
import torch.nn.functional as F
 
class MarkovLanguageModel(nn.Module):
    """k阶马尔可夫语言模型"""
    def __init__(self, vocab_size, embed_dim, hidden_dim, k=5):
        super().__init__()
        self.k = k
        self.embedding = nn.Embedding(vocab_size, embed_dim)
        
        # 位置编码的k阶马尔可夫层
        self.markov_gru = nn.GRU(
            input_size=embed_dim,
            hidden_size=hidden_dim,
            batch_first=True
        )
        
        # 发射层
        self.emission = nn.Linear(hidden_dim, vocab_size)
        
    def forward(self, x):
        """
        x: (batch_size, seq_len)
        返回: (batch_size, seq_len, vocab_size)
        """
        # 嵌入
        emb = self.embedding(x)  # (B, L, E)
        
        # k阶马尔可夫处理
        # 截断到最近k个token
        if emb.size(1) > self.k:
            emb = emb[:, -self.k:, :]
        
        # GRU前向
        output, _ = self.markov_gru(emb)  # (B, L', H)
        
        # 发射概率
        logits = self.emission(output)  # (B, L', V)
        
        return logits
    
    def loss(self, x):
        """语言模型交叉熵损失"""
        logits = self.forward(x[:, :-1])
        target = x[:, 1:]
        return F.cross_entropy(
            logits.reshape(-1, logits.size(-1)),
            target.reshape(-1)
        )

8.2 马尔可夫链采样

def markov_chain_sampling(model, start_token, num_steps, temperature=1.0):
    """基于马尔可夫链的文本生成"""
    model.eval()
    tokens = [start_token]
    
    with torch.no_grad():
        for _ in range(num_steps):
            # 构建输入
            input_ids = torch.tensor([tokens[-model.k:]]).long()
            
            # 前向传播
            logits = model(input_ids)
            next_token_logits = logits[0, -1] / temperature
            
            # 采样下一个token
            probs = F.softmax(next_token_logits, dim=-1)
            next_token = torch.multinomial(probs, 1).item()
            
            tokens.append(next_token)
    
    return tokens

8.3 马尔可夫链收敛性诊断

def diagnose_markov_convergence(sequence, lag=1):
    """诊断马尔可夫链的收敛性"""
    # 自相关函数
    def autocorrelation(x, lag):
        n = len(x)
        x_mean = np.mean(x)
        x_var = np.var(x)
        return np.array([
            np.correlate(x[:n-lag], x[lag:])[0] / ((n - lag) * x_var)
            for lag in range(lag)
        ])
    
    acf = autocorrelation(sequence, lag)
    
    # Geweke检验
    from scipy import stats
    n = len(sequence)
    fraction = 0.1
    
    first = sequence[:int(n * fraction)]
    last = sequence[int(n * (1 - fraction)):]
    
    z_score = (np.mean(first) - np.mean(last)) / np.sqrt(
        np.var(first) / len(first) + np.var(last) / len(last)
    )
    
    p_value = 2 * (1 - stats.norm.cdf(abs(z_score)))
    
    return {
        'autocorrelation': acf,
        'geweke_z': z_score,
        'geweke_p': p_value,
        'converged': p_value > 0.05
    }

9 总结与展望

马尔可夫链为理解深度学习提供了强大的理论工具：

核心发现：

• LLMs可以形式化为有限状态马尔可夫链
• Transformer可以学习任意阶马尔可夫源的估计器
• Mamba通过选择性机制实现马尔可夫最优估计
• SGD可以理解为隐式MCMC方法

未来方向：

• 更精细的马尔可夫阶数分析
• 非平稳马尔可夫过程与在线学习
• 马尔可夫链设计与架构自动搜索
• 量子马尔可夫链与量子深度学习

---

参考文献

Footnotes

1. LLMs as Markov Chains: Stationary Distributions and Temperature Control. arXiv:2410.02724. 2024. ↩ ↩²

2. Transformers Can Learn k-th Order Markov Sources. ICLR 2025. ↩ ↩²

3. Mamba vs Transformers on Markov Data: Statistical Optimality. arXiv:2502.10178. 2025. ↩