I was asked to give the "Inference" tutorial in one of the reading groups here, and wanted to post some of the notes I made from that here.

Behold, the TREE OF LIF... uh, I mean INFERENCE! Gorgeous, right?

What does it all mean. Well! For a given $P_x(x_1 ... x_n)$, we can represent it as a directed, undirected or factor graph. Directed models are best at capturing the conditional independencies of children from non-parents given parents, while undirected and factor graphs are best at capturing conditional independencies of set $x_a$ from $x_b$ given separator set $x_s$.

Exact Inference:

Regardless of graph type, the first thing to consider is whether you should just do direct marginalization via the Elimination Algorithm.

Approximate Inference:

Other options are to try for approximate methods, which fall broadly into Sampling, Variational Inference, and Spectral Methods.

For our given $P$, sampling (Monte Carlo or MC) methods like importance sampling randomly generate samples from some proposal distribution(s) $P^*$. We then evaluate to see how close $P^*$ is to $P$, and compute our weighted approximation. Sampling is widely used because they're often most easy to implement, and (as we hit an infinite number of samples) it converges to $P$. However, sampling methods are slow and they can get stuck in local maxima without

Variational methods pick some distribution $Q$ that is easier to sample from than $P$ and that is close to $P$ is that the KL divergence between them is minimized. Variational inference is often much faster than sampling methods and has the nice guarantee of an improvemnt to the KL Divergence after every iteration. However, variational update equations can be hard to derive, and while there is often good convergence, that convergence is to $Q$ not $P$.

Spectral methods have become popular recently, and are an application of linear algebra techniques to fitting and perform inference in latent variable models.