Belief-Based Irrelevance and Networks: Toward Faster Algorithms for Predication

Contents

We propose a definition of irrelevance based on notions of plausibility and belief that are well founded in an order-of-magnitude abstraction of probability theory. We then describe how this definition in conjunction with a belief network (to record direct dependencies), can be used to speed up the computations in updating belief after a sequence of actions. The result is an algorithm whose asymptotic complexity is O(E), where E is the number of edges in the network, regardless of the structure of the network. The algorithm presents a conservative behavior in that it is always sound but not always complete. We characterize precisely when the algorithm is complete in terms of irrelevance, and show that completeness can be decided in O(E). Finally, we describe the application of the algorithm for belief update in the context of the kappa calculus (e-semantics), conditional logics of belief, and as an heuristic estimate for probabilistic reasoning.