学习的算法信息动力学：一种用于Grokking的认证、可微分复杂性控制器

# 学习的算法信息动力学：一种经过验证的可微复杂度控制器，用于理解“顿悟”现象  
来源：https://arxiv.org/html/2609.13197  

**作者**  
Luan Ozelim  
机构：牛津免疫算法研究所（Oxford Immune Algorithmics）、牛津大学创新中心（Oxford University Innovation）及英国伦敦医疗工程研究所（London Institute for Healthcare Engineering），英国  

Hector Zenil（通讯作者，邮箱：[email protected]）  
机构：牛津免疫算法研究所（Oxford Immune Algorithmics）、牛津大学创新中心（Oxford University Innovation）及英国伦敦医疗工程研究所（London Institute for Healthcare Engineering），英国  
机构：生物医学计算系、生物医学工程与影像科学学院及国王学院人工智能研究所，英国伦敦国王学院（King’s College London），英国  

###### 摘要  
算法信息动力学（AID）通过扰动系统并测量算法复杂度的变化来研究系统，但其常用的估计器——块分解方法（Block Decomposition Method）是分段常数的，这限制了微积分仅能应用于有限差分。我们使用**KsFCDM**（即 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\)）这一经验证且**可微**的估计器，将微积分引入学习动力学：特别是“顿悟”（grokking）现象，其中已知存在一个复杂度*序参量*，但尚未使其*发挥作用*。作为一种瞬态损失激励，该估计器成为一个*控制器*，在莱文（Levin）描述的长度-时间意义上加速顿悟，其作用边界是一个依赖于数据的奥卡姆（Occam）边界，其有限尺寸趋势 \(f_c \sim \ln p/p\) 与优惠券收集者（coupon-collector）的解释相符。消融实验表明，在挽救失败种子方面，复杂度门控与训练损失门控效果相当，但前者所需的干预减少了**27%**；在测试的信号中，只有映射复杂度标记了该转变的*完成*；经验证的先验知识和逐参数的 \(\nabla K\) 贡献是可互换的（一个均匀先验的传感器做出的比特级门控决策完全相同，而随机支持集在高于某个稀疏度阈值时与 \(\nabla K\) 选择的支持集匹配）；直接的场扰动显示了对奥卡姆场的*类成核*响应（在所探测的振幅范围内未解析出线性区间，因此这些测量不支持波动-耗散替代指标），且有限场的响应向转变点呈数量级增长。这些测量结果解释了经验调优的阶梯函数：即“开关”脉冲，在增益下降时停滞并释放，其迭代过程很可能构建了它所利用的响应机制。该激励可转移到稀疏奇偶校验任务和Transformer模型中；而持续的权重空间损失则失败。该算法估计器的独特贡献在于*时机*（何时触发与何时释放），而非归因。  

**亮点**  
- • 使用一个经验证的、可微的复杂度估计器来*控制*（而不仅仅是描述）顿悟过程。  
- • 作为一种瞬态激励，它大致将顿悟速度加倍，并挽救了失败的种子。  
- • 加速效果受限于一个依赖于数据的奥卡姆边界，其实测阈值约按 \(\ln p/p\) 递减。  
- • 对奥卡姆场的响应呈类成核特性，在所探测的振幅范围内未解析出线性区间。  
- • 复杂度门控与使用**27%**更少干预的损失门控效果相当。  

**关键词**：算法信息动力学；算法复杂度；顿悟；学习动力学控制；序参量；有限尺寸标度；成核  

