# Variational autoencoders: Computational vs. analytical intractability of KL divergence

I am currently trying to understand the ideas behind variational autoencoders. Specifically, I am a trying to understand why the KL divergence between the approximate posterior $$q(z | x)$$ and true posterior $$p(z | x)$$ is merely computationally intractable rather than analytically intractable.

In this blog post, the author states that the posterior is computationally intractable given that it relies on computing the following integral:

$$p(x) = \int p(x |z) \cdot p(z)\ dz,$$

which according to him "requires exponential time to compute." The author of this post states something similar, while adding that, given enough time, one could estimate $$p(x)$$ by Monte Carlo sampling

$$p(x) \approx\frac{1}{m} \sum_m^M p(x | z^{(m)}).$$

This I interpret as "If we had enough time, we could simply sample a huge number of $$z$$'s and look at the corresponding $$x$$'s, which would enable us to make a decent estimate of $$p(x)$$."

What puzzles me is how one would even begin to compute the above integral or to perform Monte Carlo sampling. It seems to me that one would need to know $$p(x | z)$$ in advance to be able to do this, and that the issue therefore has nothing to do with "exponential time" but with an intractable analytical problem. Am I missing something?

Your interpretation about MC sampling is correct. MC is powerful and unbiased but requires too much samples to get a better approximation compared to variational inference. Here $$p(x | z)$$ is the data likelihood or decoder receiving a stochastic input, which is a parameterized function in our case. If you know the prior and the parameters, you can model the likelihood and can construct MC samples from it. In VAE, likelihood is characterised as a neural net. Just pass your latent variable to the likelihood(decoder) network and get an estimate of your data.Otherwise, you need to know the form of your likelihood, of course .

One note, you cannot evaluate the integral for the evidence term as there can be infinitely many latent variables for an input. You can think it as VAE maps input to probabilistic spheres which has infinitely many points inside of it. If there were a exact pair of input and latent pairs, you could compute the integral, however you may have to deal with the numerical computation of it. Being fully Bayesian is not scalable unless you are dealing with certain distributions(conjugate priors) . VAE is a bridge between approximate Bayesian inference and deep learning.

If I couldn't explain it properly, let's discuss!

• "If you know the prior and the parameters, you can model the likelihood" - I assume by "parameters" you mean the parameters of the true decoder $p(x|z)$. If MC sampling requires access to these parameters (which makes sense to me), saying that we could approximate $p(x)$ by MC sampling sounds to me like we could approximate it by magic. We don't know the parameters of the decoder, so MC sampling won't work. My question is therefore: Why are people saying this is a computational problem ("it takes too long") when it looks to me like an analytical one ("we don't even know how to begin")?
– wstr
Commented May 15, 2020 at 9:28
• I was talking about VAE decoder. We cant do these with True decoder since you dont know it. With your logic, we couldnt have done ML at all. Of course there 's a true decoder underlying your problem. When we reconstruct, we try to learn a function. We do sampling with learned decoder in VAE. Commented May 15, 2020 at 10:36
• Thanks for taking the time to answer my questions. I really appreciate it! The way I understand it, you are suggesting that we do MC sampling using $p(x) \approx \frac{1}{M} \sum_{m=1}^M q(x|z^{(m)})$, where $q(x|z)$ denotes our approximation of the true decoder. But isn't it true that this only works if we already have a good approximation?
– wstr
Commented May 15, 2020 at 12:09
• As in Adam's blog, we want to use a parametrized distribution $p_{\theta}(x |z)$ (also please just dont use $q(x|z)$ for encoder as $q$ is used to denote variational approximation ) , with the hope that it would give a good solution. Inference/sampling actually turns into optimization. If you cannot get a good approximation with a neural network learned proposal), yes that's an another problem. Commented May 15, 2020 at 13:30