Inference refers to the process of computing the posterior probability of a set X of query variables after obtaining some observations . Here Y is a list of observed variables and is the corresponding list of observed values. Often, X consists of only one query variable.
In theory, can be obtained from the marginal probability , which in turn can be computed from the joint probability by summing out variables outside one by one. In practice, this is not viable because summing out a variable from a joint probability requires an exponential number of additions.
The key to more efficient inference lies in the concept of factorization. A factorization of a joint probability is a list of factors (functions) from which one can construct the joint probability.
A factor is a function from a set of variables into a number. We say that the factor contains a variable if the factor is a function of that variable; or say it is a factor of the variables on which it depends. Suppose and are factors, where is a factor that contains variables --- we write this as --- and is a factor with variables , where are the variables in common to and . The product of and is a factor that is a function of the union of the variables, namely , defined by:
Let be a function of variable . Setting, say in to a particular value yields , which is a function of variables .
If is a factor, we can sum out a variable, say , resulting in a factor of variables , defined
where are the possible values of variable .
Because of equation (1), a BN can be viewed as representing a factorization of a joint probability. For example, the Bayesian network in Figure 1 factorizes the joint probability into the following list of factors:
Multiplying those factors yields the joint probability.
Suppose a joint probability is factorized into the multiplication of a list of factors , , ..., . While obtaining by summing out from requires an exponential number of additions, obtaining a factorization of can often be done with much less computation. Consider the following procedure:
Proceduresum-out
:
- Inputs: --- a list of factors; z --- a variable.
- Output: A list of factors.
- Remove from the all the factors, say , ..., , that contain z,
- Add the new factor to and return .
Proof: Suppose consists of factors , , ..., and suppose appears in and only in factors , , ..., . Then
The theorem follows.
Only variables that appear in the factors , , ...,
participated in the computation of
sum-out
, and those are often only a small
portion of all the variables.
This is why inference in a BN can be tractable in many cases, even if the
general problem is NP-hard [5].