Abstract

How would you identify a small number of face images that together accurately represent a data set of face images? How would you identify a small number of sentences that accurately reflect the content of a document? How would you identify a small number of cities that are most easily accessible from all other cities by commercial airline? How would you identify segments of DNA that reflect the expression properties of genes? Data centers, or exemplars, are traditionally found by randomly choosing an initial subset of data points and then iteratively refining it, but this only works well if that initial choice is close to a good solution. I'll describe a method called 'affinity propagation', which takes as input measures of similarity between pairs of data points, akin to kernels. Real-valued messages are exchanged between data points until a high-quality set of exemplars and corresponding clusters gradually emerges. I'll describe results we obtained when we used affinity propagation to identify exemplars and corresponding clusters in the above applications. Affinity propagation uniformly found clusters with much lower error than those found by other methods, and it did so in a fraction of the amount of time. Affinity propagation can be implemented in a few lines of MATLAB code.

About the Speaker

Brendan Frey received his PhD from the University of Toronto in 1997. From 1997 to 1999, he was a Beckman Fellow at the University of Illinois at Urbana Champaign and then he joined the Department of Computer Science at the University of Waterloo as an Assistant Professor. In 2001, Dr. Frey moved to the University of Toronto, where he is now an Associate Professor in Electrical and Computer Engineering, with cross-appointments to Computer Science and the Centre for Cellular and Bio-molecular Research.

He has consulted for Microsoft Research and various startup companies in the Toronto area. Dr. Frey is the author of the book Graphical Models for Machine Learning and Digital Communication and studies machine learning, probabilistic graphical models, molecular biology, computer vision and iterative decoding. Dr. Frey's most highly-cited work is on 'factor graphs and the sum-product algorithm'. In 2005, Dr. Frey's work on computational 'epitomes' with applications in vision received honorable mention for Best Paper at the IEEE Conference on Computer Vision and Pattern Recognition.

Dr. Frey's 2005 Nature Genetics paper reporting the first-ever exon-resolution analysis of the mammalian genome stirred up controversy in the molecular biology and genomics communities, which was reconciled in his favour in the March 2006 issue of Science. Dr. Frey is a Fellow of the Canadian Institute for Advanced Research, a winner of the Premier's Research Excellence Award, a former Fellow of the Beckman Foundation and a recipient of the NSERC 1967 Science and Engineering Award.