Consider a Quasi-Bayesian network where variables zi are associated to polytopic credal sets with has vertices pi,j. The CCM transformation modifies each variable zi associated with a credal set (Figure 2):
The variables z'i are called transparent variables . 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 .
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 mi vertices, there are prodi=1s mi 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 . 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  (subsection 4.3).
Fri May 30 15:55:18 EDT 1997