Machine-Learning Research
Four Current Directions
Thomas G.Dietterich
- Machine-learning research has been making great progress in many directions. This article summarizes four of these directions and discusses some current open problems. The four directions are (1) the improvement of classification accuracy by learning ensembles of classifiers, (2) methods for scaling up supervised learning algorithms, (3) reinforcement learning, and (4) the learning of complex stochastic models.
The last five years have seen an explosion in machine-learning research. This explosion has many causes: First, separate research communities in symbolic machine learning, computation learning theory, neural networks, statistics, and pattern recognition have discovered one another and begun to work together. Second, machine-learning techniques are being applied to new kinds of problem, including knowledge discovery in databases, language processing, robot control, and combinatorial optimization, as well as to more traditional problems such as speech recognition, face recognition, handwriting recognition, medical data analysis, and game playing.
In this article, I selected four topics within machine learning where there has been a lot of recent activity. The purpose of the article is to describe the results in these areas to a broader AI audience and to sketch some of the open research problems. The topic areas are (1) ensembles of classifiers, (2) methods for scaling up supervised learning algorithms, (3) reinforcement learning, and (4) the learning of complex stochastic models.
The reader should be cautioned that this article is not a comprehensive review of each of these topics. Rather, my goal is to provide a representative sample of the research in each of these four areas. In each of the areas, there are many other papers that describe relevant work. I apologize to those authors whose work I was unable to include in the article.
Ensembles of Classifiers
The first topic concerns methods for improving accuracy in supervised learning. I begin by introducing some notation. In supervised learning, a learning program is given training examples of the form {(x1, y1),hellip;, (xm, ym)} for some unknown function y = f(x). The xi values are typically vectors of the form lt; Xi,1 ,Xi,2 ,. hellip; , Xi,ngt; whose components are discrete or real valued, such as height, weight, color, and age. These are also called the feature of Xi, I use the notation Xij to. refer to the jth feature of Xi. In some situations, I drop the i subscript when it is implied by the context.
The y values are typically drawn from a discrete set of classes {1,hellip;, k} in the case of classification or from the real line in the case of regression. In this article, I focus primarily on classification. The training examples might be corrupted by some random noise.
Given a set S of training examples, a learning algorithm outputs a classifier. The classifier is a hypothesis about the true function f. Given new x values, it predicts the corresponding y values. I denote classifiers by h1,hellip;， hi.
An ensemble of classifier is a set of classifiers whose individual decisions are combined in some way (typically by weighted or unweighted voting) to classify new examples. One of the most active areas of research in supervised learning has been the study of methods for constructing good ensembles of classifiers. The main discovery is that ensembles are often much more accurate than the individual classifiers that make them up.
An ensemble can bee more accurate than its component classifiers only if the individual classifiers disagree with one another (Hansen and Salamon 1990). To see why, imagine that we have an ensemble of three classifiers: {h1, h2, h3}, and consider a new case x. If the three classifiers are identical, then when h1(x) is wrong, h2(x) and h3(x) are also wrong. However, if the errors made by the classifiers are uncorrelated, then when h1(x) is wrong, h2(x) and h3(x) might be correct, so that a majority vote correctly classifies x. More precisely, if the error rates of L hypotheses hi are all equal to plt;L/2 and if the errors are independent, then the probability that binomial distribution where more than L/2 hypotheses are wrong. Figure 1 shows this area for a simulated ensemble of 21 hypotheses, each having an error rate of 0.3. The area under the curve for 11 or more hypotheses being simultaneously wrong is 0.026, which is much less than the error rate of the individual hypotheses.
Of course, if the individual hypotheses make uncorrelated errors at rates exceeding 0.5, then the error rate of the voted ensemble increases as a result of the voting. Hence, the key to successful ensemble methods is to construct individual classifiers with error rates below 0.5 whose errors are at least somewhat uncorrelated.
Methods for Constructing Ensembles
Many methods for constructing ensembles have been developed. Some methods are general, and they can be applied to any learning algorithm. Other methods are specific to particular algorithms. I begin by reviewing the general techniques.
Subsampling the Training Examples
The first method manipulates the training examples to generate multiple hypotheses. The learning algorithm is run several times, each time with a different subset of the training examples. This technique works especially well for unstable learning algorithms-algorithms whose output classifier undergoes major changes in response to small changes in the training data. Decision tree, neural network, and rule-learning algorithms are all unstable. Linear-regression, nearest-neighbor, and linear-threshold algorithms are generally stable.
The most straightforward way of manipulating the training set is
剩余内容已隐藏，支付完成后下载完整资料
机器学习的研究
当前的四个方向
——Thomas G.Dietterich
- 机器学习已经在许多方面取得了进步。这篇文章总结了其中的四个方面，并且讨论了当前一些公开的问题。四个方面的问题是 (1) 通过对多分类器集成的研究来提高分类的精确度。 (2)用按比例增加的方法负责研究算法 (3) 强化学习, 以及 (4) 复杂随机模型的学习。
过去五年在机器学习的研究方面已经取得了惊人的发展。导致这种发展的原因有许多：首先，基于符号机器学习的单独研究群体，计算的学习理论，神经网络，统计学 , 和模式识别都逐个被发现并且共同起作用。第二，机器学习技术正适合于解决新问题，包括数据库技术的发现、语言处理、机器人控制、和最佳化配置，还有许多传统问题比如语音识别、外观识别、笔迹识别、医学数据分析，以及游戏竞技。
在这篇文章中，我选择了四个有关机器学习的主题，近来在这些主题上都有许多探讨。写这篇文章的目的是展示机器学习在这些领域的进展以发展人工智能，和起草一些公开的研究问题。主要研究领域是(1) 多分类器集成,(2) 用按比例增加的方法负责研究算法(3)强化学习,以及(4)复杂随机模型的学习。
读者应该注意这篇文章不是各个方面的全面调查。准确地说，我的目的是为四个研究领域分别提供一个典型实例。在每一个领域，都有其他类似的研究报告。对于那些不能被我的文章吸纳的作品的作者，我深表遗憾。
多分类器集成
首要的问题是改良有监督学习的准确度与所采用的方法有关。我以引介符号为始。在有监督的学习中，一种自我学习的程序能通过{(x1, y1),hellip;, (xm, ym)}的表格数据获知未知函数y = f(x)。而数值xi是由离散型的或具有现实意义的量如高度、重量、颜色、和年龄组成的表格中的典型矢量。这些也被称为xi的特征量，我用符号Xij表示Xi的第j个特征量。有的时候，当它被语境暗示时，我把i写在X的下方。
y 数值典型地来自在分类时的一组离散的类别 {1 ，hellip;被画,k}或在退化的情况下的线性变化。在这篇文章中，我主要地把重心集中在分类。示例可能被一些随意评论破坏。
以一组学习算法输出分类器的示例S为例。其中分类器是关于待实现的功能f的一个模拟。给定一个x的值,预测对应的y的值，得到h1 ，hellip;，hi的分类器。
一个集成的分类器就是把一组分类器以某种方式联合起来（典型的是通过是否有投票的权限）对新的实例进行分类。在有监督学习的研究中最有效的领域是研究能构件好的分类器集成的方法。主要的发现是集成的分类器比单一的分类器模仿地更准确。
只有当单一的分类器彼此 (Hansen 和 Salamon 1990) 不兼容时，集成的分类器比组成它的各分类器精确。为了说明原因，假设我们有一个由三个分类器：{h1, h2, h3}集成的分类器，并且把一新事件看作x。如果三个分类器是同一的,若 h1(x) 是错误的时候,则h2(x) 和 h3(x) 也是错误的。但是，如果各分类器所犯的错误是不相关的, 那么当 h1(x) 是错误的时候, h2(x) 和 h3(x) 可能是正确的,所以以多数单一分类正确来分类 x 。已知常数L，假定hi的错误率都等于plt;L/2，而且错误是独立的，那么二项分布的可能性超过L/2的是错误的。图1显示的是一组21个假定的被模拟的全体的区域图，每一个假定都有30%的错误率。11个或较多的假定在曲线下面的区同时错误的概率是 0.026, 比单一的假定错误率少许多。
当然，如果单一的相互不关联的模拟的错误率超过50%的话，整体结果的错误率会增加。因此，成功的集成方法的关键是构建错误率低于50%各单一分类器并且这些错误之间不相关。
构建集成的分类器的方法
现在已经发展了许多集成的方法。一些方法是一般的，而且他们能被应用到任何的学习算法。 其他的方法对特别的算法是特定的。我从介绍一般的方法开始。
示例的二次抽样法
第一个方法操纵示例产生多重假设。 学习算法被运用好几次,且每一次为一组不同示例子集。这种技术对不稳定的学习算法特别适用，这样的算法在回应示例数据的小的变化时输出分类器噪声主要的变化。 决断树，神经的网络和学习规则的算法都是不稳定的。而线性-退化,最近的-邻接,和线性- 临限算法通常是稳定的。
操纵培训组的最直接的方法被叫做装袋。在每个游程上，装袋提出训练组的学习算法，其中训练组是由m个训练实例组成的样本，这些样本被来自最初的m个项目的训练组随意的代替。 这样的一个培训组叫做被设定的最初培训的启动程序统计实验，而这种技术叫做启动程序集合(Breiman 1996a)。每个启动程序统计实验一般说来包含 63.2% 的最初组,即多次出现的几个示例。
另一个训练组的取样方法是通过去除不相交的子集构造训练组。然后，10个交叠的训练组能被任意的分成10个不相交的子集。然后，10个交叠的训练组通过舍去这10个子集中与其他不同的一个的方法被构建。相同的程序用来构造十倍的交换确认训练组;因此，通过这种方法构造的全体有时被称为交叉确认委员(Parmanto, Munro, and Doyle 1996).
操纵培训组的第三个方法用ADABOOST算法举例,被 Freund 和Schapire (1996,1995)改进，如图2所示。像装袋一样，ADABOOST 操纵示例产生多重假定。ADABOOST 维持在示例上的分配概率pi(x)。在i的每一次迭代，根据分配概率pi(x)置换取样，抽取大小为m的训练组。然后，学习算法被应用产生一个分类器hi。分类器在示例上的出错率（以pi(x)委权限）￡i计算出来并被用作调整示例的分配概率。（在图2中，注意分配概率被示例上的一组权重wi(i)常态化获得。）
改变权重的作用是被在正确地被分类的例子上的hi和低权重的错误的分类的实例增加权重。因此，在后来的迭代中，ADABOOST日益增多地构造更困难的研究问题。
最后的分类器hi是由各个单一的分类器按不同的权限构建的。每一个分类器根据它的通过逐渐改善概率pi而得到的准确度决定权重。
在ADABOOST算法(图2)的第4行中，基本的学习算法Learn带权限pi一起被调用。如果学习算法Learn能直接地使用这一个权限（分配概率）,那么这个程序通常提供较好的结果。举例来说，Quinlan(1996)编写了一个能决断的学习树的程序c4.5版 ，该程序以一个加重的样本工作。他的实验表示了这样的程序能极好的工作我们可以想像因为示例(Xi,Yi) 带权重pi(i)的比例不同，计算机出错的概率向后传播。重要示例出现错误比不重要的示例（低权限）引起准确度的较大的滑坡。
然而，如果算法不能直接地使用权限（分配概率）pi，那么就用一示例构造一个按概率pi的比例替换的随机样本。这样的程序使ADABOOST更加随机程序，但是实验已经证明它仍然是有效的。
图3对程序c4.5与带ADABOOST.M1(适用随机样本)的程序c4.5的错误率进行比较。首先一点是策划来自机器学习数据库 (Merz 和Murphy 1996)的欧文资源库的27个测试领域中的每一个。 我们发现大多数的点都在直线y=x的上面,这说明ADABOOST的错误率比c4.5的错误率小。图4对封装的c4.5与c4.5的错误率单独进行了比较。 而且，我们发现在很多问题上封装后的程序c4.5的错误率明显的减少了。最后，图5把封装与优化进行了比较(两者都用c4.5作为底层的算法). 结果显示虽然优化仍然比封装占优势，但是两种技术是可比较的。
控制输入的特征值
第二个产生多分类器的常用技术是控制输入有效的学习算法特征组。例如，实施在金星上探测火山的工程中，Cherkauer (1996) trained 所有32个神经网络。 这32个网络是基于8个不同的119个有效输入特征值的子集和4个不同的网络规模。通过手工选择的输入-功能的子集组成功能组是基于不同的图像处理操作的（就像主要元件的分析和快速的傅立叶变换）。产生的集成分类器能够在识别火山方面与人类专家的绩效相媲美。Tumer和Ghosh(1996)曾申请了一项与一个带有25个输入功能的声纳数据装置相类似的技术。可是，他们发现即使删除很少的输入特征值都会极大的影响单一的分类器的性能，从而导致整个分类器不能很好的工作。显然，只有当输入特征值极大的冗余时，这项技术才有效。
控制输出的结果
构造一个好的集成分类器的第三项技术是控制提供给学习算法的y的数值。 Dietterich和Bakiri(1995)描述了一个被称为输出纠错编码(ECOC)。假如类别的数目K很大。 那么，通过把K个类任意地划分成二个子集Ai和 Bi构造新的研究问题。然后输入数据能被再标示，以便在固定的子集Ai中的任何一个初始类被出始化的标为为0，而固定的子集Bi的初始类被初始化的标示为1。接着这些被再标示的数据被使用到学习算法中，以构造一个分类器hi。通过重复这程序L次 (产生不同的子集Ai和Bi)，我们获得一个 L 的集成分类器h1 ，hellip;， hl。现在,给出一个新的数据点 x,我们应该如何对它分类? 答案是用每个Hi都对x分类。 如果Hi(x)=0,那么子集Ai的每个类计数器加1。如果Hi (x)=1,那么Bi的每个类计数器加1。在L的每一个分类器已经检测之后，有最高数目计数值的类被确定为全体的预测。
与这个方法等价的想法是每一个类都被编码L-bit，代号为Cj，这样当且仅当jisin;Bi时i为1。 第i个学习分类器试图预测这些代码的i位。当使用分类器L分类新的点x的时候,他们的预测被组合成一个字符串L-bit。我们选择最接近L-bit的输出字串的类j。设计高质量的纠错代码的方法能被应用去选择代号Cj。(或,相等地,子集Ai和 Bi)。
Dietterich 和 Bakiri 指出这项技术能改善c4.5和多种困难的分类问题的迭代-遗传算法的性能。最近， Schapire(1997)指出ADABOOST如何与纠错输出代码结合产生一个优良的集成分类器的方法(并封装)，但是本质上与另外的(复合的)一个算法ADABOOST.M2相同。因此，ADABOOST.OC的主要优点是实施简单: 它能与任何解决二个类的问题的学习算法一起运作。
Ricci 和 Aha (1997) 发明了一个结合纠错输出编码和功能选择的方法。当研究每个分类器Hi的时候，他们应用功能-选择的技术为学习分类器选择最好的功能。 通过这种方法他们改进了10个任务中的7个。
引入随机性
产生集成分类器最后一个泛用型的方法是把随机性运用到学习算法之中。 在学习神经的网络的迭代-遗传的算法中,应用到网络的初始权限可被任意地设定。 如果算法被应用到相同的示例上，但是由于不同的初始权限，产生的分类器可能是不同的 (Kolen 和 Pollack 1991)。
虽然这一个方法可能是产生神经网络的全体的最常用的方法, 但是控制培训组可能更有效。Parmanto, Munro, 和 Doyle (1996) 的一项研究把这项技术与封装和十字确认委员会进行比较。他们发现最好的是十字确认委员会，封装排第二,多重随机初始权限在一种合成物质，数据集和二个医学的诊断数据集上是第三个好。
对于c4.5决断树算法,也容易inject randomness (Kwok and Carter 1990). c4.5的主要决断是选择一个功能对决断树的每个内部的节点测试。在每个内部的节点，c4.5应用一个叫做信息-增益的比值区分各种不同的可能功能检验的准则。然后选择级别最高的功能-数值的检验。对于V值的离散数，决断树按照被选择的功能数值把数据分离成V个子集，对于真正有价值的功能，决断树根据被选择的功能的数值是高于还是低于在最高的20个最好的检验中随机选择 的功能(按照相同的概率) 把数据分离成二个子集。表格1把单一的c4.5程序、200个封装的c4.5程序构建的分类器以及带随机数的c4.5程序进行比较。结果显示在三个方法中带随机数的方法表现最好。尤其要注意的是带随机数的方法在文字-识别测试组方面有完美的表现。
Ali和Pazzani (1996)为研究Prologstyle规则，把随机数应用到FOlL算法之上。FOlL算法的作用有时像c4.5因为它把信息-获取准则追加到规则中以分类可能的情况。Ali 和 Pazzani 计算了在80%的一流的候选者里面刻划的所有候选者的条件式，然后申请一个加权的随机-选择的算法在它们之中选择。他们以统计上来比较11个集成分类器和单一的FOlL算法并且发现只有在一个任务的表现上严重失真。他们用11-fold的交叉确认构造训练组的的方法获得相似的结果。
Raviv 和 Intraor(1996)把试验数据的引导程序与带有误差的输入功能的学习算法结合在一起。为了演示一个神经网络的全体每个部分，他们用来自原始训练数据代替示例。每个示例的x数值被高斯无用信息加入到输入功能产生误差。他们叙述在综合性的基准任务和医学的诊断任务的方面的大进步。
一个密切涉及到带随机数的技术的方法是Markov chain Monte Carlo (MCMC) 方法,该方法已经被MacKay (1992)和Neal (19
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19930]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
