From AND/OR Search to AND/OR Sampling

GRAND Seminar Nov. 11, 1 PM., Monday. 2013, ENGR 4201

Rina Dechter
Professor of Computer Science
The University of California, Irvine.

Abstract:

Sampling is one of the main approaches for approximate reasoning in graphical models. In this work we show that while sampling can be structure-blind, exploiting the graph-structure can reduce sampling variance and hence speed-up convergence. Specifically, I will show how “AND/OR Importance sampling” can exploit problem decomposition, yielding significantly improved estimators. Moreover, combining AND/OR sampling with cutset-sampling to reduce the effective dimensionality yields further variance reduction. Extensive empirical evaluation demonstrates the power of the new estimators, often showing an order of magnitude improvements over previous schemes. In particular, these schemes were part of a solver that won first place in the recent UAI 2010 competition and first place in the Pascal 2011 approximate reasoning challenge.

Short 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, has authored over 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research 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 and received the 2007 Association of Constraint Programming (ACP) research excellence award. She has been Co-Editor-in-Chief of Artificial Intelligence, since 2011.