CAAI副秘书长于剑教授：机器学习——从公理到算法

1 机器学习公理化问题的提出

2015 年，华盛顿大学计算机系教授、机器学习大伽佩德罗•多明戈斯（Pedro Domingos）出版了一本畅销书，英文名称为“The Master Algorithm：How the Quest for the Ultimate Learning Machine Will Remake Our World”，中文译名为《终极算法》，其扉页引用了爱因斯坦的名言：“所有科学中最重大的目标就是，从最少量的假设和公理出发，用逻辑演绎推理的方法解释最大量的经验事实 "。令人惊讶的是，作者明明知道公理化非常重要，但在《终极算法》这本书中，却没有提出机器学习如何公理化这个问题。这令人困惑，原因何在？

它与聚类分析公理化研究遭遇的挫折有关。众所周知，聚类分析是典型的无监督学习问题，属于机器学习的子领域。聚类分析的公理化问题，早在1971年就提出了 [1]。研究了 31 年之后，2002年，康奈尔大学教授、美国三院院士 Kleinberg 在 NIPS 上发表了一篇著名的论文“An impossibility theorem for clustering”[2]。这篇文章模仿阿罗不可能性定理的思路，提出了一个似乎很合理的聚类公理框架，却出人意料地证明了没有任何聚类算法满足该公理框架。这个惊人结果对聚类公理化的研究可行性提出了严重质疑。有不少后来研究试图修正 Kleinberg 的结论，但整体来看并没有成功，有关的文章请参考文献 [3-4]。

由于聚类公理化的可行性存在问题，作为聚类分析公理化的上位问题，机器学习公理化问题的可行性自然也成了无根之木，似乎成了一个不可解的死问题。因此，机器学习公理化问题就很难以本来面目出现。但是，这个问题极其重要且本质，绕不开，在文献中必然会以其他面目出现。就作者所知，早在 2004 年，南京大学周志华教授在国家自然科学基金委作了一个报告《普适机器学习》，其中就明确指出：机器学习“以 Tom Mitchell 的经典教科书为例，很难看到基础学科（例如数学、物理学）教科书中那种贯穿始终的体系，也许会让人感到这不过是不同方法和技术的堆砌”。就是以否定的方式提出了如下问题：机器学习是否存在一个像数学、物理那种贯穿始终的体系。唯一遗憾的是，这个报告没有以文章的形式正式出版。整整过了 11 年之后，先是 2015 年 1 月，佩德罗 • 多明戈斯（Pedro Domingos）在《终极算法》提出了终极算法的思想，指出：“终极算法与机器学习的关系就像标准模型和粒子物理学或中心法则与分子生物学的关系：该统一原理能理解人类当今知道的一切，并为未来数十年或者数百年的进步奠定基础”；接着在 2015 年 7月，Jordan 和 Mitchell 在 Science 上发表了一篇文章 [5]，指出机器学习有两个核心问题，其中一个是能否找到一个统管所有学习系统（包括人、机器和组织）的学习法则。这些论述几乎看不出机器学习公理化问题的任何底色了。但如果将终极算法看作机器学习公理，如果机器学习能公理化，则上面论述的问题都可以解决。

2 机器学习公理化的可行路径

机器学习公理化问题真的不可行吗？这需要仔细界定什么是公理。公理是共同的预设。机器学习中真的有共同预设吗？从机器学习问题框架考虑，由数据表示、学习判据、学习算法和性能评估四个部分组成。聚类分析公理化曾经沿着三个方向（判据、算法、性能评估）进行研究，结果都不理想。不同学习算法，这四个部分差别极大；找到共性，挑战极大。从算法角度入手Kleinberg 直接否定了聚类算法公理化的可能 [2]。

这给了另一种启示。机器学习的预设是在算法自身吗？如果不是算法自身，又是什么？经过多年研究，作者注意到，不管什么学习算法，其学习目的是相同的，即学到知识。从这个意义上，机器学习确实有共性。但知识有共性吗？如果知识没有共性，则这个发现意义不大。令人惊奇的是，知识还真有共性。笔者发现了知识的一个重要共性——知识的基本单位是概念，而知识自身也是概念。由此，可以知道学习知识，就是学习概念。那什么是学习概念？

众所周知，学习概念就是会使用概念。使用概念，又叫做归类。人活着，无时无刻不在归类。早上起床，已经是个复杂的归类问题，其至少包含两个子概念的复合概念：早上，起床。去吃早餐，又是一个将食物归类的过程。北京人的早餐——豆腐脑、豆浆、油条、包子、馒头、面条、小米粥、大米粥、玉米粥……总要选几样。每一样都是一个概念。选的过程，即是归类。不会归类，归类错误，在人类社会，连早餐都吃不了，说寸步难行，已经是最轻的后果。

