Source
Teh, Görür and Ghahramani (2007), Stick-breaking construction for the Indian buffet process, LIT-1627, read in full in NOTE-1210: §3.1 (the construction, (5)–(15)) and §3.2 (truncation, (19)–(20)).
What was actually shown
The construction (the paper’s). For the finite model’s K independent Beta(α/K, 1) prevalences, the largest has cdf μ^α, so it is Beta(α, 1); given the k largest, the next has cdf (μ/μ_(k))^{α(K − k)/K} → (μ/μ_(k))^α. So ν_(k) = μ_(k)/μ_(k−1) are i.i.d. Beta(α, 1) and μ_(k) = ∏{l≤k} ν(l). E[μ_(k)] = (α/(α + 1))
The truncation’s count (the record’s). An object holds feature k with probability μ_(k), independently given the sticks, so feature k is occupied among N objects with probability 1 − E[(1 − μ_(k))^N] = Σ_{j=1}^{N} (−1)^{j+1} C(N, j) E[μ_(k)^j], and E[μ_(k)^j] = (α/(α + j))^k. Summing over all k gives Σ_j (−1)^{j+1} C(N, j) α/j = αH_N, the IBP’s count (THEORY-1043); summing to K gives the truncation’s. At N = 12, α = 3:
| K | 8 | 16 | 24 | 32 | 50 | limit |
|---|---|---|---|---|---|---|
| truncated construction | 6.799 | 8.974 | 9.274 | 9.306 | 9.310 | 9.310 |
| finite model, K independent Beta(α/K, 1) (THEORY-999) | 6.83 | 8.38 | 9.310 |
Simulation of the truncated construction at K = 16 (200,000 draws) gives 8.969 ± 0.006. Each object holds Σ_{k≤16} (3/4)^k = 2.97 features on average there, against α = 3. The deficit at K = 16, 0.34, is the expected number of occupied features beyond the 16th stick; at least one such feature is occupied in 24% of draws, although P(K+ > 16) under Poisson(9.31) is only 0.015.
What this does not say
- Not a bound on the error of the matrix. It gives the expected count only; the paper points to the Dirichlet process’s truncation bound and computes nothing.
- Not about the posterior. A truncation’s effect on inference depends on the data.
- Not that the two approximations are interchangeable. At the same K the finite model and the truncated construction are different priors; CASE-165’s model (T23) is the finite one.
Connections
- CASE-165, item 1. Confirms the case’s “8.97, simulated” and its “close to it”, and qualifies its reason: what the truncation loses is features beyond the 16th stick, occupied in 24% of draws, not the 1.5% of draws in which more than 16 features are occupied.
- THEORY-999. The finite model at the same K = 16 expects 6.83. Both approach αH_N from below, the construction much faster.
- THEORY-1034. The Markov IBP’s stick-breaking construction is this one with an independent persistence attached to each stick.