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].