🔢 数学

Going deep, reaching further: What can Boltzmann machines efficiently represent?

本文证明了尽管各种机器学习模型在理论上具有通用性，但更深层的架构和具有高阶交互的模型拥有严格更强的“有效覆盖范围”，从而建立了一个理论层级，解释了为什么深度玻尔兹曼机在高效表示复杂函数方面优于其浅层对应模型。

原作者： Tobias Reinhart, Gemma De les Coves

发布于 2026-10-30

📖 1 分钟阅读🧠 深度阅读

原作者： Tobias Reinhart, Gemma De les Coves

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

在现代人工智能的广阔版图中，一个困扰了研究人员数十年的持久谜题始终存在：为什么深度神经网络凭借其众多的处理层，能够持续超越其浅层网络？虽然数学定理早已证实，即使是最简单的网络在理论上也能模拟任何模式，但这些证明往往忽略了实现这一目标的实际成本。它们表明，一个浅层网络可以解决复杂问题，但前提是必须允许它增长到一种不可能的巨大规模，其所需的参数量甚至会超过宇宙中的原子总数。这种理论可能性与实际效率之间的差距，正是驱动这项针对机器学习基本极限的新型研究的核心问题。这项工作的研究人员试图理解是什么让一个模型真正具有效率，从而超越“所有通用模型都是平等的”这一观念。他们专注于两个特定的架构特征：网络的深度（指数据通过的连续层数）以及相互作用阶数（描述单个处理单元可以同时考虑多少个变量）。

这项由因斯布鲁克大学的物理学家及其巴塞罗那同事共同开展的研究表明，并非所有的机器学习模型都具有同等的潜力，即使它们拥有相同的理论潜能。研究团队证明，在标准计算复杂度假设成立的前提下，具有更深度的模型在高效表示复杂函数的能力方面具有显著优势。他们引入了一个被称为“有效触达”（efficient reach）的概念，该概念衡量了一个模型在不需要其内部设置发生爆炸式增长的情况下，能够解决多少种不同的问题。他们的研究结果显示，像深度玻尔兹曼机（Deep Boltzmann Machines）这样的深层模型，可以高效地表示大量复杂的模式，而浅层模型除非多项式层级坍缩（这在计算机科学中被广泛认为是不可能的场景），否则无法高效地模拟这些模式。相比之下，像广泛使用的受限玻尔兹曼机（Restricted Boltzmann Machines）这样的浅层模型，在同样的假设下，仅限于处理规模小得多的高效可解问题集。研究人员证明，这种局限性不仅仅是一个微小的缺陷，而是一个根本性的障碍；除非关于这些问题难度的基本假设被证明是错误的，否则浅层模型在数学上无法高效地模拟某些类型的困难计算任务，而深度模型却可以处理这些任务。

为了得出这些结论，作者借鉴了物理学中的框架，将机器学习模型视为相互作用的粒子系统。他们分析了这些系统如何在最低能量状态下编码信息。通过应用植根于计算复杂度理论的严密数学证明，他们表明高效表示一个函数的能力与模型的结构直接相关。具体而言，他们发现深度模型可以将简单的操作组合成复杂的运算，而浅层模型则无法做到这一点。深度模型可以逐层构建复杂的表示，通过复用之前的计算结果来构建新的内容。而缺乏这些中间层的浅层模型，必须尝试在单一步骤中描述整个复杂度，这迫使它使用指数级的资源。团队证明，这种差异创造了一个严格的等级制度：随着浅层模型相互作用阶数的增加（即它同时考虑更多的变量），它确实获得了一些能力，但永远无法追赶上深度模型的效率。

研究人员还探索了浅层模型所能达到的边界。他们发现，即使允许一个浅层模型同时考虑三个或更多变量的相互作用，它仍然逊色于具有简单二体相互作用的深度模型。这为浅层模型创造了一个效率的无限阶梯，其中相互作用阶数的每一步提升都能让模型解决稍复杂一些的问题，但这个阶梯的顶端仍严格低于深度模型的触及范围。这一等级制度通过特定的、极具挑战性的数学函数进行了测试，例如计算两个数据集模二的内积。研究表明，虽然深度模型可以高效地模拟这个函数，但浅层模型除非关于某些问题难度的计算机科学基本假设被证明是错误的，否则无法做到。

