Tony Jebara
Location: (New York, NY)
Personal Research Web Page: http://www.cs.columbia.edu/~jebara
Keywords: machine learning, graphs, matchings, perfect graphs, networks, graphical models, inference, large margin methods, structured prediction, kernel methods, spatiotemporal data, generative and discriminative learning, maximum entropy, combinatorics
Posted on: Saturday, May 16th, 2009
Broad Research Area: AI / Machine Learning / Robotics / Vision
Research Interests:
I am interested in the application of generalized matching and other graph-theoretic / combinatorial methods to machine learning problems. Matchings and generalized matchings are a family of graphs (such as trees) that enjoy fascinating combinatorics and fast algorithms. Matching goes by many names and variations including permutation (or permutation-invariance), assignment, auction, alignment, correspondence, bipartite matching, unipartite matching, generalized matching and b-matching. The group of matchings is called the symmetric group in algebra. Generalized matching is an excellent competitor to local methods (such as k-nearest neighbors) in many machine learning problems and has improved performance in classification, clustering, semisupervised learning, image matching, collaborative filtering, and visualization settings.
Generalized matching problems can be written as a graphical model and solved efficiently and exactly for large scale problems using belief propagation. Currently, I am working on using these tools in machine learning applications. I am also interested in theoretical guarantees for b-matching in terms of its generalization performance when applied to independently sampled data. Is there some larger family of graphs which subsumes matchings? This answer is yes and leads to another exciting topic in combinatorics: perfect graphs. Perfect graphs have important implications in the field of machine learning. Decoding and inference with graphical models that are perfect graphs is exact and when can be solved efficiently via linear programming, or even more efficiently, via message passing. This opens up interesting connections between machine learning problems and combinatorial algorithms on perfect graphs.
Please see www.cs.columbia.edu/~jebara/research.html for details.
Contact Information:
Send me an email or meet me in person at the upcoming machine learning conferences (ICML, COLT or UAI in Montreal June 14-21).
