Reasoning with Probabilistic and Deterministic Graphical Models

Reasoning with Probabilistic and Deterministic Graphical Models
Exact Algorithms

Rina Dechter,
ISBN: 9781627051972 | PDF ISBN: 9781627051989
Copyright © 2015 | 191 Pages | Publication Date: 12/01/2013

BEFORE YOU ORDER: You may have Academic or Corporate access to this title. Click here to find out: 10.2200/S00529ED1V01Y201308AIM023

Ordering Options: Paperback $45.00   E-book $36.00   Paperback & E-book Combo $56.25

Why pay full price? Members receive 15% off all orders.
Learn More Here

Read Our Digital Content License Agreement (pop-up)

Purchasing Options:

Graphical models (e.g., Bayesian and constraint networks, influence diagrams, and Markov decision processes) have become a central paradigm for knowledge representation and reasoning in both artificial intelligence and computer science in general. These models are used to perform many reasoning tasks, such as scheduling, planning and learning, diagnosis and prediction, design, hardware and software verification, and bioinformatics. These problems can be stated as the formal tasks of constraint satisfaction and satisfiability, combinatorial optimization, and probabilistic inference. It is well known that the tasks are computationally hard, but research during the past three decades has yielded a variety of principles and techniques that significantly advanced the state of the art. In this book we provide comprehensive coverage of the primary exact algorithms for reasoning with such models. The main feature exploited by the algorithms is the model's graph. We present inference-based, message-passing schemes (e.g., variable-elimination) and search-based, conditioning schemes (e.g., cycle-cutset conditioning and AND/OR search). Each class possesses distinguished characteristics and in particular has different time vs. space behavior. We emphasize the dependence of both schemes on few graph parameters such as the treewidth, cycle-cutset, and (the pseudo-tree) height. We believe the principles outlined here would serve well in moving forward to approximation and anytime-based schemes. The target audience of this book is researchers and students in the artificial intelligence and machine learning area, and beyond.

Table of Contents

What are Graphical Models
Inference: Bucket Elimination for Deterministic Networks
Inference: Bucket Elimination for Probabilistic Networks
Tree-Clustering Schemes
AND/OR Search Spaces and Algorithms for Graphical Models
Combining Search and Inference: Trading Space for Time
Author's Biography

About the Author(s)

Rina Dechter, University of California, Irvine
Rina Dechter's research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing, and probabilistic reasoning. She is a professor of computer science at the University of California, Irvine. She holds a Ph.D. from UCLA, an M.S. degree in applied mathematics from the Weizmann Institute, and a B.S. in mathematics and statistics from the Hebrew University in Jerusalem. She is an author of Constraint Processing published by Morgan Kaufmann (2003), has co-authored over 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial IntelligenceResearch (JAIR), and Journal of Machine Learning Research(JMLR). She is a fellow of the American Association of Artificial Intelligence, was a Radcliffe Fellow 2005-2006, received the 2007 Association of Constraint Programming (ACP) Research Excellence Award, and she is a 2013 ACM Fellow. She has been Co-Editor-in-Chief of Artificial Intelligence since 2011. She is also co-editor with Hector Geffner and Joe Halpern of the book Heuristics, Probability and Causality: A Tribute to Judea Pearl, College Publications, 2010.


Related Series

Human Language Technologies


Customers who bought this product also purchased
Bayesian Analysis in Natural Language Processing
Bayesian Analysis in Natural Language Processing
The Shortest-Path Problem
The Shortest-Path Problem
Browse by Subject
Case Studies in Engineering
ACM Books
IOP Concise Physics
0 items

Note: Registered customers go to: Your Account to subscribe.

E-Mail Address:

Your Name: