A Variational EM Acceleration for Efficient Clustering at Very Large Scales.

Area of Science:

• Machine Learning
• Data Mining
• Computational Statistics

Background:

• Efficiently clustering large datasets with high dimensionality is a significant challenge in data analysis.
• Gaussian Mixture Models (GMMs) are powerful tools for clustering but can be computationally intensive.

Purpose of the Study:

• To develop a novel variational approach for optimizing GMMs to enable efficient large-scale clustering.
• To reduce the computational complexity and improve the scalability of GMM optimization.

Main Methods:

• Utilized a variational method approximating Expectation Maximization (EM) with truncated posteriors and partial E-steps.
• Incorporated coresets to reduce data size, leading to a reduced run time complexity per iteration.
• Developed a parallelized and efficient clustering algorithm based on the reduced complexity.

Main Results:

• Reduced run time complexity per EM iteration from O(NCD) to O(N'G^2D) using coresets.
• Demonstrated sublinear scaling of overall clustering times with the number of clusters (C) and dataset size (N).
• Achieved substantial wall-clock speedups compared to existing efficient methods on large-scale benchmarks.

Conclusions:

• The proposed variational approach offers a highly efficient and scalable solution for GMM-based clustering.
• The algorithm's sublinear scaling enables applications on massive datasets where other methods fail.
• Successfully demonstrated applicability on the YFCC100M benchmark with 50,000 clusters and 150 million parameters.