Multiple Word Alignment with Profile Hidden Markov Models

Aditya Bhargava, Grzegorz KondrakNAACL 2009

TL;DR

This paper adapts Profile Hidden Markov Models (Profile HMMs), a technique from bioinformatics, for linguistic tasks like aligning sets of related words (cognates) and identifying which cognate set a new word belongs to. The authors demonstrate that Profile HMMs outperform traditional edit distance methods for these tasks, offering a more robust way to handle word-family relationships.

What Problem Does This Paper Address?

In linguistics, aligning words is crucial for tasks like historical language reconstruction and measuring dialectal differences. While methods exist for aligning pairs of words, aligning multiple related words simultaneously has been a challenge. Furthermore, classifying a word into its correct cognate set (a group of words with a common origin) is also important, especially when dealing with large datasets where manual classification is infeasible. Existing methods often rely on pairwise comparisons or handcrafted rules, which can be less effective for capturing the nuances of word families.

Methods

The core of this paper is the adaptation of Profile Hidden Markov Models (Profile HMMs) for linguistic applications. Profile HMMs, originally used in bioinformatics for aligning families of DNA or protein sequences, are extended here to handle sets of words.

Here's a breakdown of their approach:

  • Profile HMM Structure: A Profile HMM is built for a set of aligned sequences (in this case, words). It consists of states representing positions in the alignment:
  • Match states: Capture conserved characters (or phonemes) at a specific position. They have emission probabilities for each symbol in the alphabet.
  • Insert states: Account for characters that are inserted at a position and don't have a direct correspondence in other sequences.
  • Delete states: Represent characters that are deleted from a position. These are silent.
  • Begin/End states: Mark the start and end of the model.
  • Training: For multiple word alignment, a Profile HMM is constructed from an initial set of aligned cognates. The model is then trained using the Baum-Welch algorithm, which iteratively refines the transition and emission probabilities.
  • Alignment: Once trained, the Profile HMM can align new, unaligned sequences (words) to the model using the Viterbi algorithm.
  • Cognate Set Matching: For classifying a word into a cognate set, a Profile HMM is trained for each potential cognate set. The word is then scored against each model using the forward algorithm, and the set with the highest score is chosen.
  • Pseudocounts and Smoothing: To handle sparse data and avoid zero probabilities, the authors employ pseudocount methods. They investigate different strategies, including adding a constant value, incorporating background frequencies, and using substitution matrices derived from pairwise alignments. They also explore "smoothing during Baum-Welch" to help the algorithm escape local optima.

Datasets

The primary dataset used in this paper is the Comparative Indoeuropean Data Corpus (Dyen et al., 1992). This corpus contains word lists for 200 meanings across 95 Indoeuropean languages. The authors manually converted this data into disjoint sets of cognate words, ensuring each set contained only one word per language and removing words that were not cognate with any others.

  • Average cognate set size: 4.37 words.
  • Smallest cognate set size: 2 words.
  • Largest cognate set size: 84 words.
  • Average number of cognate sets per meaning: 10.92.

A development set of 10 meanings (approximately 5% of the data) was used for parameter tuning.

Key Insights and Ideas

  • Profile HMMs bridge the gap between pairwise and multiple alignment: By modeling a "profile" of an entire word family, Profile HMMs can capture shared patterns across multiple words more effectively than methods that only consider pairs.
  • Linguistic data can be treated like biological sequences: The paper demonstrates that the structural similarities between related words (cognates) and related biological sequences make Profile HMMs a suitable tool for linguistic analysis.
  • Pseudocounts are crucial for robustness: The choice and application of pseudocount methods significantly impact the performance, especially when dealing with limited or noisy linguistic data.
  • Substitution matrices enhance alignment quality: Incorporating knowledge from substitution matrices (which quantify similarity between characters) into the pseudocount calculation leads to better alignments.
  • Profile HMMs are more robust than edit distance baselines: Especially in the presence of duplicate words or when considering the entire set rather than just the closest word, Profile HMMs provide a more reliable measure of similarity.

Key Results

  • Multiple Cognate Alignment: The Profile HMM method produced "good-quality multiple cognate alignments." Figure 4 shows an example alignment for the meaning "day," where conserved characters are identified as match states. The authors note that the substitution matrix was key to identifying similar characters.
  • Cognate Set Matching:
    • The Profile HMM method achieved an accuracy of 93.2% in identifying the correct cognate set.
  • This significantly outperformed the average edit distance baseline, which achieved 77.0% accuracy.
  • The minimum edit distance baseline achieved 91.0% accuracy but was deemed less appropriate as it relies on a single word and is more susceptible to noise from duplicate words.

Limitations and Future Work

  • Phonetic Transcription: The authors acknowledge that using only English orthography can lead to difficulties in isolating phonemes, especially for digraphs. They suggest that using standard phonetic notation (like IPA) could improve results.
  • Initial Model Construction: Profile HMM training is sensitive to the initial model. The authors wish to explore more informed methods for constructing this initial model.
  • Domain Knowledge: For building models from unaligned sequences, incorporating domain knowledge is seen as a potential avenue for improvement.
  • Better Pseudocount Methods: Investigating more advanced pseudocount techniques is a future direction.
  • N-grams as Output Symbols: The possibility of using n-grams as output symbols is also mentioned as a potential enhancement.
  • Broader Applications: The success in cognate tasks suggests applicability to other word-related problems like named entity recognition in multilingual corpora.

Summary updated

BibTeX
@inproceedings{bhargava2009multiple,
  author = {Aditya Bhargava and Grzegorz Kondrak},
  title = {{Multiple Word Alignment with Profile Hidden Markov Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure