Variational Inference - Part 1

Introduction

Practically intractable inference tasks emerges in several problems. For this reason the computation of the marginal or posterior probabilities has to be tackled in an approximate fashion.
Our objective is to approximate an intractable distribution $p(x)$ using a simpler distribution $q(x)$. The more obvious choice for quantifying the diversity of two distributions, is the Kullback-Leibler divergence:
$$\begin{equation} \mathbb{KL}(q||p)=\sum_{x} q(x) \log \frac{q(x)}{p(x)} = \mathbb{E}_q[\log \frac{q(x)}{p(x)}] = \mathbb{E}_q[\log q(x)] - \mathbb{E}_q[\log p(x)] \quad (1) \end{equation}$$
We could have chosen the $\mathbb{KL}(p||q)$ but the expectation w.r.t. $p(x)$ is assumed to be intractable.
We can observe that $\mathbb{KL}(q||p) \ge 0$ and is zero only if the two distributions are identical.

Inference as Optimization

Suppose that the probabilistic model we are focusing on is composed by observed variables, globally denoted as ${\bf x}$ and latent variables, globally denoted as ${\bf s}$. Usually we want to compute the posterior distribution:
$$\begin{equation} p({\bf s}| {\bf x}) = \frac{p({\bf x},{\bf s})}{p({\bf x})} = \frac{p({\bf x},{\bf s})}{ \sum_{{\bf s} \in \mathcal{S}}p({\bf x}, {\bf s})} \quad (2) \end{equation}$$
Where $\mathcal{S}$ represents the alphabet containing the possible values of the hidden variables ${\bf s}$.
The presence of the ${\bf s}$ and the necessary marginalization over ${\bf s}$, makes very difficult the exact computation of the $p({\bf x})$.

In Variational Inference, we seek for a function $q({\bf s}) \in \mathcal{Q}$ that approximates the exact conditional $p({\bf s}| {\bf x})$. The inference problem is transformed in an optimization problem where we want to minimize the “distance” between the two distributions:
$$\begin{equation} \hat{q}({\bf s}) = \arg\min_{q({\bf s}) \in \mathcal{Q}} \mathbb{KL}(q({\bf s})||p({\bf s}|{\bf x})) \quad (3) \end{equation}$$
The objective is again not computable. In fact it depends on the Observed Data Log Likelihood $\log p({\bf x})$:
$$\begin{equation} \mathbb{KL}(q({\bf s})||p({\bf s}|{\bf x})) = \mathbb{E}_q[\log q({\bf s})] - \mathbb{E}_q[\log p({\bf s}|{\bf x})] = \mathbb{E}_q[\log q({\bf s})] - \mathbb{E}_q[\log p({\bf x},{\bf s})] + \log p({\bf x}) \quad (4) \end{equation}$$
Instead of minimizing the KL divergence, we optimize another function that is linked to the original objective.

The Evidence Lower Bound

The Observed Data Log Likelihood can be rewritten using an arbitrary distribution $q({\bf s})$ over the hidden variables:
$$\begin{equation} \log p({\bf x}) = \log \Bigg\{ \sum_{{\bf s} \in \mathcal{S}}p({\bf x}, {\bf s}) \Bigg\} = \log \Bigg\{ \sum_{{\bf s}\in \mathcal{S}} q({\bf s}) \ \frac{p({\bf x}, {\bf s})}{q({\bf s})} \Bigg\} \quad (5) \end{equation}$$
Since $\log(u)$ is a concave function, using Jensen’s Inequality for the Observed Data Log Likelihood, we obtain:
$$\begin{equation} \log p({\bf x}) \geq \mathcal{L}({\bf x}, q) \quad (6) \end{equation}$$
where $\mathcal{L}({\bf x}, q)$ is the Evidence Lower Bound defined as:
$$\begin{equation} \mathcal{L}({\bf x}, q) = \sum_{{\bf s} \in \mathcal{S}} q({\bf s}) \log \Bigg\{ \frac{p({\bf x}, {\bf s})}{q({\bf s})} \Bigg\} \quad (7) \end{equation}$$
For any choice of $q({\bf s})$, $\mathcal{L}({\bf x}, q)$ is a lower bound for the Observed Data Log Likelihood.
We can observe that the Evidence Lower Bound is composed by two contributions (an Energy Term and an Entropic Term):
$$\begin{equation} \begin{array}{rcl} \mathcal{L}({\bf x}, q) & = & \displaystyle \sum_{{\bf s} \in \mathcal{S}} q({\bf s}) \log \Bigg\{ \frac{p({\bf x}, {\bf s})}{q({\bf s})} \Bigg\} \\[10pt] & = & \displaystyle \sum_{{\bf s} \in \mathcal{S}} q({\bf s}) \log (p({\bf x}, {\bf s})) - \displaystyle \sum_{{\bf s} \in \mathcal{S}} q({\bf s}) \log(q({\bf s})) \\[10pt] & = & \mathbb{E}_{q({\bf s})}[\log (p({\bf x}, {\bf s}))] + \mathbb{H}(q({\bf s})) \\[10pt] \end{array} \quad (8) \end{equation}$$

