---
abstract: 'We develop a framework for approximating collapsed Gibbs sampling in generative latent variable cluster models. Collapsed Gibbs is a popular MCMC method, which integrates out variables in the posterior to improve mixing. Unfortunately for many complex models, integrating out these variables is either analytically or computationally intractable. We efficiently approximate the necessary collapsed Gibbs integrals by borrowing ideas from expectation propagation. We present two case studies where exact collapsed Gibbs sampling is intractable: mixtures of Student-$t$’s and time series clustering. Our experiments on real and synthetic data show that our approximate sampler enables a runtime-accuracy tradeoff in sampling these types of models, providing results with competitive accuracy much more rapidly than the naive Gibbs samplers one would otherwise rely on in these scenarios.'
author:
- 'Christopher Aicher[^1] and Emily B. Fox[^2]'
bibliography:
- 'bib.bib'
title: Approximate Collapsed Gibbs Clustering with Expectation Propagation
---

Introduction
============

Background {#sec:background}
==========

Approximate Collapsed Gibbs Sampling
====================================

\[sec:inference\]

Case Studies
============

\[sec:case\_studies\] We consider two motivating examples for the use of our EP-based approximate collapsed Gibbs algorithm. The first is a mixture of Student-$t$ distributions, which can capture heavy-tailed emissions crucial in robust modeling (i.e., reducing sensitivity to outliers). The second example is a time series clustering model.

Mixture of Multivariate Student-$t$
-----------------------------------

\[sec:student\]

Time Series Clustering
----------------------

\[sec:tscluster\]

Experiments
===========

\[sec:experiments\]

Conclusion
==========

We presented a framework for constructing approximate collapsed Gibbs samplers for efficient inference in complex clustering models. The key idea is to approximately marginalize the nuisance variables by using EP to approximate the conditional distributions of the variables with an individual observation removed; by approximating this conditional, the required integral becomes tractable in a much wider range of scenarios than that of conjugate models. Our use of this EP approximation takes two steps from its traditional use: (1) we approximate a (nearly) full conditional rather than directly targeting the posterior, and (2) our targeted conditional changes as we sample the cluster assignment variables. For the latter, we provided a brief analysis and demonstrated the impact of the changing target, drawing parallels to previously proposed samplers that use stale sufficient statistics.

We demonstrated how to apply our EP-based approximate sampling approach in two applications: mixtures of Student-$t$ distributions and time series clustering. Our experiments demonstrate that our EP approximate collapsed samplers mix more rapidly than naive Gibbs, while being computationally scalable and analytically tractable. We expect this method to provide the greatest benefit when approximately collapsing large parameter spaces. There are many interesting directions for future work, including deriving bounds on the asymptotic convergence of our approximate sampler [@pillai2014ergodicity; @dinh2017convergence], considering different likelihood approximation update rules such as *power EP* [@minka2004power], and extending our idea of approximately integrating out variables to other samplers. For the analysis, [@dehaene2015expectation] showed that EP with Gaussian approximations is exact in the large data limit; one could extend these results to consider the case of data being allocated amongst *multiple* clusters. Another interesting direction is to explore our EP-based approximate collapsing within the context of variational inference, possibly extending the set of models for which collapsed variational Bayes [@teh2007collapsed] is possible. Finally, there are many ways in which our algorithm could be made even more scalable through distributed, asynchronous implementations, such as in [@ahmed2012scalable].

Acknowledgements {#acknowledgements .unnumbered}
================

We would like to thank Nick Foti, You “Shirley” Ren and Alex Tank for helpful discussions. This paper is based upon work supported by the NSF CAREER Award IIS-1350133

This paper is an extension of our previous workshop paper [@aicher2016scalable].

**Appendix**

Mixture of Multivariate Student-$t$ {#app:student}
===================================

Time Series Clustering {#app:tscluster}
======================

EP Convergence {#app:ep_converge}
==============

Synthetic Time Series Trace Plots {#app:traceplots}
=================================

Seattle Housing Data {#app:housing_data}
====================

[^1]: Department of Statistics, University of Washington, `aicherc@uw.edu`

[^2]: Department of Computer Science and Statistics, University of Washington, `ebfox@uw.edu`
