介绍

  首先我们将描述算法概率的发现-它的动机，它是如何被发现的，以及它的一些特性。第二节讨论了它的完备性——它发现数据规律性的完美能力，以及为什么它的不可计算性不妨碍它在实际预测中的应用。第三节和第四节是关于它的主观性和多样性——这些特征如何在训练一个强人工智能系统中发挥关键作用。第五节和第六节是关于构建和训练这种体系的实践方面。最后一节，第七节，讨论目前的进展和存在的问题。

1.发现

  我对这一领域最早的兴趣源于我对科学和数学的迷恋。然而，在最初研究几何学时，我更感兴趣的是论证是如何被发现的，而不是定理本身。同样，在科学方面，我的兴趣更多是在如何发现事物，而不是发现的内容。这似乎有点本末倒置。
  这些思想被形式化为两个目标：一个是找到解决所有数学问题的通用方法。另一个是寻找发现所有科学真理的一般方法。我觉得第一个问题比较容易，因为数学是确定性的，而科学真理是概率性的。后来，我们可以很明显的发现，这两个问题的解决方案是一样的！¹
  一些重要的启发性的想法：
  第一个——来自鲁道夫•卡尔纳普（Rudolph Carnap）：宇宙的状态可以用一个长的二进制字符串来表示，科学的主要问题是根据它的过去来预测该字符串未来的数据块。
  第二篇——来自马文•明斯基（Marvin Minsky）和约翰•麦卡锡（John McCarthy）：通用图灵机的概念。任何这样的机器都可以模拟任何可描述函数或任何其他的图灵机（通用或非通用）。它有一个必要的“停机问题”——不存在一个能够判定任何程序在给定输入上是否会结束的程序。
  第三，诺姆•乔姆斯基（Noam Chomsky）对生成语法和非生成语法的描述。为了利用它们进行预测，1958年我发明了概率语法（见（Sol 59）的附录）。
  最后的发现发生在1960年（Sol 60），当时我开始研究最普遍的确定性语法——基于通用图灵机。它的概率版本有一些惊人的特性，并且启发我，基于通用图灵机的概率语法将是可能的最通用的语法类型，并且这可能是进行预测的最佳方法。
  这就是算法概率（ALP）的诞生。在最初的版本中，我们使用一个带有输入磁带和输出磁带的通用图灵机。每当机器要求输入时，我们就给它一个0或者一个概率为1/2的1。输出磁带是某个二进制字符串x的概率（如果当机器停止时）是这个字符串的普适概率，这就是有限字符串上的普遍分布。
  我对序列预测更感兴趣（就像对Carnap的问题一样），所以我把它总结为：我们使用一种特殊的通用图灵机，它有三个磁带，分别是单向输入和输出磁带，以及无限的双向工作磁带。我们用0和1填充输入磁带，分别各有一半的概率。字符串$x$的概率是在输出磁带中以$x$开头的字符串的概率。
  第二个普遍分布可以用以下方式用于序列预测：假设$P(x1)$是字符串$x1$在分布上的概率, $P(x0)$是字符串$x0$在分布上的概率。那么$x$后面跟1的概率是

\[P(x1)/(P(x0) + P(x1))\]

  当我讨论算法概率（ALP）时，我通常会提到第二个模型。
  需要注意的是，算法概率（ALP）不需要图灵机也能正常工作。我们使用其他任何可以有效表达所有可计算函数的通用计算机或通用计算机语言，它的所有属性几乎都会继续存在。在这个意义上，所有通用计算机都是“广泛适用的”，如通用编程语言FORTRAN、LISP、C、C++、BASIC、APL、Mathematica、Maple、…

