Lecture 3: Exact Bayesian Inference

  1. Why is exact inference in Bayesian networks NP-hard?

Program for next week:

  1. What are factor graphs and how can we derive them from Bayesian networks?
  2. 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)

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:

  1. variable layer
    • REVIEW where does P come in?
  2. clause layer
  3. 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!