words in the vocabulary, and evaluates how much the objective function would change by moving the word to each class. If there are moves that would improve the objective function, the word is moved to the class that provides the largest improvement.

By storing word and class bigram statistics, the evaluation of the objective function can be done in $\mathcal{O}(N_C)$, and thus one word iterated in $\mathcal{O}(N_C^2)$ time [@Martin:1995]. The number of words that will be iterated is not limited by a fixed bound. Even though we did not perform the experiments in such a way that we could get a fair comparison of the training times, we noticed that our exchange implementation needed less time to converge than what the Brown clustering needed to finish.[^5]

These algorithms perform a lot of computation of statistics and evaluations over pairs of adjacent classes and words. In practice the running times are better than the worst case estimates, because all classes and words do not follow each other. The algorithms can also be parallelized using multiple CPUs, on the expense of memory requirements. Parallelization using a GPU would be difficult, because that would involve sparse matrices.

The exchange algorithm is greedy so 