机器学习研究

　　　　　　V ol .21　　N o .2June 　2003收稿日期:2002212230

基金项目:国家重大基础研究项目基金支持(G 1998030508)

作者简介:王　珏(1948—),男,江苏苏州人,中国科学院自动化研究所研究员,IEEE 高级会员,《自动化学报》副主编,

博导;石纯一(1935—),男,河北山海关人,清华大学计算机科学与技术系教授,《计算机研究与发展》副主编,博导.

机器学习研究

王　珏1,石纯一2

(11中国科学院自动化研究所,北京100080;21清华大学计算机科学与技术系,北京100084)

摘　要:由于Internet 的使用,不分时间与地域地获得信息已成为现实,但是,如何有效利用这些信息,并使用这些信息提高生产率成为迫切需要解决的问题.机器学习是解决这类问题的有效方法之一.在此将对目前机器学习研究的主要趋势、理论与技术以及存在的问题,根据作者的研究经验进行综述,以便引起研究者的注意.

关键词:机器学习;统计机器学习;符号机器学习;增强机器学习

中图分类号:T P 181　　　文献标识码:A 　　　文章编号:100126600(2003)022*******

0　引言

经过10余年的努力,In ternet 已获得巨大的成功,由此,人们可以在不同时间与地域获取自己希望获得的信息.然而,有效获得信息是一回事,获得的信息是否能够有效且方便地使用则是另一回事.目前的现状是大量可以有效获得的信息,大约只有1%可以被使用,消耗了大量资源的信息不仅未能够被有效地使用,而且由于有用的信息正在更深地被掩埋在无用信息之中,变得更难以利用.花费了大量人力物力而获得信息,却无法有效使用,长此以往,这将与未获得信息无区别.如何有效利用这些被掩埋的有用信息已成为信息产业继续兴旺发展的关键.

与此有关的研究在不同的计算机分支有着不同的说法.例如,在图像处理中,它称为基于内容的检索,在文本分析中称为文本摘抄、文本检索,在数据分析中称为数据挖掘等,但是,这些任务的本质都是试图从不同媒体表示的信息中发掘出对用户有意义的知识.无论从何种角度理解和解释这个任务,建立模型与理解数据是两个必须解决的问题.由于图像与文本是非结构化或半结构化数据,直接使用这类数据建立模型存在着大量的困难,因此,一般根据用户需求(或领域知识、先验知识)进行特征抽取,以将这类非结构化或半结构化数据变换为结构化数据,并根据这个结构化数据建立模型.由此,机器学习就成为解决这类问题的有力工具.

在传统意义下,机器学习可以描述为:令W 是一个问题空间,(x ,y )∈W ,称为样本或对象,其中,x 是一个n 维矢量,y 是一个类别域中的一个值①.由于我们观察能力的,我们只能获得W 的一个真子集,记为Q ①　这称为有教师的机器学习(supervise learning ).如果样本不包含y ,则称为无教师的学习(unsupervise learning ).本文将不讨论无教师的学习.

　　这个描述暗示了三个方面的内容.

①一致性假设,假设样本集合Q与问题空间W之间存在某种一致的性质,如果使用统计模型,则一般假设Q与W满足同分布.这是机器学习的本质.

②划分,根据实际问题,将样本集合划分为不相交的区域(等价类).这是模型对样本集合适用能力的描述,是机器学习必须(力求)满足的必要条件.

③泛化能力,从样本集合建立的模型必须是对问题空间的描述,这样,依据样本集合获得对问题空间具有最大泛化能力的模型成为机器学习的主要任务.

一般地说,机器学习采用数值建模的方法,这个方法被W iener归纳为“黑箱”原理,具体地说,所建立模型的对问题空间的检验,只与其输入输出一致,而模型本身对问题空间所观察的实际世界没有解释.这样,建模过程可以描述如下:对给定问题空间中的一个子集,将其理解为一个函数y=f(x).令f′是一个数学基函数,建模任务就是根据一个算法,从f′获得f,使得在样本集合中的所有样本满足给定的目标函数,并使得问题空间中的非样本满足一定的正确率.这个方法已被机器学习广泛采用,例如,BP算法是以y=f(w1f(w2x))为基函数,通过这个算法,从给定样本集合计算出w1与w2,由此获得一个基于上述基函数的模型.

另外,机器学习的目标可以使用信息描述长度来刻画[1],这意味着,不能改变信息描述长度的机器学习算法是平凡的.同时,保持泛化能力(或保持样本集合信息不丢失)并使得对样本集合的信息描述长度最小的机器学习算法为最优.

近几年,由于DAN数据分析、金融与经济数据分析、信息安全的需求,以及各类科学与技术数据的分析,使得机器学习研究的观念发生了很大的改变,处理非线性、海量数据、提高泛化能力与直接面向用户等目标成为新的挑战性的问题.如果说处理“非线性海量数据与提高泛化能力”早在30年前就已为M insky 所认识,那么,“直接面向用户”则是近几年根据In ternet出现而应生的新任务了.这个任务是基于下述事实:大多数数据集合与问题空间不能满足一致性假设,人们一般不指望,甚至不相信从这些集合中获得对问题空间适用的模型,相反,只期望了解当前这个数据集合在认可阅读的条件下的真实反映.如果考虑这样的数据集合可能占我们可以收集到的数据集合的大多数,这类任务将是必须认真对待的问题了.这个任务将改变传统意义下“基于符号机器学习”的命运.

“基于符号机器学习”是最具人工智能色彩的机器学习研究,不幸的是,由于这类方法所建立的模型不具有统计性质,换句话说,模型是确定的,因此,如果不考虑其他统计方法的补充,单纯这类模型不具有泛化能力.根据机器学习任务的性质,这类机器学习将不具有竞争性.为此,很多研究者在这类研究的基础下,将统计方法嵌套在原有模型之中,使之具有泛化能力,例如从I D3[2]发展的C4.5[3].与基于统计机器学习相比较,这类机器学习算法的最大优点是实现方法比较简单,容易为计算机工程师所理解.这也是这类方法至今还被广泛应用的原因.然而,这也是这类方法最大的缺点,在理论上,这类方法几乎没有理论基础,工程师的随意性随处可见,经验实现远比理论分析重要.

在20世纪90年代初,与机器学习密切相关的研究方向被提出,即从数据库中的知识发现.在哲理上,可以将这类研究说明为“从数据库中发现对特定用户有趣且非平凡的知识”.这意味着,机器学习最重要的指标——泛化能力,已不是在算法设计中必须考虑的问题.我们可以进一步定义这类问题为:给定一个通过观察获得的对象集合U(样本集合),并假设U是问题空间,如果在这给定的对象集合中,存在对特定用户有意义的对象x∈U,设计的算法应该保证对象x能够显现地、与其他对象有区别地告诉用户,以引起这个用户的注意.解决这类问题的关键是算法必须能够处理海量数据(108～10),并且所获得的解答应该能够根据用户需求给出不同简洁程度的且可阅读的文本.由于这类问题无需考虑泛化,基于统计理论的“黑箱”方法受到很大的,而由于基于符号的机器学习方法是基于符号表示,这意味着,它具有语言描述基础,从而,它将从这类研究中获得新的生命力.

在不同的时期,人们对机器学习有着不同的兴奋点.19年,Carbonell发表文章[4]指出机器学习有4个研究方向:连接机器学习、基于符号的归纳机器学习、遗传机器学习与分析机器学习.十年过去了,1997年, D ietterich提出了另外4个新的研究方向:分类器的集成(En se m bles of classifiers)、海量数据的有教师学习

