Adaboost经典论文资源-CSDN文库

3星 · 超过75%的资源需积分: 46 115 浏览量 2012-02-13 15:33:12 上传评论 1 收藏 338KB PDF 举报

《Adaboost经典论文》是机器学习领域内一篇极具影响力的研究成果，主要介绍了BoosTexter系统，一种基于Adaboost算法的文本分类系统。该论文由Robert E. Schapire和Yoram Singer共同撰写，发表于Machine Learning期刊，具体为第39卷的2/3期，页码在135至168之间，出版年份为2000年。本文将深入探讨Adaboost算法、BoosTexter系统及其在文本和语音分类任务中的应用。 ### Adaboost算法简介 Adaboost（自适应增强）是一种迭代的机器学习算法，最初由Yoav Freund和Robert Schapire提出。其核心思想是通过结合多个弱分类器来创建一个强分类器。弱分类器是指准确率略高于随机猜测的分类模型。在Adaboost中，每个弱分类器都会被训练并赋予一个权重，这个权重会根据其在训练数据上的表现进行调整。如果某个弱分类器在某些样本上分类错误，那么这些样本在后续训练中的权重会增加，使得后续的弱分类器更加关注这些难以正确分类的样本。最终，所有弱分类器的预测结果会加权组合成一个强分类器，用于最终的预测。 ### BoosTexter系统 BoosTexter是一个基于Adaboost算法的文本分类系统，它专为多类文本和语音分类任务设计。BoosTexter的核心在于利用Adaboost算法的强大能力来处理复杂的文本分类问题，如新闻文章的主题分类或自动识别客户电话请求的类型。系统首先将语音转换为文本，然后对文本进行分类。为了提高分类的准确性，BoosTexter采用了一种改进的Adaboost算法家族，这种算法能够在训练过程中逐步优化分类规则，使模型能够更准确地捕捉到数据的复杂性。 ### 实验结果与比较论文中详细介绍了BoosTexter与其他文本分类算法在多种任务上的性能对比。实验结果表明，BoosTexter在许多分类任务上表现出色，其准确率显著高于其他常见的文本分类方法。这主要是因为BoosTexter能够有效地整合多个弱分类器的信息，从而形成一个强大的分类模型。此外，论文还讨论了BoosTexter在自动呼叫类型识别方面的应用，展示了其在处理自然语言处理和语音识别任务时的灵活性和有效性。 ### 结论与展望《Adaboost经典论文》不仅详细介绍了Adaboost算法的理论基础和BoosTexter系统的实现细节，还通过丰富的实验证明了该系统在文本和语音分类领域的强大性能。BoosTexter的成功应用进一步验证了Adaboost算法在处理复杂分类任务时的有效性。未来的研究可以探索Adaboost在更多领域内的应用，如图像识别、生物信息学等，以及如何进一步优化Adaboost算法，以适应更大规模的数据集和更复杂的分类任务。同时，随着深度学习技术的发展，Adaboost算法也可以与神经网络等先进模型相结合，探索出更加高效和精确的分类解决方案。

资源推荐

资源详情

资源评论

Machine Learning, 39(2/3):135-168, 2000.

BoosTexter:

A Boosting-based System for Text Categorization

ROBERT E. SCHAPIRE

schapire@research.att.com

AT&T Labs, ShannonLaboratory, 180 Park Avenue, Room A279, Florham Park, NJ 07932-0971

YORAM SINGER

singer@research.att.com

AT&T Labs, ShannonLaboratory, 180 Park Avenue, Room A277, Florham Park, NJ 07932-0971

Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech

categorization tasks. Our approach is based on a new and improved family of boosting algorithms. We describe

in detail an implementation, called BoosTexter, of the new boosting algorithms for text categorization tasks. We

present results comparing the performance of BoosTexter and a number of other text-categorizationalgorithms on

a variety of tasks. We conclude by describing the application of our system to automatic call-type identiﬁcation

from unconstrained spoken customer responses.

1. Introduction

Text categorization is the problem of classifying text documents into categories or classes.

For instance, a typical problem is that of classifying news articles by topic based on their

textual content. Another problem is to automatically identify the type of call requested

by a customer; for instance, if the customer says, “Yes, I would like to charge this call to

my Visa,” we want the system to recognize that this is a calling-card call and to process

the call accordingly. (Although this is actually a speech-categorization problem, we can

nevertheless apply a text-based system by passing the spoken responses through a speech

recognizer.)

