Inference By Enumeration

General Info

What

Inference by enumeration is the general framework for solving inference queries when a joint distribution is given

Structure

General inference queries will have the following attributes

• $E = e_1, e_2,..,e_n$. Observed evidence variables
• $Q$. Query variables, or variables we wish to know the probability of
• $H = h_1, h_2,..., h_n$. Hidden variables, variables that are along for the ride but that we don't care about

The general query structure is $P(Q|e_1,e_2,...,e_n)$

How

1. a new table with elements from the joint distribution table that matches the evidence
2. Squeeze the table out by the hidden variables
3. Normalize the result

Disadvantages

• is $O(d^n)$. At worst, we could end up examining every entry in the joint distribution
• Space complexity is $O(d^n)$. We have to load the entire joint distribution into memory before working on it