🤖 machine learning

Path-dependent Discrete Amortized Inference

本文提出了“路径依赖型离散摊销推理”（Path-dependent Discrete Amortized Inference），该方法通过利用可学习的潜在动力系统取代标准的马尔可夫假设，增强了从非归一化后验分布中进行离散采样的能力，从而使策略能够利用完整的轨迹历史来克服状态别名问题，并提高收敛性与探索能力。

原作者： Tiago da Silva, Esmeralda S. Whitammer, Salem Lahlou

发布于 2026-08-11

📖 1 分钟阅读☕ 轻松阅读

CC0 1.0

原作者： Tiago da Silva, Esmeralda S. Whitammer, Salem Lahlou

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图教一个机器人如何一步步构建复杂的结构，比如一个乐高城堡或一条 DNA 链。这个机器人有一个“目标表”（一个数学地图），告诉它哪些最终结构是最有价值的。挑战在于，机器人不仅仅是挑选出最好的最终城堡，它必须在实现目标的过程中做出数百万个微小的决策。在人工智能领域，这被称为“从分布中采样”。对于平滑、连续的事物（如绘制曲线），计算机拥有强大的工具来进行此类操作。但当任务涉及构建离散、块状的事物（如图、句子或化学分子）时，情况就会变得非常棘手。可能性的空间如此巨大且崎岖不平，以至于标准方法往往会陷入困境、感到困惑或无法找到最佳设计。这就是一种较新的方法——GFlowNets 发挥作用的地方。把 GFlowNets 想象成一支聪明的建筑队，它们通过将构建过程视为一场游戏，其中每一步都是马尔可夫决策过程（MDP）中的一次移动，从而学习构建这些物体。在这个游戏中，机器人只根据当前的构建状态来决定下一步行动，而忽略它是如何到达那里的历史过程。

然而，这里有一个陷阱。就像人类建筑师可能会忘记自己在三步之前走错了路，并继续犯同样的错误一样，一个只看当前状态的机器人可能会感到困惑。这种情况被称为“状态别名”（state aliasing），即两种截然不同的构建历史在机器人眼中看起来完全一样，导致它做出了错误的决策。你即将阅读的论文正是针对这一特定问题。作者 Tiago da Silva 及其同事认为，“只看当前状态”这一规则过于局限。他们提出了一种教导这些建筑师的新方法：给他们一个记忆。机器人不再仅仅看到当前的乐高塔，它还应该记住它构建这座塔的整个路径。通过添加一个“潜在动力系统”（latent dynamical system）——一种高级的说法，即一个随着机器人构建而更新的内置记忆——他们展示了机器人可以学得更快，并能构建出更复杂、更好的结构。他们从数学上证明了这种“路径依赖”的方法可以解决旧有的“无记忆”方法无法解决的问题，并通过实验表明其效果更好。

问题所在：患有失忆症的机器人

想象你在玩一个搭建积木塔的游戏。你从底部开始，每一步你可以向左添加一个积木、向右添加一个，或者停止。你的目标是搭建一座符合特定复杂颜色模式的塔。

在旧的方法中（称为马尔科夫（Markovian）方法），制造塔的机器人只观察塔此时此刻的状态。它不记得自己先加的是红积木还是蓝积木；它只看到当前的形状。这对于简单的塔来说没问题。但想象一下一个棘手的场景：你有两种不同的方式来建造一座塔，它们在第 10 步时看起来完全一样，但其中一条路径通向一件精美的杰作，而另一条则通向一个摇摇欲坠的烂摊子。因为机器人在第 10 步只能看到相同的形状，它无法分辨两者的区别。这就像患有失忆症。在论文中，作者称之为状态别名（state aliasing）。机器人感到困惑，因为两种不同的历史看起来是一样的，所以它无法学习正确的策略来构建杰作。

作者表明，这不仅仅是一个小故障；这是一个根本性的限制。即使你给机器人一个超级聪明的大脑（深度神经网络），如果它被迫只能观察当前状态，它在逻辑上无法学会解决某些复杂的谜题。他们用数学证明了这一点，即“无记忆”的机器人被困在了一个可能性之盒中，而拥有记忆的机器人则拥有一个更大的游戏空间。

解决方案：给机器人一本日记

为了解决这个问题，作者引入了一种他们称之为路径依赖离散摊销推理（Path-Dependent Discrete Amortized Inference）的新方法。机器人不再仅仅观察当前的塔，它现在随身携带了一本日记（或一个“潜在动力系统”）。

每当机器人添加一个积木时，它不仅更新塔的状态，还会更新它的日记。日记记录了构建这座塔的整个旅程。当机器人需要决定下一步该做什么时，它会同时查看塔和它的日记。

