柯尔莫哥洛夫复杂度是指相对于某个固定的通用计算系统,能够生成指定有限对象并随后停机的最短程序的长度。它将这样一种直观认识形式化:如果一个对象具有简短的有效描述,它就是简单的;如果不存在比对象本身短得多的描述,它就是复杂的。同一个符号重复一百万次,可以用一条简短的指令生成;而一个典型的百万比特串则无法如此生成。这一理论关注的是单个对象的信息含量,而不只是概率源产生的平均信息量。
这一概念由雷·所罗门诺夫、安德雷·柯尔莫哥洛夫和格雷戈里·柴廷在20世纪60年代各自独立发展而来,是算法信息论的核心概念。它将可计算性理论、随机性、数据压缩、数理逻辑与归纳推理联系起来。其定义所涉及的量一般是不可计算的,但这一局限本身也带来了重要的数学成果:它为压缩、随机性证明以及通过机械方法发现模式划定了精确的界限。
通常区分两种主要形式:普通复杂度,一般记为 ;无前缀复杂度,一般记为 。在有关编码、概率和无限随机序列的精确定理中,两者的差别十分重要。它们描述的都是理想化的最小描述长度,既不是某个特定压缩工具的输出大小,也不是生成一个对象所需的计算工作量。
历史起源与思想背景
柯尔莫哥洛夫复杂度的形成有两条不同的发展脉络:计算的数学理论与信息的概率理论。1936 年,艾伦·图灵提出了一种有效计算的通用模型,如今称为图灵机,并确立了机械化计算过程的根本局限。通用图灵机能够根据编码后的描述模拟其他机器。这种通用性使得程序本身可以被视为对某个对象的有限描述。
克劳德·香农于 1948 年发表的研究奠定了信息论的基础,使其成为一门以数学方法研究通信的学科。香农熵衡量的是与某个概率分布相关的不确定性,而他的编码定理则将这种不确定性与平均消息长度联系起来。然而,另一个问题仍未得到解答:不依赖预先指定的信源分布,一个特定字符串本身究竟包含多少信息?两个字符串即使长度相同,所含的零和一的数量也相同,其排列方式的简单程度仍可能相差甚远。
所罗门诺夫从预测和归纳推断的角度研究了这一问题。在早期报告的基础上,他于 1964 年发表的研究为较短程序生成的假设赋予了更大的权重。其目标不只是描述数据,而是为从观测中学习建立一套通用的数学理论。他的方法将通用计算与概率预测联系起来,成为所罗门诺夫归纳的基础。
柯尔莫哥洛夫于 1965 年发表的论文,通常译作《关于信息定量定义的三种途径》,通过个体对象的最短算法描述,直接定义了该对象的复杂度。柴廷独立发展了密切相关的思想,于 1966 年发表论文,随后又探讨了这些思想对随机性和数学不完备性的意义。他们的研究动机并不完全相同,但都以基于有效描述的精确度量,取代了对简单性的非形式化诉求。
在随后的数十年里,这一理论发展出了几种相互补充的形式。佩尔·马丁-勒夫于 1966 年提出了针对随机无穷序列的有效统计检验。列昂尼德·列文、柴廷等人的研究阐明了自定界描述、通用概率以及编码关系的重要性。后续研究又发展出算法统计、信息距离、资源受限复杂度和逻辑深度等概念。因此,这一领域不再只是对压缩的形式化阐述,而是为个体信息、随机性、预测以及计算的局限提供了一套共同语言。
通用描述、普通复杂度与前缀复杂度
令 表示有限二进制串的集合,令 表示字符串 的长度,以比特为单位。固定一台最优通用描述机 。字符串 的普通柯尔莫哥洛夫复杂度定义为
这台机器必须恰好输出 ,然后停机。一个持续输出以 开头的序列、却永不停机的程序,不符合这一定义。“最优”是指, 能够模拟任何其他有效描述系统,且所需的额外描述长度仅取决于被模拟的系统,而不取决于 。
核心的不变性定理指出,对于任意两台最优通用机 和 ,都存在一个常数 ,使得对每个 都有
成立。一个固定的模拟器或编译器提供了将一台机器的程序转换为另一台机器的程序所需的额外描述。该定理并没有选出唯一正确的机器,也没有使所有有限对象的复杂度数值都相同。它所保证的是:更换描述语言所带来的优势,不会随着对象增大而无限增长。
无前缀复杂度提出了一项额外要求。对于无前缀机,任何停机程序都不能是另一个停机程序的真前缀。因此,其有效程序构成一种前缀码,无需外部结束标记即可识别程序的边界。对于一台最优通用无前缀机,有
前缀条件使程序长度满足克拉夫特不等式,并使其与概率之间形成尤为简洁的联系。普通程序可以利用外部提供的自身长度作为信息;无前缀程序则必须编码足够的结构,以便界定自身的边界。因此,
而一个标准的反向界是
其中要求 足够大。按照惯例,这类编码公式中的所有对数都以二为底。
对于二进制串以外的有限对象,可以通过有效编码来处理。整数、图、图像和数学表达式都可以表示为字符串。如果两种编码之间可以通过固定的可计算转换相互转化,那么它们的复杂度之差至多为一个常数。同样的结论也适用于固定的有效操作:对于每个部分可计算函数 ,只要 有定义,就有
其中的常数包含了实现 的程序的长度。这并不意味着,在实际尺度下,任何非形式化的表示方式选择都无关紧要:一个很大的固定常数可能主导短描述的长度,而一种表示方式也可能纳入大量背景知识。
不可计算性与形式证明的局限
柯尔莫哥洛夫复杂度是一个定义精确的整数值函数,但不存在能对每个输入都算出其精确值的算法。障碍并不只是穷举搜索速度太慢。程序可能永不停机,因此,遍历所有更短的候选程序,通常也无法确定它们之中没有任何一个最终会输出所需的对象。这使复杂度与停机问题联系起来,不过,也可以通过直接导出矛盾来证明其不可计算性。
假设存在一个程序,能够精确计算 。给定整数 ,它就可以按照某种固定且可有效执行的顺序枚举字符串,并选出第一个复杂度超过 的字符串 。这样的字符串必然存在,因为短程序的数量少于字符串的数量。然而,这样一来, 就有了一个简短的描述:编码 ,运行假定存在的复杂度计算程序,再执行上述搜索。这只需要 比特;当 足够大时,这就与 矛盾。将一个对象描述为“第一个没有简短描述的对象”,本身就存在一种内在冲突,而上述论证正是这种冲突的严格表述。
不过,复杂度是上半可计算的。一个过程可以交错地模拟所有程序的执行步骤,并针对每个输出,记录迄今找到的最短程序。每当发现一个更短且成功产生该输出的程序时,当前的上界就会下降。这个上界最终会达到真实值,但不存在一种通用的有效方法来判定何时已经达到。因此,未能发现进一步压缩的方法,并不能证明对象不可压缩。
固定的形式理论所能证明的内容也存在相应的局限。在适当的、可靠且可有效公理化的理论中,存在一个界限:超过这一界限,理论就无法证明某个明确指定的具体字符串的复杂度大于该界限。否则,一个简短的过程就可以搜索该理论中的证明,找到这样的断言,并输出其中的字符串,从而与所声称的复杂度下界矛盾。这一现象尤其与柴廷不完备定理有关。这个阈值取决于所用的理论、选定的通用机以及具体的形式化方式。
这些局限并不妨碍证明高复杂度对象的存在,也不妨碍利用复杂度论证来证明通常的数学定理。通过计数,可以确立不可压缩字符串的存在,而无须用有效方法逐一找出它们。同样,限制描述语言或限定运行时间,也可以得到可计算的变体。关键在于区分两件事:证明一般性的结构事实,以及拥有一个统一的过程,能够确定任意单个数据在不加限制时的精确复杂度。
不可压缩性与计数方法
关于柯尔莫哥洛夫复杂度,最直接的事实是:绝大多数足够长的字符串都是不可压缩的。长度为 的二进制字符串共有 个,但长度小于 的二进制程序只有
个。每个程序至多产生一个输出。因此,在长度为 的字符串中,普通复杂度低于 的字符串少于 个。对于均匀随机选取的 比特字符串 ,有
例如,在这种以描述长度精确定义的意义下,长度为 的字符串中,能够压缩超过 20 比特的比例不到 分之一;阈值处的具体表述取决于采用严格不等式还是非严格不等式。
每个字符串也都有一种直接写出其内容的描述。普通程序可以包含字符串本身,再加上一条固定的输出指令,因此
对于前缀复杂度,一个一般性的上界是
因为直接写出的数据需要以自定界方式编码其长度,或采用等效的边界约定。因此,说看似随机的字符串的复杂度“大致等于其长度”,在主导项的意义上是正确的;但要给出精确表述,就必须区分普通复杂度和前缀复杂度。
高度规则的字符串则不同。如果 表示 个零,那么 :一个简短的程序可以输出 次零;反过来,根据输出的长度也能还原 。对于可计算的无限序列,例如 的二进制展开,其前 比特的复杂度至多为 。这些前缀可能呈现复杂的局部模式,也可能难以用常规压缩工具压缩,但在不限制描述方式的情况下,它们的描述复杂度很小。
不可压缩性方法将这些观察转化为证明。典型的论证会选取一个不可压缩对象,并说明:如果它具有某种假定的异常性质,就能对它作出过于简短的描述。例如,零和一的数量若极不均衡,就会减少候选字符串的数量。只要给出这种不均衡的程度,以及某个字符串在候选集合中的序号,就能重建该字符串,所需比特数少于描述一个完全不受限制的长度为 的字符串所需的比特数。
同样的策略也适用于重复子串、图的性质以及计算任务的下界。它可以用针对一个有代表性的不可压缩对象的描述论证,取代冗长的平均情形计数论证。不过,仍然必须仔细核算各项开销:描述中必须包含长度、参数、重建指令以及所有辅助选择。忽略这些开销,可能会使一个看似合理的压缩论证变成无效论证。
熵、编码与通用概率
柯尔莫哥洛夫复杂度与信息熵回答的是不同的问题。熵是概率分布的性质;复杂度则是单个对象相对于某台通用机器的性质。如果随机变量 的概率为 ,其熵为
这给出的是平均编码长度的基准,而不是为每个结果赋予一种内在的描述复杂度。一个对象在某个分布下的概率可能很低,却仍然可以由一个很短的程序生成。
这两个量通过编码定理联系起来。对于可计算分布 ,基于码长 的描述给出如下形式的上界:
这里, 表示以适当的有效表示方式描述该分布的程序长度。这个上界既计入数据的描述代价,也计入模型的描述代价。这解释了为什么一个极其复杂、将某个特定字符串的概率设为一的分布,并不能自动证明该字符串具有很短的无条件描述:描述这个分布可能与描述该字符串同样困难。
对于概率能够以有效方式给出的有限分布,在固定的表示方式和编码约定下,以该分布为条件的前缀复杂度的期望值接近熵:
如果不将分布作为背景信息提供,相应的上界就要计入该分布的描述代价。霍夫曼编码和算术编码等常规方法,为这类依赖模型的编码原理提供了可实际构造的实现,但它们并不能计算柯尔莫哥洛夫复杂度。
更深层的联系涉及通用算法概率。对于一台最优的通用无前缀机器 ,定义离散先验半测度
它之所以是半测度,是因为有些程序所对应的概率可能永远不会产生停机输出。它是下半可计算的:模拟运行的程序每当停机时,就贡献相应的概率质量。通用性意味着, 在乘法常数意义下支配每一个下半可计算的离散半测度,其中常数取决于被支配的半测度。
与列文相关的算法编码定理指出:
尽管 汇总了所有生成 的程序的贡献,其负对数与最短程序长度之差仍不超过一个常数。这在描述长度与通用概率之间建立了精确的桥梁。必须将它与所罗门诺夫预测中用于无限序列续接的相关半测度区分开来;在后者中,概率赋予的是所有以指定前缀开头的输出。
有限不可压缩性与无限随机性
对于有限字符串,随机性必然是相对于某种编码约定、某个长度以及所允许的复杂度亏损而言的。例如,当一个字符串满足
时,就可以说它在允许 比特亏损的意义下不可压缩。
这并不意味着有限随机性是一种独立于表示方式、可观测的物理性质。经过特殊选择的通用机,可以为某个特定字符串设置一条简短的专用指令。不变性定理将由此造成的变化限制在一个依赖于机器的常数范围内,但对于规模较小的例子,这个常数的影响依然存在。
对于无限二进制序列,则有更强的理论可用。马丁–勒夫随机性将这样一种要求形式化:序列应避开所有能够有效描述的、测度为零的统计例外集。马丁–勒夫检验是一个一致有效可枚举的开集序列 ,这些开集在公平抛硬币测度下的概率满足 。如果一个序列属于每一个 ,它就未通过该检验。随机序列能够通过所有这类有效检验。
莱文–施诺尔定理将这一统计定义与前缀复杂度联系起来。无限二进制序列 相对于公平抛硬币测度具有马丁–勒夫随机性,当且仅当存在常数 ,使得对每个 都有
其中, 表示该序列的前 比特。这里使用前缀复杂度至关重要:将 换成普通复杂度,就无法得到相同的刻画。相继前缀的普通复杂度存在不可避免的振荡。
这一概念蕴含了一些熟悉的统计性质。马丁–勒夫随机序列中,0 和 1 各自的极限频率均为二分之一,并且这类序列满足许多概率为一的定律的有效版本。反过来则不成立:具有正确的频率或正规性并不足以保证随机性。有些可计算序列是正规的,即每个有限比特块都以预期的极限频率出现,但没有任何可计算的无限序列具有马丁–勒夫随机性。只要给出前缀的长度,一个简短的生成程序就能描述任意长的前缀。
一个尤为重要的例子是最优通用无前缀机的柴廷常数,即其停机概率:
实数 是下半可计算的,但不可计算,而其二进制展开具有马丁–勒夫随机性。给定它的前 比特以及相关的机器约定,就能判定所有长度不超过 的程序是否停机。这将最高程度的有效随机性与有关计算的高度结构化信息联系在一起:不可压缩并不意味着没有数学意义。
条件复杂度与共享信息
条件复杂度衡量的是:在免费提供另一个对象的情况下,描述某个对象所需的长度。对于具有辅助输入的通用机,
条件可以是字符串、整数、模型,也可以是按照固定的有效约定编码的元组。一幅数字图像的无条件复杂度可能很大,但在给定一幅几乎相同的图像时,其条件复杂度可能很小,因为只需一个简短的程序就能描述两者的差异。作为条件提供的信息不计入程序长度。
几个基本恒等式体现了这一含义。例如,
如果将 和 编码为一个有序对,那么它们的联合复杂度 就描述了重建二者所需的信息量。前缀复杂度的一条尤其精确的链式法则是
提供整数 这一点很重要。去掉它通常需要对数级的修正,而不只是常数级的修正。等价的表述也可以使用按规范方式选定的、生成 的最短程序 。
在允许约定所带来的加性项差异的意义下,算法互信息通常表示为
它衡量的是将两个对象合在一起描述,而不是分别描述时所节省的描述长度。同一个不可压缩字符串的两个副本几乎共享全部信息:一个副本加上一条简短的复制指令,就能描述这一对对象。相比之下,两个独立选取的长随机字符串,除了长度等偶然共有的参数外,通常几乎没有互信息。
这是统计学中互信息在单个对象层面的对应概念,但它与基于概率分布求平均得到的量并不相同。它也不能确立因果关系。共享信息可能来自复制、共同来源、共同的生成规则,或所选用的编码方式。确定性的有效处理无法凭空产生任意大量的新共享算法信息:任何变化都必须由处理过程的描述及相关加性项来解释。
条件复杂度还引出了信息距离。两个方向的条件复杂度中的较大值,
衡量了将任一对象转换为另一个对象所需的信息量。用近似为 的量进行归一化,可以得到一种不依赖尺度、具有类似度量性质的相异度,但需允许较小的加性修正。这些构造为比较对象提供了一个理想框架,无须选定某一种针对特定应用的特征表示,尽管其不受限制的版本仍然不可计算。
归纳推断与最小描述长度
简短的描述不仅可以表示已有数据,也可以作为解释这些数据如何生成的假设。所罗门诺夫归纳通过考察在通用机上运行的程序,并按程序长度赋予权重,将这一思想形式化。程序获得的权重与 成正比,因此,更简单的有效解释会获得更大的先验权重。预测则综合了所有与已观测序列相符的程序的贡献。
由此得到的通用序列半测度,在相差一个乘法常数的意义下,支配每一个可计算的概率源。这种支配关系为收敛性结论提供了依据:当数据由可计算的概率测度生成时,基于通用半测度的预测会在适当的概率意义下趋近真实的预测概率。其中的常数取决于该概率源的描述复杂度。这些是关于理想预测器的数学结论,而不是构建可行的通用预测系统的操作指南。
这一思想与贝叶斯推断有着直接的概念联系。偏好简短有效描述的先验,将偏好简单解释的原则形式化了。然而,在有限尺度下,通用先验并不是唯一确定的:它们依赖于所选的参考机,尽管通用性将这种依赖限制为概率上的乘法因子和描述长度上的加法常数。此外,通用混合一般不可计算。它的意义在于为归纳提供一种极限理论,而不是提供一种能够精确求值的实用估计量。
一个相关但不同的框架是最小描述长度原则,由约尔马·里萨宁从1978年开始发展。在两部分表述中,通过最小化下式来选择模型 :
第一项计入指定模型所需的长度,第二项计入在该模型下编码数据所需的长度。更复杂的模型可能更好地拟合观测数据,但也需要更长的描述。因此,这一原则以明确的长度核算方式,解释了模型拟合程度与模型复杂度之间的权衡。现代形式不仅包括字面意义上的两部分程序描述,还包括通用编码和归一化最大似然等方法。
在机器学习中,这一视角有助于解释为什么仅有良好的模型拟合还不够。一个记住全部训练数据的模型,可能使这些观测数据的条件编码很短,但模型本身的描述却很长。然而,当数据生成方式发生任意变化时,较短的训练描述长度本身并不能保证泛化。相关结论取决于假设类、编码方案、采样假设以及对辅助信息的处理方式。柯尔莫哥洛夫复杂度为讨论这些问题提供了理想的语言;可计算的学习方法则必须采用受限模型或近似方法,而不能搜索所有可能的程序。
结构、随机性亏损与计算深度
单一的复杂度数值无法区分有意义的组织结构与偶然细节。随机字符串难以压缩,因此具有很高的柯尔莫哥洛夫复杂度,但它可能几乎不包含可复用的结构。高度有序的对象也可能需要很长的描述,尤其是在其结构十分庞大时。算法统计学通过探讨如何将单个对象表示为一个简单模型与一份典型残差的组合,来处理这一区别。
一种基本模型是包含观测字符串 的有限集合 。两段式描述首先指定 ,然后通过 在集合中的索引来确定它。描述长度近似为
这里, 是以固定的规范形式输出该有限集合并停机的程序的长度。单元素模型 解释了一切,却可能与 本身一样复杂。由所有长度为 的字符串组成的集合很简单,但除了长度之外,它几乎不能解释什么。
这种权衡可以用如下结构函数来刻画:
它考察的是:在模型描述最多使用 比特的预算下,能够将数据定位到多小的范围内。与之相关的随机性亏损则将索引长度 与 进行比较。如果在给定 的条件下, 的描述比典型成员所需的描述短得多,就说明模型仍有某种可检测的规律未能解释。采用模型最短描述的定义,可以进一步精确处理这些比较中的常数项。
这些思想引出了算法充分统计量和精致度,它们旨在衡量这样一种模型的复杂度:模型能够捕捉有效结构,却不必编码每一个偶然细节。显著性容限至关重要:改变所允许的总描述长度增量,可能会使选定模型的复杂度发生显著变化。不存在一种不受限制、可计算的通用程序,能够可靠地从每个对象中提取出唯一有意义的模式;而且,这一理论也不能脱离其形式化建模假设来界定“意义”。
查尔斯·贝内特在20世纪80年代提出的逻辑深度提供了另一种区分方式。在显著性水平 下,一种典型定义是
深度大的对象,从接近最短的描述生成出来时,需要经历漫长的计算。因此,一个字符串可以描述很短,却具有很大的深度,前提是展开这一描述需要大量计算。反过来,在适当的显著性水平下,典型的不可压缩字符串可以由一个近乎直接照录它的程序快速生成。复杂度衡量的是不可再缩减的描述长度;深度衡量的则是这样一种计算历程:除非使用明显更长的描述,否则就难以绕过它。
资源限制与基于压缩的实用方法
不受资源限制的柯尔莫哥洛夫复杂度不考虑程序运行需要多长时间。即使执行一个程序所需的时间长到实际无法接受,其描述依然可以很短。这使它与计算复杂性有所区别,后者研究资源需求如何随输入规模增长而变化。一个简短的程序可能需要枚举极其庞大的搜索空间才能产生输出,这便体现了两者的差异:描述简单并不意味着计算上易于实现。
限时复杂度引入了指定的执行时间预算。对于一个全可计算的界函数 ,可以定义
如果不存在符合条件的程序,则将其值视为无穷大。如果程序长度有一个可有效确定的有限搜索上界,就可以通过穷举检查程序能否在限定时间内完成执行。在标准计算机模型中,在固定步数内,只有有限量的输入能够影响计算,因此这类受限变体可以进行有效搜索。与不受资源限制的复杂度相比,其结果对所选计算机和模拟开销要敏感得多。
莱文的时间敏感复杂度采用了另一种折中方式,将长度与执行时间结合起来:
对运行时间施加对数惩罚,将简短描述与高效搜索和计算联系起来。其他变体则限制空间复杂度、电路规模或允许使用的描述语言。这些限制在密码学中十分重要:一个字符串可以由简短程序生成,但计算资源受限的检验仍可能无法将它与随机字符串区分开来。当种子较短时,伪随机数生成器的输出在不受资源限制的意义下可能具有较低的复杂度,但这并不意味着能够高效地区分或预测其输出。
实用的无损数据压缩给出的是复杂度的上界,而非精确值。如果一个固定的解压程序能从压缩表示 重建 ,那么,在采用适当的自定界约定时,有
其中的常数项计入了解码器所需的描述长度。压缩成功证明了简短描述的存在。某个压缩器未能压缩,并不能证明不存在更短的程序。压缩器可能无法发现算术规律、长程依赖或特定领域的结构,而对于较小的样本,文件格式头部可能占据主要篇幅。
一种应用性构造是归一化压缩距离,通常写作
其中, 表示压缩器输出的长度, 表示经过适当编码的拼接结果。它近似体现了归一化信息距离的思想,已用于文档、生物序列、音乐及其他数据的聚类。其表现取决于压缩器的窗口大小、对象边界、头部信息、顺序效应和预处理方式;有限的实际实现未必严格满足理想的度量性质。这些方法将特定压缩器检测共同结构的能力转化为可操作的度量,而不是让不可计算的通用信息量变得可以直接测量。