How Specifically do Sampling methods help in training Machine learning models? 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.
 A: 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.