算法(M ethods fo r scaling up supervised learn ing algo rithm )、增强机器学习(R einforce m ent learning )与学习复杂统计模型(L earning comp lex stochastic models )[5].在理论上,我们可以将其进一步归纳为三类不同的学习理论:海量数据的符号机器学习理论、统计机器学习理论与基于适应性的机器学习理论①.

与10年前对机器学习热点相比较是有趣的,因为这恰恰反映了这10年时间中社会需求的变化与不同机器学习理论与技术进展的状况.在10年前有些热点问题已被更有效的理论与方法所代替,连接机器学习方法就是典型例子,统计机器学习理论与技术的完善,使得连接机器学习成为昨日黄花.而有些方法则因为在理论与技术上进展缓慢而退据次席,遗传机器学习就是如此.而分析机器学习则由于至今未能找到理论基础和一些当前在理论与技术上暂时无法克服的困难,已基本处于停滞状态.但是,我们必须指出,尽管这些类型已不是目前机器学习的研究热点,不等于说这些研究永远不重要,因为其中有些方法已成熟,当前的问题不再是理论与技术的研究,而是如何有效地应用.当然,其中有些类型的机器学习需要进一步完善它们的理论与技术,也许在下一个五年或十年,这种类型的研究将重新以新的形式出现,并成为热点问题.

作为一篇机器学习研究的综述,本文将讨论聚焦在当前的热点问题上,由此,我们将主要讨论下述四类机器学习的问题:(1)统计机器学习理论,(2)集成机器学习方法,(3)基于符号的归纳机器学习理论,(4)增强机器学习理论.

1　统计机器学习理论

研究统计机器学习就不能不考虑Ro senblatt 的感知机[6],应该说,如果不考虑在工程与技术上经常使用的曲线拟合的各种方法,感知机是最早的与统计机器学习理论有关的方法.尽管关于统计机器学习的理论与技术有了重要的发展,并且在形式上已不同于感知机的原始形式,但是,其思想一直延续至今.应该说,Ro senblatt 对机器学习做出了奠基性的贡献.甚至对感知机持最激烈批评态度的M insky ,在1988年重

版的他的名著“Percep tron ”的翩页上写下了这样的话语:“仅以此纪念Rosenblatt ”[7].如果考虑正是这本出

版在1969年的书,中断了感知机的研究进程,不能不说,感知机对人工智能乃至整个计算机科学的贡献是重大的.感知机所经历的风风雨雨,恰恰是人工智能坎坷发展历程的缩影.

111　感知机

感知机方法的原始动机是“人类学习的根源是神经系统”,根据神经系统的原理建立模型是解决学习的合理途径.由此,1956年,Ro senblatt 根据Ja m es 在16年提出的神经元相互连接与M cCull och 和P itts 发现神经元的“兴奋”和“抑制”工作方式为基础[8],建立一种神经网络的数学模型,并使用线性优化的方法,奠定了感知机的理论基础.

感知机提出之后,受到M insky 的严厉批评[9].这个批评主要集中在两个问题上,其一,感知机模型不能向非线性(线性不可分)问题推广,这是对算法的批评;其二,感知机是基于“黑箱”原理,学习后的模型与实际世界没有直接的对应关系,这是对模型形式的批评.以后,研究者主要是针对前者进行研究.

直到1986年,R um elhart 等人提出多层感知机[10],从而,解决了感知机向非线性扩展的问题,人们似乎看到了感知机算法解决非线性问题的曙光,但是,在1988年,M in sky 再次向这项研究发出挑战,在不作修改的情况下,重版“Percep tron ”一书,在他的长篇重版序言与跋中再次说明,多层感知机算法并没有解决他们在30年前提出的问题,因为多层感知机还是一类解决玩具世界问题的算法.不幸的是,经过10余年的研究,多层感知机的缺陷又被M in sky 言中了.随着数字网络的普遍使用,获得的数据呈指数增长,多层感知机算法越来越难以适应这种态势,研究新的替代算法成为必然.应该指出的是,尽管多层感知机的研究遇到了本质性的困难,但是,唤醒对感知机价值的重新认知,是多层感知机研究的重要贡献.

3第2期　　　　　　　　　　　　　　　　　　王　珏等:机器学习研究　　　　　　　　　　　　　　　　　　①在理论上,集成机器学习方法可以归入统计机器学习理论,但是,在技术上,这种方法具有重要的价值,因此,在本文中,我们将其

作为一种的机器学习类型进行讨论.

那么,M in sky 对机器学习的建议是什么呢?他认为,感知机算法的研究应该建立在几何上,而不是数学的其他方法上.理由是,基于几何的算法可能是将其从解决玩具世界问题推广到解决实际世界问题的关键,作者认为这个考虑是深刻的.因为直观性是基于几何的算法的最主要的特点,这意味着,我们可以通过对问题的直观描述,更深入地了解问题的内在结构,从而可以设计更有效的搜索算法,以获得解答.一般地说,有些其他数学方法具有更好的一般性,因为,它暗示了更大的搜索空间,这是这类方法设计有效算法更为困难的原因.

感知机之后,为了解决线性不可分问题,W idrow 做了一次重要的努力.1960年,他提出了M adaline 方案[11],尽管对线性不可分问题这是一个失败的努力,但是,这个方案所蕴含的思想,启示了基于符号归纳机器学习的研究,并在某种意义下是集成机器学习研究的早期雏形.

M adaline 是基于一个朴素的考虑

.既然感知机试图寻找一个连续且光滑的超平面划分样本集合,因此,对线性不可分问题是不可行的,是否可以寻找一个不光滑,甚至不连续的超平面划分样本集合呢?例如,对XOR

问题(见图1).

图1　XOR 问题

显然,图1中超平面S 是不光滑的,但是,S 却将样本集合{a ,b ,c ,d }划分为

{a ,c }与{b ,d }两部分.不幸的是,人们提出了一个疑问,这样的方法可能获得一

个平凡的解答,因为如果假设样本集合包含n 个样本,显然,有n -1个不光滑点

(或不连续)的超平面可以将其划分,具体地说,这个超平面是这个样本集合的一

个学习解答.但是,从信息描述长度的角度讲,对样本集合的信息描述长度并未

减少.这与机器学习的初衷相悖.这样,人们自然会提出另一个问题,是否存在一

个算法,保证可以从任意样本集合获得一个具有最少不光滑点(不连续点)的超

平面?M adaline 无法回答这个问题.尽管M adaline 方案在技术上是可行的,但是,

在理论上却是平凡的.事实上,M adaline 方案是一种分段线性化的思想.112　有限样本的统计理论[12]

对机器学习的研究者来说,统计机器学习理论所派生的算法SVM 似乎更有吸引力.但是,如果研究者忘记SVM 所基于的统计基础,就与V apn ik 的本意相悖了.事实上,统计机器学习理论中,有限样本的统计理论才是其精华,而基于这个理论的算法只是从这个统计理论派生的自然结果.

一般地说,机器学习的统计基础是基于经验风险最小假设[13],换句话说,对机器学习算法所建立的模型的泛化能力的估计(经验风险),是以假设的统计分布为基础的.令期望风险与经验风险分别表示为

R (f )=∫ f (x )-y P (x ,y )d x d y ,R e mp (f )=1

l 6l i =1 f (x i )-y i ,

其中x i 同分布于概率密度函数P (x ,y ).

