Houjun Liu


inference is the act of updating the distribution of a random variable based on distribution of actually observed variables:

\begin{equation} P(X|Y) \end{equation}

where \(Y\) is observed, and we want to know how likely \(X\) would therefore be.

We call the set \(X\) the “query variables”, \(Y\) as “evidence varibales”, and anything that we didn’t use which connects the two variables as “hidden variables”.

If things are not in the right order of \(X\) and \(Y\), consider the Bayes rule.

Inference is Hard


Suppose we’d like to know \(P(b^{1} | d^{1}, c^{1})\), where \(b^{1}\) is considered a query variable, and \(c^{1}\) is considered evidence varibales. The definition of the conditional probability gives us:

\begin{equation} p(b^{1} | d^{1}, c^{1}) = \frac{p(b^{1}, d^{1}, c^{1})}{p(d^{1}, c^{1})} \end{equation}

To compute \(p(b^{1}d^{1}c^{1})\), we first compute:

\begin{equation} p(b^{1}, d^{1}, c^{1}, E, S) \end{equation}

and then, use the law of total probability to get:

\begin{equation} p(b^{1}, d^{1}, c^{1}) = \sum_{e=E} \sum_{s=S} p(b^{1}, d^{1}, c^{1}, E, S) \end{equation}

you will note this is very expensive computationally O(es) — and if you have like a 1000 hidden variables you will die.

We therefore introduce sum-product elimination.

sum-product elimination

You will note the summation in the example above has a lot of interlocking for loops. You can “factor them out” via the sum-product elimination algorithm.

Suppose you are interested in:

\begin{equation} P(b | d’, c’) \end{equation}

Step 1: write down factors

Write down all factors associated with this computation:

\begin{equation} \phi_{1}(B), \phi_{2}(S), \phi_{3}(E,B,S), \phi_{4}(D,E), \phi_{5}(C,E) \end{equation}

we have evidence at two variables: \(D, C\).

Step 2: performing factor conditioning for all evidence variables

Therefore, \(\phi_{4}\) and \(\phi_{5}\) can be replaced by the factor conditioning as we observed \(d, c\), so we no longer need \(d, c\) as input because we know them:

now we have, to replace \(\phi_{4}, \phi_{5}\):

\begin{equation} \phi_{6}(E), \phi_{7}(E) \end{equation}

Step 3: using the law of total probability and factor product, get rid of hidden variables

We then choose an ordering of the hidden variables and apply a factor product using the law of total probability to get rid of them:

  • First get rid of any hidden variables
  • Then use factor product to combine results

\begin{equation} \phi_{8}(B,S) = \sum_{E=e} \phi_{3}(E,B,S) \phi_{6}(e) \phi_{7}(e) \end{equation}

\begin{equation} \phi_{9}(B) = \sum_{S=s} \phi_{2}(s) \cdot \phi_{8}(B,S) \end{equation}

We now only have two factors left: \(\phi_{1}(B)\phi_{9}(B)\). We finally apply factor product again:

\begin{equation} \phi_{10} (B) = \phi_{9}(B) \cdot \phi_{1}(B) \end{equation}

Approximate Inference

See Approximate Inference

Gaussian Inference

See Inference for Gaussian Models