Brown clustering

Brown clustering is a hard hierarchical agglomerative clustering problem based on distributional information proposed by Peter Brown, William A. Brown, Vincent Della Pietra, Peter V. de Souza, Jennifer Lai, and Robert Mercer.^[1] The method, which is based on bigram language models,^[2] is typically applied to text, grouping words into clusters that are assumed to be semantically related by virtue of their having been embedded in similar contexts.

Introduction

In natural language processing, Brown clustering^[3] or IBM clustering^[4] is a form of hierarchical clustering of words based on the contexts in which they occur, proposed by Peter Brown, William A. Brown, Vincent Della Pietra, Peter de Souza, Jennifer Lai, and Robert Mercer of IBM in the context of language modeling.^[1] The intuition behind the method is that a class-based language model (also called cluster n-gram model^[4]), i.e. one where probabilities of words are based on the classes (clusters) of previous words, is used to address the data sparsity problem inherent in language modeling. The method has been successfully used to improve parsing, domain adaptation, and named entity recognition.^[5]

Jurafsky and Martin give the example of a flight reservation system that needs to estimate the likelihood of the bigram "to Shanghai", without having seen this in a training set.^[4] The system can obtain a good estimate if it can cluster "Shanghai" with other city names, then make its estimate based on the likelihood of phrases such as "to London", "to Beijing" and "to Denver".

Technical definition

Brown groups items (i.e., types) into classes, using a binary merging criterion based on the log-probability of a text under a class-based language model, i.e. a probability model that takes the clustering into account. Thus, average mutual information (AMI) is the optimization function, and merges are chosen such that they incur the least loss in global mutual information.

As a result, the output can be thought of not only as a binary tree^[6] but perhaps more helpfully as a sequence of merges, terminating with one big class of all words. This model has the same general form as a hidden Markov model, reduced to bigram probabilities in Brown's solution to the problem. MI is defined as:

${\displaystyle \operatorname {MI} (c_{i},c_{j})=\Pr(\langle c_{i},c_{j}\rangle )\log _{2}{\frac {\Pr(\langle c_{i},c_{j}\rangle )}{\Pr(\langle c_{i},*\rangle )\Pr(\langle *,c_{j}\rangle )}}}$

Finding the clustering that maximizes the likelihood of the data is computationally expensive. The approach proposed by Brown et al. is a greedy heuristic.

The work also suggests use of Brown clusterings as a simplistic bigram class-based language model. Given cluster membership indicators c_i for the tokens w_i in a text, the probability of the word instance w_i given preceding word w_i-1 is given by:^[4]

${\displaystyle \Pr(w_{i}|w_{i-1})=\Pr(w_{i}|c_{i})\Pr(c_{i}|c_{i-1})}$

This has been criticised^{[citation needed]} as being of limited utility, as it only ever predicts the most common word in any class, and so is restricted to |c| word types; this is reflected in the low relative reduction in perplexity found when using this model and Brown.

When applied to Twitter data, for example, Brown clustering assigned a binary tree path to each word in unlabelled tweets during clustering.^[7] The prefixes to these paths are used as new features for the tagger.^[7]

Variations

Brown clustering has also been explored using trigrams.^[8]

Brown clustering as proposed generates a fixed number of output classes. It is important to choose the correct number of classes, which is task-dependent.^[9] The cluster memberships of words resulting from Brown clustering can be used as features in a variety of machine-learned natural language processing tasks.^[3]

A generalization of the algorithm was published in the AAAI conference in 2016, including a succinct formal definition of the 1992 version and then also the general form.^[10] Core to this is the concept that the classes considered for merging do not necessarily represent the final number of classes output, and that altering the number of classes considered for merging directly affects the speed and quality of the final result.

There are no known theoretical guarantees on the greedy heuristic proposed by Brown et al. (as of February 2018). However, the clustering problem can be framed as estimating the parameters of the underlying class-based language model: it is possible to develop a consistent estimator for this model under mild assumptions.^[11]

See also

• Feature learning

References

1. Brown, Peter F.; de Souza, Peter V.; Mercer, Robert L.; Della Pietra, Vincent J.; Lai, Jenifer C. (1992). "Class-based n-gram models of natural language" (PDF). Computational Linguistics. 18 (4): 467–479. CiteSeerX 10.1.1.94.9004.
2. Gómez, Manuel Montes y; Escalante, Hugo Jair; Segura, Alberto; Murillo, Juan de Dios (2016). Advances in Artificial Intelligence - IBERAMIA 2016: 15th Ibero-American Conference on AI, San José, Costa Rica, November 23-25, 2016, Proceedings. Cham, Switzerland: Springer. p. 177. ISBN 978-3-319-47954-5.
3. Turian, Joseph; Ratinov, Lev; Bengio, Yoshua (2010). Word representations: a simple and general method for semi-supervised learning (PDF). Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. pp. 1533–9. CiteSeerX 10.1.1.714.8528.
4. Jurafsky, Daniel; Martin, James H. (2009). Speech and Language Processing. Pearson Education International. pp. 145–6. ISBN 9780131873216.
5. Rehm, Georg; Declerck, Thierry (2018). Language Technologies for the Challenges of the Digital Age: 27th International Conference, GSCL 2017, Berlin, Germany, September 13-14, 2017, Proceedings. Cham, Switzerland: Springer. p. 66. ISBN 978-3-319-73705-8.
6. Sun, Maosong; Zhang, Min; Lin, Dekang; Wang, Haifeng (2013). Chinese Computational Linguistics and Natural Language Processing Based on Naturally Annotated Big Data: 12th China National Conference, CCL 2013 and First International Symposium, NLP-NABD 2013, Suzhou, China, October 10-12, 2013, Proceedings. Heidelberg: Springer. p. 54. ISBN 978-3-642-41490-9.
7. Gurevych, Iryna; Biemann, Chris; Zesch, Torsten (2013). Language Processing and Knowledge in the Web: 25th International Conference, GSCL 2013, Darmstadt, Germany, September 25-27, 2013, Proceedings. Heidelberg: Springer. p. 167. ISBN 978-3-642-40721-5.
8. Martin, Sven; Liermann, Jorg; Ney, Hermann (1999). "Algorithms for bigram and trigram word clustering". Speech Communication. 24 (1): 19–37. CiteSeerX 10.1.1.53.2354. doi:10.1016/S0167-6393(97)00062-9.
9. Derczynski, Leon; Chester, Sean; Bogh, Kenneth S. (2015). Tune your Brown clustering, please (PDF). Proceedings of the conference on Recent Advances in Natural Language Processing. CiteSeerX 10.1.1.713.5576.
10. Derczynski, Leon; Chester, Sean (2016). Generalised Brown Clustering and Roll-Up Feature Generation. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. pp. 1533–9. CiteSeerX 10.1.1.714.8528.
11. Stratos, Karl; Kim, Do-kyum; Collins, Michael; Hsu, Daniel (2014). A Spectral Algorithm for Learning Class-Based n-gram Models of Natural Language (PDF). Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence. pp. 762–771. CiteSeerX 10.1.1.643.6343.

External links

• How to tune Brown clustering