A Variational EM Acceleration for Efficient Clustering at Very Large Scales
Florian Hirschberger, Dennis Forster, Jorg Lucke · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2021
How can we efficiently find very large numbers of clustersCin very large datasetsNof potentially high dimensionalityD? Here we address the question by using a novel variational approach to optimize Gaussian mixture models (GMMs) with diagonal covariance matrices. The variational method approximates expectation maximization (EM) by applying truncated posteriors as variational distributions and partial E-steps in combination with coresets. Run time complexity to optimize the clustering objective then reduces fromO(NCD) per conventional EM iteration toO(N′G2D) for a variational EM iteration on coresets (with coreset sizeN ′ ≤ Nand truncation parameterG≪C). Based on the strongly reduced run time complexity per iteration, which scales sublinearly withNC, we then provide a concrete, practically applicable, parallelized and highly efficient clustering algorithm. In numerical experiments on standard large-scale benchmarks we (A) show that also overall clustering times scale sublinearly withNC, and (B) observe substantial wall-clock speedups compared to already highly efficient recently reported results. The algorithm’s sublinear scaling allows for applications at scales where alternative methods cease to be applicable. We demonstrate such very large-scale applicability using the YFCC100M benchmark, for which we realize with a GMM of up to 50.000 clusters an optimization of a data density model with up to 150 M parameters.