机器学习综述

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