Consider a Quasi-Bayesian network where variables z_{i} are
associated to polytopic credal sets with has vertices p_{i,j}.
The CCM transformation modifies each variable z_{i} associated
with a credal set (Figure 2):

- Add a new variable z'
_{i}with no parents to the network. The variable z'_{i}has z_{i}as its only child. If 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 the same 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}.

The variables z'_{i} are called *transparent* variables [5].
Note that each vertex in the original credal set can be obtained by
properly adjusting the transparent variables.

**Figure:** The CCM transformation for variable A

The minimum and maximum values of the posterior credal set can be generated by visiting the vertices of the joint credal set; this can be done by visiting the values of transparent variables.

Suppose one is interested in exact bounds for the posterior p(a|e). One possibility is to cycle over all combinations of transparent variables and use a standard Bayesian inference for each one of them; maxima and minima can be stored as the cycling evolves.

Another exact algorithm comes from trading memory for speed;
the idea is to perform a single standard Bayesian inference to
obtain the joint distribution p(a,e,z'_{i}), which includes all
transparent variables. Maximization and minimization with respect
to the transparent variables produces the required bounds.
These algorithms have been hinted in the analysis of the CCM
transform [5].

Exact algorithms may be practical in cases where a few
credal sets are under consideration, but their complexity grows too fast.
If the network has s credal sets, each credal set represented
by m_{i} vertices, there are prod_{i=1}^{s} m_{i} independent Bayesian
inference runs to be performed.
To tackle large problems, we must use approximations.

Cano, Cano and Moral have looked at approximations that treat the selection of transparent variable values as an integer programming problem; they use probabilistic techniques such as simulated annealing and genetic algorithms to handle such problems [5]. We describe two different approaches to this numerical problem. The first approach investigates interior-point methods for its solution (subsection 4.2). The second approach uses Lavine's algorithm to reduce robust inference to signomial programming [1] (subsection 4.3).

Fri May 30 15:55:18 EDT 1997