本文主要参考中科院自动化研究所复杂系统与智能科学实验室王珏研究员《关于机器学习的讨论》，讨论机器学习的描述，理论基础，发展历史以及研究现状。
0引言
20世纪90年代初，当时的美国副总统提出了一个重要的计划——国家信息基本设施计划(NationalInformationInfrastructure,NII)。这个计划的技术含义包含了四个方面的内容：
(4)保证信息安全。
本文主要讨论解决“信息有效利用”问题，其本质是：如何根据用户的特定需求从海量数据中建立模型或发现有用的知识。对计算机科学来说，这就是机器学习。
计算机科学，特别是人工智能的研究者一般公认Simon对学习的论述：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。”这是一个相当广泛的说明,其要点是“系统”,它涵盖了计算系统、控制系统以及人系统等,对这些不同系统的学习,显然属于不同的科学领域。即使计算系统,由于目标不同,也分为了“从有限观察概括特定问题世界模型的机器学习”、“发现观测数据中暗含的各种关系的数据分析”,以及“从观测数据挖掘有用知识的数据挖掘”等不同分支。由于这些分支发展的各种方法的共同目标都是“从大量无序的信息到简洁有序的知识”,因此,它们都可以理解为Simon意义下的“过程”,也就都是“学习”。
1机器学习描述
本文将讨论限制在“从有限观察概括特定问题世界模型的机器学习”与“从有限观察发现观测数据中暗含的各种关系的数据分析”的方法上,并统称其为机器学习。
我们描述机器学习如下:
令W是给定世界的有限或无限的所有观测对象的集合,由于我们观察能力的限制,我们只能获得这个世界的一个有限的子集QW,称为样本集。机器学习就是根据这个样本集,推算这个世界的模型,使它对这个世界(尽可能地)为真。
这个描述隐含了三个需要解决的问题:
(1)一致:假设世界W与样本集Q有相同的性质。例如,如果学习过程基于统计原理,独立同分布(i.i.d)就是一类一致条件。
(2)划分:将样本集放到n维空间,寻找一个定义在这个空间上的决策分界面(等价关系),使得问题决定的不同对象分在不相交的区域。
(3)泛化:泛化能力是这个模型对世界为真程度的指标。从有限样本集合,计算一个模型,使得这个指标最大(最小)。
这些问题对观测数据提出了相当严厉的条件,首先需要人们根据一致假设采集数据,由此构成机器学习算法需要的样本集;其次,需要寻找一个空间,表示这个问题;最后,模型的泛化指标需要满足一致假设,并能够指导算法设计。这些条件限制了机器学习的应用范围。
2机器学习的发展历史
2.1机器学习与人工智能
机器学习是人工智能研究的核心内容。它的应用已遍及人工智能的各个分支，如专家系统、自动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。
2.2机器学习的理论基础
机器学习的科学基础之一是神经科学,然而,对机器学习进展产生重要影响的是以下三个发现,分别是:
(1)James关于神经元是相互连接的发现。
(2)McCulloch与Pitts关于神经元工作方式是“兴奋”和“抑制”的发现。
(3)Hebb的学习律(神经元相互连接强度的变化)。
其中,McCulloch与Pitts的发现对近代信息科学产生了巨大的影响。对机器学习,这项成果给出了近代机器学习的基本模型,加上指导改变连接神经元之间权值的Hebb学习律,成为目前大多数流行的机器学习算法的基础。
1954年,Barlow与Hebb在研究视觉感知学习时,分别提出了不同假设:Barlow倡导单细胞学说,假设从初级阶段而来的输入集中到具有专一性响应特点的单细胞,并使用这个神经单细胞来表象视觉客体。这个考虑暗示,神经细胞可能具有较复杂的结构;而Hebb主张视觉客体是由相互关联的神经细胞集合体来表象,并称其为ensemble。在神经科学的研究中,尽管这两个假设均有生物学证据的支持,但是,这个争论至今没有生物学的定论。这个生物学的现实,为我们计算机科学家留下了想象的空间,由于在机器学习中一直存在着两种相互补充的不同研究路线,这两个假设对机器学习研究有重要的启示作用。
在机器学习划分的研究中,基于这两个假设,可以清晰地将机器学习发展历程总结为:以感知机、BP与SVM等为一类；以样条理论、k-近邻、Madaline、符号机器学习、集群机器学习与流形机器学习等为另一类。
在McCulloch与Pitts模型的基础上,1957年,Rosenblatt首先提出了感知机算法,这是第一个具有重要学术意义的机器学习算法。这个思想发展的坎坷历程,正是机器学习研究发展历史的真实写照。感知机算法主要贡献是:首先,借用最简单的McCulloch与Pitts模型作为神经细胞模型;然后,根据Hebb集群的考虑,将多个这样的神经细胞模型根据特定规则集群起来,形成神经网络,并将其转变为下述机器学习问题:计算一个超平面,将在空间上不同类别标号的点划分到不同区域。在优化理论的基础上,Rosenblatt说明,如果一个样本集合是线性可分,则这个算法一定可以以任何精度收敛。由此导致的问题是,对线性不可分问题如何处理。
1969年,Minsky与Paper出版了对机器学习研究具有深远影响的著作Perceptron(《感知机》)。目前,人们一般的认识是,由于这本著作中提出了XOR问题,从而扼杀了感知机的研究方向。然而,在这本著作中对机器学习研究提出的基本思想,至今还是正确的,其思想的核心是两条:
(1)算法能力:只能解决线性问题的算法是不够的,需要能够解决非线性问题的算法。
(2)计算复杂性:只能解决玩具世界问题的算法是没有意义的,需要能够解决实际世界问题的算法。
在20世纪60年代的另一个重要研究成果来自Widrow。1960年,Widrow推出了Madaline模型,在算法上,对线性不可分问题,其本质是放弃划分样本集的决策分界面连续且光滑的条件,代之分段的平面。从近代的观点来看,这项研究与感知机的神经科学假设的主要区别是:它是确认Barlow假设中神经细胞具有较复杂结构的思想,由此,将线性模型(例如,感知机)考虑为神经细胞模型(而不是简单的McCulloch与Pitts模型),然后,再基于Hebb神经元集合体假设,将这些局部模型集群为对问题世界的表征,由此解决线性不可分问题。但是,这项研究远不如感知机著名,其原因是:其一,尽管Madaline可以解决线性不可分问题,但是,其解答可能是平凡的;其二,Widrow没有给出其理论基础,事实上,其理论基础远比感知机复杂,直到1990年,Schapire根据Valiant的“概率近似正确(PAC)”理论证明了“弱可学习定理”之后,才真正引起人们的重视。
进一步比较机器学习中两个不同路线的神经科学启示是有趣的:对机器学习来说,它们最显著的差别是对神经细胞模型的假设,例如,感知机是以最简单的McCulloch与Pitts模型作为神经细胞模型,而Madaline是以问题世界的局部模型作为神经细胞模型,两种方法都需要根据Hebb思想集群。因此,对机器学习研究,两个神经科学的启示是互补的。但是,两者还有区别:前者强调模型的整体性,这与Barlow“表征客体的单一细胞论”一致,因此,我们称其为Barlow路线;而后者则强调对世界的表征需要多个神经细胞集群,这与Hebb“表征客体的多细胞论”一致,我们称其为Hebb路线。鉴于整体模型与局部模型之间在计算上有本质差别,尽管根据Barlow与Hebb假设区分机器学习的方法。
在这一节的最后,将1989年Carbonell对机器学习以后十年的展望与十年后Dietterich的展望作一个对比,可能是有趣的,我们希望以此说明机器学习研究由于面临问题的改变所发生的变迁(表1)。
3统计机器学习
3.1统计机器学习概述
统计机器学习方法的基本假设是同类数据具有一定的统计规律性。其目标是从假设空间（也即模型空间，从输入空间到输出空间的映射函数空间）中寻找一个最优的模型。
通过对统计机器学习目标的描述，我们可以发现统计机器学习方法主要研究三个问题：
(1)模型假设：这个问题解决的是如何将样本从输入空间转化到输出空间的，它往往是一个后验概率或者是一个映射函数。
(2)模型选择：模型所在空间也就是假设空间，往往包含无穷多个满足假设的可选模型，如何从假设空间中选择一个最优模型，应该采用怎样的选择标准？这就是模型选择应该解决的问题。一般采用损失函数来制定模型选择策略，将模型选择转化为一个最优化问题来求解。常用的损失函数包括0-1损失、平方误差损失、绝对损失、对数损失等等。通常我们也会在损失函数中加上正则化项，从而降低模型的复杂性，提高模型的泛化能力，拒绝Overfitting。
(3)学习算法：学习算法是用来解决最优化问题的方法。在给定损失函数后，如何快速找到损失函数约定条件下的最优解就是学习算法需要解决的问题。常用的学习算法包括梯度下降、拟牛顿法等等。
统计机器学习方法的三个问题都是非常值得研究的，对于模型假设这个问题，如果模型都选择错误，无论后面如何选择模型，也都难以反映数据集的正确分布。因此，首先需要选择对模型做出正确假设，如何选择模型的假设空间是一个学问，除掉交叉验证的方法之外还有不少其他方法。模型选择的关键在于如何设计损失函数，而损失函数通常包括损失项和正则化项，不同的模型选择策略通常选出的模型也非常不同，从而导致模型的预测效果也大大不同。学习算法比较定式，不同的学习算法不仅学习的效率不同，而且学习出来的效果也不一样。
3.2统计机器学习的理论基础
尽管以Open问题驱动的BP算法研究大大推动了感知机研究方向的发展,然而,近十年计算机科学与技术的快速发展,使得人们获得数据的能力大大提高,BP这类算法已不能完全适应这种需求,同时,Minsky的算法设计原则愈显重要。
然而,沿着Barlow路线的机器学习研究并没有终止,自1992年开始,Vapnik将有限样本统计理论介绍给全世界,并出版了统计机器学习理论的著作尽管这部著作更多地是从科学、哲学上讨论了机器学习的诸多问题,但是,其暗示的算法设计思想对以后机器学习算法研究产生了重要的影响。
Vapnik的研究主要涉及机器学习中两个相互关联的问题,泛化问题与表示问题。前者包含两个方面的内容:其一,有限样本集合的统计理论;其二,概率近似正确的泛化描述。而后者则主要集中在核函数,由此,将算法设计建立在线性优化理论之上。
Valiant的“概率近似正确”学习的考虑在机器学习的发展中扮演了一个重要的角色。1984年,Valiant提出了机器学习的一个重要考虑,他建议评价机器学习算法应该以“概率近似正确(PAC)”为基础,而不是以传统模式识别理论中以概率为1成立为基础,由此,他引入了类似在数学分析中的ε-δ语言来描述PAC,这个考虑对近代机器学习研究产生了重要的影响。首先,统计机器学习理论中泛化不等式的推导均以这个假设为基础;其次,基于这个考虑的“弱可学习理论”,为研究基于Hebb路线的学习算法设计奠定了理论基础,并产生被广泛应用的集群机器学习理念(ensemble)。
3.3统计机器学习的研究现状
3.3.1SVM与DeepLearning的竞争
可以认为神经网络与支持向量机都源自于感知机（Perceptron）。感知机是由Rosenblatt发明的线性分类模型（1958年）。感知机对线性分类有效，但现实中的分类问题通常是非线性的。
神经网络与支持向量机（包含核方法）都是非线性分类模型。1986年，Rummelhart与McClelland发明了神经网络的学习算法BackPropagation。后来，Vapnik等人于1992年提出了支持向量机。神经网络是多层（通常是三层）的非线性模型，支持向量机利用核技巧把非线性问题转换成线性问题。
神经网络与支持向量机一直处于“竞争”关系。SVM应用核函数的展开定理，无需知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”。而早先的神经网络算法比较容易过训练，大量的经验参数需要设置；训练速度比较慢，在层次比较少(小于等于3)的情况下效果并不比其它方法更优。
神经网络研究领域领军者Hinton在2006年提出了神经网络DeepLearning算法，使神经网络的能力大大提高，向支持向量机发出挑战。DeepLearning假设神经网络是多层的，首先用RestrictedBoltzmannMachine（非监督学习）学习网络的结构，然后再通过BackPropagation（监督学习）学习网络的权值。
3.3.2支持向量机SVM
SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilber空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题。升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津。但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）。一般的升维都会带来计算的复杂化，SVM方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．
选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：
⑴性核函数K(x,y)=x·y；
⑵多项式核函数K(x,y)=[(x·y)+1]d；
⑵向基函数K(x,y)=exp(-|x-y|^2/d^2）
⑶层神经网络核函数K(x,y)=tanh(a(x·y)+b）．
3.3.2.1SVM有如下主要几个特点：
(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；
(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；
(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。(4)SVM是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
(5)SVM的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
(6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
①增、删非支持向量样本对模型没有影响;
②支持向量样本集具有一定的鲁棒性;
③有些成功的应用中,SVM方法对核的选取不敏感
3.3.2.2SVM的两个不足：
(1)SVM算法对大规模训练样本难以实施
(2)用SVM解决多分类问题存在困难
经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。
3.3.2DeepLearning
DeepLearning本身算是MachineLearning的一个分支，简单可以理解为NeuralNetwork的发展。大约二三十年前，NeuralNetwork曾经是ML领域特别火热的一个方向，但是后来确慢慢淡出了，原因包括以下几个方面：
(1)比较容易过训练，参数比较难确定；
(2)训练速度比较慢，在层次比较少(小于等于3)的情况下效果并不比其它方法更优；
3.3.3.1DeepLearning与传统的神经网络异同
DeepLearning与传统的神经网络的相同在于DeepLearning采用了神经网络相似的分层结构，系统由包括输入层、隐层（多层）、输出层组成的多层网络，只有相邻层节点之间有连接，同一层以及跨层节点之间相互无连接，每一层可以看作是一个LogisticRegression模型；这种分层结构，是比较接近人类大脑的结构的。
而为了克服神经网络训练中的问题，DL采用了与神经网络很不同的训练机制。传统神经网络中，采用的是BackPropagation的方式进行，简单来讲就是采用迭代的算法来训练整个网络，随机设定初值，计算当前网络的输出，然后根据当前输出和label之间的差去改变前面各层的参数，直到收敛（整体是一个梯度下降法）。而DeepLearning整体上是一个Layer-Wise的训练机制。这样做的原因是因为，如果采用BackPropagation的机制，对于一个DeepNetwork（7层以上），残差传播到最前面的层已经变得太小，出现所谓的GradientDiffusion。
3.3.3.2DeepLearning训练过程
(2)基于第一步得到的各层参数进一步fine-tune整个多层模型的参数，这一步是一个有监督训练过程；第一步类似神经网络的随机初始化初值过程，由于DL的第一步不是随机初始化，而是通过学习输入数据的结构得到的，因而这个初值更接近全局最优，从而能够取得更好的效果；所以deeplearning效果好很大程度上归功于第一步的featurelearning过程。
总之，deeplearning能够得到更好地表示数据的feature，同时由于模型的层次、参数很多，capacity足够，因此，模型有能力表示大规模数据，所以对于图像、语音这种特征不明显（需要手工设计且很多没有直观物理含义）的问题，能够在大规模训练数据上取得更好的效果。此外，从模式识别特征和分类器的角度，deeplearning框架将feature和分类器结合到一个框架中，用数据去学习feature，在使用中减少了手工设计feature的巨大工作量（这是目前工业界工程师付出努力最多的方面），因此，不仅仅效果可以更好，而且，使用起来也有很多方便之处。
4集群机器学习
4.1弱可学习定理
4.2经典算法
AdaBoost是Boosting家族中的基础算法。Boosting家族中的大部分扩展(算法)都由它得来,对AdaBoost的分析结论也适用于其它的Boosting。下面简要地介绍一下它的思想。
AdaBoost算法的主要思想是给定一弱学习算法和训练集(x1,y1),,,(xn,yn)。这里xi为一向量,yi对于分类问题为一类别标志,对于回归问题为一数值。初始化时对每一个训练例赋相等的权重1/n,然后用该学习算法对训练集训练t轮,每次训练后,对训练失败的训练例赋以较大的权重,也就是让学习算法在后续的学习中集中对比较难的训练例进行学习,从而得到一个预测函数序列h1,,,ht,其中hj也有一定的权重,预测效果好的预测函数权重较大,反之较小。最终的预测函数H对分类问题采用有权重的投票方式,对回归问题采用加权平均的方法对新示例进行判别。
Boosting算法是一种基于其他机器学习算法之上的用来提高算法精度和性能的方法。当用于回归分析时,不需要构造一个拟合精度高、预测能力好的回归算法,只要一个效果只比随机猜测略好的粗糙算法即可,称之为基础算法。通过不断地调用这个基础算法就可以获得一个拟合和预测误差都相当好的组合回归模型。Boosting算法可以应用于任何的基础回归算法,无论是线性回归、神经网络、还是SVM方法,都可以有效地提高精度。因此,Boosting可以被视为一种通用的增强基础算法性能的回归分析算法。
Bagging(BootstrapAggregating)又被称为自举聚合,是Breiman提出的与Boosting相似的技术。[11]Bagging技术的主要思想是给定一弱学习算法和一训练集(x1,y1),,(xn,yn)。让该学习算法训练多轮,每轮的训练集由从初始的训练集中随机取出的n个训练例组成,初始训练例在某轮训练集中可以出现多次或根本不出现。训练之后可得到一个预测函数序列:h1,,,ht,最终的预测函数H对分类问题采用投票方式,对回归问题采用简单平均。
5符号机器学习
符号机器学习的最大优点是归纳的解答与归纳的过程是可解释的,换句话说,数据集合中的每个观测(样本或对象)对用户都是透明的,它在解答以及计算过程中所扮演的角色,用户都是可以显现了解的。然而,它的缺陷同样突出,就是泛化能力。由于学习结果是符号表述,因此,只可能取“真”与“假”,这样大大减低了对具有一定噪音数据的分析能力,需要其他技术来补充:其一,观测世界的数据到符号域的映射,其二,不确定推理机制。但是,这两种方法与符号机器学习方法本身并没有必然的关系。
近几年,由于数据挖掘的提出,符号机器学习原理有了新的用途,这就是符号数据分析,在数据挖掘中称为数据描述,以便与数据预测类型的任务相区别(从任务来说,这类任务与机器学习是一致的)。
与机器学习的目标不同,数据分析不是以所有用户具有相同需求为假设,相反,强调不同用户具有不同的需求。另外,数据分析强调,分析结果是为用户提供可阅读的参考文本,决策将依赖人的洞察。如何根据用户的特定需求将观测数据集合变换为简洁的、可为用户理解的表示成为关键。这是符号机器学习的另一个可以考虑的应用领域。由于符号机器学习在泛化能力上的欠缺,这也是它在与基于统计的机器学习方法竞争中避免遭到淘汰的出路。
6增强机器学习方法
增强机器学习(reinforcementlearning)的本质是对变化的环境的适应。应该说,这是一种“古老”的机器学习思想.在1948年,Wiener的著作“控制论”中,就讨论了这个问题,而在以后的控制理论的研究中,这发展成为重要的研究课题——自适应控制。由于控制理论研究这个问题的焦点在于控制品质,且其使用的数学工具是微分方程,因此,对非线性问题,使用计算机进行数值求解存在着本质性的困难。这是这类机器学习长期未得到计算机科学家注意的原因。
直到20世纪70年代,Holland在讨论进化计算时,需要考虑控制物种群体的染色体数量,以便淘汰对变化环境不适应的个体,为此,提出使用桶队算法解决这个问题。桶队算法在Holland提出的分类器系统中扮演着对变换环境适应的角色。
以后,在20世纪90年代初,Sutton提出将这类机器学习建立在Markov过程上,并称其为增强机器学习方法。这个方法是根据环境变化对系统的刺激,并作为系统输入,然后,利用基于统计的方法优化转移概率,并使系统适应新的环境。
一般地说,增强机器学习应该属于无教师学习,但是,如果考虑环境就是教师,这类机器学习也可以认为是一类特殊有教师的机器学习,与一般有教师机器学习的区别在于:教师是环境,且是变化的环境。这意味着,不像传统意义下的有教师学习,教师教授的知识不是事先给定的,而是采用更灵活方法,在问题求解的过程中获得的。
7总结
本文从机器学习的起源，发展依据，历史上的重要事件角度讨论了机器学习发展脉络。通过“对神经细胞模型假设的差别”将机器学习领域划分为两大支系——强调模型的整体性，基于Barlow“表征客体的单一细胞论”的Barlow路线；强调对世界的表征需要多个神经细胞集群，基于Hebb“表征客体的多细胞论”的Hebb路线。这一划分可以清晰地将机器学习发展历程总结为：以感知机、BP与SVM等为一类的Barlow路线；以样条理论、k-紧邻、Madaline、符号机器学习，集群机器学习与流行机器学习等为一类的Hebb路线。
本文提倡研究者需要重视这样一个问题：我们探讨机器学习在理念、理论、与技术上发展的各种方法所遵循的假设，是否能够适应当前任务的需要？如果问题是否定的,那么，我们是修补这些已被普遍认可的理念、理论与方法(打补丁)，以适应当前的需要，还是从根本上清理原有假设，提出新的假设，从而发展新的理念、理论和方法？这是一个需要仔细分析已有理论与方法，并权衡各种利弊才能决定的事情。综上所述，讨论机器学习发展脉络，以从这个脉络发现有趣的经验和教训，对回答这个问题是重要的，这必须考虑机器学习发展的科学依据，历史上的重要事件，以及理论研究中的重要结论。这就是我们本文的讨论集中在动机和理论的原因。