根据统计学中的大数定律,对于学习模型f ,当样本点的个数l 趋于无穷大时,经验风险R e mp (f )依概率收敛趋于期望风险R (f ).机器学习算法一般以经验风险R e mp (f )最小作为目标函数,但是,在1971年,V apnik 指出R e mp (f )的下界未必依概率收敛于R (f )的下界,这意味着,将R e mp (f )下界作为机器学习的目标函数是不合理的.V apnik 进一步证明,R e mp (f )的下界依概率收敛于R (f )的下界当且仅当R e mp (f )依概率一致收敛于R (f )(即泛函空间的大数定律).这就是有限样本的统计理论.由于这个统计理论可以使用表述样本集合结构的V C 维来描述,这样,机器学习的目标函数就需要建立在样本集合的结构之上(在本文113节,可以看出,它可以表示为最大边缘),而不是在均方差之类的最小经验风险之上了,这是统计机器学习理论的精髓.

113　SV M

对有限样本统计理论,V apn ik 给出了其所对应的目标函数.以下不等式依概率1-Γ成立:

R (Q )≤R e mp (Q 3)+c l (P 2M 2

l og l -l og Γ),其中P 是包含所有样本的球半径,M 边缘,l 样本个数.

假设给定样本集合,所有样本可以线性分为两类.这样,P 是确定的,如果我们试图使得上式的左边部

4　　　　　　　　　　　　　　　广西师范大学学报(自然科学版)　　　　　　　　　　　　　　　第21卷

分为最小,这样,在保证R e mp (Q 3)最小的条件下,只需边缘M 最大.根据凸分析可知,线性可分为两类的样本集合,对应了两个不相交的闭凸集,这暗示,基于有限样本统计理论的目标函数是计算这两个闭凸集之间的具有最大距离的区域,称为两个闭凸集之间最大边缘.这已变换为清晰的几何问题.如图2

.

图2　两个闭凸集之间的边缘与最大边缘

从图2中可以看出,两个闭凸集之间存在着多个边缘,我们的任务是从这些边缘中计算最大的一个作为解答.这样,统计机器学习算法设计就是变换为有效地计算两个闭凸集之间的最大边缘的问题,这就是支持向量机(Suppo rt V ector M ach ine ,SVM ).这类计算存在着多种方法,大致可以分为两类:其一,L agrange 乘子法[12];其二,计算几何法[14,15].无论何种算法,最终获得在边缘上的支持向量,并使其作为判据,以求解在问题空间中非训练样本的解答.V apn ik 给出的最初算法是L agrange 乘子法,但是,由于这个算法需要进行矩阵计算,因此,无论时间与空间都不适合建立海量数据的统计模型,而几何法则是充分利用一个事实:远离边缘的样本与最大边缘的确定无关.这意味着,大量这样的样本无需参与优化计算,从而大大节省计算开销[14～16].这恰恰验证了M insky 所提倡使用几何原理设计学习算法的论断.114　核函数

如果训练样本集合是线性不可分的,样本集合将不能保证存在两个不相交的闭凸集,这样,上述方法不成立.根据泛函分析中的M ercer 定理,存在一个从样本空间到特征空间映射Υ(x ),使得在特征空间中,Υ(x )的点集可以构成两个不相交的闭凸集,且在特征空间中两个点的内积等于一个函数下对应样本空间中两个样本的内积,即

Υ(x ) Υ(y )=K (x y ).

其中K ( )称为核函数.

由于特征空间具有比样本空间大得多的维数,如果可以确定核函数,则在特征空间中样本之间的内积计算,可以变换为在样本空间中内积计算.这对计算来说是十分重要的.

这个结果似乎是激动人心的,因为线性不可分问题可以就此化为线性可分问题,由此,SVM 方法不仅对线性可分问题成立,而且对线性不可分问题同样成立.不幸的是,如何选择核函数,却是一个困难的问题,至今没有一个一般性的方法能够解决这个问题.相对于核函数选择,寻找有效的SVM 算法只能是一个技巧问题了,事实上,无论SVM 算法设计得多么精巧,其前提是核函数必须选择正确,否则由于不能保证样本集合在特征空间可以构成不相交的闭凸集,算法将不收敛.作者认为核函数选择问题充分体现了线性不可分问题的本质.

在SVM 的研究中,有一类研究是基于邻域概念的覆盖算法[17],其本质与M adaline 类似.目前,一般将其归为算法研究类,事实上,作者认为,将这类研究归入核函数选择似乎更合适,因为其本质就是一种映射,这与核函数的性质没有区别.另外,对普适核函数的研究在理论上也是有意义的[18],这类研究是借用函数的级数展开原理,由此达到通过扩维将线性不可分变为线性可分,这个方法的问题是,如何确定最小或者最合适的维数.

总之,统计机器学习理论为机器学习研究提供了一个重要的理论框架,但是,这个理论远未完成,核函数选择已成为公开的难题(open p roble m ),还需研究者对此做出艰苦的努力.也许数学家的介入是不可避

5第2期　　　　　　　　　　　　　　　　　　王　珏等:机器学习研究　　　　　　　　　　　　　　　　　　

2　集成机器学习

如果将M adaline理解为多个线性分类器,则这个模型应该是集成机器学习最早的雏形了.然而, M adaline不能回答可能导致平凡的最少分类器的数量问题,也未能回答集成多个分类器后泛化能力改变的问题.因此,未能引起研究者的进一步关注就是自然的事情了.但是,当人们仔细考察与反省解决线性不可分问题的历程时,彻底在理论上解决这个问题可能有本质性的困难,神经网络如此(非线性算法),统计机器学习理论同样如此(核函数选择),其区别仅仅在于其表现形式不同而已.这样,M adaline方案似乎应该成为人们关注的建议.目前,对这个建议关注的焦点不是试图回答最少分类器数量问题,因为这个问题与选择核函数问题一样困难,而是将注意聚焦在其泛化能力的提高上.如果一组分类器可以具有与一个单独分类器相等甚至更好的泛化能力,并且与单独分类器相比较,每个分类器的设计更为简单,这个考虑就有吸收力了.另外,由于大多数情况,样本集合在统计上不能满足一致性假设(同分布),使用多分类器作为一种补充①,从而增加其泛化能力,应该说是一种简单有效的办法.事实上,集成机器学习就是基于这个考虑.

由于集成机器学习的泛化理论与统计机器学习一致,因此,我们将在这章中主要介绍其结构与设计方法,其统计基础将仅仅列出已有的事实.

211　弱分类器

讨论机器学习的集成问题,就不能不涉及弱分类器问题,事实上,这个概念来源于V aliant在1984年提出的PA C学习理论[19].之后,Kearn s和V aliant提出了强PA C学习和弱PA C学习的概念,以及二者之间的等价性问题,通俗的说法是,弱学习算法可以提升为强学习算法[20].1990年,Schap ire针对此问题给出了构造性证明并提出集成方法和相应的Boosting算法.所谓弱分类器就是以比随机猜测略好的精度学习一

组概念的分类器,换句话说,如果一个分类器的分类正确率大于完全随机事件,

则这个分类器称为弱分类

图3　集成前后,泛化错误率之间的关系器[19～22].进而,Schap ire说明,如果集成多个这样的弱分类器,则其分类能力可以成为一个强分类器.由于这个论断不十分明显,但是,十分有趣且令人惊讶,所以我们需要进一步解释Schap ire 的论断.对于二分类问题,假设h1,h2,h3是三个弱PA C学习模型,它们的泛化错误率小于Α(Α<0.5)②,按照少数服从多数原则将它们集成后所得学习模型的泛化错误率应该小于3Α2-2Α3,如图3.

其中横坐标与纵坐标分别是弱分类器与强分类器的泛化错误率.如果考虑一个弱分类器做为强分类器,显然,因为两者的泛化错误率无区别,因此,两者泛化错误率的关系可以如图3虚线所示.三个弱分类器集成为一个强分类器之后,其与一个弱分类器泛化错误率之间的关系表示为图3的实线,这说明,上述三

个弱分类器集成之后,泛化错误率可以降低.

之后的几年,Schap ire等人针对集成机器学习(尤其是Boo sting方法)进一步开展了大量的理论研究工作,建立了Boo sting方法和统计学习理论之间的联系[23～29].

弱分类器的设计是集成机器学习的重要内容之一,与一般机器学习算法设计的区别在于弱分类器无需考虑线性不可分问题,这大大减轻了研究者面临的“快速学习算法与线性不可分算法”不可兼得的两难6　　　　　　　　　　　　　　　广西师范大学学报(自然科学版)　　　　　　　　　　　　　　　第21卷①

②Α<0.5意味着比随机猜测略好,即弱PA C学习.

其本质是在划分上使用相容关系代替等价关系.

处境.这是集成机器学习吸引大量应用研究者关注的主要原因.这样,应该指出的是,基于BP 算法的神经网络集成似乎不是一个可取的方法,因为这与集成机器学习的初衷相悖.

212　集成

集成机器学习的另一个重要机制是多个弱分类器集成的方法,以及由此对弱分类器设计需要满足的条件.尽管存在着一些弱分类器集成的方法,但是,使用且研究最多的还是Schap ire 等人提出的Boosting 算法①[23].这个算法有两种结构,如图4所示.

图4　弱学习模型集成后得到强学习模型

(a )多层,(b )单层

弱分类器集成的关键是投票,最简单的方法是“绝对多数”的方法.这个方法假设所有弱分类器具有相同的分类能力(泛化),其区别仅仅在于对问题空间中的不同子集有效.这个考虑在集成设计上是简单的,但是,由于其所基于的假设暗示,在弱分类器设计中需要满足“具有相同或近似相同分类能力”的弱分类器,这个条件很难实现,因为这意味着需要事先了解问题空间结构.而且这个要求也是不合理的,如果我们已经知道问题空间的结构,是否还需要机器学习就是一个问题了.

目前,大多数的方法是采用加权投票的方法,这是承认一个事实,所集成的弱分类器,具有不同的分类能力,在投票决定选择时,有高分类能力的弱分类器将握有更大的决定权.这个方案尽管使得确定每个弱分类器应该具有的票数带来一定的困难,但是,相比设计具有等能力弱分类器还是容易得多.这个方法一

般采用加权平均的方式,即h =6T

i =1Αi h i (x ),

其中,h 是强分类器,h i (x )是弱分类器,T 和Αi 分别是弱分类器个数和权值

.在此模型下,F reund 和Scha 2p ire 提出A da Boo st 算法,此算法可以很容易应用到实际问题当中

.1998年,Schap ire 等人从边缘出发证明了关于Boosting 方法的泛化不等式[25],与统计机器学习理论类似,在这个泛化不等式中,存在一个边缘的变量,由此,说明边缘是影响学习模型泛化性能的更本质因素,在无噪音情况下,增加边缘可以提高泛化性能.

在有噪音的情况下,问题就不这样简单了.1996年,Q uin lan 指出在有噪音干扰的情况下,Boosting 方法在增加边缘时不一定能够提高泛化性能,有时甚至使泛化性能变差(见图5),并给出实验加以证实[30].这个问题至今还没有一个确定的理论解释.

尽管集成机器学习在理论上已取得了重要的进展,并且由于弱分类器设计简单,使得这种方法有了广泛的应用前景,但是,与W idrow 的M adaline 类似,这些研究结果都是在不计较弱分类器数量的前提下的结果,如何更合理地组织弱分类器,至今没有一个令人信服的说法.另外,集成机器学习是试图解决线性不可分问题,尽管在统计意义上已说明这种方法的合理性,但是,在算法解释上似乎还未达到统计机器学习的水平.

①“Boosting ”

一词,顾名思义就是将多个弱学习模型提升为一个强学习模型.

左图为无噪音情况;中图为噪音对边缘影响;右图为噪音使得线性分类任务无法完成的情况

3　基于符号的归纳机器学习

基于符号的归纳机器学习应该源于1959年So l omonoff的工作与1967年Gold的工作[31].他们的研究是针对语言的机器学习,具体地说,就是给定一组语句实例,求出有关文法,因此,这也可以理解为Parsing 问题的逆问题.但是,这类机器学习的研究结果是令人失望的,因为在可学习问题上,Gold证明:(1)在严格意义下,只有所有实例都是正例且语言类是有限个语句组成的条件下,才是可学习的;(2)在极限意义下,只有原始递归的语言(大于1型,小于0型)才是可学习的.所谓严格意义是指:在逐一呈示正反事例的条件下,一旦学到了(即系统的判断从此与外界的事例完全相一致),系统会“知道”自己已经学到了;而所谓极限意义是指:在逐一呈示正反事例的条件下,尽管系统事实上学到了,但系统也无法判断自己是否学到了.Gold的理论揭示了这类学习在理论上不可逾越的障碍.以后,人工智能研究将问题简化为,从对象集合(样本集合)归纳一组规则集[32].由此,基于符号的归纳机器学习被赋予了新的含义,本文将讨论在这新的含义之下.

应该指出的是,在传统意义下,这类机器学习的目标与本文前几章所讨论的研究方向无任何区别,即以泛化能力作为主要指标.但是,事实上,因为这类机器学习方法不是建立在统计基础之上的①,因此,其所学的模型并不具有向非训练集合对象推广的能力.具体地说,与统计机器学习相比较,在泛化能力上,这类机器学习方法没有竞争力.那么,研究这类机器学习的目的是什么?所需解决的问题又是什么?

这类机器学习方法最重要的特点是:它可以将数据集合在可解释的条件下变换为更为简洁的表示.这与近几年为了解决数据理解而运生的数据挖掘的任务一致,已成为这类机器学习方法的主要应用领域.这类问题所面临的问题是,数据集合往往十分巨大,超过百万,甚至数亿的对象,超过千,甚至数万的属性,几百个的类别.如何约简这样规模的数据集合,使用户可以理解数据集合的内容,是这类机器学习所面临的挑战性的问题.

311　不可区分关系[33]

一般地说,基于符号的归纳机器学习(符号机器学习)是以一类特殊的等价关系来划分给定对象集合为基础的,其目标是使用最少的等价关系可以完全划分这个对象集合.因此,这类机器学习就是求出这个划分对象集合的等价关系集合.由于这类机器学习的等价关系定义在符号集合上,因此,往往使用一类特殊等价关系,称为不可区分关系.

定义在U上的等价关系a是不可区分关系.

①如果说这类机器学习方法与统计有关,则应该表现在数据的符号化(离散化)上.但是,数据的符号化与这类机器学习的算法是可

以完全分开考虑的,换句话说,它们无论在理论基础还是在实现方法上,是两件完全不同的事情.{(x,y) a(x)=a(y),x,y∈U}.

在人工智能与模式识别的研究中,一般不使用等价关系这样纯数学的语言,而是用属性这类更贴近实际问题的语言.作为机器学习的综述,本文有时使用属性代替等价关系.