这就像一名侦探在破解谜案。一个无记忆的侦探只看现在的犯罪现场。而一个路径依赖的侦探既看犯罪现场，也看导致现状的时间线。有了日记，机器人可以分辨出“杰作路径”和“烂摊子路径”，即使塔在那个时刻看起来是一样的。机器人可以说：“啊，我知道这个形状！但在我的日记里，我看到我在三步之前向左转了，所以我知道我现在需要加一个蓝色积木，而不是红色。”

作者并不仅仅是猜测这会有用；他们使用一种被称为**自引用权重矩阵（Self-Referential Weight Matrix, SRWM）**的巧妙数学技巧构建了一种特定类型的“日记”。这是一种特殊的记忆，它会随着机器人的构建而自我更新，通过旋转和移动其内部状态来追踪独特的历史。这就像一本会在你每次写下新条目时，用秘密代码重写页面的日记，确保没有任何两个历史会被混淆。

他们的发现：更快、更聪明的建筑师

团队将他们的新型“路径依赖”机器人与旧有的“无记忆”机器人在几个标准挑战中进行了对比测试，例如构建数字集、设计 DNA 序列以及在网格世界中导航。

解决不可解之题： 在某些实验中，无记忆机器人完全无法学会正确的模式。它一直在构建错误的东西，因为它无法区分不同的路径。然而，路径依赖机器人却完美地学会了模式。作者在数学上证明了，对于某些类型的问题，训练无记忆机器人获得正确答案是不可能的，而路径依赖机器人则可以做到。
加速进程： 即使无记忆机器人最终能够学会答案，它也需要很长时间。路径依赖机器人学得更快。在一项测试中，无记忆机器人需要大约 100 倍的训练步骤才能分辨出两个相似状态之间的区别，而路径依赖机器人几乎能立即分辨出来。
更好的结果： 当他们衡量机器人的输出与完美目标之间的接近程度时，路径依赖机器人的表现始终更优。无论是生成数字集、DNA 序列还是在网格中导航，带有日记的机器人都产生了更高质量的结果。

核心启示

这篇论文表明，当我们教 AI 构建复杂的、分步式的物体时，强迫它忘记过去是一个错误的决定。通过赋予 AI 一个关于其整个旅程的“记忆”，我们释放了更高水平的智能。作者证明了这不仅仅是一个“锦上添花”的功能；它是解决某些此前无法触及的问题所必需的升级。他们不仅说“它可能有用”，还通过严密的数学和计算机模拟证明了路径依赖方法在能力和效率上都严格优于传统方法。

所以，下次当你看到 AI 试图构建复杂的东西时，请记住，它不仅仅是在看它现在所见到的东西。它还在记住它是如何到达那里的。有了一点点记忆，它就能创造出曾经不可能实现的奇迹。

技术摘要：路径依赖型离散摊销推理

问题陈述

本文解决了从给定的非归一化后验分布中采样组合式和离散对象（例如图、序列、系统发育树）的挑战。虽然最近的生成流网络（GFlowNets）进展已将此问题框架化为学习一个逐步构建对象的马尔可夫决策过程（MDP），但作者指出了标准马尔可夫假设的局限性。具体而言，马尔可夫性质——即策略仅取决于当前状态——会阻碍训练期间的信号传播，并导致**状态别名（state aliasing）**问题。在状态别名中，不同的状态对智能体而言在表示上变得不可区分，导致学习到的采样器无法为收敛到相同状态的不同轨迹区分最优动作。这一问题在奖励稀疏或具有复杂结构依赖的环境中尤为突出，因为标准的深度神经网络可能缺乏表示最优策略所需的表达能力。

方法论

为了克服这些局限性，作者提出了路径依赖型离散摊销推理（Path-dependent Discrete Amortized Inference）。其核心方法是通过引入一个可学习的状态条件潜在动力系统 $\{W_t\}_{t \ge 1}$ 来“提升（lifting）”原始 MDP 的状态空间。

1. 提升后的指向型 DAG

该方法不再使用标准的态图 $G = (S, X, E)$ ，而是在提升后的指向型 DAG $G^\star$ 上运行。状态空间从 $S$ 扩展到 $S^\star \subseteq S \times \Omega$ ，其中 $\Omega$ 是一个潜在空间（通常为 $\mathbb{R}^d$ ）。

潜在动力学： 潜在变量 $W_t$ 根据当前状态 $s_t$ 和前一潜在状态 $W_{-1}$ ，通过一个可学习的向量场 $\phi$ 确定性地演化：
$W_t = W_{t-1} + \phi(s_t, W_{t-1})$
策略依赖性： 前向策略 $p_F$ 变为路径依赖的，以 $(s_t, W_t)$ 对为条件。这使得策略能够区分导致相同状态 $s_t$ 的不同轨迹，从而有效地打破了原始状态空间的马尔可夫约束。

