Scalable Inference on Kingman’s Coalescent using Pair Similarity

Dilan Gorur, Levi Boyles, Max Welling
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:440-448, 2012.

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 this Paper

BibTeX
@InProceedings{pmlr-v22-gorur12, 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}, pages = {440--448}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/gorur12/gorur12.pdf}, url = {https://proceedings.mlr.press/v22/gorur12.html}, 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.} }
Endnote
%0 Conference Paper %T Scalable Inference on Kingman’s Coalescent using Pair Similarity %A Dilan Gorur %A Levi Boyles %A Max Welling %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-gorur12 %I PMLR %P 440--448 %U https://proceedings.mlr.press/v22/gorur12.html %V 22 %X 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.
RIS
TY - CPAPER TI - Scalable Inference on Kingman’s Coalescent using Pair Similarity AU - Dilan Gorur AU - Levi Boyles AU - Max Welling BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-gorur12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 440 EP - 448 L1 - http://proceedings.mlr.press/v22/gorur12/gorur12.pdf UR - https://proceedings.mlr.press/v22/gorur12.html AB - 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. ER -
APA
Gorur, D., Boyles, L. & Welling, M.. (2012). Scalable Inference on Kingman’s Coalescent using Pair Similarity. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:440-448 Available from https://proceedings.mlr.press/v22/gorur12.html.

Related Material