Fast Bayesian Inference in Dirichlet Process Mixture Models
Background
- How to perform online/streaming inference in Dirichlet process mixture model?
Conceptual Notes
- Problem: Enumerating & updating all possible partitions (hypothesized clusters) requires super-exponential time and space
- Idea: if each observation is assigned to one cluster, then the previous customers’
table assignments are known exactly
- For each observation \(x_n\), set cluster assignment to the MAP value \(\hat{z}_n = \argmax_{k} p(z_n = k | \hat{z}_{1:n}, x_{1:n})\)
- Then, using that cluster assignment, update the cluster’s parameter(s)
-
Algorithm is called Sequential Updating and Greedy Search (SUGS). Gershman calls it the “local MAP” approximation, which I feel is better
- Challenge: This sequential process means the latent variables are no longer exchangeable
- Answer: Repeat the sequential process multiple times, changing the sequential ordering of the data, and average over the permutations