5 机器学习之发展历程

所谓“知识就是力量”​。

1965年，Feigenbaum主持研制了世界上第一个专家系统DENDRAL。

机器学习是人工智能(artificial intelligence)研究发展到一定阶段的必然产物。二十世纪五十年代到七十年代初，人工智能研究处于“推理期”​，那时人们以为只要能赋予机器逻辑推理能力，机器就能具有智能。这一阶段的代表性工作主要有A.Newell和H.Simon的“逻辑理论家”(Logic Theorist)程序以及此后的“通用问题求解”(GeneralProblem Solving)程序等，这些工作在当时取得了令人振奋的结果。例如，​“逻辑理论家”程序在1952年证明了著名数学家罗素和怀特海的名著《数学原理》中的38条定理，在1963年证明了全部52条定理，特别值得一提的是，定理2.85甚至比罗素和怀特海证明得更巧妙。A.Newell和H.Simon因为这方面的工作获得了1975年图灵奖。然而，随着研究向前发展，人们逐渐认识到，仅具有逻辑推理能力是远远实现不了人工智能的。E.A.Feigenbaum等人认为，要使机器具有智能，就必须设法使机器拥有知识。在他们的倡导下，从二十世纪七十年代中期开始，人工智能研究进入了“知识期”​。在这一时期，大量专家系统问世，在很多应用领域取得了大量成果。E.A.Feigenbaum作为“知识工程”之父在1994年获得图灵奖。但是，人们逐渐认识到，专家系统面临“知识工程瓶颈”​，简单地说，就是由人来把知识总结出来再教给 计算机是相当困难的。于是，一些学者想到，如果机器自己能够学习知识该多好！
参见（休息一会儿——小故事：​“机器学习”名字的由来）​。

事实上，图灵在1950年关于图灵测试的文章中，就曾提到了机器学习的可能；二十世纪五十年代初已有机器学习的相关研究，例如A.Samuel著名的跳棋程序。五十年代中后期，基于神经网络的“连接主义”(connectionism)学习开始出现，代表性工作有F.Rosenblatt的感知机(Perceptron)、B.Widrow的Adaline等。在六七十年代，基于逻辑表示的“符号主义”(symbolism)学习技术蓬勃发展，代表性工作有P.Winston的“结构学习系统”​、R.S.Michalski等人的“基于逻辑的归纳学习系统”​、E.B.Hunt等人的“概念学习系统”等；以决策理论为基础的学习技术以及强化学习技术等也得到发展，代表性工作有N.J.Nilson的“学习机器”等；二十多年后红极一时的统计学习理论的一些奠基性结果也是在这个时期取得的。

IWML后来发展为国际机器学习会议ICML。
1980年夏，在美国卡耐基梅隆大学举行了第一届机器学习研讨会(IWML)；同年，​《策略分析与信息系统》连出三期机器学习专辑；1983年，Tioga出版社出版了R.S.Michalski、J.G.Carbonell和T.Mitchell主编的《机器学习：一种人工智能途径》​[Michalski et al.,1983]​，对当时的机器学习研究工作进行了总结；1986年，第一本机器学习专业期刊Machine Learning创刊；1989年，人工智能领域的权威期刊Artificial Intelligence出版机器学习专辑，刊发了当时一些比较活跃的研究工作，其内容后来出现在J.G.Carbonell主编、MIT出版社1990年的《机器学习：范型与方法》​[Carbonell,1990]一书中。总的来看，二十世纪八十年代是机器学习成为一个独立的学科领域、各种机器学习技术百花初绽的时期。

R.S.Michalski等人[Michalskietal.,1983]把机器学习研究划分为“从样例中学习”​“在问题求解和规划中学习”​“通过观察和发现学习”​“从指令中学习”等种类；E.A.Feigenbaum等人在著名的《人工智能手册》​（第三卷）​[Cohen andFeigenbaum,1983]中，则把机器学习划分为“机械学习”​“示教学习”​“类比学习”和“归纳学习”​。机械学习亦称“死记硬背式学习”​，即把外界输入的信息全部记录下来，在需要时原封不动地取出来使用，这实际上没有进行真正的学习，仅是在进行信息存储与检索；示教学习和类比学习类似于R.S.Michalski等人所说的“从指令中学习”和“通过观察和发现学习”​；归纳学习相当于“从样例中学习”​，即从训练样例中归纳出学习结果。二十世纪八十年代以来，被研究最多、应用最广的是“从样例中学习”​（也就是广义的归纳学习）​，它涵盖了监督学习、无监督学习等，本书大部分内容均属此范畴。下面我们对这方面主流技术的演进做一个简单回顾。

参见（第4章 决策树）​。
这时实际是ILP的前身。
参见（第15章 规则学习）​。

在二十世纪八十年代，​“从样例中学习”的一大主流是符号主义学习，其代表包括决策树(decisiontree)和基于逻辑的学习。典型的决策树学习以信息论为基础，以信息熵的最小化为目标，直接模拟了人类对概念进行判定的树形流程。基于逻辑的学习的著名代表是归纳逻辑程序设计（Inductive Logic Programming，简称ILP）​，可看作机器学习与逻辑程序设计的交叉，它使用一阶逻辑（即谓词逻辑）来进行知识表示，通过修改和扩充逻辑表达式（例如Prolog表达式）来完成对数据的归纳。符号主义学习占据主流地位与整个人工智能领域的发展历程是分不开的。前面说过，人工智能在二十世纪五十到八十年代经历了“推理期”和“知识期”​，在“推理期”人们基于符号知识表示、通过演绎推理技术取得了很大成就，而在“知识期”人们基于符号知识表示、通过获取和利用领域知识来建立专家系统取得了大量成果，因此，在“学习期”的开始，符号知识表示很自然地受到青睐。事实上，机器学习在二十世纪八十年代正是被视为“解决知识工程瓶颈问题的关键”而走上人工智能主舞台的。决策树学习技术由于简单易用，到今天仍是最常用的机器学习技术之一。ILP具有很强的知识表示能力，可以较容易地表达出复杂数据关系，而且领域知识通常可方便地通过逻辑表达式进行描述，因此，ILP不仅可利用领域知识辅助学习，还可通过学习对领域知识进行精化和增强；然而，成也萧何、败也萧何，由于表示能力太强，直接导致学习过程面临的假设空间太大、复杂度极高，因此，问题规模稍大就难以有效进行学习，九十年代中期后这方面的研究相对陷入低潮。

参见（第5章 神经网络

二十世纪九十年代中期之前，​“从样例中学习”的另一主流技术是基于神经网络的连接主义学习。连接主义学习在二十世纪五十年代取得了大发展，但因为早期的很多人工智能研究者对符号表示有特别偏爱，例如图灵奖得主H.Simon曾断言人工智能是研究“对智能行为的符号化建模”​，所以当时连接主义的研究未被纳入主流人工智能研究范畴。尤其是连接主义自身也遇到了很大的障碍，正如图灵奖得主M.Minsky和S.Papert在1969年指出，​（当时的）神经网络只能处理线性分类，甚至对“异或”这么简单的问题都处理不了。1983年，J.J.Hopfield利用神经网络求解“流动推销员问题”这个著名的NP难题取得重大进展，使得连接主义重新受到人们关注。1986年，D.E.Rumelhart等人重新发明了著名的BP算法，产生了深远影响。与符号主义学习能产生明确的概念表示不同，连接主义学习产生的是“黑箱”模型，因此从知识获取的角度来看，连接主义学习技术有明显弱点；然而，由于有BP这样有效的算法，使得它可以在很多现实问题上发挥作用。事实上，BP一直是被应用得最广泛的机器学习算法之一。连接主义学习的最大局限是其“试错性”​；简单地说，其学习过程涉及大量参数，而参数的设置缺乏理论指导，主要靠手工“调参”​；夸张一点说，参数调节上失之毫厘，学习结果可能谬以千里。

参见（第6章 支持向量机）​。

参见习题（6.5 支持向量回归）​。

二十世纪九十年代中期，​“统计学习”(statistical learning)闪亮登场并迅速占据主流舞台，代表性技术是支持向量机（Support Vector Machine，简称SVM）以及更一般的“核方法”(kernel methods)。这方面的研究早在二十世纪六七十年代就已开始，统计学习理论[Vapnik,1998]在那个时期也已打下了基础，例如V.N.Vapnik在1963年提出了“支持向量”概念，他和A.J.Chervonenkis在1968年提出VC维，在1974年提出了结构风险最小化原则等。但直到九十年代中期统计学习才开始成为机器学习的主流，一方面是由于有效的支持向量机算法在九十年代初才被提出，其优越性能到九十年代中期在文本分类应用中才得以显现；另一方面，正是在连接主义学习技术的局限性凸显之后，人们才把目光转向了以统计学习理论为直接支撑的统计学习技术。事实上，统计学习与连接主义学习有密切的联系。在支持向量机被普遍接受后，核技巧(kernel trick)被人们用到了机器学习的几乎每一个角落，核方法也逐渐成为机器学习的基本内容之一。

参见（5.6 深度学习）​。

“过拟合”参见（第2章 模型评估与选择）

有趣的是，二十一世纪初，连接主义学习又卷土重来，掀起了以“深度学习”为名的热潮。所谓深度学习，狭义地说就是“很多层”的神经网络。在若干测试和竞赛上，尤其是涉及语音、图像等复杂对象的应用中，深度学习技术取得了优越性能。以往机器学习技术在应用中要取得好性能，对使用者的要求较高；而深度学习技术涉及的模型复杂度非常高，以至于只要下工夫“调参”​，把参数调节好，性能往往就好。

因此，深度学习虽缺乏严格的理论基础，但它显著降低了机器学习应用者的门槛，为机器学习技术走向工程实践带来了便利。那么，它为什么此时才热起来呢？有两个基本原因：数据大了、计算能力强了。深度学习模型拥有大量参数，若数据样本少，则很容易“过拟合”​；如此复杂的模型、如此大的数据样本，若缺乏强力计算设备，根本无法求解。恰由于人类进入了“大数据时代”​，数据储量与计算设备都有了大发展，才使得连接主义学习技术焕发又一春。有趣的是，神经网络在二十世纪八十年代中期走红，与当时Intel x86系列微处理器与内存条技术的广泛应用所造成的计算能力、数据访存效率比七十年代有显著提高不无关联。深度学习此时的状况，与彼时的神经网络何其相似。

需说明的是，机器学习现在已经发展成为一个相当大的学科领域，本节仅是管中窥豹，很多重要技术都没有谈及，耐心的读者在读完本书后会有更全面的了解。