算法概率，又称所罗门诺夫归纳推理理论，是一种为可能观测序列分配概率的形式化框架。它基于通用图灵机的程序长度，为给定二进制字符串将被该机器生成的概率提供了数学定义。该理论由雷·所罗门诺夫于20世纪60年代提出，后经列昂尼德·莱文等人完善，成为算法信息论的基石，并影响了人工智能和机器学习等领域。
其核心思想是，一个字符串的概率与其最短程序长度的2的负次幂成正比，这一概念被称为科尔莫戈罗夫复杂性。这天然倾向于更简单的解释，因为较短的程序获得较高的概率。算法概率在一般情况下不可计算，但它作为预测和模式识别的理论理想，常与机器学习和深度学习等实用方法形成对比。
历史发展
雷·所罗门诺夫在1960年的一份技术报告中首次描述了算法概率，并于1964年发表了题为“归纳推理的形式理论”的开创性论文。他的工作旨在通过为所有可能序列提供通用先验来解决归纳问题。20世纪70年代，列昂尼德·莱文独立贡献了相关概念，定义了莱文搜索和通用分布，将算法概率与计算复杂性联系起来。后来，在20世纪80年代和90年代，李明和保罗·维塔尼等研究者将这些思想整合到更广泛的算法信息论领域中，出版了综合性的著作，形式化了科尔莫戈罗夫复杂性、算法概率和通用归纳之间的关系。
形式定义
对于通用图灵机U，二进制字符串x的算法概率定义为所有生成x后停机程序p的概率之和。形式上，P_U(x) = Σ_{p: U(p)=x} 2^{-|p|}，其中|p|是程序p的比特长度。该和收敛，因为所有程序的总概率受克拉夫特不等式约束。前缀自由版本（即没有程序是另一个程序的前缀）确保该和定义良好，并导出通用先验。算法概率与科尔莫戈罗夫复杂性K(x)的关系由不等式 -log P_U(x) ≤ K(x) + O(1) 给出，这意味着低复杂性的字符串具有高概率。
与奥卡姆剃刀的联系
算法概率为奥卡姆剃刀原则（即更简单的解释更可能是正确的）提供了严格的数学论证。在该框架中，简单性以程序长度衡量，较短的程序被赋予指数级更高的先验概率。这并非任意选择，而是由通用图灵机的性质以及先验必须可计算且一致的要求所决定。该理论表明，在所有与观测数据一致的假设中，描述最短的假设最有可能，这一原则支撑了机器学习和大语言模型训练中的许多实用算法。
在归纳推理中的作用
所罗门诺夫的框架将归纳推理形式化为对所有可能可计算假设的贝叶斯更新。给定观测数据序列，每个假设的后验概率与其先验（算法概率）乘以似然成正比。这产生了一种通用预测方法，在数据生成过程可计算的条件下，该方法以概率1收敛到真实数据生成过程，因此是最优的。这一结果被称为所罗门诺夫完备性定理。然而，该方法无法直接实现，因为它需要对无限多个程序求和，导致计算上不可行。尽管如此，它作为评估实用预测算法的理论基准。
与通用搜索和莱文搜索的关系
算法概率与莱文搜索密切相关，莱文搜索是一种按概率顺序搜索程序来解决问题的方法。莱文搜索利用通用分布优先考虑算法概率高的程序，对于具有短解的问题实现接近最优的时间复杂性。这种联系将算法概率与计算复杂性理论联系起来，表明通用先验可以指导人工智能系统中的高效搜索。该概念影响了神经网络架构和训练方法的设计，尽管现代方法如Transformer模型依赖经验先验而非显式算法概率。
在人工智能中的应用
虽然算法概率并未直接用于大多数当代AI系统，但其原则塑造了理论基础。例如，源自算法概率的最小描述长度（MDL）原则被应用于机器学习中的模型选择和正则化。深度学习中的贝叶斯推断通常纳入近似简单性的先验，呼应了所罗门诺夫的思想。人工智能安全性和可解释性研究有时引用算法概率来论证更简单模型的合理性。OpenAI和Google DeepMind等公司在理论工作中探索了相关概念，但实际实现依赖随机梯度下降和大规模数据，而非显式程序搜索。
局限性与批评
算法概率面临若干根本性局限。它不可计算，即没有算法能为所有字符串计算精确概率。对特定通用图灵机的依赖引入了影响绝对概率的加性常数，尽管相对排序在常数范围内与机器无关。批评者认为，该框架假设固定的计算模型，未考虑观察者或环境的复杂性。此外，该先验对不可计算序列分配零概率，这限制了其对可能并非由可计算过程生成的真实世界数据的适用性。这些问题促使一些研究者开发替代框架，如随机过程模型和经验贝叶斯方法，这些方法在实践中更易处理。
对现代研究的影响
尽管存在局限，算法概率继续影响机器学习和认知科学的理论研究。它启发了关于通用归纳、算法随机性和生成式AI基础的研究。MIT CSAIL和斯坦福AI实验室等机构的研究者研究了算法概率与神经网络泛化之间的联系。该概念也出现在人工通用智能的讨论中，被提议作为通用学习智能体的组成部分。近期关于大语言模型可解释性的工作将下一个词元预测与所罗门诺夫归纳进行了类比，尽管实际机制差异显著。
参见
参考文献
- Solomonoff, R. J. (1964). "A Formal Theory of Inductive Inference." Information and Control, 7(1), 1-22.
- Li, M., & Vitányi, P. (2008). "An Introduction to Kolmogorov Complexity and Its Applications." Springer.
- Hutter, M. (2005). "Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability." Springer.