A Boosted Semi-Markov Perceptron

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 47–55, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics A Boosted Semi-Markov Perceptron Tomoya Iwakura Fujitsu Laboratories Ltd. 1-1, Kamikodanaka 4-chome, Nakahara-ku, Kawasaki 211-8588, Japan iwakura.tomoya@jp.fujitsu.com Abstract This paper proposes a boosting algorithm that uses a semi-Markov perceptron. The training algorithm repeats the training of a semi-Markov model and the update of the weights of training samples. In the boost- ing, training samples that are incorrectly segmented or labeled have large weights. Such training samples are aggressively learned in the training of the semi-Markov perceptron because the weights are used as the learning ratios. We evaluate our training method with Noun Phrase Chunk- ing, Text Chunking and Extended Named Entity Recognition. The experimental re- sults show that our method achieves better accuracy than a semi-Markov perceptron and a semi-Markov Conditional Random Fields. 1 Introduction Natural Language Processing (NLP) basic tasks, such as Noun Phrase Chunking, Text Chunking, and Named Entity Recognition, are realized by segmenting words and labeling to the segmented words. To realize these tasks, supervised learn- ing algorithms have been applied successfully. In the early stages, algorithms for training classifiers, including Maximum Entropy Models (Tsuruoka and Tsujii, 2005), AdaBoost-based learning algo- rithms (Carreras et al., 2002), and Support Vector Machines (SVMs) (Kudo and Matsumoto, 2001) were widely used. Recently, learning algorithms for structured prediction, such as linear-chain structured predictions, and semi-Markov model- based ones, have been widely used. The examples of linear-chain structured predictions include Con- ditional Random Fields (CRFs) (Lafferty et al., 2001) and structured perceptron (Collins, 2002). The examples of semi-Markov model-based ones include semi-Markov model perceptron (Cohen and Sarawagi, 2004), and semi-Markov CRFs (Sarawagi and Cohen, 2005). Among these methods, semi-Markov-based ones have shown good performance in terms of accuracy (Cohen and Sarawagi, 2004; Sarawagi and Cohen, 2005; Okanohara et al., 2006; Iwakura et al., 2011). One of the reasons is that a semi-Markov learner trains models that assign labels to hypothesized segments (i.e., word chunks) instead of labeling to individual words. This enables use of features that cannot be easily used in word level processing such as the beginning word of a segment, the end word of a segment, and so on. To obtain higher accuracy, boosting methods have been applied to learning methods for training classifiers. Boosting is a method to create a final hypothesis by repeatedly generating a weak hy- pothesis and changing the weights of training sam- ples in each training iteration with a given weak learner such as a decision stump learner (Schapire and Singer, 2000) and a decision tree learner (Car- reras et al., 2002). However, to the best of our knowledge, there are no approaches that apply boosting to learning algorithms for structured pre- diction. In other words, if we can successful apply boosting to learning algorithms for structured pre- diction, we expect to obtain higher accuracy. This paper proposes a boosting algorithm for a semi-Markov perceptron. Our learning method uses a semi-Markov perceptron as …

Content truncated to 500 words