机器学习算法发展历程详解

在科学技术刚刚萌芽的时候，科学家Blaise Pascal和Von Leibniz就想到了有朝一日能够实现人工智能。即让机器拥有像人一样的智能。

机器学习是AI中一条重要的发展线，在工业界和学术界都异常火爆。企业、大学都在投入大量的资源来做机器学习方面的研究。最近，机器学习在很多任务上都有了重大的进步，达到或者超越了人类的水平（例如，交通标志的识别[1]，ML达到了98.98%，已超越了人类）。图1中展示了ML的一个粗略的时间线，标记了很多里程碑。熟悉该图，阅读下文会觉得顺畅很多。

图 1 机器学习时间线

推动机器学习流行化的第一个舵手是Hebb，1949年他提出了神经心理学学习范式——Hebbian学习理论。经过简单的扩展，该理论就开始研究递归神经网络的节点之间的相关度，它记录下网络上的共性然后像记忆一样工作，正式的表达是这样：

假设反射活动的持久性或重复性可以诱导细胞发生变化，以适应这种活动…当神经元细胞A距离神经元细胞B足够近时，它就可以持续重复的激活B，那么这两个细胞之一或者全部就会发生一些代谢过程或生长变化来提高效率[1]。

1952年，IBM的Arthur Samuel写出了西洋棋程序，该程序可以通过棋盘状态学习一个隐式的模型来为下一步给出较好的走法。Samuel和程序对战多局后，觉得这个程序经过一定时间的学习后可以达到很高的水平。

用这个程序，Samual驳倒了机器不能像人类那样可以学习显式代码之上的模式。他定义并解释了一个新词——机器学习。

机器学习是给计算机一种不用显式编程就能获得能力的领域。

1957年，Rosenblatt的感知器算法是第二个有着神经系统科学背景的机器学习模型，它与今天的ML模型已经很像了。在当时，感知器的出现引起了不小的轰动，因为它比Hebbian的想法更容易实现。Rosenblatt用下面的话向大家阐释感知器算法：

感知器算法的作用是，在不用深入理解只对一些特定生物有机体有效的未知条件的前提下，说明了通用智能系统一些基础特点[2]。

3年之后，Widrow [4] 因发明Delta学习规则而载入ML史册，该规则马上就很好的应用到了感知器的训练中，对，没错，就是现在常见的最小二乘问题。感知器和Delta学习规则的联姻着实构造了一个极好的线性分类器。但是，根据后浪拍死前浪的历史规律，感知器的热度在1969被Minskey[3]一盆冷水泼灭了。他提出了著名的XOR问题，论证了感知器在类似XOR问题的线性不可分数据的无力。对神经网络（NN）社区来说，形成了几乎当时看来几乎不可逾越的鸿沟，史称“明斯基之印”。然而无论如何，在10年的19世纪80年代，NN学者们还是打破了这个紧箍咒。

图 2 XOR问题-线性不可分数据示例

被封印后，ML的发展几乎停滞，尽管BP的思想在70年代就被Linnainmaa [5] 以“自动微分的翻转模式”被提出来，但直到1981年才被Werbos [6]应用到多层感知器(MLP)中，直到现在仍是神经网络架构的关键组成部分。多层感知器和BP算法的出现，促成了第二次神经网络大发展，1985-1986年NN研究者们成功的实现了实用的BP算法来训练MLP。（Rumelhart, Hinton, Williams [7]- Hetch, Nielsen[8]）

图 3 来自Hetch和Nielsen

花开并蒂，各表一枝。另一个同样很著名的ML算法在1986年被J. R. Quinlan[9]提出，即决策树算法，具体来说是ID3算法。这是机器学习的另一条主流中一个灯塔式的成就。ID3以其简单的规则和明确的推理，解决了很多现实世界的问题，实际上，它就是以一个实用软件的姿态出现的，相对于黑箱子般的NN算法。

ID3之后，很多其他的算法或改进如雨后春笋般的出现，例如ID4，回归树，CART等等)。直到现在，决策树仍然是ML界中的热点。

图 4 一个简单的决策树

接下来就是ML领域最重要的一个突破——支持向量机（SVM）。SVM由大师Vapnik and Cortes[10] 在1995年提出，它有很强的理论论证和实证结果。自此之后，ML社区就楚河汉界划分为NN和SVM两派。2000年左右，随着核方法的提出，SVM大占上风，在很多领域上都超过了NN模型。除此之外，SVM还发展了一系列的针对NN模型的基础理论，包括凸优化、泛化间隔理论和核方法。可以说，在这个时段，SVM的发展无论是理论还是实践都占尽天时地利，因而发展速度极快。

图 5 From Vapnik and Cortes [10]