A Sequential Model for Multi-Class Classification

A Sequential Model for Multi-Class Classification � Yair Even-Zohar Dan Roth Department of Computer Science University of Illinois at Urbana-Champaign � evenzoha,danr � @uiuc.edu Abstract Many classification problems require decisions among a large number of competing classes. These tasks, however, are not handled well by general pur- pose learning methods and are usually addressed in an ad-hoc fashion. We suggest a general approach – a sequential learning model that utilizes classi- fiers to sequentially restrict the number of compet- ing classes while maintaining, with high probability, the presence of the true outcome in the candidates set. Some theoretical and computational properties of the model are discussed and we argue that these are important in NLP-like domains. The advantages of the model are illustrated in an experiment in part- of-speech tagging. 1 Introduction A large number of important natural language infer- ences can be viewed as problems of resolving ambi- guity, either semantic or syntactic, based on proper- ties of the surrounding context. These, in turn, can all be viewed as classification problems in which the goal is to select a class label from among a collection of candidates. Examples include part-of speech tagging, word-sense disambiguation, accent restoration, word choice selection in machine trans- lation, context-sensitive spelling correction, word selection in speech recognition and identifying dis- course markers. Machine learning methods have become the most popular technique in a variety of classifi- cation problems of these sort, and have shown significant success. A partial list consists of Bayesian classifiers (Gale et al., 1993), decision lists (Yarowsky, 1994), Bayesian hybrids (Gold- ing, 1995), HMMs (Charniak, 1993), inductive logic methods (Zelle and Mooney, 1996), memory- � This research is supported by NSF grants IIS-9801638, IIS- 0085836 and SBR-987345. based methods (Zavrel et al., 1997), linear classi- fiers (Roth, 1998; Roth, 1999) and transformation- based learning (Brill, 1995). In many of these classification problems a signif- icant source of difficulty is the fact that the number of candidates is very large – all words in words se- lection problems, all possible tags in tagging prob- lems etc. Since general purpose learning algorithms do not handle these multi-class classification prob- lems well (see below), most of the studies do not address the whole problem; rather, a small set of candidates (typically two) is first selected, and the classifier is trained to choose among these. While this approach is important in that it allows the re- search community to develop better learning meth- ods and evaluate them in a range of applications, it is important to realize that an important stage is missing. This could be significant when the clas- sification methods are to be embedded as part of a higher level NLP tasks such as machine transla- tion or information extraction, where the small set of candidates the classifier can handle may not be fixed and could be hard to determine. In this work we develop a general approach to the study of multi-class classifiers. We suggest a se- quential learning model that utilizes (almost) …

Content truncated to 500 words