I have this confusion related to the tractability of an integral. In the attachment given below for equation 3 why is it intractable.
- Let's try to compute it. First, we can take advantage of the conditional independence of the $z_i$'s given the cluster centers, $$p(x_{1:n})=\int_{\mu_{1:K}}\prod_{k=1}^K p(\mu_k)\prod_{i=1}^n\sum_{z_i}p(z_i)p(x_i\,|\, z_i,\mu_{1:K}).\tag3$$ This leads to an integral that we can't (easily, anyway) compute.
- Alternatively, we can move the summation over the latent assignments to the outside, $$p(x_{1:n})=\int_{\mu_{1:K}}\prod_{k=1}^K p(\mu_k)\prod_{i=1}^n\sum_{z_i}p(z_i)p(x_i\,|\, z_i,\mu_{1:K}).\tag4$$ It turns out that we can compute each term in this summation. (This is an exercise.) However, there are $K^n$ terms. This is intractable when $n$ is reasonably large.
Further in equation 4 they have said that there are $K^n$ terms. I didn't get what makes it $K^n$ terms. Any suggestions guys?
The snippet is not very clear, but one might assume that each $z_i$ runs over $K$ values (this is not specified), and the terms referred to are the ones that arise after expanding $\prod_{i=1}^n\sum_{z_i}$ by distributivity into a sum of products, where each $z_i$ varies independently. Presumably only the terms obtained after such expansion can be computed directly.