In this paper, we introduce the use of a machine-learning technique called boosting to

the problem of text categorization. The main idea of boosting is to combine many simple

and moderately inaccurate categorization rules intoa single, highly accurate categorization

rule. The simple rules are trained sequentially; conceptually, each rule is trained on the

examples which were most difﬁcult to classify by the preceding rules.

Our approach is based on a new and improved family of boosting algorithms which we

have described and analyzed in detail in a companion paper (Schapire & Singer, 1998).

This new family extends and generalizes Freund and Schapire’s AdaBoost algorithm (Fre-

und & Schapire, 1997), which has been studied extensively and which has been shown

to perform well on standard machine-learning tasks (Breiman, 1998; Drucker & Cortes,

1996; Freund & Schapire, 1996, 1997; Maclin & Opitz, 1997; Margineantu & Dietterich,

1997; Quinlan, 1996; Schapire, 1997; Schapire, Freund, Bartlett, & Lee, 1998). The pur-

pose of the current work is to describe some ways in which boosting can be applied to the

problem of text categorization, and to test its performance relative to a number of other

text-categorization algorithms.

Text-categorization problems are usually multiclass in the sense that there are usually

more than two possible categories. Although in some applications there may be a very

R. E. SCHAPIRE AND Y. SINGER

large number of categories, in this work, we focus on the case in which there are a small

to moderate number of categories. It is also common for text-categorization tasks to be

multi-label, meaning that the categories are not mutually exclusive so that the same doc-

ument may be relevant to more than one category. For instance, bibliographic medical

articles are routinely given multiple Medical Subject Index (MeSH) categories when en-

tered into Medline, the nationalbibliographic searchable archive which contains more than

twenty million documents. While most machine-learning systems are designed to handle

multiclass data, much less common are systems that can handle multi-label data. While

numerous categorization algorithms, such as

-nearest neighbor, can be adapted to multi-

label categorization problems, when machine-learning and other approaches are applied

to text-categorization problems, a common technique has been to decompose the multi-

class, multi-label problem into multiple, independent binary classiﬁcation problems (one

per category).

In this paper, we adopt a different approach in which we use two extensions of AdaBoost

that were speciﬁcally intended for multiclass, multi-label data. In the ﬁrst extension, the

goal of the learning algorithm is to predict all and only all of the correct labels. Thus,

the learned classiﬁer is evaluated in terms of its ability to predict a good approximation of

the set of labels associated with a given document. In the second extension, the goal is to

design a classiﬁer that ranks the labels so that the correct labels will receive the highest

ranks. We next describe BoosTexter, a system which embodies four versions of boosting

based on these extensions, and we discuss the implementation issues that arise in multi-

label text categorization.

There has been voluminouswork done on text categorization, includingtechniques based

on decision trees, neural networks, nearest neighbor methods, Rocchio’s method, support-

vector machines, linear least squares, naive Bayes, rule-based methods and more. (See,

for instance, (Apt´e, Damerau, & Weiss, 1994; Biebricher, Fuhr, Lustig, Schwantner, &

Knorz, 1988; Cohen & Singer, 1996; Field, 1975; Fuhr & Pfeifer, 1994; Koller & Sahami,

1997; Lewis & Ringuette, 1994; Moulinier, Raˇskinis, & Ganascia, 1996; Ng, Goh, & Low,

1997; Yang, 1994).) It would be impossible for us to compare our algorithms to all of the

previous methods. Instead, we compare to four very different methods which we believe

are representative of some of the most effective techniques available, and report results on

several different tasks. Our experiments show that, using a number of evaluation measures,

our system’s performance is generally better than the other algorithms, sometimes by a

wide margin.

To further compare our algorithm to other methods, we tested the performance of Boos-

Texter on a standard benchmark problem so that performance could be compared directly

with a large body of results reported in the literature. We speciﬁcally focus on a recent

study by Yang (1999) who conducted several experiments on this benchmark and who also

surveyed many results reported by other authors. BoosTexter’s performance places it at the

very top of all the methods included in Yang’s study.

Finally, we discuss the application of BoosTexter to an automatic speech-categorization

task and compare the performance of our system to a previous algorithm which was specif-

ically designed for this task.

A BOOSTING-BASED SYSTEM FOR TEXT CATEGORIZATION

2. Preliminaries

In this section, we describe the formal setting we use to study multi-label text categoriza-

