Can someone explain Gibbs sampling in very simple words? [duplicate]

Question

I'm doing some reading on topic modeling (with Latent Dirichlet Allocation) which makes use of Gibbs sampling. As a newbie in statistics―well, I know things like binomials, multinomials, priors, etc.―,I find it difficult to grasp how Gibbs sampling works. Can someone please explain it in simple English and/or using simple examples? (If you are not familiar with topic modeling, any examples will do.)

Answer 1

You are a dungeonmaster hosting Dungeons & Dragons and a player casts 'Spell of Eldritch Chaotic Weather (SECW). You've never heard of this spell before, but it turns out it is quite involved. The player hands you a dense book and says, 'the effect of this spell is that one of the events in this book occurs.' The book contains a whopping 1000 different effects, and what's more, the events have different 'relative probabilities.' The book tells you that the most likely event is 'fireball'; all the probabilities of the other events are described relative to the probability of 'fireball'; for example: on page 155, it says that 'duck storm' is half as likely as 'fireball.'

How are you, the Dungeon Master, to sample a random event from this book? Here's how you can do it:

The accept-reject algorithm:

1) Roll a d1000 to decide a 'candidate' event.

2) Suppose the candidate event is 44% as likely as the most likely event, 'fireball'. Then accept the candidate with probability 44%. (Roll a d100, and accept if the roll is 44 or lower. Otherwise, go back to step 1 until you accept an event.)

3) The accepted event is your random sample.

The accept-reject algorithm is guaranteed to sample from the distribution with the specified relative probabilities.

After much dice rolling you finally end up accepting a candidate: 'summon frog'. You breathe a sigh of relief as you now you can get back to the (routine in comparison) business of handling the battle between the troll-orcs and dragon-elves.

However, not to be outdone, another player decides to cast 'Level. 2 arcane cyber-effect storm.' For this spell, two different random effects occur: a randomly generated attack, and a randomly generated character buff. The manual for this spell is so huge that it can only fit on a CD. The player boots you up and shows you a page. Your jaw drops: the entry for each attack is about as large a the manual for the previous spell, because it lists a relative probability for each possible accompanying buff

'Cupric Blade'

The most likely buff accompanying this attack is 'Hotelling aura'

'Jackal Vision' is 33% as likely to accompany this attack as 'Hotelling aura'

'Toaster Ears' is 20% as likely to accompany this attack as 'Hotelling aura'

...

Similarly, the probability of a particular attack spell occurring depends on the probability of the buff occurring.

It would be justified to wonder if a proper probability distribution can even be defined given this information. Well, it turns out that if there is one, it is uniquely specified by the conditional probabilities given in the manual. But how to sample from it?

Luckily for you, the CD comes with an automated Gibbs' sampler, because you would have to spend an eternity doing the following by hand.

Gibbs' sampler algorithm

1) Choose an attack spell randomly

2) Use the accept-reject algorithm to choose the buff conditional on the attack

3) Forget the attack spell you chose in step 1. Choose a new attack spell using the accept-reject algorithm conditional on the buff in step 2

4) Go to step 2, repeat forever (though usually 10000 iterations will be enough)

5) Whatever your algorithm has at the last iteration, is your sample.

You see, in general, MCMC samplers are only asymptotically guaranteed to generate samples from a distribution with the specified conditional probabilities. But in many cases, MCMC samplers are the only practical solution available.

Answer 2

I find this document GIBBS SAMPLING FOR THE UNINITIATED by Resnik & Hardisty very useful for non-statistics background folks. It explains why & how to use Gibbs sampling, and has examples demonstrating the algo.

Seems I cannot comment yet.

Gibbs sampling is not a self-contained concept. It requires some prerequisite knowledge. Below is the knowledge chain i summarized from my own study, as for your reference (My major was applied physics):

1. Monte Carlo (high level understanding)
2. Markov model (high level)
3. Bayes theorem
4. Gibbs sampling

The document I named here is roughly following the chain. If the link is broken, google the document name. You will find it.

Some thoughts: I don't think Gibbs sampling can be understood solely by some abstracts. There is no shortcut for it. You need to understand the math behind it. And since it's more like a "technique", my criterion of "understanding it" is "you can edit its code and understand what you're doing (not necessarily from scratch)". For those who think they have understood it by looking at some quick notes, they probably just understand what is "Markov Chain Monte Carlo" in a high level and think they have got it all (I made this illusion myself).

Answer 3

From wikipedia: "The goal of Gibbs Sampling here is to approximate the distribution of $P(\mathbf{Z}|\mathbf{W};\alpha,\beta)$" Notation can be found on the wiki site or from the original paper here.

One "scan" of Gibbs sampling targeting the above distribution will give you draws from the following probability distributions: $P(\mathbf{Z}_{(1,1)}|\mathbf{Z}_{-(1,1)}\mathbf{W};\alpha,\beta)$, $P(\mathbf{Z}_{(1,2)}|\mathbf{Z}_{-(1,2)}\mathbf{W};\alpha,\beta)$, $P(\mathbf{Z}_{(1,3)}|\mathbf{Z}_{-(1,3)}\mathbf{W};\alpha,\beta),\ldots, P(\mathbf{Z}_{(N,K)}|\mathbf{Z}_{-(N,K)}\mathbf{W};\alpha,\beta)$. You can either run through them in a sequence, or you can randomly chose which of these to sample form. But you keep doing scans over and over to get a lot of samples. Whatever option you choose, you get a sequence of $\mathbf{Z}$s.

$$ \mathbf{Z}^1, \mathbf{Z}^2, \mathbf{Z}^3\ldots $$

Each $\mathbf{Z}^i$ is an $N\times K$ matrix. Also, for two consecutive $\mathbf{Z}$ matrices, only one element will be different. That's because you're sampling from a distribution $P(\mathbf{Z}_{(m,n)}|\mathbf{Z}_{-(m,n)}\mathbf{W};\alpha,\beta)$ when you go from one sample to the next.

Why would you want this? Don't we want independent and identical draws from $P(\mathbf{Z}|\mathbf{W};\alpha,\beta)$? That way we could use the law of large numbers and central limit theorems to approximate expectations, and we would have some idea of the error. But I doubt these $\mathbf{Z}$ draws are independent. And are they even identical (are they even coming from the same distribution)?

Gibbs sampling can still give you a law of large numbers and a central limit theorem. $\mathbf{Z}^1, \mathbf{Z}^2, \mathbf{Z}^3\ldots $ is a Markov Chain with stationary/invariant distribution $P(\mathbf{Z}|\mathbf{W};\alpha,\beta)$. That means the marginal distribution of each draw is from the distribution you're targetting (so they're identical draws). However, they are not independent. In practice this means you run the chain for longer or you subsample the chain (only take every 100th sample, say). Everything can still "work," though.

For more information I would click the link underneath the question. There are some good references posted in that thread. This answer just attempts to give you the jist using the notation in common LDA references.