Lecture 3: Exact Bayesian Inference
- Why is exact inference in Bayesian networks NP-hard?
Program for next week:
- What are factor graphs and how can we derive them from Bayesian networks?
- Apply the message parsing algorithm to factor graphs
What are realistic examples of NP-hard problems?
Ex. resource allocation problems, e.g. crew scheduling in an airport. So how do people then still solve such a problem? We do not always have to care about the optimal solution.
- Local optima; greedy algorithms
- Heuristics
- Integer Linear Programming (ILP)
- Family of resource allocation problems
- Constraint-based?
- Gurobi optimization
Take-away: NP-hard problems are not solvable, but we have to make concessions and apply good shortcuts.
What is Bayesian inference?
Take a Bayesian network and compute some probability; could be marginal or conditional.
But we can narrow it down in this lecture to marginal probabilities, because we can always compute joints and conditionals from that.
We look at a subclass where we only consider marginals for a single variable.
NP recap
REVIEW 25-26: missed an example of somethign that also cannot be verified in NP (?).
3-SAT
3-SAT is shown to be NP-hard; with 3-CNF: conjunction of disjunctions with <= 3 literals per clause.
Any NP verification can be constructed as a "guess and check principle": Imagine we are handed a potential solution, can we verify it in polynomial time?
However to find a solution, you have to try all assignments in worst case; e.g. grid search.
Inference as a decision problem
We're going to transform a 3-CNF formula into a BN.
We have three layers from top to bottom:
- variable layer
- REVIEW where does P come in?
- clause layer
- formula layer
The final node x is the whole formula. Then the decision problem is P(x)>0?
- Then draw an edge from each variable to all clauses in which that variable appears.
- Draw an edge from each clause to the formula node.
Now we need to get the probability tables.
- Assign each variable with p=0.5
- Annotate clauses with a probability that encodes that clause, i.e. identical to their truth table
Note that this network is deterministic.
REVIEW slide 3-10. I had a wrong answer here.
If you make a network this way, the network will have an exponential amount of nodes due to the last node.
Solution: check the final "and" step wise, so each step only has two parameters.
From n+8k+2^k [exponential] -> n + 8k + 4(k-1) [linear in k and n] nodes.
Because we can simulate 3-SAT with a BN (3-SAT < IBN), and 3-SAT is hard, inference in BN is also NP-hard.
Naive marginalization & Distributive Law
Take a Markov Chain with n-variables, x1 -> x2 -> x3 -> x4.
To now compute x4, we marginalize out x1...x3.
Tactic: full common factor out of the sum, using the distributive law.
Result of summands can be written in vector form; operations can then be represented as series of matrix vector products.
$\sum_{x_1} P(x_2|x_1)P(x_1) = P(x_2|X_1=0)P(X_1=0) + P(x_2|X_1=1)P(X_1=1)$
With P(X_1=1)=0.4; and with P(X2=1|X1=0)=0.4; P(X2=1|X1=1)=0.9,
This can be seen as scalars (from $P(X_1)$) multiplied with vectors $P(X_2|X_1)$ resulting in another vector. Variables "higher up" in the factorization can be represented as matrices, so we end up with n-1 matrix-vector products.
E.g. $P(x_2)P(x_3|x_2)$ can be interpreted as a 2x2 matrix with $X_2$ in the columns and $X_3$ in the rows.
Results in n-1 matrix-vector multiplications instead of 2^n additions!
If your BN is a Markov chain, then inference is not NP-hard because we can easily find elimination orderings.
Parents complexity: Complexity goes up insanely hard when we have multiple parents.
Trees and polytrees
- Tree: only exactly one path between any two nodes
- Skeleton: undirected graph that you get by removing direction from edges of directed graph
- Polytree: directed graph whose skeleton is a tree
- Because directed graphs are not necessarily trees; but we still want to exclude cycles
For polytree networks, an efficient elimination ordering is guaranteed to exist.
So for this class of polytree networks, we can do tractable inference!