🤖 machine learning

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models

本文通过引入一种基于截断格拉伯动力学（truncated Glauber dynamics）的新型低度近似，提出了一种在具有高效局部采样器的图形模型下学习 $\mathsf{AC}^0$ 电路的拟多项式时间算法，从而将先前的学习保证扩展到了不需要多项式增长的任意有界度图。

原作者： Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

发布于 2026-07-10

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图教一个机器人识别一个非常拥挤、混乱的房间里的模式。这个房间里充满了人（变量），他们都在向邻居低声耳语。如果你向一个人大声提问，他给出的答案很大程度上取决于他的朋友们在说什么。这就是科学家们所说的 吉布斯分布（Gibbs distribution） 或 图模型（graphical model）：一个所有事物都相互连接且相互关联的系统，这使得预测或学习变得异常困难。

长期以来，计算机科学家拥有一种学习模式的“超能力”，但这种能力只适用于一个“安静的房间”，即每个人都独立地大声喊出答案（称为 乘积分布/product distribution）。2026年，一组研究人员（Feng, Yang, Yu, and Zhang）设法将这种超能力带入了嘈杂拥挤的房间，但他们遇到了一个障碍：他们只能在房间不是“太大”或“太复杂”的情况下做到这一点（具体来说，如果一定距离内的人数增长得不会太快，即所谓的 多项式增长/polynomial growth 规则）。

重大突破
这篇论文证明了，要教机器人学习，并不需要那个“房间大小”的规则。作者们展示了，只要房间拥有一个 局部采样器（local sampler）——一种聪明的办法，通过只观察一个人的微小局部邻居圈子就能弄清楚那个人在说什么——你就可以教机器人学习 AC0 电路（AC0 circuits）（这本质上是简单的、浅层的决策机器）并获得极高的准确率。

他们不仅仅是在猜测；他们用数学证明了这一点。他们构建了一种新的学习算法，该算法以 拟多项式时间（quasipolynomial time） 运行（虽然不是瞬间完成，但足够实用），并且适用于任何具有有限每人邻居数量的图，即使是一个像 扩展图（expander graph） 或 随机网络（random network） 那样规模巨大且复杂的网络（其中人群呈指数级增长）。

他们是如何做到的：“时空旅行”侦探
为了实现这一点，作者们使用了一个精妙的技巧，涉及一场“反向进行的传声游戏”。

正向游戏（采样器）： 想象一个游戏，你从一张白纸开始，在一个圆圈中逐一更新人们的观点。为了让过程可预测，他们引入了“魔法骰子”（称为 标记/marks）。如果你掷出了特定的数字，一个人的观点就会被强制固定；如果你掷出了另一个数字，他就会观察自己的邻居。通过按特定顺序掷这些骰子，你可以模拟整个房间的状态。
反向游戏（逆转器）： 这是神奇之处。通常，如果你知道房间的最终状态，你很难猜出掷出了哪些骰子才得到了这个结果。但作者意识到，如果“骰子”是以一种让最终结果不依赖于游戏如何开始的方式（这是一个被称为 确定性标记序列/determining mark sequence 的概念）来掷出的，那么你可以倒着运行这个游戏。
局部侦探： 他们证明了对于许多系统（例如 硬核模型/hard-core model，即邻居不能同时处于“占据”状态；或 伊辛模型/Ising model，即邻居倾向于达成一致或产生分歧），你只需要观察一小簇特定的朋友及其特定的骰子掷点，就能推断出一个人的最终观点。你不需要知道整个房间的历史。

“截断”技巧
这里有趣的部分在于：作者意识到这些反向侦探游戏通常结束得非常快。这种“影响”起始条件的效应会迅速消退。因此，他们决定 缩短游戏。他们告诉侦探：“在检查了大约 $\log(n)$ 个朋友后就停止。”

因为侦探几乎总是能在达到时间限制前完成任务，所以截断游戏引入的误差几乎可以忽略不计。这种“截断”将一个复杂的、看似无限的过程变成了一个简单的、短小的步骤列表。这个短列表可以被写成一个 低阶多项式（low-degree polynomial）（一种简单的数学公式）。由于公式很简单，机器人可以使用标准技术快速学习它。

他们否定了什么
该论文明确反对了认为需要“多项式增长”规则（即房间不能增长得太快）才能学习这些模式的观点。之前的研究认为：“如果房间增长得太快，我们就无法学习它。”而这篇论文说：“不！只要你能进行局部观察，房间的大小就无关紧要。”

