Scalable Inference on Kingman’s Coalescent Using Pair Similarity
Abstract
We present a scalable sequential Monte Carlo algorithm and its greedy counterpart for models based on Kingman’s coalescent. We utilize fast nearest neighbor algorithms to limit expensive computations to only a subset of data point pairs. For a dataset size of n, the resulting algorithm has O(n log n) computational complexity. We empirically verify that we achieve a large speedup in computation. When the gain in speed is used for increasing the number of particles, we can often obtain significantly better samples than those of previous algorithms. We apply our algorithm for learning visual taxonomies of birds on 6033 examples, a dataset size for which previous algorithms fail to be feasible.
Cite
Text
Gorur et al. "Scalable Inference on Kingman’s Coalescent Using Pair Similarity." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.Markdown
[Gorur et al. "Scalable Inference on Kingman’s Coalescent Using Pair Similarity." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.](https://mlanthology.org/aistats/2012/gorur2012aistats-scalable/)BibTeX
@inproceedings{gorur2012aistats-scalable,
title = {{Scalable Inference on Kingman’s Coalescent Using Pair Similarity}},
author = {Gorur, Dilan and Boyles, Levi and Welling, Max},
booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics},
year = {2012},
pages = {440-448},
volume = {22},
url = {https://mlanthology.org/aistats/2012/gorur2012aistats-scalable/}
}