Generic Inference E-Book

Marc Pouly

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 780

Veröffentlichungsjahr: 2012

Beschreibung

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.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Dedication

List of Instances and Applications

List of Figures

Acknowledgments

Introduction

Generic Algorithms

Complexity Considerations

Generic Constructions

The Content of this Book

Part I: Local Computation

Part II: Generic Constructions

Part III: Applications

Beyond the Content of this Book

Part I: Local Computation

Chapter 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.2 Valuation Algebras on General Lattices

A.3 Valuation Algebras with Partial Projection

Chapter 2: Inference Problems

2.1 Graphs, Trees and Hypergraphs

2.2 Knowledgebases and their Representation

2.3 The Inference Problem

2.4 Conclusion

Chapter 3: Computing Single Queries

3.1 Valuation Algebras with Variable Elimination

3.2 Fusion and Bucket Elimination

3.3 Valuation Algebras with Neutral Elements

3.4 Valuation Algebras with Null Elements

3.5 Local Computation as Message-Passing Scheme

3.6 Covering Join Trees

3.7 Join Tree Construction

3.8 The Collect Algorithm

3.9 Adjoining an Identity Element

3.10 The Generalized Collect Algorithm

3.11 An Application: The Fast Fourier Transform

3.12 Conclusion

Appendix: Proof of the Generalized Collect Algorithm

Chapter 4: Computing Multiple Queries

4.1 The Shenoy-Shafer Architecture

4.2 Valuation Algebras with Inverse Elements

4.3 The Lauritzen-Spiegelhalter Architecture

4.4 The Hugin Architecture

4.5 The Idempotent Architecture

4.6 Answering Uncovered Queries

4.7 Scaling and Normalization

4.8 Local Computation with Scaling

4.9 Conclusion

Appendix: Valuation Algebras with Division

D.1 Properties for the Introduction of Division

D.2 Proofs of Division-Based Architectures

D.3 Proof for Scaling in Valuation Algebras

Part II: Generic Constructions

Chapter 5: Semiring Valuation Algebras

5.1 Semirings

5.2 Semirings and Order

5.3 Semiring Valuation Algebras

5.4 Examples of Semiring Valuation Algebras

5.5 Properties of Semiring Valuation Algebras

5.6 Some Computational Aspects

5.7 Set-Based Semiring Valuation Algebras

5.8 Properties of Set-Based Semiring Valuation Algebras

5.9 Conclusion

Appendix: Semiring Valuation Algebras with Division

E.1 Separative Semiring Valuation Algebras

E.2 Regular Semiring Valuation Algebras

E.3 Cancellative Semiring Valuation Algebras

E.4 Idempotent Semiring Valuation Algebras

E.5 Scalable Semiring Valuation Algebras

Chapter 6: Valuation Algebras for Path Problems

6.1 Some Path Problem Examples

6.2 The Algebraic Path Problem

6.3 Quasi-Regular Semirings

6.4 Quasi-Regular Valuation Algebras

6.5 Properties of Quasi-Regular Valuation Algebras

6.6 Kleene Algebras

6.7 Kleene Valuation Algebras

6.8 Properties of Kleene Valuation Algebras

6.9 Further Path Problems

6.10 Conclusion

Chapter 7: Language and Information

7.1 Propositional Logic

7.2 Linear Equations

7.3 Information in Context

7.4 Conclusion

Part III: Applications

Chapter 8: Dynamic Programming

8.1 Solutions and Solution Extensions

8.2 Computing Solutions

8.3 Optimization and Constraint Problems

8.4 Computing Solutions of Optimization Problems

8.5 Conclusion

Chapter 9: Sparse Matrix Techniques

9.1 Systems of Linear Equations

9.2 Symmetric, Positive Definite Matrices

9.3 Semiring Fixpoint Equation Systems

9.4 Conclusion

Chapter 10: Gaussian Information

10.1 Gaussian Systems and Potentials

10.2 Generalized Gaussian Potentials

10.3 Gaussian Information and Gaussian Potentials

10.4 Valuation Algebra of Gaussian Potentials

10.5 An Application: Gaussian Dynamic Systems

10.6 An Application: Gaussian Bayesian Networks

10.7 Conclusion

Appendix:

J.1 Valuation Algebra Properties of Hints

J.2 Gaussian Densities

References

Index

GENERIC INFERENCE

Copyright © 2011 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/pennission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Pouly, Marc, 1980–, author.Generic Inference: A Unifying Theory for Automated Reasoning / Marc Pouly, Jürg Kohlas.p. cmIncludes bibliographical references and index.ISBN 978-0-470-52701-6 (hardback)1. Valuation theory. 2. Algorithms. 3. Algebra, Abstract. I. Kohlas, Jürg, 1939–, author. II. Title.QA162.P65 2011519.5′4—dc222010042336

oBook ISBN: 9781118010877 ePDF ISBN: 9781118010846 ePub ISBN: 9781118010860

To Marita and Maria

List of Instances and Applications

1.1 Indicator Functions, Boolean Functions and Crisp Constraints

1.2 Relational Algebra

1.3 Arithmetic Potentials

1.4 Set Potentials

1.5 Density Functions

1.6 Gaussian Densities and Gaussian Potentials

A.7 Set Potentials on Partition Lattices

A.8 Quotients of Density Functions

2.1 Bayesian Networks

2.2 Query Answering in Relational Databases

2.3 Dempster-Shafer Theory of Evidence

2.4 Satisfiability of Constraints and Propositional Logic

2.5 Hadamard Transform

2.6 Discrete Fourier and Cosine Transforms

B.4 Filtering, Prediction and Smoothing in hidden Markov chains

4.4 Probability Potentials

4.5 Probability Density Functions

D.9 Scaling of Belief Functions

5.1 Weighted Constraints, Spohn Potentials and GAI Preferences

5.2 Possibility Potentials, Probabilistic Constraints and Fuzzy Sets

5.3 Set-based Constraints and Assumption-based Reasoning

5.3 Possibility Measures

5.3 Disbelief Functions

E.15 Quasi-Spohn Potentials

E.18 Bottleneck Constraints

6.1 Connectivity Path Problem

6.2 Shortest and Longest Distance Problem

6.3 Maximum Capacity Problem

6.4 Maximum Reliability Problem

6.5 Regular Languages

6.6 Path Counting Problem

6.7 Markov Chains

6.8 Numeric Partial Differentiation

6.9 Matrix Multiplication

F.1 Path Listing Problems

F.2 Testing whether Graphs are Bipartite

F.3 Identifying Cut Nodes in Graphs

F.6 Network Compilation

F.6 Symbolic Partial Differentiation

7.1 Satisfiability in Propositional Logic

7.2 Theorem Proving in Propositional Logic

7.3 Propositional Logic

7.4 Linear Equations Systems and Affine Spaces

7.5 Linear Inequality Systems and Convex Polyhedra

7.6 Predicate Logic

G.1 Consequence Finding in Propositional Logic

8.1 Classical Optimization

8.2 Satisfiability of Constraints and Propositional Logic

8.3 Maximum Satisfiability of Constraints and Propositional Logic

8.4 Most and Least Probable Explanations

8.5 Bayesian and Maximum Likelihood Decoding

8.6 Linear Decoding and Gallager-Tanner-Wiberg Algorithm

9.1 Least Squares Method

9.2 Smoothing and Filtering in Linear Dynamic System

10.1 Gaussian Time-Discrete Dynamic Systems

10.2 Kalman Filter: Filtering Problem

10.3 Gaussian Bayesian Networks

List of Figures

I.1 The graph associated with the inference problem of Exercise I.1.

A.1 A tree of diagnoses for stubborn cars.

2.1 Undirected graphs.

2.2 Directed graphs.

2.3 A labeled graph.

2.4 Hypergraph, primal graph and dual graph.

2.5 Possibilities of knowledgebase representation.

2.6 Bayesian network of a medical example.

2.7 A digital circuit of a binary adder.

2.8 The result table of a full adder circuit.

2.9 Connecting two 1-bit-adders produces a 2-bit-adder.

2.10 Input and output of a discrete Fourier transform.

2.11 Function board of a discrete Fourier transform.

2.12 A hidden Markov chain.

3.1 Finalization of the graphical fusion process.

