A New Perceptron Algorithm for Sequence Labeling with Non-Local Features

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 315–324, Prague, June 2007. c⃝2007 Association for Computational Linguistics A New Perceptron Algorithm for Sequence Labeling with Non-local Features Jun’ichi Kazama and Kentaro Torisawa Japan Advanced Institute of Science and Technology (JAIST) Asahidai 1-1, Nomi, Ishikawa, 923-1292 Japan {kazama, torisawa}@jaist.ac.jp Abstract We cannot use non-local features with cur- rent major methods of sequence labeling such as CRFs due to concerns about com- plexity. We propose a new perceptron algo- rithm that can use non-local features. Our algorithm allows the use of all types of non-local features whose values are deter- mined from the sequence and the labels. The weights of local and non-local features are learned together in the training process with guaranteed convergence. We present experi- mental results from the CoNLL 2003 named entity recognition (NER) task to demon- strate the performance of the proposed algo- rithm. 1 Introduction Many NLP tasks such as POS tagging and named entity recognition have recently been solved as se- quence labeling. Discriminative methods such as Conditional Random Fields (CRFs) (Lafferty et al., 2001), Semi-Markov Random Fields (Sarawagi and Cohen, 2004), and perceptrons (Collins, 2002a) have been popular approaches for sequence label- ing because of their excellent performance, which is mainly due to their ability to incorporate many kinds of overlapping and non-independent features. However, the common limitation of these meth- ods is that the features are limited to “local” fea- tures, which only depend on a very small number of labels (usually two: the previous and the current). Although this limitation makes training and infer- ence tractable, it also excludes the use of possibly useful “non-local” features that are accessible after all labels are determined. For example, non-local features such as “same phrases in a document do not have different entity classes” were shown to be use- ful in named entity recognition (Sutton and McCal- lum, 2004; Bunescu and Mooney, 2004; Finkel et al., 2005; Krishnan and Manning, 2006). We propose a new perceptron algorithm in this pa- per that can use non-local features along with lo- cal features. Although several methods have al- ready been proposed to incorporate non-local fea- tures (Sutton and McCallum, 2004; Bunescu and Mooney, 2004; Finkel et al., 2005; Roth and Yih, 2005; Krishnan and Manning, 2006; Nakagawa and Matsumoto, 2006), these present a problem that the types of non-local features are somewhat con- strained. For example, Finkel et al. (2005) enabled the use of non-local features by using Gibbs sam- pling. However, it is unclear how to apply their method of determining the parameters of a non-local model to other types of non-local features, which they did not used. Roth and Yih (2005) enabled the use of hard constraints on labels by using inte- ger linear programming. However, this is equivalent to only allowing non-local features whose weights are fixed to negative infinity. Krishnan and Manning (2006) divided the model into two CRFs, where the second model …

Content truncated to 500 words