When and How to Canonize: a Generalization Perspective¶
会议: NeurIPS 2026
arXiv: 2605.11008
OpenReview: https://openreview.net/forum?id=auino4yMsg
代码: https://github.com/yonatansverdlov/when_and_how_to_canonize
领域: 优化/理论
关键词: 规范化 (Canonization), 群平均 (Group Averaging), 泛化误差界, 覆盖数 (Covering Number), 希尔伯特曲线 (Hilbert Curve)
一句话总结¶
本文基于覆盖数理论建立了规范化（Canonization）、群平均与非对称模型之间的泛化误差层次体系，从理论上严格证明了连续等距规范化可达群平均的最优界而强不连续规范化会导致泛化退化至非不变性基线，并首次为 Point Transformer V3 等架构中希尔伯特曲线排序的多项式级覆盖数优势提供了严格泛化证明。
研究背景与动机¶
几何先验与对称性约束（如置换不变性、旋转平移等变性）在点云处理、图学习和分子建模中被广泛证明能够显著降低样本复杂度并改善泛化表现。传统处理对称数据的标准范式主要依赖于内生不变架构（如 DeepSets、GNN、SE(3) 等变网络）或群平均（Group Averaging）。然而，内生对称模型往往大幅限制了主干网络的设计灵活性且计算复杂度较高；完全群平均积分在置换群或大群作用下在计算上完全不可行，随机群数据增强则面临收敛缓慢的问题。为了在保留任意高效非对称骨干网络（如标准 MLP、Transformer）的同时诱导对称不变性，规范化（Canonization）成为极具吸引力的实用替代方案——它通过将每个群轨道映射到一个唯一的确定性规范代表元，仅需处理单个样本即可满足完全不变性并具备通用近似保证。
尽管规范化在点云序列化（如 Point Transformer V3 的网格排序）和分子 SMILES 表示中取得了极具竞争力的经验效果，但其泛化误差的理论基础一直缺乏严谨的研究体系。领域内存在诸多悬而未决的核心矛盾：直觉上规范化只需在单一代表元上拟合，参数空间更为紧致，但在化学分子等领域的实证中，随机数据增强却往往超越确定性规范化；更严峻的是，先验数学结论指出在许多对称场景下（例如高维点云置换群作用）全局连续的规范化在拓扑上是不可能存在的，不连续规范化对学习与泛化到底会产生怎样的影响长期缺乏定量刻画。
本文的切入角度是跳出传统的函数近似能力范式，转而利用度量空间中假设类与输入域的覆盖数（Covering Numbers）作为刻画泛化误差上界的统一量化工具。核心 idea：通过度量空间的覆盖数建立对称学习泛化层次，证明规范化模型的泛化界上受内生不变/群平均模型的商空间覆盖数下界约束、下劣至非不变模型的原空间覆盖数上界，并证明希尔伯特空间填充曲线规范化具备多项式级覆盖数增长、严格优于字典序排序的指数爆炸。
方法详解¶
整体框架¶
本文定义对称空间 \((K, \rho, \mathbb{G})\)，其中紧致度量空间 \((K, \rho)\) 具备保度量的群作用 \(\rho(g\cdot x, g\cdot y) = \rho(x, y)\)。商空间 \(K/\mathbb{G}\) 赋予商度量 \(\rho_{\mathbb{G}}([x], [y]) = \min_{g\in\mathbb{G}} \rho(g\cdot x, y)\)。规范化算子 \(c: K \to K\) 满足将任意样本映射至其轨道内代表元且同一轨道具有相同输出（\(c(x)\in [x]\) 且 \(\forall y\in[x], c(y)=c(x)\)）。学习目标是利用有限样本拟合群不变的目标函数 \(f: K \to Y\)。
整体理论框架从统计泛化误差分析出发，对比三类模型构造策略（非对称骨干模型、规范化复合模型 \(h = \tilde{h} \circ c\)、群平均/结构内生不变模型），将其泛化界形式化归结为不同结构作用域的 \(\epsilon\)-覆盖数 \(\mathcal{N}(A, \rho, \epsilon)\)。进而深入剖析连续性与正则性对规范化质量的影响，最后落地到三维点云在置换群作用下的序列化规范化构造（字典序排序 vs 希尔伯特曲线投影）。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["对称空间度量与群作用定义<br/>(K, ρ, 𝔾) 及商度量 ρ_𝔾"] --> B["覆盖数驱动的泛化误差统一上界<br/>|L_exp - L_emp| ≤ O(ε + √(𝒩(·)/n))"]
B --> C["泛化层次理论构建<br/>𝒩(K/𝔾) ≤ 𝒩(c(K)) ≤ 𝒩(K)"]
C --> D["规范化正则性分析<br/>等距/Lipschitz最优 vs 强不连续性劣界"]
D --> E["点云置换群案例分析<br/>Lexsort指数增长 vs Hilbert多项式增长"]关键设计¶
1. 基于覆盖数的对称模型泛化层级：刻画不变性引入带来的样本复杂度改善边界
针对传统分析难以横向对比不同对称性策略的问题，本文基于算法鲁棒性与覆盖数框架推导了泛化误差界。若损失函数为有界且 Lipschitz 连续，则假设在样本集 \(S\) 上的泛化误差界主要由输入表示域的覆盖数 \(\mathcal{N}(h_S)\) 控制。对于非对称基线、规范化模型与内生不变/群平均模型，其有效覆盖数分别对应： $\(\mathcal{N}(h_S) = \begin{cases} \mathcal{N}(K, \rho, \epsilon), & \text{非对称 Lipschitz 模型} \\ \mathcal{N}(c(K), \rho, \epsilon), & \text{规范化模型 } h_S = \tilde{h}_S \circ c \\ \mathcal{N}(K/\mathbb{G}, \rho_{\mathbb{G}}, \epsilon), & \text{群平均或结构内生不变模型} \end{cases}\)$ 由于商映射 \(q(x)=[x]\) 是 \(1\)-Lipschitz 满射且 \(c(K) \subseteq K\)，论文严格推导了核心不等式链： $\(\mathcal{N}(K/\mathbb{G}, \rho_{\mathbb{G}}, \epsilon) \leq \mathcal{N}(c(K), \rho, \epsilon) \leq \mathcal{N}(K, \rho, \epsilon)\)$ 该层级揭示：规范化模型的泛化表现理论上最好仅能追平群平均/内生不变模型，而最差可能完全退化到与忽略对称性的非对称模型相同；有限群作用下其间隙上限被群阶数 \(|\mathbb{G}|\) 所约束（即 \(\mathcal{N}(K, \rho, \epsilon) \leq |\mathbb{G}| \cdot \mathcal{N}(K/\mathbb{G}, \rho_{\mathbb{G}}, \epsilon)\)）。
2. 规范化正则性与最优/劣规范化分类：阐明拓扑连续性对泛化的决定性作用
论文将覆盖数达到商空间下界 \(\mathcal{N}(c(K), \rho, \epsilon) = \mathcal{N}(K/\mathbb{G}, \rho_{\mathbb{G}}, \epsilon)\) 的算子定义为最优规范化（Optimal Canonization），达到原空间上界 \(\mathcal{N}(c(K), \rho, \epsilon) = \mathcal{N}(K, \rho, \epsilon)\) 的定义为劣规范化（Poor Canonization）。证明了当且仅当规范化算子 \(c\) 是等距映射（即满足 \(\rho(c(x), c(y)) = \rho_{\mathbb{G}}([x], [y])\)，在标准度量下等价于 \(1\)-Lipschitz 连续）时，规范化对于任意 \(\epsilon > 0\) 均为最优，如实数轴绝对值映射、一维序列标量排序和点云去质心平移中心化。
反之，若规范化算子存在严重的不连续性，使其在某点 \(x\) 处拥有 \(|\mathbb{G}|\) 个不同的极限点，则必然存在对称不变子集使得规范化的覆盖数完全退化为最差界： $\(\mathcal{N}(c(A), \rho, \epsilon) = \mathcal{N}(A, \rho, \epsilon) = |\mathbb{G}| \cdot \mathcal{N}(A/\mathbb{G}, \rho_{\mathbb{G}}, \epsilon)\)$ 这一机制原理解释了为何在不存在连续规范化的场景中，生硬引入强不连续规范化无法缩小假设类的有效几何体积，反而会在不连续界面附近急剧破坏泛化。
3. 希尔伯特曲线置换规范化：建立点云序列化多项式级覆盖数保证
针对三维点云在置换群 \(\mathbb{G}=S_n\) 作用下的规范化难题，自然界普遍采用两类排序策略：字典序排序（Lexsort）与空间填充曲线（如希尔伯特曲线）。论文证明，在超立方体输入域 \(K=[0,1]^{d \times n}\) 上，字典序排序因在首行坐标相等的低维流形处具有严重不连续性，导致其覆盖数随点数 \(n\) 呈指数级爆炸： $\(\left(\frac{1}{2\epsilon}\right)^{(d-1) \cdot n + 1} \leq \mathcal{N}(c_{\text{lex}}(K), \rho_{\infty}, \epsilon)\)$ 相比之下，真实商空间的覆盖数通过隔板法组合计数证明仅随点数 \(n\) 呈多项式增长：\(\mathcal{N}(K/S_n, \rho_{S_n}, \epsilon) \leq \binom{n + \lceil 1/(2\epsilon) \rceil^d - 1}{n}\)。
论文证明利用有限分辨率希尔伯特曲线 \(H_m: [0,1] \to [0,1]^d\) 构造的规范化算子 \(c_m = H_m \circ \text{sort} \circ H_m^{-1}\)（结合网格中心量化），借由希尔伯特曲线的 Hölder 连续性（\(\|H_m(x) - H_m(y)\|_{\infty} \leq 4|x - y|^{1/d}\)），保证其覆盖数在固定 \(\epsilon\) 下同样仅随点数 \(n\) 呈多项式增长： $\(\mathcal{N}(c_m(K), \rho_{\infty}, \epsilon) \leq \binom{n + \lceil 1/(2\delta) \rceil - 1}{n}, \quad \text{其中 } \delta = \left(\frac{\epsilon - 2^{-m-1}}{4}\right)^d\)$ 这是学界首次严格证明希尔伯特排序在学习理论上显著优于字典序排序，为点云大模型（如 Point Transformer V3）选择希尔伯特曲线序列化提供了坚实的泛化理论依据。
实验关键数据¶
主实验¶
论文在 ModelNet10 与 ModelNet40 点云分类基准上检验了覆盖数估计指标（Mean Coverage 与 Max Coverage）以及不同架构策略的测试集准确率与泛化差距（Train Acc - Test Acc）。骨干网络使用纯非对称的 Global MLP，分别对比无规范化、Lexsort 规范化和 Hilbert 规范化，并以置换不变的 DeepSets 作为强不变基线。
| 数据集 | 模型配置 | 测试准确率 (Test Acc ↑) | 泛化误差 (Gen. error ↓) | Mean Coverage ↓ | Max Coverage ↓ |
|---|---|---|---|---|---|
| ModelNet10 | MLP (无规范化) | 0.573 | 0.427 | 0.4545 | 0.6290 |
| ModelNet10 | MLP (Lexsort 规范化) | 0.762 | 0.215 | 0.3770 | 0.5407 |
| ModelNet10 | MLP (Hilbert 规范化) | 0.782 | 0.116 | 0.2013 | 0.5283 |
| ModelNet10 | DeepSets (内生不变模型) | 0.813 | 0.077 | 0.0917 (群距离) | 0.2742 (群距离) |
| ModelNet40 | MLP (无规范化) | 0.441 | 0.559 | 0.3823 | 0.7304 |
| ModelNet40 | MLP (Lexsort 规范化) | 0.692 | 0.256 | 0.2989 | 0.5550 |
| ModelNet40 | MLP (Hilbert 规范化) | 0.742 | 0.082 | 0.1951 | 0.5490 |
| ModelNet40 | DeepSets (内生不变模型) | 0.755 | 0.039 | 0.0958 (群距离) | 0.4880 (群距离) |
消融实验¶
为验证第一条核心理论推论（群平均优于规范化，规范化优于非不变模型），论文在 Rotated-MNIST（旋转 \(p4\) 群不变性）和隐式神经表示（INR）权重分类任务（置换不变性）上展开对比验证：
| 实验任务 | 模型/方法 | 核心指标 (准确率 ↑) | 几何覆盖度 (Coverage ↓) | 理论与实验说明 |
|---|---|---|---|---|
| Rotated-MNIST (\(p4\) 旋转) | 标准 CNN (非对称) | 94.7 ± 0.12% | 0.185 | 忽略旋转对称性，覆盖度最大 |
| Rotated-MNIST (\(p4\) 旋转) | CN(p4 frozen)-CNN 规范化 | 95.5 ± 0.15% | 0.176 | 随机固定权重规范化网络 |
| Rotated-MNIST (\(p4\) 旋转) | CN(p4)-CNN 规范化 | 96.5 ± 0.13% | 0.175 | 可学习权重规范化网络 |
| Rotated-MNIST (\(p4\) 旋转) | AvgCNN (群平均) | 97.3 ± 0.12% | 0.167 | 对 \(p4\) 的 4 个元素做完全群平均，泛化最好 |
| INR 权重分类 (MNIST) | 标准 MLP | 16.34 ± 0.61% | - | 忽略网络权重置换对称性 |
| INR 权重分类 (MNIST) | MLP + 规范化 | 31.06 ± 0.46% | - | 权值排序规范化，性能明显跃升 |
| INR 权重分类 (MNIST) | DWSNet (内生等变架构) | 86.66 ± 0.73% | - | 结构性保持权值置换等变性，表现碾压 |
| INR 权重分类 (Fashion) | 标准 MLP | 14.41 ± 0.39% | - | 无法捕获复杂的权重空间几何 |
| INR 权重分类 (Fashion) | MLP + 规范化 | 40.02 ± 0.23% | - | 规范化带来 25.6% 绝对增益 |
| INR 权重分类 (Fashion) | DWSNet (内生等变架构) | 65.53 ± 0.29% | - | 验证理论层级 DWSNet > 规范化 > MLP |
关键发现¶
- 严格遵循覆盖数泛化阶梯：在所有任务中均呈现“内生不变/群平均 > 规范化 > 非对称基线”的严格表现与泛化差距梯度；数据覆盖度（Coverage）与测试准确率具有高度负相关性。
- Hilbert 排序的实证优越性：Hilbert 规范化相比 Lexsort 在 ModelNet10/40 上泛化差距分别下降 0.099 与 0.174，覆盖度从 0.377 骤降至 0.201，有力印证了多项式覆盖数对实际模型容量与过拟合抑制的直接影响。
- 群增强与规范化的收敛权衡：在 PCA 主轴符号歧义消除实验中，群平均（76.0%）超越偏度规范化（74.2%）和符号数据增强（74.2%），且数据增强方案表现出明显的训练收敛滞后。
亮点与洞察¶
- 将对称模型比较范式从近似能力引向泛化几何：以往理论文献多聚焦于规范化与等变模型的表达能力与通用近似性，本文首度利用度量覆盖数工具建立了样本复杂度与泛化界的统一评估框架，清晰指明了规范化相比群平均在泛化界上的理论折损。
- 破解点云领域希尔伯特曲线经验成功的理论谜题：现代三维骨干（如 Point Transformer V3）普遍采用 Hilbert 序列化，此前文献仅定性提及空间连续性；本文给出了第一个关于 Hilbert 排序具备多项式级覆盖数、彻底规避字典序指数爆炸的严格数学证明。
- 拓扑不连续性对泛化的定量惩罚：给出了强不连续规范化在对抗区域使得覆盖数等同于原空间上界的严密证明，直观揭示了当数据流形跨越规范化间断点时模型泛化崩溃的内在机理。
局限与展望¶
- 覆盖数上界的紧致度受限：基于算法鲁棒性与覆盖数导出的统计泛化界本质上是悲观上界，未能完全捕获深度神经网络中隐式正则化与梯度优化的细粒度动力学。
- 未覆盖连续李群的局部框架平均：目前针对不连续性的分析主要聚焦于有限群与离散对称性，尚未完全推广至 \(SO(3)\) 或 \(SE(3)\) 等连续紧致李群下的框架平均（Frame Averaging）一般理论。
- 未来方向：作者指出后续将致力于把该覆盖数框架推广至更广泛的局部规范化、松弛规范化以及图结构中的对称性泛化分析中。
相关工作与启发¶
- vs Tahmasebi & Jegelka (2025a)：后者指出规范化模型在特定设定下由于逼近误差较低而在无限样本渐近下优于群平均；本文则从统计样本复杂度出发，证明在任意固定样本下群平均模型的泛化误差上界严格优于或等于规范化模型。
- vs Point Transformer V3 (Wu et al., 2024)：PTv3 借助 Hilbert 曲线序列化极大地加速了结构化点云处理并取得 SOTA 效果，但缺乏数学证明；本文为其提供了首个覆盖数多项式增长的泛化理论基础。
- vs Dym et al. (2024) 拓扑不可能性结论：Dym 等人证明了在多种对称任务中不存在连续规范化；本文在此基础上推进，证明了强不连续性将直接导致覆盖数膨胀至非不变模型的上限。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立基于覆盖数的规范化泛化理论层级，并完成 Hilbert 排序的理论证明。
- 实验充分度: ⭐⭐⭐⭐ 涵盖点云分类、旋转图像、INR 权重空间及图谱嵌入多类场景，紧扣理论结论。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，几何直觉与实际模型关联清晰。
- 价值: ⭐⭐⭐⭐⭐ 为几何深度学习中对称性处理机制的选择与设计提供了重要的理论指引。