算法信息论 与 Kolmogorov复杂度

Shannon信息论 是建立在概率论的基础上的。算法信息论 则更接近 Turning 的可计算理论。其复杂度的定义不是基于概率,而是算法。

不太正式的说,一段字符串的 Kolmogorov复杂度 是在某一描述语言下最短的能够描述这一字符串的程序的长度。这里的“某一描述语言”定义比较含糊,可以把图灵机看作代表,其它图灵完备的描述语言都与其等价。

两个例子:
π 是无限长的无理数/超越数,但其 Kolmogorov复杂度 只是常数。简单的如 Gauss-Legendre算法 可以完全的描述 π。
一段随机生成的字符串的 Kolmogorov复杂度 是它的长度。我们所能想到的描述它的方式只是 print [string]。(在算法信息论,这才是随机字符串的定义。)

有时学科的深邃程度可以用其涉及的悖论来衡量。与 Kolmogorov复杂度 相关的是 Berry悖论:“最小的不能用20个以内的汉字描述的正整数”。其结果是 Kolmogorov复杂度的不可计算性和 Chaitin不完备定理。

Kolmogorov复杂度 是描述方面的一种复杂度的计量。在上面的两个例子看来,其解释是有点反直觉的。显然 π 要比什么意义都没有的随机字符串要“复杂”的多。如果从一个方面,即从计算复杂度的角度来看,π 的复杂度则要高的多,就是说,从其(压缩后的)描述/程序来重新构造它所需要的时间要比那个随机字符串长的多。这是 Charles Bennett 更一般性的 逻辑深度 的想法。

一个应用是 Ray Solomonoff 的算法概率(说起来这才是算法信息论的起源)。还是用上面的例子好了。想象面前有 π 的前200位数字的字符串,在直觉上,我们会认为这就是 π,并且预测下一位数字是 π 的第201位数字。从理论上,也不能排除这完全只是偶然的巧合。现在从随机生成的程序的角度考虑,比如取所有长度为200的程序(字符串),把它们输入图灵机,然后考虑能够生成 π 的前200位数字的程序。假设 π 的 Kolmogorov复杂度 是100。在这些程序里,用 print 方式的程序只有一个。而利用 π 的最小描述的程序却有指数多个,因为只要程序的前100位等于最小描述,后100位可以完全任意。当然,长度小于200的 π 的描述更不止一个。那么,上面那个200位字符串就是 π 的概率压倒性的大。这种视角相当自然的(并且是相当一般性/确定性的)构造了一个概率分布,使得结果的简单描述优于复杂描述(Occam剃刀),并且依据这一分布,我们能够概率性的预测下一个结果。

可以看到,以上的论述其实非常类似于 Graham Wallis 建立在组合数学上的对 最大熵原理 的解释。最大熵原理 也同样可以用于构造先验概率分布。

Advertisements
This entry was posted in Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s