怎么学习算法信息论? 第1页

与1950年代不同，彼时柯尔莫哥洛夫的工作集中在将信息论应用到数学的各个分支上，而1960年代他创建了新的数学领域：

算法信息论，算法概率论。

通过分析各种信息理论，柯尔莫哥洛夫区分了其中三种方法（[IA]，第251-253页）：

1.纯粹的组合学方法。 2.纯粹的概率论方法。 3.算法方法。

在关于他的信息论著作以及各种应用的评论中（[IA]，第251-253页），柯尔莫哥洛夫描述了第一种方法的本质：

“在组合学方法中，一个包含 个对象的集合，其中某元素能传输的信息量（quantity of information）被视为 的二进制对数（R. Hartley，1928年）。例如，对 个字母的字母表，能组成的不同单词数目是

，

这里 是包含第 个字母的次数（ ）。

对应的信息量是

如果 趋于无穷大，我们可得到如下渐进公式

读者肯定注意到了该式与信息论中表达式的相似性：

“如果我们的工作是通过众所周知的独立试验的模式构建，那么渐近公式（i）是（ii）式和大数定律的显然结果，但是（i）的适用范围是更广的（例如，可参见有关通过非平稳信道传输信息的工作）。总的来说，我认为尽可能消除多余的概率假设非常有用。我在讲课中反复强调过纯粹组合学方法解决信息理论问题的适当价值。

我和我的同事有关 熵和紧函数类的 容量的工作，基于熵的纯组合学方法。这里的 熵 是从一类函数中选择某个函数所需的信息量；而 容量 则是指能由中的元素编码的信息量，若来自 的这些元素（彼此间的距离不小于）可被置信地区分。”

以上已经描述了信息论基本概念的概率方法（1950年代）。对于算法方法，柯尔莫哥洛夫的思路是在算法和可计算函数的基础上定义熵（或者，复杂度）和信息量。

在1963年4月24日莫斯科数学会概率部的报告中，柯尔莫哥洛夫描述了算法方法的本质和背景：

“人们在很多情形下，不得不处理非常长的符号序列。其中一些序列（例如5位对数表中的符号序列）允许用简单的逻辑定义，因此可以通过对简单模式的计算（尽管有时会显得笨拙）来得到。

其他一些序列似乎没法用足够简单的”合理“方式来构建。例如，对于随机数表中相当长的片段，情况就是这样。

这里就出现了构建严格的数学理论以解决这些差异的需要。

让我们遵循信息论的传统，将讨论限于二进制序列，即如下类型：

其中 或 1。记长度为 的此种序列构成的集合是 ， .“

柯尔莫哥洛夫强调，与以上成形的想法相应，在引入序列 的“复杂度”的度量 时，采用不同的方法是可能的，尽管很难避免某些任意性。 柯尔莫哥洛夫在[IA，第253页]中写道：“这项基本发现，是由我与R. Solomonoff独立且同时完成的：即算法理论使我们能够通过近不变性的复杂度来对此任意性加以限制（不同方法的区别仅在于边界项）。”

让我们用自然数来标识每个序列 ，其二进制扩展由有序集 唯一地确定。这种标识使我们能够讨论定义域和值域均在 上的部分递归（可计算）函数 。根据定义，柯尔莫哥洛夫假设对于任一个函数 ，

并称之为模式 下的”对象 的复杂度“。

然后，柯尔莫哥洛夫引入了最优（Optimal）函数 的类 ，其性质为，对于任何其他函数 都存在一个常数C，使得对于所有

。

由柯尔莫哥洛夫和Solomonoff [185]独立发现的基本结果指出，可计算函数 的类 不为空。于是我们总可以构造函数

,

