Fast Variational Mode-Seeking

Bo Thiesson and Jingu Kim

Abstract

Mode-seeking algorithms (e.g., mean-shift) constitute a class of powerful non-parametric clustering methods, but they are slow. We present VMS, a dual-tree based variational EM framework for mode-seeking that greatly accelerates performance. VMS has a number of pleasing properties: it generalizes across different mode-seeking algorithms, it does not have typical homoscedasticity constraints on kernel bandwidths, and it is the first truly sub-quadratic acceleration method that maintains provable convergence for a well-defined objective function. Experimental results demonstrate acceleration benefits over competing methods and show that VMS is particularly desirable for data sets of massive size, where a coarser approximation is needed to improve the computational efficiency.

Details

Publication typeInproceedings
Published inProceedings of The Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS) 2012, JMLR 22: W&CP 22
Pages(To appear)
PublisherJournal of Machine Learning Research
> Publications > Fast Variational Mode-Seeking