Accelerated sampling for the Indian Buffet Process

ABSTRACT

We often seek to identify co-occurring hidden features in a set of observations. The Indian Buffet Process (IBP) provides a non-parametric prior on the features present in each observation, but current inference techniques for the IBP often scale poorly. The collapsed Gibbs sampler for the IBP has a running time cubic in the number of observations, and the uncollapsed Gibbs sampler, while linear, is often slow to mix. We present a new linear-time collapsed Gibbs sampler for conjugate likelihood models and demonstrate its efficacy on large real-world datasets.

REFERENCES

• 1: Chu, W., Ghahramani, Z., Krause, R., & Wild, D. (2006). Identifying protein complexes in high-throughput protein interaction screens using an infinite latent feature model. Pacific Symposium on Biocomputing (pp. 231--242).
• 2: Doshi-Velez, F., Miller, K. T., Gael, J. V., & Teh, Y. W. (2009). Variational inference for the Indian buffet process. Proceedings of the Intl. Conf. on Artificial Intelligence and Statistics (pp. 137--144).
• 3: Gelman, A., Carlin, J. B., Stern, H. S., & Rubin, D. B. (2003). Bayesian Data Analysis. Chapman & Hall/CRC.
• 4: Athinodoros S. Georghiades , Peter N. Belhumeur , David J. Kriegman, From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.6, p.643-660, June 2001 [doi>10.1109/34.927464]
• 5: Dilan Görür , Frank Jäkel , Carl Edward Rasmussen, A choice model with infinitely many latent features, Proceedings of the 23rd international conference on Machine learning, p.361-368, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143890]
• 6: Griffiths, T., & Ghahramani, Z. (2005). Infinite latent feature models and the Indian buffet process. TR 2005--001, Gatsby Comp. Neuroscience Unit.
• 7: Hoffmann, U., Vesin, J.-M., Ebrahimi, T., & Diserens, K. (2008). An efficient P300-based brain-computer interface for disabled subjects. Journal of Neuroscience Methods, 167, 115--125.
• 8: Aleix M. Martínez , Avinash C. Kak, PCA versus LDA, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.228-233, February 2001 [doi>10.1109/34.908974]
• 9: Meeds, E., Ghahramani, Z., Neal, R., & Roweis, S. (2007). Modeling dyadic data with binary latent factors. Advances in Neural Information Processing Systems (pp. 977--984).
• 10: Daniel J. Navarro , Thomas L. Griffiths, Latent features in similarity judgments: A nonparametric bayesian approach, Neural Computation, v.20 n.11, p.2597-2628, November 2008 [doi>10.1162/neco.2008.04-07-504]
• 11: Graham E. Poliner , Daniel P. W. Ellis, A discriminative model for polyphonic piano transcription, EURASIP Journal on Applied Signal Processing, v.2007 n.1, p.154-154, 1 January 2007 [doi>10.1155/2007/48317]
• 12: Teh, Y. W., Görür, D., & Ghahramani, Z. (2007). Stick-breaking construction for the Indian buffet process. Proceedings of the Intl. Conf. on Artificial Intelligence and Statistics (pp. 556--563).
• 13: Welling, M., & Kurihara, K. (2009). Bayesian K-means as a "maximization-expectation" algorithm. Neural Computation (pp. 1145--1172).
• 14: Wood, F., & Griffiths, T. L. (2007). Particle filtering for nonparametric Bayesian matrix factorization. Advances in Neural Information Processing Systems (pp. 1513--1520).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory