Revision Learning and its Application to Part-of-Speech Tagging

Revision Learning and its Application to Part-of-Speech Tagging Tetsuji Nakagawa∗ and Taku Kudo and Yuji Matsumoto tetsu-na@plum.freemail.ne.jp,{taku-ku,matsu}@is.aist-nara.ac.jp Graduate School of Information Science Nara Institute of Science and Technology 8916−5 Takayama, Ikoma, Nara 630−0101, Japan Abstract This paper presents a revision learn- ing method that achieves high per- formance with small computational cost by combining a model with high generalization capacity and a model with small computational cost. This method uses a high capacity model to revise the output of a small cost model. We apply this method to English part- of-speech tagging and Japanese mor- phological analysis, and show that the method performs well. 1 Introduction Recently, corpus-based approaches have been widely studied in many natural language pro- cessing tasks, such as part-of-speech (POS) tag- ging, syntactic analysis, text categorization and word sense disambiguation. In corpus-based natural language processing, one important is- sue is to decide which learning model to use. Various learning models have been studied such as Hidden Markov models (HMMs) (Rabiner and Juang, 1993), decision trees (Breiman et al., 1984) and maximum entropy models (Berger et al., 1996). Recently, Support Vector Ma- chines (SVMs) (Vapnik, 1998; Cortes and Vap- nik, 1995) are getting to be used, which are supervised machine learning algorithm for bi- nary classification. SVMs have good generaliza- tion performance and can handle a large num- ber of features, and are applied to some tasks ∗ Presently with Oki Electric Industry successfully (Joachims, 1998; Kudoh and Mat- sumoto, 2000). However, their computational cost is large and is a weakness of SVMs. In general, a trade-off between capacity and com- putational cost of learning models exists. For example, SVMs have relatively high generaliza- tion capacity, but have high computational cost. On the other hand, HMMs have lower compu- tational cost, but have lower capacity and dif- ficulty in handling data with a large number of features. Learning models with higher capac- ity may not be of practical use because of their prohibitive computational cost. This problem becomes more serious when a large amount of data is used. To solve this problem, we propose a revision learning method which combines a model with high generalization capacity and a model with small computational cost to achieve high per- formance with small computational cost. This method is based on the idea that processing the entire target task using a model with higher ca- pacity is wasteful and costly, that is, if a large portion of the task can be processed easily using a model with small computational cost, it should be processed by such a model, and only difficult portion should be processed by the model with higher capacity. Revision learning can handle a general multi- class classification problem, which includes POS tagging, text categorization and many other tasks in natural language processing. We ap- ply this method to English POS tagging and Japanese morphological analysis. This paper is organized as follows: Section 2 describes the general multi-class classification Computational Linguistics (ACL), Philadelphia, July 2002, pp. 497-504. Proceedings of …

Content truncated to 500 words