1.1.3　机器学习简史

总体而言，机器学习可以分为有监督学习（supervised learning）、无监督学习（unsupervised learning）和强化学习（reinforcement learning）三类，半监督学习可以认为是有监督学习和无监督学习的结合，不再专门讨论。下面分别对这三类学习方法的发展历史进行简单回顾。

1．有监督学习

有监督学习通过训练样本学习得到一个模型，然后用这个模型进行推理与预测。如果只是预测一个类别值，则成为分类问题，如果需要预测一个实数值，则称之为回归问题。

1980年之前，有监督学习算法都是零碎化的，不成体系。比较著名的算法包括线性判别分析（linear discriminant analysis, LDA）方法（1936年）、贝叶斯分类器（1950年）、logistic回归（1958年）、感知机模型（1958年）、kNN算法（1967年）等。

1980年后，机器学习成为一个独立的方向。从1980年至1990年的重要成果是决策树，包括ID3、CART和C4.5。1986年诞生了反向传播算法，用于训练多层神经网络；1989年，LeCun设计出了第一个真正意义上的卷积神经网络，用于手写数字识别；1995年诞生了两种经典的算法SVM和Adaboost；1997年出现了LSTM（long short-term memory）算法；2001年出现了随机森林算法。

从1980年开始到2012年深度学习兴起之前，有监督学习得到了快速的发展，各种思想和方法层出不穷，百家争鸣。2012年，Alex网络的成功使得深度神经网络卷土重来。在这之后，卷积神经网络（convolutional neural networks, CNN）被广泛地应用于机器视觉的各类问题。循环神经网络（recurrent neural network, RNN）则被用于语音识别、自然语言处理等序列预测问题。整合了循环神经网络和编码器-解码器框架的seq2seq技术解决了大量的实际应用问题。生成式对抗网络（generative adversarial networks, GAN）作为深度生成模型的典型代表，可以生成以假乱真的图像，取得了不可思议的效果。

2．无监督学习

无监督学习没有训练过程，其主要过程是给定一些样本数据，让机器学习算法直接对这些数据进行分析，得到数据的某些知识，典型代表是聚类。

与有监督学习相比，无监督学习的发展较为缓慢，至今仍未取得大的突破，下面我们从聚类和数据降维两个方面对无监督学习的算法进展做个介绍。

（1）聚类。聚类是无监督学习中历史悠久的一类问题，层次聚类方法出现于1963年，该方法非常符合人的直观思维过程，至今仍然广泛使用。经典的k均值算法（k-means）出现于1967年，此后出现了大量的改进算法，应用非常广泛。EM算法出现于1977年，不光用于聚类问题，还用于求解机器学习中带有缺失数据的各种极大似然估计问题。Mean shift算法、DBSCAN和OPTICS算法都是属于基于密度的聚类算法。谱聚类算法诞生于2000年，该类算法将聚类问题转化为图切割问题。

（2）数据降维。经典的PCA算法诞生于1901年。1930年出现了线性判别分析方法。此后近70年中，数据降维在机器学习领域一直没有重量级的成果，直到1998年，核PCA作为非线性降维算法出现。2000年开始，流形学习方法开始兴起，包括局部线性嵌入、拉普拉斯特征映射、局部保持投影、等距映射等算法相继提出。2008年出现了t-SNE（t-distributed stochastic neighbor embedding）算法，想法简单，效果很好。

3．强化学习

强化学习算法要根据当前的环境状态确定一个动作来执行，然后进入下一个状态，如此反复，目标是让得到的收益最大化。常见的强化学习算法的应用场景是棋类游戏。

与有监督学习和无监督学习相比，强化学习方法的起步更晚。20世纪80～90年代出现了时序差分学习、Q学习和SARSA等算法，但由于状态和动作空间过于巨大，无法穷举，因此强化学习方法一直无法大规模使用。直到2010年后，将神经网络与强化学习相结合，即深度强化学习（deep reinforcement learning, DRL）才为强化学习带来了实用化的机会，代表性算法包括Double Q学习、DQN、DPG、DDPG、A3C和AlphaGo等。