Tuesday, April 26, 2016. 12:00PM. NSH 3305.
Rina Dechter - Modern Exact and Approximate Combinatorial Optimization Algorithms (max-product and max-sum-product) for Graphical models
In this talk I will present several principles behind state of the art algorithms for solving combinatorial optimization tasks defined over graphical models (Bayesian networks, Markov networks, constraint networks, Influence diagrams) and demonstrate their performance on some benchmarks.
Specifically I will present branch and bound search algorithms which explore the AND/OR search space over graphical models and thus exploit problem's decomposition (using AND nodes), equivalence (by caching) and pruning irrelevant subspaces via the power of bounding heuristics. In particular I will show how the two ideas of mini-bucket partitioning which relaxes the input problem using node duplication only, combined with linear programming relaxations ideas which optimize cost-shifting/re-parameterization schemes, can yield tight bounding heuristic information within systematic, anytime, search. I will then show our recent extension to solving the far more challenging task of Marginal Map (as time permits).
Notably, a solver for finding the most probable explanation (MPE or MAP), embedding these principles has won first place in all time categories in the 2012 PASCAL2 approximate inference challenge, and first or second place in the UAI-2014 competitions.
Parts of this work were done jointly with: Radu Marinescu, Kalev Kask, Alex Ihler, Robesrt Mateescu and Lars Otten.
Speaker Bio
Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, an MS degree in Applied Mathematics from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning.
Professor Dechter is an author of 'Constraint Processing' published by Morgan Kaufmann, 2003, and 'Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms' by Morgan and Claypool publishers, 2013, has co-authored over 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research, Logical Methods in Computer Science (LMCS) and journal of Machine Learning (JLMR). She was awarded the Presidential Young investigator award in 1991, is a fellow of the American association of Artificial Intelligence since 1994, was a Radcliffe Fellowship 2005-2006, received the 2007 Association of Constraint Programming (ACP) research excellence award and is a 2013 Fellow of the ACM. She has been Co-Editor-in-Chief of Artificial Intelligence, since 2011.