柯氏复杂性和生物信息学先驱｜CCCF精选（Blast Mining）

关键词：柯氏复杂性理论　计算生物学

编者按：李明，2021年CCF海外杰出贡献奖获得者，ACM/IEEE Fellow，滑铁卢大学计算机科学系讲座教授，加拿大皇家科学院院士，加拿大最高科学奖“基廉奖”（Killam Prize）获奖者。他在计算机理论、生物信息学和机器学习领域都作出了开创性贡献，是公认的柯氏复杂性理论(Kolmogorov Complexity)的先驱研究者和世界级权威。他带领团队开创了柯氏复杂性与计算机科学相结合的交叉领域；发展了不可压缩方法进行算法平均时间分析的方法，解决了诸多世界难题；从物理定律出发得到了两个信息载体之间的信息距离，第一次从根本上定义了信息之间的最佳距离；他还解决了计算生物学中两个最著名的理论问题：最短超串的近似算法分析和间隔种子序列(spaced seed)理论，将计算机科学在生命信息工程方面的应用向前推进了一大步。

近日，李明教授接受了CCCF的专访，畅谈了他在柯氏复杂性和生物信息学等领域的工作。

问：您在柯氏复杂性方面做了很多非常有影响力的工作，可以跟我们简单谈谈香农信息论(Shannon Information Theory)与柯氏复杂性的关系吗？

李明：柯氏复杂性是一个近代信息论，用来描述一个对象里的信息量。一个对象里的信息量是指描述这个对象所需的最短的程序。这个理论对计算机科学、物理、生物、哲学等领域都有很多影响。例如，分析下界、算法平均复杂度等都必须用这个理论。香农信息论是对象集合的描述。

问：您是从什么时候开始对柯氏复杂性感兴趣的？您是怎么接触到这些领域的？

李明：20世纪80年代，我在读研究生期间，刚开始研究理论计算机科学。我的导师尤里斯·哈特马尼斯(Juris Hartmanis)获得过ACM图灵奖。有一次，他在黑板上花了5分钟给我讲了柯氏复杂性。他说，这是个新领域，我可以研究这个。我当时正好在研究一个图灵机的下界，要回答“图灵机模拟多个图灵机，时间复杂度要增加多少”的问题。一个图灵机如果模拟两个图灵机，一个平方级的模拟，那它的下界是什么，能否改进？我用柯氏复杂性证明了一个平方级的紧致下界。我花了几个星期完成了这个证明。

我们也用柯氏复杂性分析了希尔排序(shell sort)：第一轮步长h1，每h1选一个，做冒泡排序(bubble sort)，如果做完一轮还没排好序，就做第二轮，选步长h2，做冒泡排序。这个算法非常复杂，其平均复杂性的下界当时没人知道，我用柯氏复杂性解决了这个问题。

利用柯氏复杂性可以解决很多计算平均复杂度的问题。计算平均复杂度很不容易实现，因为要对所有的输入取平均。柯氏复杂性有一个好处是，不需要考虑所有的输入，可以定义某个输入是随机的，也就是一个代表性输入。针对这个输入去分析算法，如果这个输入足够有代表性，分析的结果就是平均复杂度。有代表性的输入怎么找呢？柯氏复杂性可以做出来。

问：您在柯氏复杂性方面做了很多开创性的工作，能否简单介绍一下您认为最重要或者最有意义的研究成果？

李明：我最喜欢的工作是对信息距离(information distance)的研究。柯氏复杂性描述的是一个对象有多少信息，如果要度量两个对象之间差了多少信息，就需要一个统一的度量。

我们把柯氏复杂性从一个对象推广到两个对象。类似地，我们把一个序列有多少信息，推广到多个序列之间有多少信息。这个研究很困难，相关成果最终发表在信息论顶刊IEEE Transactions on Information Theory上，合作者包括查尔斯·本内特(Charles Bennett)、彼特·高奇(Peter Gacs)、保罗·威塔涅(Paul Vitanyi)和祖雷克(W. Zurek)。

