The JavaBayes inference algorithm

 

Now, for the inference algorithm. Please skip this if you do not intend to know the gory details of JavaBayes.

Overview and terminology

The core inference engine in JavaBayes handles arbitrary Bayesian networks. Consider a set x of discrete variables with a finite number of values. A Bayesian network defines a probability distribution through the expression:

  p(x) = prod_i p(x_i | pa(x_i)),

where pa(x_i) is a set of variables, the parents of variable x_i. We use the abbreviation p_i for p(x_i|pa(x_i)); in this notation, a generic Bayesian network can be written as p(x) = prod_i p_i. The evidence e is a set of values for some variables in the network. Write p^e() for a distribution p() with the evidence values fixed. The JavaBayes core engine performs calculation of posterior marginals, expectations, maximum a posteriori explanations and maximum a posteriori expectation for univariate utility functions. The core engine is provided as a Java package which can be adapted and used in other applications as a tool for probabilistic reasoning.

Inferences with Bayesian networks usually involve the calculation of posterior marginals for a particular set of variables, a problem which is called belief assessment or belief updating. Another standard problem is the calculation of expectations for a utility function u(x):

E_p[u|e] = sum_{x not in e} u^e(x) p(x|e),

where p(x|e) indicates the joint distribution conditioned on the evidence. A particular case is u(x) = x_q, in which case the posterior expectation for u(x) is the posterior expected value for the queried variable x_q.

Maximization of probabilities and expectations are respectively called the maximum a posteriori hypothesis problem (called MAP) and the maximum expected utility problem (called MEU) MAP and MEU problems seek to obtain:

  max_d [ sum_{x not in d, e} ( u^{d, e}(x) prod_i p^d,e_i ) ]

for some function u(x); the set of variables d is the set of decision variables. The objective is to find values for the decision variables so that we maximize the expectation of u(x).

The MAP problem is obtained when u(x) = 1:

  max_d [ sum_{x not in d, e} ( prod_i p^{d, e}_i ) ].

A particular case of the MAP problem which has received great attention in the literature is the most probable explanation problem (called MPE), where all variables are decision variables. The MPE solution is the configuration of variables that has highest posterior probability.

Gory details

JavaBayes is centered upon a general algorithm for probabilistic inference, variously called bucket elimination [2] or variable elimination [7]. All the standard problems mentioned above are solved through a generalized version of bucket elimination.

The algorithms are derived for the general case where a set of variables x is under consideration, where x is actually a subset of the full set of variables. It is assumed that x does not overlap with the evidence. When marginals or expectations involve a single variable x_q, we can take x = x_q without any modifications in the algorithms.

The basic algorithm in JavaBayes is adapted from Zhang and Poole [7], but is extended to handle maximizations and expectations in the uniform manner suggested by Dechter [2].

Three preliminary steps are necessary. The first step is to incorporate the evidence e into the network. Every probability distribution and utility function is restricted to a domain that contains no evidence. For example, evidence x₂ = 3 transforms a distribution p(x₁, x₂, x₃) into p^e(x₁, x₃) = p(x₁, x₂ = 3, x₃).

Second, select an ordering for the set x, equal to x₁, ... , x_n Call y_i the ith variable in this ordering. Two types of restrictions must be respected by this ordering. If the objective is to solve a MAP or MEU problem, then the decision variables must come last. If not, then the variables in x must come last.

Third, construct a set of functions F containing all probability distributions in the network. If a utility function u(x) is specified, then include u(x) into F.

The idea of the algorithm is to multiply the members of F in the sequence given by the ordering. In doing so we construct the expression for the Bayesian network; the key fact about the algorithm is that it attempts to eliminate variables as soon as possible so that the resulting products are always manageable. Variables are eliminated by summation or maximization depending on the problem.

For all y_i such that y_i is not in x or e, repeat the following.

1. Construct a list B_i of all functions in F containing y_i. These functions are removed from F. This list B_i is called a bucket. The variable y_i is called the bucket variable for bucket B_i.
2. Multiply all distributions in the bucket and obtain a joint function b_i(y_i, Y_i). This function depends on y_i and some other variables which are indicated by Y_i.
3. Either sum out or maximize out y_i from b_i(y_i, Y_i). The result is a function b_i(Y_i) which is then included into F.

To sum y_i out from a function b(), evaluate b_i(Y_i) = sumy_i b_i(y_i, Y_i). To maximize y_i out from a function b_i(y_i, Y_i), evaluate b_i(Y_i) = maxy_i b_i(y_i, Y_i). When a bucket function b_i(y_i, Y_i) is maximized, a second function c_i(Y_i) can be constructed which indicates the value of y_i that maximizes b_i(y_i, Y_i). The function c(Y_i) is used to generate ``best'' configurations if required.

There are several cases to consider after the buckets are processed.

• Suppose that a utility function u(x) was included into F. Two cases are possible:
  • The objective is to calculate posterior expected utility. We have E_p[u] = sumy_n b_n(y_n).
  • The objective is to maximize posterior expected utility given a set of decision variables. Choose y*_n that maximizes b_n(y_n). The maximum expected utility is b_n(y*_n). It is also possible to select values for the decision variables so that expected utility is maximized. Start with y_n = y*_n. Then pick y*_n-1 = c(y*_n); then y*_n-2 = c(y*_n, y*_n-1) and so on, for all decision variables.
• Suppose that no utility function is used. Two cases are possible:
  • The objective is to calculate the posterior marginal p(x). First multiply together the functions b_i for all the buckets B_i such that y_i isinx. This creates a function which is proportional to p(x|e); the posterior marginal for x is obtained by normalizing this function.
  • The objective is to maximize the posterior probability given a set of decision variables. The same procedure used to obtain maximum expected utility can be employed.

The variable ordering used in the algorithm is arbitrary (except for the conditions imposed above), but different orderings lead to different computational loads. A minimum deficiency heuristic search is known to produce efficient orderings in practice [5], but this is not implemented yet in JavaBayes.