在过去的这类机器学习中,最有代表性的研究是AQ11[34,35]与I D3.尽管I D3的决策树表示的本质就是对对象集合的划分,但是,在算法描述中,没有显现地使用等价关系与划分等术语[2],而AQ11的操作是定义在逻辑运算上[34],根据数理逻辑中的命题,F∧～F=□并且F∨～F=□,可以证明,在机器学习意义下,这恰恰就是一种划分.因此,这类机器学习的理论可以建立在等价关系上[36].

1982年,波兰数学家Pa w lak提出一种建立在不可区分关系上的数据分析方法[33],由于这种方法可以表示知识的不确定性,为了与当时流行的理论——Fuzzy set理论对应,Pa w lak命名这个理论为Rough set 理论,并由此建立了基于这种理论的逻辑系统.在1996年之前,Rough set理论主要集中在对这个逻辑系统性质的研究.不幸的是,1996年,旅居加拿大的华人学者姚一豫教授(Y.Y.Yao)证明,这个逻辑系统与模态逻辑中的S5公理体系等价[37],自此,基于Rough set理论中逻辑系统的研究逐年减少.另外,Rough sets 这个术语也显得不十分确切了①.

我们说,尽管Rough set理论的重要性不在其逻辑系统,但是,其对计算机科学还是有重要的贡献:这个理论使用不可区分关系规范了符号机器学习.另外,在这个理论中第一次提出了reduct,co re与边缘区域等概念,这些概念的本质是强调对信息系统的约简,这样,使得这个理论可以作为近几年兴起的“数据库知识发现”(KDD,或称为数据挖掘)研究的理论基础.

在Rough set理论的研究中,最重要的事件是1991年Skow ron提出了差别矩阵方言[38].在理论上,这是将reduct,co re与边缘区域定义在一类距离之上的方法,尽管Skow ron没有进一步研究这个方法的几何性质,但是,正是由于其所具有的几何特性,使得这个方法更便于计算.

312　对数据集合的描述

严格地说,“对数据集合的描述”不应该划归到机器学习,因为它的目标是简化给定的数据集合为用户可阅读的语言文本,即对这个数据集合的描述[39,40].但是,本文之所以将这类研究放在机器学习的研究之中,主要考虑其理论基础来自符号机器学习.

如果我们从对样本(对象)空间的划分来理解这个问题,它与以泛化为目标的机器学习的区别是:它是基于事先给定的特殊等价关系——不可区分关系,而以泛化为目标的机器学习则是需要从数据集合求出等价关系.这样,这类研究的重点是约简算法.另外,由于对给定数据集合,约简不是唯一的,而不同用户也需要从这个数据集合获得不同的解答.这是数据挖掘或从数据库中发现知识研究中最有特点,且有别于机器学习研究的任务.

简单地说,数据挖掘是从数据中发现有趣的知识.首先需要回答的问题是:什么知识是有趣的?事实上,这个问题没有一般的答案,这是一个仁者见仁智者见智的问题.在早期数据挖掘的研究中,一般是基于一个不合理的假设:对一个给定的数据集合,存在着一个最合理的解答,例如,最短信息长度的解.因此,研究是以这类一般性的目标作为算法的目标函数,这是机器学习研究习惯的延续,是数据挖掘任务不能接受的.

对数据挖掘来说,机器学习的另一个“惯性思维”也深深影响着数据挖掘的研究者.这涉及的问题是“有趣的知识躲藏在哪里”?如果沿袭机器学习的考虑,答案是躲藏在规则集合中,因为规则是数据结构中有规律的事物,因此,它们是知识,而在这个数据集合中的其他数据,只是我们观察能力的所造成的误差,因此是噪音.一般地说,这个说法是正确的.但是,这些反映数据集合规律的规则是用户感兴趣的么?例如,“鸟会飞”是对鸟的一般性描述,对大多数鸟这是有规律的,但是,如果我们从一个脊椎动物数据集合中

①Rough set理论提出之初的动机是试图将不确定知识表示作为其理论基础,但是,在这个理论的三个组成部分中,恰恰这个部分最

不重要,约简与Roughness更为重要,前者将是符号机器学习的基础,而Roughness可以成为知识粒度测量的基础.因此,这个理论的名称似乎有些疑问,甚至有对研究误导之嫌,但是,由于历史的原因,这个理论的名称已约定俗成,重新给出一个什么新的名称似乎也没有什么意义了.挖掘出这样的知识,这些知识对大多数用户来说,可能是平凡的.而在一般意义下的噪音,对实际世界是例外的对象可能更令用户感兴趣,例如,“鸵鸟是鸟,但是它不会飞”与“蝙蝠会飞,但是它不是鸟”,尽管它们对“鸟会飞”是噪音.这意味着,在数据挖掘中,有趣的知识可能躲藏在一般意义是噪音的对象中.“例外可能是比规则更有趣的知识”[41].这可能是数据挖掘与机器学习最本质的区别了.

313　Rough set理论

我们认为由于在Rough set理论中包含了reduct,co re与边缘区域等新概念,由此,它为数据挖掘研究提供了有力的工具.

在数据挖掘中的首要任务是根据用户的需求,获得给定数据集合的一个约简,由此,需要从数据集合中删除所有无关的数据.在Rough set理论中,reduct是一个特殊的概念,它是Pa w lak为了区别reducti on 而创造的一个英文词,在中文中,我们无法找到合适对应的词,只好使用不能区分其差别“约简”一词. reduct的本意是属性集合的一个子集,其中的所有属性应该满足下述条件.

Πr∈R,PO S R(D)≠PO S R-{r}(D)

其中R是一个约简,PO S是正区域.

这个公式说明,对R中的所有属性,如果删除其中一个属性,将改变正区域,即增加矛盾对象的数量.这意味着reduct是使得矛盾对象集合不改变的相对最小的属性集合,因此reduct可以作为规则集合的基本单元.

Core是另一个重要的概念.它同样是属性集合的一个子集,但是不同于reduct,对给定数据集合(严格地说,应该是信息系统或决策表),core是唯一的,并且对co re中的任一个属性,在对象集合中一定至少存在一对对象,它们之间的差别只有这个属性的值.因此,co re反映了信息系统的本质.Co re的另一个重要的性质是:如果R是给定信息系统的reduct,则对以R构成的新信息系统,R是这个新信息系统的co re.这个性质对发现例外有重要的意义.

边缘区域是Rough set理论的一个重要贡献,这个概念第一次使研究者可以研究矛盾对象的性质.在统计机器学习理论中,同样存在一个边缘概念.事实上,这两个概念在不可分意义(矛盾)上是相同的,但是,它们的结构必须使用相容关系描述,这为研究这个问题带来困难.有趣的是,在约简意义下,它们有较好的性质,对数据挖掘来说,这似乎已足够了.

总之,Rough set理论为数据挖掘的研究提供了一个理论框架,包括关联规则等研究同样可以纳入这个框架,只要在信息系统中根据需求(或领域知识)确定不同的决策属性即可.

4　增强机器学习

增强机器学习(reinforce m en t learn ing)的本质是对变化的环境的适应[42].应该说,这是一种“古老”的机器学习思想.在1948年,W iener的著作“控制论”中,就讨论了这个问题[43],而在以后的控制理论的研究中,这发展成为重要的研究课题——自适应控制[44,45].由于控制理论研究这个问题的焦点在于控制品质,且其使用的数学工具是微分方程,因此,对非线性问题,使用计算机进行数值求解存在着本质性的困难.这是这类机器学习长期未得到计算机科学家注意的原因.

