Evidence Lower Bound (ELBO)
A basic approach to approximate the evidence P(D) using sampling. E.g. in importance sampling, we approximate the marginal likelihood P(D) as the expectation over likelihood times prior relative to a sampling distribution $q(z)$.
Importance sampling
Recall: when computing p(z|D) using Bayes' rule, the evidence p(D) is the integral we are approximating.
$$p(D) = \int p(D|z)p(z)dz$$
Idea:
- Introduce a new sampling distribution $q(z)$ that is concentrated on the important high density region of $p(z)$
- Rewrite the model evidence $p(D)$ as the expectation over sampling distribution $q(z)$.
- Q Why is that called the model evidence?
- Because in this case you integrate out model parameters $z$; in this case the conditioning on the model is implicit.
- Approximate the expectation by sampling from $q(z)$.
Rewriting as model evidence:
$$p(D) = \int p(D|z)p(z)dz$$ $$= \int p(D|z)p(z)\frac{q(z)}{q(z)}dz$$ $$= \int p(D|z)\frac{p(z)}{q(z)}q(z)dz$$ $$= \E_{z~q(z)}[p(D|z)\frac{p(z)}{q(z)}]$$
The expectation is taken over $w_k=\frac{p(D|z_k)p(z_k)}{q(z_k)}$, which is usually called the importance weight in this context, because it weighs probabilities from $p$ by their importance in $q$.
$$p(D) \approx \frac{1}{K} \sum_{k=1}^K w_k$$
with $z_k ~ q(z)$.
We divide by $q(z_k)$ in order to compensate for the fact that you are sampling from an arbitrary distribution $q(z)$ instead of the posterior distribution $(p(z|D)$).
From importance sampling to ELBO
In practice, you usually take the log because this solves many practical issues:
$$log P(D)= log( \E_{z~q(z)}[p(D|z)\frac{p(z)}{q(z)}])$$
But this does not really help much yet because in order to evaluate the log, we still need to approximate the evidence P(D) first.
Instead, we want to push the log within the expectation. We can do this using the Jensen inequality for convex and concave functions.
Since the log is a concave function, we have
$$log( \E_{z~q(z)}[p(D|z)\frac{p(z)}{q(z)}]) \leq \E_{z~q(z)}[log( p(D|z)\frac{p(z)}{q(z)})]$$
Now we can simplify the expression within the expectation greatly!
The term within the expectation are the sampling weights, so we have
$$\E_{z~q(z)}[log( p(D|z)\frac{p(z)}{q(z)})] \approx \frac{1}{K}\sum_k^K log w_k$$
This is the ELBO!
You can just take the exponential of this for the lower bound on the evidence.
Insight: the variance of an importance sampler depends on how close the sampling distribution $q(z)$ is to the real posterior $p(z|D)$. This also implies that if we use the real posterior as sampling distribution $q(z)$, then the sampling weights in ELBO are equal to the actual marginal likelihood. Likewise, ELBO is then equal to the log marginal likelihood.
This means that when we have a good sampling distribution we can approximate the true marginal likelihood!
The question then is: what is a good sampling distribution $q(z)$. The previous result shows that the goal is to find a $q(z)$ that is close to the real posterior.
ELBO and KL-divergence
The question then is: what is a good sampling distribution $q(z)$. The previous result shows that the goal is to find a $q(z)$ that is close to the real posterior.
A statistical divergence is a measure between two probability distributions. This is not symmetric and thus not a real distance. But it's behavior is similar: positive and only zero is distributions are identical.
Main point: The KL-divergence between a sampling distribution and the posterior distribution is exactly the difference between the ELBO and the true marginal likelihood!
$$log P(D) = \E_{z~q(z)}[log( p(D|z)\frac{p(z)}{q(z)})] + D_{KL}( q(z), p(z|D))$$
NOTE: when we see a KL-divergence term, we want $q(z)$ to be the left argument, because this is the distribution we sample from. If it is not, you can switch the arguments and take the negative expectation:
$$D_{KL}(q(z), p(z)) = E_{q~q(z)}[ log \frac{q(z)}{p(z)}] = $$ $$ - E_{q~q(z)}[ log \frac{p(z)}{q(z)}] $$
We want to minimize the difference between ELBO and the marginal likelihood, so we can achieve this by minimizing the KL-divergence of the sampling distribution with the posterior distribution!
To prove this result:
- This is as simple as writing out the KL-divergence between $q(z)$ and $p(z|D)$
- Mostly making use of $log(x/y)=log(x)-log(y)$
Of course... we don't actually have access to the posterior, which we use in the KL-divergence. But it turns out that we do not need to know the marginal likelihood when computing the gradient over the KL-divergence.
Decomposing ELBO
We found the following main insight:
$$log P(D) = \E_{z~q(z)}[log( p(D|z)\frac{p(z)}{q(z)})] + D_{KL}( q(z), p(z|D))$$
We can split the ELBO further into two terms.
$$ \E_{z~q_{\theta}(z)}[ log \frac{p(z,D)}{q_(\theta)(z)}] = $$ $$\E_{z~q_{\theta}(z)}[ log p(D|z) - \E_{z~q_{\theta}(\frac{p(z))}{q_{\theta}(z)}] = $$ $$\E_{z~q_{\theta}(z)}[ log p(D|z) - D_{KL}(q_(\theta)(z), p(z)]$$
- The first term is the average log likelihood under the sampling distribution.
- Probabilistic generalization of standard maximum likelihood losses
- Minimizing this terms concentrates the sampler's density around the ML solution
- Using this term alone would lead to typical MLE behavior, i.e. a severe underestimation of uncertainty in the posterior distribution.
- The second term is the KL-divergence between prior $p(z)$ and variational sampler $q_0(z)$
- Regularization: This term forces the MLE estimate to not deviate too much from the prior distribution
- Can be further decomposed:
- E[log(p(z))] pushes towards point with highest prior density
- E[-log(q(z))] is an entropy term: we are also maximizing the entropy which means to increase uncertainty in the sampling distribution and to avoid the sampler collapsing on a single point (a "repulsion force").
Then the whole ELBO, fully decomposed, becomes:
$$\E_{z~q_{\theta}(z)}[ log p(D|z) - D_{KL}(q_(\theta)(z), p(z)] = $$ $$\E_{z~q_{\theta}(z)}[ log p(D|z) - ( \E_{z~q_{\theta}(z)}[ \frac{ q_{\theta}(z)}{p(z)} ]) = $$ $$\E_{z~q_{\theta}(z)}[ log p(D|z) - ( \E_{z~q_{\theta}(z)}[ q_{\theta}(z) - p(z) ]) = $$ $$\E_{z~q_{\theta}(z)}[ log p(D|z) + p(z) ] - \E_{z~q_{\theta}(z)}[ q_{\theta}(z) = $$
So to code this up, we essentially have a component 1) with the log likelihood and 2) a component that expresses the entropy q of the variational distribution.
N.B. before I messed this formula up because I messed up the KL-divergence.