Seminars/Colloquia/Invited Talks

Seminars

Tony Jebara

Learning from Data Using Matchings and Graphs

PLACE:	Clark 314
EVENT:	CIS Seminar
DATE:	November 3, 2009
TIME:	1:00 - 2:00 PM

Abstract:

Many machine learning problems on data can naturally be formulated as problems on graphs. For example, dimensionality reduction and visualization are related to graph embedding. Given a sparse graph between N high-dimensional data nodes, how do we faithfully embed it in low dimension? We present an algorithm that improves dimensionality reduction by extending the Maximum Variance Unfolding method. But, given only a dataset of N samples, how do we construct a graph in the first place? The space to explore is daunting with 2^(N(N-1)/2) graphs to choose from yet two interesting subfamilies are tractable: matchings and b-matchings. By placing distributions over matchings and using loopy belief propagation, we can efficiently infer maximum weight subgraphs. These fast generalized matching algorithms leverage integral LP relaxation and perfect graph theory. Applications include graph reconstruction, graph embedding, graph transduction, and graph partitioning with emphasis on data from text, network and image domains. Time permitting, I will also present applications to large scale mobile telecommunication data.

Brief Biography:

Tony Jebara is Associate Professor of Computer Science at Columbia University and co-founder of Sense Networks. He directs the Columbia Machine Learning Laboratory whose research intersects computer science and statistics to develop new frameworks for learning from data with applications in vision, networks, spatio-temporal data, and text. He obtained his PhD in 2002 from MIT. Recently, Esquire magazine named him one of their Best and Brightest of 2008.