foundations of computational agents
The notion of conditional independence is used to give a concise representation of many domains. The idea is that, given a random variable , there may be a few variables that directly affect the ’s value, in the sense that is conditionally independent of other variables given these variables. The set of locally affecting variables is called the Markov blanket. This locality is exploited in a belief network.
A belief network is a directed model of conditional dependence among a set of random variables. The conditional independence in a belief network takes in an ordering of the variables, and results in a directed graph.
To define a belief network on a set of random variables, , first select a total ordering of the variables, say, . The chain rule (Proposition 8.3) shows how to decompose a conjunction into conditional probabilities:
Or, in terms of random variables and probability distributions,
Define the parents of random variable , written , to be a minimal set of predecessors of in the total ordering such that the other predecessors of are conditionally independent of given . Thus probabilistically depends on each of its parents, but is independent of its other predecessors. That is, such that
When there are multiple minimal sets of predecessors satisfying this condition, any minimal set may be chosen to be the parents. There can be more than one minimal set only when some of the predecessors are deterministic functions of others.
Putting the chain rule and the definition of parents together gives:
The probability over all of the variables, , is called the joint probability distribution. A belief network defines a factorization of the joint probability distribution into a product of conditional probabilities.
A belief network, also called a Bayesian network, is an acyclic directed graph (DAG), where the nodes are random variables. There is an arc from each element of into . Associated with the belief network is a set of conditional probability distributions that specify the conditional probability of each variable given its parents (which includes the prior probabilities of those variables with no parents).
Thus, a belief network consists of
a DAG, where each node is labeled by a random variable
a domain for each random variable, and
a set of conditional probability distributions giving for each variable .
A belief network is acyclic by construction. How the chain rule decomposes a conjunction depends on the ordering of the variables. Different orderings can result in different belief networks. In particular, which variables are eligible to be parents depends on the ordering, as only predecessors in the ordering can be parents. Some of the orderings may result in networks with fewer arcs than other orderings.
Consider the four variables of Example 8.12, with the ordering: , , , . Consider the variables in order. does not have any predecessors in the ordering, so it has no parents, thus . is independent of , and so it too has no parents. depends on both and , so
is independent of and given and so
The corresponding belief network is given in Figure 8.2.
This graph defines the decomposition of the joint distribution:
In the examples below, the domains of the variables are simple, for example the domain of may be or it could be the actual text answers.
The independence of a belief network, according to the definition of parents, is that each variable is independent of all of the variables that are not descendants of the variable (its non-descendants) given the variable’s parents.