tion.

Let

denote the domain of possible text documents and let

be a ﬁnite set of labels or

classes. We denote the size of

jY j

In the traditional machine-learning setting, each document

is assigned a single

class

. The goal then, typically, is to ﬁnd a classiﬁer

X!Y

which minimizes

the probabilitythat

(

)

on a newly observed example

(

x y

)

. In the multi-label case,

each document

may be assigned multiple labels in

. For example, in a multiclass

news-ﬁltering problem in which the possible classes are News, Finance and Sports,

a document may belong to both News and Finance. Thus, a labeled example is a pair

(

x Y

)

where

Y

is the set of labels assigned to

. The single-label case is a special

case in which

for all observations.

For

Y

, let us deﬁne



]

for

to be





;

In this paper, we will be primarily interested in classiﬁers which produce a ranking of

the possible labels for a given document with the hope that the appropriate labels will

appear at the top of the ranking. To be more formal, the goal of learning is to produce a

function of the form

XY !

with the interpretation that, for a given instance

the labels in

should be ordered according to

(

x



)

. That is, a label

is considered to

be ranked higher than

(

x `

)

(

x `

)

.If

is the associated label set for

, then

a successful learning algorithm will tend to rank labels in

higher than those not in

Precise evaluation measures are discussed in Sec. 5.

Finally, to simplify the notation, for any predicate



, let





]]



holds and

other-

wise.

3. Boosting algorithms for multi-label multiclass problems

In a companion paper (Schapire & Singer, 1998), we introduced and analyzed two new

boosting algorithms for multiclass, multi-label classiﬁcation problems. Here, we review

the two algorithms, discuss four versions of these algorithms, and describe an efﬁcient

implementation of the algorithms for the problem of text categorization.

The purpose of boosting is to ﬁnd a highly accurate classiﬁcation rule by combining

many weak or base hypotheses, each of which may be only moderately accurate. We

assume access to a separate procedure called the weak learner or weak learning algorithm

for computing the weak hypotheses. The boosting algorithm ﬁnds a set of weak hypotheses

by calling the weak learner repeatedly in a series of rounds. These weak hypotheses are

then combined into a single rule called the ﬁnal or combined hypothesis.

In the simplest version of AdaBoostfor single-label classiﬁcation, the boosting algorithm

maintains a set of importance weights over training examples. These weights are used by

the weak learning algorithm whose goal is to ﬁnd a weak hypothesis with moderately low

R. E. SCHAPIRE AND Y. SINGER

Given:

(

Y

)

:::

(

Y

)

where

Y

Initialize

(

i `

)=1

(

)

For

:::T



Pass distribution

to weak learner.



Get weak hypothesis

XY !



Choose





Update:

(

i `

(

i `

) exp(

;





]

(

`

))

where

is a normalization factor (chosen so that

will be a distribution).

Output the ﬁnal hypothesis:

(

x `



(

x `

)

Figure 1. The algorithm AdaBoost.MH.

error with respect to these weights. Thus, the boosting algorithm can use these weights to

force the weak learner to concentrate on the examples which are hardest to classify.

As we will see, for multiclass, multi-label problems, it is appropriate to maintain instead

a set of weights over training examples and labels. As boosting progresses, training ex-

amples and their corresponding labels that are hard to predict correctly get incrementally

higher weights while examples and labels that are easy to classify get lower weights. For

instance, for the news classiﬁcation problem, it might be easy to classify a document as a

news item but hard to determine whether or not it belongs to the ﬁnance section. Then, as

boosting progresses the weight of the label News for that document decreases while the

weight of Finance increases. The intended effect is to force the weak learning algorithm

to concentrate on examples and labels that will be most beneﬁcial to the overall goal of

ﬁnding a highly accurate classiﬁcation rule.

3.1. AdaBoost.MH

Our ﬁrst boosting algorithm for multiclass multi-label classiﬁcation problems, called

AdaBoost.MH, is shown in Fig. 1. Let

be a sequence of training examples

(

Y

)

:::

(

Y

)

where each instance

and each

Y

. As described

above, AdaBoost.MH maintains a set of weights as a distribution

over examples and

labels. Initially, this distribution is uniform. On each round

, the distribution

(together

with the training sequence

) is passed to the weak learner who computes a weak hypoth-

esis

. The output of the weak learner is a hypothesis

XY !

. We interpret

the sign of