这个距离有什么用呢？谈一个最近大火的大语言模型ChatGPT，它的训练使用了非常多的数据。而人类学习通常不需要这么多数据，人类可以做单样本学习(one-shot learning)：假如你从来没见过老虎，我给你一张老虎的图片，告诉你这是一只老虎，你下次再见到其他老虎就会知道那是只老虎。单样本学习的关键是对比两只老虎，看这两只老虎的相似度，也就是信息距离。人类做这个任务的时候，是在推理阶段做压缩，而不是在训练阶段，这和ChatGPT互补。

问：您认为柯氏复杂性对计算机科学有哪些启示和影响？

李明：柯氏复杂性给计算机科学带来了很多启示，方法论可能是最重要的启示之一。柯氏复杂性作为方法论，可以指导我们如何证明定理，以及如何分析算法。有些工作是我们做的，有些是别人做的。该方法论解决了很多未解的问题。

举个例子，姚期智先生曾经研究过一个问题，如果有限自动机有K个头，K 1个头会不会比K个好。他证明了：有限自动机K 1个头比K个头好。有限自动机如果增强成了下推自动机(PDA)，那么K 1个头是不是也比K个好？我们证明了这个问题，发展了不可压缩方法进行算法分析。

这个方法真的非常强大，但也比较简单。再举个例子：洛瓦兹局部引理(Lovász Local Lemma)描述的是一个事情发生的概率即便很小也一定会出现。这个理论特别难证明，兰斯·福特诺(Lance Fortnow)用柯氏复杂性解决了这个问题，而且用的方法特别简单。柯氏复杂性可以简化很多证明。

李明获得加拿大“基廉奖”

问：您的研究成果对其他领域，比如生物信息学、机器学习等也产生了很大价值，可以简单跟我们分享一下吗？

李明：我分享一下我们在机器学习方面的工作：k-样本学习(k-shot learning)的理论。以前有上千篇论文用k-样本学习做分类，非常简单，无需参数，只须做压缩。2004年，有3位加州大学河滨分校的教授用我们的算法做分析，找了当时数据挖掘中最有名的51个算法与我们的方法作对比，都被我们比下去了。他们用我们的方法提出了无参数数据挖掘(parameter free data mining)方法。

这是信息距离的一个应用。我们对信息距离做了重新表达后，它就变成了单样本学习。最近，我实现了一个严格的理论，把学习分成两类，深度学习和人类学习。在有数据的情况下，可以做深度学习，例如GPT；在没有数据的情况下，必须做压缩，没有别的选择。

问：您解决了计算生物学中两个最著名的理论问题：最短超串的近似算法分析和间隔种子序列理论，请您介绍一下这两个问题。您是如何将计算机科学与生物学相结合，创造出新颖而有效的方法来解决它们的？有什么实际意义？

李明：第一个是关于基因组组装(genome assembly)的问题。那个时候大家在做鸟枪法测序(shotgun sequencing)，一个基因组有30亿碱基对(basepair)，碱基要分成很多小段，然后再组装起来。组装的时候，需要找到一个最短的超串，使这些小段都是它的子串。生物界用了所谓的贪心算法：找两个子串，如果重叠最大就合并在一起，一直合并直到只剩下一个子串。这个算法到底好不好，长期以来一直是一个开放的问题。姜涛、约翰·特伦普(John Tromp)和我一起解决了这个问题。后来布鲁姆(Blum)和扬纳卡基斯(Yannakakis)独立解决了这个问题，我们一起把研究成果发表在了1991年ACM计算理论年会(STOC’91)上。

间隔种子序列是我和马斌、特伦普一起做的。假设有一个序列，在基因组数据库里做搜索，要找到近似匹配的序列。直接的方法是过一遍数据库，与每个序列作比较，但这个方法太慢了。另一个办法是用哈希算法，比如把11个碱基对的种子哈希映射到数据库里，有匹配的就做扩展，没有匹配的则忽略，然后再从局部看看结果，但这个方法仍然不够快。如果想更快一点，就把11变成12，但还是有问题，因为生物计算允许近似匹配，12个中错过一个也不行。于是我们开发了最优间隔种子序列，这个方法既敏感又快速，被美国国家生物技术信息中心(NCBI)下的BLAST(Basic Local Alignment Search Tool，生物信息学中的一种序列比对工具)采用，如今每天都在服务数以万计的用户。

如果你可以正确回答下面这个问题，就可以理解间隔种子序列的深奥之处：考虑一个长度为100的英文字母随机序列。每个位置的字母出现的概率都是1/26。在这个序列中，AAA连续出现的概率高还是ABC出现的概率高？

问：深度学习对您这样富有经验的成功学者，有什么影响吗？

李明：现在大家做深度学习都是从零开始，深度学习的潮流对我们这些人不是很友好，因为都需要从头学习。但是可以因势利导从另外一个角度融合改进以前的工作。比如，我们用深度学*改进了蛋白质测序方法。我们把信息距离也融入到k-样本学习中，和深度学习互补。深度学习（如GPT）反过来帮助我们把压缩性能提升了三倍，也帮助了很多其他领域的应用。

问：您在2000年创立了生物公司，又在2013年创立了人工智能公司。能向我们介绍一下您的公司，并分享创立公司的想法吗？

李明：我谈谈生物公司吧。我们主要用人工智能解决生物制药相关的问题。比如治疗癌症，当癌细胞变异后，它的细胞表面会产生一些新抗原，我们要想办法拿到新生抗原，做从头测序(de novo sequencing)，用深度学习进行新生抗原测序(neoantigen sequencing)，鉴定其是否有免疫原性。我们提供的这种服务非常重要，因为个性化的免疫治疗就是要找到新生抗原，找到新生抗原就可以治病了。

另外，我认为做生物方面的研究，最终一定要成立公司，否则合作成本太大。成立公司可以看到市场最前沿的问题，进而解决问题，否则做的研究可能没有实际应用。我们现在做的研究都是直接面向应用的。做生物技术，需要与实际相结合，最好的办法就是商业化，一定要结合市场去做。同时基础研究也很重要。

问：您认为做公司就是要解决实际且有挑战的问题？

李明：是的，我举个例子。我们公司在做新生抗原测序，遇到各种各样的挑战。我们做这个的缘由是2017年《自然·生物技术》(Nature Biotechnology)上的一篇文章说这是个开放问题，有巨大挑战。当时我们已经是全球最领先的蛋白质测序公司了，自然就想到我们有义务解决这个问题。

问：您多年来培养了很多优秀的青年人才，您对教育工作有什么心得或体会？您认为年轻人应该怎样选择感兴趣又适合自己的发展方向？

李明：最重要的是给学生发挥的空间。有两种导师，一种是不管学生的，好学生就容易自我发挥。另一种是什么都管的，按部就班的学生会比较适应。不同风格的导师对不同类型的学生有不同的好处。

问：您怎么看中国计算机科学的发展？

李明：中国的计算机事业有希望走出自己的路，未来做出我们自己的成果。有些人说中国的计算机事业总是跟在美国后面跑。其实这是有历史原因的，比如人才断档。计算机科学的发展，需要一代代人的努力，我们迟早会有属于自己的开创性的成果，只是时间问题。

中国计算机科学其实已经取得了巨大进步，人们总觉得国内还没有人获得图灵奖（除了姚期智之外），认为我们缺少从0到1的工作。其实不然，我举几个例子，山东大学教授王小云（兼任清华大学讲座教授）成功破译美国号称最安全的密码；高文团队做的视频压缩系统，华为的鸿蒙系统，杨强的联邦学习，乃至李国杰、孙凝晖、包云岗等一代代人做的计算机系统设计都是计算机理论或工程上的巨大成就。

海外华人，包括在外企工作的研究人员也取得了令人激动的成就，比如，李凯、李飞飞等人做的ImageNet 推动了人工智能整个领域从0到1的发展；深度学习的开始还有另外一个重要的开创性工作，那就是邓力把辛顿(Hinton)请到微软，他们用深度学习突破了语音识别技术；许锦波的蛋白质折叠深度学习系统是AlphaFold的原型，他做了30%~60%的工作，AlphaFold基本沿用同样方法改进到90%；沈向洋的全光采样；何凯明团队在郭百宁和沈向洋的领导下做出的ResNet是如今ChatGPT的基础，因为ChatGPT赖以工作的Transformer用了ResNet方法才得以达到现在的深度，使大语言模型可以成功。

我相信中国计算机科学在10年之内可以跻身世界一流。