技术摘要：基于动机马赛克的神经网络算法简化

问题陈述

大规模深度学习模型在计算机视觉、多模态学习和强化学习等领域展现出卓越性能，这主要得益于缩放定律。然而，这种缩放带来了巨大的内存、计算和能源成本。尽管剪枝、量化和知识蒸馏等压缩技术已成功利用冗余减少了模型规模，但一个根本性问题依然存在：为什么深度神经网络天生适合压缩？

现有的复杂度度量往往关注参数数量或计算足迹，却未能捕捉到学习参数的结构组织。作者假设，答案在于算法复杂度。他们提出，虽然随机初始化产生的参数具有高算法复杂度（需要冗长的描述），但优化过程会引入结构和可重复性，从而产生具有更低算法复杂度的解。当前的压缩方法通常将可压缩性视为事后属性，或针对特定目标（如稀疏性）进行优化，而非通过塑造优化域来从根本上偏好算法上更简单的解。

方法论：动机马赛克（MoMos）

为了探究并诱导这种简单性，作者提出了动机马赛克（MoMos），这是一种限制模型权重假设类的约束参数化方法。

核心概念

MoMos 将展平的权重向量 $w \in \mathbb{R}^n$ 划分为 $m$ 个大小为 $s$ 的块。MoMos 不允许可每个块为任意向量，而是限制每个块必须从一组固定的 $k$ 个可重用动机（$Z = \{z_1, \dots, z_k\}$）中选择。这些动机在各块间的排列由马赛克（重用模式）$M \in [k]^m$ 定义。

由此产生的参数化 $\hat{w}$ 构建如下：
$$\hat{w} = \psi^{-1}(z_{M(1)}, \dots, z_{M(m)})$$
其中 $\psi$ 是切片算子，$\psi^{-1}$ 重构完整的权重向量。

理论框架

该方法基于柯尔莫哥洛夫复杂度 $K(w)$，定义为输出 $w$ 的最短程序长度。

1. 无约束界：对于任意权重，最坏情况下的描述长度受限于权重的位长：$K(w) \leq nq + O(1)$。
2. MoMos 界：对于 MoMos 假设类 $\mathcal{H}_{s,k}$，作者证明了更紧的最坏情况上界：
   $$K(\hat{w}) \leq ksq + m \lceil \log_2 k \rceil + \zeta$$
   其中，$ksq$表示描述$k$个动机所需的位数，$m \lceil \log_2 k \rceil$ 表示马赛克模式所需的位数。
3. 优化几何：MoMos 假设类分解为线性子空间的并集。优化域的丰富程度由不同子空间的数量决定，这与第二类斯特林数相关。作者表明，对于固定的容量，较小的块大小（$s$）允许更丰富的优化域（更多不同的子空间），而较大的块虽然强制了更强的规律性，但也更严重地限制了搜索空间。

实现

优化过程通过交替进行标准梯度下降更新稠密权重，并将其投影到 MoMos 结构上来执行。在每一步，当前权重被切片为块，并采样（或更新）一组 $k$ 个动机，以最小化稠密块与其基于动机的表示之间的重构误差（失真）。

主要贡献

1. MoMos 参数化：引入一种强制可重复性和重用的约束参数化方法，为算法上更简单的解提供了理论依据的偏差。
2. 复杂度保证：形式化证明 MoMos 保证了比无约束参数化更低的最坏情况算法复杂度，该复杂度由块大小 $s$ 和动机数量 $k$ 控制。
3. 实证验证：证明 MoMos 推动学习到的权重趋向于算法上更规则且更易压缩的参数化（通过块分解法 BDM 等代理指标衡量），同时保持与无约束基线相当的性能。
4. 优化域分析：分析表明，MoMos 下的优化域是线性子空间的并集，且算法简化与域丰富度之间的权衡可通过块大小和容量进行调节。

实验结果

作者在多种架构（MLP、ResNet20、Tiny-ViT、Swin-B、SmolLM2）和数据集（CIFAR-10、Tiny ImageNet、WikiText-103）上评估了 MoMos。

• 性能与复杂度：MoMos 在显著降低算法复杂度的同时，实现了基线水平的准确率（或大语言模型的困惑度）。例如，在 Tiny-ViT 上，当块大小 $s=2$ 且容量 $c=5\%$ 时，模型实现了 86.99% 的准确率（基线为 86.56%），相对算法简化（RAS）为 3.02。
• 粒度权衡：较小的块大小（如 $s=2, 4$）即使在低容量下也能保持准确率，而较大的块则需要更高的容量来恢复性能。这表明细粒度的重用对于维持功能多样性更为有效。
• 结构集中：在训练过程中，动机分配变得高度集中；一小部分动机占据了绝大多数块的分配，而许多动机未被使用。这证实了优化过程自然地在稠密参数空间中选择了稀疏的可重用模式集。
• 失真与损失：稠密权重与其 MoMos 重构之间的失真随着验证损失的降低而减小，表明施加的规律性并未阻碍模型的学习能力。
• 与基线比较：在准确率与复杂度降低的权衡方面，MoMos 优于或等同于标准压缩基线（矢量量化、乘积量化、软权重共享、量化感知训练），且通常具有更低的训练时间开销。

意义与主张

本文声称提供了首个通过约束模型类本身（而非将可压缩性视为训练后属性）来对学习参数的算法复杂度提供保证的工作。

• 诱导冗余：该工作证明，冗余和结构可以从优化域中诱导出来，而不仅仅是在训练后观察到。通过塑造假设类，作者展示了模型可以在不显著降低性能的情况下变得天生更易压缩。
• 稠密简单性：一个关键见解是，模型可以在不变得稀疏的情况下变得算法上更简单。学习到的结构保持稠密（零动机很少），但重用模式创造了可压缩性。
• 理论洞察：结果支持了“学习诱导结构，从而降低解的算法复杂度（相较于随机初始化）”的假设。这与神经网络偏向于具有更低柯尔莫哥洛夫复杂度的函数的观点相一致。
• 局限性：作者指出，虽然理论界限是紧的，但当前硬件尚不支持快速、可重用的块操作，这意味着理论上的压缩并不能立即转化为硬件效率。他们还承认，当前的复杂度代理指标（如 BDM）是近似值，对于高维对象可能会产生误导。

总之，MoMos 为模型可压缩性提供了新颖的视角，表明深度学习中对海量参数数量的“需求”可能部分被结构化重用所取代，从而为更高效且理论根基更扎实的神经网络设计提供了一条路径。