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#]

Maximum Likelihood Estimation and Empirical Distribution

The Maximum Likelihood Estimation (MLE) is a method that finds the set of parameters $\hat{\theta}$ of a parametric model  $p_M({\bf x; \theta})$ that makes the data ${\bf X} = \{ {\bf x}^{(t)} \}_{t = 1}^{T}$, drawn from a true but unknown data generating distribution $p_D({\bf x})$, most likely. In other words we are looking for a parametric model $p_M({\bf x; \hat{\theta}})$ that can describe better the data.

The Data Likelihood is $p_M({\bf X} | \theta) = p_M({\bf x}^{(1)} ... {\bf x}^{(T)} | \theta)$ and, since the examples are Independent and Identically Distributed (i.i.d.), can be rewritten as $\displaystyle \prod_{t=1}^{T} p_M({\bf x}^{(t)} | \theta)$ and the Maximum Likelihood Estimation becomes:
\begin{equation}
\begin{array}{rcl}
\hat{\theta} & = & argmax_{\theta} \bigg\{ p_M({\bf x}^{(1)} ... {\bf x}^{(T)} | \theta) \bigg\} \\
& = & argmax_{\theta} \bigg\{ \displaystyle \prod_{t=1}^{T} p_M({\bf x}^{(t)} | \theta) \bigg\} \\
& = & argmax_{\theta} \bigg\{ \displaystyle \sum_{t=1}^{T} \log p_M({\bf x}^{(t)} | \theta) \bigg\}
\end{array}
\end{equation}
The last equation is due to observation that taking the logarithm of the likelihood does not change its argmax but does conveniently transform a product into a sum reducing underflow problems in the calculation.
We can rescale the cost function dividing by $T$ obtaining the final form of the MLE:

\begin{equation}
\hat{\theta} = argmax_{\theta} \bigg\{ \frac{1}{T} \displaystyle \sum_{t=1}^{T} \log p_M({\bf x}^{(t)} | \theta) \bigg\}
\end{equation}

Recalling that the Empirical Distribution is a distribution that puts probability mass of $\frac{1}{T}$ on each of the $T$ points $\{ {\bf x}^{(t)} \}_{t = 1}^{T}$:
\begin{equation}
\hat{p}_D({\bf x}) = \frac{1}{T} \displaystyle \sum_{t=1}^{T} \delta({\bf x - x}^{(t)})
\end{equation}

we can rewrite our estimation problem as:
\begin{equation}
\begin{array}{rcl}
\hat{\theta} & = & argmax_{\theta} \bigg\{ \frac{1}{T} \displaystyle \sum_{t=1}^{T} \log p_M({\bf x}^{(t)} | \theta) \bigg\} \\
& = & argmax_{\theta} \bigg\{ \frac{1}{T} \displaystyle \sum_{t=1}^{T} \log p_M({\bf x} | \theta) \delta({\bf x - x}^{(t)}) \bigg\} \\
& = & argmax_{\theta} \bigg\{ \mathbb{E}_{{\bf x} \sim \hat{p}_D} \log p_M({\bf x} | \theta) \bigg\}
\end{array}
\end{equation}
In the following we will demonstrate that MLE is the same that minimizing the KL Divergence between the empirical distribution and the model distribution.

The KL Divergence between the empirical distribution $\hat{p}_D({\bf x})$ and the model distribution $p_M({\bf x|\theta})$ is:
\begin{equation}
\begin{array}{rcl}
\mathbb{D}_{KL}(\hat{p}_D||p_M) & = & \displaystyle \mathbb{E}_{{\bf x} \sim \hat{p}_D} \Big (\log \frac{\hat{p}_D({\bf x})}{p_M({\bf x|\theta})} \Big) \\
& = &\displaystyle \mathbb{E}_{{\bf x} \sim \hat{p}_D} \Big (\log \hat{p}_D({\bf x}) \Big ) - \mathbb{E}_{{\bf x} \sim \hat{p}_D({\bf x})} \Big (\log p_M({\bf x|\theta}) \Big)\\
\end{array}
\end{equation}