Difference between Likelihood and Evidence Lower Bound

An important observation is that the difference between the Observed Data Log Likelihood and the Evidence Lower Bound is proper the KL-divergence between the distribution $q({\bf s})$ and the posterior distribution $p({\bf s}|{\bf x})$ (use (4) and (8)):
$$\begin{equation} \Delta = \log p({\bf x}) - \mathcal{L}({\bf x}, q) = \displaystyle \mathbb{KL}(q({\bf s}) || p({\bf s}|{\bf x})) \ge 0 \quad (9) \end{equation}$$
When $q({\bf s})$ is a good approximation of $p({\bf s}|{\bf x})$, the lower bound $\mathcal{L}({\bf x}, q)$ is closer to $\log p({\bf x})$ and, in particular, when the approximation is perfect ($q({\bf s}) = p({\bf s}|{\bf x})$), $\mathcal{L}({\bf x}, q) = \log p({\bf x})$.

In this way instead of reducing directly $\mathbb{KL}(q({\bf s}) || p({\bf s}|{\bf x}))$, we can find the $q({\bf s})$ that maximizes $\mathcal{L}({\bf x}, q)$.

The maximization of $\mathcal{L}({\bf x}, q)$ reduces $\Delta$ and provides, at the same time, an approximation of the posterior $p({\bf s}|{\bf x})$ and of the log evidence $\log p({\bf x})$ (because $\mathbb{KL}(q({\bf s}) || p({\bf s}|{\bf x}))$ tends to zero).

Now an important point is to find a family function $\mathcal{Q}$ that contains $q({\bf s})$ and that makes the optimization problem simpler.

References

• K. Murphy, Machine Learning: A Probabilistic Approach (§21)
• D. Barber, Bayesian Reasoning and Machine Learning (§28.3)
• I. Goodfellow et al., Deep Learning (§19.1)
• D. Blei et al., Variational Inference: A Review for Statisticians

Written using StackEdit [https://stackedit.io/editor#]

Convolutional Layer of CNN in one Picture

A complete course at Stanford has devoted to Convolutional Neural Network.
The Course Notes (by Andrej Karpathy) are well written and they worth a look.

That course notes have inspired me to create a picture for summarising some concepts.

An interesting summary (adapted from here ) is the following:

Input Layer

• Size: $W_1 \times H_1 \times D_1$
• Hyperparameters:
• Number of filters $K$
• Dimension of the filter $F \times F \times D_1$
• Stride: $S$
• Amount of Zero Padding: $P$

Output Layer

• Size: $W_2 \times H_2 \times D_2$
• $W_2 = \frac{W_1 - F + 2P}{S} + 1$
• $H_2 = \frac{H_1 - F + 2P}{S} + 1$
• $D_2 = K$

The parameter sharing introduces $F \times F \times D_1$ per filter, for a total of $(F \times F \times D_1) \times K$ weights and $K$ biases

In the output volume, the d-th depth slice (of size $W_2 \times H2$) is the result of performing a valid convolution of the d-th filter over the input volume with a stride of $S$, and then offset by d-th bias.

Another interesting post on the Convolutional Neural Network is here

TensorFlow on Databricks

TensorFlow is an Open Source Software Library for Machine Learning and AI tasks.

In these months is becoming a widely used tool in the AI community (and not only).

Databricks is an interesting Cluster Manager based on Apache Spark. It offers a Community Edition for free (pricing).

Since some ML tasks can be very computational intensive (e.g. training of the Deep Networks) could be a good idea to have a Cluster on Databricks and use it.

You can run this Notebook on your Databricks cluster (or import it).

Even though the Notebook says that "It is not required for the Databricks Community Edition", I experimented that it is necessary for the Community Edition as well.