他们还澄清了，这不是关于学习房间本身的结构（即搞清楚谁是谁的朋友）。那是另一个问题。这篇论文假设你已经知道了房间的布局，只是想学习一个在其中运行的具体规则（函数）。

证明与数据
作者们不仅仅是在计算机上模拟这个过程；他们提供了严密的 数学证明。

他们证明了对于 硬核模型（即邻居不能同时为“开启”状态），如果“亚稳态/亚稳态度/fugacity”（衡量人们想要“开启”程度的度量）小于大约 $1/(\Delta - 1)$ ，其中 $\Delta$ 是最大邻居数，那么学习工作就能完成。这是一个非常紧凑、近乎完美的条件。
对于 伊辛模型（即邻居之间存在相互作用），他们证明了如果相互作用强度 $\beta$ 在特定的范围（大约 $1 - \frac{1}{2\Delta} < \beta < 1 + \frac{1}{2\Delta}$ ）内，学习工作就能完成。
该学习算法大约需要 $n^{\log^{O(d)}(n/\varepsilon)}$ 个样本和时间，其中 $n$ 是人数， $d$ 是电路的深度， $\varepsilon$ 是你可以容忍的误差。

底线
这篇论文是一个 经过证明的 结果。它将“局部采样器”（让你窥探系统一小部分的工具）与“学习理论”（教计算机寻找模式）联系了起来。它表明，即使在一个混乱的、高度连接的世界里，只要你有一种局部窥探的方法，你就可以教机器理解大局，而无需要求世界规模小巧或简单。这就像是教一名侦探通过一次只采访几个街区的方式来解决全城的谜案，证明了你并不需要采访每一个人也能获得真相。

技术摘要：在局部可采样图模型下学习 $\text{AC}^0$

问题陈述

本文研究了在相关概率分布下学习常数深度布尔电路（具体为 $\text{AC}^0$ 类）这一基础问题。虽然 Linial, Mansour, 和 Nisan 的开创性工作 (LMN93) 确立了在均匀分布下 $\text{AC}^0$ 电路具有低度傅里叶近似（从而实现准多项式时间学习），但在相关分布下扩展这些保证仍然是一个重大挑战。

作者关注的是在给定由图形模型（马尔可夫随机场）定义的 Gibbs 分布 $\mu$ 下，学习未知函数 $f \in \text{AC}^0$ 的问题，其中样本为 $(x, f(x))$ 。之前的进展（如 Chandrasekaran 等人，CGMV26）为有界度图上的 Gibbs 分布提供了学习保证，但仅限于一个严格的多项式增长假设（即距离 $\ell$ 内的顶点数随 $\ell$ 的多项式级增长）。该假设排除了像扩展图（expanders）和 Erdős-Rényi 随机图这样体积随半径呈指数级增长的重要图类。

核心问题是：能否在不依赖多项式增长要求的情况下，在一般有界度图的 Gibbs 分布下学习 $\text{AC}^0$ ？

方法论

本文引入了一个通过利用**局部采样器（local samplers）**来绕过多项式增长障碍的新框架。其核心方法论是通过将近似过程从用于采样过程的随机比特乘积空间转移，来构建 $f$ 在 Gibbs 测度 $\mu$ 下的低度多项式近似。

1. Samp–InvSamp 框架

作者改编了抽象的 Samp–InvSamp 框架。目标是通过以下步骤近似 $\mu$ 下的 $f$ ：

Samp（采样）： 一个将随机标记字符串 $\rho$ 映射到配置 $\sigma \sim \mu$ 的采样器。
InvSamp（逆采样）： 一个给定配置 $\sigma$ ，恢复与采样路径一致的随机标记字符串 $\rho$ 的逆采样器。

如果 $f \circ \text{Samp}$ 可以被乘积空间上的低度多项式 $g$ 近似，且如果 $\text{InvSamp}$ 具有低“度”（即其输出仅依赖于 $\sigma$ 的少数坐标），那么 $g \circ \text{InvSamp}$ 就提供了 $f$ 在 $\mu$ 下的低度近似。

2. 系统扫描 Glauber 动力学作为采样器

作者没有依赖强空间混合（这需要多项式增长来限制依赖半径），而是使用**系统扫描 Glauber 动力学（Systematic-Scan Glauber Dynamics）**作为采样器。

