Inference By Enumeration

Definition: compute desired probability from model

• Query variable given evidence
• Can change with new evidence

P(X1 … Xn) is given

• Evidence variables: E = e
• Query Variables: Q
• Hidden Variables: H
• Sum over all hidden variables on the outside

Evaluation:

• O(d^n) complexity due to hidden variables
• same space to store the distribution
• same # data points to estimate entries in the joint distribution

Variable Elimination

Query: P(Q | E = e1 … E = ek)

• Start with initial factors
• while there are still hidden variables, pick Hj and sum out Hj from the product of all factors mentioning Hj
• Order matters: we want to move summations as far in as possible to reduce the size of each factor → save computation

D-Separation

Independence