A Fast Boosting-based Learner for Feature-Rich Tagging and Chunking

CoNLL 2008: Proceedings of the 12th Conference on Computational Natural Language Learning, pages 17–24 Manchester, August 2008 A Fast Boosting-based Learner for Feature-Rich Tagging and Chunking Tomoya Iwakura Seishi Okamoto Fujitsu Laboratories Ltd. 1-1, Kamikodanaka 4-chome, Nakahara-ku, Kawasaki 211-8588, Japan {iwakura.tomoya,seishi}@jp.fujitsu.com Abstract Combination of features contributes to a significant improvement in accuracy on tasks such as part-of-speech (POS) tag- ging and text chunking, compared with us- ing atomic features. However, selecting combination of features on learning with large-scale and feature-rich training data requires long training time. We propose a fast boosting-based algorithm for learning rules represented by combination of fea- tures. Our algorithm constructs a set of rules by repeating the process to select sev- eral rules from a small proportion of can- didate rules. The candidate rules are gen- erated from a subset of all the features with a technique similar to beam search. Then we propose POS tagging and text chunk- ing based on our learning algorithm. Our tagger and chunker use candidate POS tags or chunk tags of each word collected from automatically tagged data. We evaluate our methods with English POS tagging and text chunking. The experimental results show that the training time of our algo- rithm are about 50 times faster than Sup- port Vector Machines with polynomial ker- nel on the average while maintaining state- of-the-art accuracy and faster classification speed. 1 Introduction Several boosting-based learning algorithms have been applied to Natural Language Processing problems successfully. These include text catego- rization (Schapire and Singer, 2000), Natural Lan- guage Parsing (Collins and Koo, 2005), English syntactic chunking (Kudo et al., 2005) and so on. c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. Furthermore, classifiers based on boosting- based learners have shown fast classification speed (Kudo et al., 2005). However, boosting-based learning algorithms require long training time. One of the reasons is that boosting is a method to create a final hypoth- esis by repeatedly generating a weak hypothesis in each training iteration with a given weak learner. These weak hypotheses are combined as the fi- nal hypothesis. Furthermore, the training speed of boosting-based algorithms becomes more of a problem when considering combination of features that contributes to improvement in accuracy. This paper proposes a fast boosting-based algo- rithm for learning rules represented by combina- tion of features. Our learning algorithm uses the following methods to learn rules from large-scale training samples in a short time while maintaining accuracy; 1) Using a rule learner that learns sev- eral rules as our weak learner while ensuring a re- duction in the theoretical upper bound of the train- ing error of a boosting algorithm, 2) Repeating to learn rules from a small proportion of candidate rules that are generated from a subset of all the fea- tures with a technique similar to beam search, 3) Changing subsets of features used by weak learner dynamically for alleviating overfitting. We also propose feature-rich POS tagging and text chunking based on our …

Content truncated to 500 words