Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms (Paperback)

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: Preface / Introduction / 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 / Conclusion / Bibliography / Author's Biography

圖形模型（例如，貝葉斯和約束網絡、影響圖和馬爾可夫決策過程）已成為人工智能和計算機科學中知識表示和推理的核心範式。這些模型用於執行許多推理任務，例如排程、計劃和學習、診斷和預測、設計、硬件和軟件驗證以及生物信息學。這些問題可以被視為約束滿足和可滿足性、組合優化和概率推理的正式任務。這些任務的計算難度已經被廣泛認識，但在過去三十年的研究中，已經取得了一系列顯著推進現有技術的原則和技術。

在本書中，我們全面介紹了用於處理這些模型的主要精確算法。算法利用的主要特徵是模型的圖形結構。我們介紹了基於推理的消息傳遞方案（例如，變量消除）和基於搜索的條件方案（例如，循環割集條件和AND/OR搜索）。每個類別都具有獨特的特點，特別是在時間和空間行為方面有所不同。我們強調這兩種方案對圖形參數（如樹寬度、循環割集和（偽樹）高度）的依賴。我們相信這裡概述的原則將有助於推進近似和隨時可用的方案。本書的目標讀者是人工智能和機器學習領域的研究人員和學生，以及其他相關領域的讀者。

目錄：前言/引言/什麼是圖形模型/推理：用於確定性網絡的桶消除/推理：用於概率網絡的桶消除/樹聚類方案/AND/OR搜索空間和圖形模型的算法/結合搜索和推理：以空間換時間/結論/參考文獻/作者簡介