雷·所罗门诺夫(1926年7月25日—2009年12月7日)是美国研究者,其工作帮助奠定了人工智能与机器学习的理论基础。他提出了算法概率和所罗门诺夫归纳法,后者是一种数学框架,通过考察能够生成观测结果的计算机程序来预测观测结果。他的研究将归纳推理、计算、概率与信息联系起来,使他成为算法信息论的奠基人之一。
生平与研究经历
所罗门诺夫出生于俄亥俄州克利夫兰。他就读于芝加哥大学,于1951年获得物理学硕士学位。他的兴趣逐渐集中于机器如何从经验中学习、发现规律并形成解释。
1956年,他参加了达特茅斯会议,即达特茅斯人工智能夏季研究项目。这次会议标志着人工智能作为一个有明确名称的研究领域的确立。该项目由约翰·麦卡锡、马文·明斯基等研究者组织,汇集了研究机器智能的不同思路。所罗门诺夫特别关注的是如何为学习与预测建立一般性的数学基础。
此后的职业生涯中,他大部分时间并未担任传统的大学教职,而是在工业研究机构或以独立研究者的身份开展工作。他终其一生都在持续发展归纳推断、概率预测与机器智能理论。
归纳问题
所罗门诺夫关注的核心问题是:学习者在观测到一个有限数据序列后,应当如何预测接下来会出现什么。任何有限序列都与无穷多种解释相容。例如,一个以连续多个零开头的序列,可能由一个永远输出零的程序生成,也可能由一个最终转为输出一的程序生成,还可能由一个先复现已观测序列、随后任意运行的程序生成。
因此,要解决这个问题,仅仅找到与证据一致的解释还不够,还需要一项原则,为相互竞争的解释赋予相对权重。
所罗门诺夫结合了两个思想:
- **计算上的可表达性:**解释可以表示为通用图灵机上的程序。
- **对简洁性的偏好:**较短的程序应当比较长的程序获得更大的初始权重。
第二个思想为奥卡姆剃刀提供了一种数学解释。简洁性由计算描述的长度来衡量,而不是凭借非形式化的判断,认定某种解释看起来有多自然。
算法概率与通用归纳
所罗门诺夫在1960年的一份报告中提出了这一思路,并在1964年发表于《信息与控制》的两篇系列论文《归纳推断的形式理论》中加以阐述。
其基本构造设想向一台固定的通用计算机输入随机选取的二进制数据。每个有限输入程序的权重都与其长度相关:长度为 的程序获得权重 。因此,单个短程序贡献的权重大于单个长程序。
对于观测到的有限字符串 ,通用概率赋值将所有输出以 开头的相关程序的权重相加。在一种标准表述中,
其中,求和遍历机器 相应的最小输入前缀, 表示 的长度,以比特为单位。
这一构造通常是半测度,而非普通的概率测度:一部分计算权重可能无法产生后续输出。可以通过条件比值,或对半测度进行归一化,来获得预测。
这一框架与贝叶斯推断密切相关。程序充当假设,基于程序长度的权重提供先验,而观测结果决定哪些程序仍与证据相容。通用预测器并不只选取一个拟合得最好的解释,而是综合多个解释的贡献。
这里的“通用”具有精确且有限定的含义。这一构造涵盖可计算的数据生成过程,并不意味着预测绝无差错,也不意味着能够不受限制地了解世界。
与算法信息论的关系
所罗门诺夫的工作推动了通过程序长度研究信息这一方向的建立。柯尔莫哥洛夫复杂度衡量的是:相对于选定的通用机,生成某个指定对象的最短程序的长度。相比之下,所罗门诺夫的概率构造汇总的是与某项观测相容的程序的权重。
这些思想相互关联,但并不相同。最短程序对算法概率的贡献尤为重要,而总概率也可以体现多种替代描述的贡献。
安德雷·柯尔莫哥洛夫和格雷戈里·蔡廷各自独立地提出了与之密切相关的程序长度复杂度研究方法。他们与所罗门诺夫的工作共同构成了算法信息论的基础。
所罗门诺夫的框架也阐明了预测与数据压缩之间的联系。能够支持预测的规律,往往可以表示为对观测结果更简短的描述。反过来,有效的描述也能够编码一个生成这些数据的过程模型。
数学保证与局限
通用算法概率的一项核心性质是,它对可计算概率模型具有支配性。非形式化地说,对于每个可计算概率测度 ,通用半测度 都满足如下形式的界:
其中, 取决于模型和通用机,但不取决于观测到的字符串 。
这一性质支撑了强有力的收敛结论:当观测来自可计算的概率源时,在适当的数学条件下,通用预测会趋近于该概率源的预测。这类结论涉及累计预测误差或渐近预测误差,并不保证对每一次单独观测都预测正确。
不过,这一框架存在根本性的局限:
- **不可计算性。**精确的通用预测无法作为普通算法来实现。它需要考虑某些程序,而这些程序的最终行为可能是不可判定的,因此这一困难与停机问题相关。
- **对参考机的依赖。**更换通用机会改变程序长度和先验权重。不变性结论在一些重要方面约束了这些变化,但无法消除它们对较短数据集可能产生的显著影响。
- **缺乏实用的资源预算。**短程序也可能需要极长的运行时间。仅凭描述长度,无法获得实用的计算成本度量。
- **适用范围在于预测,而非因果。**一种预测观测结果的方法,本身并不能确定哪些关系是因果关系,也不能确定干预后会发生什么。
这些局限使所罗门诺夫归纳法主要成为一种理论标杆,而非可以直接执行的学习系统。
影响
所罗门诺夫的持久贡献,在于为从数据中学习提出了统一的数学解释:用计算形式表示解释,偏好简洁的描述,并以概率方式综合相互竞争的假设。
他的工作影响了通用预测、基于压缩的学习以及智能体理论模型等研究方向,也为考察归纳偏置提供了严谨的框架:即使是通用性极强的学习者,也依赖于关于如何表示假设以及如何为其赋权的预设。
现代学习系统通常并不计算所罗门诺夫的通用分布,而是使用受限的模型类别、有限的数据集和切实可行的优化过程。理想预测器与资源受限的实现之间的区别,始终是理解其理论适用范围与局限的关键。