A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 465–472, Sydney, July 2006. c⃝2006 Association for Computational Linguistics A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation Galen Andrew Microsoft Research One Microsoft Way Redmond, WA 98052 galena@microsoft.com Abstract Markov order-1 conditional random fields (CRFs) and semi-Markov CRFs are two popular models for sequence segmenta- tion and labeling. Both models have ad- vantages in terms of the type of features they most naturally represent. We pro- pose a hybrid model that is capable of rep- resenting both types of features, and de- scribe efficient algorithms for its training and inference. We demonstrate that our hybrid model achieves error reductions of 18% and 25% over a standard order-1 CRF and a semi-Markov CRF (resp.) on the task of Chinese word segmentation. We also propose the use of a powerful fea- ture for the semi-Markov CRF: the log conditional odds that a given token se- quence constitutes a chunk according to a generative model, which reduces error by an additional 13%. Our best system achieves 96.8% F-measure, the highest re- ported score on this test set. 1 Introduction The problem of segmenting sequence data into chunks arises in many natural language applica- tions, such as named-entity recognition, shallow parsing, and word segmentation in East Asian lan- guages. Two popular discriminative models that have been proposed for these tasks are the condi- tional random field (CRFs) (Lafferty et al., 2001) and the semi-Markov conditional random field (semi-CRF) (Sarawagi and Cohen, 2004). A CRF in its basic form is a model for label- ing tokens in a sequence; however it can easily be adapted to perform segmentation via labeling each token as BEGIN or CONTINUATION, or accord- ing to some similar scheme. CRFs using this tech- nique have been shown to be very successful at the task of Chinese word segmentation (CWS), start- ing with the model of Peng et al. (2004). In the Second International Chinese Word Segmentation Bakeoff (Emerson, 2005), two of the highest scor- ing systems in the closed track competition were based on a CRF model. (Tseng et al., 2005; Asa- hara et al., 2005) While the CRF is quite effective compared with other models designed for CWS, one wonders whether it may be limited by its restrictive inde- pendence assumptions on non-adjacent labels: an order-M CRF satisfies the order-M Markov as- sumption that, globally conditioned on the input sequence, each label is independent of all other labels given the M labels to its left and right. Consequently, the model only “sees” word bound- aries within a moving window of M + 1 charac- ters, which prohibits it from explicitly modeling the tendency of strings longer than that window to form words, or from modeling the lengths of the words. Although the window can in principle be widened by increasing M, this is not a practi- cal solution as the complexity of training and de- coding a linear sequence CRF grows exponentially with the …

Content truncated to 500 words