Discovering Morphological Paradigms from Plain Text Using a Dirichlet Process Mixture Model

Markus Dreyer, Jason EisnerEMNLP 2011 · OpenReview

Abstract: We present an inference algorithm that organizes observed words (tokens) into structured inflectional paradigms (types). It also naturally predicts the spelling of unobserved forms that are missing from these paradigms, and discovers inflectional principles (grammar) that generalize to wholly unobserved words. Our Bayesian generative model of the data explicitly represents tokens, types, inflections, paradigms, and locally conditioned string edits. It assumes that inflected word tokens are generated from an infinite mixture of inflectional paradigms (string tuples). Each paradigm is sampled all at once from a graphical model, whose potential functions are weighted finite-state transducers with language-specific parameters to be learned. These assumptions naturally lead to an elegant empirical Bayes inference procedure that exploits Monte Carlo EM, belief propagation, and dynamic programming. Given 50–100 seed paradigms, adding a 10-million-word corpus reduces prediction error for morphological inflections by up to 10%.

Introduction

In morphologically rich languages like German, Polish, or Finnish, a single verb can manifest in dozens or even hundreds of inflected forms (e.g., break, breaks, breaking, broke, broken). For standard Natural Language Processing (NLP) models, this diversity creates a massive data sparsity problem: a model might encounter "broken" frequently but never see "breaks," failing to recognize they represent the same underlying concept.

While previous work in unsupervised morphology focused on simple segmentation—splitting words into stems and suffixes—language is rarely so regular (consider "run" vs. "ran"). This paper, originally presented at EMNLP 2011, proposes a method to reconstruct the entire paradigm—the complete grid of possible forms for a lexeme—even when many of those forms are absent from the training corpus.

Methodology

The authors treat morphological discovery as a clustering task within a Bayesian framework, utilizing a Dirichlet Process Mixture Model (DPMM). This approach allows the model to assume an infinite potential lexicon, creating new clusters (lexemes) as it encounters novel word tokens in the text.

Figure 2: The model jointly learns to map corpus tokens to specific slots within structured paradigms in the lexicon.

The Generative Process

The model assumes a hierarchical generation process:

  1. Grammar Parameters: The language first establishes global grammar rules (parameters for string transformations).
  2. Lexemes and Paradigms: Abstract lexemes are selected, and a full paradigm of spellings is generated for each using a graphical model. The relationships between forms (e.g., lemma to past participle) are modeled via Weighted Finite-State Transducers (WFSTs) that learn specific edits like insertions or substitutions.
  3. Token Generation: Word tokens in a corpus are generated by sampling from these paradigms.

Inference

To learn from raw text, the system employs Collapsed Gibbs Sampling. The sampler iterates through the corpus, assigning word tokens to lexeme clusters and specific paradigm slots (e.g., 3rd person singular). Periodically, Monte Carlo EM updates the global grammar parameters based on the current state of the clusters. This creates a "rich get richer" effect where the model learns irregular forms for common verbs while applying general grammatical rules to rare or regular verbs.

Key Results

The model was evaluated using the WaCky corpus (German web-crawled text) and the CELEX morphological database. By providing a small number of "seed" paradigms (50–100), the model could leverage unlabeled text to significantly improve its predictive accuracy for missing forms.

Figure 4: Accuracy and edit distance improvements as corpus size increases from 0 to 10 million words.

As shown in the results table, adding a 10-million-word unlabeled corpus to 50 seed paradigms reduced prediction error by 10%, moving absolute accuracy from 89.9% to 90.9%. The corpus evidence was particularly effective for frequent, irregular verbs. For these words, the model uses corpus data to override general grammatical predictions (e.g., learning "broken" instead of a predicted regular form like "gebreaked"). Furthermore, the model showed improved generalization even for words never seen in the corpus, as the large-scale data helped refine the global grammar parameters ($\theta$).

Discussion and Limitations

While powerful, the model currently operates as a "bag of words," ignoring the surrounding sentence context that could help disambiguate forms (e.g., a word following "ich" is likely 1st person singular). Additionally, the computational cost of using WFSTs within a loopy belief propagation framework is high, presenting challenges for scaling to even larger datasets. Future work may also explore modeling phonology rather than just orthography to better capture the underlying sounds of morphological change.

Summary updated

Abstract

We present an inference algorithm that organizes observed words (tokens) into structured inflectional paradigms (types). It also naturally predicts the spelling of unobserved forms that are missing from these paradigms, and discovers inflectional principles (grammar) that generalize to wholly unobserved words. Our Bayesian generative model of the data explicitly represents tokens, types, inflections, paradigms, and locally conditioned string edits. It assumes that inflected word tokens are generated from an infinite mixture of inflectional paradigms (string tuples). Each paradigm is sampled all at once from a graphical model, whose potential functions are weighted finite-state transducers with language-specific parameters to be learned. These assumptions naturally lead to an elegant empirical Bayes inference procedure that exploits Monte Carlo EM, belief propagation, and dynamic programming. Given 50--100 seed paradigms, adding a 10-million-word corpus reduces prediction error for morphological inflections by up to 10%.
BibTeX
@inproceedings{dreyer2011discovering,
  author = {Markus Dreyer and Jason Eisner},
  title = {{Discovering Morphological Paradigms from Plain Text Using a Dirichlet Process Mixture Model}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
  url = {https://openreview.net/forum?id=HyVWqfMuZH},
}
Figure