Evidence lower bound

Suppose we have an observable random variable ${\displaystyle X}$, and we want to find its true distribution ${\displaystyle p^{*}}$. This would allow us to generate data by sampling, and estimate probabilities of future events. In general, it is impossible to find ${\displaystyle p^{*}}$ exactly, forcing us to search for a good approximation.

That is, we define a sufficiently large parametric family ${\displaystyle \{p_{\theta }\}_{\theta \in \Theta }}$ of distributions, then solve for ${\displaystyle \min _{\theta }L(p_{\theta },p^{*})}$ for some loss function ${\displaystyle L}$. One possible way to solve this is by considering small variation from ${\displaystyle p_{\theta }}$ to ${\displaystyle p_{\theta +\delta \theta }}$, and solve for ${\displaystyle L(p_{\theta },p^{*})-L(p_{\theta +\delta \theta },p^{*})=0}$. This is a problem in the calculus of variations, thus it is called the variational method.

Since there are not many explicitly parametrized distribution families (all the classical distribution families, such as the normal distribution, the Gumbel distribution, etc, are far too simplistic to model the true distribution), we consider implicitly parametrized probability distributions:

• First, define a simple distribution ${\displaystyle p(z)}$ over a latent random variable ${\displaystyle Z}$. Usually a normal distribution or a uniform distribution suffices.
• Next, define a family of complicated functions ${\displaystyle f_{\theta }}$ (such as a deep neural network) parametrized by ${\displaystyle \theta }$.
• Finally, define a way to convert any ${\displaystyle f_{\theta }(z)}$ into a simple distribution over the observable random variable ${\displaystyle X}$. For example, let ${\displaystyle f_{\theta }(z)=(f_{1}(z),f_{2}(z))}$ have two outputs, then we can define the corresponding distribution over ${\displaystyle X}$ to be the normal distribution ${\displaystyle {\mathcal {N}}(f_{1}(z),e^{f_{2}(z)})}$.

This defines a family of joint distributions ${\displaystyle p_{\theta }}$ over ${\displaystyle (X,Z)}$. It is very easy to sample ${\displaystyle (x,z)\sim p_{\theta }}$: simply sample ${\displaystyle z\sim p}$, then compute ${\displaystyle f_{\theta }(z)}$, and finally sample ${\displaystyle x\sim p_{\theta }(\cdot |z)}$ using ${\displaystyle f_{\theta }(z)}$.

In other words, we have a generative model for both the observable and the latent.

Now, we consider a distribution ${\displaystyle p_{\theta }}$ good, if it is a close approximation of ${\displaystyle p^{*}}$:

$${\displaystyle p_{\theta }(X)\approx p^{*}(X)}$$

since the distribution on the right side is over ${\displaystyle X}$ only, the distribution on the left side must marginalize the latent variable ${\displaystyle Z}$ away.

In general, it's impossible to perform the integral ${\displaystyle p_{\theta }(x)=\int p_{\theta }(x|z)p(z)dz}$, forcing us to perform another approximation.

Since ${\displaystyle p_{\theta }(x)={\frac {p_{\theta }(x|z)p(z)}{p_{\theta }(z|x)}}}$, it suffices to find a good approximation of ${\displaystyle p_{\theta }(z|x)}$. So define another distribution family ${\displaystyle q_{\phi }(z|x)}$ and use it to approximate ${\displaystyle p_{\theta }(z|x)}$. This is a discriminative model for the latent.

The entire situation is summarized in the following table:

${\displaystyle X}$: observable	${\displaystyle X,Z}$	${\displaystyle Z}$: latent
${\displaystyle p^{*}(x)\approx p_{\theta }(x)\approx {\frac {p_{\theta }(x|z)p(z)}{q_{\phi }(z|x)}}}$ approximable		${\displaystyle p(z)}$, easy
	${\displaystyle p_{\theta }(x|z)p(z)}$, easy
${\displaystyle p_{\theta }(z|x)\approx q_{\phi }(z|x)}$ approximable		${\displaystyle p_{\theta }(x|z)}$, easy

In Bayesian language, ${\displaystyle X}$ is the observed evidence, and ${\displaystyle Z}$ is the latent/unobserved. The distribution ${\displaystyle p}$ over ${\displaystyle Z}$ is the prior distribution over ${\displaystyle Z}$, ${\displaystyle p_{\theta }(x|z)}$ is the likelihood function, and ${\displaystyle p_{\theta }(z|x)}$ is the posterior distribution over ${\displaystyle Z}$.

Given an observation ${\displaystyle x}$, we can infer what ${\displaystyle z}$ likely gave rise to ${\displaystyle x}$ by computing ${\displaystyle p_{\theta }(z|x)}$. The usual Bayesian method is to estimate the integral ${\displaystyle p_{\theta }(x)=\int p_{\theta }(x|z)p(z)dz}$, then compute by Bayes' rule ${\displaystyle p_{\theta }(z|x)={\frac {p_{\theta }(x|z)p(z)}{p_{\theta }(x)}}}$. This is expensive to perform in general, but if we can simply find a good approximation ${\displaystyle q_{\phi }(z|x)\approx p_{\theta }(z|x)}$ for most ${\displaystyle x,z}$, then we can infer ${\displaystyle z}$ from ${\displaystyle x}$ cheaply. Thus, the search for a good ${\displaystyle q_{\phi }}$ is also called amortized inference.