2.完备性和不可计算性

  与其他概率评估方法相比，算法概率（ALP）有什么优势吗？首先，这是目前已知的唯一完备的方法。算法概率（ALP）的完备性意味着如果在一组数据中存在任何的规律性，我们的系统就可以保证使用一个相对较小的数据样本来发现它。更确切地说，假设我们有一些数据是由一个未知的概率源$P$生成的，我们不知道$P$，而是使用代表算法概率的数据符号$P_M$。那么用$P_M$计算的概率与它们的真实概率$P$相差多少？
  $P$和$P_M$之间的误差平方和的期望值不超过$-1/2ln(P_0)$ \(E_P[\sum_{m=1}^n(P_M(a_{m+1}=1|a_1,a_2···a_m)-P(a_{m+1}=1|a_1,a_2···a_m))^2] \leq -\frac{1}{2}lnP_0\) \(lnP_0 \approx kln2\)   $P_0$是$P$的先验概率，如果我们事先知道的话，将赋值给$P$。
  $k$是数据生成器$P$的柯氏复杂性，是可描述数据生成器$P$的最短二进制程序。
  这是一个非常小的错误率。概率误差比$1/n$更快地趋近于零。快速收敛到正确的概率是算法概率（ALP）最重要的特征。收敛性适用于任何由计算机程序描述的、包含许多形式上不可计算函数的$P$。收敛性证明见（Sol 78）。它是在1968年发现的，但由于当时对算法概率（ALP）普遍没有什么兴趣，我到1975年才发布（Sol 75），直到1978年（Sol 78）才发布了证明。最初的证明是针对于一个均方损失函数和一个归一化的通用分布。但证明本身也表明了对于更一般的KL损失函数也是正确的。后来，Peter Gács（Gács 97）证明它适用于没有归一化的通用分布，Marcus Hutter（Hut 02）证明它适用于任意（非二进制）字母表和各种损失函数。
  虽然算法概率（ALP）似乎是最好的预测方法，但科学界和数学界却被算法概率（ALP）的另一个特性所困扰：它的不可计算性！这种不可计算性可归因于“停机问题”——无法判定(不存在一个程序能够判定)任何程序在给定输入上是否会有结果（结束还是继续执行下去）。
  虽然可以得到一个收敛于最终值的算法概率（ALP）的逼近序列，但在任何时候我们都无法对与最终值的接近程度做出有用的估计。
  幸运的是，对于实际的预测，我们很少需要知道“最终值”。我们真正需要知道的是：“目前的近似预测在未来的（样本外）数据有多有效？” 在所有的预测方法中都会出现这个问题，而算法概率通常能够让我们洞察如何解决这个问题。
  需要注意的是，完备性和不可计算性是互补的性质：很容易证明任何完备的预测方法都是不可计算的。而且，任何一种可计算的预测方法都不可能是完备的，总是会有很大的规律性空间，其预测是灾难性的。
  由于不可计算性对实际的预测并无障碍，可计算的预测方法必然有很大的不确定性，因此算法概率似乎比任何可计算的预测方法都更可取。
  然而，算法概率的另一个方面让人感到不安——似乎要花费太多的时间和内存才能找到一个好的预测。在第5节中，我们将更详细地讨论这个问题。有一种实现算法概率的技术，这似乎只需要很少的时间就可以在数据中找到规律性。

3.主观性

  科学中的主观性通常被认为是邪恶的。这是“真正的科学”中没有的东西，如果它真的发生了，结果就会变得一点也不“科学”。伟大的统计学家R.A.Fisher就是这样认为的。他想摆脱主观性使统计学成为“一门真正的科学”，而主观性一直是统计学历史的一部分。
  我觉得费舍尔在这件事上犯了严重的错误，他在这方面的工作严重损害了科学界对统计学的理解——损害已经在慢慢恢复。
  统计中误差的两个重要来源是有限样本量和模型选择误差。有限样本部分已经被意识到了一段时间。模型选择误差是统计估计中的一个必要组成部分，这是一个相对较新的概念，但算法概率（ALP）清楚地表明了我们对此的理解。而且，这种误差是非常主观的，可以强烈地依赖于科学家一生的经验。
  在算法概率（ALP）中，这种主观性发生在“工具”(通用计算机或通用计算机语言)的选择上。在一开始，（从“不变性定理”）就知道，这种选择只能通过有限的因素影响概率估计，因为任何通用器件都可以用一个有限程序模拟任何其他通用器件。然而，这个“有限因素”可能是巨大的-在非常相似的计算机语言之间切换，这通常会给概率估计带来超过$2^{1000}$种变化！
  为了理解主观性在人类或智能机器生活中的作用，让我们考虑一下人类的婴儿。他天生就具有某些能力，这些能力假定了它在所处环境的某些先验特征。他期望呼吸空气，他的免疫系统是为某些类型的挑战而设计的，他通常能够在其早期环境中所发现的任何人类语言中应对自如。随着他的成长，他的先验信息被他的经验修正和增强了。
  我们正在研究的人工智能系统就是这样的。每次它解决一个问题，无论成功还是不成功，它都会更新它的先验信息中与该问题解决技术相关的部分。它的先验信息以一种非常类似于一个人类成长的方式随着系统生命体验的增长而增长。
  综上所述，算法概率的主观性是智能系统将过去的经验融入到解决未来问题技术的必要特征。

