A Stochastic Finite-State Word-Segmentation Algorithm for Chinese

Richard Sproat, Chilin Shih, William Gale, Nancy ChangACL 1994 · DOI

Abstract

Chinese word segmentation is a fundamental challenge in natural language processing due to the lack of explicit word boundaries in written text. This paper presents a robust stochastic framework based on Weighted Finite-State Transducers (WFSTs) that integrates dictionary lookup with statistical models for personal names and morphological derivatives. By estimating word costs from a large corpus and employing class-based recognition for out-of-vocabulary items, the system achieves performance levels nearly indistinguishable from human inter-judge agreement.

Introduction

Unlike languages that use whitespace to delimit words, Chinese text is composed of a continuous sequence of characters (hanzi). This absence of explicit boundaries poses significant hurdles for tasks such as Text-to-Speech (TTS) synthesis and machine translation. The core difficulty lies not only in identifying known words but also in resolving ambiguities and handling out-of-vocabulary (OOV) items.

Specifically, the system must address:

  1. Homographs: Characters with multiple pronunciations depending on their lexical context.
  2. Morphological Derivatives: Productive word formations, such as the addition of the plural suffix men.
  3. Proper Names: An open set of personal and foreign names that cannot be exhaustively listed in a dictionary.

The authors propose that a purely deterministic dictionary-based approach is insufficient. Instead, a probabilistic model is required to "guess" the most likely segmentation based on statistical evidence.

Methodology: Weighted Finite-State Transducers

The proposed algorithm represents the Chinese lexicon and linguistic rules as a Weighted Finite-State Transducer (WFST). In this framework, a sentence is treated as a sequence of characters that can be mapped to various word sequences. Each transition in the transducer is assigned a "cost," typically the negative log probability of a word or character sequence. The optimal segmentation is determined by finding the least-cost path through the resulting lattice.

Figure 2: A word lattice representing multiple possible segmentations for a Chinese sentence, illustrating the ambiguity between 'Japanese' and 'Japan' + 'Essay'.

Stochastic Modeling and Name Recognition

Word costs are derived from a 20-million hanzi training corpus. To handle unseen personal names, the authors utilize "semantic radicals"—components of Chinese characters that often hint at their meaning. Using Good-Turing estimation, the model assigns lower costs to characters containing "pleasant" radicals (e.g., "GRASS" for plants) and higher costs to those with "unpleasant" ones (e.g., "RAT"), reflecting their likelihood of appearing in a name.

Furthermore, the system incorporates finite-state rules to manage morphological processes. For instance, the probability of novel plural forms is estimated using a bigram backoff model, allowing the system to recognize words it has never encountered in its training data.

Evaluation and Results

The system was evaluated against a set of 100 random sentences (4,372 hanzi) for general segmentation and 186 sentences (12,000 hanzi) for name identification. A key finding was the inherent subjectivity of the task; human judges often disagree on "correct" segmentation.

The stochastic (ST) model achieved an average agreement of 0.75 with human judges. This is remarkably close to the average inter-human agreement of 0.76, suggesting the model performs at a near-human level. In contrast, standard "greedy" heuristics, which simply select the longest possible dictionary match, performed significantly worse, particularly when faced with OOV names.

Regional Linguistic Conventions

An intriguing insight emerged from the analysis of human judge performance. Using multidimensional scaling, the researchers found that judges from Taiwan and Mainland China formed distinct clusters. This indicates that "correct" segmentation is not universal but is influenced by regional linguistic conventions and standards.

Figure 4: Multidimensional scaling plot showing the clustering of human judges by region (Taiwan vs. Mainland) and the relative positioning of different segmentation algorithms.

Conclusion and Future Directions

The stochastic WFST approach provides a robust and flexible framework for Chinese word segmentation. By treating segmentation as a probabilistic path-finding problem, the system effectively handles the complexities of OOV names and morphological variations.

Future work aims to transition from a unigram (zero-order) model to a bigram model to capture local dependencies between words, which is expected to further enhance accuracy. Additionally, more sophisticated models for foreign name transliteration are needed to account for the specific phonetic patterns prevalent in such strings.

Summary updated

BibTeX
@inproceedings{sproat1994stochastic,
  author = {Richard Sproat and Chilin Shih and William Gale and Nancy Chang},
  title = {{A Stochastic Finite-State Word-Segmentation Algorithm for Chinese}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1994},
  doi = {10.3115/981732.981742},
}
Figure