A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 843–852, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model Yue Zhang and Stephen Clark University of Cambridge Computer Laboratory William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK {yue.zhang, stephen.clark}@cl.cam.ac.uk Abstract We show that the standard beam-search al- gorithm can be used as an efficient decoder for the global linear model of Zhang and Clark (2008) for joint word segmentation and POS-tagging, achieving a significant speed im- provement. Such decoding is enabled by: (1) separating full word features from par- tial word features so that feature templates can be instantiated incrementally, according to whether the current character is separated or appended; (2) deciding the POS-tag of a poten- tial word when its first character is processed. Early-update is used with perceptron training so that the linear model gives a high score to a correct partial candidate as well as a full out- put. Effective scoring of partial structures al- lows the decoder to give high accuracy with a small beam-size of 16. In our 10-fold cross- validation experiments with the Chinese Tree- bank, our system performed over 10 times as fast as Zhang and Clark (2008) with little ac- curacy loss. The accuracy of our system on the standard CTB 5 test was competitive with the best in the literature. 1 Introduction and Motivation Several approaches have been proposed to solve word segmentation and POS-tagging jointly, includ- ing the reranking approach (Shi and Wang, 2007; Jiang et al., 2008b), the hybrid approach (Nakagawa and Uchimoto, 2007; Jiang et al., 2008a), and the single-model approach (Ng and Low, 2004; Zhang and Clark, 2008; Kruengkrai et al., 2009). These methods led to accuracy improvements over the tra- ditional, pipelined segmentation and POS-tagging baseline by avoiding segmentation error propagation and making use of part-of-speech information to im- prove segmentation. The single-model approach to joint segmentation and POS-tagging offers consistent training of all in- formation, concerning words, characters and parts- of-speech. However, exact inference with dynamic programming can be infeasible if features are de- fined over a large enough range of the output, such as over a two-word history. In our previous work (Zhang and Clark, 2008), which we refer to as Z&C08 from now on, we used an approximate de- coding algorithm that keeps track of a set of partially built structures for each character, which can be seen as a dynamic programming chart which is greatly re- duced by pruning. In this paper we follow the line of single-model research, in particular the global linear model of Z&C08. We show that effective decoding can be achieved with standard beam-search, which gives significant speed improvements compared to the de- coding algorithm of Z&C08, and achieves accura- cies that are competitive with the state-of-the-art. Our research is also in line with recent research on improving the speed of NLP systems with little …

Content truncated to 500 words