Skip to yearly menu bar Skip to main content


Poster

Canopy --- Fast Sampling with Cover Trees

Manzil Zaheer · Satwik Kottur · Amr Ahmed · Jose Moura · Alex Smola

Gallery #39

Abstract:

Hierarchical Bayesian models often capture distributions over a very large number of distinct atoms. The need for these models arises when organizing huge amount of unsupervised data, for instance, features extracted using deep convnets that can be exploited to organize abundant unlabeled images. Inference for hierarchical Bayesian models in such cases can be rather nontrivial, leading to approximate approaches. In this work, we propose \emph{Canopy}, a sampler based on Cover Trees that is exact, has guaranteed runtime logarithmic in the number of atoms, and is provably polynomial in the inherent dimensionality of the underlying parameter space. In other words, the algorithm is as fast as search over a hierarchical data structure. We provide theory for Canopy and demonstrate its effectiveness on both synthetic and real datasets, consisting of over 100 million images.

Live content is unavailable. Log in and register to view live content