A Boosting Algorithm for Classification of Semi-Structured Text

A Boosting Algorithm for Classification of Semi-Structured Text Taku Kudo∗ Yuji Matsumoto Graduate School of Information Science, Nara Institute of Science and Technology 8916-5 Takayama, Ikoma Nara Japan {taku-ku,matsu}@is.naist.jp Abstract The focus of research in text classification has ex- panded from simple topic identification to more challenging tasks such as opinion/modality identi- fication. Unfortunately, the latter goals exceed the ability of the traditional bag-of-word representation approach, and a richer, more structural representa- tion is required. Accordingly, learning algorithms must be created that can handle the structures ob- served in texts. In this paper, we propose a Boosting algorithm that captures sub-structures embedded in texts. The proposal consists of i) decision stumps that use subtrees as features and ii) the Boosting al- gorithm which employs the subtree-based decision stumps as weak learners. We also discuss the rela- tion between our algorithm and SVMs with tree ker- nel. Two experiments on opinion/modality classifi- cation confirm that subtree features are important. 1 Introduction Text classification plays an important role in orga- nizing the online texts available on the World Wide Web, Internet news, and E-mails. Until recently, a number of machine learning algorithms have been applied to this problem and have been proven suc- cessful in many domains (Sebastiani, 2002). In the traditional text classification tasks, one has to identify predefined text “topics”, such as politics, finance, sports or entertainment. For learning algo- rithms to identify these topics, a text is usually rep- resented as a bag-of-words, where a text is regarded as a multi-set (i.e., a bag) of words and the word or- der or syntactic relations appearing in the original text is ignored. Even though the bag-of-words rep- resentation is naive and does not convey the mean- ing of the original text, reasonable accuracy can be obtained. This is because each word occurring in the text is highly relevant to the predefined “topics” to be identified. ∗At present, NTT Communication Science Laboratories, 2-4, Hikaridai, Seika-cho, Soraku, Kyoto, 619-0237 Japan taku@cslab.kecl.ntt.co.jp Given that a number of successes have been re- ported in the field of traditional text classification, the focus of recent research has expanded from sim- ple topic identification to more challenging tasks such as opinion/modality identification. Example includes categorization of customer E-mails and re- views by types of claims, modalities or subjectiv- ities (Turney, 2002; Wiebe, 2000). For the lat- ter, the traditional bag-of-words representation is not sufficient, and a richer, structural representa- tion is required. A straightforward way to ex- tend the traditional bag-of-words representation is to heuristically add new types of features to the original bag-of-words features, such as fixed-length n-grams (e.g., word bi-gram or tri-gram) or fixed- length syntactic relations (e.g., modifier-head rela- tions). These ad-hoc solutions might give us rea- sonable performance, however, they are highly task- dependent and require careful design to create the “optimal” feature set for each task. Generally speaking, by using text processing sys- tems, a text can be converted into a semi-structured text annotated with parts-of-speech, base-phrase in- formation or syntactic …

Content truncated to 500 words