# Latent variable model: why is the marginal probability of data under the model intractable?

I'm reading about Variational auto-encoders, and in section 1.8 they describe a latent variable model $$p_\theta(x,z)$$ where x are observed and z are hidden variables. They say that the marginal distribution over observed variables for a single datapoint is $$p_\theta(x)=\int p_\theta(x,z)dz$$. They proceed to say that this integral does not have an analytic solution or efficient estimator. Why is that? why can't we sample some values of z according to its prior and get a decent estimate of the distribution of x?

The apparent simplicity of latent variables marginalization disappears as soon as you consider that $$z$$ is not necessarily a scalar, but might be a set of (possibly correlated) high-dimensional vectors. In my examples, I will consider the case where $$z$$ takes discrete values, although these examples readily extend to the case where $$z$$ is a continuous variable.

Firstly, let's assume we have $$T$$ i.i.d. observations $$x = [x_1,\dots,x_T]$$, with corresponding latent variables $$z = [z_1,\dots,z_T]$$. We also assume that $$z_t$$ is a scalar which can take $$N$$ possible values in $$\{1,\dots,N\}$$. Then the marginal distribution for a single observation can be easily computed:

$$p_{\theta}(x_t) = \sum_{i=1}^N p_{\theta}(x_t,z_t=i)$$

Furthermore, if observations are i.i.d., then the probability distribution of the vector $$x$$ is simply

$$p_{\theta}(x) = \prod_{t=1}^T p_{\theta}(x_t)$$

which algorithmic complexity is simply going to scale with $$TN$$. Fairly ok.

Now, consider that each $$z_t$$ is not a scalar, but rather a $$M$$-dimensional vector $$z_t = [z_t^{(1)},\dots,z_t^{(M)}]$$, where each element $$z_t^{(\cdot)}$$ can also take $$N$$ possible values in $$\{1,\dots,N\}$$. Then

$$p_{\theta}(x_t) = \sum_{i=1}^N \sum_{j=1}^N \sum_{k=1}^N \cdots p_{\theta}(x_t,z_t^{(1)} = i, z_t^{(2)} = j, z_t^{(3)} = k, \dots)$$

This time, the algorithmic complexity is going to scale exponentially with $$M$$. Not ok.

This gets even worse if observations are correlated, e.g. if they are drawn from a Hidden Markov Chain where $$p_{\theta}(z) = p_{\theta}(z_1) \prod_{t=2}^T p_{\theta}(z_{t}|z_{t-1})$$. The likelihood $$p_{\theta}(x)$$ can be computed using the Baum-Welch algorithm, which complexity will scale with $$TN^{2M}$$. Not ok at all.

Since most problems in real life imply high-dimensional latent variables (consider, for instance the problem of Bayesian Model inference, where the vector $$\theta$$ may contain dozens of parameters), simplicity is the exception, and not the norm. Marginalizing out latent variables is far from being an easy problem in machine learning.

• thanks! but can't we estimate by sampling from z according to their prior? Commented Oct 2, 2022 at 6:58
• No, we would have the same issue : the number of samples you would need to estimate $p(z)$ increases with the dimension of $z$ (this is called the curse of dimensionality). Besides, there is no reason for your prior to be close to the true distribution of $z$. Commented Oct 2, 2022 at 9:11
• thanks again, so why are these two problems alleviated once we do the reparameterization trick? the number of samples needed is still large, and still there's no reason for the prior to be close to the true distribution, BUT now they claim that we can do a simple monte carlo estimation, by using a single noise sample at a time Commented Oct 9, 2022 at 9:39