Abstract
We introduce factored language models (FLMs) and generalized parallel backoff (GPB). An FLM represents words as bundles of features (e.g., morphological classes, stems, data-driven clusters, etc.), and induces a probability model covering sequences of bundles rather than just words. GPB extends standard backoff to general conditional probability tables where variables might be heterogeneous types, where no obvious natural (temporal) backoff order exists, and where multiple dynamic backoff strategies are allowed. These methodologies were implemented during the JHU 2002 workshop as extensions to the SRI language modeling toolkit. This paper provides initial perplexity results on both CallHome Arabic and on Penn Treebank Wall Street Journal articles. Significantly, FLMs with GPB can produce bigrams with significantly lower perplexity, sometimes lower than highly-optimized baseline trigrams. In a multi-pass speech recognition context, where bigrams are used to create first-pass bigram lattices or N-best lists, these results are highly relevant.
Introduction
Traditional statistical language models (LMs) typically predict the next word based on a fixed history of preceding words, usually the last two in a trigram model. This approach faces two major hurdles: data sparsity and atomic representation. Data sparsity occurs when word sequences in the test set never appeared in the training data, requiring the model to "back off" to shorter histories. Atomic representation treats different morphological forms of the same root (e.g., "run," "runs," "running") as completely unrelated entities. This is particularly problematic for morphologically rich languages like Arabic, where a single root can take hundreds of forms, making it nearly impossible to observe every version enough times to build a reliable model.
Methodology
The paper proposes two interconnected innovations to address these challenges: Factored Language Models and Generalized Parallel Backoff.
Factored Language Models (FLMs)
Instead of treating a word $w_t$ as an atomic unit, an FLM represents it as a vector of factors $f_t^{1:K}$. These factors can include the word itself, its stem, its morphological class, or data-driven clusters. The goal is to find a probability distribution $p(f|f_1, f_2, \dots, f_N)$ that best predicts the current factor bundle based on previous ones.
Generalized Parallel Backoff (GPB)
In a standard word model, backoff is simple: if a trigram is unseen, the model drops the oldest word. In an FLM, there is no "natural" order for dropping factors. GPB introduces the backoff graph, which allows the model to explore multiple paths, combine them in parallel (e.g., averaging results), or dynamically select the best path at run-time based on statistical reliability.
Experimental Results
The authors evaluated their methods on two distinct corpora: CallHome Arabic (spontaneous telephone conversations) and the Penn Treebank (Wall Street Journal).
CallHome Arabic
Arabic was chosen because its complex morphology makes it an ideal candidate for factored modeling. The results demonstrate that FLMs with GPB significantly reduce perplexity. Notably, a GPB-FLM bigram achieved a perplexity of 167, nearly matching the performance of a highly optimized baseline trigram (173) while using less temporal history.
English (WSJ)
Even in "morphologically simple" languages like English, factors provide significant predictive power. Using POS tags and word classes, a GPB-FLM bigram achieved a perplexity of 266, significantly closing the gap toward the baseline trigram (258) compared to the baseline bigram (320).
Conclusion
FLMs and GPB offer a flexible framework for incorporating linguistic structure into language modeling. By breaking the rigid temporal backoff rules and treating words as feature bundles, these models achieve superior performance, particularly in data-sparse or morphologically rich environments. While computational complexity in calculating backoff weights presents a trade-off, the gains in perplexity—especially for first-pass decoding in speech recognition—are substantial. Future work will focus on automated structure learning for optimal backoff graphs.
Summary updated