All in all, we have found a problem of variational Bayesian inference.

A basic result in variational inference is that minimizing the Kullback–Leibler divergence (KL-divergence) is equivalent to maximizing the log-likelihood:

$${\displaystyle \mathbb {E} _{x\sim p^{*}(x)}[\ln p_{\theta }(x)]=-H(p^{*})-D_{\mathit {KL}}(p^{*}(x)\|p_{\theta }(x))}$$

where ${\displaystyle H(p^{*})=-\mathbb {\mathbb {E} } _{x\sim p^{*}}[\ln p^{*}(x)]}$ is the entropy of the true distribution. So if we can maximize ${\displaystyle \mathbb {E} _{x\sim p^{*}(x)}[\ln p_{\theta }(x)]}$, we can minimize ${\displaystyle D_{\mathit {KL}}(p^{*}(x)\|p_{\theta }(x))}$, and consequently find an accurate approximation ${\displaystyle p_{\theta }\approx p^{*}}$. To maximize ${\displaystyle \mathbb {E} _{x\sim p^{*}(x)}[\ln p_{\theta }(x)]}$, we simply sample many ${\displaystyle x_{i}\sim p^{*}(x)}$, i.e. use Importance sampling

$${\displaystyle N\max _{\theta }\mathbb {E} _{x\sim p^{*}(x)}[\ln p_{\theta }(x)]\approx \max _{\theta }\sum _{i}\ln p_{\theta }(x_{i})}$$

[note 1] In order to maximize ${\displaystyle \sum _{i}\ln p_{\theta }(x_{i})}$, it's necessary to find ${\displaystyle \ln p_{\theta }(x)}$:

$${\displaystyle \ln p_{\theta }(x)=\ln \int p_{\theta }(x|z)p(z)dz}$$

This usually has no closed form and must be estimated. The usual way to estimate integrals is Monte Carlo integration with importance sampling:

$${\displaystyle \int p_{\theta }(x|z)p(z)dz=\mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[{\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]}$$

where ${\displaystyle q_{\phi }(z|x)}$ is a sampling distribution over ${\displaystyle z}$ that we use to perform the Monte Carlo integration. So we see that if we sample ${\displaystyle z\sim q_{\phi }(\cdot |x)}$, then ${\displaystyle {\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}}$ is an unbiased estimator of ${\displaystyle p_{\theta }(x)}$. Unfortunately, this does not give us an unbiased estimator of ${\displaystyle \ln p_{\theta }(x)}$, because ${\displaystyle \ln }$ is nonlinear. Indeed, we have by Jensen's inequality,

$${\displaystyle \ln p_{\theta }(x)=\ln \mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[{\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]\geq \mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[\ln {\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]}$$

In fact, all the obvious estimators of ${\displaystyle \ln p_{\theta }(x)}$ are biased downwards, because no matter how many samples of ${\displaystyle z_{i}\sim q_{\phi }(\cdot |x)}$ we take, we have by Jensen's inequality:

$${\displaystyle \mathbb {E} _{z_{i}\sim q_{\phi }(\cdot |x)}\left[\ln \left({\frac {1}{N}}\sum _{i}{\frac {p_{\theta }(x,z_{i})}{q_{\phi }(z_{i}|x)}}\right)\right]\leq \ln \mathbb {E} _{z_{i}\sim q_{\phi }(\cdot |x)}\left[{\frac {1}{N}}\sum _{i}{\frac {p_{\theta }(x,z_{i})}{q_{\phi }(z_{i}|x)}}\right]=\ln p_{\theta }(x)}$$

Subtracting the right side, we see that the problem comes down to a biased estimator of zero:

$${\displaystyle \mathbb {E} _{z_{i}\sim q_{\phi }(\cdot |x)}\left[\ln \left({\frac {1}{N}}\sum _{i}{\frac {p_{\theta }(z_{i}|x)}{q_{\phi }(z_{i}|x)}}\right)\right]\leq 0}$$

By the delta method, we have

$${\displaystyle \mathbb {E} _{z_{i}\sim q_{\phi }(\cdot |x)}\left[\ln \left({\frac {1}{N}}\sum _{i}{\frac {p_{\theta }(z_{i}|x)}{q_{\phi }(z_{i}|x)}}\right)\right]\approx -{\frac {1}{2N}}\mathbb {V} _{z\sim q_{\phi }(\cdot |x)}\left[{\frac {p_{\theta }(z|x)}{q_{\phi }(z|x)}}\right]=O(N^{-1})}$$

If we continue with this, we would obtain the importance-weighted autoencoder.[2] But we return to the simplest case with ${\displaystyle N=1}$:

$${\displaystyle \ln p_{\theta }(x)=\ln \mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[{\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]\geq \mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[\ln {\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]}$$

The tightness of the inequality has a closed form:

$${\displaystyle \ln p_{\theta }(x)-\mathbb {E} _{z\sim q_{\phi }(\cdot |x)}\left[\ln {\frac {p_{\theta }(x,z)}{q_{\phi }(z|x)}}\right]=D_{\mathit {KL}}(q_{\phi }(\cdot |x)\|p_{\theta }(\cdot |x))\geq 0}$$

We have thus obtained the ELBO function:

$${\displaystyle L(\phi ,\theta ;x):=\ln p_{\theta }(x)-D_{\mathit {KL}}(q_{\phi }(\cdot |x)\|p_{\theta }(\cdot |x))}$$

For fixed ${\displaystyle x}$, the optimization ${\displaystyle \max _{\theta ,\phi }L(\phi ,\theta ;x)}$ simultaneously attempts to maximize ${\displaystyle \ln p_{\theta }(x)}$ and minimize ${\displaystyle D_{\mathit {KL}}(q_{\phi }(\cdot |x)\|p_{\theta }(\cdot |x))}$. If the parametrization for ${\displaystyle p_{\theta }}$ and ${\displaystyle q_{\phi }}$ are flexible enough, we would obtain some ${\displaystyle {\hat {\phi }},{\hat {\theta }}}$, such that we have simultaneously

$${\displaystyle \ln p_{\hat {\theta }}(x)\approx \max _{\theta }\ln p_{\theta }(x);\quad q_{\hat {\phi }}(\cdot |x)\approx p_{\hat {\theta }}(\cdot |x)}$$

Since

$${\displaystyle \mathbb {E} _{x\sim p^{*}(x)}[\ln p_{\theta }(x)]=-H(p^{*})-D_{\mathit {KL}}(p^{*}(x)\|p_{\theta }(x))}$$

we have

$${\displaystyle \ln p_{\hat {\theta }}(x)\approx \max _{\theta }-H(p^{*})-D_{\mathit {KL}}(p^{*}(x)\|p_{\theta }(x))}$$

and so

$${\displaystyle {\hat {\theta }}\approx \arg \min D_{\mathit {KL}}(p^{*}(x)\|p_{\theta }(x))}$$

In other words, maximizing the ELBO would simultaneously allow us to obtain an accurate generative model ${\displaystyle p_{\hat {\theta }}\approx p^{*}}$ and an accurate discriminative model ${\displaystyle q_{\hat {\phi }}(\cdot |x)\approx p_{\hat {\theta }}(\cdot |x)}$.[3]

Suppose we take ${\displaystyle N}$ independent samples from ${\displaystyle p^{*}}$, and collect them in the dataset ${\displaystyle D=\{x_{1},...,x_{N}\}}$, then we have empirical distribution ${\displaystyle q_{D}(x)={\frac {1}{N}}\sum _{i}\delta _{x_{i}}}$.

Fitting ${\displaystyle p_{\theta }(x)}$ to ${\displaystyle q_{D}(x)}$ can be done, as usual, by maximizing the loglikelihood ${\displaystyle \ln p_{\theta }(D)}$:

$${\displaystyle D_{\mathit {KL}}(q_{D}(x)\|p_{\theta }(x))=-{\frac {1}{N}}\sum _{i}\ln p_{\theta }(x_{i})-H(q_{D})=-{\frac {1}{N}}\ln p_{\theta }(D)-H(q_{D})}$$

Now, by the ELBO inequality, we can bound ${\displaystyle \ln p_{\theta }(D)}$, and thus

$${\displaystyle D_{\mathit {KL}}(q_{D}(x)\|p_{\theta }(x))\leq -{\frac {1}{N}}L(\phi ,\theta ;D)-H(q_{D})}$$

The right-hand-side simplifies to a KL-divergence, and so we get:

$${\displaystyle D_{\mathit {KL}}(q_{D}(x)\|p_{\theta }(x))\leq -{\frac {1}{N}}\sum _{i}L(\phi ,\theta ;x_{i})-H(q_{D})=D_{\mathit {KL}}(q_{D,\phi }(x,z);p_{\theta }(x,z))}$$

This result can be interpreted as a special case of the data processing inequality.

In this interpretation, maximizing ${\displaystyle L(\phi ,\theta ;D)=\sum _{i}L(\phi ,\theta ;x_{i})}$ is minimizing ${\displaystyle D_{\mathit {KL}}(q_{D,\phi }(x,z);p_{\theta }(x,z))}$, which upper-bounds the real quantity of interest ${\displaystyle D_{\mathit {KL}}(q_{D}(x);p_{\theta }(x))}$ via the data-processing inequality. That is, we append a latent space to the observable space, paying the price of a weaker inequality for the sake of more computationally efficient minimization of the KL-divergence.[4]