为了确保这些理论发现具有实践意义，团队对训练自这些困难函数生成数据的浅层和深度模型进行了数值实验。他们发现，对于特定的系统规模，较深的模型（特别是具有三体相互作用的模型）比其浅层对应模型学习得更快、更准确，即使两者获得的训练数据和计算预算相同。然而，研究人员明确指出，这种学习优势并未在渐近增长（asymptotic growth）中得到确立；在较大的实验规模（n=16）下，学习程序未能让两种模型都恢复目标结构。这表明，虽然深度和高阶相互作用的理论优势并非仅仅是抽象的数学奇观，但将这些优势转化为切实的学习收益，取决于特定的条件，并且并不保证随着问题规模无限增长时依然成功。这项工作为“深度网络通常表现更好”这一经验观察提供了坚实的理论基础，解释了这不仅仅是拥有更多数据或更好训练算法的问题，而是模型内部信息结构化和处理方式的一个基本属性。

这项研究的影响力超出了仅仅理解深度学习为何奏效。它提供了一个看待人工智能系统设计的新视角。通过刻画不同架构的“有效触达”，该研究表明，存在某些特定类型的难题，无论如何进行调整，浅层模型在本质上都不适合处理这些问题（假设标准的复杂度猜想成立）。这有助于研究人员避免浪费资源，试图强迫一个需要深度的架构去解决一个需要深度的任务。此外，研究还阐明了相互作用阶数的角色，表明虽然增加一个单元考虑的变量数量会有所帮助，但这并不能替代深度所提供的组合能力。研究结果证实，深度学习的成功根植于一种结构性优势，这种优势使得这些模型能够以远高于其浅层亲属的效率，在可能的解决方案空间中进行探索。

最后，这篇论文解决了关于机器学习效率性质的一个长期悬而未决的问题。它确立了深度模型的优越性并非偶然的技术现象，而是由于它们能够以浅层模型无法实现的组合表示方式进行运作，这取决于广泛接受的复杂度假设。研究人员绘制了这些模型能够高效处理以及不能高效处理的任务图景，揭示了深度架构与浅层架构之间清晰的能力鸿沟。这项工作不仅解释了深度学习为何奏效，还定义了其能力的精确边界，为未来的领域发展提供了指南。通过证明在标准假设下，某些任务本质上超出了浅层模型的有效触达范围，该研究为理解人工智能的极限与潜力设定了新的标准。

标题： 向深处探索，向远方触达：玻尔兹曼机能高效表示什么？

作者： Tobias Reinhart 和 Gemma De les Coves

1. 问题陈述

通用近似定理（UATs）为机器学习模型的表示能力提供了理论基础，证明了诸如受限玻尔兹曼机（RBMs）、深度玻尔兹曼机（DBMs）和前馈网络等模型可以近似任何属于特定类别的函数。然而，作者指出了这些定理存在的两个关键缺陷：

低效性： UATs 通常需要指数级的参数（例如隐藏单元）来表示通用的目标函数，这对于理解高效模型的实际能力几乎没有提供见解。
对深度的不敏感性： UATs 既适用于浅层模型（如只有一个隐藏层的 RBMs），也适用于深层模型（如 DBMs），这无法解释观察到的深层架构在经验上的优越性。

由此引出了两个核心问题：

（Q1）在高效表示能力方面，所有的通用机器学习模型都是平等的吗？
（Q2）如果不是，那么什么样的属性可以刻画出“高效通用模型”？

2. 研究方法

作者通过利用通用自旋模型的特征化来解决这些问题。他们建立了自旋模型的通用性（即在低能扇区内编码任意能量函数的能力）与机器学习模型通用近似能力之间的联系。

该研究方法涉及三个主要的分析框架：

模拟与近似： 作者将“模拟”定义为将目标系统的能量函数编码到源系统的低能扇区中。他们通过玻尔兹曼分布的边缘分布将此与“近似”联系起来。他们引入了高效模拟的概念，其中源系统的规模随目标系统规模呈多项式增长。
计算复杂度理论： 他们利用计算复杂度界限来区分模型类别。具体而言，他们假设多项式层级不塌缩（这是 $P \neq NP$ 的一种推广），以证明某些函数（NP-hard 和 #P-hard）无法被浅层模型高效地模拟或近似。
通信复杂度： 为了分析具有有限交互阶数（ $k$ -local）的浅层模型，他们将高效模拟能力与目标函数的通信复杂度（特别是 $k$ -方内积模 2）联系起来。

