Approximate Inference for Infinite Contingent Bayesian Networks

Brian Milch
Bhaskara Marthi
David Sontag
Stuart Russell
Daniel L. Ong
Andrey Kolobov

Abstract: In many practical problems — from tracking aircraft based on radar data to building a bibliographic database based on citation lists — we want to reason about an unbounded number of unseen objects with unknown relations among them. Bayesian networks, which define a fixed dependency structure on a finite set of variables, are not the ideal representation language for this task. This paper introduces contingent Bayesian networks (CBNs), which represent uncertainty about dependencies by labeling each edge with a condition under which it is active. A CBN may contain cycles and have infinitely many variables. Nevertheless, we give general conditions under which such a CBN defines a unique joint distribution over its variables. We also present a likelihood weighting algorithm that performs approximate inference in finite time per sampling step on any CBN that satisfies these conditions.

Appeared in: 10th International Workshop on Artificial Intelligence and Statistics, Barbados, January 2005.

Download: PS version, PDF version