举个更夸张的例子。前几天，我去一个酒店，一下撞在了玻璃门上。当时，真没有发现玻璃，以为是敞开的门。还好，力度不是太大。显然，这也是一个归类问题。为什么会发生这样的归类错误？有趣的是，搞清楚这个问题，就可以弄明白机器学习公理化问题。

3 归类假设与机器学习公理

前面的分析已经说明，学习知识就是归类，因此，机器学习就是归类。不同的学习问题，就是不同的归类问题。归类问题的复杂度并不相同，有的可能简单一些，有的可能极复杂。但是归类的道理一样。

现在就来看一下，我为什么会撞玻璃门？要回答这个问题，需要注意到学习算法都有输入、输出。撞门这件事的输入、输出是什么？类比于学习算法的输入、输出，玻璃门始终在那儿，是输入；以为玻璃门是空的，是输出。更仔细地分析一下，从输入来看，酒店方是输入者，肯定知道玻璃门那儿是门；就玻璃门的位置来说，酒店方可能都找不到比玻璃门更像门，否则早就更换别的门了。因此，对作为输入方的酒店来说，其归类的依据是，一个对象应该最像其归于的类。

那我什么会撞玻璃门？因为玻璃太透明了，对作为输出方的我来说，最像空的。因为最像空的，输出方的我就真以为是空的，毫不犹豫地把玻璃门当作空气一样走过去。故对输出方的我来说，其归类的依据是，一个对象应该归于其最像的类。

如果用更符合中国语言来说，上面的归类准则可以浓缩为一句话：“归哪类，像哪类像哪类，归哪类。”这是不是机器学习的基本假设？可以肯定地说，应该是的。不然，归哪类，不像哪类；像哪类，不归哪类。在这样的假设下，机器学习就学不到正确的归类结果。

这两句话虽然简单，但依然是自然语言，不是数学语言，其精确性不足，必须借助数学符号将其准确定义。将这两句话用数学语言表示出来，就可以得到机器学习公理。怎么用数学符号表示这两句话？经过分析知道，只要将类表示清楚即可。用数学符号将类精确表示之后，根据类的数学表示和上面这两句话，可以归纳成 5 条公理，即类表示存在公理、类表示唯一公理、样本可分性公理、类可分性公理和归类等价公理；4 条归类准则。有兴趣的读者可以参考文献 [6]，在此不赘述。

4 机器学习公理的部分应用

机器学习公理化至少有三个用处。

第一个用途是基于机器学习公理推演学习算法。在文献 [6] 中，已经推演了单类和多类学习算法。单类算法包括密度估计和回归，单类数据降维包括主成分分析、非负矩阵分解、字典学习、流形学习和典型关联分析等；多类包括聚类和分类等。

第二个用途是其可以推导出常见的机器学习理论 [6]。比如，Valiant 发明的概率可能正确学习理论（PAC 学习理论），Vapnik 提出的统计学习理论。同时，这里也顺便回答了文献中已经提出 46 年的聚类公理化问题。

最后一个用途是基于机器学习公理分析算法性能。由类可分性公理可以推出，不同的类其表示也不同。但是对有些软聚类算法输出的聚类结果中，不同的类却可能表示相同。这显然是不可接受的，也不符合机器学习公理。因此，算法需要尽量避免这些结果被稳定的输出。按照这个思路，可以给出一个理论选择算法参数的框架，即凡是使不同的类表示相同的聚类结果稳定输出的算法参数必须避免被选择。在这个方向上，请参考文献 [7-9]。

5 展望

2017 年 7 月，笔者在清华大学出版社出版的《机器学习：从公理到算法》一书中，首次提出了机器学习公理化问题，并给出了机器学习公理化框架，推演出了一些典型的单类、多类学习算法。

目前，该公理化框架还存在一些问题。比如强化学习、集成学习、弱监督学习和排序学习等这些任务，还没有根据公理化框架推演的算法；即使已经根据公理化框架推演的学习任务，也只推演了部分学习算法。因此，希望感兴趣的学术同仁共同推进这方面的工作，将机器学习公理化框架进一步完善。

本工作部分得到国家自然基金重点项目（61632004）的支持。

致谢：

高新波、 张文生、 胡包钢、 张讲社、封举富、马少平、何清、胡学钢、谢娟英、余志文、王磊、杨健、高阳、杨明、叶茂、苗夺谦、尹义龙、杨博、陈小平、马尽文、陈迎庆、白璐、李凡长、文益民、赵兴明、高敬阳、李进、杨敏生、温晗秋子、李肯立、胡清华、贾彩燕、周雪忠、黄厚宽，以及中国人工智能学会机器学习专委会各位常委、北京交通大学机器学习与认知计算研究所的师生。

特别感谢：

徐宗本院士、陆汝钤院士的帮助和支持！