Exact Inference

in Bayesian Networks
CS 3491 – Artificial Intelligence and Machine Learning

Unit 2: Probabilistic Reasoning & Inference

Fundamental Task
• The basic task for any probabilistic inference system is to compute the posterior probability
distribution for a set of query variables
• Given: some observed event – assignment of values to a set of evidence variables
• Query asks for: the posterior probability distribution P(X|e)
• Where X denotes the query variable we want to infer
• Complete set of variables: X ∪ E ∪ Y (query, evidence, and hidden variables)
• A typical query asks for the posterior probability distribution P(X|e)
Notation & Definitions
• X denotes the query variable
• E denotes the set of evidence variables E₁, . . . , Em
• e is a particular observed event
• Y will denote the nonevidence variables Y₁, . . . (sometimes called the hidden variables)
• Thus, the complete set of variables: X = {X} ∪ E ∪ Y
• Typical query: What is the posterior probability distribution P(X|e)?
Burglary Network Example
Observed Events:

• JohnCalls = true
• MaryCalls = true

Query: Probability that a burglary has occurred?

P(Burglary | JohnCalls=true, MaryCalls=true) = ?
Inference by Enumeration
• Conditional probability can be computed by summing terms from the full joint distribution
• A Bayesian network gives a complete representation of the full joint distribution
• The terms P(x, e, y) in the joint distribution can be written as products of conditional probabilities
from the network
• A query can be answered using a Bayesian network by computing sums of products of
conditional probabilities from the network
• The ENUMERATE-JOINT-ASK algorithm can be modified to take a Bayesian network and "look
up" joint entries by multiplying CPT entries.
Computing with CPT Entries
Consider the query P(Burglary | JohnCalls = true, MaryCalls = true)
The hidden variables for this query are Earthquake and Alarm
Using initial letters for variables:
P(b|j,m) = α P(b) Σₑ P(e) Σₐ P(a|b,e) P(j|a) P(m|a)
The semantics of Bayesian networks gives us an expression in terms of CPT entries
Algorithmic Optimization
• An improvement can be obtained from simple observations
• The P(b) term is a constant and can be moved outside the summations over a and e
• The P(e) term can be moved outside the summation over a
• Hence: P(b|j,m) = α P(b) Σₑ P(e) Σₐ P(a|b,e) P(j|a) P(m|a)
• This expression can be evaluated by looping through the variables in order, multiplying CPT
entries as we go
• For each summation, we also need to loop over the variable's possible values
Calculation Results
Using the numbers from the CPT values, we obtain:

P(b | j, m) = α × 0.00059224
P(¬b | j, m) = α × 0.0014919

Hence, the normalization gives us:

P(Burglary | JohnCalls, MaryCalls) ≈ 0.284

That is, the chance of a burglary, given calls from both neighbors, is about 28%
Variable Elimination Algorithm
• The enumeration algorithm can be improved substantially by eliminating repeated calculations
• The idea is simple: do the calculation once and save the results for later use
• This is a form of dynamic programming – several versions of this approach exist
• Variable elimination is the simplest version
• It works by evaluating expressions in right-to-left order (bottom-up)
• Intermediate results are stored, and summations over each variable are done only for those
portions of the expression that depend on the variable
Complexity Analysis
• Variable elimination is more efficient than enumeration: avoids repeated computations and drops
irrelevant variables
• Time and space requirements are dominated by the size of the largest factor constructed during
the operation of the algorithm
• This largest factor size is determined by:
• The order of elimination of variables
• The structure of the network
• Worst case for a network with n Boolean variables: O(n·2ⁿ)
• In the worst case, where we have to sum out almost all the variables, this complexity is achieved
Polytrees: Linear Complexity
• The burglary network belongs to the family of networks with at most one undirected path
between any two nodes in the network
• These are called singly connected networks or polytrees
• They have a particularly nice property: Time and space complexity of exact inference in
polytrees is LINEAR in the size of the network
• The size is defined as the number of CPT entries
• If the number of parents of each node is bounded by a constant, then the complexity will also be
linear in the number of nodes
• These results hold for any ordering consistent with the topological ordering of the network
Multiply Connected Networks
• For multiply connected networks (multiple paths between nodes), variable elimination can have
EXPONENTIAL time and space complexity in the worst case
• This occurs even when the number of parents per node is bounded
• This is not surprising because inference in Bayesian networks includes inference in propositional
logic as a special case
• Inference in Bayesian networks is NP-hard
• The problem is as hard as computing the number of satisfying assignments for a propositional
logic formula
• It is #P-hard ("number-P hard") – strictly harder than NP-complete problems
Connection to CSPs
• There is a close connection between the complexity of Bayesian network inference and the
complexity of constraint satisfaction problems (CSPs)
• The difficulty of solving a discrete CSP is related to how "tree-like" its constraint graph is
• Measures such as hypertree width, which bound the complexity of solving a CSP, can also be
applied directly to Bayesian networks
• Moreover, the variable elimination algorithm can be generalized to solve CSPs as well as
Bayesian networks
• This demonstrates the deep theoretical connection between these two problem domains
 Thank You!
Questions on Probabilistic Inference?
CS 3491 – Unit 2: Probabilistic Reasoning