机器学习发展历史回顾

本文为回溯机器学习发展历史阅读笔记，全文链接：机器学习发展历史回顾
在之后的学习中会以此为学习路线，逐步阅读所有机器学习方面的经典论文，并对本文中简略提及的算法进行总结和详细分析。

1 概述

机器学习是现阶段解决很多人工智能问题的主流方法。最早的机器学习算法可以追溯到20世纪初，到今天为止，已经过去了100多年。从1980年机器学习称为一个独立的方向开始算起，到现在也已经过去了近40年。

2 分类

总体上，机器学习算法可以分为有监督学习，无监督学习，强化学习 3种类型。半监督学习可以认为是有监督学习与无监督学习的结合，不在本文讨论的范围之类。

2.1 有监督学习

定义： 通过训练样本学习得到一个模型，然后用这个模型进行推理。
关键词： 有样本训练
举例： 识别水果图像 （分类问题）

1. 人工标注
2. 样本训练得到模型
3. 利用模型对未知水果进行判断（预测）

若上述预测的是一个实数，如根据一个人的学历、工作年限、所在城市、行业等特征来预测这个人的收入，则属于回归问题。

2.2 无监督学习

定义： 没有训练过程，给定一些样本数据，让机器学习算法直接对这些数据进行分析，得到数据的某些知识。
关键词： 没有训练过程
举例： 网页归类 （聚类）

1. 抓取1w个网页
2. 聚类算法对网页进行归类

无监督学习的另外一类典型算法是数据降维，它将一个高维向量变换到低维空间中，并且要保持数据的一些内在信息和结构。

2.3 强化学习

定义： 强化学习是一类特殊的机器学习算法，算法要根据当前的环境状态确定一个动作来执行，然后进入下一个状态，如此反复，目标是让得到的收益最大化。
关键词： 有优化过程，启发式搜索
举例： 围棋游戏
在每个时刻，要根据当前的棋局决定在什么地方落棋，然后进行下一个状态，反复的放置棋子，直到赢得或者输掉比赛。这里的目标是尽可能的赢得比赛，以获得最大化的奖励。

2.4 总结

总结来说，这些机器学习算法要完成的任务是：

分类算法-是什么？ 即根据一个样本预测出它所属的类别。

回归算法-是多少？ 即根据一个样本预测出一个数量值。

聚类算法-怎么分？ 保证同一个类的样本相似，不同类的样本之间尽量不同。

强化学习-怎么做？ 即根据当前的状态决定执行什么动作，最后得到最大的回报。

3 详细介绍

3.1 有监督学习

下图列出了经典的有监督学习算法（深度学习不在此列）：

3.1.1 线性判别分析（LDA）

来历：1936年，Fisher
Fisher, R. A. (1936). The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics. 7 (2): 179–188.
类别：有监督的数据降维算法
介绍：通过线性变换将向量投影到低维空间中，保证投影后同一种类型的样本差异很小，不同类的样本尽量不同。

3.1.2 贝叶斯分类器

来历：1950年代
类别：分类器
介绍：基于贝叶斯决策理论，把样本分到后验概率最大的那个类。

3.1.3 logistic回归

来历：1958年
Cox, DR (1958). The regression analysis of binary sequences (with discussion). J Roy Stat Soc B. 20 (2): 215–242.
类别：解决回归问题
介绍：它直接预测出一个样本属于正样本的概率，在广告点击率预估、疾病诊断等问题上得到了应用。

3.1.4 感知器模型

来历：1958年
Rosenblatt, F. (1958). “The Perceptron: A Probalistic Model For Information Storage And Organization In The Brain”. Psychological Review. 65 (6): 386–408.
类别：线性分类器
介绍：它过于简单，甚至不能解决异或问题，因此不具有实用价值，更多的起到了思想启蒙的作用，为后面的算法奠定了思想上的基础。
个人理解：非黑即白的分类器

3.1.5 KNN

来历：1967年
Thomas M Cover, Peter E Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 1967.

介绍：这是一种基于模板匹配思想的算法，虽然简单，但很有效，至今仍在被使用。

总结： 在1980年之前，这些机器学习算法都是零碎化的，不成体系。但它们对整个机器学习的发展所起的作用不能被忽略。
从1980年开始，机器学习才真正成为一个独立的方向。在这之后，各种机器学习算法被大量的提出，得到了快速发展。

3.1.6 决策树

来历：1980年代到1990年代初期，三种典型实现——ID3[4]，CART[5]，C4.5[6]
[4] Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106
[5] Breiman, L., Friedman, J. Olshen, R. and Stone C. Classification and Regression Trees, Wadsworth, 1984.
[6] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

介绍：简单，但可解释性强，这使得决策树至今在一些问题上仍被使用。

3.1.7 反向传播算法

来历：1986年
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning internal representations by back-propagating errors. Nature, 323(99): 533-536, 1986.
介绍：这是现在的深度学习中仍然被使用的训练算法，奠定了神经网络走向完善和应用的基础。

3.1.8 卷积神经网络

来历：1989年
Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, L. D. Jackel, Backpropagation Applied to Handwritten Zip Code Recognition. 1989.
介绍：1989年，LeCun设计出了第一个真正意义上的卷积神经网络[13]，用于手写数字的识别，这是现在被广泛使用的深度卷积神经网络的鼻祖。

