Lecture 2: Stochastic Variational Inference
With deep neural networks we are not working with conjugate priors, so exact Bayesian inference is out of the question.
(Monte Carlo) sampling methods are usually already inefficient, but especially in the case of heavily parameterized deep neural nets.
Instead, we focus on "gradient-based variational inference" in this course. This "reduces inference to a non-convex optimization problem that can be solved using standard deep learning methods."
Discretization, grid integration, the curse of dimensionality
You want to use Bayesian inference when you have latent variables.
The distinction between variable and unobservable is often problem-specific: given a particular problem something is unobservable, but it may be observable in another case.
Goal: get the full probability distribution over the latent.
Problem: we can't evaluate the integral in the denominator.
Grid integration: apply bins and sum density of bins.
$$\int p(D|z)p(z)dz \approx \sum_{n=1}^N p(D|z_n)p(z_n)\Delta z$$
We'll see that often a limited amount of bins contain all the data. Those that do are relevant, but some bins barely contain density and can be considered irrelevant.
But often we work in high-dimensional space. When we divide in bins, we'll have an exponential amount of bins ($N^D$ for N bins and dimensions D) and most bins are useless. It becomes very hard to locate the relevant bins in let's say 100-dimensional space.
If we get lucky, most density is located in an extremely small region of that high dimensional space and if we are even more lucky, we can actually find those. Usually, the posterior is spread out and we'll need many bins and computing the bins is impossible.
Importance sampling
The problem with the naive binning approach is that we need to find the hopefully small region in the latent variable space that has non-negligible probability density. That is, for tractable integration, we need to find the important region in the variable space.
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 \sim 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 \sim 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)$). See the above derivation for a mathematical justification.
Q: The lecture notes suggest that $w_k$ also contains the likelihood term, but intuitively I'd call $\frac{p(z_k)}{q(z_k)}$ the importance weight.
(Intermezzo: Sampling from that posterior would ensure that you sample latent values from the relevant areas of the density function! Of course, the whole point of computing $P(D)$ is to get to this posterior... so we don't have direct access to it. Without access to the (posterior) sampling distribution, the quality of our estimation of $P(D)$ depends on our ability to find a good sampling distribution. This is hard... especially in higher dimensions).
- Exercise 2.1: show expected value is actually the marginal likelihood.
- Exercise 2.2: Show that for number of samples K tending to infinity, the estimator follows an asymptotic normal distribution
- In order to prove this, we have to assume finite variance on the importance weights $w_k$ in the estimator defined above
- Apparently, in practice the variance is often infinite so the central limit theorem does not even kick in; and we do not get the nice situation that the variance scales down with samples K.
- Q: Why is the variance of the samples drawn with an importance samples often infinite?
Problem with importance sampling
"The problem with importance sampling is that the scale of the weights tend to differ by order of magnitudes so that only a few samples tend to dominate the average."
Even if we assume a Gaussian posterior distribution and then also take a Gaussian sampling distribution (i.e. we have an appropriate choice for the sampling distribution), even then can we show that the importance weights scale exponentially with the difference in mean between the mean of $p(z)$ and $q(z)$.
$$w_k = \frac{p(z_k)}{q(z_k)} \propto \exp{-z_k(\mu_p - \mu_q) / \sigma^2 }$$
Q: I do not understand this formulation of $w_k$ and why it is different from the previous definition (see the question above on the terminology of "importance" weights)
TODO: A? I think the importance weight is of the form $\frac{p(z)}{q(z)}$, more specifically $\frac{p(z|D)}{q(z)}$. In practice we don't have access to the posterior, so instead we compute the expectation of $\frac{p(D|z)p(z)}{q(z)}$ using importance sampling? But $p(z|D) \neq p(D|z)p(z)$. What am I missing here? I think that now 1) "importance weight" is taken as $\frac{p(z)}{q(z)}$ and 2) that we in this case "know"/assume that $p(z)$ is a Gaussian, i.e. can be expressed as the Gaussian posterior $p(z|D)$. If you subtract the exponential terms from each other, write out the square, then collect terms around ($\mu_p - \mu_q$), and then drop the constant contribution of the squared means, you get above expression. I however didn't have the minus, not sure if I made a mistake or the lecture notes did.
"The exponential function in these weights convert small differences in the values of $z_k$ into enormous differences in the weights. This implies that our importance sampling estimates have a disproportionate dependence on very few samples, leading to very high variance of the estimator." (my emphasis) That is, the distribution over $w_k$ will have a huge variance.
This exponential relation means that you also need an exponentially increasing amount of samples to compensate for this difference in means. I.e. any deviation of the chosen sampling distribution from the true latent distribution is "exponentially punished".
Your sampling distribution is good if it focuses on the very small probability density region where most of the density is located. In high dimensionality, most of your samples will evaluate to 0 and you'll get useful samples once in let's say 10 million years... So importance sampling is unbiased, but not very useful often.
In practice, we do not often have a good sampling distribution so importance sampling is one of the last things you'll try. Usually we therefore accept a biased estimator. Bias is not always bad; in this case it can help avoid exploding variance.
Evidence lower bound
From importance sampling to ELBO
ELBO is an approximator of the model evidence $P(D)$, which we were also approximating with importance sampling.
For importance sampling, we used:
$$P(D)= E_{z\sim q(z)}[p(D|z)\frac{p(z)}{q(z)}]$$
The problem was that a few samples dominate the importance weights because the fraction of probabilities is extremely unstable. For unlikely values z, q(z) vanishes to 0 so $\frac{p(z)}{q(z)}$ will explode.
We can solve that by taking the log over the expectation of the sampling distribution.
$$log P(D)= log( E_{z\sim q(z)}[p(D|z)\frac{p(z)}{q(z)}])$$
The log can be pushed inside the expectation using Jensen inequality.
The resulting estimator is called the evidence lower bound (ELBO):
$$log p(D) \approx \frac{1}{K} \sum_k^K log w_k$$
where we define $w_k$ same as for importance sampling.
See ELBO evidence lower bound.
Note that the ELBO is defined in log space, so if you want to get an actual estimate for the marginal likelihood you need to take the exponent of the log weights. When using the ELBO in gradient descent, you don't care about this step because the log is monotonic anyways.
Just having a lower bound is not very useful. E.g. if we have 0 as a lower bound, we have a trivial solution.
Goal: We want ELBO to approximate the true model evidence! In the ideal case, we'll use the real posterior as the model sampler then variance and bias go to zero. So our real goal is to push the sampler towards the posterior distribution.
ELBO is actually biased because it only offers a lower bound.
When you use the true posterior as the sampling distribution $q(z)$, you'll see the sampler reduces to the actual marginal likelihood and you'll end up with $log P(D) = log P(D)$. When we use the posterior as the sampling distribution, the ELBO is equal to the real log marginal likelihood. This means that when we have a good sampling distribution we can approximate the true marginal likelihood!
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.
So to prove KL-divergence is a proper divergence, we need to show that:
- Always positive
- Only 0 when prob. distributions are identical.
Use: $-log x >= 1 - x$
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!
Q: see eq. 20 in lecture notes; should it say "posterior" instead of "prior"?
$$log P(D) = E_{z\sim 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\sim q(z)}[ log \frac{q(z)}{p(z)}] = $$ $$- E_{q\sim 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!
- Exercise 2.4: 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\sim 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\sim q_{\theta}(z)} [ log \frac{p(z,D)}{q_{\theta}(z)} ] = $$ $$E_{z\sim q_{\theta}(z)}[ log\ p(D|z) - E_{z\sim q_{\theta}}(\frac{p(z))}{q_{\theta}(z)}] = $$ $$E_{z\sim 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\sim q_{\theta}(z)}[ log\ p(D|z) - D_{KL}(q_{\theta}(z), p(z)] = $$ $$E_{z\sim q_{\theta}(z)}[ log\ p(D|z) - ( E_{z\sim q_{\theta}(z)}[ \frac{ q_{\theta}(z)}{p(z)} ]) = $$ $$E_{z\sim q_{\theta}(z)}[ log\ p(D|z) - ( E_{z\sim q_{\theta}(z)}[ q_{\theta}(z) - p(z) ]) = $$ $$E_{z\sim q_{\theta}(z)}[ log\ p(D|z) + p(z) ] - E_{z\sim 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.
Variational inference
So now we have a loss function! We can do gradient descent on KL-divergence.
We start with a parameterized distribution and then try to estimate its parameters. So gradient descent is in distribution space (space of all possible distributions, i.e. their variational parameters) not variable space (i.e. latent z).
The gradient over the KL-divergence between sampling and posterior distribution is the gradient over the negative ELBO!
When we write out the gradient over $D_{KL}(q_\theta(z), p(z|D))$, then we'll see that the gradient does not depend on P(D), so that drops out. P(D) essentially only contributes a constant shift to the KL-divergence.
- Write down the KL-divergence between parameterized sampling distribution $q_{\theta}(z)$ and posterior $p(z|D)$
- Get the familiar form of the ELBO, i.e. flip the quotient so that now we have
$$ -E_{z \sim q_{\theta}(z)}[\frac{p(z|D)}{q_{\theta}(z)}]$$
- Write down the gradient over this expression
- Multiply both sides of the quotient with P(D) (so the enumerator will be P(z, D))
- Write P(D) out of the quotient until you end up with a gradient over P(D)
- N.B. equation 26 in the lecture notes should have - log P(D) instead
- You now end up with the gradient over the negative ELBO
There is a problem: the KL-divergence in our original formulation seems to assume that we know the true posterior.
Insight: the model evidence drops out when we do SGD on KL-divergence. This rarely happens in other problems and is a really nice property of KL-divergence! This means that the gradient over KL-divergence is the negative of the gradient over ELBO.
We can thus minimize the KL-divergence between the sampling distribution q(z) and the posterior p(z|D) by maximizing the variational log evidence lower bound i.e. the variational ELBO. This is called variational inference and the parameterized latent distribution $q_{\theta}(z)$ is called the variational distribution.
Because we usually minimize loss functions, we can e.g. use PyTorch to minimize the negative ELBO.
Recall, the fully decomposed ELBO looked like this:
$$E_{z\sim q_{\theta}(z)}[ log p(D|z) - E[log p(z)] + E[log q_{\theta}(z)])$$
Reparametrization trick
This is the most important part of the lecture. How can we do backpropagation over a sampling operation?
The problem is that we want to use gradient descent to find the best variational parameters, i.e. those parameters that lead to a variational distribution that approximate the true posterior.
The problem is that you compute the gradient with respect to the samples $z$ of the variational distribution, not the variational parameters. The main question thus is: How do you backpropagate from the samples to the parameters of the underlying distribution? You can't back propagate through a sampling operation because it is not a deterministic function.
Idea of reparameterization: rewrite the parameterized sampling operation w.r.t. a fixed distribution $q_0(z)$ and a parameterized differentiable function $f_{\theta}$ such that:
$$f_{\theta}(\epsilon) \sim q_{\theta}(z)$$ $$\epsilon \sim q_0(z)$$
So notice that you need to choose $f_{\theta}$ such that, while sampling from a fixed distribution $q_0$, you "reconstruct" the original variational distribution. The sampling distribution for $\epsilon$ has to be fixed. If $\epsilon$ is again dependent e.g. on $\mu$ in case of a Gaussian, then we have simply moved the problem and still have an unknown derivative.
In the case of the Gaussian, we can use a simple reparameterization formula that translates and scales. Example with Gaussian:
$$f_{\theta}(\epsilon) = \mu +_\sigma \epsilon \sim N(\mu,\sigma^2)$$
with
$$\epsilon \sim N(0,1)$$
Now, the sampling operation does not depend on $\theta$. Take a sample $x_n = \mu + \sigma \epsilon_n$ Then we have:
$$\frac{ \partial x_n}{ \partial \mu} = 1 + \sigma \frac{ \partial \epsilon_n}{ \partial \mu}$$
But now, we know that $\epsilon_n$ does not depend on $\mu$, so $\frac{ \partial \epsilon_n}{ \partial \mu}=0$ Similar reasoning for $\sigma$.
Why is this important?
When computing the gradient over $L_{ELBO}(\theta)$ we can now push the gradient inside the expectation.
Before we had the following gradient over the ELBO:
$$\nabla_{\theta} E_{ z \sim q_{\theta}(z)} log \frac{ p(z,D) }{ q_{\theta} z }$$
In this case, when you push the gradient inside the expectation you get incorrect results, because the joint term (or if you decompose, the likelihood term) does not depend on $\theta$, meaning you'll get a gradient of 0. Also, if you move the gradient inside the expectation, you ignore the sampling operation that does depend on $\theta$.
What we want is that the gradient pushes the variational distribution to the region of $z$ for which we have high likelihood $p(D|z)$ (of course, the ELBO also takes into account prior, entropy etc.).
But now that we have our differentiable parameterized (i.e. on $\theta$) function $f_{\theta}$, also the likelihood term depends on $\theta$ and we can push the gradient inside the expectation term:
$$\nabla_{\theta} E_{ z \sim q_{\theta}(z)} log \frac{ p(z,D) }{ q_{\theta} z } = $$
$$\nabla_{\theta} E_{ z \sim q_{0}(\epsilon)} log \frac{ p( f_{\theta}(\epsilon),D) }{ q_{\theta} f_{\theta}(\epsilon) } = $$
$$E_{ z \sim q_{0}(\epsilon)} \nabla_{\theta} log \frac{ p( f_{\theta}(\epsilon),D) }{ q_{\theta} f_{\theta}(\epsilon) }$$
We still cannot exactly compute the expectation, but we can now use an unbiased Monte Carlo sampler to approximate the expected ELBO gradient. But notice that instead of sampling from the variational distribution, we now sample from the fixed base distribution $q_0$!
The variance of the estimator depends on the number N of samples (as usual) but also on the choice of reparameterization.
Often reparameterization is already implemented in practice. In PyTorch we have .rsample() where r does not send for random but for "reparameterized".
Stochastic gradient descent
Stochastic gradient descent: because we use sampling we don't get exact gradients but estimates based on samples.
Note that we want to maximize ELBO (i.e. we want the lower bound to be as little an underestimation as possible) which means that in practice we minimize the negative ELBO.
Cf. the insight we had before:
The gradient over the KL-divergence between sampling and posterior distribution is the gradient over the negative ELBO!
So... in the lecture notes Luca often forgets the minus in front of the ELBO, which is confusing. Summary:
1) As a loss function we take the (Monte Carlo estimation of) the gradient of the negative ELBO (which is equivalent to minimizing KL-divergence between the variational sampling- and posterior distribution) 2) We plug this in to the stochastic gradient descent rule (you'll end up with a double negative sign) * $\theta_{n+1} = \theta_n - \eta_n G^{(M)}(\theta_n)$ * with G being the expected gradient of negative ELBO, with M samples and n indicating the iteration
For convergence there are some constraints on the learning rate, see eq. 46-48. A proof for these constraints is not given in the lecture notes, but in any case, the constraints are asymptotic so not very handy in practice for picking a suitable learning rate. So in practice, we just use Adam :-).
Loss function is not going to be convex so we can only guarantee local minima. So in variational inference we always should check if our final result makes sense.
REINFORCE gradient estimator
We cannot always use the reparameterization trick, depending on the sampler you use.
We cannot reparameterize discrete distributions such as the Bernouilli distribution. In this case we cannot find a continuous function that maps from a base distribution.
"REINFORCE" because it was discovered in reinforcement learning.
1) Write gradient over ELBO 2) Write the expectation term in ELBO as explicit integral 3) Push gradient inside the integral * Move derivative inside the integral: we can usually switch the gradient and integral using some weak constraints that work in 99% of the cases in a deep learning context: * differentiable in theta * continuous in z 4) Apply product rule for gradient, i.e. $(f*g)' = f'g + fg'$ 5) Split integrals and notice that one term now is the expectation over ELBO gradient 6) For the second term, apply trick (see below) 7) Collect terms; factor out $q_{\theta}(z)$, the gradient, and $g_{\theta}(z)$ 8) Because q(z) is factored out, you can now write this as one big expectation 9) For this expectation we can use a Monte Carlo sampler. Voila, we have the REINFORCE gradient estimator!
Trick:
$$q_{\theta}(z) = q_{\theta}(z) \nabla_{\theta} log\ q_{\theta}(z)$$
(The derivative of the log is 1 over q(z), which times q(z) gives 1; but the gradient over q(z) is introduced due to the chain rule when taking the derivative over the log).
Because you are not actually backpropagating through samples this has higher variance than when using the reparameterization trick and doesn't work great in practice. So this is more of a last resort if there are no other options.
Mean Field Approximation
One choice for the sampling distribution $q_{\theta}(z)$ is the mean-field approximation. When we assume the latent variables are statistically independent, we can factorize $q(z_k)$ as such:
$(z1,..,z_M) = \prod_m^M q_m(z_n)$
In practice, this often does not hold for the posterior, meaning that we already know that when minimizing the negative ELBO we can never properly approximate the true posterior.
Specifically, mean field approximation tends to severely underestimate the true uncertainty (variance) of the posterior.
Example
$P(y|x)= N(y|\mu=z, \sigma^2)$
Prior: $P(z) = N(z|0, v^2)$
In this case we have an analytical solution. But let's try variational inference.
Approximate posterior $q_{\theta}(z) = N(z| \mu_q, \sigma_q^2)$ with theta the mean and std.
Write loss as function of params; i.e. write ELBO: $L[ \mu_q, \sigma_q] = -E_q [ log( (N(y|z,\sigma^2))N(z|0,v^2))/ N(z|\mu_q, \sigma_q^2)]$
log over normal (good to know by heart): $-1/2\sigma^2 (y-z)^2 - 1/2 log 2\pi \sigma^2$ ; repeat for prior etc. Write out.
$L(\mu_q, \sigma_q) = E_q[ g_\theta(g) = E_0[g(\mu_q + \sigma_q \epsilon)]_{\epsilon \sim q_0 } \approx 1/N \sum_n g()$ (REVIEW; didn't write it out completely)
Where:
$q_0(\epsilon) = N(\epsilon|0,1)$
$f = \mu_q + \sigma*\epsilon$
Exercises
Exercise 2.1:
We have sampling estimator:
$$\Phi = \frac{1}{K} \sum_{k=1}^K w_k$$
with $z_k \sim q(z)$.
Show that the expectation of this estimator is the marginal likelihood.
$$E[\Phi] = E[ \frac{1}{K}\sum_{k=1}^{K} \frac{p(\theta|z_k)p(z_k)}{q(z_k)}]$$
With the amount of samples $K \rightarrow \infty$, we have:
$$=\int_z \frac{p(D|z)p(z)}{q(z)} q(z)$$ $$= \int_z p(D, z)$$ $$=P(D)$$
Exercise 2.4 Lecture notes
Show that $log\ P(D)$ can be written as the sum of ELBO and the KL-divergence $D_{KL}(q(z), p(z|D))$.
My solution:
- Start by writing out the KL divergence.
- You can swap the quotient: log(a/b)=-log(b/a).
- Write out the posterior p(z|D)
- Take P(D) out, write product as a sum of logs
- Expectation over sum is sum of expectation over individual terms
- We get log(P(D)) as a separate term because it does not depend on q(z) and thus the expectation over z disappears.
- Resolve minuses and QED.
Remarks on Notebook questions from the practical
Mistake in z with variance mentioned by Coco.
How to discretize integral
When evaluating integrals using grid approximation, e.g. to compute the marginal evidence, you can pick a range over z, usually you want at least 3xstd from the mean to both sides (further than that the probability density of a Gaussian is usually neglibible.)
if you can solve until 2.1 and 2.2 then it better to move on until week 3 to keep up.