TL;DR
This paper explores using Minimum Description Length (MDL) for unsupervised Chinese word segmentation. While they achieve lower description lengths than prior work, surprisingly, this doesn't always translate to better segmentation accuracy. However, by incorporating simple linguistic constraints, they achieve state-of-the-art results.
What Problem Does This Paper Address?
Chinese, unlike many Western languages, doesn't use spaces to delineate words. This makes word segmentation, the process of identifying word boundaries, a crucial first step for many Natural Language Processing (NLP) tasks like parsing and part-of-speech tagging. While supervised methods (requiring manually segmented data) achieve high accuracy, they are labor-intensive. This paper focuses on unsupervised methods, aiming to achieve good segmentation without needing pre-labeled data, making it more adaptable and cost-effective. The core challenge is finding an objective criterion that reliably identifies meaningful word boundaries in the absence of explicit markers.
Methods
The paper builds upon two key concepts: Branching Entropy (BE) and Minimum Description Length (MDL).
- Branching Entropy (BE): This measures the uncertainty of what character or sequence of characters might follow a given string. High BE suggests a potential word boundary because the context becomes more diverse. The authors use a variation called Variation of Branching Entropy (VBE) and a normalized version called "autonomy" as an initial scoring mechanism.
- Minimum Description Length (MDL): This principle suggests that the best model for a dataset is the one that allows for the most compact representation of that data. In word segmentation, a good segmentation should allow the corpus to be encoded more efficiently (shorter description length) using a lexicon and codes for words.
The authors propose a two-stage approach:
- Initialization: They use an algorithm based on maximizing word "autonomy" (derived from VBE) to get an initial segmentation.
- MDL Minimization: They then iteratively refine this segmentation by applying changes (merging or splitting boundaries) that reduce the Description Length. This step explores a larger hypothesis space than previous MDL-based methods.
Crucially, they also introduce a constrained MDL approach. Recognizing that pure MDL can sometimes lead to suboptimal segmentations (e.g., merging common phrases that should be separate words), they incorporate simple linguistic knowledge:
- Limiting the length of merged units to avoid over-segmenting common multi-word expressions.
- Using a closed list of function words to prevent them from being merged with content words.
- Preventing splits of common bigrams.
Datasets
The evaluation uses corpora from the 2005 Chinese Word Segmentation Bake off. These include:
- Peking University Corpus (PKU)
- LIVAC Corpus (City-U)
- Microsoft Research (MSR)
- Balanced Corpus of the Academia Sinica (AS)
These corpora are pre-segmented according to four different guidelines, allowing for a robust evaluation of unsupervised methods against various "gold standards."
Key Insights and Ideas
- MDL doesn't guarantee better segmentation: A surprising finding is that simply minimizing the Description Length doesn't automatically lead to higher f-scores (a measure of segmentation accuracy). This suggests that the MDL criterion, while theoretically sound for compression, might not perfectly align with human linguistic intuition for word boundaries in all cases.
- Exploration vs. Optimization: The authors' MDL approach explores a larger search space, leading to lower DL. However, this broader exploration might sometimes find segmentations that are "too good" at compressing the data but linguistically less meaningful.
- The power of simple constraints: The most significant insight is that incorporating minimal, low-cost linguistic knowledge (like common function words or typical word lengths) can dramatically improve segmentation accuracy, even when using an MDL-based approach. This highlights a practical trade-off between pure unsupervised learning and incorporating domain-specific, albeit simple, rules.
- MDL as a search driver, not an end-all: MDL proves effective in guiding the search for better segmentations, especially when combined with a good initialization strategy and constraints.
Key Results
- The base system (initialization + MDL minimization) achieved lower Description Lengths than previous methods, including Zhikov et al. (2010).
- However, the f-scores for the base system were sometimes lower than the initialization step alone, and often lower than Zhikov et al.'s full algorithm.
- The constrained MDL system significantly improved performance, achieving state-of-the-art results on the evaluated corpora. For example, on the PKU corpus, the constrained system achieved an f-score of 0.832, compared to 0.808 for Zhikov et al.'s best result.
- The constrained system also maintained competitive Description Lengths, often comparable to or slightly higher than the unconstrained MDL approach, but with much better accuracy.
Limitations and Future Work
- Multi-Word Expressions (MWEs): The paper acknowledges that their constrained system has to actively prevent the detection of MWEs (like named entities) to achieve higher f-scores. This raises a question about whether the task definition or the system's limitations are at play. Future work could explore better ways to handle MWEs.
- Content vs. Grammatical Words: The distinction between content words (where MDL might be more useful due to vastness) and grammatical words (where simple rule-based approaches are effective) is highlighted. Future work could leverage this division of labor more effectively.
- Exploration of Search Space: While their MDL approach explores a larger space, the authors note that changing segmentation decisions can have cascading effects on neighboring positions, making the process computationally intensive. Further optimization of the search algorithm is a potential area for future research.
Summary updated