| 000 | 08272nam a2200865 i 4500 | ||
|---|---|---|---|
| 001 | 6812756 | ||
| 003 | IEEE | ||
| 005 | 20200413152913.0 | ||
| 006 | m eo d | ||
| 007 | cr cn |||m|||a | ||
| 008 | 140113s2013 caua foab 000 0 eng d | ||
| 020 |
_a9781627051989 _qebook |
||
| 020 |
_z9781627051972 _qpaperback |
||
| 024 | 7 |
_a10.2200/S00529ED1V01Y201308AIM023 _2doi |
|
| 035 | _a(CaBNVSL)swl00403033 | ||
| 035 | _a(OCoLC)867318552 | ||
| 040 |
_aCaBNVSL _beng _erda _cCaBNVSL _dCaBNVSL |
||
| 050 | 4 |
_aQA279 _b.D537 2013 |
|
| 082 | 0 | 4 |
_a519.5 _223 |
| 090 |
_a _bMoCl _e201308AIM023 |
||
| 100 | 1 |
_aDechter, Rina, _d1950-, _eauthor. |
|
| 245 | 1 | 0 |
_aReasoning with probabilistic and deterministic graphical models : _bexact algorithms / _cRina Dechter. |
| 264 | 1 |
_aSan Rafael, California (1537 Fourth Street, San Rafael, CA 94901 USA) : _bMorgan & Claypool, _c2013. |
|
| 300 |
_a1 PDF (xiv, 177 pages) : _billustrations. |
||
| 336 |
_atext _2rdacontent |
||
| 337 |
_aelectronic _2isbdmedia |
||
| 338 |
_aonline resource _2rdacarrier |
||
| 490 | 1 |
_aSynthesis lectures on artificial intelligence and machine learning, _x1939-4616 ; _v# 23 |
|
| 538 | _aMode of access: World Wide Web. | ||
| 538 | _aSystem requirements: Adobe Acrobat Reader. | ||
| 500 | _aPart of: Synthesis digital library of engineering and computer science. | ||
| 500 | _aSeries from website. | ||
| 504 | _aIncludes bibliographical references (pages 167-176). | ||
| 505 | 0 | _a1. 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 | _a2. What are 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 Mixed networks -- 2.7 Summary and bibliographical notes -- | |
| 505 | 8 | _a3. 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 | _a4. 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 cost networks and dynamic programming -- 4.5 Bucket elimination for mixed networks -- 4.6 The general bucket elimination -- 4.7 Summary and bibliographical notes -- 4.8 Appendix: proofs -- | |
| 505 | 8 | _a5. 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 | _a6. AND/OR search spaces and algorithms 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.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 | _a7. 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 | _a8. Conclusion -- Bibliography -- Author's biography. | |
| 506 | 1 | _aAbstract freely available; full-text restricted to subscribers or individual document purchasers. | |
| 510 | 0 | _aCompendex | |
| 510 | 0 | _aINSPEC | |
| 510 | 0 | _aGoogle scholar | |
| 510 | 0 | _aGoogle book search | |
| 520 | 3 | _aGraphical 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. | |
| 530 | _aAlso available in print. | ||
| 588 | _aTitle from PDF title page (viewed on January 13, 2014). | ||
| 650 | 0 | _aGraphical modeling (Statistics) | |
| 650 | 0 | _aBayesian statistical decision theory. | |
| 650 | 0 | _aReasoning. | |
| 650 | 0 | _aAlgorithms. | |
| 653 | _agraphical models | ||
| 653 | _aBayesian networks | ||
| 653 | _aconstraint networks | ||
| 653 | _aMarkov networks | ||
| 653 | _ainduced-width | ||
| 653 | _atreewidth | ||
| 653 | _acycle-cutset | ||
| 653 | _aloop-cutset | ||
| 653 | _apseudo-tree | ||
| 653 | _abucket-elimination | ||
| 653 | _avariable-elimination | ||
| 653 | _aAND/OR search | ||
| 653 | _aconditioning | ||
| 653 | _areasoning | ||
| 653 | _ainference | ||
| 653 | _aknowledge representation | ||
| 776 | 0 | 8 |
_iPrint version: _z9781627051972 |
| 830 | 0 | _aSynthesis digital library of engineering and computer science. | |
| 830 | 0 |
_aSynthesis lectures on artificial intelligence and machine learning ; _v# 23. _x1939-4616 |
|
| 856 | 4 | 2 |
_3Abstract with links to resource _uhttp://ieeexplore.ieee.org/servlet/opac?bknumber=6812756 |
| 856 | 4 | 0 |
_3Abstract with links to full text _uhttp://dx.doi.org/10.2200/S00529ED1V01Y201308AIM023 |
| 999 |
_c562050 _d562050 |
||