Mistake-Driven Learning in Text Categorization

Mistake-Driven Learning in Text Categorization Ido Dagan* Dept. of Math. & CS Bar Ilan University Ramat Gan 52900, Israel dagan@cs .biu. ac. il Yael Karov Dept. of Appl. Math. & CS Weizmann Institute of Science Rehovot 76100, Israel yaelk@wisdom, we £zmann. ac. il Dan Roth t Dept. of Appl. Math. & CS Weizmann Institute of Science Rehovot 76100, Israel danrQwisdom, weizmalm, ac. il Abstract Learning problems in the text processing domain often map the text to a space whose dimensions are the measured fea- tures of the text, e.g., its words. Three characteristic properties of this domain are (a) very high dimensionality, (b) both the learned concepts and the instances reside very sparsely in the feature space, and (c) a high variation in the number of active features in an instance. In this work we study three mistake-driven learning algo- rithms for a typical task of this nature - text categorization. We argue that these algorithms- which categorize documents bY learning a linear separator in the feature space - have a few properties that make them ideal for this do- main. We then show that a quantum leap in performance is achieved when we fur- ther modify the algorithms to better ad- dress some of the specific characteristics of the domain. In particular, we demonstrate (1) how variation in document length can be tolerated by either normalizing feature weights or by using negative weights, (2) the positive effect of applying a threshold range in training, (3) alternatives in consid- ering feature frequency, and (4) the bene- fits of discarding features while training. Overall, we present an algorithm, a vari- ation of Littlestone's Winnow, which per- forms significantly better than any other algorithm tested on this task using a simi- lar feature set. *Partly supported by a grant no. 8560195 from the Israeh Ministry of Science. tPartly supported by a grant from the Israeli Ministry of Science. Part of this work was done while visiting at Harvard University, supported by ONR grant N00014- 96-1-0550. 1 Introduction Learning problems in the natural language and text processing domains are often studied by mapping the text to a space whose dimensions are the mea- sured features of the text, e.g., the words appearing in a document. Three characteristic propertie s of this domain are (a) very high dimensionality, (b) both the learned concepts and the instances reside very sparsely in the feature space and, consequently, (c) there is a high variation in the number of active features in an instance. Multiplicative weight-updating algorithms such as Winnow (Littlestone, 1988) have been studied exten- sively in the theoretical learning literature. Theoret- ical analysis has shown that they have exceptionally good behavior in domains with these characteristics, and in particular in the presence of irrelevant at- tributes, noise, and even a target function chang- ing in time (Littlestone, 1988; Littlestone and War- muth, 1994; Herbster and Warmuth, 1995), but only recently have people started to use them in applica- tions (Golding and Roth, 1996; Lewis et al., …

Content truncated to 500 words