Teh 2010 - Stick-Breaking Construction

Summary

Sethuraman’s construction writes $G={\sum }_{k\ge 1}{\pi }_k{\delta }_{{\theta }_k^{\ast }}$ with ${\pi }_k={\beta }_k{\prod }_{l<k}(1-{\beta }_l)$, ${\beta }_k\sim \text{Beta}(1,\alpha )$, ${\theta }_k^{\ast }\sim H$. It is the basis of truncated samplers and variational methods, and the target of the truncation check in practical DP mixtures.

Main Content

Stick-breaking representation (Sethuraman 1994; Teh Eq. 13)

$${\beta }_k\stackrel{iid}{\sim }\text{Beta}(1,\alpha ),{\theta }_k^{\ast }\stackrel{iid}{\sim }H,{\pi }_k={\beta }_k\prod _{l=1}^{k-1}(1-{\beta }_l),G=\sum _{k=1}^{\infty }{\pi }_k{\delta }_{{\theta }_k^{\ast }}.$$

Then $G\sim \text{DP}(\alpha ,H)$. The law of $\pi$ is $\text{GEM}(\alpha )$ (Griffiths-Engen-McCloskey).

Intuition: start with a unit stick, break at ${\beta }_1$, give the left piece to atom 1, then recursively break the remainder. The advantages over earlier existence proofs: it is direct, needs no regularity on $\Theta$ or $H$, and suggests novel inference.

Properties used in practice.

• $\mathbb{E}[{\pi }_k]=\frac{1}{1+\alpha }(\frac{\alpha }{1+\alpha }{)}^{k-1}$, geometric decay, so weights decrease exponentially. Small $\alpha$ puts most mass on few atoms; large $\alpha$ spreads mass.
• Truncation at $K$ sticks sets ${\beta }_K=1$; truncation error after $K$ sticks is ${\prod }_{l\le K}(1-{\beta }_l)$ with mean $(\alpha /(1+\alpha ){)}^K$ (leftover mass). A truncation is adequate when the leftover mass is negligible, which can be checked a posteriori.
• Ordering by size is only stochastic; atoms are labelled by index, which creates label switching in posteriors (Concept - Label Switching and Label-Invariant Summaries).

Examples

How many sticks are needed?

For $\alpha =2$ and a leftover-mass tolerance of $10^{-3}$: $(2/3{)}^K<10^{-3}\Rightarrow K>17.0$, so $K=18$ sticks. For $\alpha =10$: $(10/11{)}^K<10^{-3}\Rightarrow K>72.5$, so $K=73$.

import numpy as np
rng = np.random.default_rng(0)
def gem(alpha, K):
    b = rng.beta(1, alpha, K)
    return b * np.concatenate([[1], np.cumprod(1 - b)[:-1]])
w = gem(2.0, 50)
print(w.sum(), w[:3])          # ~1, then decreasing weights
print(np.ceil(np.log(1e-3) / np.log(2/3)))  # 17 -> use 18

PyMC-style sketch (untested, PyMC 5)

import pymc as pm, pytensor.tensor as pt
K = 20
with pm.Model() as m:
    alpha = pm.Gamma("alpha", 1.0, 1.0)
    w = pm.StickBreakingWeights("w", alpha=alpha, K=K - 1)   # length K, sums to 1
    mu = pm.Normal("mu", 0, 10, shape=K)
    sd = pm.HalfNormal("sd", 5, shape=K)
    pm.NormalMixture("y", w=w, mu=mu, sigma=sd, observed=y)
# diagnostics: leftover mass, label-invariant summaries (co-clustering), not component labels

Connections

DP mixtures and sampling: Teh 2010 - DP Mixture Models and Applications. The IBP has an analogous stick-breaking form with ${\pi }_k={\prod }_{l\le k}{\beta }_l$: Griffiths 2011 - Two-Parameter IBP, Stick-Breaking and Beta Process. Mean-field VI on the stick-breaking parameterisation: Mean-Field Family and Coordinate Ascent VI (CAVI).

See Also

Teh 2010 - Dirichlet Process - Overview