Chinese Segmentation with a Word-Based Perceptron Algorithm

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 840–847, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Chinese Segmentation with a Word-Based Perceptron Algorithm 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 Standard approaches to Chinese word seg- mentation treat the problem as a tagging task, assigning labels to the characters in the sequence indicating whether the char- acter marks a word boundary. Discrimina- tively trained models based on local char- acter features are used to make the tagging decisions, with Viterbi decoding finding the highest scoring segmentation. In this paper we propose an alternative, word-based seg- mentor, which uses features based on com- plete words and word sequences. The gener- alized perceptron algorithm is used for dis- criminative training, and we use a beam- search decoder. Closed tests on the first and second SIGHAN bakeoffs show that our sys- tem is competitive with the best in the litera- ture, achieving the highest reported F-scores for a number of corpora. 1 Introduction Words are the basic units to process for most NLP tasks. The problem of Chinese word segmentation (CWS) is to find these basic units for a given sen- tence, which is written as a continuous sequence of characters. It is the initial step for most Chinese pro- cessing applications. Chinese character sequences are ambiguous, of- ten requiring knowledge from a variety of sources for disambiguation. Out-of-vocabulary (OOV) words are a major source of ambiguity. For example, a difficult case occurs when an OOV word consists of characters which have themselves been seen as words; here an automatic segmentor may split the OOV word into individual single-character words. Typical examples of unseen words include Chinese names, translated foreign names and idioms. The segmentation of known words can also be ambiguous. For example, “� � b” should be “� � (here) b (flour)” in the sentence “��b�s� 5” (flour and rice are expensive here) or “� (here) � b (inside)” in the sentence “� � b � �” (it’s cold inside here). The ambiguity can be resolved with information about the neighboring words. In comparison, for the sentences “= � � � � �”, possible segmentations include “= � (the discus- sion) � (will) � (very) � � (be successful)” and “=�� (the discussion meeting) � (very) �� (be successful)”. The ambiguity can only be resolved with contextual information outside the sentence. Human readers often use semantics, contextual in- formation about the document and world knowledge to resolve segmentation ambiguities. There is no fixed standard for Chinese word seg- mentation. Experiments have shown that there is only about 75% agreement among native speakers regarding the correct word segmentation (Sproat et al., 1996). Also, specific NLP tasks may require dif- ferent segmentation criteria. For example, “� � � L” could be treated as a single word (Bank of Bei- jing) for machine translation, while it is more natu- rally segmented into “� � …

Content truncated to 500 words