Exact algorithms and the basic transformation

 

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.

The basic transformation

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 }.

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

Exact algorithms

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.

Algorithm

1. Initialize the lower and upper bounds for the posterior marginals with ones and zeros respectively.
2. 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.

Algorithm

1. 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 }).
2. Initialize the lower and upper bounds for the posterior marginals with ones and zeros respectively.
3. 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.