Paradigm Clustering with Weighted Edit Distance

Andrew Gerlach, Adam Wiemerslage, Katharina KannACL 2021

TL;DR

This paper tackles the challenge of unsupervised morphological paradigm clustering, aiming to group inflected word forms by their underlying lemma without any labeled data. The authors propose a novel approach combining orthographic and semantic similarity metrics, showing promising results that, while not outperforming the baseline due to time constraints, demonstrate strong potential for improvement with further development.

What Problem Does This Paper Address?

Many languages express grammatical nuances like tense or case through changes to a word's form (morphological inflection). The base form of a word is its lemma. While English has relatively simple inflectional systems (e.g., "do" -> "did"), other languages like Basque can have hundreds of inflected forms for a single lemma. Automatically identifying these related word forms is crucial for Natural Language Processing (NLP) systems, especially for low-resource languages where annotated data is scarce or non-existent. This paper addresses the SIGMORPHON 2021 Shared Task on Unsupervised Morphological Paradigm Clustering, which specifically asks participants to group inflected forms into paradigms using only raw text. This is a foundational step towards unsupervised morphological paradigm completion, where systems learn to generate full paradigms from limited examples.

Methods

The core of the proposed system is an agglomerative clustering approach. This means words are initially placed in their own clusters, and then the closest clusters are merged iteratively until a stopping criterion is met. The novelty lies in the distance metric used to determine cluster closeness. This metric is a combination of two components:

  • Orthographic Distance: This measures the surface-level similarity between words. The authors experiment with two variations of an edit distance metric. Specifically, they use the Jaro-Winkler (JW) edit distance, which gives more weight to matching characters at the beginning of strings (useful for suffixing languages). They also explore a simplified variant of the string to reduce the impact of affixes.
  • Semantic Distance: This captures the meaning similarity between words. The authors leverage fastText embeddings to represent words in a vector space, and the cosine similarity between these embeddings is used to quantify semantic relatedness.

A key innovation is the LM-weighted Edit Distance. Instead of using standard edit distance costs, they train a character-level LSTM language model on the corpus. This model learns the probability of character sequences. The costs for edit operations (insertion, deletion, substitution) are then derived from these probabilities, aiming to give more weight to differences in the word stem and less to affixes. They found that training the LM in a backward direction (LM-B) yielded better results, suggesting it better captures suffix information.

Datasets

The primary dataset used is the JHU Bible corpora. The organizers also provide development and test sets consisting of gold clusters for a subset of words within these corpora. These gold clusters are derived from the UniMorph database. The development languages included Maltese, Persian, Portuguese, Russian, and Swedish. The test languages were Basque, Bulgarian, English, Finnish, German, Kannada, Navajo, Spanish, and Turkish.

Key Insights and Ideas

  • Combining Orthography and Semantics is Powerful: The paper highlights that a hybrid approach, considering both how words look and what they mean, is a robust strategy for morphological clustering.
  • LM-weighted Edit Distance Shows Promise: Using a language model to inform edit distance costs is a clever way to bias the similarity measure towards stem differences, which is crucial for identifying inflectional relationships.
  • Backward LM is Key for Suffixes: The finding that a backward-trained LM (LM-B) outperforms a forward-trained one (LM-F) for this task strongly suggests that capturing suffix information is critical for many languages, and a backward model is better suited for this.
  • Time Constraints Hurt Performance: The authors explicitly state that their submissions did not outperform the baseline due to time limitations, particularly in not processing the full vocabulary. This implies that their methods have significant room for improvement.
  • Precision vs. Recall Trade-off: The results show a clear trade-off. Their systems achieved high precision but low recall, likely because they only clustered a subset of words. The baseline, conversely, had high recall but low precision, suggesting it over-clustered.

Key Results

  • The proposed systems achieved an average F1 score of 0.328 (JW-based) and 0.327 (LM-based) on the test set, compared to the baseline's 0.334. While slightly lower, this is considered comparable given the constraints.
  • The LM-based clustering system outperformed the JW-based system on Basque (higher precision), which is an agglutinating language with long affixes.
  • Conversely, the JW-based system outperformed the LM-based one on English, a language with simpler, strictly suffixing inflection. This suggests the JW system's heuristics are well-suited for such languages.
  • The authors note that their systems achieved high average precision (around 0.646), indicating that the words they did cluster were grouped accurately. The low recall was attributed to only considering words appearing at least 5 times in the corpus.
  • Appendix results with the full dataset for selected languages showed significant improvements in F1 (e.g., Basque F1 increased from 0.330 to 0.435), with increased recall but decreased precision, confirming the hypothesis about the subsetting constraint.

Limitations and Future Work

  • Subset Processing: The most significant limitation acknowledged is that the systems only processed a subset of the corpus vocabulary due to time constraints. This directly impacted recall.
  • Threshold Sensitivity: The authors suggest that the performance of their systems might be sensitive to the chosen threshold for clustering.
  • Prefixing Languages: The paper notes that the development languages were not prefixing, and a method to automatically distinguish prefixing vs. suffixing languages from raw text would be beneficial for choosing the right LM direction.
  • Future Work: The authors imply that removing time constraints and processing the full vocabulary would lead to significant improvements. Further exploration into optimizing the LM training and the combination of orthographic and semantic metrics is also suggested. Developing a method to automatically identify prefixing languages would also be valuable.

Summary updated

BibTeX
@inproceedings{gerlach2021paradigm,
  author = {Andrew Gerlach and Adam Wiemerslage and Katharina Kann},
  title = {{Paradigm Clustering with Weighted Edit Distance}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure