Abstract

We introduce a new class of “maximization expectation ” (ME) algorithms where we maximize over hidden variables but marginalize over random parameters. This reverses the roles of expectation and maximization in the classical EM algorithm. In the context of clustering, we argue that the hard assignments from the maximization phase open the door to very fast implementations based on data-structures such as kd-trees and conga-lines. The marginalization over parameters ensures that we retain the ability to select the model structure (i.e. number of clusters). As an important example we discuss a top-down “Bayesian k-means ” algorithm and a bottom-up agglomerative clustering algorithm. In experiments we compare these algorithms against a number of alternative algorithms that have recently appeared in the literature.