(

x `

)

as a prediction as to whether the label

is or is not assigned to

(i.e.,

A BOOSTING-BASED SYSTEM FOR TEXT CATEGORIZATION

a prediction of the value of



]

). The magnitude of the prediction

(

x `

)

is interpreted

as a measure of “conﬁdence” in the prediction. The precise goal of the weak learner is

described below, as are the weak learners used in our experiments.

A parameter



is then chosen and the distribution

is updated. We discuss the choice



below. In the typical case that



is positive, the distribution

is updated in a

manner that increases the weight of example-label pairs which are misclassiﬁed by

(i.e.,

for which



]

and

(

`

)

differ in sign). The ﬁnal hypothesis ranks documents using a

weighted vote of the weak hypotheses.

This algorithm is derived using a natural reduction of the multiclass, multi-label data

to binary data. Under this reduction, each example

(

x Y

)

is mapped to

binary-labeled

examples of the form

((

x `

)

Y



])

for all

; that is, the instance or “document” part

of each derived example is formally a pair

(

x `

)

, and the binary label associated with this

instance is



]

. In other words, we can think of each observed label set

as specifying

binary labels (depending on whether a label

is or is not included in

), and we can then

apply binary AdaBoost to the derived binary data. The algorithm that results from such a

reduction is equivalent to AdaBoost.MH.

This view of AdaBoost.MH also leads to a simple analysis. Speciﬁcally, we have proved

(Schapire & Singer, 1998) a bound on the empirical Hamming loss of this algorithm, i.e.,

the fraction of examples

and labels

for which the sign of

(

`

)

differs from



]

We showed that the Hamming loss of this algorithm is at most

, where

is the

normalization factor computed on round

. This upper bound can be used in guiding both

our choice of



and the design of our weak learning algorithm. Together, these choices

should be geared on each round

toward the minimization of

(

i `

)exp(

;





]

(

`

))

(1)

In Sec. 4, we describe the methods used for choosing



and the implementation of the

weak learning algorithm for text categorization.

Note that the space and time-per-round requirements of AdaBoost.MH are

(

)

, not

including the call to the weak learner.

3.2. AdaBoost.MR

We next describe our second boosting algorithm called AdaBoost.MR. Whereas Ada-

Boost.MH is designed to minimize Hamming loss, AdaBoost.MR is designed speciﬁcally

to ﬁnd a hypothesis which ranks the labels in a manner that hopefully places the correct

labels at the top of the ranking.

With respect to a labeled observation

(

x Y

)

, we focus now only on the relative ordering

of the crucial pairs

`

for which

and

. A classiﬁcation rule

misorders a

crucial pair

`

(

x `

)



(

x `

)

so that

fails to rank

above

. Our goal now is

to ﬁnd a function

with a small number of misorderings so that the labels in

are ranked

above the labels not in

. Put another way, our goal is to minimize the average fraction of

crucial pairs which are misordered, a quantity that we call the empirical ranking loss:

剩余33页未读，继续阅读

评论收藏

内容反馈

小野狼fight

2014-09-20

这篇不算经典，但还算不错的一篇文章，值得一看吧

wenqing_y

粉丝: 1
资源: 4

Adaboost经典论文

关于adaboost算法的论文

Adaboost算法文献

adaboost的一个简单文章

adaboost资源，包括toolbox和参考文献，应用论文等

Haar-Like特征和AdaBoost论文学习的PPT

论文研究-一种基于AdaBoost-SVM的流量分类方法.pdf

Paul Viola 的Adaboost级联检测器英文原文及中文翻译

经典 AdaBoost 分类器：使用 Adaboost 将弱阈值分类器提升为强分类器-matlab开发

Adaboost人脸应用论文

Adaboost人脸检测的四篇重量级论文

论文研究-基于多阈值弱学习的Adaboost检测器.pdf

收集的adaboost论文

adaboost人脸检测算法的经典论文

adaboost资料，包括adaboost toolbox，资料，论文等

论文研究-基于Adaboost的选择性样本权重更新算法.pdf

基于Adaboost算法的人脸识别检测论文.docx

论文研究-基于多特征融合和Adaboost算法的图像检索.pdf

Haar+Adaboost人脸检测 C实现

毕业设计-微博评论文本情感分析SVM+朴素贝叶斯+AdaBoost+完整项目论文文档

中国知网肤色模型+adaboost硕士研究生论文

最新资源