Distributed anytime generic inference in valuation algebras

Thesis

In this thesis, we construct a general theoretical framework for anytime inference which automatically gives us instantiations of inference in various important domains, such as Bayesian networks, relational algebras, disjunctive normal forms and set potentials in Dempster-Shafer theory. Our framework is based on local computation schemes for inference, which perform inference by message-passing on junction trees. We also undertake an analysis of distributed inference. Our theoretical framework is implemented as a software library to illustrate examples of anytime inference using the theoretical framework.

Exact inference in general is a #P-hard problem. Due to the prohibitive computational complexity, approximate inference is well-studied. In many applications a coarse approximation is sufficient. Ideally we would like such an approximation process to be anytime. In an anytime algorithm, the approximation improves monotonically with time, and the process can be interrupted and resumed without restarting. This is especially useful in domains where time may be limited such as continuous learning and robotics. While there are several domain-specific anytime algorithms, little work has been done on generalisation. It is advantageous to develop a theoretical framework which can work for several domains, including statistical and logical inference. We use the theory of generic inference, a unification of prior local computation schemes, as a starting point for our framework. In generic inference, information is represented as elements of an algebra called a valuation algebra, with certain axioms for approximate and exact inference. We introduce axioms and operations on valuation algebras to support anytime inference. We illustrate anytime inference with applications to several domains.

Computational overhead can also be reduced by making the algorithm distributed. For our algorithm, we analyse the tradeoffs between computational, communication and synchronisation costs. We give bounds on the number of processors for maximum concurrency and describe a processor assignment algorithm for optimisation of communication costs.

The overall aim of the thesis is to contribute to the study of anytime inference, and to do so in a manner that enables some measure of control over the degree of approximation and easy applicability to a wide range of domains.

Authors: Dasgupta, A

• DOI: 10.5287/ora-6ggqbry1b
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford