The Polya Urn Scheme
Yet another way to visualize the Dirichlet process and Chinese restaurant process is as a modified Polya urn scheme. Imagine that we start with an urn filled with black balls. Then we proceed as follows:
- Each time we need an observation, we draw a ball from the urn.
- If the ball is black, we generate a new (non-black) color uniformly, label a new ball this color, drop the new ball into the urn along with the ball we drew, and return the color we generated.
- Otherwise, label a new ball with the color of the ball we drew, drop the new ball into the urn along with the ball we drew, and return the color we observed.
The resulting distribution over colors is the same as the distribution over tables in the Chinese restaurant process. Furthermore, when we draw a black ball, if rather than generating a new color, we instead pick a random value from a base distribution and use that value to label the new ball, the resulting distribution over labels will be the same as the distribution over values in a Dirichlet process.
Read more about this topic: Dirichlet Process
Famous quotes containing the word scheme:
“Television programming for children need not be saccharine or insipid in order to give to violence its proper balance in the scheme of things.... But as an endless diet for the sake of excitement and sensation in stories whose plots are vehicles for killing and torture and little more, it is not healthy for young children. Unfamiliar as yet with the full story of human response, they are being misled when they are offered perversion before they have fully learned what is sound.”
—Dorothy H. Cohen (20th century)