A Two-stage Statistical Word Segmentation System for Chinese

Guohong Fu, Kang-Kwong Luke

TL;DR

This paper introduces a two-stage system for Chinese word segmentation, tackling the persistent challenges of ambiguity and unknown words. It first segments known words using a bigram model and then employs a hybrid approach combining word juncture, formation patterns, and contextual information to identify unknown words, achieving competitive results on a standard benchmark.

What Problem Does This Paper Address?

Chinese, unlike many Western languages, does not use explicit spaces to delineate words. This makes word segmentation – identifying the boundaries between words in a continuous string of characters – a fundamental and challenging task in Chinese Natural Language Processing (NLP). While significant progress has been made, two core problems persist:

  1. Ambiguity Resolution: A sequence of characters can often be segmented into words in multiple valid ways. For instance, "北京大学" (Beijing University) could be mistakenly segmented as "北京/大学" (Beijing/University) or even "北/京/大/学" (North/Capital/Big/Study).
  2. Unknown Word Identification (Out-of-Vocabulary - OOV): New words, proper nouns, or technical terms constantly emerge and are not present in the system's predefined dictionary. Identifying and correctly segmenting these unknown words is crucial for practical applications.

This paper aims to build a robust system that effectively handles both these issues.

Methods

The proposed system employs a two-stage approach:

  1. Stage 1: Known Word Segmentation:
    • Word Bigram Model: This stage leverages a statistical model that predicts the probability of a word appearing given the previous word. This is a standard technique for capturing local word dependencies.
  2. Viterbi Algorithm: This dynamic programming algorithm is used to find the most probable sequence of words (segmentation) that maximizes the overall probability calculated by the bigram model.
  3. Stage 2: Unknown Word Identification: This stage is designed to handle words not found in the system's dictionary. It uses a hybrid algorithm that combines three key components:
  4. Word Juncture Model: This model assesses the likelihood of two adjacent known words forming a new, unknown word. It considers the "affinity" of word pairs, essentially learning which pairs are more likely to merge.
  5. Word-Formation Patterns: This component analyzes how known words contribute to the formation of unknown words. It assigns probabilities based on whether a known word acts as the beginning, middle, end, or sole component of an unknown word. For example, certain characters might be more likely to appear at the end of a word.
  6. Contextual Information: The system also incorporates the left and right contextual words (WL, WR) surrounding a potential unknown word fragment.
  7. Simple Superposition Principle: To avoid complex normalization across different model dimensions, the probabilities from these three components are simply added together.
  8. Viterbi Algorithm (again): After generating candidate segmentations involving unknown words, the Viterbi algorithm is reapplied to find the best segmentation that maximizes the combined score from the juncture, formation, and bigram models.

Datasets

  • Training Data: Peking University corpora (specific details not fully elaborated, but used for training both known and unknown word models).
  • Evaluation Data: Peking University corpora (used for testing).
  • Lexicons:
    • Closed Test: A dictionary compiled from the training corpus, containing 55,226 words.
  • Open Test: A larger dictionary containing 65,269 words.

The paper mentions participation in the "First International Chinese Word Segmentation Bakeoff" and evaluation on the "PKU corpora," which are standard benchmarks in the field.

Key Insights and Ideas

  • Two-Stage Sufficiency: The paper demonstrates that a two-stage approach, separating known and unknown word handling, can be effective. The first stage efficiently handles the majority of text, leaving the more complex unknown word problem for the second stage.
  • Hybrid for OOV: Combining word juncture, word-formation patterns, and contextual information in a hybrid model is crucial for robust unknown word identification. This multi-faceted approach allows the system to capture different linguistic cues that signal the presence of new words.
  • Simplicity in Combination: The use of a "simple superposition principle" for merging different model scores highlights a pragmatic approach to combining diverse linguistic features without overly complex mathematical formulations.
  • Character-Based vs. Word-Based: The authors explicitly contrast their word-based approach to OOV identification with previous character-based methods, arguing that their system can handle unknown words composed of multiple known words, not just single characters.

Key Results

  • Overall Performance: The system achieved a high F-score of 0.939 in the closed test and 0.937 in the open test.
  • OOV Handling: The recall on OOV words was 67.5% in the closed test and 76.2% in the open test, indicating a good capability to identify unknown words.
  • Segmentation Speed: The system is efficient, processing approximately 531,925-556,182 characters per minute on an ACER notebook.
  • Stability: The performance remained stable between closed and open tests, with only a minor drop in F-measure (0.2%) despite an increase in OOV rate.

Limitations and Future Work

  • Data Sparseness Simplification: To mitigate data sparseness, the system does not differentiate between known and unknown words when estimating word juncture and formation models. This simplification might introduce noise and affect the precision of OOV identification.
  • Independent Stages: Treating known word segmentation and unknown word identification as independent stages can lead to errors when the input contains a mixture of ambiguities and unknown words. For example, an initial incorrect segmentation of a known word fragment might prevent the unknown word identification stage from correctly identifying a multi-word unknown entity.
  • OOV Precision: The precision on OOV words is noted as being relatively low (67.1% closed, 72.5% open), meaning the system may incorrectly identify some known words as unknown.
  • Future Work: The authors suggest improving strategies for estimating word juncture and formation models and developing an integrated segmentation technique that can perform both known word segmentation and unknown word identification simultaneously, rather than in separate stages.

Summary updated

BibTeX
@inproceedings{fu2003two,
  author = {Guohong Fu and Kang-Kwong Luke},
  title = {{A Two-stage Statistical Word Segmentation System for Chinese}},
  booktitle = {SIGHAN},
  year = {2003},
  doi = {10.3115/1119250.1119273},
}
Figure