算法概率

在算法信息理论中，算法概率，也被称为所罗门诺夫概率，是一种为给定观察分配先验概率的数学方法。它是由RaySolomonoff在20世纪60年代发明的。它被用于归纳推理理论和算法的分析中。在他的归纳推理的一般理论中，所罗门诺夫将该方法与贝叶斯规则一起使用，以获得对算法未来输出的预测概率。在所使用的数学形式中，观察结果具有有限二进制字符串的形式，被视为图灵机的输出，而通用先验是由程序（即通用图灵机的输入）的概率分布计算出的有限二进制字符串集合的概率分布。在图灵可计算性的意义上，该先验是普遍的，也就是说，没有一个字符串的概率为零。它是不可计算的，但它可以被近似计算。

算法概率是所罗门诺夫的归纳推理理论的主要成分，即基于观察的预测理论；发明它的目的是将其用于机器学习；给定一个符号序列，接下来会是哪一个？所罗门诺夫的理论提供了一个在某种意义上是最优的答案，尽管它是不可计算的。与卡尔-波普尔的非正式归纳推理理论不同，所罗门诺夫的理论在数学上是严谨的。所罗门诺夫的算法概率的四个主要灵感是。奥卡姆剃刀、伊壁鸠鲁的多重解释原则、现代计算理论（例如使用通用图灵机）和贝叶斯的预测规则。奥卡姆剃刀和伊壁鸠鲁原则本质上是对普遍先验的两种不同的非数学近似。奥卡姆剃刀：在与观察到的现象相一致的理论中，应该选择最简单的理论。伊壁鸠鲁的多重解释原则：如果有一个以上的理论与观察结果相一致，就保留所有这些理论。普遍先验的核心是计算机的抽象模型，如通用图灵机。任何抽象计算机都可以，只要它是图灵完备的，也就是说，每个可计算的函数至少有一个程序可以在抽象计算机上计算其应用。抽象计算机被用来赋予简单解释这一短语的精确含义。在所使用的形式主义中，解释或现象的理论，是在抽象计算机上运行时产生观察字符串的计算机程序。每个计算机程序都被分配了一个与它的长度相对应的权重。普遍概率分布是随机输入的所有可能的输出串上的概率分布，为每个有限的输出前缀q分配计算以q开始的东西的程序的概率之和。一个复杂的解释是一个长的计算机程序。简单的解释更有可能，所以一个高概率的观察串是由一个短的计算机程序产生的，也可能是由大量稍长的计算机程序产生的。低概率的观察串是一个只能由长的计算机程序产生的观察串。算法概率与Kolmogorov复杂性的概念密切相关。科尔莫戈罗夫引入复杂性的动机是信息论和随机性中的问题，而所罗门诺夫引入算法复杂性的原因则不同：归纳推理。

所罗门诺夫发明了一个可以替代贝叶斯规则中每个实际先验概率的单一通用先验概率，并将科尔莫戈罗夫复杂性作为一个副产品。它预测了该观察最可能的延续，并提供了这种延续的可能性的衡量标准。Solomonoff的可列举措施在某种强大的意义上是普遍的，但计算时间可能是无限的。处理这个问题的一种方法是列昂尼德-列文的搜索算法的变种，它限制了计算可能程序的成功率的时间，较短的程序会得到更多的时间。当运行的时间越来越长时，它将产生一连串的近似值，这些近似值将收敛于普遍的概率分布。处理这个问题的其他方法包括通过包括训练序列来限制搜索空间。Solomonoff证明这种分布在一个常数范围内是机器不变的（称为不变性定理）