Los Alamos National Laboratory

Science >  LANL Institutes

National Security Education Center


IS&T Seminar: Inference and Search for Graphical Models

September 25, 2013
Time: 3:00 - 4:00 PM
Location: TA-3, Bldg. 1690, Room 102 (CNLS Conference Room)

Speaker: Rina Dechter, Ph.D, University of California, Irvine

Abstract:  Graphical models, e.g., Bayesian networks, Markov random fields, constraint networks and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of reasoning tasks. Their applications include scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. Algorithms for reasoning in graphical models are of two primary types: inference-based (e.g., variable-elimination, join-tree clustering) and search-based. Exact inference-based algorithms are exponentially bounded (both time and space) by the tree-width of the graph. Search algorithms that explore an AND/OR search space can accommodate a more flexible time and memory tradeoff but their performance can also be bounded exponentially by the tree-width.

In my talk I will present and contrast the two primary types of reasoning algorithms and subsequently will focus on bounded inference approximations such as belief propagation and mini-bucket elimination.  In particular, I will show the gain obtained from a hybrid of search and inference, using mini-bucket lower-bounds heuristics to guide AND/OR search. New algorithms that combine mini-bucket with cost-shifting lower-bounding schemes such as moment matching and linear relaxation will be described, if time permits.

Collaborators: Robert Mateescu, Radu Marinescu , Alex Ihler and Lars Otten

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 Mathematic 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 100 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and Logical Method in Computer Science (LMCS). 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.

For more information contact the technical host Misha Chertkov, chertkov@lanl.gov, 695-5684.

Download announcement here.

Hosted by the Information Science and Technology Institute (ISTI)

<< Back to calendar
Operated by Los Alamos National Security, LLC for the U.S. Department of Energy's NNSA
Inside | © Copyright 2008-09 Los Alamos National Security, LLC All rights reserved | Disclaimer/Privacy | Web Contact