Exemplar-based clustering is a combinatorial optimization problem where we wish to partition a set of data points into clusters, given their pairwise similarities, and associate each cluster with its most representative data point (called exemplar). Using exemplar-based clustering as a motivating example, I will give a brief introduction to factor graphs, how they can be used to describe combinatorial optimization problems. I will discuss how we can find approximate inference solutions to such problems using message passing algorithms, and in particular max-product belief propagation.
Affinity propagation (Frey & Dueck, 2007) is an exemplar-based clustering method based on the above techniques. In my talk, I will describe several extensions of affinity propagation that I have developed. These include capacitated affinity propagation, semi-supervised affinity propagation, and hierarchical affinity propagation. The extensions provide clustering tools that go beyond the capabilities of the basic affinity propagation algorithm, and generalize it to various problems of interest in machine learning. I will discuss applications of these extensions to problems in computer vision and computational biology.
I will also discuss some surprising results obtained for exemplar-based clustering when comparing max-product belief propagation to alternative inference techniques such as max-product linear programming, and dual decomposition. I show that for a collection of benchmark data sets, affinity propagation outperforms these more theoretically justified approaches.