Belief Revision


Modeling Belief Change on Epistemic States

AAAI Conferences

Belief revision always results in trusting new evidence, so it may admit an unreliable one and discard a more confident one. We therefore use belief change instead of belief revision to remedy this weakness. By introducing epistemic states, we take into account of the strength of evidence that influences the change of belief. In this paper, we present a set of postulates to characterize belief change by epistemic states and establish representation theorems to characterize those postulates. We show that from an epistemic state, a corresponding ordinal conditional function by Spohn can be derived and the result of combining two epistemic states is thus reduced to the result from combining two corresponding ordinal conditional functions proposed by Laverny and Lang. Furthermore, when reduced to the belief revision situation, we prove that our results induce all the Darwiche and Pearl's postulates.


Morphologic for knowledge dynamics: revision, fusion, abduction

arXiv.org Artificial Intelligence

Several tasks in artificial intelligence require to be able to find models about knowledge dynamics. They include belief revision, fusion and belief merging, and abduction. In this paper we exploit the algebraic framework of mathematical morphology in the context of propositional logic, and define operations such as dilation or erosion of a set of formulas. We derive concrete operators, based on a semantic approach, that have an intuitive interpretation and that are formally well behaved, to perform revision, fusion and abduction. Computation and tractability are addressed, and simple examples illustrate the typical results that can be obtained.


Book Reviews

AI Magazine

Conceptual Spaces--The Geometry of Thought is a book by Peter Gärdenfors, professor of cognitive science at Lund University, Sweden. Gärdenfors has authored another book in this series (based on work with Carlos Alchourron and David Makinson), Knowledge in Flux, a definitive account of the widely examined AGM (after Alchourron, Gärdenfors, and Makinson) theory of belief revision. The AGM theory is firmly based on classical logic and its model theory, and by his founding participation in developing it, Gärdenfors has earned the right to critique knowledge representation. His new book is not primarily about logic, but it is certainly not an apostasy either. If I may be permitted a minor irreverence, I would say that this book came not to destroy logic but to fulfill.


Book Review

AI Magazine

The idea is that although an AI system without the frame problem might, say, read an echocardiogram and diagnose a heart defect, a really smart autonomous robot will arrive only if, like us humans, it can handle the frame problem. The highlight … is an entertaining go-round between two pugilists trading blows in civil but gloves-off style, reminiscent of a net discussion. We're still confronted by a difficult question: Is there a solution to it? If not, then R2D2 might forever be but a creature of fiction. If, however, the frame problem is solvable, we must confront yet another question: Is there a general solution to the frame problem, or is the best that can be mustered a so-called domain-dependent solution?


The 2005 AAAI Classic Paper Awards

AI Magazine

Haussler's paper was therefore important in linking the new PAC learning theory work with the ongoing work on machine learning within AI. Twenty years later that link is firmly established, and the two research communities have largely merged into one. In fact, much of the dramatic progress in machine learning over the past two decades has come from a fruitful marriage between research on learning theory and design of practical learning algorithms for particular problem classes. Mitchell and Levesque provide commentary on the two AAAI Classic Paper awards, given at the AAAI-05 conference in Pittsburgh, Pennsylvania. The two winning papers were "Quantifying the Inductive Bias in Concept Learning," by David Haussler, and "Default Reasoning, Nonmonotonic Logics, and the Frame Problem," by Steve Hanks and Drew Mc-Dermott.


Convergence analysis of belief propagation for pairwise linear Gaussian models

arXiv.org Machine Learning

Gaussian belief propagation (BP) has been widely used for distributed inference in large-scale networks such as the smart grid, sensor networks, and social networks, where local measurements/observations are scattered over a wide geographical area. One particular case is when two neighboring agents share a common observation. For example, to estimate voltage in the direct current (DC) power flow model, the current measurement over a power line is proportional to the voltage difference between two neighboring buses. When applying the Gaussian BP algorithm to this type of problem, the convergence condition remains an open issue. In this paper, we analyze the convergence properties of Gaussian BP for this pairwise linear Gaussian model. We show analytically that the updating information matrix converges at a geometric rate to a unique positive definite matrix with arbitrary positive semidefinite initial value and further provide the necessary and sufficient convergence condition for the belief mean vector to the optimal estimate.


Preorder-Based Triangle: A Modified Version of Bilattice-Based Triangle for Belief Revision in Nonmonotonic Reasoning

arXiv.org Artificial Intelligence

Bilattice-based triangle provides an elegant algebraic structure for reasoning with vague and uncertain information. But the truth and knowledge ordering of intervals in bilattice-based triangle can not handle repetitive belief revisions which is an essential characteristic of nonmonotonic reasoning. Moreover the ordering induced over the intervals by the bilattice-based triangle is not sometimes intuitive. In this work, we construct an alternative algebraic structure, namely preorder-based triangle and we formulate proper logical connectives for this. It is also demonstrated that Preorder-based triangle serves to be a better alternative to the bilattice-based triangle for reasoning in application areas, that involve nonmonotonic fuzzy reasoning with uncertain information.


Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow

arXiv.org Machine Learning

Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.


Belief Propagation, Bethe Approximation and Polynomials

arXiv.org Machine Learning

Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partition functions, arise naturally when working with factor graphs. Belief propagation is a widely deployed iterative method for solving these problems. However, despite its significant empirical success, not much is known about the correctness and efficiency of belief propagation. Bethe approximation is an optimization-based framework for approximating partition functions. While it is known that the stationary points of the Bethe approximation coincide with the fixed points of belief propagation, in general, the relation between the Bethe approximation and the partition function is not well understood. It has been observed that for a few classes of factor graphs, the Bethe approximation always gives a lower bound to the partition function, which distinguishes them from the general case, where neither a lower bound, nor an upper bound holds universally. This has been rigorously proved for permanents and for attractive graphical models. Here we consider bipartite normal factor graphs and show that if the local constraints satisfy a certain analytic property, the Bethe approximation is a lower bound to the partition function. We arrive at this result by viewing factor graphs through the lens of polynomials. In this process, we reformulate the Bethe approximation as a polynomial optimization problem. Our sufficient condition for the lower bound property to hold is inspired by recent developments in the theory of real stable polynomials. We believe that this way of viewing factor graphs and its connection to real stability might lead to a better understanding of belief propagation and factor graphs in general.


Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation

arXiv.org Machine Learning

Belief propagation (BP) is an iterative method to perform approximate inference on arbitrary graphical models. Whether BP converges and if the solution is a unique fixed point depends on both the structure and the parametrization of the model. To understand this dependence it is interesting to find \emph{all} fixed points. In this work, we formulate a set of polynomial equations, the solutions of which correspond to BP fixed points. To solve such a nonlinear system we present the numerical polynomial-homotopy-continuation (NPHC) method. Experiments on binary Ising models and on error-correcting codes show how our method is capable of obtaining all BP fixed points. On Ising models with fixed parameters we show how the structure influences both the number of fixed points and the convergence properties. We further asses the accuracy of the marginals and weighted combinations thereof. Weighting marginals with their respective partition function increases the accuracy in all experiments. Contrary to the conjecture that uniqueness of BP fixed points implies convergence, we find graphs for which BP fails to converge, even though a unique fixed point exists. Moreover, we show that this fixed point gives a good approximation, and the NPHC method is able to obtain this fixed point.