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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.