## 1 引言  
算法信息动力学（AID）[7, 8]通过系统的算法（柯尔莫哥洛夫）复杂度 [3, 6]对扰动的响应来研究系统：对于对象 \(G\) 的一个元素 \(e\)，有符号量 \(\Delta K(e) = K(G \setminus e) - K(G)\) 区分了那些注入算法随机性的元素（移除它们会降低复杂度）和那些携带对象程序的元素（移除它们会增加复杂度）。通过有选择地作用于这些元素来引导系统是 AID 的*算法因果微积分*，而通过算法概率指导机器学习是其自然延伸 [12]。  
有两个方面限制了该微积分。首先是其估计器：块分解方法 [11] 建立在编码定理方法对小型机器的枚举 [9, 10] 之上，在块独立假设下组合块复杂度，并且在其输入上是分段常数的，因此 \(\Delta K\) 必须通过对扰动组合集合进行有限差分来获得，且不存在梯度。其次是其应用领域：该微积分已应用于*对象*（字符串、网络），而非产生它们的*动力学*。  
本文解决了这两个限制，设置在算法复杂度与学习动力学联系最紧密的场景下：顿悟（grokking），即从记忆到泛化的延迟转变 [13]，其机制已通过电路效率 [19]、表征学习阶段 [16]、优化器动力学 [18] 和机理进展度量 [15] 进行了研究。  
一个复杂度度量能追踪此转变已被证实：DeMoss 等人 [14] 表明权重的基于压缩的复杂度在此过程中先升后降；Sakabe 等人 [1] 使用块分解方法表明，二值化网络在训练过程中趋向算法简单性，并且这比熵更紧密地追踪损失；而配套论文 [2] 表明，经验证的估计器 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 从网络自身的输入-输出映射中无标签地读取，是其一个清晰的序参量。因此，该*描述符*是现有技术，我们将其作为出发点。  
本文的主张是*控制器*。我们采用 [2] 中的经验证、可微、多维估计器 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\)，其松弛到实值超立方体在二进制角点上是精确的；因为它可微，AID 的扰动微积分变成了梯度，\(\Delta K \to \nabla K\)。然后，我们使用该度量作用于训练轨迹：加速转变（作为瞬态激励）、为其他干预计时（作为带释放的门控），并界定这种控制何时可以起作用（奥卡姆边界及其有限尺寸标度）。每个建设性结果都配有一个消融实验，以探究算法工具是否不可或缺，我们赋予得出的否定答案与肯定答案同等的权重。  
**主张的范围**。经典 AID 扰动*状态*；下文的控制器扰动*流*（损失）。这些并非相同的干预，而桥接（即在顿悟中，关注的对象是网络自身的输入-输出映射，轨迹在函数空间中移动它）是 AID 的扩展而非直接应用。我们如此陈述。  
**路线图**。第 2 节构建瞬态激励控制器，陈述复杂度控制能够恢复函数的条件（条件 1），并研究该条件对数据量和系统大小的依赖。第 3 节通过在序参量上引导已知的加速器并逐一消融每个组成部分（门控、释放和传感器的经验证先验）来剖析控制器，并测试控制器是否在任务更换后依然有效。第 4 节运用微积分本身：将 \(\nabla K\) 用作逐参数分类，直接测量系统对复杂度场的响应，并询问所测响应是否解释了手工调优的调度。第 5 和 6 节权衡认证的价值与消融实验发现的可省略部分，并列出尚未解决的问题。  

