机器学习综述

机器学习综述曹晓敏摘要：机器学习是计算机领域最活泼，最有潜力的方向之一。本文概述了机器学习当前研究的几个方向：符号机器学习、集成机器学习、增强机器学习、统计机器学习，梳理了各自的理论根底。在此根底上，以统计机器学习为重点，就其一致性、收敛性、推广性以及构造算法的原那么四个核心方面进行了综述，最后提出几点思考和建议。引言计算机相比人脑而言在存储、计算方面具有无与伦比的优势，然而，其是否可以具备一定智能，一直以来是科学家们、科幻小说家们致力研究、探索和想象的一片非常广阔的领域。计算机智能化的起步阶段包含两方面工作：一方面是将人类已有的知识或经验“教”会计算机，从而使计算机成为某个领域的专家，其焦点在于知识库和推理机两方面，已经有比拟成功的案例；另一方面是从大量的数据、现象中，学习产生新的知识或经验，这就是机器学习过程。后者比前者难，前者开展到一定程度会面临同样的问题。目前，机器学习已经成为计算机领域最活泼，最有潜力的研究方向之一，受到了广泛的关注。机器学习概述机器学习的经典定义是1997年TomM.Mitchell在“MachineLearning”一书中提出的“计算机利用经验改善系统自身性能的行为。”这是一个相当宽泛的说明，将“机器”限定在“计算机”，而对学习的定义那么过于宽泛以致不便理解。人们通常所说的“学习”是指通过对事实的分析、归纳、演绎，形成新的知识，其目的在于对未知的事实能做出比拟符合实际的判断、指导和预测。其中有四个关键要素：事实、学习方法、新的知识、预判未来。其关系如REF_Ref264796613\h图1所示。得到得到知识事实新的事实学习方法指导未来图SEQ图\*ARABIC1学习过程对应于REF_Ref264796613\h图1，在机器学习领域，事实对应于“样本空间”，需要预判的新的事实对应于“问题空间”，所得到的知识对应于“构建的模型”。由此，机器学习可以描述为[3]：令W是问题空间，(x，y)∈W称为样本，其中，x是一个n维矢量，y是类别域中的一个值。由于观察能力的限制，我们只能获得W的一个真子集，记为Q⊂W，称为样本集合。根据Q建立模型M，并期望M对W中的所有样本预测的正确率大于一个给定的常数θ。M对W的预测正确率，称为M对W的泛化能力或推广能力。机器学习的本质和目的就是要使得M尽可能接近真实，也就是其泛化〔推广〕能力尽可能强。然而，机器学习面临的第一个问题就是其问题空间如何表示？即数据描述问题。对于计算机而言，最本质的特征是量化表示以及对数值的处理；对于人类而言，其思考、表达的过程往往借助于语言或图像，而不是数值。由此，诞生了两类不同方向的机器学习领域：基于符号的机器学习，基于数值的机器学习。1989年，Carbonell指出机器学习有4个研究方向：符号机器学习、连接机器学习、遗传机器学习与分析机器学习。十年过去后，1999年，Dietterich提出了另外4个新的研究方向：符号机器学习、统计机器学习、集成机器学习、增强机器学习。其关系如表1所示[4]。表SEQ表\*ARABIC1机器学习研究方向变迁Carbonell，1989Dietterich，1999注解符号机器学习符号机器学习保存：发生本质变化，转变成符号数据分析连接机器学习统计机器学习分为：基于Barlow提出的功能单细胞假设为依据集成机器学习分为：基于Hebb提出的神经集合体假设为依据遗传机器学习增强机器学习扩展：强调反应的作用，以及动态规划的解决方案分析机器学习——放弃：问题过于复杂其中，符号机器学习方法最初由于其建立的模型是确定的，不具备泛化能力而被认为不具备竞争能力，然而随着海量信息的出现以及对简洁阅读的要求，符号机器学习重新获得生命力。随着统计机器学习理论和技术的完善，连接机器学习渐渐演变为统计机器学习和集成机器学习。遗传机器学习那么因为理论和技术上进展缓慢而让位给增强机器学习。分析机器学习那么由于至今未能找到理论根底，以及一些当前在理论与技术上暂时无法克服的困难，已根本处于停滞状态。本文在简略介绍符号机器学习、集成机器学习、增强机器学习的根底上，重点介绍统计机器学习。符号机器学习最早的符号机器学习源于1959年Solomonoff关于文法归纳的研究，给定一组语句实例，求出有关文法。传统意义下，这类机器学习也以泛化能力作为主要指标。然而事实上，这类建模方法不建立在统计根底上，不具备泛化能力。1967年，Gold证明了这类学习在理论上存在不可逾越的障碍。随着海量信息的出现，人们对简约阅读的需求增长，Samuel将这类机器学习演变为一类基于符号数据集合的约简过程，将其赋予了新的含义。这类方法可以将数据集合在可解释的条件下变换为更为简洁的表示，与近几年数据挖掘的任务一致，已成为这类机器学习方法的主要应用领域。两类最重要的符号机器学习算法包括：覆盖算法与分治算法。覆盖算法有上世纪70年代末Michalski提出的AQ11算法；分治算法以Quinlan提出的决策树算法ID3，及其后继C4.5算法为代表，后者在前者的根底上嵌入了统计方法以增强其泛化能力，大多数已开发的决策树学习算法都是这两种核心算法的变体。集成机器学习集成机器学习的依据是Hebb提出的神经集合体假设，即集成多个分类器，使不同模型补充一个模型的缺乏。也就是设计一组分类器，其中每个分类器的设计更为简单，而其组合可以获得与单个分类器相同或者更好的泛化能力；另外，对于大多数情况，样本集合很难满足同分布的一致性条件，可以考虑设计多个分类器作为单个分类器的补充，增加其泛化能力。1960年Widrow提出Madline可以视为集成机器学习的最早雏形，1984年Valiant提出PAC模型〔Probablyapproximatelycorrectmodel〕，1990年Schapire提出了弱学习定理，1995年Freund和Schapire提出了AdaBoost算法，在上述研究成果的根底上，逐渐形成了泛化理论。增强机器学习增强机器学习(reinforcementlearning)的本质是对变化的环境相适应。最早的思想表达在1948年Wiener著作的“控制论”中，逐渐开展成一类重要的研究课题——自适应控制。将自适应控制的原理应用于机器学习领域就是：设计一组规那么，使用这组规那么求解问题，如果能够解决当前环境所提出的问题，支持获得这个解答的所有规那么就被增强，否那么被减弱。这个过程在分类器系统中称为桶队算法。如果所有规那么均不能解决环境所提出的问题，就使用遗传算法进行学习，产生新的规那么，直到可以适应环境。也就是说，其规那么集是动态变化的，使用遗传算法求解问题的同时改变规那么集。目前，这个研究路线进展缓慢，主要是改良桶队算法中利益均分的策略。如果将这种利益变换为对状态的评价，这个问题那么变换为一个Markov过程。20世纪90年代初，Sutton将这类机器学习建立在Markov过程上，称为增强机器学习方法。理论根底历史上，机器学习根本是在经验范畴内进行研究的，随意性非常大。Internet的普及带来海量数据现象，如何从大量数据中提取有用的信息和知识面临巨大的需求空间，有力地推动了机器学习研究。20世纪80年代奠定了统计学习理论、Roughset理论、适应性理论等理论根底，在机器学习的研究和应用中起着重要的指导作用。Roughset理论和统计学习理论可以在不增加计算复杂性的条件下，分别描述符号机器学习和统计机器学习〔集成机器学习可以理解为统计机器学习在技术上的变种〕。这两个理论有坚实的数学根底，因此大大减少了算法设计的随意性，并且使比拟已有的各种机器学习算法有了理论根底。增强机器学习理论研究还存在很大困难。本文重点关注以统计学习理论为根底的统计机器学习。统计机器学习获得一组问题空间的观测数据之后，如果不能或者没必要对其建立严格的物理模型，从这组数据推算问题空间的数学模型，在输入输出之间的关系上反映问题空间的实际，而不需要对问题世界做物理解释，这是“黑箱”原理。统计学习理论本质上是“黑箱”原理的延续，其中数学方法是研究的焦点。传统的统计学要求样本数据数目趋于无穷大，这实际上是一种不可到达的假设，现实世界中，可以获取的样本数目总是有限的。统计学系理论就是一种专门研究小样本情况下机器学习规律的理论。回忆2.2小节所描述的机器学习过程，其描述隐含了三个方面的内容：1、一致。问题空间W必须和样本空间Q性质相同，才可以根据Q对W进行推测和预判，表达在统计学意义上就是W中的元素满足同分布的一致性条件。2、划分。正确预判的前提是正确地划分，将Q放到n维空间，要寻找一个定义在这个空间上的决策分界面〔等价关系〕，使得问题决定的不同对象分在不相交的区域。3、泛化。判断模型M的好坏不仅仅在于对样本空间Q有好的判断效果，更重要的是要对问题空间W有尽量准确的预测效果，即好的推广能力。一般地说，机器学习的统计根底是经验风险最小化原那么〔EmpiricalRiskMinimization，ERM〕。令期望风险为：R经验风险为：R其中，xi独立同分布于概率密度函数P(x,y)。根据统计学中的大数定律，样本个数l趋于无穷大时，经验风险Rempf依概率收敛于期望风险Rf，所以传统的机器学习算法一般以经验风险Rempf最小作为目标函数。1971年，Vapnik指出经验风险Rempf的下界未必依概率收敛于期望风险Rf的下界，也就是说将Rempf作为目标函数是不合理的。Vapnik进一步证明了经验风险Rempf的下界依概率收敛于期望风险Rf的下界当且仅当经验风险Rempf其核心概念是VC维，它是描述函数集或学习机器的复杂性或学习能力的一个重要指标，在此概念根底上开展出一系列关于统计学习的一致性、收敛性、推广性能等重要结论。概括地说，统计学习理论的主要研究内容包括：统计学习过程的一致性理论学习过程收敛速度的非渐进理论控制学习过程的推广能力的理论构造学习算法的理论VC维模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开,那么称函数集能够把h个样本打散；函数集的VC维就是它能打散的最大样本数目h。假设对任意数目的样本都有函数能将它们打散，那么函数集的VC维是无穷大。有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。一致性、收敛性、推广性在学习过程的一致性、收敛性研究中，还涉及到三个重要概念：VC熵，退火的VC熵，生长函数。这里均以模式识别问题的指示函数为例进行说明，实函数集的情况是指示函数集情况的推广。设Q(z,α)，α∈⋀是一个指示函数集，考虑样本z1,z2,……VC熵：H退火的VC熵：H生长函数：G1968年，Vapnik和Chervonenkis证明了在Q(z,α)，α∈⋀可测性的一定条件下，一致双边收敛的充分必要条件是下述等式〔1〕liml→∞H∧1981年，Vapnik和Chervonenkis将该充要条件推广到有界实函数集。1989年，得到学习理论的关键定理，将ERM方法一致性的问题转化为了一致性收敛的问题。从而得出学习理论的第一个里程碑：最小化经验风险的充分条件是满足等式〔1〕。然而，这个条件并没有对收敛速度给出证明。接下来，Vapnik和Chervonenkis找到了收敛速度快的充分条件，如下式〔2〕。liml→∞Hann这一等式是学习理论的第二个里程碑：保证了收敛有快的渐近速度。至此，式1和式2对一致性以及收敛速度有了理论保证，然而这些都是和给定分布相关的。如何保证对于任意的分布，ERM原那么是一致的，且同时有快的收敛速度？下式〔3〕给出了任意分布下一致且快速收敛的充分必要条件：liml→∞G∧这就是学习理论中的第三个里程碑，从理论上证明了对任意分布ERM原那么满足一致性且能保证快速收敛的充分必要条件。值得一提的是在1968年，Vapnik和Chervonenkis发现了VC维的概念与生长函数之间的重要联系：任意生长函数要么是线性的，此时指示函数集的VC维无穷大；要么就是以一个参数为h的对数函数为上界，此时指示函数集的VC维是有限的且等于h。至此，函数集的VC维有限成了ERM原那么下满足一致性、收敛速度快，且不依赖于测度分布的充分条件。接下来，在1968，1971以及1979，1996年间，Vapnik和Chervonenkis找到了两个重要的不等式，形成了统计学习理论中关于界的理论，如下式〔4〕。Rf≤R式4中，h是学习机器函数集的VC维，l是样本数。该不等式带来的推论就是推广能力的界是可以控制的，那么，基于什么原那么可以使得所构造的算法其推广能力最正确？这是统计学习理论中的另外一个重要原那么：结构风险最小化〔StructuralRiskMinimization，SRM〕归纳原那么。结构风险最小化原那么式4说明，实际风险由两局部组成：Rempf是经验风险；Φ（hl）是置信范围，它和学习机器的VC维和样本数有关，VC维越大，那么学习机器的复杂性越高，置信范围越大，导致真实风险与经验风险之间可能的差异也越大。结构风险最小化原那么的核心是通过最小化经验风险和置信范围的和来最小化风险泛函，其本质是在对给定样本逼近的精度和逼近函数的复杂性之间取得一种折衷，如REF_Ref264975756\h图2图SEQ图\*ARABIC2结构风险最小化原那么示意在REF_Ref264975756\h图2中，随着函数子集的序号增加，经验风险的最小值减小，而置信范围却增加。SRM原那么通过选择子集S2将二者都考虑在内，选择S2使得在这个子集中最小化经验风险会得到实际风险的最好的界。至此，统计学习理论根本成熟，具备了坚实的数学根底。几点思考机器学习的前提机器学习的根本目的是让机器具备一定的智能，如何理解智能？这里，需要区分一下智慧和知识，拥有知识不等于拥有智慧。人类智慧的根底是基于规那么的知识，还是基于直接感悟真理的修养？这是几千年来没有答案的一个年轻的哲学问题。目前机器学习研究只能限定在通过明晰推导过程所能获得的知识领域。Vapnik提出在有限数量信息的前提下推导知识的根本原那么是：在解决一个给定的问题时，要设法防止把解决一个更一般的问题作为其中间步骤。这一原那么是显然的，但是遵循到什么程度并非易事。统计学理论很大程度上遵循了这一原那么，不需要建立物理模型而是直接通过数学模型寻找输入输出之间的“黑箱”关系；不需要先估计密度而是直接寻找待求的函数。那么，如果问题是“根据样本寻找规律”，这一原那么得到了很好地执行；如果问题是“根据样本寻找特定点上的取值”，那么这一过程实际上还是先转变成了一个更一般的“寻找待求函数”这一中间问题。如果不通过这一中间步骤，意味着通过“直觉”直接推导。然而，在上世纪30年代，K.Popper提出了区分真理论和假理论的准那么，一个理论可以被证实的必要条件是它存在被证伪的可能性。而通过感性的直觉方法所得出的理论“应该”是不可证伪的，也就不能称为一种科学理论。目前的机器学习问题大多转化成寻找待求函数的问题〔符号机器学习除外〕，也就是说将所有问题转化为数学问题进行推导。机器学习研究的是转化成数学问题之后的理论和算法，而第一步的物理世界到数学世界的转化是否严格可信？至此，本文梳理了机器学习的几个大前提，质疑这些前提那么可能开展出来另一片广阔的研究领域。事实上，统计学习理论就是质疑“样本数目趋于无穷大”这一前提开展起来的。1、智能研究考虑的是知识，而非智慧。如果智慧基于感悟，现有的计算机硬件根底和软件结构是否将面临挑战？生物计算机是否将成为下一代智能计算机的主体？2、知识依赖于明晰的推导过程，而非感悟。如果通过直觉推导知识，如何防止不可证伪的问题？是否可以开展另一套关于科学或者哲学的理论？3、基于数值的机器学习是将物理世界的问题转换成数学问题再进行研究，这个转换过程如何保证不丧失关键信息？是否可以开展一套理论研究转换以及其可信度保证问题？4、是否存在并不适合转换成数学问题研究的物理问题？符号机器学习是否有更广阔的开展空间？笔者认为挑战以上这些问题可能更适合东方或者中国人的思维方式，而且可以改变在西方阴影下亦步亦趋的现象。不得不成认的是，目前各种主客观环境不利于这种挑战。那么，研究人员在当前环境下的努力方向是什么？研究人员的努力方向从当前机