A Bottom-up Merging Algorithm for Chinese Unknown Word Extraction

Wei-Yun Ma, Keh-Jiann ChenSIGHAN 2003 · OpenReview

TL;DR

This paper introduces a novel bottom-up merging algorithm for Chinese unknown word extraction, addressing the common issue of over-extracting superfluous character strings. By combining general morphological rules with linguistic and statistical constraints, and employing a priority-based merging strategy, the algorithm achieves promising performance in identifying and extracting previously unseen words in Chinese text.

What Problem Does This Paper Address?

Chinese, unlike many Western languages, lacks explicit word delimiters (spaces) in its written form. This makes word segmentation—the process of identifying word boundaries—a fundamental and challenging task. A significant hurdle in word segmentation is the presence of "unknown words" (UW), words not present in the system's lexicon. These unknown words can severely degrade the performance of segmentation systems. While methods exist for extracting these unknown words, a common problem is the over-extraction of character sequences that exhibit strong statistical associations but are not actual words, leading to noisy results. This paper aims to improve the precision of unknown word extraction by developing a more robust algorithm that can differentiate true unknown words from spurious character combinations.

Methods

The proposed approach combines several key ideas:

  • General Morphological Rules: Instead of relying solely on statistical methods, the paper uses a set of general, context-free grammar rules to model the structure of unknown words. These rules are designed to be broad, capturing a wide range of potential unknown word formations.
  • Constraints and Priorities: To combat the over-generation from broad rules, linguistic and statistical constraints are appended to them. Furthermore, a priority measure is introduced to dynamically decide which rule should be applied first during the extraction process. This priority is calculated based on the association strength of the right-hand side symbols of the rules.
  • Bottom-up Merging Algorithm: The core of the paper is a bottom-up merging algorithm. It starts with an initially segmented sentence, identifies potential unknown word morphemes, and then recursively merges adjacent tokens based on the general rules, their constraints, and their assigned priorities. This merging continues until no further rule applications are possible. This iterative merging process allows for the extraction of unknown words of potentially unlimited length.
  • Unknown Word Detection: Prior to extraction, an unknown word detection stage is employed. This stage uses syntactic discriminators, learned from a corpus, to identify monosyllabic morphemes that are likely part of unknown words.

Datasets

  • Training Data: The Sinica balanced corpus version 3.0 (5 million segmented words) was used for training the unknown word detection component.
  • Testing Data: 150 documents of Chinese news from the internet were randomly selected for testing. These documents were manually segmented according to a standard for information processing. Each testing text contained an average of 300 words and 16.6 unknown word types.

Key Insights and Ideas

  • Balancing Generality and Selectivity: The paper highlights the inherent trade-off between the generality (recall) and selectivity (precision) of rules. Broad rules increase recall but decrease precision, while narrow rules do the opposite. The strategy of using general rules with appended constraints is a key insight for managing this trade-off.
  • Priority-based Merging: The dynamic decision-making through rule priorities is crucial for resolving ambiguities and guiding the bottom-up merging process effectively. This prevents the algorithm from getting stuck in suboptimal merges.
  • Co-occurrence as a Strong Priority Measure: The experiments suggest that co-occurrence measures are more effective than pure mutual information for prioritizing rule applications in unknown word extraction. This is because unknown words might share morphemes, leading to lower MI values for individual words, while co-occurrence better captures the likelihood of adjacent elements forming a word.
  • Bottom-up Approach for Complex Ambiguities: The bottom-up merging strategy is shown to be effective in handling not only simple overlapping ambiguities but also more complex coverage ambiguities that can arise from consecutive unknown words.

Key Results

The paper reports promising experimental results:

  • The unknown word detection stage achieved a detection rate of 96% and a precision of 60%.
  • The bottom-up merging algorithm, when evaluated with different priority measures, achieved a recall of around 45% and a precision of approximately 75%.
  • Comparing priority measures, co-occurrence and t-score performed slightly better than mutual information (MI), achieving around 75% precision and 45% recall.
  • The general rules, when used in conjunction with morphological rules, significantly improved recall by 32% compared to using only morphological rules for specific categories like names and compounds, without a substantial loss in precision.

Limitations and Future Work

  • Unknown Word Detection Performance: The authors acknowledge that the performance of the entire system is significantly influenced by the initial unknown word detection stage. While its precision is 60%, there is room for improvement.
  • Future Work: The authors suggest exploring more advanced statistical methods for detection, such as Support Vector Machines (SVM) and Maximal Entropy models. They also propose incorporating textual semantic relations and using updated statistical methods to achieve better unknown word detection performance.

Summary updated

BibTeX
@inproceedings{ma2003bottom,
  author = {Wei-Yun Ma and Keh-Jiann Chen},
  title = {{A Bottom-up Merging Algorithm for Chinese Unknown Word Extraction}},
  booktitle = {SIGHAN},
  year = {2003},
  url = {https://openreview.net/forum?id=_qEXWCw2Eq5},
}
Figure