國立虎尾科技大學 |

Reasoning with probabilistic and deterministic graphical models : = exact algorithms /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Reasoning with probabilistic and deterministic graphical models :/ Rina Dechter.
Reminder of title:	exact algorithms /
Author:	Dechter, Rina,
Description:	1 PDF (xiv, 185 pages) :illustrations. :
Notes:	Part of: Synthesis digital library of engineering and computer science.
Subject:	Graphical modeling (Statistics) -
Online resource:	https://ieeexplore.ieee.org/servlet/opac?bknumber=8643123
ISBN:	9781681734910

Reasoning with probabilistic and deterministic graphical models : = exact algorithms /
Dechter, Rina,1950-,

Reasoning with probabilistic and deterministic graphical models :exact algorithms /Rina Dechter. - Second edition - 1 PDF (xiv, 185 pages) :illustrations. - Synthesis lectures on artificial intelligence and machine learning,# 411939-4616 ;. - Synthesis digital library of engineering and computer science..

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 175-184).

1. Introduction -- 1.1 Probabilistic vs. deterministic models -- 1.2 Directed vs. undirected models -- 1.3 General graphical models -- 1.4 Inference and search-based schemes -- 1.5 Overview of the book --

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

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.

Mode of access: World Wide Web.

ISBN: 9781681734910

Standard No.: 10.2200/S00893ED2V01Y201901AIM041doiSubjects--Topical Terms:

785858
Graphical modeling (Statistics)
Subjects--Index Terms:

graphical models

LC Class. No.: QA279.5 / .D43 2019

Dewey Class. No.: 006.31

