TY - MANSCPT
AU - Pouly,Marc
AU - Kohlas,Jürg
ED - ebrary, Inc
TI - Generic inference: a unifying theory for automated reasoning
SN - 1283126338 (ebk)
AV - QA162
U1 - 519.5/4
PY - 2011///
CY - Hoboken, New Jersey
PB - Wiley
KW - Valuation theory
KW - Algorithms
KW - Algebra, Abstract
N1 - Includes bibliographical references and index; GENERIC INFERENCE: A Unifying Theory for Automated Reasoning; CONTENTS; List of Instances and Applications; List of Figures and Tables; Acknowledgments; Introduction; PART I LOCAL COMPUTATION; 1 Valuation Algebras; 1.1 Operations and Axioms; 1.2 First Examples; 1.3 Conclusion; Appendix: Generalizations of the Valuation Algebra Framework; A.1 Ordered Sets and Lattices; A.1.1 Partitions and Partition Lattices; A.2 Valuation Algebras on General Lattices; A.3 Valuation Algebras with Partial Projection; Problem Sets and Exercises; 2 Inference Problems; 2.1 Graphs, Trees and Hypergraphs; 2.2 Knowledgebases and their Representation2.3 The Inference Problem; 2.4 Conclusion; Problem Sets and Exercises; 3 Computing Single Queries; 3.1 Valuation Algebras with Variable Elimination; 3.2 Fusion and Bucket Elimination; 3.2.1 The Fusion Algorithm; 3.2.2 Join Trees; 3.2.3 The Bucket Elimination Algorithm; 3.2.4 First Complexity Considerations; 3.2.5 Some Generalizing Complexity Comments; 3.2.6 Limitations of Fusion and Bucket Elimination; 3.3 Valuation Algebras with Neutral Elements; 3.3.1 Stable Valuation Algebras; 3.4 Valuation Algebras with Null Elements; 3.5 Local Computation as Message-Passing Scheme3.5.1 The Complexity of Fusion as Message-Passing Scheme; 3.6 Covering Join Trees; 3.7 Join Tree Construction; 3.7.1 Join Tree Construction by Triangulation; 3.8 The Collect Algorithm; 3.8.1 The Complexity of the Collect Algorithm; 3.8.2 Limitations of the Collect Algorithm; 3.9 Adjoining an Identity Element; 3.10 The Generalized Collect Algorithm; 3.10.1 Discussion of the Generalized Collect Algorithm; 3.10.2 The Complexity of the Generalized Collect Algorithm; 3.11 An Application: The Fast Fourier Transform; 3.12 Conclusion; Appendix : Proof of the Generalized Collect AlgorithmProblem Sets and Exercises; 4 Computing Multiple Queries; 4.1 The Shenoy-Shafer Architecture; 4.1.1 Collect & Distribute Phase; 4.1.2 The Binary Shenoy-Shafer Architecture; 4.1.3 Performance Gains due to the Identity Element; 4.1.4 Complexity of the Shenoy-Shafer Architecture; 4.1.5 Discussion of the Shenoy-Shafer Architecture; 4.1.6 The Super-Cluster Architecture; 4.2 Valuation Algebras with Inverse Elements; 4.2.1 Idempotent Valuation Algebras; 4.3 The Lauritzen-Spiegelhalter Architecture; 4.3.1 Complexity of the Lauritzen-Spiegelhalter Architecture4.4 The HUGIN Architecture; 4.4.1 Complexity of the HUGIN Architecture; 4.5 The Idempotent Architecture; 4.5.1 Complexity of the Idempotent Architecture; 4.6 Answering Uncovered Queries; 4.6.1 The Complexity of Answering Uncovered Queries; 4.7 Scaling and Normalization; 4.8 Local Computation with Scaling; 4.8.1 The Scaled Shenoy-Shafer Architecture; 4.8.2 The Scaled Lauritzen-Spiegelhalter Architecture; 4.8.3 The Scaled HUGIN Architecture; 4.9 Conclusion; Appendix: Valuation Algebras with Division; D.1 Properties for the Introduction of Division; Online-Ausg; Palo Alto, Calif; ebrary; 2011; Electronic reproduction; Available via World Wide Web
N2 - "This book provides a rigorous algebraic study of the most popular inference formalisms with a special focus on their wide application area, showing that all these tasks can be performed by a single generic inference algorithm. Written by the leading international authority on the topic, it includes an algebraic perspective (study of the valuation algebra framework), an algorithmic perspective (study of the generic inference schemes) and a "practical" perspective (formalisms and applications). Researchers in a number of fields including artificial intelligence, operational research, databases and other areas of computer science; graduate students; and professional programmers of inference methods will benefit from this work"--; "The book provides a rigorous algebraic study of the most popular inference formalisms with a special focus on their wide application area and shows that all these tasks can be performed by a single generic inference algorithm. It will include an algebraic perspective (study of the valuation algebra framework), an algorithmic perspective (study of the generic inference schemes) and a "practical" perspective (formalisms and applications)"--
UR - http://www.gbv.de/dms/bowker/toc/9780470527016.pdf
ER -