机器学习综述.docx

精品文档，仅供学习与交流，如有侵权请联系网站删除机器学习综述曹晓敏摘要：机器学习是计算机领域最活跃，最有潜力的方向之一。本文概述了机器学习当前研究的几个方向：符号机器学习、集成机器学习、增强机器学习、统计机器学习，梳理了各自的理论基础。在此基础上，以统计机器学习为重点，就其一致性、收敛性、推广性以及构造算法的原则四个核心方面进行了综述，最后提出几点思考和建议。1 引言计算机相比人脑而言在存储、计算方面具有无与伦比的优势，然而，其是否可以具备一定智能，一直以来是科学家们、科幻小说家们致力研究、探索和想象的一片非常广阔的领域。计算机智能化的起步阶段包含两方面工作：一方面是将人类已有的知识或经验“教”会计算机，从而使计算机成为某个领域的专家，其焦点在于知识库和推理机两方面，已经有比较成功的案例；另一方面是从大量的数据、现象中，学习产生新的知识或经验，这就是机器学习过程。后者比前者难，前者发展到一定程度会面临同样的问题。目前，机器学习已经成为计算机领域最活跃，最有潜力的研究方向之一，受到了广泛的关注。2 机器学习概述机器学习的经典定义是1997年Tom M. Mitchell在“Machine Learning”一书中提出的“计算机利用经验改善系统自身性能的行为。”这是一个相当宽泛的说明，将“机器”限定在“计算机”，而对学习的定义则过于宽泛以致不便理解。人们通常所说的“学习”是指通过对已知事实的分析、归纳、演绎，形成新的知识，其目的在于对未知的事实能做出比较符合实际的判断、指导和预测。其中有四个关键要素：已知事实、学习方法、新的知识、预判未来。其关系如图 1所示。得到知识已知事实新的事实学习方法指导未来图 1 学习过程对应于图 1，在机器学习领域，已知事实对应于“样本空间”，需要预判的新的事实对应于“问题空间”，所得到的知识对应于“构建的模型”。由此，机器学习可以描述为3：令W是问题空间，(x ，y )W称为样本，其中，x是一个n维矢量，y是类别域中的一个值。由于观察能力的限制，我们只能获得W的一个真子集，记为QW，称为样本集合。根据Q建立模型M，并期望M对W中的所有样本预测的正确率大于一个给定的常数。M对W的预测正确率，称为M对W的泛化能力或推广能力。机器学习的本质和目的就是要使得M尽可能接近真实，也就是其泛化（推广）能力尽可能强。然而，机器学习面临的第一个问题就是其问题空间如何表示？即数据描述问题。对于计算机而言，最本质的特征是量化表示以及对数值的处理；对于人类而言，其思考、表达的过程往往借助于语言或图像，而不是数值。由此，诞生了两类不同方向的机器学习领域：基于符号的机器学习，基于数值的机器学习。1989年，Carbonell指出机器学习有4个研究方向：符号机器学习、连接机器学习、遗传机器学习与分析机器学习。十年过去后，1999年，Dietterich提出了另外4个新的研究方向：符号机器学习、统计机器学习、集成机器学习、增强机器学习。其关系如表1所示4。表 1 机器学习研究方向变迁Carbonell，1989Dietterich，1999注解符号机器学习符号机器学习保留：发生本质变化，转变成符号数据分析连接机器学习统计机器学习分为：基于Barlow提出的功能单细胞假设为依据集成机器学习分为：基于Hebb提出的神经集合体假设为依据遗传机器学习增强机器学习扩展：强调反馈的作用，以及动态规划的解决方案分析机器学习放弃：问题过于复杂其中，符号机器学习方法最初由于其建立的模型是确定的，不具备泛化能力而被认为不具备竞争能力，然而随着海量信息的出现以及对简洁阅读的要求，符号机器学习重新获得生命力。随着统计机器学习理论和技术的完善，连接机器学习渐渐演变为统计机器学习和集成机器学习。遗传机器学习则因为理论和技术上进展缓慢而让位给增强机器学习。分析机器学习则由于至今未能找到理论基础，以及一些当前在理论与技术上暂时无法克服的困难，已基本处于停滞状态。本文在简略介绍符号机器学习、集成机器学习、增强机器学习的基础上，重点介绍统计机器学习。2.1 符号机器学习最早的符号机器学习源于1959年Solomonoff关于文法归纳的研究，给定一组语句实例，求出有关文法。传统意义下，这类机器学习也以泛化能力作为主要指标。然而事实上，这类建模方法不建立在统计基础上，不具备泛化能力。1967年，Gold证明了这类学习在理论上存在不可逾越的障碍。随着海量信息的出现，人们对简约阅读的需求增长，Samuel将这类机器学习演变为一类基于符号数据集合的约简过程，将其赋予了新的含义。这类方法可以将数据集合在可解释的条件下变换为更为简洁的表示，与近几年数据挖掘的任务一致，已成为这类机器学习方法的主要应用领域。两类最重要的符号机器学习算法包括：覆盖算法与分治算法。覆盖算法有上世纪70年代末Michalski提出的AQ11算法；分治算法以Quinlan提出的决策树算法ID3，及其后继C4.5算法为代表，后者在前者的基础上嵌入了统计方法以增强其泛化能力，大多数已开发的决策树学习算法都是这两种核心算法的变体。2.2 集成机器学习集成机器学习的依据是Hebb提出的神经集合体假设，即集成多个分类器，使不同模型补充一个模型的不足。也就是设计一组分类器，其中每个分类器的设计更为简单，而其组合可以获得与单个分类器相同或者更好的泛化能力；另外，对于大多数情况，样本集合很难满足同分布的一致性条件，可以考虑设计多个分类器作为单个分类器的补充，增加其泛化能力。1960年Widrow提出Madline可以视为集成机器学习的最早雏形，1984年Valiant提出PAC模型（Probably approximately correct model），1990年Schapire提出了弱学习定理，1995年Freund和Schapire提出了AdaBoost算法，在上述研究成果的基础上，逐渐形成了泛化理论。2.3 增强机器学习增强机器学习(reinforcement learning)的本质是对变化的环境相适应。最早的思想体现在1948年Wiener著作的“控制论”中，逐渐发展成一类重要的研究课题自适应控制。将自适应控制的原理应用于机器学习领域就是：设计一组规则，使用这组规则求解问题，如果能够解决当前环境所提出的问题，支持获得这个解答的所有规则就被增强，否则被减弱。这个过程在分类器系统中称为桶队算法。如果所有规则均不能解决环境所提出的问题，就使用遗传算法进行学习，产生新的规则，直到可以适应环境。也就是说，其规则集是动态变化的，使用遗传算法求解问题的同时改变规则集。目前，这个研究路线进展缓慢，主要是改进桶队算法中利益均分的策略。如果将这种利益变换为对状态的评价，这个问题则变换为一个Markov过程。20世纪90年代初，Sutton将这类机器学习建立在Markov过程上，称为增强机器学习方法。2.4 理论基础历史上，机器学习基本是在经验范畴内进行研究的，随意性非常大。Internet的普及带来海量数据现象，如何从大量数据中提取有用的信息和知识面临巨大的需求空间，有力地推动了机器学习研究。20世纪80年代奠定了统计学习理论、Rough set理论、适应性理论等理论基础，在机器学习的研究和应用中起着重要的指导作用。 Rough set理论和统计学习理论可以在不增加计算复杂性的条件下，分别描述符号机器学习和统计机器学习（集成机器学习可以理解为统计机器学习在技术上的变种）。这两个理论有坚实的数学基础，因此大大减少了算法设计的随意性，并且使比较已有的各种机器学习算法有了理论基础。增强机器学习理论研究还存在很大困难。本文重点关注以统计学习理论为基础的统计机器学习。3 统计机器学习获得一组问题空间的观测数据之后，如果不能或者没必要对其建立严格的物理模型，从这组数据推算问题空间的数学模型，在输入输出之间的关系上反映问题空间的实际，而不需要对问题世界做物理解释，这是“黑箱”原理。统计学习理论本质上是“黑箱”原理的延续，其中数学方法是研究的焦点。传统的统计学要求样本数据数目趋于无穷大，这实际上是一种不可达到的假设，现实世界中，可以获取的样本数目总是有限的。统计学系理论就是一种专门研究小样本情况下机器学习规律的理论。回顾2.2小节所描述的机器学习过程，其描述隐含了三个方面的内容：1、一致。问题空间W必须和样本空间Q性质相同，才可以根据Q对W进行推测和预判，体现在统计学意义上就是W中的元素满足同分布的一致性条件。2、划分。正确预判的前提是正确地划分，将Q放到n维空间，要寻找一个定义在这个空间上的决策分界面（等价关系），使得问题决定的不同对象分在不相交的区域。3、泛化。判断模型M的好坏不仅仅在于对样本空间Q有好的判断效果，更重要的是要对问题空间W有尽量准确的预测效果，即好的推广能力。一般地说，机器学习的统计基础是经验风险最小化原则（Empirical Risk Minimization，ERM）。令期望风险为：Rf=fx-yPx,ydxdy经验风险为：Rempf= 1li=1lfxi-y其中，xi独立同分布于概率密度函数P(x,y)。根据统计学中的大数定律，样本个数l趋于无穷大时，经验风险Rempf依概率收敛于期望风险Rf，所以传统的机器学习算法一般以经验风险Rempf最小作为目标函数。1971年，Vapnik指出经验风险Rempf的下界未必依概率收敛于期望风险Rf的下界，也就是说将Rempf作为目标函数是不合理的。Vapnik进一步证明了经验风险Rempf的下界依概率收敛于期望风险Rf的下界当且仅当经验风险Rempf依概率一致收敛于期望风险Rf（即泛函空间的大数定律）。这就是有限样本的统计理论。这个统计理论可以用函数集的VC维来描述，这样，机器学习的目标函数就建立在函数集的结构之上，而不是均方差之类的最小经验风险之上。这是统计机器学习理论的精髓。其核心概念是VC维，它是描述函数集或学习机器的复杂性或学习能力的一个重要指标，在此概念基础上发展出一系列关于统计学习的一致性、收敛性、推广性能等重要结论。概括地说，统计学习理论的主要研究内容包括：l 统计学习过程的一致性理论l 学习过程收敛速度的非渐进理论l 控制学习过程的推广能力的理论l 构造学习算法的理论3.1 VC维模式识别方法中VC 维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h 种形式分开, 则称函数集能够把h 个样本打散；函数集的VC 维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。有界实函数的VC 维可以通过用一定的阈值将它转化成指示函数来定义。3.2 一致性、收敛性、推广性在学习过程的一致性、收敛性研究中，还涉及到三个重要概念：VC熵，退火的VC熵，生长函数。这里均以模式识别问题的指示函数为例进行说明，实函数集的情况是指示函数集情况的推广。设Q(z,)， 是一个指示函数集，考虑样本z1,z2,zl，定义一个量Nz1,z2,zl，代表用指示函数集中的函数能够把给定的样本分成多少种不同的分类，即表征函数集在给定数据集上的多样性。则VC熵： HlElnNz1,z2,zl退火的VC熵： HannllnENz1,z2,zl生长函数： GllnsupNz1,z2,zl1968年，Vapnik和Chervonenkis证明了在Q(z,)，可测性的一定条件下，一致双边收敛的充分必要条件是下述等式（1）。limlHll0（1）1981年，Vapnik和Chervonenkis将该充要条件推广到有界实函数集。1989年，得到学习理论的关键定理，将ERM方法一致性的问题转化为了一致性收敛的问题。从而得出学习理论的第一个里程碑：最小化经验风险的充分条件是满足等式（1）。然而，这个条件并没有对收敛速度给出证明。接下来，Vapnik和Chervonenkis找到了收敛速度快的充分条件，如下式（2）。limlHannll0（2）这一等式是学习理论的第二个里程碑：保证了收敛有快的渐近速度。至此，式1和式2对一致性以及收敛速度有了理论保证，然而这些都是和给定分布相关的。如何保证对于任意的分布，ERM原则是一致的，且同时有快的收敛速度？下式（3）给出了任意分布下一致且快速收敛的充分必要条件：limlGll0（3）这就是学习理论中的第三个里程碑，从理论上证明了对任意分布ERM原则满足一致性且能保证快速收敛的充分必要条件。值得一提的是在1968年，Vapnik和Chervonenkis发现了VC维的概念与生长函数之间的重要联系：任意生长函数要么是线性的，此时指示函数集的VC维无穷大；要么就是以一个参数为h的对数函数为上界，此时指示函数集的VC维是有限的且等于h。至此，函数集的VC维有限成了ERM原则下满足一致性、收敛速度快，且不依赖于测度分布的充分条件。接下来，在1968，1971以及1979，1996年间，Vapnik和Chervonenkis找到了两个重要的不等式，形成了统计学习理论中关于界的理论，如下式（4）。Rf Rempf （hl）（4）式4中，h是学习机器函数集的VC维，l是样本数。该不等式带来的推论就是推广能力的界是可以控制的，那么，基于什么原则可以使得所构造的算法其推广能力最佳？这是统计学习理论中的另外一个重要原则：结构风险最小化（Structural Risk Minimization，SRM）归纳原则。3.3 结构风险最小化原则式4表明，实际风险由两部分组成：Rempf是经验风险；（hl）是置信范围，它和学习机器的VC维和样本数有关，VC维越大，则学习机器的复杂性越高，置信范围越大，导致真实风险与经验风险之间可能的差别也越大。结构风险最小化原则的核心是通过最小化经验风险和置信范围的和来最小化风险泛函，其本质是在对给定样本逼近的精度和逼近函数的复杂性之间取得一种折衷，如图 2所示。图 2 结构风险最小化原则示意在图 2中，随着函数子集的序号增加，经验风险的最小值减小，而置信范围却增加。SRM原则通过选择子集S2将二者都考虑在内，选择S2使得在这个子集中最小化经验风险会得到实际风险的最好的界。至此，统计学习理论基本成熟，具备了坚实的数学基础。4 几点思考4.1 机器学习的前提机器学习的根本目的是让机器具备一定的智能，如何理解智能？这里，需要区分一下智慧和知识，拥有知识不等于拥有智慧。人类智慧的基础是基于规则的知识，还是基于直接感悟真理的修养？这是几千年来没有答案的一个年轻的哲学问题。目前机器学习研究只能限定在通过明晰推导过程所能获得的知识领域。Vapnik提出在有限数量信息的前提下推导知识的基本原则是：在解决一个给定的问题时，要设法避免把解决一个更一般的问题作为其中间步骤。这一原则是显然的，但是遵循到什么程度并非易事。统计学理论很大程度上遵循了这一原则，不需要建立物理模型而是直接通过数学模型寻找输入输出之间的“黑箱”关系；不需要先估计密度而是直接寻找待求的函数。那么，如果问题是“根据样本寻找规律”，这一原则得到了很好地执行；如果问题是“根据样本寻找特定点上的取值”，则这一过程实际上还是先转变成了一个更一般的“寻找待求函数”这一中间问题。如果不通过这一中间步骤，意味着通过“直觉”直接推导。然而，在上世纪30年代，K.Popper提出了区分真理论和假理论的准则，一个理论可以被证实的必要条件是它存在被证伪的可能性。而通过感性的直觉方法所得出的理论“应该”是不可证伪的，也就不能称为一种科学理论。目前的机器学习问题大多转化成寻找待求函数的问题（符号机器学习除外），也就是说将所有问题转化为数学问题进行推导。机器学习研究的是转化成数学问题之后的理论和算法，而第一步的物理世界到数学世界的转化是否严格可信？至此，本文梳理了机器学习的几个大前提，质疑这些前提则可能发展出来另一片广阔的研究领域。事实上，统计学习理论就是质疑“样本数目趋于无穷大”这一前提发展起来的。1、智能研究考虑的是知识，而非智慧。如果智慧基于感悟，现有的计算机硬件基础和软件结构是否将面临挑战？生物计算机是否将成为下一代智能计算机的主体？ 2、知识依赖于明晰的推导过程，而非感悟。如果通过直觉推导知识，如何避免不可证伪的问题？是否可以发展另一套关于科学或者哲学的理论？ 3、基于数值的机器学习是将物理世界的问题转换成数学问题再进行研究，这个转换过程如何保证不丢失关键信息？是否可以发展一套理论研究转换以及其可信度保证问题？4、是否存在并不适合转换成数学问题研究的物理问题？符号机器学习是否有更广阔的发展空间？笔者认为挑战以上这些问题可能更适合东方或者中国人的思维方式，而且可以改变在西方阴影下亦步亦趋的现象。不得不承认的是，目前各种主客观环境不利于这种挑战。那么，研究人员在当前环境下的努力方向是什么？4.2 研究人员的努力方向从当前机器学习研究方向来看，主流以数学方法为主。“数学不是万能的，但是没有数学是万万不能的。8”在机器学习领域内要有所建树，一定要有深厚的数学功底，不仅仅是学习理解现有的数学知识，更重要的是能灵活运用各种原理和方法证明自己的算法或理论。因此，第一要务是强化数学功底。在此基础上，研究人员一定要明确自己的问题和目标是什么。如前所述，问题是“找到规律”还是“得到给定点上的值”，是“基础理论研究”还是“解决具体应用问题”，明确问题将会更好地引导研究思路和途径。值得强调的是，如果是解决具体的应用问题，或许理论难度和创新思想相对而言要求稍低，却更需要极其严谨细致的工作作风。从问题出发，做了什么转化，基于什么假设，采用什么算法，算法的前提是什么，是否符合真正的应用需求，局限性在哪里，最终得出什么结论，每一个步骤都需要有明晰、严谨的科学思路。另外，在解决具体问题时，一个非研究性质然而异常重要的方面是：如何用通俗易懂的语言向最终用户描述以上各个方面的内容，从而让用户接受其算法及相应的系统。这一点往往被研究人员所忽视，认为用户们根本“不懂，不识货”，事实上，能用浅显易懂的语言向外行描述清楚其问题及机理体现了更高层次的研究水平，研究人员既要能深入，也要能浅出。况且，也只有深入了，才能正确概要地浅出。参考文献：1 2 3王珏，石纯一，机器学习研究，广西师范大学学报（自然科学版）2003，21(2)：2154 王珏, 关于机器学习的讨论5 徐从富、李石坚、王金龙，机器学习研究与应用新进展6 Vapnik著，张学工译统计学习理论的本质，清华大学出版社7 Mitchell著，曾华军等译 机器学习，机械工业出版社8 王珏，机器学习研究.ppt9 SVM的一些学习总结 【精品文档】第 15 页