柯尔莫哥洛夫复杂度(Kolmogorov Complexity)

柯尔莫哥洛夫复杂度(Kolmogorov Complexity)是算法信息论中的核心概念,用来度量单个对象所含的信息量。一个字符串的柯尔莫哥洛夫复杂度,定义为在固定的通用计算模型上,能够输出该字符串的最短程序的长度。程序越短,说明该串越有规律、越可压缩;程序越长,说明它越接近随机。

概述

这一概念由柯尔莫哥洛夫(Andrey Kolmogorov)等人于二十世纪六十年代独立提出。与香农信息论关注随机变量的平均信息不同,它关注的是具体对象本身的内在复杂性。例如,一个由三分之一个 π 的数字组成的长串看似随机,但其柯尔莫哥洛夫复杂度很低,因为存在一个短程序可以生成它。

核心特点

• 依赖通用机但差异有界:选用不同的通用计算模型,复杂度之差只相差一个与串无关的常数。
• 随机性判据:若一个串的复杂度约等于其自身长度,不可被明显压缩,就称其为算法随机的。
• 不可计算:不存在算法能对任意串计算其精确的柯尔莫哥洛夫复杂度,这可由停机问题归约证明。
• 可用上界近似:实际中常用压缩算法得到的长度作为复杂度的上界估计。

应用场景

柯尔莫哥洛夫复杂度为随机性、数据压缩和归纳推理提供了理论基础。它启发了基于压缩的相似度度量,可用于聚类、异常检测和序列比较。在机器学习中,它与最小描述长度原则相关,支持通过简洁性进行模型选择;在数学中,它也被用于给出某些定理的信息论式证明。

常见问题

问:为什么它不可计算却仍有价值?答:虽然无法精确计算,但它给出了信息含量的严格定义,并可用压缩长度等手段近似,理论指导意义重大。

问:它和香农熵有什么区别?答:香农熵刻画随机源的平均信息量,柯尔莫哥洛夫复杂度刻画单个具体对象的信息量,二者在期望意义下相互接近。