Abstract: Grzegorz Chrupala. Proceedings of 5th International Joint Conference on Natural Language Processing.
2011.
Introduction
In Natural Language Processing (NLP), grouping words into classes based on their distributional properties is a fundamental technique for improving model generalization. For decades, the Brown clustering algorithm has served as the industry standard. However, it suffers from two significant limitations: it produces "hard" assignments where each word belongs to exactly one cluster, and its computational complexity scales quadratically with the number of classes ($K$). This paper proposes using Latent Dirichlet Allocation (LDA) to induce "soft," probabilistic word classes, offering both better handling of ambiguity and superior computational efficiency.
Methodology: LDA for Word Class Induction
The authors re-frame the word class induction problem to fit the LDA framework, which is traditionally used for topic modeling. In this adaptation:
- Documents are represented by individual word types (e.g., the word "Krzysztof").
- Words within these documents are the context features—specifically, the immediate left and right neighbors—observed for that word type across a large corpus.
- Topics correspond to the induced word classes.
By applying LDA to this configuration, the model generates a probability distribution over classes for every word type. This allows for "soft" clustering, where a single word can belong to multiple classes simultaneously. Furthermore, because LDA can be implemented with efficient inference techniques like Gibbs sampling, its complexity scales linearly with the number of classes.
Results: Efficiency and Scalability
The most immediate advantage of the LDA approach is its scalability. While Brown clustering becomes prohibitively slow as the number of desired classes increases, LDA maintains a manageable runtime.
As shown in the figure above, for 1,000 classes, the Brown algorithm required over 110 hours of computation. In contrast, the LDA-based method completed the same task in just 4 hours. This efficiency enables researchers to explore much finer-grained word representations than were previously practical.
Performance and Ambiguity Handling
Beyond speed, the probabilistic nature of LDA provides a qualitative advantage in handling linguistic ambiguity. Hard clustering algorithms like Brown's must force every word into a single category, which is problematic for polysemous words or names that serve multiple roles.
The pie charts illustrate how LDA captures the multi-faceted nature of words. Names like "Martin" and "Cameron" are assigned to several classes, reflecting their potential use as first names, last names, or components of geographical entities.
In downstream evaluations, these LDA-induced features consistently outperformed Brown clusters. On Named Entity Recognition (NER) tasks, 200 LDA classes achieved better results than 1,000 Brown classes. In Semantic Relation Classification, the inclusion of LDA word classes provided an error reduction equivalent to doubling the amount of training data.
Conclusion
This work demonstrates that LDA is a highly effective alternative to traditional clustering methods for word class induction. By providing a probabilistic framework that scales linearly, it allows for the creation of nuanced, high-capacity word representations that significantly enhance the performance of various NLP tasks while drastically reducing computational overhead.
Summary updated