称之为序列 的”复杂度“（复杂性的度量）。在这个意义上，类 的所有最优函数都是等价的，因而 ([K461] [[A-13], page 243)：”从渐进的观点，复杂度 并不依赖于所选最优方法的随机特性“。

与单个对象 的“复杂度” （也称为“简单柯尔莫哥洛夫熵”）一起，柯尔莫哥洛夫引入了对象 相对 的条件熵 ，以及信息 。 [柯尔莫哥洛夫引入的熵 ， ，...与后来发展的“递归函数的复杂度”的概念有密切关联，后者由Schnorr于1970年代引入[166-168]，定义为某函数相对“最优枚举”的数目的对数。]

所有这些概念都由柯尔莫哥洛夫在如下三篇论文得以引入和研究：“定义信息量的三种方法(Three approaches to the definition of the quantity of information)” [K320][IA-10]，“信息论和概率论的逻辑基础(On the logical foundations of information theory and probability theory)” [K354]， [IA-12]和“信息论的组合学基础和概率演算（Combinatorial foundations of information theory and the calculus of probability）” [K461][[A-13]，也可参见他的学生和其他研究人员的工作（更多详细信息，见AH Sheny在[IA]第257-261页的评论）。这些概念催生了算法信息论这一新领域的发展。另见Chaitin的书[28]。

柯尔莫哥洛夫引入的“复杂度”的思想使他重新思考了由0和1组成的序列 ，例如，哪一类可以被视为随机的，哪一类不能。

举个例子，如果某人公正地将无偏硬币扔了 次，并用1和0表示结果，那么对于足够大的 ，结果 或 很难被认为是随机的，尽管从概率的角度来看，每个这样的序列（与其他序列一样）具有相同的概率 。因此，经典概率论无法回答如何区分“随机”和“非随机”序列，以及单个序列的“随机性”的真正含义是什么。

区分无限序列（例如二进制） 的子类的想法可以追溯到 R. von Mises，他使用了德语单词“ Kollectiv”。在他的方案下，要使序列 是“随机的”，必要条件是存在极限 ，其中 是 中1的个数。序列 存在此极限，这表明此条件对于“随机性”是必要的，但绝非充分的。 ”

这就是von Mises 提出进一步要求的原因，他说，序列及其任一无限子序列（通过任何可接受的选择规则得到），1的平均频率应当相同。但是他没有提供确切的定义。 1940年，Church [81]给出了“可接受的选择规则”的可能定义，从而正式定义了随机序列，并使von Mises的概念更为精准。

柯尔莫哥洛夫的工作“关于随机数表（On tables of random numbers）” [K311]，[IA-9]的重要性，正如他在[IA-9]引言中所说的那样，代表了他“尝试理解 von Mises 对概率的频率诠释”的阶段，主要在于引入一种更笼统的选择模式，该模式扩大了可接受的选择规则的类，并指出“子序列中的项的顺序不一定与它们在原序列中的一致”（Loveland在1966年独立获得了这一结果[119，120]）。如此定义的这类序列在von Mises-Kolmogorov-Loveland的意义上称为随机序列的类，且所有这些序列在von Mises（Church）的意义上都是随机的。但是，相反的说法是不正确的（如Loveland所示）。

在[K311]中（另见著作[IA]俄语版204页的“作者评论”），柯尔莫哥洛夫讨论了他对随机选择算法的更宽泛的定义（与von Mises相比），并强调“与von Mises相比，主要差异是整个概念的严格有限的实质，并为频率稳定性引入了定量界限。” 柯尔莫哥洛夫的意思是，可以为足够长的有限序列以及无限序列定义随机性的度量。

由柯尔莫哥洛夫在[K311]中发展的，基于有限选择规则系统的方法，自然可以称为“频率”方法。

后来，柯尔莫哥洛夫与他两位学生Martin-Léf[125]和Levin [107]基于复杂度的概念发展了一种方法，其中复杂度最大的那些序列 被称为随机的。 [由于复杂度 ，那么当度 ，则称序列 是随机的。] 更多详细信息，请参见[IA]第272页。

此后，柯尔莫哥洛夫反复提到“随机性和复杂度”问题。在1970年尼斯举行的国际数学大会上，他作了题为“信息理论和概率演算的组合学基础”的报告，不幸的是，该报告直到1983年才发表[K461][IA-13]。在1982年第比利斯举行的第四届苏联-日本概率论与数理统计研讨会上，柯尔莫哥洛夫作了报告“论概率论的逻辑基础 (On logical foundations of probability theory)” [K462]，[PS-53]，其中他认为“随机性意味着规则（regularity）的缺失”，并解释了有限对象的复杂度概念如何使这一思想变得精确。

柯尔莫哥洛夫和他的学生V. A. Uspenskii撰写的论坛报告“算法和随机性（ Algorithms and randomness ）”提交给了1986年伯努利学会（Bernoulli Society）第一次世界大会，它的全文在[K475]。它包含了柯尔莫哥洛夫与其学生和追随者关于“随机性”定义的算法方法的概念和结果的最详尽的阐述。另可参见论文Zvonkin和Levin [215]和Vovk [207]，以及Li和Vitanyi的详尽研究[112]。

本系列文章翻译自Shiryaev院士在1989年，为他的老师柯尔莫哥洛夫（Kolmogorov）写的长文《Kolmogorov：life and creative activities》（俄文Жизнь и творчество. Биографический очерк ），感谢Shiryaev院士允许我翻译他的著作。

流传的说法——柯尔莫哥洛夫”放弃“概率论，就是指本文讲到的、1960年代柯大师基于算法思想对概率论、信息论的重构工作。

本阶段柯尔莫哥洛夫对确定性、随机性、复杂性、概率论等概念的数学和哲学思考，几乎是他一生兴趣的总结。

本文是系列文章的第九篇，我根据相关内容补充了一些图片。还会间断做些优化更新，准确性、行文等问题，欢迎指教~。

第一篇：宋维凯HEOM：译作——老师柯尔莫戈洛夫的生平和工作（1）：童年和中小学

第二篇：宋维凯HEOM：译作——老师柯尔莫戈洛夫的生平和工作（2）：大学时代

第三篇：宋维凯HEOM：译作——老师柯尔莫戈洛夫的生平和工作（3）：1930年代，现代概率论、随机过程的创立

第七篇：宋维凯HEOM：译作——老师柯尔莫戈洛夫的生平和工作（7）：1950年代之动力系统，三体问题与KAM理论，信息论数学基础，熵