总结： 在1986到1993年之间，神经网络的理论得到了极大的丰富和完善，但当时的很多因素限制了它的大规模使用。

3.1.9 SVM

来历：1995年
介绍：SVM代表了核技术的胜利，这是一种思想，通过隐式的将输入向量映射到高维空间中，使得原本非线性的问题能得到很好的处理。

3.1.10 AdaBoost

来历：1995年
介绍：代表了集成学习算法的胜利，通过将一些简单的弱分类器集成起来使用，居然能够达到惊人的精度。

3.1.11 LSTM

来历：2000年
介绍：在很长一段时间内一直默默无闻，直到2013年后与深度循环神经网络整合，在语音识别上取得成功。

3.1.12 随机森林

来历：2001年
介绍：与AdaBoost算法同属集成学习，虽然简单，但在很多问题上效果却出奇的好，因此现在还在被大规模使用。

总结： 从1980年开始到2012年深度学习兴起之前，有监督学习得到了快速的发展，这有些类似于春秋战国时代，各种思想和方法层出不穷，相继登场。另外，没有一种机器学习算法在大量的问题上取得压倒性的优势，这和现在的深度学习时代很不一样。

3.2 无监督学习

相比于有监督学习，无监督学习的发展一直和缓慢，至今仍未取得大的突破。下面我们按照聚类和数据降维两类问题对这些无监督学习算法进行介绍。

3.2.1 聚类

聚类算法的历史与有监督学习一样悠久。层次聚类算法出现于1963年[26]，这是非常符合人的直观思维的算法，现在还在使用。它的一些实现方式，包括SLINK[27]，CLINK[28]则诞生于1970年代。

3.2.1.1 k均值算法

聚类算法中知名度最高的，其历史可以追溯到1967年，此后出现了大量的改进算法，也有大量成功的应用，是所有聚类算法中变种和改进型最多的。

3.2.1.2 EM算法

诞生于1977年，它不光被用于聚类问题，还被用于求解机器学习中带有缺数数据的各种极大似然估计问题。

3.2.1.3 Mean Shift算法

Mean Shift算法[32]早在1995年就被用于聚类问题，和DBSCAN算法[30]，OPTICS算法[31]一样，同属于基于密度的聚类算法。

3.2.1.4 谱聚类算法

诞生于2000年左右，它将聚类问题转化为图切割问题，这一思想提出之后，出现了大量的改进算法。

3.2.2 数据降维

经典的PCA算法[14]诞生于1901年，这比第一台真正的计算机的诞生早了40多年。LDA在有监督学习中已经介绍，在这里不再重复。

3.2.2.1 核PCA

来历：1998年
介绍：非线性降维算法。这是核技术的又一次登台，与PCA的结合将PCA改造成了非线性的降维算法。

3.2.2.2 局部线性嵌入LLL

来历：2000年
介绍：非线性方法。此后，拉普拉斯特征映射，局部保持投影，等距映射等算法相继提出[17-19]。流形学习在数学上非常优美，但遗憾的是没有多少公开报道的成功的应用。

3.2.2.3 t-SNE算法

降维算法中年轻的成员，诞生于2008年，虽然想法很简单，效果却非常好。

3.3 概率图模型

概率图模型是机器学习算法中独特的一个分支，它是图与概率论的完美结合。在这种模型中，每个节点表示随机变量，边则表示概率。有些晦涩，但理解了之后并不难。

3.3.1 隐马尔可夫模型

诞生于1960年，在1980年代，它在语音识别中取得了成功，一时名声大噪，后来被广泛用于各种序列数据分析问题，在循环神经网络大规模应用之前，处于主导地位。

3.3.2 马尔可夫随机场

马尔可夫随机场诞生于1974年[23]，也是一种经典的概率图模型算法。

3.3.3 贝叶斯网络

贝叶斯网络[22]是概率推理的强大工具，诞生于1985年，其发明者是概率论图模型中的重量级人物，后来获得了图灵奖。

3.3.4 条件随机场

条件随机场[24]是概率图模型中相对年轻的成员，被成功用于中文分词等自然语言处理，还有其他领域的问题，也是序列标注问题的有力建模工具。

3.4 强化学习

相比有监督学习和无监督学习，强化学习在机器学习领域的起步更晚。虽然早在1980年代就出现了时序差分算法[42-44]，但对于很多实际问题，我们无法用表格的形式列举出所有的状态和动作，因此这些抽象的算法无法大规模实用。

神经网络与强化学习的结合，即深度强化学习46-50]，才为强化学习带来了真正的机会。在这里，深度神经网络被用于拟合动作价值函数即Q函数，或者直接拟合策略函数，这使得我们可以处理各种复杂的状态和环境，在围棋、游戏、机器人控制等问题上真正得到应用。神经网络可以直接根据游戏画面，自动驾驶汽车的摄像机传来的图像，当前的围棋棋局，预测出需要执行的动作。其典型的代表是DQN[46]这样的用深度神经网络拟合动作价值函数的算法，以及直接优化策略函数的算法[47-50]。