直到20世纪70年代,Holland在讨论进化计算时,需要考虑控制物种群体的染色体数量,以便淘汰对变化环境不适应的个体,为此,提出使用桶队算法解决这个问题[46].桶队算法在Holland提出的分类器系统中扮演着对变换环境适应的角色.

以后,在20世纪90年代初,Sutton提出将这类机器学习建立在M arkov过程上,并称其为增强机器学习方法[47].这个方法是根据环境变化对系统的刺激,并作为系统输入,然后,利用基于统计的方法优化转移概率,并使系统适应新的环境.

一般地说,增强机器学习应该属于无教师学习,但是,如果考虑环境就是教师,这类机器学习也可以认为是一类特殊有教师的机器学习,与一般有教师机器学习的区别在于:教师是环境,且是变化的环境.这意味着,不像传统意义下的有教师学习,教师教授的知识不是事先给定的,而是采用更灵活方法,在问题求解的过程中获得的.

411　分类器系统

分类器系统的原理是:在分类器系统中有一组规则,使用这组规则求解问题,如果它们能够解决当前的环境所提出的问题,支持获得这个解答的所有规则将被增强,否则将被减弱,这个过程,在分类器系统中称为桶队算法[48].目前最经常被使用的方法是将所获得的增强(或减弱)平均分配给贡献者.如果对所有规则均不能解决环境所提出的问题,就使用遗传算法进行学习,产生新的规则,直到可以适应环境.由于分类器系统是建立在进化的基础上,因此,它的学习过程使用遗传算法就是自然的事.

由于分类器系统以遗传算法为基础,这意味着在分类器系统中的规则集将是动态变化的,即为了对变化环境的适应,系统必须使用遗传算法在问题求解的同时改变规则集.

目前,这个研究路线进展缓慢,主要是改进桶队算法的利益均分的策略,这样,如果将这种利益变换为状态的评价,则这个问题将变换为一个M arkov过程.

412　增强机器学习

增强机器学习的算法是建立在M arkov过程上,具体地说,在问题求解时,状态的改变取决于知识网络上各个节点事先给定的转移概率,而增强机器学习则是根据基于这种转移概率的知识对变化环境的适应能力决定是否需要修改转移概率.如果需要,学习过程将修改有关的转移概率.

与基于进化计算的方法比较是有趣的.首先,根据对变化环境的适应能力改变知识,两者是相同的,换句话说,两种方法启动学习功能的条件都是由于系统已有知识不能适应当前环境.这意味着,这类机器学习是在问题求解的过程中在线执行的.这点与“提供样本或领域知识”的传统机器学习方法有本质差别.其次,对使问题求解成功的知识增加强度或增加转移概率,对使问题求解失败的知识减小强度,在原理上,两者又是相同的,但是在增强与减小的方法上却不同.基于进化计算的方法,并没有很坚实的理论基础,尽管平均的方法在理论上也可以认为是一种基于概率的方法,但是,对其行为的进一步分析则将显得比较苍白.而基于增强机器学习的方法,由于以M arkov过程为基础,其理论相对更为坚实.

413　环境

由于增强机器学习是基于对变换环境的适应,因此,环境的性质是这类机器学习不能回避的问题.

如果说在计算机科学中从未考虑过环境,这显然不是真的.但是,如果说计算机科学将环境已作为一个必须考虑的因素,这显然也不是真的.事实上,计算机科学对环境的考虑,只是计算机需要与外部世界交换指令信息时不得不考虑的因素,因此,其主要研究内容就是界面.

从W iener控制论的观点看,计算机科学对环境的考虑只是一种开环系统,这个观点已不能适应用户对计算机能力的需求.20世纪80年代中期开始,M IT对此作出了一系列努力:B rook s的临场人工智能[49]、M insky的M ulti2A gen ts系统(M A S)[50]以及P icard的情感计算[51].

B rook s的临场人工智能中的机器昆虫所面临的是物理环境,或者称为自然环境.这些环境对带有某些智能的实体(B rook s的机器昆虫)是僵死的,且非智能的,这些实体对这些自然环境的适应与W iener最初的动机,甚至目前控制工程所解决的问题没有本质的差别.

M in sky的M A S所面临的则是社会环境,是由一组智能实体组成的一个社会.尽管在W iener的控制论中对这样的问题也作了讨论,但是真正将这个思想应用于分析社会问题,则是20世纪七八十年代的事了,作者直到今天还不认为这方面的理论研究已取得了什么重要的结果.

P icard的情感计算,在初衷上,这个研究似乎并没有与适应性联系在一起,而只是考虑情感识别,并由此作为可穿戴计算机研究开发的基础.但是,如果考虑设计带有个性的计算系统,并将这个计算系统建立在用户的情感空间上,而不仅仅是指令空间上,则将涉及计算系统对人需求的适应,并将这种适应定义在情感空间上.

另外,对环境表示的考虑,在适应性计算中与传统控制理论与工程完全不同.在传统控制理论与工程中,环境往往使用一种数学方式来刻划,事实上,环境最真实的描述是它自身,任何使用其他工具对它的刻划都仅仅是对环境本身的一种近似,如果这种近似是由于数学工具的所造成的,这对研究或工程实现是一个悲剧,如果这种近似是由于研究者的疏忽或偏好所造成的,则这对研究或工程实现可能就是一个可变为喜剧的悲剧.目前,在适应性计算中,对环境的表示强调使用真实的直接表示,事实上,这种说法并未切中要害,其要害是相反,使用真实的直接表示的系统,是适应性必须考虑的问题.

对自然环境的直接表示是简单的,而对社会环境的直接表示则需要考虑对社会成员行为的观察,而人的环境则除了直接表示之外,几乎没有其他表示的方法,其基础与社会环境的直接表示类似.

总之,环境可以分为三种类型:自然环境、社会环境与人的环境,这三类环境具有完全不同的性质,分别研究这些环境的性质,并设计对变化环境适应的计算机制是机器学习的一项挑战性的课题.

414　对用户需求的适应——情感计算

由于In ternet的广泛使用,一类特殊的依赖适应性的研究浮现出来,这就是情感计算.其目的就是使系统适应人的变化需求(环境).

在文献[52]中,作者使用了两种完全不同场景描述情感计算的意义.现将其抄录如下:

“领导要求属下完成有关任务,有两种不同的领导方式:其一,领导直接告诉下属做什么与怎样做,即领导对下属发出一系列指令,下属的做法是严格执行领导的指令;其二,领导不知道,甚至不关心他的下属应该做什么与怎样做,但是领导能够判断下属所完成的结果是否是自己所期望的,这时,下属的做法是通过领导对结果的态度(情感)来判断自己工作正确与否,并直到领导满意为止。”

如果将这个场景中的领导与下属分别理解为用户与计算机,则对应了两种完全不同的人机交互模型.

,而后者则是对用户情感变化适应的模型.两者的区别是:前者是用户在指令空间中选择一系列指令,计算机执行指令;后者则是计算机观察用户的“情感”变化(态度),并从情感空间中学习适应这种变化的执行方式.计算系统的这两种工作方式是完全不同的,在计算机越来越普遍使用的今天,基于指令空间工作方式的传统计算系统,由于用户熟悉计算系统指令集合的困难,已成为阻碍计算机推广使用的主要障碍.事实上,在上述例子中,“领导不知道”的情景可能是大多数初学或非计算机专业用户对使用计算机时普遍存在的问题.这些用户在很多情况下,不知道让计算机干什么才能解决自己希望解决的问题,但是,他们却知道计算机给出的回答是否是自己希望得到的回答,这就需要改变计算机基于指令的工作方式变为基于情感方式.

