News

Colloquia

B-Matching for Embedding and Clustering

Tony Jebara
Columbia University

March 30, 2006
JEC 3117 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

Many machine learning algorithms require building a weighted graph on data prior to clustering, embedding or classification. Typically, the edges in an affinity graph are used as-is or pruned using heuristics such as k-nearest neighbors. We propose pruning the graph using b-matching instead. This removes spurious edges prior to embedding or clustering. B-matching is a generalization of traditional maximum weight matching and is solvable in polynomial time. Instead of a permutation matrix, b-matching produces a binary matrix whose rows and columns sum to an integer b that can be greater than unity. The b-matching procedure effectively prunes graph edges and sets the in-degree and out-degree of each node to b. Subsquent applications of embedding (such as Weinberger's semidefinite embedding) or spectral clustering (such as Ng's relaxation of normalized cut) are more stable and accurate than pruning with k nearest neighbors or other heuristics. Experiments are shown on various UCI datasets, visualizations and image datasets.

Bio:

Tony Jebara is an Assistant Professor of Computer Science at Columbia University. He is Director of the Columbia Machine Learning Laboratory whose research focuses upon machine learning, computer vision and related application areas such as human-computer interaction. Jebara is also a Principal Investigator at Columbia's Vision and Graphics Center. He has published over 30 papers in the above areas including the book Machine Learning: Discriminative and Generative (Kluwer). Jebara is the recipient of the Career award from the National Science Foundation and has also received honors for his papers from the International Conference on Machine Learning and from the Pattern Recognition Society. He has served as co-chair and program committee member for various conferences and workshops. Jebara's research has been featured on television (ABC, BBC, New York One, TechTV, etc.) as well as in the popular press (Wired Online, Scientific American, Newsweek, Science Photo Library, etc.). Jebara obtained his Bachelor's from McGill University (at the McGill Center for Intelligent Machines) in 1996. He obtained his Master's in 1998 and his PhD in 2002 both from the Massachusetts Institute of Technology (at the MIT Media Laboratory). He is currently a member of the IEEE, ACM and AAAI. Professor Jebara's research and laboratory are supported in part by the Central Intelligence Agency, Microsoft, Alpha Star Corporation and the National Science Foundation.

Hosted by: Bulent Yener (x6907)

Last updated: February 27, 2006