训练让神经网络变得更"简单"了——算法复杂度告诉你学的怎么样

"学习即压缩"是一个在机器学习理论中被广泛讨论但很难验证的假说。它说的是：一个训练好的神经网络的权重，比随机初始化的权重包含更多的结构——因此可以用更少的比特来描述。Kolomogorov 复杂度是衡量这个"结构多少"的理论工具，但它不可计算——你无法实际算出描述一组任意权重所需的最短程序长度。

Bakhtiarifard、Wilson、Afifi、Wenshøj 和 Selvan 提出的 Quantized Block Decomposition 方法让 Kolmogorov 复杂度变得可计算。做法分两步：先把网络权重量化到有限字母表（把连续浮点数变成离散的符号），然后通过按比特平面聚合编码定理估计值来计算复杂度。

有了这个工具，他们做了一系列观察。训练过程中权重的算法复杂度确实在下降低——权重变得越来越"简单"，结构越来越多。数据量越大，降低越明显。出现过拟合时，复杂度反而上升——模型开始记忆噪声，结构遭到破坏。在"顿悟"（grokking）现象中，复杂度的下降滞后于泛化的改善——模型先记住了训练数据（复杂度高），然后在某个临界点突然发现了底层结构（复杂度骤降）。复杂度和泛化性能之间存在相关性。

还有一个实用的发现：算法信息主要集中在最高有效位平面。这意味着在训练后做量化压缩时——你想知道保留多少比特就够了——QuBD 可以告诉你哪些位平面包含真正的信息。

不清楚的地方：KCS 复杂度的估计是否敏感于量化方式的选择？不同量化策略可能影响结果。复杂度和泛化之间的相关关系并不一定意味着因果关系——复杂度降低是学习的结果，还是学习的原因？该分析目前限于中等规模的神经网络——在超大规模模型上，QuBD 是否还能保持计算可行性？

参考文献

1. Bakhtiarifard, P., Wilson, S. N., Afifi, M., Wenshøj, J., & Selvan, R. (2026). Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis. arXiv:2605.15551 [cs.LG].

2. Chaitin, G. J. (1975). A Theory of Program Size Formally Identical to Information Theory. Journal of the ACM.

3. Arora, S., et al. (2018). Stronger Generalization Bounds for Deep Nets via a Compression Approach. ICML.