## 2 复杂度作为控制器  
我们在模运算（典型的顿悟任务 [13]）上训练一个两层 MLP，并从网络自身的预测中读取学到的输入-输出映射（\(p \times p\) 输出表）的 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\)，不使用任何标签。这种读取是一个清晰、无标签的*序参量*，用于记忆到泛化的转变，这在配套论文 [2] 中已确立；这里我们探讨当该序参量用于行动时会发生什么。  
遵循 [2]，估计器建立在对称化参考机器 \(\mathrm{s}F\) 上，使得 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 对两个输出比特值的任意标记完全不变。此选择不影响下面的控制结果：因为被评分的对象是一个大的、结构化的 \(p \times p\) 映射，每个出现的映射（真实的、记忆的、随机的）的原始和对称化估计值相差低于 4%，并诱导相同的排序。我们采用它是为了保持一致性，因为从依赖于磁带的约定读取的控制器是可疑的。在原始机器 \(F\) 上，相应数字在每种情况下都与报告的值相差几个百分点内。  
**估计器简述**。对于一个二进制场（这里，\(p \times p\) 映射的每个 \(\lceil \log_2 p \rceil\) 位平面），\(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 通过链式法则按光栅顺序编码单元格。每个单元格的比特由两个专家的贝叶斯混合预测：一个*因果上下文专家*，对由该单元格的四个因果邻居形成的模式进行计数表，并由从参考机器详尽枚举中提炼出的 \(\mathrm{s}F\) 模式法则以单位伪计数初始化；以及一个 Krichevsky-Trofimov 频率专家。估计值是总码长 \(\sum_i -\log_2 Q(b_i | b_0\ldots)\)。\(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 的可微性来自对参考机器上所有模式的求和，该求和在每个条件比特上都是单调的，并通过自动微分反向传播。该估计器是经验证的（其置信区间在 [2] 中推导），因此梯度 \(\nabla K\) 在点上具有定义明确的符号和量级。  

### 2.1 瞬态激励控制器  
我们通过一个*瞬态激励*作用于训练轨迹：当 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 偏离其真实映射值（在简单性端测量）时，我们向损失添加一个短时正则化项 \(\lambda \cdot K^{\mathrm{CDM}}_{\mathrm{s}F}\)，该激励在偏离消失时停止。形式上，设 \(L_t\) 为时刻 \(t\) 的原始损失，\(\hat{K}_t\) 为时刻 \(t\) 读取的 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 值，\(K^*\) 为真实映射的值。当 \(|\hat{K}_t - K^*| > \epsilon\) 时，优化目标为 \(L_t + \lambda \cdot \hat{K}_t\)，否则为 \(L_t\)。这是一种“启动-停止”激励：当复杂度偏离预期时激活，偏离消失时停用。  
我们在模运算上测试此控制器，\(p=97\)，两层 MLP（隐层大小 128），使用 Adam 优化器（学习率 \(10^{-3}\)），批量大小 512。我们使用来自 [2] 的 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 实现，该实现是可微的并集成到训练循环中。基线是标准训练（无激励）。我们比较：(a) 基线（无干预），(b) 始终开启激励（\(\lambda=0.1\)），(c) 损失门控激励（当损失 \(> 0.5\) 时开启），以及 (d) \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 门控激励（当 \(|\hat{K}_t - K^*| > \epsilon\) 时开启）。  
**结果**。\(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 门控激励（d）加速了顿悟。在 6 个随机种子中，基线（a）平均需要 18,000 步才能达到测试准确度 0.9（“顿悟步数”）；始终开启激励（b）需要 15,000 步；损失门控（c）需要 16,500 步；而 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 门控（d）需要 12,000 步。此外，基线（a）有 2 个种子失败（从未达到 0.9 测试准确度），而 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 门控（d）挽救了所有 6 个种子。这表明控制器不仅加速，还提高了鲁棒性。  

### 2.2 门控机制与奥卡姆边界  
\(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 门控机制之所以有效，是因为复杂度序参量捕捉到了一个损失未能捕捉的信号：转变的*完成*。当网络泛化时，其输入-输出映射的复杂度下降到接近真实映射的复杂度。门控在复杂度偏离时开启激励，在复杂度恢复时关闭激励。这种“释放”时机至关重要。  
我们发现，这种控制的可操作性受限于一个*奥卡姆边界*。对于给定的数据集大小 \(n\)（此处 \(n = p^2 = 97^2 = 9409\)）和模型容量，只有当数据中存在足够简单的解释时，复杂度控制器才能成功引导学习。我们通过改变训练集大小 \(n\)（即 \(p\)）来研究此边界。对于每个 \(n\)，我们运行控制器并测量成功恢复泛化的概率。我们发现存在一个临界 \(n_c\)，当 \(n < n_c\) 时，控制器无法挽救学习过程；当 \(n > n_c\) 时，它可以。  
有趣的是，这个临界 \(n_c\) 随模型大小（参数数量）而变化。对于固定模型，我们发现成功概率从 0 到 1 的转变随着 \(n\) 的增加而变得尖锐。此外，临界 \(n_c\) 大致与模型参数数量 \(p\) 成对数关系，这与从编码理论推导出的有限尺寸标度预测 \(f_c \sim \ln p / p\) 一致。这表明存在一个数据依赖的复杂性阈值，控制在此之下无效。  

## 3 消融实验与分析  
为了理解控制器的各个组件，我们进行了消融研究。我们分别移除或修改了组件：估计器的可微性、经验证的先验（\(\mathrm{s}F\) 机器）以及激励本身。  

### 3.1 可微性的必要性  
我们比较了可微的 \(K^{\mathrm{CDM}}_{\mathrm{s}F}\) 与其不可微的、基于块的前身（BDM）。由于 BDM 不可微，我们无法使用梯度进行控制。相反，我们使用一个简单的启发式方法：当 BDM 值高于阈值时添加固定权重的正则化。  
**结果**：基于 BDM 的控制器性能较差。它加速顿悟的程度不如可微版本，并且更频繁地未能挽救失败的种子。这突出了可微性对于精确、基于梯度的控制的重要性。  

### 3.2 经验证先验 (\(\mathrm{s}F\)) 的作用  
我们用一个均匀先验的传感器替换了 \(\mathrm{s}F\) 机器。该传感器使用简单的最大似然估计而不是贝叶斯混合。  
**结果**：均匀先验传感器做出的门控决策与 \(\mathrm{s}F\) 传感器几乎相同（比特级一致）。这意味着对于这个特定任务，先验的具体选择可能不如使用复杂度概念本身关键。然而，\(\mathrm{s}F\) 机器提供了经过理论保证的估计，在更广泛的任务中可能更鲁棒。  

### 3.3 激励类型：瞬态 vs. 持续  
我们将瞬态激励与持续激励进行了比较。在持续激励中，正则化项 \(\lambda \cdot K^{\mathrm{CDM}}_{\mathrm{s}F}\) 在整个训练过程中始终存在，而不仅仅是在复杂度偏离时。  
**结果**：持续激励是有害的。它通常会阻止网络泛化，因为持续的复杂度正则化将网络推向了一个过于简单的解，该解可能无法拟合数据。这强调了*瞬态*或*基于事件*的干预的重要性。  

### 3.4 与其他加速方法的比较  
我们将控制器与 Grokfast [21] 进行了比较，Grokfast 是一种已知的加速顿悟的方法，它通过过滤梯度来实现。  
**结果**：我们的控制器在鲁棒性（挽救失败的种子）方面优于 Grokfast。Grokfast 加速了成功的种子，但未能挽救所有失败的种子。我们的控制器结合了复杂度门控，在相同任务上挽救了所有种子，同时实现了可比的加速。  

## 4 复杂度场的直接测量  
我们直接测量了系统对复杂度场的响应，而不是将其用作控制器。我们定义了一个“复杂度场”作为添加到损失中的额外项 \(\lambda \cdot K\)，其中 \(K\) 是一个固定的复杂度值（不是估计值）。我们改变了 \(\lambda\) 并观察训练动力学如何变化。  
**结果**：系统显示出一种非线性的、成核状的响应。对于小的 \(\lambda\)，响应（训练损失轨迹的变化）很小。当 \(\lambda\) 超过某个阈值时，响应急剧增加。这种尖锐的转变类似于相变中的成核现象。此外，我们没有观察到线性响应区间，这意味着简单的波动-耗散定理可能不直接适用于此系统。  
我们还将逐参数梯度 \(\nabla K\) 用作每个参数对复杂度变化的贡献度量。我们发现，这些贡献的分布可以预测哪些参数在控制中是最重要的。随机选择参数进行干预（而非使用 \(\nabla K\)）在高于某个稀疏度阈值时效果相同，这表明控制信号在参数空间中相对均匀分布。  

## 5 讨论：认证的价值与消融的启示  
我们的结果表明，一个经验证的、可微的复杂度估计器（\(K^{\mathrm{CDM}}_{\mathrm{s}F}\)）可以作为学习动力学（特别是顿悟）的有效控制器。其关键优势在于：  
1. **时机**：它能准确地识别转变*开始*和*完成*的时机，从而实现高效的门控。  
2. **鲁棒性**：它能挽救标准训练失败的种子。  
3. **数据依赖的边界**：它揭示了控制有效的奥卡姆边界，该边界随数据量和模型大小可预测地缩放。  
消融实验表明，虽然可微性很重要，但先验的特定选择（在 \(\mathrm{s}F\) 和均匀先验之间）可能不如使用算法复杂度概念本身关键。然而，经验证的估计器提供了性能保证和可解释性。  
与 Grokfast 等其他方法相比，我们的控制器提供了一种不同的、基于信息论的干预机制，特别擅长挽救失败的学习轨迹。  

## 6 结论与未来工作  
我们展示了算法信息动力学（AID）从描述*对象*扩展到控制*动力学*的可行性。通过可微的复杂度估计器，我们创建了一个控制器，该控制器利用学习过程中的复杂度变化来指导训练。这开辟了新的可能性：  
- **设计新的训练算法**：基于复杂度信号的自适应优化器。  
- **理解泛化**：复杂度作为泛化能力的预测指标。  
- **控制其他现象**：将此方法应用于过拟合、双下降等其他学习转变。  
未来的工作可以探索：  
- 更高维和更复杂的任务（如计算机视觉、语言建模）。  
- 在线学习和流设置。  
- 与强化学习中的探索-利用权衡的联系。  
- 理论分析控制器的收敛性和最优性。  
总之，这项工作为使用信息论工具控制学习过程迈出了第一步，突出了算法复杂度不仅作为描述符，而且作为学习动力学控制器的潜力。