在20世纪90年代中期,M IT的P icard提出了情感计算(A ffective Computing)的概念,尽管目前她将这个问题的研究重点落实在对情感的识别上,但是,这个思想启示我们将人机交互模型建立在情感空间上,以使计算机具有对用户情感变化的适应能力.另外,这个考虑的直接推论,就是将A gent赋予“个人”的情感,以解决那些“只可意会,不可言传”的经验性知识的学习问题.

借鉴P icard的考虑,我们认为可以将用户情感变化理解为一种特殊的由用户的情感元素集合构成的环境,由此,将人机交互的过程建立在情感空间的适应性上,而不是传统的指令空间上.这将有助于解决由于指令空间难以记忆而阻碍计算机广泛应用的问题.这是增强机器学习的一个重要应用领域.

5　总结

自从19年国际人工智能杂志出版Carbonell编辑的关于机器学习的专辑之后,10余年过去了,机器学习的研究取得了重要的进展.1997年,D ietterich试图对这方面的研究再次进行总结[5],提出了今后4个研究方向.应该说,这篇文章所提出的问题是重要的,但是,与Carbonell的分析相比较,文章过于注重经验结果,而在理论分析上缺少深度.本文并不准备对机器学习在今后的研究作全面的分析、阐述与展望,而仅仅是对过去10年中,我们认为在机器学习研究中的一些有趣的动向作一个简单的说明.

在过去10年中,由于Internet技术的普遍使用,有效使用获得的数据成为今后研究的重要课题.这个需求大大刺激了机器学习的研究,其中又以理论研究为根本,因为10年前的技术(大多数算法没有理论基础)已难满足当今对海量数据、泛化能力以及各种类型的数据(包括各种媒体数据、时序数据)分析的需求,这些需求需要创建新的理论并发展新的技术.统计学习理论、Rough set理论、适应性理论等这些在20世纪80年代奠定的理论,将在今后的研究与应用中起着重要的指导作用.

在历史上,机器学习基本上是在经验范畴内进行研究的,随意性是相当严重的.其一,机器学习往往受

启于某个自然科学的原理,特别是认知心理学的原理,认知心理学研究的那种随意性也带入了机器学习的研究之中;其二,对学习解的选择涉及搜索策略,使用什么样的搜索策略往往没有一般的原则可循;其三,对学习结果的评价没有可以描述的标准,因此,对不同学习算法难以比较它们的优劣.这种现状是不能接受的,自20世纪90年代以来,一些数学家试图改变这种状况,其中Rough set 理论与统计机器学习理论是典型例子.这两个理论可以在不增加计算复杂性的条件下,分别描述上述符号机器学习与统计机器学习两种机器学习已有的主要算法.由于这两个理论有坚实的数学基础,因此大大减少了算法设计的随意性,并且使比较已有的各种机器学习算法有了理论基础.

另外,非线性海量数据(至少107～8数量级)分析与处理的需求是这类基础研究的重要推动力,无论是Rough set 理论还是统计机器学习理论,其主要着眼点均是解决非线性海量数据所面临的问题,这是当前实际需求所决定的.

事实上,本文只考虑了三类机器学习理论的研究现状,因为集成机器学习应该理解为一类统计机器学习在技术上的变种.目前,在理论研究上还不成功的是适应性机器学习,在这方面,我们还未看到类似统计机器学习理论与Rough set 理论那样的理论结果.其主要困难具有根本性,即在计算意义上表示时间变量,这是一个十分困难的问题.目前解决的方法是,将时间变量变换为有序状态或有序事件,然后使用有的搜索技术解决这个问题.作者还不能判断这是否是最好的方法,至少与时序分析方法的比较也许是必要的.

尽管统计机器学习理论与Rough set 理论获得了成功,但是,大量的理论问题尚未解决,这需要更深的数学知识.数学已成为计算机科学家与工程师的拦路虎,作者认为,在今后的几年内,计算机科学可能将进入理论积累时期,以为下一阶段的信息业的发展奠定必要的理论基础.为了避免在下一轮的竞争中被淘汰,补充数学知识已成为计算机科学家与工程师的当务之急.

必须说明的是,我们并未企图将这个研究报告作为一份对机器学习研究全面的分析与综述,只是借此文来阐述作者强调机器学习理论的重要性.因此,这只是对当前这个问题的理论研究的热点作一个有选择的提纲式的描述并提出我们的理解与认识,因此,遗漏大量机器学习技术研究与有关应用研究的进展就在所难免了.

在文章组织上,我们更强调一些重要研究的思想与内涵,为了使读者能够更清楚地了解问题的本质,在有些地方,我们对文献的内容作了简单的介绍,但是由于篇幅的,这种介绍不得不使用一些不十分容易理解的术语,这样,这些介绍也许对某些读者是“画蛇添足”,而对另一些读者则是“适得其反”.

致谢:本文作者之一的学生王家琦为这篇综述收集了大量的材料,并与作者进行了有趣的讨论,作者对他的帮助表示感谢.

参　考　文　献:

[1]　R issanen J .M odeling by shortest data descri p ti on [J ].A utom atica ,1978,14:465—471.

[2]　Q uinlan J .Inducti on of decisi on trees [J ].M ach ine L earning ,1986,1(1):81—106.

[3]　Q uinlan J .I mp roved use of continuous attributes in C 4.5[J ].Journal of A rtificail Intelligence R esearch ,1996,4:77—90.

[4]　Carbonell J .Introducti on :Paradigm s for m ach ine learning [J ].A rtificail Intelligence ,19,40(1):1—9.

[5]　D ietterich T .M ach ine learning research :Four current directi ons (F inal draft )[J ].A IM agazine ,1997,18(4):97—136.

[6]　Rosenblatt F .T he percep tron :A perceiving and recognizing autom aton (T echnical report 85246021)[R ].Ithaca N Y :

Cornell A eronauticalL aboratory ,1957.

[7]　M insky M ,Parpert S .Percep tron (Expanded editi on 1988)[M ].Cam bridge ,M A :M IT P ress ,1988.

[8]　M cCull och W ,P itts W .A l ogical calculus of the ideas i m m anent in nervous activity [J ].Bulletin of M athe m atical

B i ophysics ,1943,5(1):115—133.

[9]　M insky M ,Parpert S .Percep tron [M ].Cam bridge ,M A :M IT P ress ,1969.

[10]　R um elhart D E ,M cC lelland J L .Parallel distributed p rocessing [M ].Cam bridge ,M A :M IT P ress ,1986.

[11]　W idrow B ,HoffM .A dap tive s w itch ing circuits [A ].I R E W ESCON conventi on record (Part 4)[C ].N e w York :Institute

31第2期　　　　　　　　　　　　　　　　　　王　珏等:机器学习研究　　　　　　　　　　　　　　　　　　

of R adi o Engineers,1960.96—104.

[12]　V apnik V.T he nature of statistical learning theory[M].N e w York:Sp ringer2V erlag,1995.

[13]　D uda R,H art P.Pattern classificati on and scene analysis[M].Hoboken,N J:John W iley&Sons,1973.

[14]　P latt J.Fast training of support vector m ach ines using sequential m ini m al op ti m izati on[A].Scholkopf B,Burges C,

S mola A.A dvances in kernel m ethods2support vector learning[C].Cam bridge,M A:M IT P ress,1999.185—208. [15]　Keerth i S,Shevade S,Bhattacharyya C.A fast iterative nearest point algorithm for support vector m ach ine classifier

design[J].IEEE T ransacti ons on N eural N etwork s,2000,11(1):124—136.

