🤖 machine learning

Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

本文建立了保证置换不变神经网络通用性所需的嵌入维度的新下界，为 Deep Sets 提供了正确的最小维度，并为 $k$ -元 Janossy 池化给出了首个非平凡下界。

原作者： Ali Syed, Aditya Nambiar, Jonathan W. Siegel

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Ali Syed, Aditya Nambiar, Jonathan W. Siegel

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

想象一下，你正在尝试教计算机理解一袋弹珠。无论你是一次取出一颗、两颗，还是全部一次性取出，这袋弹珠本身都是一样的。在数学和机器学习中，这被称为置换不变性。计算机需要学习一条规则，无论物品的顺序如何被打乱，该规则都能适用。

构建这些“抗打乱”计算机的两种流行方法被称为Deep Sets（深度集合）和Janossy Pooling（雅诺西池化）。

Deep Sets 就像把每一颗弹珠都拿出来，根据其形状涂上特定的颜色，然后将所有涂好色的弹珠倒入一个桶中混合。计算机只能看到桶中最终混合后的颜色。
Janossy Pooling 则稍微复杂一些。它不只是观察单颗弹珠，而是观察弹珠的组（对、三元组等），给这些组上色，然后进行混合。这使得计算机能够看到弹珠之间是如何相互作用的。

这篇论文回答的核心问题是：这个“桶”（即隐藏记忆空间）需要有多大，才能保证计算机能够学习关于这些弹珠的任何可能规则？

如果桶太小，计算机就会困惑，无法区分不同的弹珠袋。如果它足够大，它就能学习任何事物。

问题：“桶”的大小之谜

科学家们已经知道在简单情况下（例如当弹珠仅仅是直线上的数字时）桶需要有多大。但是，当弹珠变得复杂时（拥有许多特征，如大小、颜色和纹理同时存在），没有人知道所需的最小尺寸。

本文的作者希望找到使系统达到完美所需的隐藏记忆（称为“嵌入维度”）的最小尺寸。

新工具：“对跖”技巧

为了解决这个问题，作者发明了一种基于著名**博苏克 - 乌拉姆定理（Borsuk-Ulam Theorem）**的新数学技巧。

类比：
想象你有一个地球仪（球体）。该定理指出，如果你试图用有限数量的颜料桶给整个地球仪上色，你不可避免地会遇到一个问题：你不得不给地球仪上两个相对的点（如北极和南极）涂上完全相同的颜色，即使这两个点代表完全不同的事物。

作者利用这一思想证明，如果计算机的“桶”太小，从数学上讲，它就无法区分两个截然不同的弹珠袋。计算机会“卡住”，将它们视为相同，尽管它们并非如此。

发现：多大才算足够大？

利用这个“地球仪”技巧，作者计算了不同场景下的最小桶尺寸：

1. 对于 Deep Sets（一次观察一颗弹珠）：
他们证明，桶的大小必须大致为 $d \times (n - 1)$ 。

这意味着： 如果你有 $n$ 颗弹珠，且每颗弹珠有 $d$ 个特征，计算机需要的记忆空间必须随着弹珠数量和其复杂度的增加而增长。
为何重要： 在此之前，我们并不确切知道复杂度（ $d$ ）的影响有多大。现在我们知道，记忆需求必须随复杂度线性增长。这就像意识到，要整理一个有 100 个玩具的杂乱房间，你需要的空间不仅仅是 100 个玩具的空间，而是 100 个玩具乘以每个玩具的复杂程度。

2. 对于 Janossy Pooling（观察弹珠组）：
他们证明了针对观察组（如对或三元组）的第一个非平凡规则。桶的大小必须大致按 $(d \times n)^{1/k}$ 增长。

这意味着： 即使你让计算机通过观察弹珠组来更好地理解它们，它仍然需要大量的记忆空间。随着你增加弹珠数量或使其更复杂，记忆空间仍然必须增长。
“首次”成就： 这是首次有人证明，对于大于 1 的组，记忆尺寸必须随着物品数量的增加而增加。

数学背后的“原因”

论文解释说，如果计算机的“编码器”（即给弹珠上色的部分）是固定的，不能根据特定任务改变，那么证明它需要一个大桶很容易。但真正的挑战在于，当编码器可以改变以适应任务时。

作者表明，即使使用灵活的编码器，如果桶太小，你总是可以构造出两个不同的弹珠袋，让计算机产生混淆。这就像试图将一个巨大且复杂的 3D 拼图塞进一个小小的鞋盒里；无论你如何扭曲这些碎片，如果不弄破盒子或丢失碎片，它们就是放不进去。

总结

目标： 确定 AI 完美理解数据集（如点云）所需的最小记忆尺寸。
方法： 利用拓扑学技巧（博苏克 - 乌拉姆定理）表明，过小的记忆空间会迫使 AI 混淆不同的输入。
结果：
- 对于简单的"Deep Sets"，记忆需求必须与物品数量及其复杂度的乘积成正比。
- 对于"Janossy Pooling"（观察组），尽管数学上更为复杂，记忆需求仍然必须随着物品数量和复杂度的增加而显著增长。
结论： 你无法在数学上作弊。要完美处理复杂且无序的数据，你的神经网络需要一个随数据规模和复杂度而扩展的隐藏记忆空间。不存在一个能包办一切的“神奇小桶”。

技术摘要：Deep Sets 与 Janossy 池化通用性的嵌入维度下界

