1 机器学习与人工智能此项研究受到国家重大基础研究项目(“973”计划)“数字内容理解的理论与方法”中“机器学习与数据描述”课题(2004CB318103)的支持。 王珏 中国科学院自动化研究所复杂系统和智能科学实验室,北京100190 1引言 “学习”是人类以及各种动物与生俱有的最基本的能力,自从人们试图在计算机上表现人类智能之日起,“学习”自然就成为研究的主要问题。人工智能(artificial intelligence)为了将这种在计算机上表现的学习与人类的学习相区别,特为其取了一个新术语——机器学习(machine learning)。加在“学习”之前的“机器”二字,也许缘于如果将“人工智能”的“人工(artificial)”平行移植到“学习”之前,成为“人工学习”,不足以表示“令计算机学习”的本意,且可能与其他什么意思相混淆,因此,将当时欧洲流行的“机器智能(machine intelligence)”的“机器”移植到这个研究领域作为代名词,更为确切。考证其由来,并没有太大的意义,我们仅仅是想告诉读者,“机器学习”这个术语的起源,是来自人工智能的研究。 而在机器学习之前再加上“统计”,变为“统计机器学习(statistical machine learning)”,则是统计学家Vapnik的建议。大多数机器学习研究者并没有关注这个变化,因为在机器学习的发展历史中(包括模式识别基础),基于统计的学习一直是其研究的一个方面,尽管在20世纪整个70年代,这类研究在人工智能领域曾经中断过,但是,它一直是模式识别基础的主要研究课题之一,特别是,自从1986年多层感知机给出了解决线性不可分问题的一个非线性算法方案之后这是对分类问题的说法,事实上,使用“回归问题”的语言可能更符合实际。但是,为了直观,本文采用了分类的说法。,这类研究重新兴起。然而,研究者使用“人工神经网络”代替“机器学习”,也许是这类问题的研究者希望与人工智能研究相区分吧! 作为计算机科学家,现在我们不得不关注“统计”二字加在机器学习之前的现实了,因为很多统计学家已经将这类研究纳入他们的研究领域,并作为主要研究课题。换句话说,目前,机器学习已经不再是人工智能,甚至计算机科学家的专有领域,它在“统计”的伞盖下,已经成为统计学领域中的重要课题,并被赋予新的含义,统计学家希望借此推动统计学的发展。 事实上,机器学习并没有一个公认的指导算法设计的定义。1983年,H.Simon给出了一个关于“学习”哲学式的说明(不是机器学习): “如果一个系统能够通过执行某种过程而改进它的性能,这就是学习”(文献[1])这个翻译引自陆汝钤教授的著作《人工智能》第五章,由于在《人工智能》这本著作中作者没有给出这个说法的原始出处,而本文作者只找到Simon在1983年的文章与这个译文相近。Simon在这篇文章中的原文是: Learning denotes changes in the system that is adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more effectively the next time. 如果陆老师的译文就是来自这篇文章,应该说,这个格言式的翻译实在是漂亮。。对算法设计,我们一般将机器学习理解为: 给定一个样本集,它是来自对实际问题世界y=F(x)(本文以后将称其为自然模型)的独立同分布(independent identical distribution,iid)采样,设计一个算法,计算一个函数y=f(x),使得它对自然模型在一定统计指标下为真,即,f(x)是自然模型的一个近似模型。这里,f(x)可以是一个规则集。 机器学习及其应 用2009 1机器学习与人工智能 机器学习的研究一直存在着两种不同的方法: 其一,以统计(度量)为基础的感知机; 其二,以划分(非度量)为基础的符号归纳。不同的问题,人们关注的侧重不同,例如,由于字符识别的成败取决于所建立的模型对新获得字符的识别精度,而不关注对模型作出识别行为的解释,这时,基于统计的方法有效; 而在分子生物学上,如果我们试图寻找致病基因,对模型行为的解释就是必需的,符号归纳也许就更为有用。这也就是为什么数据挖掘将其任务分为预测和描述两类的原因。 事实上,这两种观点的争论,恰恰反映了人工智能研究与当前“统计机器学习”研究在理念上的差异,这种差异是重要的。为了保持文章的完整性,本文只能在这一节剩余的部分阐述符号机器学习的发展历程,以后就不再有机会说明这个问题了。以下,作者流水账式地罗列这类研究的情况,顺便介绍两类研究“结怨”的由来,而其理念的差异,则留在本文以后各小节中讨论。 感知机类的机器学习源自1957年Rosenblatt的一篇文章(文献[2]),他根据神经科学的三个重要结论(文献[3])——神经元相互连接、兴奋和抑制是神经元的基本工作方式,以及改变神经元之间的连接强度来学习——设计了一个算法,其要点是: 其一,统计学基础是线性判别优化理论; 其二,算法设计是基于给定空间上的度量; 其三,算法对线性可分问题收敛。其本质是使用线性判别理论,进而将优化作为设计算法的基础。这个理念被其他研究者抓住两个话柄: 其一,给定数据集合建立的模型是自然模型的真实反映吗?模型仅在输入输出意义下对自然模型为真,而其本身对自然模型没有解释; 其二,对线性不可分问题,算法不收敛。 1969年,人工智能的奠基人Minsky等出版了《感知机》一书(文献[4]),二十年之后,人们一般将人工智能领域终止对感知机的研究归罪于这本书,然而,这本书提出了机器学习算法需要满足的一个似乎相互矛盾的原则: 其一,只能解决玩具世界问题的算法是无用的; 其二,算法复杂性应是多项式的。前者,主要考虑数据的数量和数据的性质,特别是线性不可分性质。一般地说,对线性不可分的数据在没有任何领域知识的条件下试图找到一个多项式复杂性且对自然模型具有普遍意义的算法是不可能的,因此,这本书最为重要的动机似乎是告诉研究者,领域知识是解决复杂问题学习所必需的在那个年代,当时人们的研究主要是在寻找解决复杂问题的普适的方法,例如,从自然语言样本学习文法的研究,以及基于逻辑的知识研究等。。在今天,这个思想已经几乎被所有机器学习的研究者所认识。应该指出的是,尽管Minsky关于“领域经验知识在设计机器学习算法的作用”的论述有重要的意义,但是,否定线性感知机是这本著作的重要缺憾。Minsky似乎没有注意到von Neumman在1932年建立量子力学数学基础时暗示的一个哲学道理: 如果说一个事物我们已经理解,是说我们找到了一个空间,这个事物在这个空间上可以线性表述。这就是近三十年后,Vapnik将算法设计建立在Hilbert空间的思想源泉。另外,我们猜测,Minsky在背后的另一个动机,就是试图主张和推广基于符号的人工智能体系的研究。对机器学习而言,在同一个时期,基于符号的学习机制也同时提出。 说到基于符号的学习,就不得不涉及文法归纳的研究。1959年,Solomonoff发表了一篇短文(文献[5]),他试图从一组自然语言样本归纳文法,尽管他的研究不是理论性的,但是,这个“理想”还是吸引了当时很多人的眼球。近十年过去之后,这个“理想”不幸被Gold在理论上证明是不可行的(文献[6]),Gold证明: ①在“学到”系统“知道”已“学到”的意义下,只有所有实例都是正例且语言类是有限个语句组成的条件下,才是可学习的; ②在系统“学到”,但系统无法判定自己是否“学到”的意义下,只有原始递归语言才是可学习的。这揭示了这类学习在理论上不可逾越的障碍。 Minsky在批评感知机时,使用了一个貌似简单、实质性质复杂的例子XOR,这使得人们有了“如此简单的问题,感知机却无能为力”的印象。非常有趣的是,在文法归纳中,也有一个看似简单但却实质复杂的例子,就是Chomsky给出的“A,B,C是a,b,c的丈夫”。这是使用大于1型的文法无法表述的语句。处理这类复杂例子的方法就是引入所谓“语义”,即,考虑(A,a),(B,b)和(C,c)的对应关系,由此,上述语句可以分解为: “A是a的丈夫”,“B是b的丈夫”和“C是c的丈夫”三个3型文法就可描述的语句。这个思想就是符号机器学习将问题限制在数据以“属性值对”表示的根据。 以后的符号机器学习就是以处理表述为“属性值对”数据的方法,Samuel在研究下棋学习问题时,使用了这种方法(文献[7]),但是将这个方法形成一个理论框架的是Hunt提出的CLS(Concept Learning System)(文献[8]),对这类研究做出最大贡献的是Quinlan,他所提出的ID3和C4.5,至今还是机器学习经常普遍使用的方法之一(文献[9,10])。这类方法有时也称为“非度量”方法(文献[11])。沿着这个考虑,目前最重要的发展方向是“关系学习”,其困难在于样本集不能写成给定空间上的向量形式,数据之间存在与领域有关的特定的“关系”,如何解决这类问题,尽管目前已存在大量的研究,但是,至今还没有一个对解决实际问题有本质意义的理论框架。 最后,应该指出,由于近几年所谓“非度量”方法在重采样意义下获得了统计的解释,因此,像c4.5这类算法得到研究者和应用者的喜爱。 2机器学习与人工智能的不同理念 一般地说,机器学习由于本文以后主要讨论统计机器学习,因此,只有在个别地方,为了避免混淆或为了强调“统计”,才使用“统计机器学习”,大多数情况下,就简称机器学习。研究者不十分关注算法设计所应该遵循的统计学准则和原理,他们的研究往往将问题考虑为优化问题: 给定基函数,计算特定约束下使得被选择的损失函数最小的优化解答。这样,他们需要解决的问题就是如何选定合适的基函数与损失函数,以及如何有效计算,即,发展算法才是他们的主要任务。至于统计学,机器学习关注的是对计算结果的统计解释,以及统计学对计算结果检验的指导。 机器学习基于下述统计框架: 由于观测数据(一般称为样本在统计学中是将一组观察称为样本,在机器学习和模式识别中,则是将一次观测获得数据称为样本,而将一组观察称为样本集,本文将使用后者。)不完整且含有噪音,因此,需要使用后验概率描述yj= f(xj)成立的可能性,其中{xj,yi}为一次观察的样本。设计一个损失函数,样本集的风险就等于每个样本损失和每个样本的后验概率乘积之和。计算参数,使得Bayes风险(样本集风险)最小。这就是三十余年前Duda与Hart在他们的著作《模式分类和场境分析(Pattern Classification and Scene Analysis)》中给出的框架(文献[12])。尽管机器学习近十年获得了重要的进展,但是,这个框架并没有实质地改变,特别是分类问题。 这个框架需要一个重要的假设: 样本集与自然模型同分布(来自同一个自然模型的样本趋于无穷大),以及需要每次观察的样本满足独立条件,以便使得计算多个事件的联合分布成为可能,即,独立同分布。 独立的条件可以认为是为了数学处理的方便而人为规定的条件,它可以在设计数据采样时满足。但是,同分布则是机器学习的本质。 同分布可以这样理解: 如果样本集趋于无穷大,要求样本集中的所有样本来自同一个自然模型,如果样本集是有限的,要求样本集与自然模型在统计上具有相同分布,或者训练集和测试集具有相同分布。 机器学习要求样本集与自然模型满足同分布是相当显然的,否则使用统计方法建立的模型就有“指鹿为马”的嫌疑了。但是,当样本集是有限的,如何保证它与自然模型同分布呢?考虑到当前“非可控数据涌现”的现实,这已成为机器学习面临的根本性的困难。人工智能是否能够解决或改善这种窘境?为了说明这个问题,我们需要了解机器学习与人工智能之间理念的差别与联系。 目前机器学习成为吸引众多研究者注意的原因是“泛化”,这是人工智能没有在理论上给予足够关注的问题。对统计学来说,“泛化”的要害就是“同分布”,即,如果在机器学习中考虑“泛化”,就不能回避“同分布”问题。 如果说人工智能不考虑“泛化”,大概也不是真的,开发的任何一个智能系统,其问题求解能力一定是评价这个系统的重要指标,但是,这个指标是基于领域专家对自然模型的认识程度,不是客观的自然模型,即,假设领域专家对自然模型具有深刻理解,由此,对自然模型的泛化取决于领域专家所能够提供的知识的质量而间接考虑。由此,人工智能研究的焦点变为选择最优秀的专家和收集这个专家的所有知识。 为了进一步讨论机器学习与人工智能之间的差别,我们看一个有趣的问题: 在人工智能研究中,有时也需要考虑不确定问题,但是,它没有采用统计学原理,而是发展了其他方法,以代替统计学的方法。在人工智能中描述不确定性的最著名理论是模糊集,在这个理论中,隶属度是关键,这是一个与概率“类似”的定义在[0,1]上的实数。一个自然的问题是,它与概率有何区别呢?粗略地说,概率满足排中律,但因果律破缺; 隶属度满足因果律,但排中律破缺事实上,模糊集理论的隶属度并不严格满足因果律,而仅仅是一种经验因果关系,但是,排中律破缺。我们可以粗略地设立两个口袋——“排中律破缺”和“因果律破缺”,并将不同理论方法放在这两个口袋之中,而不作进一步的细致划分。模糊集可以装入“排中律破缺”的口袋。事实上,机器学习往往采用一种逼近优化的方法,说这样的机器学习满足排中律,同样是不严格的,但是,因果律破缺。由于本文没有讨论“排中律”和“因果律”这两个概念哲学含义的动机,因此,读者不妨将这两个概念理解为作者为了划分机器学习与人工智能各种理论方法所使用的一种简单表述,以便更加显现地说明这些理论方法在理念上的差别。,由于排中律与因果律不能互导,因此,两者不同。 由于机器学习基于统计学,假设对特定自然模型具有特定分布就是自然的事情了,这样,这个分布是这个自然模型的属性,另外,研究这个自然模型的每次观察发生的原因没有意义,因为这将与泛化目标相悖,因此,因果律破缺也不奇怪。总之,机器学习属于因果律破缺范畴。应该指出,机器学习采用这种方式是为强调“泛化”而有意为之。事实上,对机器学习来说,样本数量是否趋于无穷大并不是一个本质的要点,其要点就是同分布,换句话说,样本集对自然模型是充分的。不幸的是,由于机器学习强调“对自然模型一无所知”,这样,给定样本集“充分与否”就是不能判定的。 我们来看人工智能是如何看待世界的。它采用了另外一个假设: 智能系统不一定是对自然模型的精确描述,在理想情况下,这取决于领域专家对自然模型认识的程度,即,从人工智能创立之时,就没有试图让它的研究建立在对自然模型的排中律之上,而要求满足一类领域专家特有的因果关系,严格地说是“经验因果关系或似然因果关系”,即,默认“很多事物之间存在某种程度的因果关系,但是不能证明它是否正确”。以人工智能的语言来说,就是可以使用这个知识(因果关系)推断,但是,不能证明结论对自然模型永真或永假。这个思想本质就是休谟的哲学。这样,我们可以将其粗略地划分到“排中律破缺”的口袋之中。 由于因果律的破缺,使得基于统计的方法必须满足同分布条件。对目前机器学习所面临的描述自然模型的数据而言,由于人力和物力的限制,甚至技术发展的限制,我们无法保证所获得的数据能够满足同分布条件,而由于统计学的本意,因果律又不能纳入到这个理论之中,否则将破坏这个理论的优美性和统计学的初衷,这的确是一个两难问题。对自然模型描述,人工智能是基于经验因果关系,由于排中律破缺,因此,它不必在同分布上烦恼,但是,它也将丧失对自然模型“排中”描述的权利,从而在系统“泛化”描述上遇到困难。 事实上,当我们希望获得一个对自然模型真实且可解释(知其然又知其所以然)的模型时,排中律和因果律必须同时满足,因此,统计学对因果律的破缺或人工智能对排中律的破缺,在某种程度上,是由于我们对自然模型认识的局限,而不得不采用的处理自然模型的有效方法。在某种程度上,实属无奈! 无论机器学习还是人工智能,即使最极端的研究者也不会追求满足排中律和因果律,因为我们面临的自然模型是未知的,遵循这些原则不现实(请读者进一步阅读本文第5节),但是,使用的理论与方法的倾向还是存在,而且这种倾向说明了研究者的理念(对问题的认识)。我们在这里从两个“律”说明机器学习与人工智能,主要是强调它们的差别,而不是期望研究一种满足其中一个“律”的理论和方法,因为我们最终的目的是将两者取长补短。 需要指出的是,上述关于“破缺”的讨论是对描述自然模型而言的,对排中律和因果律的不同破缺,是人工智能和机器学习理念的差别,但是,这种差别不是两者发展的结果,而是研究者有意识的选择,这暗示,这种破缺是对“确定描述自然模型”客观不可行时,一种无奈的选择。 另外,在人工智能的研究中有一个有趣现象引起我们的注意,在考虑因果关系的规则中往往附加不确定描述(也可以理解为经验或似然),尽管研究者喜欢使用纯经验的方法,例如,模糊方法,但是,有时也会毫不犹豫地使用统计方法,例如,Markov过程或Bayes网络。说这种现象有趣,是因为这些附加的不确定描述尽管使用了统计的方法,但是,它所表示的问题是否对自然模型满足排中律,却是不重要的,因为此时此刻描述不确定的“概率”,并不是这个自然模型的属性,而仅仅是为了说明当存在某个“原因”时,其发生某个结果的可能性,以便与发生的其他结果的可能性相比较,以决定将要发生的结果是什么。形式地说,这些统计数值的作用就是为了对发生的结果的可能性作一个排序。总之,这种情况下,即使使用统计的方法,其数值也不是自然模型的属性,即,排中律破缺与否并不重要!这时,统计的方法获得的“概率”仅仅是一个评价因果关系的数值,如果一个“因”存在多个“果”,这个数值就是对可能性的一个排序,以决定哪个“果”是最可能的。在某种程度上,对自然模型而言,这个方式又可以划入“排中律破缺”口袋。 在统计意义下,对因果关系的讨论,是一个十分复杂的问题,特别是它与相关关系的区别可能是机器学习研究不熟悉的,如果读者对这个问题有更多的兴趣,可以参读本书收录的由北京大学概率统计系耿直教授撰写的行文优美的论文《因果关系挖掘的统计方法》。 我们不厌其烦地说明统计机器学习和人工智能选择不同的“破缺”,主要试图说明,在某种程度上,这实在是一种人对自然的无奈。既然不能做到“知其然又知其所以然”,人们只能求其次,力求做到“知其然”,甚至“不知其然,但有效”也罢。事实上,机器学习的研究历程就是这样发展的: 当仅因果律破缺还不足以解决问题时(描述自然模型,计算复杂性),排中律同时也人为地破缺,例如,Valiant的“概率近似正确”理论就是如此。但是,人们当然不会在“无奈”之下就此止步。 3统计机器学习的特点 机器学习的最终目的是描述自然模型(泛化),由于自然模型中单一事件难以刻画自然模型的特性,只能依赖因果律破缺的统计学,以描述其整体特性,这不是一种游戏,而是描述自然模型的需要。 目前,机器学习面临的问题是: 观测次数有限但需保证精度,问题不适定但必须可计算。这些要求的本质就是计算与精度及可解释性的矛盾。这是当前机器学习面临的基本问题之一。 首先将计算复杂性作为一个必须考虑的因素,对基于“自然模型”有限次观察作统计分析的研究者是计算机学家Valiant。1984年,他发表了一篇文章(文献[13]),以计算机科学家的立场,提出计算复杂性是机器学习算法设计必须考虑的因素,即,算法的复杂性必须是多项式的。为了达到这个目的,不惜牺牲模型精度,Valiant将这个传统统计学家难以接受的理念称为“概率近似正确(probably approximately correct,PAC)”。为了描述这个理念并增加其可信程度,Valiant使用类似数学分析的εδ语言来定义这个考虑Valiant的原始定义更为严格,本文仅对Valiant思想作一个简单说明。: 假设自然模型为y=F(x),S={x,y}n是对y=F(x)的n次观察的样本集,通过复杂性为多项式的算法A,获得模型y=f(x)。考虑所有从y=F(x)可能观测的样本,对任意正数ε>0,0≤δ<1,|F(x)-f(x)|≤ε成立的概率大于1-δ。 这个思想最易受到传统统计学家的“攻击”之处是,“|F(x)-f(x)|≤ε成立的概率大于1-δ”。其关键是,为了满足计算复杂性是多项式的要求,需要付出代价,就是|F(x)-f(x)|≤ε成立的概率不是1,而是小于等于1。换句话说,对特定问题,算法设计合理,那么,问题的复杂程度将决定δ的大小,问题越复杂,δ越大。这时,严谨统计学的排中律不能完整保留!这是统计学难以容忍的。但是,这可以理解为解决精度与计算之间矛盾所不得不付出的代价。 Vapnik的研究与统计学家的研究理念有很大的区别(文献[14]),统计学家认为精确解析地估计概率密度是问题的关键,而Vapnik则认为,不能将估计概率密度这个更为困难的问题作为解决机器学习分类或回归问题的中间步骤,因此,他直接将问题变为线性判别问题其本质是放弃机器学习建立的模型对自然模型的可解释性。。事实上,这正是统计学与计算机科学之间的区别。由于计算机科学将可计算性与计算复杂性放在第一位,因此,对任一个理论或方法,首要的评价就是这个指标,当无法找到一个解决这个问题的方法时(无论是本质不可还是暂时不可),一定采用放松其他重要指标的替代方法,“与其一无所有,不如求其次”。这是统计学的传统无法接受的,但是,由于我们所面临的数据如此巨大复杂且未知,使用计算机处理这些数据成为必然,这时,统计学和计算机科学必须面对“可计算性与计算复杂性”的现实。 Vapnik研究的第一个特点是,泛化作为机器学习的核心问题,并指出,分类问题的泛化能力与两类样本之间的距离有关,这就是“边缘(margin)”问题margin,目前存在多种翻译的方法,我们将其翻译为“边缘”,有些研究者则翻译为“间隔”。。这是Vapnik对机器学习的贡献。 在说明Vapnik研究的第二个特点之前,我们需要将BP算法作为参考物。本文在引言中描述了感知机的坎坷发展历程,“坎坷”的要点就在“线性可分否”的争论上,即,是否可以突破线性判别的限制,这个争论由于1986年出现的非线性的BP算法而基本终结。BP算法采用一个非线性的形式y=f1(θ1f2(θ2x)),学习算法由此成为一个非线性优化问题(文献[15])。孤立地看BP算法,应该说是十分漂亮的,充满着智慧和技巧,但是,如果放入机器学习发展过程来看,这仅仅是一个孤立的事件,并没有对后续发展给出理论的线索。二十余年过去了,这项研究的影响远不如感知机深远。 Vapnik的第二个特点是在线性特征空间上设计算法的建议。Vapnik认为人工神经网络的贡献是回归感知机。换句话说,尽管BP算法的研究解决了困惑人们二十余年的难题,但是,其对科学的意义仅仅是使人们重新认识到感知机的重要性。Vapnik建议设计一个映射,称为核映射,将在原样本空间(一般是欧氏空间)上定义的样本集映射到特征空间,Hilbert空间,一个线性内积空间。由于在这个空间上,样本集成为线性可分,因此,可以直接使用感知机。尽管Vapnik在其著作中一再声称,这个空间可以不必显现表示,但是,从目前的研究来看,这仅仅是理论的说法,在具体实现算法时,由于我们不得不使用级数逼近核函数,因此,这个空间的基是显现表现的,也就是说,特征空间一般是清楚的。 这个建议似乎解决了线性不可分问题。事情没有这么简单,没有免费的午餐!将一个线性不可分问题映射到特征空间成为线性可分,是需要付出代价的,就是可以线性可分的特征空间的维数一般需要指数增加。考虑一个极端的例子——nXOR问题。将这个问题映射到多项式基张成的特征空间上,并规定空间各维度定义在{0,1}上,立即可以证明,nXOR问题在这个空间上线性可分维数是2n-1。进一步我们可以将特征空间的各维度定义在实数域上,可以线性划分这个问题的维数一定会减低,最小的维数是什么?这就是目前被广泛注意的核函数选择问题了。 Vapnik研究的第三个特点是,对分类问题,Vapnik建议将模型泛化能力与不同类别样本(一般是两类)之间的距离(闭凸集之间的距离)联系在一起,这为有效算法的设计奠定了基础。在算法研究上,最重要的结果是1998年,ShaweTaylor等推出的基于边缘的泛化不等式(文献[16]): err(h)≤c lR2 M2log2l-log δ 其中M称为属于不同类别数据的分界的边缘,如图1所示。 图1 根据上式,M>0,边缘不能等于零,这意味着,样本集必须是可划分的。边缘最大,误差函数最小,泛化能力最强。这样,泛化能力就可以使用样本集的边缘来刻画。由此,问题变为设计使得两个闭凸集边缘最大的算法。由于“边缘”直观地描述了通过样本集建立的模型的泛化能力,这个研究受到理论和应用研究者的偏爱,因此,Vapnik称这个时期的研究为“边缘”时期。 总之,Vapnik理论的核心是泛化,有限样本似乎并不是这个理论的本质,因为独立同分布条件也是这个理论的条件。这个理论中的另两个特点——线性空间和最大边缘对计算机科学更为重要,前者使得研究非线性算法变为寻找线性空间的问题,尽管这并不是一个轻松的任务,后者则充满了精彩的技巧,其对计算的贡献毋庸置疑。 4集群学习(ensembleEnsemble术语来自神经科学家Donald O. Hebb,他使用这个术语表述他的主张——多细胞集群学说,主张“视觉客体是由相互关联的神经元集群来表象”。神经科学领域将其翻译为“集群”。目前国内一些机器学习研究者将其翻译为“集成”。本文建议遵循神经科学的翻译,将ensemble翻译为“集群”。 learning) 自Valiant提出PAC之后,有着大量的有趣的研究,陆如钤教授在他的著作《人工智能》一书的第五部分20.4节中收集了大量研究结果(文献[17]),而与本文有关的是弱可学习。所谓弱可学习就是将在本文上节关于PAC的说明中的“|F(x)-f(x)|≤ε成立的概率大于1-δ”修改为“|F(x)-f(x)|≤ε成立的概率大于(1/2)+δ,其中0<δ≤(1/2)”。这意味着,学习成功率只需大于50%,比随即猜想稍好!这时,相对弱可学习,对PAC的原始定义可以称为强可学习。1990年,Schapire依然证明,对任一个概念,PAC弱可学习的充要条件是PAC强可学习(文献[18])。 在理论上,这是一个令人难以置信的命题,然而,Schapire使用构造性的方法证明了这个命题,这个证明方法同时暗示一个算法: 给定样本集S1,根据弱可学习的定义,从S1学习一个弱模型通过弱学习器学习到的模型,本文称为弱模型。L1,即,它的精度仅比随即猜想稍好,然后,重新构造新的样本集S2,使其包含L1不能正确学习的样本与从原样本集S1中随机采样的其他部分样本,并获得一个弱模型L2,以后,构造第三个样本集S3,包括L1和L2不能正确学习的样本与从原样本集S1中随机采样的其他样本,并获得第三个弱模型,直到所有样本可以被正确学习。最后,可以对获得的弱模型适当加权,以表示其能力,就获得了一个强模型。 对机器学习研究者,Schapire的这个命题似乎很神奇,但是,我们从常识来看这个命题,却更加自然。这个命题本质是: 一个自然模型可以从不同角度来描述(模型),其中每个角度均不能完全概括自然模型,如果所有角度构成这个自然模型的全集,并在统计意义下集群这些模型,则有可能获得对自然模型的一个较完整的描述。对给定样本集,弱模型仅是对给定样本集的一个方面的解释,收集的弱模型足以覆盖这个问题的所有描述,就可能在PAC意义下获得一个强模型,甚至对自然模型的描述,尽管不一定可解释。 弱可学习定理最重要的动机是解决复杂问题(一般是非线性问题)的计算问题,但是,统计学家则喜欢将上述研究考虑为重采样问题。 本节仅简单讨论重采样方法中的“自助法(Boostrap)”,从这个方法派生的各种机器学习方法的区别仅在于采样“重复”的策略。最简单的自助法是Bagging(Bagging Predictors)(文献[19]),其原理是从给定样本集中随机采集一个大小给定的子集,并使用一种机器学习算法学习一个弱模型,重复采样多次,学习若干模型,集群就是: 对自然模型一次观察,分别使用这些模型求解,然后投票,以少数服从多数的原则,决定其解答。另一个方法是根据“弱可学习定理”证明过程暗示的算法,称为Boosting。两个算法的区别仅在采样“重复”的策略,前者,“机械”地采集给定大小的样本集子集,而后者则要强调样本集中一定包含前一个学习器未能正确求解的样本,即,“富信息”的样本。对计算而言,相对后者,前者可能需要采样次数更多。目前,后者更被应用研究者看好,除了“富信息样本”的考虑增加了弱模型的多样性之外有相同看法的模型过多,对问题的解答往往流于形式,且对复杂问题可能变为平凡,而集群学习必须强调集群的模型是对复杂问题不同侧面的反映。,更为有趣的是,大量的经验说明,这种方法不出现“过学习(overfitting)”,尽管这个问题至今没有理想的理论解释。 集群学习有两个重要的特点: 其一,使用多个弱模型代替一个强模型,其二,决策方法是以弱模型投票,并以少数服从多数的原则决定解答。前者本节已经作了讨论,以下我们讨论后者。