# How to implement Brown Clustering Algorithm in O(|V|k^2)

I am trying to implement the Brown Clustering Algorithm.

Paper details: "Class-Based n-gram Models of Natural Language" by Brown et al

The algorithm is supposed to in O(|V|k^2) where |V| is the size of the vocabulary and k is the number of clusters. I am unable to implement it this efficiently. In fact, the best I can manage is O(|V|k^3) which is too slow. My current implementation for the main part of the algorithm is as follows:

for w = number of clusters + 1 to |V|
{
word = next most frequent word in the corpus

assign word to a new cluster

initialize MaxQuality to 0

initialize ArgMax vector to (0,0)

for i = 0 to number of clusters - 1
{
for j = i to number of clusters
{
Quality = Mutual Information if we merge cluster i and cluster j

if Quality > MaxQuality
{
MaxQuality = Quality

ArgMax = (i,j)
}
}
}
}


I compute quality as follows:

1. Before entering the second loop compute the pre-merge quality i.e. quality before doing any merges.
2. Every time a cluster-pair merge step is considered:
i. assign quality := pre-merge quality
ii. quality = quality - any terms in the mutual information equation that contain cluster i or cluster j (pre-merge)
iii. quality = quality + any terms in the mutual information equation that contain (cluster i U cluster j)  (post-merge)


In my implementation, the first loop has approx |V| iterations, the second and third loop approx k iterations each. To compute quality at each step requires approx a further k iterations. In total it runs in (|V|k^3) time.

How do you get it to run in (|V|k^2)?

• Can you add a full citation for the paper? The link doesn't work. – shadowtalker Aug 6 '14 at 0:47
• @ssdecontrol the paper is called "Class-Based n-gram Models of Natural Language" by Brown et al. I have actually managed to resolve this. I will post details as an answer. – Ofir Aug 7 '14 at 3:02