Since the first term is not dependent from $\theta$, when we train the model to minimize KL divergence, we need only to minimize the cross-entropy between the empirical distribution defined by the training set ($\hat{p}_D({\bf x})$) and the model ($p_M({\bf x|\theta})$):
\begin{equation}
\mathbb{H}(\hat{p}_D({\bf x}),p_M({\bf x|\theta})) = - \mathbb{E}_{{\bf x} \sim \hat{p}_D({\bf x})} \Big (\log p_M({\bf x|\theta}) \Big)
\end{equation}
which is, the negative of the term we try to maximize in MLE.

We can thus see Maximum Likelihood Estimation as an attempt to make the model distribution match the Empirical Distribution $\hat{p}_D({\bf x})$. Ideally, we would like to match the true data generating distribution $p_D({\bf x})$ but we don have a direct access to this distribution and the Empirical Distribution is the best we can have.

Usually, instead of Maximizing the Log-Likelihood, we Minimize the Negative Log-Likelihood (equivalently Minimize the Cross-Entropy) leading to the following equation:
\begin{equation}
\begin{array}{rcl}
\hat{\theta} = argmin_{\theta} \bigg\{ - \mathbb{E}_{{\bf x} \sim \hat{p}_D} \log p_M({\bf x} | \theta) \bigg\} \\
\end{array}
\end{equation}

We can conclude that the empirical distribution is the probability density that maximizes the likelihood of the training data.

Note:
The Dirac delta distribution is only necessary to define the empirical distribution over continuous variables. For discrete variables an empirical distribution is categorical distribution, with a probability associated to each possible input value that is simply equal to the empirical frequency of that value in the training set.


This post has been inspired by I. Goodfellow et al. Deep Learning (5.5)

Back Propagation

An useful link for understanding the Back Propagation step by step

Link

Common Probability Distributions

An interesting introduction to the most used Probability Distributions.

LINK

MLP - Multilayer Perceptron (Output Function)

Conda Environments

Anaconda Environments

Anaconda is an open data science platform powered by Python. The user can create separate environments. The following table is a simple summary of the information you can find here

Operation	Windows	Linux, OS X
Create a new conda environment	conda create -n envName python=2.7	The Same of Windows
List the conda environments	conda env list	The Same of Windows
Change environments	activate envName	source activate envName
Deactivate the environment	deactivate	source deactivate

Some interesting videos on Deep Learning [Work in Progress]

This post shall contain some interesting videos on Deep Learning. The list shall be continuously updated [Last Update 20 Aug. 2017].

Deep Learning

• Deep Learning Summer School 2015 - Deep Learning Summer School 2015
• Deep Learning Summer School 2016 - Deep Learning Summer School 2016
• Deep Learning Summer School 2017 - Deep Learning and Reinforcement Learning Summer School 2017

• Bay Area School 2016 Day1 - Bay Area Deep Learning School Day 1
• Bay Area School 2016 Day2 - Bay Area Deep Learning School Day 2

MapReduce in Apache Spark

Based on the Course CS120x Distributed Machine Learning with Apache Spark.

Basically we can summarize the map/reduce paradigm as following:

• Map: transforms a series of elements by applying a function individually to each element in the series. It then returns the series of transformed elements.
• Filter: applies a function individually to each element in a series but, the function evaluates to True or False and only elements that evaluate to True are retained.
• Reduce: operates on pairs of elements in a series. It applies a function that takes in two values and returns a single value. Using this function, reduce is able to, iteratively, “reduce” a series to a single value.

We have define an array of 10 elements and transform it in a Resilient Distributed Dataset (RDD)

numberRDD = range(0,10)
numberRDD = sc.parallelize(numberRDD, 4)
numberRDD.collect()
> Out[1]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

Map the numberRDD using a lambda function that mulitplies each element by 5

numberRDD.map(lambda x:x*5).collect()
> Out[2]: [0, 5, 10, 15, 20, 25, 30, 35, 40, 45] 

Filter the numberRDD in order to obtain only the number multiple of 2

numberRDD.filter(lambda x:x%2==0).collect()
> Out[3]: [0, 2, 4, 6, 8]

Reduce the numberRDD summing pairs of numbers

numberRDD.reduce(lambda x1,x2:x1+x2)
> Out[4]: [45]

Putting all together we obtain the sum of the numbers in the even positions

numberRDD.map(lambda x:x*5).filter(lambda x:x%2==0).reduce(lambda x1,x2:x1+x2)
> Out[5]: [100]

This post has been written using Markdown and Dillinger. Here an interesting Markdown Cheatsheet

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.