2. 架构：自引用权重矩阵 (SRWM)

为了高效实现潜在动力系统，作者使用了一种改进的自引用权重矩阵（Self-Referential Weight Matrix, SRWM）。

潜在状态（以权重矩阵 $W_t$ 表示）的更新规则遵循特定的递归形式：
$q_t, k_t, v_t, \beta_t = W \psi(s_t) + b$
$\bar{v}_t = W_{t-1} \zeta(k_t)$
$W_t = W_{t-1} R + \sigma(\beta_t) \cdot (v_t - \bar{v}_t) \otimes \zeta(q_t)$
关键机制： 包含一个固定的、遍历性的旋转矩阵 $R$ 至关重要。它在整个轨迹展开过程中旋转权重矩阵的特征向量。该机制旨在增强策略隐藏表示的多样性，从而比 LSTM 或 GRU 等标准循环架构更有效地缓解状态别名问题。

3. 学习目标

作者证明了现有的 GFlowNet 学习算法可以扩展到这种提升后的设置。他们证明了轨迹平衡（TB）、**子轨迹平衡（SubTB）和对比平衡（CB）**条件在提升后的 DAG 中仍然有效。

学习过程最小化了平衡方程左右两边之平方差的期望。
至关重要的是，向量场 $\phi$ 和策略网络通过在单一损失函数上进行随机梯度下降进行联合学习。
理论结果（命题 4.8）表明，如果后向策略 $p_B$ 是马尔可夫的（独立于 $W_t$ ），则最优前向策略 $p_F$ 对于未提升的状态也将是马尔可夫的。然而，当 $p_B$ 是路径依赖时， $p_F$ 可以利用完整的历史信息来实现更好的表达能力。

核心贡献

路径依赖算法： 引入了一种通用的路径依赖算法，用于离散和组合空间的摊销推理，明确解决了马尔可夫采样器的表达能力限制问题。
理论表达能力证明：
- 线性策略： 作者证明（命题 3.1），对于线性策略，路径依赖设置下的可学习分布空间严格大于马尔可夫设置。
- GNN 策略： 他们将此扩展到图神经网络（命题 3.2），表明路径依赖参数化可以区分 1-WL GNN 无法区分的状态（例如，区分在不同时间添加的边），从而严格提高了表达能力。
扩展学习理论： 论文提供了正式证明（命题 4.5 及推论 4.6, 4.7），表明标准的 GFlowNet 学习目标（TB, SubTB, CB）足以确保在提升后的路径依赖设置中的正确采样。
实证验证： 在标准基准测试（集合生成、序列设计、网格世界、Ising 模型等）上的广泛实验表明，与相似参数化的马尔可夫模型相比，路径依赖方法实现了更快的收敛和更好的拟合优度（通过全变分距离和流一致性分数衡量）。

结果

实证分析强调了几个一致的发现：

表达能力： 在 “LINES” 环境和图结构任务中，马尔可夫采样器无法学习非均匀分布或区分结构相似的状态，而路径依赖模型实现了近乎完美的拟合。
收敛性： 路径依赖模型一致地实现了更快的收敛。例如，在稀疏的 LINES 环境中，马尔可夫 ReLU 网络在区分不同状态的策略方面，比路径依赖对应模型大约需要多出 100 倍的迭代次数。
架构效率： 带有旋转矩阵的 SRWM 在收敛速度和最终性能方面均优于标准的门控 RNN（LSTM, GRU），这归功于其通过旋转机制缓解状态别名的能力。
鲁棒性： 该方法在多种任务中表现出卓越的性能，包括生物序列设计（DNA 结合亲和力）、偏好学习和 Ising 模型模拟。

重要性与主张

本文声称，通过潜在动力系统提升状态空间是离散摊销采样的必要策略，类似于哈密顿蒙特卡洛（HMC）通过增加动量变量来增强连续空间以加速收敛。作者认为：

状态别名是一个根本性的瓶颈： 马尔可夫采样器无法根据轨迹历史区分状态的能力，是复杂组合空间中表现不佳的主要原因。
路径依赖在理论上更优： 理论结果证实，路径依赖参数化严格扩展了可学习分布的假设类。
实际适用性： 所提出的方法是标准 GFlowNet 训练的“即插即用”替代方案，仅需修改状态表示并使用在提升空间中依然有效的特定学习目标。

作者总结道，设计用于部分可观测 MDP（POMDP）的算法非常适合离散摊销采样。他们指出，虽然目前的重点是确定性潜在动力学，但随机动力学的可行性仍是未来研究的一个开放问题。这项工作并不声称解决了所有的离散采样问题，而是提供了一个通用的框架，用以缓解当前马尔可夫方法面临的特定局限性。