Binary Tree based Chinese Word Segmentation

Kaixu Zhang, Can Wang, Maosong SunarXiv 2013 · OpenReview

TL;DR

This paper introduces a novel binary tree-based framework for Chinese word segmentation (CWS) that effectively addresses the "granularity mismatch" problem, a major source of errors. By representing potential segmentations at various granularities within a binary tree and then pruning it, the authors achieve significant error reductions, demonstrating up to a 20% improvement over state-of-the-art methods.

What Problem Does This Paper Address?

Chinese word segmentation (CWS) is a crucial preprocessing step for many Natural Language Processing (NLP) tasks involving Chinese text. Unlike languages with explicit word delimiters (like spaces), Chinese sentences are sequences of characters, and identifying word boundaries is inherently ambiguous. This ambiguity is exacerbated by the "granularity mismatch" problem: the definition of a "word" can vary. For instance, "老人" (old person) is a single word, while "老树" (old tree) might be segmented into "老" (old) and "树" (tree). This inconsistency between the desired segmentation granularity and the model's output is a primary cause of errors in CWS systems. Existing methods, often treating CWS as a sequence tagging problem, struggle to gracefully handle these varying granularity requirements.

Methods

The paper proposes a two-step framework built around a binary tree representation:

  1. Tree Building: A raw Chinese sentence is parsed into a binary tree. This initial tree doesn't aim to capture morphological or syntactic structure but rather represents all possible word boundary decisions at different levels. The splitting point at each node is determined by a confidence score (e.g., from a Conditional Random Field - CRF model) indicating the likelihood of a word boundary.
  2. Tree Pruning: This is the core step for addressing granularity. The binary tree is pruned using a "tree pruning function." The leaves of the pruned tree then form the final segmented output. This pruning step allows for explicit control over the granularity of the segmentation. The authors explore various pruning functions, including a simple threshold-based one and a more sophisticated Support Vector Machine (SVM)-based approach. The SVM-based pruning leverages features derived from CRF probabilities, word dictionaries, and association measures to make more informed pruning decisions.

The framework is designed to be flexible, allowing existing CWS methods (like dictionary-based, association-based, or sequence tagging methods) to be employed within the tree-building step.

Datasets

The experiments were conducted using four corpora from the SIGHAN bake-off 2005: AS, CityU, MSR, and PKU. These are standard benchmarks for Chinese word segmentation. The paper also discusses cross-corpus experiments, specifically "MSR to PKU" and "PKU to MSR," to evaluate performance when training and testing on different corpora, highlighting the impact of granularity mismatch in such scenarios.

Key Insights and Ideas

  • Binary Tree as a Granularity Repository: The binary tree structure is a powerful way to implicitly store all possible segmentations of a sentence at various granularities. This is a key insight that enables the focus on the granularity problem.
  • Pruning as Granularity Control: The tree pruning step directly addresses the granularity mismatch by allowing the system to select the desired level of segmentation. This is a more explicit and controllable approach than relying solely on the output of a single-model prediction.
  • Quantitative Error Analysis: The framework enables a new way to classify errors into "tree errors" (words not even present in the binary tree) and "pruning errors" (words present in the tree but removed by pruning). This distinction helps pinpoint the source of errors, with pruning errors being directly linked to granularity issues.
  • SVM for Sophisticated Pruning: Using an SVM for the pruning step, with carefully engineered features, significantly improves performance by making more nuanced decisions about which potential word boundaries to keep or discard.

Key Results

  • The proposed binary tree-based framework, when combined with a sophisticated SVM-based tree pruning function, achieved an error reduction of up to 20% compared to a state-of-the-art CRF-based baseline.
  • Error analysis revealed that granularity mismatch is the primary cause of errors in CWS, significantly outweighing "tree errors."
  • The oracle pruning function (which perfectly mimics the gold standard) showed that the upper bound of performance is very high, indicating that the proposed pruning approach can effectively close the gap to the ideal performance.
  • Cross-corpus experiments showed a significant performance drop due to granularity mismatch, which the proposed framework aims to mitigate.

Limitations and Future Work

  • Definition of Chinese Words: The paper acknowledges that the definition of a Chinese word is not always clear, even for linguists, and that disagreements exist between corpora (e.g., MSR vs. PKU), primarily concerning granularity.
  • Future Work: The authors suggest that their binary tree representation and framework can be extended to handle different granularity requirements for various applications (e.g., machine translation, information retrieval) by simply employing different tree pruning functions for different corpora or tasks. This offers a unified approach to CWS with adaptable granularity.

Summary updated

Abstract

Chinese word segmentation is a fundamental task for Chinese language processing. The granularity mismatch problem is the main cause of the errors. This paper showed that the binary tree representation can store outputs with different granularity. A binary tree based framework is also designed to overcome the granularity mismatch problem. There are two steps in this framework, namely tree building and tree pruning. The tree pruning step is specially designed to focus on the granularity problem. Previous work for Chinese word segmentation such as the sequence tagging can be easily employed in this framework. This framework can also provide quantitative error analysis methods. The experiments showed that after using a more sophisticated tree pruning function for a state-of-the-art conditional random field based baseline, the error reduction can be up to 20%.
BibTeX
@misc{zhang2013binary,
  author = {Kaixu Zhang and Can Wang and Maosong Sun},
  title = {{Binary Tree based Chinese Word Segmentation}},
  year = {2013},
  eprint = {1305.3981},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1305.3981},
}
Figure