
Reasoning with Probabilistic and Deterministic Graphical Models
Exact Algorithms
Rina Dechter(Author)
Morgan & Claypool Publishers
2nd Edition
Published on 28. February 2019
Book
Paperback/Softback
199 pages
978-1-68173-490-3 (ISBN)
Description
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.
This book provides 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. The new edition includes the notion of influence diagrams, which focus on sequential decision making under uncertainty. We believe the principles outlined in the book 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.
This book provides 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. The new edition includes the notion of influence diagrams, which focus on sequential decision making under uncertainty. We believe the principles outlined in the book 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.
More details
Series
Edition
2nd Revised edition
Language
English
Place of publication
San Rafael
United States
Edition type
Revised edition
Dimensions
Height: 235 mm
Width: 190 mm
Weight
333 gr
ISBN-13
978-1-68173-490-3 (9781681734903)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Persons
Rina Dechter's research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing, and probabilistic reasoning. She is a Chancellor's 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 the author of Constraint Processing published by Morgan Kaufmann (2003), and of Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms published by Morgan and Claypool (2013). She has co-authored close to 200 research papers and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research (JAIR), and Journal of Machine Learning Research (JMLR). She is a Fellow of the American Association of Artificial Intelligence since 1994, was a Radcliffe Fellow during 2005-2006, received the 2007 Association of Constraint Programming (ACP) Research Excellence Award, and became an ACM Fellow in 2013. She was a Co-Editor-in-Chief of Artificial Intelligence from 2011 to 2018 and is the conference chair-elect for IJCAI-2022.
Content
- Preface
- Introduction
- Defining Graphical Models
- Inference: Bucket Elimination for Deterministic Networks
- Inference: Bucket Elimination for Probabilistic Networks
- Tree-Clustering Schemes
- AND/OR Search Spaces for Graphical Models
- Combining Search and Inference: Trading Space for Time
- Conclusion
- Bibliography
- Author's Biography
- Introduction
- Defining Graphical Models
- Inference: Bucket Elimination for Deterministic Networks
- Inference: Bucket Elimination for Probabilistic Networks
- Tree-Clustering Schemes
- AND/OR Search Spaces for Graphical Models
- Combining Search and Inference: Trading Space for Time
- Conclusion
- Bibliography
- Author's Biography