Brown clustering

Brown clustering is a method used to create clusters of words that are similar. It is an instance of a Clustering algorithm which generates a hierarchical cluster of words.

Basic Idea

Every word is assigned a bit-string. The bits to the left are the most significant. If a word's significant bits agree with another word's, those words will be in a similar category. If you can imagine a tree of words, the leafs are words that are assigned a bit-string, depending on the position in the tree. Words close together will have closer bit-strings. Another advantage of this method is that the number of clusters can be chosen. If you only examine the first $k$ bits of a string, you will generate a cluster of size $2^{k}$. For example, using the first few bits would give very general clusters (a la part of speech granularity). Using all the bits but one would give clusters of size 2.

Algorithm

The input is a large corpus of words. The output is a tree of words, each with an assigned bit-string. An example output is shown below in list form.

Resources

• Lectures slides by Collins
• A Word Clustering Approach for Language Model-based Sentence Retrieval in Question Answering Systems is a paper that expands on the Brown clustering.