High-Performance, Language-Independent Morphological Segmentation

Sajib Dasgupta, Vincent NgNAACL 2007

TL;DR

This paper introduces a novel unsupervised morphological segmentation algorithm that achieves robust performance across languages with varying morphological complexity. By incorporating techniques for detecting incorrect morpheme attachments and inducing orthographic rules and allomorphs, the algorithm significantly outperforms existing methods, particularly on challenging agglutinative languages.

What Problem Does This Paper Address?

Morphological analysis, the task of breaking words into their smallest meaningful units (morphemes), is crucial for many natural language processing tasks. Traditional approaches rely on manually crafted rules, which are labor-intensive and language-specific. While unsupervised methods have emerged, they often struggle with languages exhibiting complex morphology (like Turkish or Finnish) and fail to generalize well across different linguistic structures. Specifically, existing unsupervised parsers often incorrectly segment words by:

  • Incorrectly attaching morphemes: For example, segmenting "candidate" as "candid" + "ate" when "ate" is not a valid suffix for "candid."
  • Failing to handle root changes: Words like "denial" (from "deny" + "al") are often mis-segmented as "deni" + "al" because the root "deny" changes to "deni."
  • Not generalizing across languages: Algorithms that perform well on English often fail on highly agglutinative languages.

This paper aims to bridge this gap by developing a single, unsupervised algorithm that can effectively segment words across a diverse range of languages, addressing these specific segmentation challenges.

Methods

The proposed algorithm builds upon existing unsupervised morpheme induction techniques and introduces several key innovations:

  • Basic Morpheme Induction: This initial step involves identifying candidate prefixes, suffixes, and roots from an unannotated corpus. It uses a simple idea of checking for character sequences that appear as both a word and a part of another word to identify potential affixes.
  • Detecting Incorrect Attachments:
    • Relative Corpus Frequency: This technique leverages the observation that inflected or derived forms of a word often occur less frequently than the root itself. By comparing the frequency of a word to its potential root, the algorithm can identify implausible attachments (e.g., if "candidate" is much more frequent than "candid," the attachment of "ate" is deemed incorrect).
  • Suffix Level Similarity: This method addresses cases where frequency alone isn't sufficient. It checks if a word also combines with suffixes that are morphologically similar to the proposed suffix. If a word only combines with a proposed suffix but not with its similar counterparts, the attachment is considered incorrect.
  • Inducing Orthographic Rules and Allomorphs: This is a significant contribution. The algorithm automatically learns rules that account for spelling changes when roots combine with suffixes (e.g., "deny" becoming "deni" before "al"). It focuses on changes at morpheme boundaries and learns rules for edit distance 1 changes (insertions, deletions, replacements). This allows the system to correctly segment words like "denial" by recognizing the allomorphic variation of the root.
  • Composite Suffix Detection: The algorithm identifies and removes composite suffixes (e.g., "ers" from "er" + "s") to prevent under-segmentation.

The final segmentation process involves generating all possible segmentations and then applying a series of tests to prune them down to the most likely one, considering linguistic constraints and morpheme strengths.

Datasets

The paper evaluates its algorithm on several datasets:

  • English: A vocabulary of approximately 60,000 distinct words was created from the Wall Street Journal and BLLIP corpora. A test set of 5,000 words was prepared, with segmentations largely adopted from CELEX and cross-checked with Merriam-Webster.
  • Bengali: A vocabulary of 140,000 words was generated from the Bengali newspaper Prothom Alo. A test set of 5,000 words was hand-segmented by linguists.
  • PASCAL Challenge Datasets: The algorithm was also evaluated on the PASCAL Challenge datasets for English, Finnish, and Turkish. These datasets consist of gold standards for evaluating unsupervised word segmentation.

Key Insights and Ideas

  • Frequency Disparity as a Signal: The simple idea that derived/inflected forms are less frequent than roots is a surprisingly effective heuristic for detecting incorrect morpheme attachments, especially when combined with a threshold.
  • Learning Orthographic Rules is Crucial: The ability to automatically learn and apply rules for root changes (allomorphy) is essential for achieving high performance, particularly in morphologically rich languages. This moves beyond simple segmentation to understanding word formation.
  • Language Independence through General Techniques: The core techniques (frequency analysis, similarity metrics, rule induction) are designed to be general and not tied to specific linguistic features, enabling performance across diverse languages.
  • Incremental Improvement: The paper demonstrates that adding each new technique (relative frequency, suffix similarity, allomorph detection) to the basic morpheme induction algorithm leads to significant performance gains, highlighting the synergistic effect of these components.

Key Results

The algorithm demonstrates strong performance across multiple languages:

  • English and Bengali: The proposed algorithm outperforms existing systems like Goldsmith's Linguistica and Creutz and Lagus's Morphessor on both English and Bengali in terms of exact accuracy and F-score.
  • PASCAL Challenge: The algorithm achieves competitive results on the PASCAL Challenge datasets for English, Finnish, and Turkish. It outperforms the PASCAL winner for English and shows comparable or better performance than other top systems across all three languages.
  • Contribution of Techniques: The paper shows that relative corpus frequency and allomorph detection contribute most significantly to performance improvements. The "Complete" system (with all three additions) consistently achieves the best results. For example, on English, the Complete system achieved an F-score of 79.4%, outperforming the PASCAL winner by 2.6%.

Limitations and Future Work

  • Edit Distance 1 for Rules: The orthographic rule induction is currently limited to edit distance 1 changes. The paper acknowledges that more complex changes might require further investigation.
  • Suffixal Attachments and Frequency Hypothesis: The hypothesis that derived forms are less frequent than roots holds better for Bengali (83.6% accuracy) than English (71.7%), particularly failing on suffixal attachments in English and verbs in Bengali. This suggests that while useful, it's not a perfect rule.
  • Future Work: The authors suggest extending the orthographic rule induction to handle more complex changes and exploring further improvements for languages where the frequency hypothesis is less effective. The paper also notes the potential for inducing out-of-vocabulary (OOV) roots, which is particularly relevant for languages like Bengali.

Summary updated

BibTeX
@inproceedings{dasgupta2007high,
  author = {Sajib Dasgupta and Vincent Ng},
  title = {{High-Performance, Language-Independent Morphological Segmentation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
}
Figure