[16]　W ang J iaqi,T ao Q ing,W ang Jue.Kernel p rojecti on algorithm for large2scale S VM p roble m s[J].Journal of Computer

Science and T echnol ogy,2002,17(5):556—5.

[17]　Zhang L,Zhang B.A geom etrical rep resentati on of M cCull och2p itts neural model and its app licati ons[J].IEEE

T ransacti ons on N eural N etwork s,1999,10(4):925—929.

[18]　Steinw art I.O n the influence of the kernel on consistency of support vector m ach ine[J].Journal of M ach ine L earning

R esearch,2001,2:67—93.

[19]　V aliant L.A theory of learnability[J].Comm unicati on of the A C M,1984,27:1134——1142.

[20]　KearnsM,V ahant L.L earning boolean for m ulae or finite autom ata is as hard as factoring(T echnical report TR214288)

[R].Cam bridge,M A:H arvard U niversity A iken Computati on L ab,1988.

[21]　B lum er A,Eh renfeuch t A,H aussler D,et al.L earnability and the vapnik2chervonenk is di m ensi on[J].Journal of the

A C M,19,36(4):925—965.

[22]　KearnsM,V azirani U.A n introducti on to computati onal learning theory[M].Cam bridge,M A:M IT P ress,1994.

[23]　Schap ire R.T he strength of w eak learnability[J].M ach ine L earning,1990,5(2):197—227.

[24]　F reund Y,Schap ire R.A decisi on2theoretic generalizati on of on2line learning and an app licati on to boosting[J].Journal

of Computer and Syste m Sciences,1997,55(1):119—139.

[25]　Schap ire R,F reund Y,Bartlett Y,et al.Boosting the m argin:A ne w exp lanati on for the effectiveness of voting m ethods

[J].T he A nnals of Statistics,1998,26(5):1651—1686.

[26]　F reund Y,Schap ire R.A short introducti on of boosting[J].Journal of Japanese Society for A rtificial Intelligence,1999,

14(5):771—780.

[27]　R atsch G,O noda T,M uller K.Soft m argins for adaBoost[J].M ach ine L earning,2001,42(3):287—320.

[28]　R atsch G,W ar m uth M.M arginal boosting(N euroCOL T2technical report N C2TR2012097)[R].L ondon:Royal

Holl ow ay College,2001.

[29]　R atsch G.Robust boosting via convex op ti m izati on:T heory and app licati ons[D].Potsdam:U niversity of Potsdam,

2002.

[30]　Q uinlan J.Boosting first2order learning[A].A rikaw a S,Shar m a A.P roceedings of the7th internati onal work shop on

algorithm ic learning theory[C].Berlin:Sp ringer,1996,1160:143—155.

[31]　Gold M.L anguage identificati on in the li m it[J].Infor m ati on and Control,1967,10(5):447—474.

[32]　Sam uelL.Som e studies in m ach ine learning using the gam e of checkers [J].I BM Journal R esearch and D evel opm ent,

1967,11(4):601—618.

[33]　Paw lak Z.Rough set—theoretical as pects of reas oning about data[M].Boston,M A:K luw er A cade m ic Publishers,1991.

[34]　M ichalsk i R S,Ch ilausky R L.L earning by being told and learning from examp les:A n experi m ental comparis on of two

m ethods of know ledge acquisiti on in context of devel op ing on expert syste m for s oybean disease diagnosis[J].

Internati onal Journal of Policy A nalysis and Infor m ati on Syste m s,1980,4(2):125—160.

[35]　Hong J,U nrik C.T he extensi on m atrix app roach to attribute2based learning[A].B rartko I,L avrac N.P rogress in

m ach ine learning[C].W il m sl ow:S IG M A P ress,1987.

[36]　W ang Jue,Cui J ia,Zhao Kai.Investigati on on AQ11,I D3and the p rinci p le of discernibility m atrix[J].Journal of

Computer Science and T echnol ogy,2001,16(1):1—12.

[37]　Yao Y,L in T.Generalizati on of rough sets using model l ogics[J].Intelligent A utom ati on and Soft Computing,1996,2

(2):103—120.

[38]　Skow ron A,R auszer C.T he discernibility m atrices and functi ons in infor m ati on syste m s[A].Sl ow insk i R.Intelligent

decisi on support—handbook of app licati ons and advances of the rough sets theory[C].Dordrech t:K luw er A cade m ic

Publishers ,1992.331—362.

[39]　H an J ,Kam ber M .D ata m ining :Concep ts and techniques [M ].San M ateo :M organ Kauf m ann Publishers ,2000.

[40]　郭　萌,王　珏.数据挖掘与数据库知识发现:综述[J ].模式识别与人工智能,1998,11(3):292—299.

[41]　Zhou Yu 2jian ,W ang Jue .R ule +excep ti on modeling based on rough set theory [A ].Polkow sk i L ,Skow ron A .Rough

sets and current trends in computing [C ].Berlin :Sp ringer ,1998.529—536.

[42]　Kaelbling L ,L ittm an M ,M oore A .R einforce m ent learning :A survey [J ].Journal of A rtificail Intelligence R esearch ,

1996,4:237—285.

[43]　W iener N .控制论(中译本)[M ].北京:科学出版社,1962.

[44]　A rbib M .B rains m ach ines and m athe m atics [M ].N e w York :M cGraw H ill companies ,19.

[45]　A shby W .D esign for a brain the origin of adap tive behavi or [M ].L ondon :Chapm an &H all ,1950.

[46]　Holland J .A dap tati on in natural and artificial syste m s [M ].A nn A rbor :U niversity of M ich igan P ress ,1975.

[47]　Sutton R ,Barto A .R einforce m ent learning :A n introducti on [M ].Cam bridge ,M A :M IT P ress ,1998.

[48]　Goldberg D .Genetic algorithm s in search op ti m azati on and m ach ine learning [M ].R eading ,M A :A ddis on 2W esley

Publish ing Company ,19.

[49]　B rook s R .Intelligence w ithout reas on [A ].John M ,R ay R .P roceedings of the 12th internati onal j oint conference on

artificail intelligence [C ].San M ateo :M organ Kauf m ann Publishers ,1991.569—595.

[50]　M insky M .T he s ociety of m ind [M ].N e w York :Si m on &Schuster ,1986.

[51]　P icard R W .A ffective computing (T echnical report 321)[R ].Cam bridge ,M A :M IT M edia L aboratory ,1995.

[52]　赵　凯,王　珏.适应性计算[J ].模式识别与人工智能,2002,13(4):407—414.

I NV EST IGA T I ON S ON M A CH I N E L EA RN I N G

WANG Jue 1,SH I Chun -y i

2(11Institute of A utom ati on ,Ch inese A cade m y of Sciences ,Beijing 100080,Ch ina ;

21D epartm ent of Computer Science and T echnol ogy ,T singhua U niversity ,Beijing 100084,Ch ina )

Abstract :A s In ternet is w idely used ,hum an beings can obtain a l o t of infor m ati on convenien tly .How ever ,how to use these infor m ati on effectively and efficien tly ?M ach ine learn ing is just one of the i m portan t w ays to s olve th is p roble m .T h is paper in troduces s om e theo ries and future work in the field of m ach ine learning in o rder to m ake mo re peop le pay attenti on to it .

Key words :m ach ine learning ;statistical m ach ine learning ;sym bo lic m ach ine learn ing ;reinforce m en t m ach ine learn ing

(责任编辑　李小玲)5

1第2期　　　　　　　　　　　　　　　　　　王　珏等:机器学习研究