Probabilistic Inference
& Bayesian Networks
CS 3491 – Artificial Intelligence and Machine Learning
Unit 2: Probabilistic Reasoning
Probabilistic Inference: Overview
• Task: Compute posterior probability distribution P(X|e)
• X = query variable (what we want to know)
• E = evidence variables (observed events)
• Y = hidden/nonevidence variables
• Goal: Determine probability given observed data
Key Notation & Definitions
X = Query variable
E = Set of evidence variables (E₁, ..., Em)
e = Particular observed event
Y = Hidden variables (Y₁, ...)
Complete variable set = X ∪ E ∪ Y
Burglary Network Example
Observed Events:
• JohnCalls = true
• MaryCalls = true
Query: What is the probability that a burglary has occurred?
Calculate: P(Burglary | JohnCalls=true, MaryCalls=true)
Inference by Enumeration
• Compute conditional probability from full joint distribution
• Bayesian network provides complete representation
• Terms P(x,e,y) can be written as products of conditional probabilities
• Algorithm: ENUMERATE-JOINT-ASK
Computing with CPT Entries
Query: P(Burglary | JohnCalls=true, MaryCalls=true)
Hidden variables: Earthquake and Alarm
Semantic: P(b|j,m) = α P(b) Σₐ Σₑ P(a|b,e) P(e) P(j|a) P(m|a)
Expression computed by multiplying CPT entries from network and summing over all combinations of hidden variables
Algorithmic Optimization
• Constant terms moved outside summations
• P(b) is constant: move before Σₐ and Σₑ
• P(e) moves before Σₐ: P(b|j,m) = α P(b) Σₑ P(e) Σₐ P(a|b,e) P(j|a) P(m|a)
• Loop through variables in order, multiply CPT entries
• For each summation, loop over variable's possible values
Burglary Calculation Results
Compute by adding four terms (multiplying five numbers each)
P(b | j, m) = α × 0.00059224
P(¬b | j, m) = α × 0.0014919
Final Result: P(burglary|j,m) ≈ 0.284 or 28.4%
Probability of burglary given both neighbors called
Variable Elimination Algorithm
• Improves enumeration substantially - avoids repeated calculations
• Dynamic programming approach: calculate once, save results
• Evaluates expressions right-to-left (bottom-up)
• Stores intermediate results for reuse
• Summations performed only on relevant expression portions
• Drops irrelevant variables early to reduce computation
Complexity of Exact Inference
• Time and space requirements dominated by largest factor
• Largest factor size determined by:
• Variable elimination order
• Network structure/topology
Worst case for n Boolean variables: O(n2ⁿ)
Polytrees: Linear Complexity Networks
• Property: At most ONE undirected path between any two nodes
• Also called: singly connected networks
Time complexity: LINEAR in network size
Space complexity: LINEAR in network size
• Size measure: number of CPT entries
• Holds for any topological ordering (if bounded parents)
Multiply Connected Networks
• Multiple undirected paths between some nodes
Variable elimination: EXPONENTIAL time/space worst-case
• Happens even with bounded parents per node
• Includes propositional logic inference as special case
Bayesian network inference is NP-hard
Problem is #P-hard: strictly harder than NP-complete
Connection to CSPs
• Close theoretical connection between BN and CSP complexity
• Discrete CSP solving difficulty relates to constraint graph "tree-likeness"
• Hypertree width: complexity measure for both BN and CSP
• Same bounding measures apply to Bayesian networks
• Variable elimination algorithm generalizes to solve CSPs AND Bayesian networks
Key Takeaways
✓ Probabilistic inference computes posterior probabilities
✓ Multiple algorithms with different complexity profiles
✓ Network structure critically affects computation
✓ General inference is computationally hard (NP-hard)
Thank You!
Questions on Probabilistic Inference?
CS 3491 – Unit 2: Probabilistic Reasoning