THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Canopy --- Fast Sampling with Cover Trees
Manzil Zaheer · Satwik Kottur · Amr Ahmed · Jose Moura · Alex Smola

Tue Aug 08 06:06 PM -- 06:24 PM (PDT) @ C4.9& C4.10
in Monte Carlo methods 1 »

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.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Manzil Zaheer (Carnegie Mellon University)
Satwik Kottur (Carnegie Mellon University)
Amr Ahmed (Google)
Jose Moura (CMU)
Alex Smola (Amazon)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors