We start by considering exact algorithms. Cano et all. considered the same type of structures analyzed here, focusing more on the axiomatic aspects of inference, and producing explicit algorithms for networks with polytree topology [Cano, Delgado, & Moral1993]. Here we discuss how to generate exact algorithms for arbitrary networks associated with finitely generated credal sets.

The technique we use to generate exact algorithms is based on a transformation that operates on the Quasi-Bayesian network and produces a Bayesian network. This transformation is central to our exact and approximate algorithms.

Start from a network where some
variables are associated with credal sets. Call these variables z_{i}.
For each variable z_{i}, suppose its credal set has
m_{i} vertices p_{i,j}.

The basic transformation starts by modifying the original Bayesian network:

- For each variable z
_{i}associated with a credal set:- Add a new variable z'
_{i}with no parents to the network. The variable z'_{i}has z_{i}as its only child. The credal set for variable z_{i}has m_{i}vertices, then z'_{i}has m_{i}integer values:z'

_{i}= { 1, ..., m_{i}}. - Replace the variable z
_{i}by a new variable z''_{i}with the same values of z_{i}, all the parents of z_{i}plus z'_{i}, and all the children of z_{i}. Define the distribution of z''_{i}to be:p(z''

_{i}|pa (z''_{i})) = {(p _{i,j}(z_{i}|pa (z_{i}))when z'_{i}= j}.

- Add a new variable z'

Figure 2 illustrates the basic transformation.
Call the variables z'_{i} *artificial* variables.
The original network represents a finitely generated credal set, and each
vertex in this credal set can be obtained by setting the artificial
variables to arbitrary values. This is the crucial property of the
basic transformation.

**Figure 2:** The basic transformation for the
credal set associated with variable A

Consider a network with s credal sets, each credal set represented
by m_{i} vertices. There are M = prod_{i=1}^{s} m_{i} possible vertices in
the joint credal set.
Based on the previous discussion, we have an exact algorithm for
computation of posterior bounds as follows.

- Initialize the lower and upper bounds for the posterior marginals with ones and zeros respectively.
- Run any Bayesian inference algorithm on the transformed network, for each one of the M vertices of the original Quasi-Bayesian network. Each vertex is generated by fixing the values of the artificial variables. For each vertex, store the posterior marginal values that are smaller than the lower bounds, and the posterior marginal values that are larger than the upper bounds.

The algorithm has essentially the same memory requirements as usual Bayesian inferences. The drawback is that the algorithm does not use computations efficiently, wasting calculations by repeating the same inferences again and again. To speed up the algorithm, an implementation must cache parts of the network that have no credal sets, for example by forming cliques of those parts and caching intermediate results for such cliques. Based on this idea, a new algorithm can be devised which which trades memory requirements for speed. Instead of repeating computations, the following algorithm performs a single Bayesian inference in the transformed network.

- Run any Bayesian inference algorithm on the transformed network,
leaving the values of the artificial variables unspecified, such that
they form a single cluster. The result is
the conditional p(x
_{q}| { z'_{i}}). - Initialize the lower and upper bounds for the posterior marginals with ones and zeros respectively.
- For all combinations of values for the artificial variables, store the posterior marginal values that are smaller than the lower bounds, and the posterior marginal values that are larger than the upper bounds.

Tue Jan 21 15:59:56 EST 1997