ML简史_ml软件发行时间

原文地址：http://www.52ml.net/15427.html

图 1 机器学习时间线

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

机器学习是AI中一条重要的发展线，在工业界和学术界都异常火爆。企业、大学都在投入大量的资源来做机器学习方面的研究。最近，机器学习在很多任务上都有了重大的进步，达到或者超越了人类的水平（例如，交通标志的识别[1]，ML达到了98.98%，已超越了人类）。

图1中展示了ML的一个粗略的时间线，标记了很多里程碑。熟悉该图，阅读下文会觉得顺畅很多。

推动机器学习流行化的第一个舵手是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]

不仅在外部遭到了巨大的挑战，NN内部也发生了问题。1991年的Hochreiter[40]和2001年的Hochreiter[11]的工作，都表明在使用BP算法时，NN单元饱和之后会发生梯度损失。简单来说，训练NN模型时，超过一定的迭代次数后，再迭代NN模型就很容易过拟合。

再往前一点点，另一个坚实的ML模型AdaBoost在1997被Freund和Schapire提出，该算法最大的特点在于组合弱分类器形成强分类器。这个成果为它的作者赢得了Godel奖。Adaboost通过给那些难的样例更高的权重来对那些容易训练的分类器进行训练。该模型在脸部识别和检测方面应用的很广。它还是PAC（概率近似正确理论）的一种实现。通常来说，所谓的弱分类器都被Adaboost用来当树桩——即单个的决策树节点。他们这样来描述Adaboost：

作为一个良好的在线预测模型的抽象扩展，Adaboost可以被解释为一个通用的决策理论设置…[11]

另外一个可以将多个决策树组合起来的模型在2001年被Breiman[12]提出。该模型被称为随机森林(RF)，因为它的每个组成节点都是随机的选择一组示例和一组特征。RF也拥有理论上和实验上的抗过拟合的证据。甚至有些数据Adaboost都不能很好的克服过拟合和离群点的时候，RF都能有很好的鲁棒性。RF在很多其他不同领域比如Kaggle比赛上都有很成功的表现。

随机森林是一个树预测器的组合体，每棵树都取决于一个独立同分布的随机向量。因而整个森林的泛化误差随着森林数目的增多而收敛[12]。

时间终于走到了当下，一个新的NN领域——深度学习出现了。在这个阶段，NN模型可以拥有多层。3层的NN模型在2005年被Hinton,LeCun, Bengio, Andrew Ng等诸多大师一一实现。下面列举了一些深度学习上的重要概念：

Ø  GPU programming

Ø  Convolutional NNs [18][20][40]

Ø  Deconvolutional Networks [21]

Ø  Optimization algorithms

Ø  Stochastic Gradient Descent [19][22]

Ø  BFGS and L-BFGS [23]

Ø  Conjugate Gradient Descent [24]

Ø  Backpropagation [40][19]

Ø  Rectifier Units

Ø  Sparsity [15][16]

Ø  Dropout Nets [26]

Ø  Maxout Nets  [25]

Ø  Unsupervised NN models [14]

Ø  Deep Belief Networks [13]

Ø  Stacked Auto-Encoders [16][39]

Ø  Denoising NN models [17]

将上面列举的这些技术和想法综合到一起，NN模型迎来了又一个春天，在物体识别、语音识别、自然语言处理等方面，均击败之前的最高水平的技术。但重要的事，这并不意味着其他ML流派的终结，即使现在深度学习的成功故事还在一个接一个的上演，仍然有着参数众多、训练花费巨大的缺陷。而且，SVM由于其简单性仍然被广泛使用。

在结束之前，我们再介绍一个相对年轻的ML趋势，随着www和社会媒体的发展，大数据出现且影响了很多ML的研究。因为大数据中的问题数据量都极大，很多强大的ML算法在机器性能的限制下都变得有些无用（对大公司来说自然不是这样）。因此，研究人员提出了一套简单模型——dubbed  Bandit Algorithms[27-38]，这些算法都是在线学习算法，都能适应大规模问题。

这只是一个简单的ML历史的介绍，若有问题，欢迎指出。

Reference：

[1] Hebb D. O., The organization of behaviour. New York: Wiley & Sons.

[2] Rosenblatt, Frank. "The perceptron: a probabilistic model for information storage and organization in the brain."  Psychological review 65.6 (1958): 386.

[3] Minsky, Marvin, and Papert Seymour. "Perceptrons." (1969).

[4]Widrow, Hoff  "Adaptive switching circuits." (1960): 96-104.

[5]S. Linnainmaa. The representation of the cumulative rounding error of an algorithm as a Taylor
expansion of the local rounding errors. Master’s thesis, Univ. Helsinki, 1970.

[6] P. J. Werbos. Applications of advances in nonlinear sensitivity analysis. In Proceedings of the 10th
IFIP Conference, 31.8 - 4.9, NYC, pages 762–770, 1981.

[7]  Rumelhart, David E., Geoffrey E. Hinton, and Ronald J. Williams.  Learning internal representations by error propagation. No. ICS-8506. CALIFORNIA UNIV SAN DIEGO LA JOLLA INST FOR COGNITIVE SCIENCE, 1985.

[8]  Hecht-Nielsen, Robert. "Theory of the backpropagation neural network."  Neural Networks, 1989. IJCNN., International Joint Conference on. IEEE, 1989.

[9]  Quinlan, J. Ross. "Induction of decision trees."  Machine learning 1.1 (1986): 81-106.