3.2 Extending a labeled tree to a join tree.

3.3 The bucket-tree of Example 3.5.

3.4 The join tree obtained from the bucket-tree of Figure 3.3

3.5 The join tree for Example 1.2.

3.6 Different elimination sequences produce different join trees.

3.7 A primal graph and its induced graph.

3.8 A covering join tree of an inference problem.

3.9 The fusion algorithm as message-passing scheme.

3.10 A covering join tree of Instance 2.1.

3.11 A covering join tree of Instance 2.1.

3.12 A graph with two possible triangulations.

3.13 The triangulated primal graph of Instance 2.1.

3.14 Join graph and derived join tree.

3.15 A complete run of the collect algorithm.

3.16 Join tree of a discrete Fourier transform.

4.1 Changing the root of a join tree.

4.2 Mailboxes in the Shenoy-Shafer architecture.

4.3 Join tree to illustrate the Shenoy-Shafer architecture.

4.4 Using non-binary join trees creates redundant combinations.

4.5 Larges treewidth due to non-binary join trees.

4.6 The performance gain due to the identity element 1.

4.7 The performance gain due to the identity element 2.

4.8 Illustration of the super-cluster approach.

4.9 Separator in the HUGIN architecture.

4.10 The path between node 1 and node 6 in the join tree of Figure 4.3.

4.11 A graphical summary of local computation architectures.

D.1 Embedding a separative valuation algebra into a union of groups.

D.2 Decomposing a regular valuation algebra into a union of groups.

5.1 Semiring valuation algebras with neutral and null elements.

E.1 Embedding a separative semigroup into a union of groups.

E.2 Decomposing a regular semigroup into a union of groups.

E.3 Embedding a cancellative semigroup into a group.

E.4 Semiring valuation algebras and division-related properties.

6.1 The connectivity path problem.

6.2 The shortest distance problem.

6.3 The maximum capacity problem.

6.4 The maximum reliability problem.

6.5 Determining the language of an automaton.

6.6 Path sets in cycled graphs may be infinite.

6.7 The adjacency matrix of a directed, weighted graph.

6.8 An interpretation of equation (6.32).

6.9 The path counting problem.

6.10 Interpreting computations in Markov chains as path problems.

6.11 The computational graph of a function.

8.1 A binary, unreliable, memoryless communication channel.

8.2 The join tree that belongs to the node factors of Example 8.4.

8.3 A serial connection of unreliable, memoryless channels.

8.4 A parallel connection of unreliable, memoryless channels.

9.1 Zero-pattern of a linear equation system.

9.2 The join tree for Figure 9.1.

9.3 The join tree induced by the variable elimination in Example 9.1.

9.4 Recursive buildup of lower triangular matrices.

9.5 The join tree of Example 9.3.

9.6 The graph representing the non-zero pattern of Example 9.4.

9.7 The join tree of the triangulated graph in Figure 9.6.

9.8 The join tree covering the equations of the linear dynamic system.

9.9 A path problem with values from a partially ordered semiring.

10.1 A causal model for the wholesale price of a car.

10.2 The graph of the time-discrete dynamic system.

10.3 A covering join tree for the system (10.6).

10.4 Influence among variables in the Kalman filter model.

10.5 A covering join tree for the Kalman filter model.

Acknowledgments

The authors would like to thank our collaborators from the Department of Informatics at the University of Fribourg (Switzerland), the Cork Constraint Computation Centre at the University College Cork (Ireland) and the Interdisciplinary Centre for Security, Reliability and Trust at the University of Luxembourg for the many interesting discussions that helped to improve the content and presentation of this book. In particular, we are grateful for the indispensable support of Christian Eichenberger during our journey through the Gaussian world and to Radu Marinescu and Nic Wilson for providing expert knowledge regarding inference, search methods and semiring systems. Jutta Langel and Jacek Jonczy both corrected parts of this book and provided valuable feedback. Special thank also goes to Cassie Craig from John Wiley & Sons, Inc. for the editing support and to the Swiss National Science Foundation, which financed the research stay of Marc Pouly at the Cork Constraint Computation Centre.

Marc Pouly & Jürg Kohlas

PART I

LOCAL COMPUTATION