问题陈述
本文探讨了置换不变神经网络架构（特别是 Deep Sets 及其推广形式 Janossy 池化）通用性的理论问题。尽管已确立这些架构能够逼近任意连续置换不变函数，但一个关键的未决问题仍然存在：确定保证这种通用性所需的最小嵌入维度 $M$ （即潜在维度）。

先前的工作提供了上界（例如，对于 $d>1$ 的 Deep Sets， $M \le 2nd + 1$ ）以及平凡下界（例如，对于 $d=1$ ， $M \ge n$ ）。然而，对于 $d > 1$ 的 Deep Sets 以及 $k > 1$ 的 $k$ 元 Janossy 池化，此前尚不存在随环境维度 $d$ 缩放的非平凡下界。本文聚焦于定义域 $K = [0, 1]^d$ 上的标量输出情况（ $p=1$ ），将 $M_{univ}(d, n, k)$ 定义为实现通用性所需的最小嵌入维度。

方法论
作者引入了一种基于Borsuk-Ulam 定理的新颖技术，以建立嵌入维度的下界。方法论通过以下几个关键步骤展开：

归约至索引 Janossy 池化：作者首先证明，如果标准的 $k$ 元 Janossy 架构具有通用性，则意味着一个更大的、非不变类（称为“索引 Janossy 池化”）也具有通用性。在这种索引变体中，编码器函数 $\phi_{i_1, \dots, i_k}$ 被允许依赖于输入元组的具体索引，而不是在所有置换之间共享。这种归约使得作者能够为索引类证明下界，这些下界自动适用于原始对称类。
有限差分刚性：建立了一个关键引理，表明索引 Janossy 潜在映射满足特定的“有限差分刚性”。如果映射在网格的“轴”子集（其中至少一个坐标为零）上一致，则它必须在整个网格上一致。这一性质将编码器在稀疏输入集上的行为与其在稠密网格上的行为联系起来。
Borsuk-Ulam 构造：为了证明下界，作者在输入空间内构造了两个不相交的紧集 $E_+$ 和 $E_-$ 。他们利用 Borsuk-Ulam 定理证明，如果嵌入维度 $M$ 过小（具体而言，如果 $M$ 小于某个推导出的阈值），则任何映射到 $\mathbb{R}^M$ 的连续编码器 $\Phi$ 必须将一对对径点（一个来自 $E_+$ ，一个来自 $E_-$ ）映射到同一个潜在向量。
碰撞论证：通过构造一个连续目标函数 $g$ ，使其在 $E_-$ 和 $E_+$ 上分别取不同值（0 和 1），作者表明，如果编码器将这些集合中的点映射到同一个潜在向量，则没有任何解码器 $\rho$ 能以小于 $1/2$ 的误差逼近 $g$ 。这一矛盾证明了假设的维度 $M$ 不足以实现通用性。

主要贡献与结果

Deep Sets ( $k=1$ ) 的新下界：本文证明，对于作用于 $\mathbb{R}^d$ 中 $n$ 个点集合的 Deep Sets，最小嵌入维度满足：
$M_{univ}(d, n, 1) \ge d(n - 1)$
这是首个随环境维度 $d$ 增长的 $d > 1$ 情况下的下界。结合现有的上界 $2nd + 1$（来自 Dym–Gortler），这确立了所需维度按 $\Theta(nd)$ 缩放（忽略常数因子）。对于 $d=1$ ，该界限给出 $n-1$ ，恢复了已知的对 $n$ 的线性依赖（直至一个加性常数）。
$k$ 元 Janossy 池化 ( $k > 1$ ) 的首个非平凡下界：对于一般的 $k$ 元 Janossy 池化，作者推导出了首个依赖于 $d$ 的非平凡下界。结果为：
$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$
这一结果表明，即使存在有限阶交互（ $k > 1$ ），所需的潜在维度也必须随环境维度 $d$ 和集合大小 $n$ 增长。
技术框架：本文提供了一个严格的框架，通过将对称架构归约至索引架构，并对潜在空间映射应用拓扑障碍（Borsuk-Ulam），来分析通用性。

意义与局限性
本文声称，这些结果解决了先前文献中强调的关于置换不变网络维度要求的重大未决问题。具体而言，它证实了对于 Deep Sets，嵌入维度必须随 $n$ 和 $d$ 线性缩放，纠正了此前仅在 $d>1$ 时已知仅依赖于 $n$ 的界限的空白。对于 $k$ 元池化，它确立了交互作用并不能消除随 $d$ 增长的维度需求。

作者指出了当前构造中的具体局限性：

对于 Deep Sets ( $k=1$ )，界限为 $d(n-1)$ 而非 $dn$。这种“损失”一个点是因为证明策略需要一个变量块来分离 Borsuk-Ulam 论证中使用的两个不相交紧集。
对于 $k > 1$ ，下界中的指数 $1/k$ 是当前构造的局限性，该构造使用 $k$ 个基变量来标记球面上的区域。这使得推导出的下界与从 Deep Sets 继承的 $O(nd)$ 上界之间存在巨大差距。

本文结论指出，确定 $d$ 、 $n$ 和 $k$ 的确切依赖关系，并为有限阶 Janossy 池化证明匹配的上界和下界，仍然是一个未决问题。

问题：“桶”的大小之谜

新工具：“对跖”技巧

发现：多大才算足够大？

数学背后的“原因”

总结

类似论文