Reasoning with probabilistic and deterministic graphical models : = exact algorithms /
LDR:07977nam 2200769 i 4500 001 959748
003 IEEE
005 20190227151734.0
006 m eo d
007 cr cn |||m|||a
008 201209s2019 caua foab 000 0 eng d
020 $a 9781681734910 $q ebook
020 $z 9781681734927 $q hardcover
020 $z 9781681734903 $q paperback
024 7 $a 10.2200/S00893ED2V01Y201901AIM041 $2 doi
035 $a (CaBNVSL)swl000409037
035 $a (OCoLC)1088564438
035 $a 8643123
040 $a CaBNVSL $b eng $e rda $c CaBNVSL $d CaBNVSL
050 4 $a QA279.5 $b .D43 2019
082 0 4 $a 006.31 $2 23
100 1 $a Dechter, Rina, $d 1950-, $e author. $3 1253059
245 1 0 $a Reasoning with probabilistic and deterministic graphical models : $b exact algorithms / $c Rina Dechter.
250 $a Second edition
264 1 $a [San Rafael, California] : $b Morgan & Claypool, $c 2019.
300 $a 1 PDF (xiv, 185 pages) : $b illustrations.
336 $a text $2 rdacontent
337 $a electronic $2 isbdmedia
338 $a online resource $2 rdacarrier
490 1 $a Synthesis lectures on artificial intelligence and machine learning, $x 1939-4616 ; $v # 41
500 $a Part of: Synthesis digital library of engineering and computer science.
504 $a Includes bibliographical references (pages 175-184).
505 0 $a 1. Introduction -- 1.1 Probabilistic vs. deterministic models -- 1.2 Directed vs. undirected models -- 1.3 General graphical models -- 1.4 Inference and search-based schemes -- 1.5 Overview of the book --
505 8 $a 2. Defining graphical models -- 2.1 General graphical models -- 2.2 The graphs of graphical models -- 2.2.1 Basic definitions -- 2.2.2 Types of graphs -- 2.3 Constraint networks -- 2.4 Cost networks -- 2.5 Probability networks -- 2.5.1 Bayesian networks -- 2.5.2 Markov networks -- 2.6 Influence diagrams -- 2.7 Mixed networks -- 2.8 Summary and bibliographical notes --
505 8 $a 3. Inference: bucket elimination for deterministic networks -- 3.1 Bucket elimination for constraint networks -- 3.2 Bucket elimination for propositional CNFs -- 3.3 Bucket elimination for linear inequalities -- 3.4 The induced-graph and induced-width -- 3.4.1 Trees -- 3.4.2 Finding good orderings -- 3.5 Chordal graphs -- 3.6 Summary and bibliography notes --
505 8 $a 4. Inference: bucket elimination for probabilistic networks -- 4.1 Belief updating and probability of evidence -- 4.1.1 Deriving BE-bel -- 4.1.2 Complexity of BE-bel -- 4.1.3 The impact of observations -- 4.2 Bucket elimination for optimization tasks -- 4.2.1 A bucket elimination algorithm for mpe -- 4.2.2 A bucket elimination algorithm for map -- 4.3 Bucket elimination for Markov networks -- 4.4 Bucket elimination for influence diagrams -- 4.5 Bucket elimination for cost networks and dynamic programming -- 4.6 Bucket elimination for mixed networks -- 4.7 The general bucket elimination -- 4.8 Summary and bibliographical notes -- 4.9 Appendix: proofs --
505 8 $a 5. Tree-clustering schemes -- 5.1 Bucket-tree elimination -- 5.1.1 Asynchronous bucket-tree propagation -- 5.2 From bucket trees to cluster trees -- 5.2.1 From buckets to clusters - the short route -- 5.2.2 Acyclic graphical models -- 5.2.3 Tree decomposition and cluster tree elimination -- 5.2.4 Generating tree decompositions -- 5.3 Properties of CTE for general models -- 5.3.1 Correctness of CTE -- 5.3.2 Complexity of CTE -- 5.4 Illustration of CTE for specific models -- 5.4.1 Belief updating and probability of evidence -- 5.4.2 Constraint networks -- 5.4.3 Optimization -- 5.5 Summary and bibliographical notes -- 5.6 Appendix: proofs --
505 8 $a 6. AND/OR search spaces for graphical models -- 6.1 AND/OR search trees -- 6.1.1 Weights of OR-AND arcs -- 6.1.2 Pseudo trees -- 6.1.3 Properties of AND/OR search trees -- 6.2 AND/OR search graphs -- 6.2.1 Generating compact AND/OR search spaces -- 6.2.2 Building context-minimal AND/OR search graphs -- 6.2.3 Size of AND/OR graph -- 6.3 Finding good pseudo-trees -- 6.3.1 Pseudo trees created from induced-graphs -- 6.3.2 Hypergraph decompositions -- 6.4 Value functions of reasoning problems -- 6.4.1 Searching and/or tree (AOT) and and/or graph (AOG) -- 6.5 General AND-OR search - AO(i) -- 6.5.1 Complexity -- 6.6 AND/OR search algorithms for mixed networks -- 6.6.1 AND-OR-cpe algorithm -- 6.6.2 Constraint propagation in AND-OR-cpe -- 6.6.3 Good and nogood learning -- 6.7 Summary and bibliographical notes -- 6.8 Appendix: proofs --
505 8 $a 7. Combining search and inference: trading space for time -- 7.1 The cutset-conditioning scheme -- 7.1.1 Cutset-conditioning for constraints -- 7.1.2 General cutset-conditioning -- 7.1.3 Alternating conditioning and elimination -- 7.2 The super-cluster schemes -- 7.3 Trading time and space with AND/OR search -- 7.3.1 AND/OR cutset-conditioning -- 7.3.2 Algorithm adaptive caching (AOC.q/) -- 7.3.3 Relations between AOC(q), AO-ALT-VEC(q) and AO-VEC(q) -- 7.3.4 AOC(q) Compared with STCE(q) -- 7.4 Summary and bibliographical notes -- 7.5 Appendix: proofs --
505 8 $a 8. Conclusion -- Bibliography -- Author's biography.
506 $a Abstract freely available; full-text restricted to subscribers or individual document purchasers.
510 0 $a Compendex
510 0 $a INSPEC
510 0 $a Google scholar
510 0 $a Google book search
520 3 $a 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.
530 $a Also available in print.
538 $a Mode of access: World Wide Web.
538 $a System requirements: Adobe Acrobat Reader.
588 $a Title from PDF title page (viewed on February 26, 2019).
650 0 $a Graphical modeling (Statistics) $3 785858
650 0 $a Bayesian statistical decision theory. $3 527671
650 0 $a Reasoning. $3 557675
650 0 $a Algorithms. $3 527865
650 0 $a Machine learning. $3 561253
653 $a graphical models
653 $a Bayesian networks
653 $a constraint networks
653 $a Markov networks
653 $a influence diagrams
653 $a induced-width
653 $a treewidth
653 $a cycle-cutset
653 $a loop-cutset
653 $a pseudo-tree
653 $a bucket-elimination
653 $a variable-elimination
653 $a AND/OR search
653 $a conditioning
653 $a reasoning
653 $a inference
653 $a knowledge representation
776 0 8 $i Print version: $z 9781681734927 $z 9781681734903
830 0 $a Synthesis digital library of engineering and computer science. $3 598254
830 0 $a Synthesis lectures on artificial intelligence and machine learning ; $v 29 $3 1136768
856 4 2 $3 Abstract with links to resource $u https://ieeexplore.ieee.org/servlet/opac?bknumber=8643123