[10]  Cortes, Corinna, and Vladimir Vapnik. "Support-vector networks."  Machine learning 20.3 (1995): 273-297.

[11]  Freund, Yoav, Robert Schapire, and N. Abe. "A short introduction to boosting." Journal-Japanese Society For Artificial Intelligence 14.771-780 (1999): 1612.

[12]  Breiman, Leo. "Random forests."  Machine learning 45.1 (2001): 5-32.

[13]  Hinton, Geoffrey E., Simon Osindero, and Yee-Whye Teh. "A fast learning algorithm for deep belief nets."  Neural computation 18.7 (2006): 1527-1554.

[14] Bengio, Lamblin, Popovici, Larochelle, "Greedy Layer-Wise
Training of Deep Networks", NIPS’2006

[15] Ranzato, Poultney, Chopra, LeCun " Efficient Learning of  Sparse Representations with an Energy-Based Model ", NIPS’2006

[16] Olshausen B a, Field DJ. Sparse coding with an overcomplete basis set: a strategy employed by V1? Vision Res. 1997;37(23):3311–25. Available at: http://www.ncbi.nlm.nih.gov/pubmed/9425546.

[17] Vincent, H. Larochelle Y. Bengio and P.A. Manzagol,  Extracting and Composing Robust Features with Denoising Autoencoders , Proceedings of the Twenty-fifth International Conference on Machine Learning (ICML‘08), pages 1096 - 1103, ACM, 2008.

[18]  Fukushima, K. (1980). Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics, 36, 193–202.

[19]  LeCun, Yann, et al. "Gradient-based learning applied to document recognition." Proceedings of the IEEE 86.11 (1998): 2278-2324.

[20]  LeCun, Yann, and Yoshua Bengio. "Convolutional networks for images, speech, and time series."  The handbook of brain theory and neural networks3361 (1995).

[21]  Zeiler, Matthew D., et al. "Deconvolutional networks."  Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010.

[22] S. Vishwanathan, N. Schraudolph, M. Schmidt, and K. Mur- phy. Accelerated training of conditional random fields with stochastic meta-descent. In International Conference on Ma- chine Learning (ICML ’06), 2006.

[23] Nocedal, J. (1980). ”Updating Quasi-Newton Matrices with Limited Storage.” Mathematics of Computation 35 (151): 773782. doi:10.1090/S0025-5718-1980-0572855-

[24] S. Yun and K.-C. Toh, “A coordinate gradient descent method for l1- regularized convex minimization,” Computational Optimizations and Applications, vol. 48, no. 2, pp. 273–307, 2011.

[25] Goodfellow I, Warde-Farley D. Maxout networks. arXiv Prepr arXiv …. 2013. Available at: http://arxiv.org/abs/1302.4389. Accessed March 20, 2014.

[26] Wan L, Zeiler M. Regularization of neural networks using dropconnect. Proc …. 2013;(1). Available at: http://machinelearning.wustl.edu/mlpapers/papers/icml2013_wan13. Accessed March 13, 2014.

[27]  Alekh Agarwal ,  Olivier Chapelle ,  Miroslav Dudik ,  John Langford ,  A Reliable Effective Terascale Linear Learning System , 2011

[28]  M. Hoffman ,  D. Blei ,  F. Bach ,  Online Learning for Latent Dirichlet Allocation , in Neural Information Processing Systems (NIPS) 2010.

[29]  Alina Beygelzimer ,  Daniel Hsu ,  John Langford , and  Tong Zhang   Agnostic Active Learning Without Constraints  NIPS 2010.

[30]  John Duchi ,  Elad Hazan , and  Yoram Singer ,  Adaptive Subgradient Methods for Online Learning and Stochastic Optimization , JMLR 2011 & COLT 2010.

[31]  H. Brendan McMahan ,  Matthew Streeter ,  Adaptive Bound Optimization for Online Convex Optimization , COLT 2010.

[32]  Nikos Karampatziakis  and  John Langford ,  Importance Weight Aware Gradient Updates  UAI 2010.

[33]  Kilian Weinberger ,  Anirban Dasgupta ,  John Langford ,  Alex Smola ,  Josh Attenberg ,  Feature Hashing for Large Scale Multitask Learning , ICML 2009.

[34]  Qinfeng Shi ,  James Petterson ,  Gideon Dror ,  John Langford ,  Alex Smola , and  SVN Vishwanathan , Hash Kernels for Structured Data , AISTAT 2009.

[35]  John Langford ,  Lihong Li , and  Tong Zhang ,  Sparse Online Learning via Truncated Gradient , NIPS 2008.

[36]  Leon Bottou ,  Stochastic Gradient Descent , 2007.

[37]  Avrim Blum ,  Adam Kalai , and  John Langford   Beating the Holdout: Bounds for KFold and Progressive Cross-Validation . COLT99 pages 203-208.

[38]  Nocedal, J.  (1980). "Updating Quasi-Newton Matrices with Limited Storage". Mathematics of Computation 35: 773–782.

[39] D. H. Ballard. Modular learning in neural networks. In AAAI, pages 279–284, 1987.

[40] S. Hochreiter. Untersuchungen zu dynamischen neuronalen Netzen. Diploma thesis, Institut f ̈ur In-
formatik, Lehrstuhl Prof. Brauer, Technische Universit ̈at M ̈unchen, 1991. Advisor: J. Schmidhuber.