A Spectral Algorithm for Learning Class-Based $n$-gram Models of Natural Language

Karl Stratos Columbia University, Do-kyum Kim, Daniel Hsu Columbia University, Michael Collins Columbia University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:745-754, 2014.

Abstract

The Brown clustering algorithm (Brown et al., 1992) is widely used in natural language process- ing (NLP) to derive lexical representations that are then used to improve performance on vari- ous NLP problems. The algorithm assumes an underlying model that is essentially an HMM, with the restriction that each word in the vocab- ulary is emitted from a single state. A greedy, bottom-up method is then used to find the clus- tering; this method does not have a guarantee of finding the correct underlying clustering. In this paper we describe a new algorithm for clustering under the Brown et al. model. The method relies on two steps: first, the use of canonical correla- tion analysis to derive a low-dimensional repre- sentation of words; second, a bottom-up hierar- chical clustering over these representations. We show that given a sufficient number of training examples sampled from the Brown et al. model, the method is guaranteed to recover the correct clustering. Experiments show that the method recovers clusters of comparable quality to the al- gorithm of Brown et al. (1992), but is an order of magnitude more efficient.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14u, title = {A Spectral Algorithm for Learning Class-Based $n$-gram Models of Natural Language}, author = {University, Karl Stratos Columbia and Kim, Do-kyum and University, Daniel Hsu Columbia and University, Michael Collins Columbia}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {745--754}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14u/university14u.pdf}, url = {https://proceedings.mlr.press/r12/university14u.html}, abstract = {The Brown clustering algorithm (Brown et al., 1992) is widely used in natural language process- ing (NLP) to derive lexical representations that are then used to improve performance on vari- ous NLP problems. The algorithm assumes an underlying model that is essentially an HMM, with the restriction that each word in the vocab- ulary is emitted from a single state. A greedy, bottom-up method is then used to find the clus- tering; this method does not have a guarantee of finding the correct underlying clustering. In this paper we describe a new algorithm for clustering under the Brown et al. model. The method relies on two steps: first, the use of canonical correla- tion analysis to derive a low-dimensional repre- sentation of words; second, a bottom-up hierar- chical clustering over these representations. We show that given a sufficient number of training examples sampled from the Brown et al. model, the method is guaranteed to recover the correct clustering. Experiments show that the method recovers clusters of comparable quality to the al- gorithm of Brown et al. (1992), but is an order of magnitude more efficient.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Spectral Algorithm for Learning Class-Based $n$-gram Models of Natural Language %A Karl Stratos Columbia University %A Do-kyum Kim %A Daniel Hsu Columbia University %A Michael Collins Columbia University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14u %I PMLR %P 745--754 %U https://proceedings.mlr.press/r12/university14u.html %V R12 %X The Brown clustering algorithm (Brown et al., 1992) is widely used in natural language process- ing (NLP) to derive lexical representations that are then used to improve performance on vari- ous NLP problems. The algorithm assumes an underlying model that is essentially an HMM, with the restriction that each word in the vocab- ulary is emitted from a single state. A greedy, bottom-up method is then used to find the clus- tering; this method does not have a guarantee of finding the correct underlying clustering. In this paper we describe a new algorithm for clustering under the Brown et al. model. The method relies on two steps: first, the use of canonical correla- tion analysis to derive a low-dimensional repre- sentation of words; second, a bottom-up hierar- chical clustering over these representations. We show that given a sufficient number of training examples sampled from the Brown et al. model, the method is guaranteed to recover the correct clustering. Experiments show that the method recovers clusters of comparable quality to the al- gorithm of Brown et al. (1992), but is an order of magnitude more efficient. %Z Reissued by PMLR on 04 October 2026.
APA
University, K.S.C., Kim, D., University, D.H.C. & University, M.C.C.. (2014). A Spectral Algorithm for Learning Class-Based $n$-gram Models of Natural Language. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:745-754 Available from https://proceedings.mlr.press/r12/university14u.html. Reissued by PMLR on 04 October 2026.

Related Material