Dr. Nonparametric Bayes
Or: How I Learned to Stop Worrying
and Love the Dirichlet Process
Kurt Miller
CS 294: Practical Machine Learning
November 19, 2009
Today we will discuss Nonparametric
Bayesian methods.
“Nonparametric Bayesian methods”?
What does that mean?
Kurt T. Miller Dr. Nonparametric Bayes 2
Today we will discuss Nonparametric
Bayesian methods.
“Nonparametric Bayesian methods”?
What does that mean?
Kurt T. Miller Dr. Nonparametric Bayes 2
Introduction
Nonparametric
Nonparametric: Does NOT mean there are no
parameters.
Kurt T. Miller Dr. Nonparametric Bayes 3
Introduction
Example: Classification
Build model
Predict using model
Data
Parametric Approach
Nonparametric Approach
⇒
⇒
⇒
46
++
++
++++
++
++
++
++
++
++
++
++
⇒
Kurt T. Miller Dr. Nonparametric Bayes 4
Introduction
Example: Regression
Build model
Predict using model
Data
Parametric Approach
Nonparametric Approach
⇒
⇒
⇒
Kurt T. Miller Dr. Nonparametric Bayes 5
Introduction
Example: Clustering
Build model
Data
Parametric Approach
Nonparametric Approach
⇒
⇒
⇒
Kurt T. Miller Dr. Nonparametric Bayes 6
Introduction
So now we know what nonparametric means,
but what does Bayesian mean?
Statistics: Bayesian Basics
The Bayesian approach treats statistical problems by
maintaining probability distributions over possible
parameter values.
That is, we treat the parameters themselves as random
variables having distributions:
1 We have some beliefs about our parameter values θ before
we see any data. These beliefs are encoded in the prior
distribution P(θ).
2 Treating the parameters θ as random variables, we can
write the likelihood of the data X as a conditional
probability: P(X |θ).
3 We would like to update our beliefs about θ based on the
data by obtaining P(θ|X ), the posterior distribution.
Solution: by Bayes’ theorem,
P(θ|X ) = P(X |θ)P(θ)
P(X )
where
P(X ) =
∫
P(X |θ)P(θ)dθ
(Slide from tutorial lecture)
Kurt T. Miller Dr. Nonparametric Bayes 7
Introduction
Why Be Bayesian?
You can take a course on this question.
One answer:
Infinite Exchangeability: ∀n p(x1, . . . , xn) = p(xσ(1), . . . , xσ(n))
De Finetti’s Theorem (1955): If (x1, x2, . . .) are infinitely
exchangeable, then ∀n
p(x1, . . . , xn) =
∫ ( n∏
i=1
p(xi|θ)
)
dP (θ)
for some random variable θ.
Kurt T. Miller Dr. Nonparametric Bayes 8
Introduction
Why Be Bayesian?
You can take a course on this question. One answer:
Infinite Exchangeability: ∀n p(x1, . . . , xn) = p(xσ(1), . . . , xσ(n))
De Finetti’s Theorem (1955): If (x1, x2, . . .) are infinitely
exchangeable, then ∀n
p(x1, . . . , xn) =
∫ ( n∏
i=1
p(xi|θ)
)
dP (θ)
for some random variable θ.
Kurt T. Miller Dr. Nonparametric Bayes 8
Introduction
Why Be Bayesian?
You can take a course on this question. One answer:
Infinite Exchangeability: ∀n p(x1, . . . , xn) = p(xσ(1), . . . , xσ(n))
De Finetti’s Theorem (1955): If (x1, x2, . . .) are infinitely
exchangeable, then ∀n
p(x1, . . . , xn) =
∫ ( n∏
i=1
p(xi|θ)
)
dP (θ)
for some random variable θ.
Kurt T. Miller Dr. Nonparametric Bayes 8
Introduction
Simple Example
Task: Toss a (potentially biased) coin N times. Compute θ, the
probability of heads.
Suppose we observe: {T, H, H, T}. What do we think θ is?
The
maximum likelihood estimate is θ = 1/2. Seems reasonable.
Now suppose we observe: {H, H, H, H}. What do we think θ is? The
maximum likelihood estimate is θ = 1. Seem reasonable?
Not really. Why?
Kurt T. Miller Dr. Nonparametric Bayes 9
Introduction
Simple Example
Task: Toss a (potentially biased) coin N times. Compute θ, the
probability of heads.
Suppose we observe: {T, H, H, T}. What do we think θ is? The
maximum likelihood estimate is θ = 1/2. Seems reasonable.
Now suppose we observe: {H, H, H, H}. What do we think θ is? The
maximum likelihood estimate is θ = 1. Seem reasonable?
Not really. Why?
Kurt T. Miller Dr. Nonparametric Bayes 9
Introduction
Simple Example
Task: Toss a (potentially biased) coin N times. Compute θ, the
probability of heads.
Suppose we observe: {T, H, H, T}. What do we think θ is? The
maximum likelihood estimate is θ = 1/2. Seems reasonable.
Now suppose we observe: {H, H, H, H}. What do we think θ is?
The
maximum likelihood estimate is θ = 1. Seem reasonable?
Not really. Why?
Kurt T. Miller Dr. Nonparametric Bayes 9
Introduction
Simple Example
Task: Toss a (potentially biased) coin N times. Compute θ, the
probability of heads.
Suppose we observe: {T, H, H, T}. What do we think θ is? The
maximum likelihood estimate is θ = 1/2. Seems reasonable.
Now suppose we observe: {H, H, H, H}. What do we think θ is? The
maximum likelihood estimate is θ = 1. Seem reasonable?
Not really. Why?
Kurt T. Miller Dr. Nonparametric Bayes 9
Introduction
Simple Example
Task: Toss a (potentially biased) coin N times. Compute θ, the
probability of heads.
Suppose we observe: {T, H, H, T}. What do we think θ is? The
maximum likelihood estimate is θ = 1/2. Seems reasonable.
Now suppose we observe: {H, H, H, H}. What do we think θ is? The
maximum likelihood estimate is θ = 1. Seem reasonable?
Not really. Why?
Kurt T. Miller Dr. Nonparametric Bayes 9
Introduction
Simple Example
When we observe {H, H, H, H}, why does θ = 1 seem unreasonable?
Prior knowledge! We believe coins generally have θ ≈ 1/2. How to
encode this? By using a Beta prior on θ.
Kurt T. Miller Dr. Nonparametric Bayes 10
Introduction
Simple Example
When we observe {H, H, H, H}, why does θ = 1 seem unreasonable?
Prior knowledge! We believe coins generally have θ ≈ 1/2. How to
encode this? By using a Beta prior on θ.
Kurt T. Miller Dr. Nonparametric Bayes 10
Introduction
Bayesian Approach to Estimating θ
Place a Beta(a, b) prior on θ. This prior has the form
p(θ) ∝ θa−1(1− θ)b−1.
What does this distribution look like?
0 1
0
1
2
3
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
Kurt T. Miller Dr. Nonparametric Bayes 11
Introduction
Bayesian Approach to Estimating θ
Place a Beta(a, b) prior on θ. This prior has the form
p(θ) ∝ θa−1(1− θ)b−1.
What does this distribution look like?
0 1
0
1
2
3
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
Kurt T. Miller Dr. Nonparametric Bayes 11
Introduction
Bayesian Approach to Estimating θ
After observing X, a sequence with n heads and m tails, the posterior on
θ is:
p(θ|X) ∝ p(X|θ)p(θ)
∝ θa+n−1(1− θ)b+m−1
∼ Beta(a+ n, b+m).
If a = b = 1 and we observe 5 heads and 2 tails, Beta(6, 3) looks like
0 1
0
1
2
3
Kurt T. Miller Dr. Nonparametric Bayes 12
Introduction
Bayesian Approach to Estimating θ
After observing X, a sequence with n heads and m tails, the posterior on
θ is:
p(θ|X) ∝ p(X|θ)p(θ)
∝ θa+n−1(1− θ)b+m−1
∼ Beta(a+ n, b+m).
If a = b = 1 and we observe 5 heads and 2 tails, Beta(6, 3) looks like
0 1
0
1
2
3
Kurt T. Miller Dr. Nonparametric Bayes 12
Nonparametric Bayesian Methods overview
Nonparametric Bayesian Methods
Now we know what nonparametric and Bayesian mean. What should we
expect from nonparametric Bayesian methods?
• Complexity of our model should be allowed to grow as we get more
data.
• Place a prior on an unbounded number of parameters.
Kurt T. Miller Dr. Nonparametric Bayes 13
Nonparametric Bayesian Methods overview
Nonparametric Bayesian Methods
Now we know what nonparametric and Bayesian mean. What should we
expect from nonparametric Bayesian methods?
• Complexity of our model should be allowed to grow as we get more
data.
• Place a prior on an unbounded number of parameters.
Kurt T. Miller Dr. Nonparametric Bayes 13
Nonparametric Bayesian Methods overview
Nonparametric Bayesian Methods
Now we know what nonparametric and Bayesian mean. What should we
expect from nonparametric Bayesian methods?
• Complexity of our model should be allowed to grow as we get more
data.
• Place a prior on an unbounded number of parameters.
Kurt T. Miller Dr. Nonparametric Bayes 13
Nonparametric Bayesian Methods overview
Nonparametric Bayesian Methods overview
• Dirichlet Process/Chinese Restaurant Process
Latent class models - often used in the clustering context
• Beta Process/Indian Buffet Process
Latent feature models
• Gaussian Process (No culinary metaphor - oh well)
Regression
Today we focus on the Dirichlet Process!
Kurt T. Miller Dr. Nonparametric Bayes 14
Nonparametric Bayesian Methods overview
Today’s topic: The Dirichlet Process
A nonparametric approach to clustering. It can be used in any
probabilistic model for clustering.
Before diving into the details, we first introduce several key ideas.
Kurt T. Miller Dr. Nonparametric Bayes 15
Nonparametric Bayesian Methods overview
Key ideas to be discussed today
• A parametric Bayesian approach to clustering
• Defining the model
• Markov Chain Monte Carlo (MCMC) inference
• A nonparametric approach to clustering
• Defining the model - The Dirichlet Process!
• MCMC inference
• Extensions
Kurt T. Miller Dr. Nonparametric Bayes 16
Nonparametric Bayesian Methods overview
Key ideas to be discussed today
• A parametric Bayesian approach to clustering
• Defining the model
• Markov Chain Monte Carlo (MCMC) inference
• A nonparametric approach to clustering
• Defining the model - The Dirichlet Process!
• MCMC inference
• Extensions
Kurt T. Miller Dr. Nonparametric Bayes 17
Preliminaries
A Bayesian Approach to Clustering
We must specify two things:
• The likelihood term (how data is affected by the parameters):
p(X|θ)
• The prior (the prior distirubution on the parameters):
p(θ)
We will slowly develop what these are in the Bayesian clustering context.
Kurt T. Miller Dr. Nonparametric Bayes 18
Preliminaries
Motivating example: Clustering
How many clusters?
Kurt T. Miller Dr. Nonparametric Bayes 19
Preliminaries
Motivating example: Clustering
How many clusters?
Kurt T. Miller Dr. Nonparametric Bayes 19
Preliminaries
Clustering – A Parametric Approach
Frequentist approach: Gaussian Mixture Models with K mixtures
Distribution over classes: pi = (pi1, . . . , piK)
Each cluster has a mean and covariance: φi = (µi,Σi)
Then
p(x|pi, φ) =
K∑
k=1
pikp(x|φk)
Use Expectation Maximization (EM) to maximize the likelihood of the
data with respect to (pi, φ).
Kurt T. Miller Dr. Nonparametric Bayes 20
Preliminaries
Clustering – A Parametric Approach
Frequentist approach: Gaussian Mixture Models with K mixtures
Alternate definition:
G =
K∑
k=1
pikδφk
where δφk is an atom at φk.
Then
θi ∼ G
xi ∼ p(x|θi)
G
θi
xi
N
Ω
Kurt T. Miller Dr. Nonparametric Bayes 21
Parametric Bayesian Clustering
Clustering – A Parametric Approach
Bayesian approach: Bayesian Gaussian Mixture Models with K mixtures
Distribution over classes: pi = (pi1, . . . , piK)
pi ∼ Dirichlet(α/K, . . . , α/K)
(We’ll review the Dirichlet Distribution in a several slides.)
Each cluster has a mean and covariance: φk = (µk,Σk)
(µk,Σk) ∼ Normal-Inverse-Wishart(ν)
We still have
p(x|pi, φ) =
K∑
k=1
pikp(x|φk)
Kurt T. Miller Dr. Nonparametric Bayes 22
Parametric Bayesian Clustering
Clustering – A Parametric Approach
Bayesian approach: Bayesian Gaussian Mixture Models with K mixtures
G is now a random measure.
φk ∼ G0
pi ∼ Dirichlet(α/K, . . . , α/K)
G =
K∑
i=1
pikδφk
θi ∼ G
xi ∼ p(x|θi)
G
θi
xi
N
Ω
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 23
Parametric Bayesian Clustering
The Dirichlet Distribution
We had
pi ∼ Dirichlet(α1, . . . , αK)
The Dirichlet density is defined as
p(pi|α) =
Γ
(∑K
k=1 αk
)
∏K
k=1 Γ(αk)
piα1−11 pi
α2−1
2 · · ·piαK−1K
where piK = 1−
∑K−1
k=1 pik.
The expectations of pi are
E(pii) =
αi∑K
i=1 αi
Kurt T. Miller Dr. Nonparametric Bayes 24
Parametric Bayesian Clustering
The Beta Distribution
A special case of the Dirichlet distribution is the Beta distribution for
when K = 2.
p(pi|α1, α2) = Γ (α1 + α2)Γ(α1)Γ(α2)pi
α1−1(1− pi)α2−1
0 1
0
1
2
3
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
α1=, α2=
Kurt T. Miller Dr. Nonparametric Bayes 25
Parametric Bayesian Clustering
The Dirichlet Distribution
In three dimensions:
p(pi|α1, α2, α3) = Γ (α1 + α2 + α3)Γ(α1)Γ(α2)Γ(α3)pi
α1−1
1 pi
α2−1
2 (1− pi1 − pi2)α3−1
α = (2, 2, 2) α = (5, 5, 5) α = (2, 2, 25)
Kurt T. Miller Dr. Nonparametric Bayes 26
Parametric Bayesian Clustering
Draws from the Dirichlet Distribution
α = (2, 2, 2) 1 2 30
1 2 3
0
1 2 3
0
α = (5, 5, 5) 1 2 30
1 2 3
0
1 2 3
0
α = (2, 2, 5) 1 2 30
1 2 3
0
1 2 3
0
Kurt T. Miller Dr. Nonparametric Bayes 27
Parametric Bayesian Clustering
Key Property of the Dirichlet Distribution
The Aggregation Property: If
(pi1, . . . , pii, pii+1, . . . , piK) ∼ Dir(α1, . . . , αi, αi+1, . . . , αK)
then
(pi1, . . . , pii + pii+1, . . . , piK) ∼ Dir(α1, . . . , αi + αi+1, . . . , αK)
This is also valid for any aggregation:(
pi1 + pi2,
∑
k=3K
pik
)
∼ Beta
(
α1 + α2,
K∑
k=3
αk
)
Kurt T. Miller Dr. Nonparametric Bayes 28
Parametric Bayesian Clustering
Key Property of the Dirichlet Distribution
The Aggregation Property: If
(pi1, . . . , pii, pii+1, . . . , piK) ∼ Dir(α1, . . . , αi, αi+1, . . . , αK)
then
(pi1, . . . , pii + pii+1, . . . , piK) ∼ Dir(α1, . . . , αi + αi+1, . . . , αK)
This is also valid for any aggregation:(
pi1 + pi2,
∑
k=3K
pik
)
∼ Beta
(
α1 + α2,
K∑
k=3
αk
)
Kurt T. Miller Dr. Nonparametric Bayes 28
Parametric Bayesian Clustering
Multinomial-Dirichlet Conjugacy
Let Z ∼ Multinomial(pi) and pi ∼ Dir(α).
Posterior:
p(pi|z) ∝ p(z|pi)p(pi)
= (piz11 · · ·pizKK )(piα1−11 · · ·piαK−1K )
= (piz1+α1−11 · · ·pizK+αK−1K )
which is Dir(α+ z).
Kurt T. Miller Dr. Nonparametric Bayes 29
Parametric Bayesian Clustering
Clustering – A Parametric Approach
Bayesian approach: Bayesian Gaussian Mixture Models with K mixtures
G is now a random measure.
φk ∼ G0
pi ∼ Dirichlet(α/K, . . . , α/K)
G =
K∑
i=1
pikδφk
θi ∼ G
xi ∼ p(x|θi)
G
θi
xi
N
Ω
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 30
Parametric Bayesian Clustering
Bayesian Mixture Models
We no longer want just the maximum likelihood parameters, we want the
full posterior:
p(pi, φ|X) ∝ p(X|pi, φ)p(pi, φ)
Unfortunately, this is not analytically tractable.
Two main approaches to approximate inference:
• Markov Chain Monte Carlo (MCMC) methods
• Variational approximations
Kurt T. Miller Dr. Nonparametric Bayes 31
Parametric Bayesian Clustering
Monte Carlo Methods
Suppose we wish to reason about p(θ|X), but we cannot compute this
distribution exactly. If instead, we can sample θ ∼ p(θ|X), what can we
do?
p(θ|X)
Samples from p(θ|X)
This is the idea behind Monte Carlo methods.
Kurt T. Miller Dr. Nonparametric Bayes 32
Parametric Bayesian Clustering
Markov Chain Monte Carlo (MCMC)
We do not have access to an oracle that will give use samples
θ ∼ p(θ|X). How do we get these samples?
Markov Chain Monte Carlo (MCMC) methods have been developed to
solve this problem.
We focus on Gibbs sampling, a special case of the Metropolis-Hastings
algorithm.
Kurt T. Miller Dr. Nonparametric Bayes 33
Parametric Bayesian Clustering
Gibbs sampling
An MCMC technique
Assume θ consists of several parameters θ = (θ1, . . . , θm). In the finite
mixture model, θ = (pi, µ1, . . . , µK ,Σ1, . . . ,ΣK).
Then do
• Initialize θ(0) = (θ(0)1 , . . . , θ
(0)
m ) at time step 0.
• For t = 1, 2, . . ., draw θ(t) given θ(t−1) in such a way that eventually
θ(t) are samples from p(θ|X).
Kurt T. Miller Dr. Nonparametric Bayes 34
Parametric Bayesian Clustering
Gibbs sampling
An MCMC technique
In Gibbs sampling, we only need to be able to sample
θ
(t)
i ∼ p(θi|θ(t)1 , . . . , θ(t)i−1, θ(t−1)i+1 , . . . , θ(t−1)m , X).
If we repeat this for any model we discuss today, theory tells us that
eventually we get samples θ(t) from p(θ|X).
Example: θ = (θ1, θ2) and p(θ) ∼ N (µ,Σ).
−3 −2 −1 0 1 2 3 4 5
−3
−2
−1
0
1
2
3
4
5
−3 −2 −1 0 1 2 3 4 5
−3
−2
−1
0
1
2
3
4
5
First 50 samples First 500 samples
Kurt T. Miller Dr. Nonparametric Bayes 35
Parametric Bayesian Clustering
Gibbs sampling
An MCMC technique
In Gibbs sampling, we only need to be able to sample
θ
(t)
i ∼ p(θi|θ(t)1 , . . . , θ(t)i−1, θ(t−1)i+1 , . . . , θ(t−1)m , X).
If we repeat this for any model we discuss today, theory tells us that
eventually we get samples θ(t) from p(θ|X).
Example: θ = (θ1, θ2) and p(θ) ∼ N (µ,Σ).
−3 −2 −1 0 1 2 3 4 5
−3
−2
−1
0
1
2
3
4
5
−3 −2 −1 0 1 2 3 4 5
−3
−2
−1
0
1
2
3
4
5
First 50 samples First 500 samples
Kurt T. Miller Dr. Nonparametric Bayes 35
Parametric Bayesian Clustering
Bayesian Mixture Models - MCMC inference
Introduce “membership” indicators zi where zi ∼ Multinomial(pi)
indicates which cluster the ith data point belongs to.
p(pi,Z, φ|X) ∝ p(X|Z, φ)p(Z|pi)p(pi, φ)
xi
N
α G0pi
zi
K
φk
Kurt T. Miller Dr. Nonparametric Bayes 36
Parametric Bayesian Clustering
Gibbs sampling for the Bayesian Mixture Model
Randomly initialize Z, pi, φ. Repeat until we have enough samples:
1. Sample each zi from
zi|Z−i, pi, φ,X ∝
K∑
k=1
pikp(xi|φk)11{zi=k}
2. Sample each pi from
pi|Z, φ,X ∼ Dir(n1 + α/K, . . . , nK + α/K)
where ni is the number of points assigned to cluster i.
3. Sample each φk from the NIW posterior based on Z and X.
Kurt T. Miller Dr. Nonparametric Bayes 37
Parametric Bayesian Clustering
MCMC in Action
!"#"$!%
&%
Inference in the Finite Mixture Model
As was done in the GMM, we will introduce labels zi where zi = k if data point
i belongs to the jth cluster. Gibbs sampling for the finite mixture then proceeds
as follows:
1. Holding pit−1, µt−1,Σt−1 fixed, sample each zti . zti is drawn from the dis-
tribution
zti ∼
1
Z
K∑
j=1
pit−1j N (xi;µt−1j ,Σt−1j )1zti=j
2. Now holding zt, µt−1,Σt−1 fixed, sample pi from
pit ∼ Dirichlet(n1 + α/K, n2 + α/K, . . . , nK + α/K)
where ni is the number of points assigned to the ith cluster and use the
fact that the Dirichlet distribution is conjugate to the multinomial.
3. Finally, holding zt and pit fixed, we resample µt and Σt from their pos-
terior distribution. Using the fact that the NIW is the conjugate prior
to the normal distribution, this is a simple draw from the posterior NIW
distribution.
4. Repeat until we have enough samples.
What does this look like in action?
Show Matlab demo
Bad Initialization Point
Iteration 25
Iteration 65
Improvements
•! The Gibbs sampler presented here is one of the
most basic samplers for this model. We can
improve the sampler by integrating out some
of the parameters. This is called a collapsed
sampler. See the next slide.
•! Other methods for doing inference introduce
Metropolis-Hastings steps in the sampler or do
variational inference. We will not present
these here.
Collapsed Gibbs Sampler
Here, we will show how to marginalize out pi. Similar techniques can be used
for (µ,Σ).
We placed a Dir(α/K, . . . ,α/K) prior on pi. Suppose we integrate pi out of all
equations. Step 2 disappears and step 3 is left unchanged. In step 1, using
Bayes’ rule, we are sampling zti from
p(zti |zt−1−i , X, µt−1,Σt−1,α) ∝ p(zti |zt−1−i ,α)p(xi|zti , µt−1i ,Σt−1i ).
p(xi|zi, µt−1i ,Σt−1)i is the same likelihood term as before.
p(zti |zt−1−i ,α) is the expectation of our posterior Dirichlet distribution. If cluster
j has nj data points assigned to it (not including point i), then this is
p(zti |zt−1−i ,α) =
nj + α/K
n− 1− α
Collapsed Gibbs Sampler
The collapsed Gibbs sampler for µ,Σ, z is now:
1. Holding µt−1,Σt−1 fixed, sample each zti . zti is drawn from the distribution
zti ∼
1
Z
K∑
j=1
nj + α/K
n− 1 + αN (xi;µ
t−1
j ,Σ
t−1
j )1zti=j
2. Holding zt fixed, we resample µt and Σt from their posterior distribution.
This is a simple draw from the posterior NIW distribution.
3. Repeat.
Note about the likelihood term
For easy visualization purposes, we used a
normal mixture model here. However, the
likelihood term can be chosen to fit your
particular application. The same ideas
presented here apply for any mixture model.
[Matlab demo]
Kurt T. Miller Dr. Nonparametric Bayes 38
Parametric Bayesian Clustering
Collapsed Gibbs Sampler
Idea for an improvement: we can marginalize out some variables due to
conjugacy, so do not need to sample it. This is called a collapsed
sampler. Here marginalize out pi.
Randomly initialize Z, φ. Repeat:
1. Sample each zi from
zi|Z−i, φ,X ∝
K∑
k=1
(nk + α/K)p(xi|φk)11{zi=k}
2. Sample each φk from the NIW posterior based on Z and X.
Kurt T. Miller Dr. Nonparametric Bayes 39
Parametric Bayesian Clustering
Note about the likelihood term
For easy visualization, we used a Gaussian mixture model.
You should use the appropriate likelihood model for your application!
Kurt T. Miller Dr. Nonparametric Bayes 40
Parametric Bayesian Clustering
Summary: Parametric Bayesian clustering
• First specify the likelihood - application specific.
• Next specify a prior on all parameters.
• Exact posterior inference is intractable. Can use a Gibbs sampler for
approximate inference.
Kurt T. Miller Dr. Nonparametric Bayes 41
5 minute break
Kurt T. Miller Dr. Nonparametric Bayes 42
Parametric Bayesian Clustering
How to Choose K?
Generic model selection: cross-validation, AIC, BIC, MDL, etc.
Can place of parametric prior on K.
What if we just let K →∞ in our parametric model?
Kurt T. Miller Dr. Nonparametric Bayes 43
Parametric Bayesian Clustering
How to Choose K?
Generic model selection: cross-validation, AIC, BIC, MDL, etc.
Can place of parametric prior on K.
What if we just let K →∞ in our parametric model?
Kurt T. Miller Dr. Nonparametric Bayes 43
Parametric Bayesian Clustering
Thought Experiment
Let K →∞.
φk ∼ G0
pi ∼ Dirichlet(α/K, . . . , α/K)
G =
K∑
i=1
pikδφk
θi ∼ G
xi ∼ p(x|θi)
Kurt T. Miller Dr. Nonparametric Bayes 44
Parametric Bayesian Clustering
Thought Experiment: Collapsed Gibbs Sampler
Randomly initialize Z, φ. Repeat:
1. Sample each zi from
zi|Z−i, φ,X ∝
K∑
k=1
(nk + α/K)p(xi|φk)11{zi=k}
→
K∑
k=1
nkp(xi|φk)11{zi=k}
Note that nk = 0 for empty clusters.
2. Sample each φk based on Z and X.
Kurt T. Miller Dr. Nonparametric Bayes 45
Parametric Bayesian Clustering
Thought Experiment: Collapsed Gibbs Sampler
What about empty clusters? Lump all empty clusters together. Let K+
be the number of occupied clusters. Then the posterior probability of
sitting at any empty cluster is:
zi|Z−i, φ,X ∝ α/K × (K −K+)f(xi|G0)
→ αf(xi|G0)
for f(xi|G0) =
∫
p(x|φ)dG0(φ).
Kurt T. Miller Dr. Nonparametric Bayes 46
Parametric Bayesian Clustering
Key ideas to be discussed today
• A parametric Bayesian approach to clustering
• Defining the model
• Markov Chain Monte Carlo (MCMC) inference
• A nonparametric approach to clustering
• Defining the model - The Dirichlet Process!
• MCMC inference
• Extensions
Kurt T. Miller Dr. Nonparametric Bayes 47
The Dirichlet Process Model
A Nonparametric Bayesian Approach to Clustering
We must again specify two things:
• The likelihood term (how data is affected by the parameters):
p(X|θ)
Identical to the parametric case.
• The prior (the prior distirubution on the parameters):
p(θ)
The Dirichlet Process!
Exact posterior inference is still intractable. But we have already derived
the Gibbs update equations!
Kurt T. Miller Dr. Nonparametric Bayes 48
The Dirichlet Process Model
What is the Dirichlet Process?
Image from tab/nsb0600 443
Kurt T. Miller Dr. Nonparametric Bayes 49
The Dirichlet Process Model
What is the Dirichlet Process?
(G(A1), . . . , G(An))
∼ Dir(α0G0(A1), . . . ,α0G0(An))
Kurt T. Miller Dr. Nonparametric Bayes 50
The Dirichlet Process Model
The Dirichlet Process
A flexible, nonparametric prior over an infinite number of clusters/classes
as well as the parameters for those classes.
Kurt T. Miller Dr. Nonparametric Bayes 51
The Dirichlet Process Model
Parameters for the Dirichlet Process
• α - The concentration parameter.
• G0 - The base measure. A prior distribution for the cluster specific
parameters.
The Dirichlet Process (DP) is a distribution over distributions. We write
G ∼ DP (α,G0)
to indicate G is a distribution drawn from the DP.
It will become clearer in a bit what α and G0 are.
Kurt T. Miller Dr. Nonparametric Bayes 52
The Dirichlet Process Model
The DP, CRP, and Stick-Breaking Process
G
θi
xi
N
Ω
α
G0G ∼ DP(α, G0)
Stick-Breaking Process
(just the weights)
The CRP describes the
partitions of θ when G
is marginalized out.
Kurt T. Miller Dr. Nonparametric Bayes 53
The Dirichlet Process Model
The Dirichlet Process
Definition: Let G0 be a probability measure on the measurable space
(Ω, B) and α ∈ R+.
The Dirichlet Process DP (α,G0) is the distribution on probability
measures G such that for any finite partition (A1, . . . , Am) of Ω,
(G(A1), . . . , G(Am)) ∼ Dir(αG0(A1), . . . , αG0(Am)).
A
A
A
A
A
1
2
3
4
5Ω
(Ferguson, ’73)
Kurt T. Miller Dr. Nonparametric Bayes 54
The Dirichlet Process Model
Mathematical Properties of the Dirichlet Process
Suppose we sample
• G ∼ DP (α,G0)
• θ1 ∼ G
What is the posterior distribution of G given θ1?
G|θ1 ∼ DP
(
α+ 1,
α
α+ 1
G0 +
1
α+ 1
δθ1
)
More generally
G|θ1, . . . , θn ∼ DP
(
α+ n,
α
α+ n
G0 +
1
α+ n
n∑
i=1
δθi
)
Kurt T. Miller Dr. Nonparametric Bayes 55
The Dirichlet Process Model
Mathematical Properties of the Dirichlet Process
Suppose we sample
• G ∼ DP (α,G0)
• θ1 ∼ G
What is the posterior distribution of G given θ1?
G|θ1 ∼ DP
(
α+ 1,
α
α+ 1
G0 +
1
α+ 1
δθ1
)
More generally
G|θ1, . . . , θn ∼ DP
(
α+ n,
α
α+ n
G0 +
1
α+ n
n∑
i=1
δθi
)
Kurt T. Miller Dr. Nonparametric Bayes 55
The Dirichlet Process Model
Mathematical Properties of the Dirichlet Process
With probability 1, a sample G ∼ DP (α,G0) is of the form
G =
∞∑
k=1
pikδφk
(Sethuraman, ’94)
Kurt T. Miller Dr. Nonparametric Bayes 56
The Dirichlet Process Model
The Dirichlet Process and Clustering
Draw G ∼ DP (α,G0) to get
G =
∞∑
k=1
pikδφk
Use this in a mixture model:
G
θi
xi
N
Ω
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 57
The Dirichlet Process Model
The Stick-Breaking Process
• Define an infinite sequence of Beta random variables:
βk ∼ Beta(1, α) k = 1, 2, . . .
• And then define an infinite sequence of mixing proportions as:
pi1 = β1
pik = βk
k−1∏
l=1
(1− βl) k = 2, 3, . . .
• This can be viewed as breaking off portions of a stick:
1 2 ...1β β (1−β )
• When pi are drawn this way, we can write pi ∼ GEM(α).
Kurt T. Miller Dr. Nonparametric Bayes 58
The Dirichlet Process Model
The Stick-Breaking Process
• We now have an explicit formula for each pik:
pik = βk
∏k−1
l=1 (1− βl)
• We can also easily see that ∑∞k=1 pik = 1 (wp1):
1−
K∑
k=1
pik = 1− β1 − β2(1− β1)− β3(1− β1)(1− β2)− · · ·
= (1− β1)(1− β2 − β3(1− β2)− · · · )
=
K∏
k=1
(1− βk)
→ 0 (wp1 as K →∞)
• So now G =∑∞k=1 pikδφk has a clean definition as a random
measure
Kurt T. Miller Dr. Nonparametric Bayes 59
The Dirichlet Process Model
The Stick-Breaking Process
G
θi
xi
N
Ω
α
G0
φk
pik
∞
∞
Kurt T. Miller Dr. Nonparametric Bayes 60
The Dirichlet Process Model
The Chinese Restaurant Process (CRP)
• A random process in which n customers sit down in a Chinese
restaurant with an infinite number of tables
• first customer sits at the first table
• mth subsequent customer sits at a table drawn from the following
distribution:
P (previously occupied table i|Fm−1) ∝ ni
P (the next unoccupied table|Fm−1) ∝ α
where ni is the number of customers currently at table i and where
Fm−1 denotes the state of the restaurant after m− 1 customers
have been seated
��
�� ��
��
��
��
��
��
��
��
��
Kurt T. Miller Dr. Nonparametric Bayes 61
The Dirichlet Process Model
The CRP and Clustering
• Data points are customers; tables are clusters
• the CRP defines a prior distribution on the partitioning of the data
and on the number of tables
• This prior can be completed with:
• a likelihood—., associate a parameterized probability distribution
with each table
• a prior for the parameters—the first customer to sit at table k
chooses the parameter vector for that table (φk) from the prior
φ2φ1 φ3 φ
��
�� ��
��
��
��
��
��
��
��
��
4
• So we now have a distribution—or can obtain one—for any quantity
that we might care about in the clustering setting
Kurt T. Miller Dr. Nonparametric Bayes 62
The Dirichlet Process Model
The CRP Prior, Gaussian Likelihood, Conjugate Prior
φk = (µk,Σk) ∼ N(a, b)⊗ IW (α, β)
xi ∼ N(φk) for a data point i sitting at table k
Kurt T. Miller Dr. Nonparametric Bayes 63
The Dirichlet Process Model
The CRP and the DP
OK, so we’ve seen how the CRP relates to clustering. How does it relate
to the DP?
Important fact: The CRP is exchangeable.
Remember De Finetti’s Theorem: If (x1, x2, . . .) are infinitely
exchangeable, then ∀n
p(x1, . . . , xn) =
∫ ( n∏
i=1
p(xi|G)
)
dP (G)
for some random variable G.
Kurt T. Miller Dr. Nonparametric Bayes 64
The Dirichlet Process Model
The CRP and the DP
OK, so we’ve seen how the CRP relates to clustering. How does it relate
to the DP?
Important fact: The CRP is exchangeable.
Remember De Finetti’s Theorem: If (x1, x2, . . .) are infinitely
exchangeable, then ∀n
p(x1, . . . , xn) =
∫ ( n∏
i=1
p(xi|G)
)
dP (G)
for some random variable G.
Kurt T. Miller Dr. Nonparametric Bayes 64
The Dirichlet Process Model
The CRP and the DP
The Dirichlet Process is the De Finetti mixing
distribution for the CRP.
That means, when we integrate out
G, we get the CRP.
p(θ1, . . . , θn) =
∫ n∏
i=1
p(θi|G)dP (G)
G
θi
xi
N
Ω
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 65
The Dirichlet Process Model
The CRP and the DP
The Dirichlet Process is the De Finetti mixing
distribution for the CRP.
That means, when we integrate out
G, we get the CRP.
p(θ1, . . . , θn) =
∫ n∏
i=1
p(θi|G)dP (G)
G
θi
xi
N
Ω
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 65
The Dirichlet Process Model
The CRP and the DP
The Dirichlet Process is the De Finetti mixing
distribution for the CRP.
In English, this means that if the DP is the prior on
G, then the CRP defines how points are assigned to
clusters when we integrate out G.
Kurt T. Miller Dr. Nonparametric Bayes 66
The Dirichlet Process Model
The DP, CRP, and Stick-Breaking Process Summary
G
θi
xi
N
Ω
α
G0G ∼ DP(α, G0)
Stick-Breaking Process
(just the weights)
The CRP describes the
partitions of θ when G
is marginalized out.
Kurt T. Miller Dr. Nonparametric Bayes 67
Inference for the Dirichlet Process
Inference for the DP - Gibbs sampler
We introduce the indicators zi and use the CRP representation.
Randomly initialize Z, φ. Repeat:
1. Sample each zi from
zi|Z−i, φ,X ∝
K∑
k=1
nkp(xi|φk)11{zi=k} + αf(xi|G0)11{zi=K+1}
2. Sample each φk based on Z and X only for occupied clusters.
This is the sampler we saw earlier, but now with some theoretical basis.
Kurt T. Miller Dr. Nonparametric Bayes 68
Inference for the Dirichlet Process
MCMC in Action for the DP
!"#"$!%
&$%
What does this look like in action?
Show Matlab demo
!! !" !# !$ % $ # " !
!&
%
&
'%
()*+,-./.))/.2-+32.-/
!!" !# !$ !% !& " & % $ #
!'
"
'
!"
()*+,)-./0!"
!! !" !# !$ % $ # "
!#
!$
%
$
#
"
!
&'()*'+,-.$%
What about the other views of the
Dirichlet Process?
Remember how in the finite case we had a pi and (µ,Σ) associated with each
cluster? When we let K → ∞, the expected value of each pii went to zero.
However, as we have seen, the data points still cluster into groups. Why?
It turns out that even though in probability each pii is getting arbitrarily small,
we will still sample some that are large. These pii can be drawn from a size-
biased distribution known as the stick breaking distribution.
1 2
...
1
! ! !""!##$
Slide courtesy of Michael Jordan Slide courtesy of Michael Jordan
Stick breaking continued
We now have an explicit formula for
Each of these corresponds to a cluster
where are drawn from their prior.
This infinite sample is a sample from the
Dirichlet Process.
pik = βk
k−1∏
l=1
(1− βl)
(µk,Σk)
A
A
A
A
A
1
2
3
4
5
!
The Dirichlet Process
Slide courtesy of Michael Jordan
This is the formal definition of the Dirichlet Process. It is not
important that you understand it. I only include it for completeness.
Summary of the Dirichlet Process
•! The Dirichlet Process is a nonparametric prior
that we can use in clustering that allows us to
simultaneously learn a the number of clusters,
which points are assigned to each cluster, and
the cluster parameters.
•! We presented a Gibbs sampler based on the
Chinese Restaurant Process that samples
clusters from this distribution.
[Matlab demo]
Kurt T. Miller Dr. Nonparametric Bayes 69
Inference for the Dirichlet Process
Improvements to the MCMC algorithm
• Collapse out the φk if conjugate model.
• Split-merge algorithms.
Kurt T. Miller Dr. Nonparametric Bayes 70
Inference for the Dirichlet Process
Summary: Nonparametric Bayesian clustering
• First specify the likelihood - application specific.
• Next specify a prior on all parameters - the Dirichlet Process!
• Exact posterior inference is intractable. Can use a Gibbs sampler for
approximate inference. This is based on the CRP representation.
Kurt T. Miller Dr. Nonparametric Bayes 71
Inference for the Dirichlet Process
Key ideas to be discussed today
• A parametric Bayesian approach to clustering
• Defining the model
• Markov Chain Monte Carlo (MCMC) inference
• A nonparametric approach to clustering
• Defining the model - The Dirichlet Process!
• MCMC inference
• Extensions
Kurt T. Miller Dr. Nonparametric Bayes 72
Hierarchical Dirichlet Process
Hierarchical Bayesian Models
Original Bayesian idea
View parameters as random variables - place a prior on them.
“Problem”?
Often the priors themselves need parameters.
Solution
Place a prior on these parameters!
Kurt T. Miller Dr. Nonparametric Bayes 73
Hierarchical Dirichlet Process
Hierarchical Bayesian Models
Original Bayesian idea
View parameters as random variables - place a prior on them.
“Problem”?
Often the priors themselves need parameters.
Solution
Place a prior on these parameters!
Kurt T. Miller Dr. Nonparametric Bayes 73
Hierarchical Dirichlet Process
Hierarchical Bayesian Models
Original Bayesian idea
View parameters as random variables - place a prior on them.
“Problem”?
Often the priors themselves need parameters.
Solution
Place a prior on these parameters!
Kurt T. Miller Dr. Nonparametric Bayes 73
Hierarchical Dirichlet Process
Multiple Learning Problems
Example: xi ∼ N (θi, σ2) in m different groups.
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · ·
How to estimate θi for each group?
Kurt T. Miller Dr. Nonparametric Bayes 74
Hierarchical Dirichlet Process
Multiple Learning Problems
Example: xi ∼ N (θi, σ2) in m different groups.
Treat θis as random variables sampled from a common prior
θi ∼ N (θ0, σ20)
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · ·
θ0
Kurt T. Miller Dr. Nonparametric Bayes 75
Hierarchical Dirichlet Process
Recall Plate Notation:
θ0
θi
xij
Ni
m
is equivalent to
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · ·
θ0
Kurt T. Miller Dr. Nonparametric Bayes 76
Hierarchical Dirichlet Process
Let’s Be Bold!
Independent estimation Hierarchical Bayesian
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · · ⇒
θ0
θi
xij
Ni
m
What do we do if we have DPs for multiple related datasets?
G1
θ1i
x1i
N1
α1
H1 H2 Hm
αmG2 Gm
θ2i θmi
xmix2i
N2 Nm
· · ·
α2
⇒
m
Ni
xij
θij
Gi
H
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 77
Hierarchical Dirichlet Process
Let’s Be Bold!
Independent estimation Hierarchical Bayesian
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · · ⇒
θ0
θi
xij
Ni
m
What do we do if we have DPs for multiple related datasets?
G1
θ1i
x1i
N1
α1
H1 H2 Hm
αmG2 Gm
θ2i θmi
xmix2i
N2 Nm
· · ·
α2
⇒
m
Ni
xij
θij
Gi
H
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 77
Hierarchical Dirichlet Process
Let’s Be Bold!
Independent estimation Hierarchical Bayesian
x1j
N1
θ2θ1
N2
x2j xmj
Nm
θm
· · · ⇒
θ0
θi
xij
Ni
m
What do we do if we have DPs for multiple related datasets?
G1
θ1i
x1i
N1
α1
H1 H2 Hm
αmG2 Gm
θ2i θmi
xmix2i
N2 Nm
· · ·
α2
⇒
m
Ni
xij
θij
Gi
H
α
G0
Kurt T. Miller Dr. Nonparametric Bayes 77
Hierarchical Dirichlet Process
Attempt 1
m
Ni
xij
θij
Gi
H
α
G0
What kind of distribution do we use for G0? H?
Suppose θij are mean parameters for a Gaussian where
Gi ∼ DP(α,G0)
and G0 is a Gaussian with unknown mean?
G0 = N (θ0, σ20)
This does NOT work! Why?
Kurt T. Miller Dr. Nonparametric Bayes 78
Hierarchical Dirichlet Process
Attempt 1
m
Ni
xij
θij
Gi
H
α
G0
What kind of distribution do we use for G0? H?
Suppose θij are mean parameters for a Gaussian where
Gi ∼ DP(α,G0)
and G0 is a Gaussian with unknown mean?
G0 = N (θ0, σ20)
This does NOT work! Why?
Kurt T. Miller Dr. Nonparametric Bayes 78
Hierarchical Dirichlet Process
Attempt 1
m
Ni
xij
θij
Gi
H
α
G0
The problem: If G0 is continuous, then with
probability ONE, Gi and Gj will share ZERO atoms.
⇒ This means NO clustering!
Gi
Gj
G0
Kurt T. Miller Dr. Nonparametric Bayes 79
Hierarchical Dirichlet Process
Attempt 2
m
Ni
xij
θij
Gi
H
α
G0
So G0 must be discrete. What discrete prior can we
use on G0?
How about a parametric prior?
Gee, if only we had a nonparametric prior on discrete
measures...
Kurt T. Miller Dr. Nonparametric Bayes 80
Hierarchical Dirichlet Process
Attempt 2
m
Ni
xij
θij
Gi
H
α
G0
So G0 must be discrete. What discrete prior can we
use on G0?
How about a parametric prior?
Gee, if only we had a nonparametric prior on discrete
measures...
Kurt T. Miller Dr. Nonparametric Bayes 80
Hierarchical Dirichlet Process
Attempt 2
m
Ni
xij
θij
Gi
H
α
G0
So G0 must be discrete. What discrete prior can we
use on G0?
How about a parametric prior?
Gee, if only we had a nonparametric prior on discrete
measures...
Kurt T. Miller Dr. Nonparametric Bayes 80
Hierarchical Dirichlet Process
The Hierarchical Dirichlet Process
Solution:
m
Ni
xij
θij
Gi
H
α
G0γ
G0 ∼ DP(γ,H)
Gi ∼ DP(α,G0)
θij |Gi ∼ Gi
xij |θij ∼ p(xij |θij)
(Teh, Jordan, Beal, Blei, 2004)
Kurt T. Miller Dr. Nonparametric Bayes 81
Hierarchical Dirichlet Process
G0 vs. Gi
Since
G0 ∼ DP(γ,H)
Gi ∼ DP(α,G0)
we know
G0 =
∞∑
k=1
pikδφk
Gi =
∞∑
k=1
piikδφk
What is the relationship between pik and piik?
Kurt T. Miller Dr. Nonparametric Bayes 82
Hierarchical Dirichlet Process
G0 vs. Gi
Since
G0 ∼ DP(γ,H)
Gi ∼ DP(α,G0)
we know
G0 =
∞∑
k=1
pikδφk
Gi =
∞∑
k=1
piikδφk
What is the relationship between pik and piik?
Kurt T. Miller Dr. Nonparametric Bayes 82
Hierarchical Dirichlet Process
Relationship between pik and pijk
Let (A1, . . . , Am) be a partition of Ω.
A
A
A
A
A
1
2
3
4
5Ω
By properties of the DP
(Gi(A1), . . . , Gi(Am)) ∼ Dir(αG0(A1), . . . , αG0(Am))
⇒
(∑
k∈K1
piik, . . . ,
∑
k∈Km
piik
)
∼ Dir
(
α
∑
k∈K1
pik, . . . , α
∑
k∈Km
pik
)
Kurt T. Miller Dr. Nonparametric Bayes 83
Hierarchical Dirichlet Process
Relationship between pik and pijk
Let (A1, . . . , Am) be a partition of Ω.
A
A
A
A
A
1
2
3
4
5Ω
By properties of the DP
(Gi(A1), . . . , Gi(Am)) ∼ Dir(αG0(A1), . . . , αG0(Am))
⇒
(∑
k∈K1
piik, . . . ,
∑
k∈Km
piik
)
∼ Dir
(
α
∑
k∈K1
pik, . . . , α
∑
k∈Km
pik
)
Kurt T. Miller Dr. Nonparametric Bayes 83
Hierarchical Dirichlet Process
Stick-Breaking Construction for the HDP
G0 ∼ DP(γ,H) pi ∼ GEM(γ)
Gi ∼ DP(α,G0) pii ∼ DP(α, pi)
θij |Gi ∼ Gi φk ∼ H
xij |θij ∼ p(xij |θij) zij ∼ pii
xij ∼ p(xij |φzij )
m
Ni
xij
θij
Gi
H
α
G0γ
φk
m
Ni
xij
α
γ
zij
pi
pij G0
∞
Kurt T. Miller Dr. Nonparametric Bayes 84
Hierarchical Dirichlet Process
Stick-Breaking Construction for the HDP
Remember:0@X
k∈K1
piik, . . . ,
X
k∈Km
piik
1A ∼ Dir
0@α X
k∈K1
pik, . . . , α
X
k∈Km
pik
1A
Explicit relationship between pi and pii:
βk ∼ Beta(1, γ)
pik = βk
k−1Y
j=1
(1− βj)
βik ∼ Beta
αpik, α
1−
kX
j=1
pij
!!
piik = βik
k−1Y
j=1
(1− βij)
Kurt T. Miller Dr. Nonparametric Bayes 85
Hierarchical Dirichlet Process
The Effect of α
pi ∼ GEM(γ), pii ∼ DP(α, pi)
pi: γ = 2 1 2 3 4 5 6 7 8 9 100
pii:
α = 1 1 2 3 4 5 6 7 8 9 100
1
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10
0
1
α = 5 1 2 3 4 5 6 7 8 9 100
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10
0
α = 20 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10
0
α = 100 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10
0
Kurt T. Miller Dr. Nonparametric Bayes 86
Hierarchical Dirichlet Process
The Hierarchical Dirichlet Process
For the DP, we had:
• Mathematical definition
• Stick-breaking construction
• Chinese restaurant process
G
θi
xi
N
Ω
α
G0G ∼ DP(α, G0)
Stick-Breaking Process
(just the weights)
The CRP describes the
partitions of θ when G
is marginalized out.
For the HDP, we have
• Mathematical definition
• Stick-breaking construction
• ?
Kurt T. Miller Dr. Nonparametric Bayes 87
Hierarchical Dirichlet Process
The Chinese Restaurant Franchise (CRF) - Step 1
First integrate out the Gi.
m
Ni
xij
θij
Gi
H
α
G0γ
⇒
m
Ni
xij
θij
H
α
G0γ
Kurt T. Miller Dr. Nonparametric Bayes 88
Hierarchical Dirichlet Process
The Chinese Restaurant Franchise (CRF) - Step 1
What is the generative process when we integrate out Gi?
1. Draw global G0 =
∑∞
k=1 pikδφk .
2. Each group acts like a separate
CRP.
m
Ni
xij
θij
H
α
G0γ
G0
. . .φ1
. . .
. . .
φ2
φ3
θ11
φ2 φ2
φ4φ1
φ1
φ1
θ12 θ13
θ14 θ15
θ16
θ26
θ21
θ22
θ23 θ24
θ25
θ31
θ32
θ33
θ34
θ35
φ1 φ2 φ3φ4
Kurt T. Miller Dr. Nonparametric Bayes 89
Hierarchical Dirichlet Process
The Chinese Restaurant Franchise (CRF)
First integrate out the Gi, then integrate out G0
m
Ni
xij
θij
Gi
H
α
G0γ
⇒
m
Ni
xij
θij
H
α
G0γ
⇒
m
Ni
xij
θij
H
α
γ
Kurt T. Miller Dr. Nonparametric Bayes 90
Hierarchical Dirichlet Process
Chinese Restaurant Franchise (CRF)
G0
. . .φ1
. . .
. . .
φ2
φ3
θ11
φ2 φ2
φ4φ1
φ1
φ1
θ12 θ13
θ14 θ15
θ16
θ26
θ21
θ22
θ23 θ24
θ25
θ31
θ32
θ33
θ34
θ35
φ1 φ2 φ3φ4
⇒
. . .φ1
. . .
. . .
φ2
φ3
θ11
φ2 φ2
φ4φ1
φ1
φ1
θ12 θ13
θ14 θ15
θ16
θ26
θ21
θ22
θ23 θ24
θ25
θ31
θ32
θ33
θ34
θ35
Kurt T. Miller Dr. Nonparametric Bayes 91
Hierarchical Dirichlet Process
The Hierarchical Dirichlet Process
For the DP, we had:
• Mathematical definition
• Stick-breaking construction
• Chinese restaurant process
G
θi
xi
N
Ω
α
G0G ∼ DP(α, G0)
Stick-Breaking Process
(just the weights)
The CRP describes the
partitions of θ when G
is marginalized out.
For the HDP, we have
• Mathematical definition
• Stick-breaking construction
• Chinese restaurant franchise
process
Kurt T. Miller Dr. Nonparametric Bayes 92
Hierarchical Dirichlet Process
Inference
Same classes of algorithms used for the DP:
• MCMC
• CRF representation
• Stick-breaking representation
• Variational
We will not go into these.
Kurt T. Miller Dr. Nonparametric Bayes 93
Hierarchical Dirichlet Process
Application of the HDP - Infinite Hidden Markov Model
Finite Hidden Markov Models (HMMs):
• m states s1, . . . , sm
• si has parameter φi with emission distribution
y ∼ p(y|φi)
• m×m transition matrix
s1 s2 · · · sm
s1 pi11 pi12 · · · pi1m
s2 pi21 pi22 · · · pi2m
...
...
...
. . .
...
sm pim1 pim2 · · · pimm
How do we let m→∞?
Kurt T. Miller Dr. Nonparametric Bayes 94
Hierarchical Dirichlet Process
Application of the HDP - Infinite Hidden Markov Model
How do we let m→∞?
Think a bit outside the traditional clustering context.
Let each state si corresponds to a group.
pi|γ ∼ GEM(γ)
pii|α, pi ∼ DP(α, pi)
φk|H ∼ H
xt|xt−1, (pii)∞i=1 ∼ pixt−1
yt|xt, (pii)∞i=1 ∼ p(yt|φxt)
Kurt T. Miller Dr. Nonparametric Bayes 95
Questions?
Great set of references for the Machine Learning community:
Includes both the “classics” as well as modern applications.
Kurt T. Miller Dr. Nonparametric Bayes 96
Introduction
Nonparametric Bayesian Methods overview
Preliminaries
Frequentist Approach
Parametric Bayesian Clustering
Dirichlet Distribution
Bayesian Inference
Model Selection
Thought Experiment
The Dirichlet Process Model
Mathematical definition of the DP
The Stick-Breaking Process
The CRP
Inference for the Dirichlet Process
Gibbs sampler
Hierarchical Dirichlet Process
Multiple Learning Problems
Bad Attempt
Mathematical Definition
Stick-Breaking Construction
The Chinese Restaurant Franchise
Applications
