Griffiths 2011 - Two-Parameter IBP, Stick-Breaking and Beta Process

Summary

The one-parameter IBP couples sparsity and dimensionality through $\alpha$. The two-parameter IBP (Ghahramani et al. 2007) introduces $\beta$ to decouple them; the IBP also has a stick-breaking form (Teh et al. 2007) and a de Finetti measure, the beta process (Thibaux and Jordan 2007); and exchangeability can be relaxed (Markov and phylogenetic IBPs).

Main Content

Two-parameter IBP (7.1)

Finite model ${\pi }_k\mid \alpha ,\beta \sim \text{Beta}(\frac{\alpha \beta }{K},\beta )$. Sequentially: customer 1 samples $\text{Poisson}(\alpha )$ dishes; customer $i$ takes dish $k$ with probability $m_k/(\beta +i-1)$ and tries $\text{Poisson}\left(\frac{\alpha \beta }{\beta +i-1}\right)$ new dishes.

Expected features per object stays $\alpha$; $K_{+}\sim \text{Poisson}\left(\alpha {\sum }_{i=1}^N\frac{\beta }{\beta +i-1}\right)$. Small $\beta$: features shared by all objects (extreme: $K_{+}\approx \alpha$); large $\beta$: object-specific features (extreme: $K_{+}\to N\alpha$). For finite $\beta$ growth is $\alpha \beta \ln N$, preceded by linear growth when $N<\beta$. Fig. 10 shows draws with $\alpha =10$ and $\beta =0.2,1,5$.

Stick-breaking for the IBP (7.2)

Sort the feature probabilities ${\pi }_k$ from largest to smallest. Then the sorted sequence has the law of the cumulative products of $\text{Beta}(\alpha ,1)$ breaks of the DP stick (Teh, Gorur and Ghahramani 2007): ${\pi }_{(1)}={\nu }_1$, ${\pi }_{(k)}={\prod }_{l\le k}{\nu }_l$ with ${\nu }_l\sim \text{Beta}(\alpha ,1)$. This supports slice sampling and the variational algorithm of Doshi-Velez et al.

Beta process (7.3). de Finetti representation: the IBP law equals independent Bernoulli draws from a latent measure given by the beta process (Hjort 1990; Thibaux and Jordan 2007), just as the CRP arises from the DP. Consequences: natural two-parameter analogues, hierarchical IBPs for correlated feature use across data sets, and a power-law variant via stable processes (Teh and Gorur 2010).

Relaxing exchangeability (7.4). Column correlations: a secondary process on features (Doshi-Velez and Ghahramani 2009b). Row dependence in time: Markov IBP (Van Gael et al. 2009), each column follows a Markov chain with transition parameters given beta priors, enabling infinite factorial HMMs with slice sampling. Row dependence by a tree: phylogenetic IBP (Miller et al. 2008), original IBP recovered by a star tree.

Examples

Effect of $\beta$ on dimensionality

$\alpha =10$, $N=100$, $E[K_{+}]=\alpha {\sum }_{i=1}^N\frac{\beta }{\beta +i-1}$. $\beta =0.2$: $\approx 19.8$ (features widely shared); $\beta =1$: $10H_{100}\approx 51.9$; $\beta =5$: $\approx 157.2$ (more object-specific features). Average features per object remains 10 in all three cases.

Connections

The DP side of the stick-breaking story: Teh 2010 - Stick-Breaking Construction. Pitman-Yor discount as a different decoupling of cluster-count growth: De Blasi 2015 - Subclasses Pitman-Yor NGG and Finite-Species Priors. Variational inference background: Variational Inference - Overview.

See Also

Griffiths 2011 - The Indian Buffet Process - Overview