Robust Bayesian inference is the calculation of posterior probability bounds given perturbations in a probabilistic model [3, 22, 38]. This paper presents robust inference algorithms when local perturbations to Bayesian networks are modeled by polytope-like convex sets of distributions.

We consider two ways of defining the combinations of local information in a Bayesian network when convex sets are present.

The first approach generates the largest set of joint distributions that satisfies all constraints from local perturbations. We present the first algorithmic analysis of this approach in the context of graphical models. We show how the robust inference problem can be reduced to a fractional programming problem and then solved through standard linear programming techniques.

The second approach takes the convex hull of all combinations of
vertices in the local convex sets. We discuss exact algorithms for this
problem using the Cano/Cano/Moral (CCM) transform [5].
Due to the complexity of exact algorithms, we develop two classes of
approximation algorithms. Firstly, we demonstrate how to use the CCM
transform to generate *interior-point* algorithms that converge
to robust inferences; the novel idea is to use the CCM transform to
reduce robust inference to a formulation that is similar to the
problem of learning Bayesian networks. Secondly, we use Lavine's
method to reduce the robust inference problem to a particular case of
nonlinear programming for which convergence to a global optimizer is assured.

We discuss generalizations of the results to expected utility and
variance problems, and present the implementation
of local robustness analysis algorithms in the *JavaBayes*
system. We also indicate the existence of global perturbation models,
in contrast to the local models considered in this paper.

This paper presents several novel algorithms for exact robust inferences; such results promise to open the field of robust Bayesian Statistics to graphical approaches. We conclude by presenting several challenges for future research in this area.

Fri May 30 15:55:18 EDT 1997