4.多样性

  在第1节中，我们描述了基于随机输入的通用图灵机的算法概率（ALP）。一个考虑了所有的预测方法，并基于所有这些预测因子的加权进行预测的等价模型。每个预测因子的权重是两个因素的乘积：第一个是每个预测因子的先验概率。这个预测因子的概率是由一个随机输入的通用图灵机来描述。如果预测因子只用了少量的数据位来描述，它将被赋予很高的先验概率。第二个因素是预测因子分配给用于预测的历史数据的概率。我们可以把每种预测方法看作是数据的一种模型或解释。许多人只会使用最好的模型或解释，而抛弃其他的。最小描述长度（RIS 78）和最小消息长度（WAL 68）是只使用这类最佳模型的算法概率（ALP）的两种常用的近似方法。当一个模型比其他任何模型都好很多时，最小描述长度、最小消息长度和算法概率（ALP）给出的预测是相同的。如果最佳模型有多个且有相同的权重，那么算法概率（ALP）给出结果是更好的。
  然而，这并不是算法概率（ALP）使用多样性解释的主要优势。如果我们只做一种单一的预测，那么丢弃非最优模型带来的损失通常很小。但是如果我们正在研究一系列的预测问题，我们常常会发现，过去最有效的模型不足以应对新的问题。当这发生在科学领域时，我们必须修正我们的旧理论。一个好的科学家会记住许多过去有用但被抛弃的理论，要么是因为他们不相信新的数据，要么是因为他们先入为主得认为“不可能”。新理论的特点是利用过去失败的模型，把它们拆开，并利用这些创建新的候选理论。通过手头有大量多样的（非最优）模型来创建新的试验模型，算法概率（ALP）是创建新的、有效的预测模型的最好选择。
  当算法概率应用于遗传程序设计时，其丰富的模型多样性，可以期望得到非常好的、非常快的且不太会“早收敛”的解决办法。

5.计算成本

  如果算法概率确实是如此有效，那么很自然地会询问它的计算成本，看起来评估大量的预测模型需要花费大量时间。然而我们发现通过使用类似于Levin针对不同类型的问题使用的搜索技术，可以在接近最佳速度的情况下搜索到好的模型。有时可能需要很长时间才能找到一个非常好的解，但没有其他搜索技术能够更快地找到这个解。
  这个过程有效的第一个近似：假设我们有一台带有输入和输出磁带和一个很大内存的通用机器。我们有一个二进制字符串$x$，我们想推断，找到$x$的各种可能延续的概率。我们可以简单地将许多随机字符串输入到机器中，并注意以$x$开头的输出的输入。不过这需要大量的时间。有一种更有效率的方法：
  我们选择一个小的时间限制T，然后测试所有输入字符串，就像 \(t_k < T2^{-l_k}\)   这里的$l_k$是正在测试的第$k$个输入字符串的长度，$t_k$是测试它所需的时间。测试本身就是看输出是否以字符串$x$开始。如果我们没有找到期望输出种类的输入，我们将$T$加倍，然后执行相同的测试程序。我们重复这个程序，直到找到以$x$开头的输出字符串的输入字符串。如果我们给每个这样的输出一个$2^{-l_k}$的权重（$l_k$是其输入的长度），加权输出的字符串将得到字符串$x$可能的概率分布。
  在给定的示例中，假定所给长度的所有输入字符串具有相同的概率。随着系统继续预测一个长的二进制序列，产生输出的输入序列会出现一定的规律性。这些规律性被用于对所给长度的输入字符串上施加非均匀概率分布。在未来，这种输入分布的“适应性”使我们能够更快地找到我们想要预测的数据字符串的连续性。

6.训练顺序

  很明显，呈现给这个系统的问题的顺序将会决定成熟的系统是否比初期的系统更有能力的一个重要因素。设计这类训练顺序是智能化发展的关键和挑战性问题。
  在大多数情况下，为智能机器设计训练顺序与为人类的学生设计训练顺序非常相似。然而，在早期两者之间有着明显的区别。在机器的早期训练中，我们确切地知道机器对任何输入问题的反应。我们可以计算出机器解决早期问题所需时间的精确上限。就是： \(T_i/P_i\)   $P_i$是机器分配给训练者已知解的概率。$T_i$是测试这个解决办法所需的时间。我把这个上限称为“概念跳跃大小”（CJS）。它告诉我们对于一个特定的人工智能来说这个问题有多难。我说“上限”，是因为系统可能会发现比训练者已知的更好、更快的解决方案。
  这个CJS估计使我们能够很容易地确定，一个问题在系统训练中的某个特定点上是否是可行的。在系统的生命周期内，特定问题的$P_i$将发生变化。对于一个构造得当的训练顺序，与特定问题相关的$P_i$应随着系统的成熟而提高。
  最终，在一台非常智能的机器的任何训练顺序中，训练者将无法对系统进行足够详细地了解，从而计算出CJS值。然后，训练者将机器视为人类学生。通过标注哪些问题对于机器来说是容易的，哪些问题对于机器来说是困难的，训练者将设计出非常近似的模型，并利用该模型设计训练问题。
  学习如何训练智能机器，对于如何培训学生也会产生非常有用的见解。

7.目前的进展？

  Schmidhuber（Sch 02）编程实现了一个我们讨论过的包含一些特性的系统。在找到一个早期的，更容易的问题的递归的解后，它已经能够计算“汉诺塔”问题的递归解。
  为了取得进一步的进展，我们需要更大、更详细的训练——编写此类训练是一个持续的“开放性问题”（Sol 89）。
  使用系统过去的经验，对其进行更新的过程是正在进行研究的另一个重要的领域。我们认为PPM（部分匹配预测（Tea 95））、APPM（PPM的增强版本）和SVR（支持向量回归（Sap 09））是可能更新的系统。更新算法的改进仍然是另一个持续的“开放性问题”。

1 本文开头的主题在“算法概率的发现”（Sol 97）中进行了详细的讨论。在这里，我们将总结论文中的一些想法，并处理重要的后续发展。

算法概率的发现--它的性质及其在强人工智能中的应用
雷•所罗门诺夫
客座教授 计算机学习研究中心 伦敦皇家霍洛威学院
瑞士曼诺卢加诺，CH-6928，凯丹广场2号，IDSIA rjsolo@ieee.org http://world.std.com/˜rjs/pubs.html

参考文献
[1] （G’acs 74）G’acs。P、 《Kolmogorov复杂性及其应用导论》中的定理5.2.1，Springer Verlag，纽约，第2版，第328-331页，1997。
[2] （Hut 02）Hutter，M.，“一般损失和字母表通用贝叶斯序列预测的最优性” http://www.idsia.ch/marcus/ai/
[3] （Ris 78）Rissanen，J.“通过最短数据描述建模”，Automatica，14:465–471，1978。
[4] （Sch 02）Schmidhuber，J.，“最优排序问题求解器”，TR IDSIA-12-02，2002年7月31日。http://www.idsia.ch/juergen/oops.html
[5] （Sap 09）Sapankevych，N.和Sankar，R.，“使用支持向量机的时间序列预测：调查”，IEEE计算智能第4卷，第2期，第24-38页，2009年5月
[6]（（SOL 59）Solomonoff，R.J.）关于学习翻译语言和检索信息的机器的进度报告，文献和图书馆学进展，第三卷，第。2，第941-953页。（1959年9月会议记录）
[7] (Sol 60) Solomonoff, R.J. “归纳推理一般理论的初步报告。” （报告V-1311960年2月修订），合同AF 49（639）-376，报告ZTB-138，Zator公司，马萨诸塞州剑桥，1960年11月。
[8] (Sol 75) Solomonoff, R.J. “归纳推理理论——解决模式识别和人工智能问题的统一方法，” 第四届国际人工智能会议记录，第274-280页，格鲁吉亚第比利斯，苏联，1975年9月。
[9]（SOL 78）Solomonoff，R.J.“基于复杂性的归纳系统：比较和收敛定理”，IEEE Trimes。关于信息论，第IT-24卷，第4期，第422-432页，1978年7月。
[10] （Sol 89）Solomonoff，R.J.，“基于算法概率的增量学习系统”，以色列第六届人工智能、计算机视觉和模式识别会议论文集，第515-527页，1989年12月。
[11] （Sol 97）Solomonoff，R.J.“算法概率的发现”，《计算机与系统科学杂志》，第55卷，第1期，第73-88页，1997年8月。
[12] （Tea 95）Teahan，W.J.“PPM的概率估计”，新西兰计算机科学研究学生会议的过程，怀卡托大学，汉密尔顿，新西兰，1995年。 http://cotty.16x16.com/compress/peppm.htm网站
[13] (Wal 68) Wallace, C.S and Boulton, D.M. “用于分类的信息度量”，《计算机期刊》，11:185-194页，1968年。