引入的关键定义包括：

可见闭包（Visible Closure）： 自旋机器学习（ML）模型的一种属性，其中可见自旋可以有效地转换为隐藏自旋（在模拟范围内），从而允许可见模拟的组合。
极大性（Maximality）： 一个模型具有“极大高效触达”是指它可以高效模拟任何其他模型能高效模拟的目标。

3. 主要贡献与结果

A. 极大模型的特征化

论文对具有极大高效触达能力的模型进行了完整的特征化。

等价性： 对于自旋模型，通用性和极大性（高效触达）是等价的。
可见闭包： 对于自旋机器学习模型（具有可见单元和隐藏单元），可见闭包是决定性属性。作者证明，对于任何自旋机器学习模型，以下三个属性中的任意两个都蕴含第三个：
1. 通用性（可以模拟所有目标）。
2. 可见闭包（可以组合可见模拟）。
3. 极大性（具有极大高效触达）。
启示： 由于 DBMs（至少有两个隐藏层）是通用且严格可见闭合的，因此它们是极大的。相比之下，RBMs 虽然是通用的，但不是可见闭合的，因此不具备极大高效触达能力。

B. 浅层模型与极大模型之间的分离

作者在假设多项式层级不塌缩的前提下，在三种表示任务中建立了浅层模型（如 RBMs）与极大模型（如 DBMs）之间的明确分离：

NP-hard 函数的模拟： 极大模型可以高效模拟伊辛模型（Ising model）的基态能量函数（这是一个 NP-hard 问题）。浅层模型则无法做到，因为这会意味着 $NP \subseteq FP/poly$ ，从而导致层级塌缩。
#P-hard 未归一化边缘分布的近似： 极大模型（特别是那些强可见闭合的模型）可以在其未归一化可见边缘分布中高效近似伊辛模型的配分函数（这是一个 #P-hard 问题）。浅层模型无法做到。
#P-hard 归一化分布的近似： 极大模型可以近似相应的归一化边缘分布概率分布。即使归一化因子对浅层模型来说在计算上可能很困难，但由于所需的相对概率仍然难以近似 #P-hard，浅层模型也无法实现。

C. 浅层模型的分离层级

论文证明，在浅层模型内部，高效触达能力并不是统一的，而是形成了一个由交互阶数（ $k$ ）索引的无限层级。

层级结构： 对于任何 $k \geq 2$ ，都存在某些函数，浅层 $k$ -local 模型无法高效模拟，但浅层 $(k+1)$ -local 模型却可以。
见证函数： 这种分离由 $k$ -方内积模 2（ $IP_k$ ）见证。浅层 $k$ -local 模型无法高效模拟 $IP_k$ （受限于通信复杂度下界），但浅层 $(k+1)$ -local 模型可以。
示例： 3-体 RBMs（3RBMs）可以高效模拟标准 2-体 RBMs 无法模拟的目标（如 $IP_2$ ）。

4. 意义与主张

作者声称，这项工作为关于深层模型和高阶交互优越性的启发式观察提供了理论基础。

交织的缺陷： 论文认为，通用近似定理的两个缺陷（忽略效率和深度）是深度交织在一起的。深度（通过可见闭包）是实现极大高效触达的必要条件。
资源权衡： 结果表明，通用模型在高效表示能力方面存在显著差异。虽然所有考虑的模型在不受约束的情况下都是通用的，但它们根据深度和交互阶数形成了丰富的效率图谱。
学习启示： 虽然主要结果关注的是高效表示的存在性，但作者通过数值实验（第 D 部分）表明，这些理论上的分离在学习性能中有所体现。具体而言，在涉及内积模 2 的任务时，3-体 RBMs 表现出了比标准 RBMs 更强的学习优势，尽管作者在声称这证明了渐近极限下的“高效可学习性”方面保持了谨慎。

5. 结论

论文得出结论，深度玻尔兹曼机（DBMs）由于其深度和可见闭包，具有极大高效触达能力，而受限玻尔兹曼机（RBMs）则是次极大的。此外，浅层模型之间的差距可以通过无限的交互阶数层级来弥补。这项工作将研究重点从单纯的通用性转向了高效通用性，证明了结构属性（如深度和交互阶数）是决定模型实际表示能力的关键因素。