前向过程： 链从一个固定配置 $\sigma_0$ 开始，并按循环顺序 $u_1, \dots, u_T$ 更新顶点。每次更新都通过由随机“标记” $\rho_t$ 驱动的确定性规则 $\psi_t$ 来实现。
确定标记序列： 一个关键见解是，如果标记序列 $\rho$ 是“决定性的（determining）”，那么最终配置 $\sigma_T$ 将独立于初始配置 $\sigma_0$ 。这使得固定初始化的采样器可以表现得如同从平稳分布 $\mu$ 中初始化一样。
局部采样器： 作者利用了**局部计算算法（LCAs）**进行采样。这些是能够通过查询标记序列和初始配置的局部邻域来解决特定顶点 $v$ 自旋的自动机。至关重要的是，只要 Gibbs 分布满足特定的混合条件，这些局部采样器即使在具有指数增长的图上也能以高概率快速终止。

3. 截断与低度近似

为了确保生成的多项式具有低度：

局部采样器（正向和反向）在多项式对数步数后进行截断。
作者证明了截断误差很小，因为采样器未能在截断深度内终止的概率随之呈指数级衰减。
截断后的采样器/逆采样器与 $\text{AC}^0$ 函数 $f$ 的复合，产生了一个可以在标记空间上由常数深度、多项式规模电路计算的函数。
利用 Tal 的傅里叶尾部界限在有限乘积域上的扩展（第 4 节），他们展示了此类电路具有低度多项式近似。

核心贡献

消除多项式增长假设： 本文为一般有界度图上的 Gibbs 分布下的 $\text{AC}^0$ 建立了学习保证，消除了此前工作 (CGMV26) 所需的多项式增长假设。
LCAs 与学习之间的新联系： 该工作架起了局部计算算法（特别是用于 Gibbs 分布的局部采样器）与布尔函数学习之间的桥梁。它证明了存在高效局部采样器意味着存在 $\text{AC}^0$ 的低度近似。
广义低度近似： 作者提供了 $\text{AC}^0$ 电路在布尔立方体之外的通用有限乘积域上的低度近似定理的扩展（定理 4.2），这对于处理采样模拟器中使用的非布尔标记字母是必要的。
双向良好局部采样器条件： 他们定义了一个“双向良好局部采样器”条件（条件 5.6），确保正向采样和反向求逆都可以局部且高效地执行。

结果

本文提供了在任意有界度图上的特定图形模型下学习 $\text{AC}^0$ 的准多项式时间算法：

硬核模型（Hard-Core Model）： 当 $\lambda < (1-\eta)/(\Delta-1)$ 时可以学习。这一条件仅比经典的 Dobrushin 阈值强一个常数因子，而之前的强空间混合条件要求 $\lambda < (\Delta-1)^{\Delta-1}/(\Delta-2)^\Delta$ 。
软约束模型（包括 Ising 模型）： 对于满足归一化软约束条件的相互作用矩阵，学习是可能的。对于边活性为 $\beta$ 的 Ising 模型，当 $\beta$ 在 1 的常数因子范围内时（具体为 $1 - \frac{1-\eta}{2\Delta} < \beta < (1 - \frac{1-\eta}{2\Delta})^{-1}$ ）学习成立。
复杂度： 学习算法的运行时间为 $n^{\log^{O(d)}(n/\varepsilon)}$ ，且需要 $n^{\log^{O(d)}(n/\varepsilon)}$ 个样本，其中 $d$ 是电路深度， $n$ 是顶点的数量。隐藏的常数仅取决于度数 $\Delta$ 、电路参数以及模型的混合参数。

意义与主张

本文声称其主要意义在于规避了多项式增长的要求，从而将可学习相关分布的范围扩展到了包括扩展图和随机图在内的模型。通过将局部采样器的效率（采样文献中的一个概念）与布尔函数的学习联系起来，作者提供了一种不依赖于几何约束的、学习具有依赖性分布下的函数的鲁棒机制。

作者谦逊地将他们的贡献描述为一种“新的联系”和“框架”，并由此得到了针对硬核模型和 Ising 模型特定区间的学习器。他们并未声称解决了所有 Gibbs 分布的学习问题，而是针对那些允许高效局部采样器的模型，这涵盖了一类广泛且具有实际意义的模型。这项工作代表了在理解超越先前研究的特定几何设置、真正具有依赖性的分布下的学习方面迈出的重要一步。

技术摘要：在局部可采样图模型下学习 AC0\text{AC}^0AC0