Affiliation:
Electrical and Computer Engineering
University of Toronto
10 King's College Road
Toronto, ON  M5S 3G4
Canada
 

Latest Research: Affinity Propagation

Here is my Ph.D. thesis, Affinity Propagation: Clustering Data by Passing Messages (smaller viewable PDF, large printable ZIP)

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. Affinity propagation is a new algorithm that takes as input measures of similarity between pairs of data points and simultaneously considers all data points as potential exemplars. Real-valued messages are exchanged between data points until a high-quality set of exemplars and corresponding clusters gradually emerges. We have used affinity propagation to solve a variety of clustering problems and we found that it uniformly found clusters with much lower error than those found by other methods, and it did so in less than one-hundredth the amount of time. Because of its simplicity, general applicability, and performance, we believe affinity propagation will prove to be of broad value in science and engineering.

The following animated visualization shows affinity propagation gradually identifying three exemplars among a small set of two-dimensional data points:

For more information, see http://www.psi.toronto.edu/affinitypropagation.

Earlier Research: Probabilistic Sparse Matrix Factorization

We propose a new method of finding sparse matrix factorizations employing probabilistic inference techniques, and apply them to discover structures underlying gene expression data.

Given a data matrix XÎÂ^G×T, containing G T-dimensional data points, we perform matrix factorization (X»Y·Z).  Specifically, we find a matrix of hidden factors (or causes), ZÎÂ^C×T, and a factor loading matrix, YÎÂ^G×C, under a structural sparseness constraint that each row of Y contains at most N (of C possible) non-zero entries.  Intuitively, this corresponds to explaining each row-vector of X as a linear combination (weighted by the corresponding row in Y) of a small subset of factors (causes) given by rows of Z.  Note that this framework includes simple clustering (N=1) and ordinary low-rank approximation (N=C) as special cases.

We construct a probability model presuming Gaussian sensor noise in X (i.e. X=Y·Z+noise) and uniformly distributed factor assignments.  We utilize a factorized variational method to perform tractable inference on the latent variables, and also account for noise in the factor matrix (Z) and uncertainty in assigning factors (Y).  We explore several different factorization depths to allow a tradeoff between increased model accuracy and decreased computational complexity.

Figure: Probabilistic Sparse Matrix Factorization of a 22709×55 gene expression array
Click for animation (1.2 MB)

We apply our algorithm to mouse gene expression data from the Hughes Lab, as shown in the figure above.  We show a data set of G=22709 gene expression profiles (expressed across T=55 tissues) approximated by linear combinations of at most N=3 (of a possible C=50) hidden transcription factor profiles.  Experimental results demonstrate that our method can identify genetic functional categories with higher statistical significance than the method currently in greatest use, hierarchical agglomerative clustering.

(updated 11/03/2009)

.