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?
 A: 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!
