Joint Word Segmentation and POS Tagging Using a Single Perceptron

Proceedings of ACL-08: HLT, pages 888–896, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Joint Word Segmentation and POS Tagging using a Single Perceptron Yue Zhang and Stephen Clark Oxford University Computing Laboratory Wolfson Building, Parks Road Oxford OX1 3QD, UK {yue.zhang,stephen.clark}@comlab.ox.ac.uk Abstract For Chinese POS tagging, word segmentation is a preliminary step. To avoid error propa- gation and improve segmentation by utilizing POS information, segmentation and tagging can be performed simultaneously. A challenge for this joint approach is the large combined search space, which makes efficient decod- ing very hard. Recent research has explored the integration of segmentation and POS tag- ging, by decoding under restricted versions of the full combined search space. In this paper, we propose a joint segmentation and POS tag- ging model that does not impose any hard con- straints on the interaction between word and POS information. Fast decoding is achieved by using a novel multiple-beam search algo- rithm. The system uses a discriminative sta- tistical model, trained using the generalized perceptron algorithm. The joint model gives an error reduction in segmentation accuracy of 14.6% and an error reduction in tagging ac- curacy of 12.2%, compared to the traditional pipeline approach. 1 Introduction Since Chinese sentences do not contain explicitly marked word boundaries, word segmentation is a necessary step before POS tagging can be performed. Typically, a Chinese POS tagger takes segmented in- puts, which are produced by a separate word seg- mentor. This two-step approach, however, has an obvious flaw of error propagation, since word seg- mentation errors cannot be corrected by the POS tag- ger. A better approach would be to utilize POS in- formation to improve word segmentation. For ex- ample, the POS-word pattern “number word” + “� (a common measure word)” can help in segmenting the character sequence “���” into the word se- quence “� (one) � (measure word) � (person)” instead of “� (one) �� (personal; adj)”. More- over, the comparatively rare POS pattern “number word” + “number word” can help to prevent seg- menting a long number word into two words. In order to avoid error propagation and make use of POS information for word segmentation, segmen- tation and POS tagging can be viewed as a single task: given a raw Chinese input sentence, the joint POS tagger considers all possible segmented and tagged sequences, and chooses the overall best out- put. A major challenge for such a joint system is the large search space faced by the decoder. For a sentence with n characters, the number of possible output sequences is O(2n−1 · T n), where T is the size of the tag set. Due to the nature of the com- bined candidate items, decoding can be inefficient even with dynamic programming. Recent research on Chinese POS tagging has started to investigate joint segmentation and tagging, reporting accuracy improvements over the pipeline approach. Various decoding approaches have been used to reduce the combined search space. Ng and Low (2004) mapped the joint segmentation and POS …

Content truncated to 500 words