How Specifically do Sampling methods help in training Machine learning models?

Question

I get the gist of sampling methods in probability. These algorithms were developed while building the Atom Bomb to estimate some distribution. The idea was just to try a simulation and note the results. And keep doing it for long enough, you will get a distribution over the outcomes, that is your probability.

Now, I am really having trouble understanding how do these methods work in machine learning.

Consider a topic model.

This is a probabilistic model like $P(x, z, y)$, where z is the hidden variable and there are distributions linking $x$ y and $z$.

The model is generative so the output is only on $x$ and $y$.

How does sampling method help here? How are the simulations run?

Could you explain how MCMC and Metropolis-Hastings are related to these? How do they actually work, what do they compute? How can you compute them without any optimization?

I really want to understand these methods and try some probabilistic programming but I am not getting the hang of it.

Answer 1

In general sampling methods can be used wherever you need to estimate some expected value.

How does sampling method help here? How are the simulations run?

Say $x$ is input, $y$ is target and $z$ the hidden variable, and we want to know $p(y|x)$ then $$p(y|x)=\int p(y,z|x) dz\approx\frac{1}{m}\sum_{i=1}^mp(y|z_i,x)$$ where $z_i$ are samples from $p(z|x)$.

Could you explain how MCMC and Metropolis-Hastings are related to these? How do they actually work, what do they compute?

In general generating samples from a high dimensional distribution is not easy, so MCMC is used to draw samples $z_i$ from $p(z|x)$.

What MCMC (and many other sampling methods) computes is roughly to simulate samples from $p(z|x)$ by making use of another distribution that we can easily get samples from (say a uniform distribution between 0 and 1).

How can you compute them without any optimization?

If we treat $z$ as a parameter, of course we can use optimization to solve $z$ $$z_{MAP}=\arg\max_zp(z|x)=\arg\max_zp(x|z)p(z) $$ then $p(y|x)\approx p(y|z_{MAP},x)$.

So the difference between optimization and sampling is, by optimization (MAP) we estimate $p(y|x)$ using the most likely sample, by sampling we estimate $p(y|x)$ using a collection of samples.