Next: INTERIOR-POINT ALGORITHMS Up: TYPE-1 JOINT CREDAL SETS Previous: TYPE-1 JOINT CREDAL SETS

## EXACT ROBUST INFERENCES

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):

• Add a new variable z'i with no parents to the network. The variable z'i has zi as its only child. If the credal set for variable zi has mi vertices, then z'i has mi integer values z'i = 1, ..., mi;.
• Replace the variable zi by a new variable z''i with the same values of zi, all the parents of zi plus z'i, and the same children of zi. Define the distribution of z''i to be: p(z''i|pa(z''i)) = {( pi,j (zi|pa(zi)) 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 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 [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).

Next: INTERIOR-POINT ALGORITHMS Up: TYPE-1 JOINT CREDAL SETS Previous: TYPE-1 JOINT CREDAL SETS