Sketched Clustering via Hybrid Approximate Message Passing.

Evan Byrne, Antoine Chatalic, Rémi Gribonval, Philip SchniterIEEE TSP 2019 · OpenReview

TL;DR

This paper introduces CL-AMP, a novel algorithm for sketched clustering that uses approximate message passing to efficiently recover cluster centroids from a compressed "sketch" of the data. CL-AMP demonstrates superior sample complexity and computational efficiency compared to existing sketched clustering methods and k-means++, particularly for large datasets.

What Problem Does This Paper Address?

Traditional clustering algorithms like k-means++ can be computationally expensive and memory-intensive, especially when dealing with massive datasets (large $T$). Sketched clustering offers a solution by first compressing the data into a smaller representation (a "sketch") from which centroids are then extracted. This reduces storage requirements and can make centroid extraction independent of the original data size. However, existing sketched clustering methods, like CL-OMPR, often require a very large sketch size ($M \ge 10KN$) to achieve good results, limiting their efficiency. This paper aims to develop a sketched clustering algorithm that can achieve accurate results with smaller sketch sizes and lower computational complexity.

Methods

The core contribution is the CL-AMP (Clustered Learning via Approximate Message Passing) algorithm. It frames the centroid recovery problem as a high-dimensional inference task, modeling the data as a Gaussian Mixture Model (GMM). Instead of directly optimizing for centroids, CL-AMP uses a simplified hybrid generalized approximate message passing (SHyGAMP) framework. SHyGAMP is an iterative algorithm that approximates the posterior distribution of the centroids.

Key methodological aspects include:

  • Sketching: The paper utilizes a specific sketching method proposed by Keriven et al., which samples the empirical characteristic function of the data. This sketch is a vector $y$ of size $M$, where $M$ is typically much smaller than the original data size $T$.
  • Approximate Message Passing (AMP): CL-AMP leverages AMP, and specifically its simplified variant SHyGAMP, to efficiently infer the cluster centroids from the sketch. AMP algorithms are known for their ability to handle high-dimensional inference problems with computational complexity that scales favorably with data size.
  • Hybrid Approach: CL-AMP combines SHyGAMP with an Expectation-Maximization (EM) algorithm to jointly estimate the cluster weights and variances (hyperparameters $\alpha$ and $\tau$) along with the centroids.
  • Initialization: The paper proposes a multi-random initialization strategy for CL-AMP to improve robustness and avoid local optima.

Datasets

The paper evaluates CL-AMP on:

  • Synthetic Data: Generated from Gaussian Mixture Models (GMMs) with varying parameters for $K$ (number of clusters), $N$ (dimension), and $T$ (number of samples). This allows for controlled experiments to assess performance under different conditions.
  • MNIST Dataset: Used for spectral clustering. The standard MNIST dataset was augmented to create a larger version. The data preprocessing involved extracting SIFT descriptors, computing K-nearest-neighbor adjacency matrices, and then obtaining principal eigenvectors to form the feature vectors.

Key Insights and Ideas

  • AMP for Sketched Clustering: The paper demonstrates that approximate message passing, particularly the SHyGAMP framework, is a powerful tool for efficiently solving the centroid recovery problem in sketched clustering. This moves beyond traditional optimization-based approaches.
  • Improved Sample Complexity: CL-AMP achieves competitive or better clustering accuracy (measured by SSE and Classification Error Rate) with significantly smaller sketch sizes ($M \ge 2KN$) compared to CL-OMPR ($M \ge 10KN$). This is a crucial advantage for reducing memory and computational overhead.
  • Computational Efficiency: For large datasets ($T$ large), CL-AMP is shown to be more computationally efficient than both CL-OMPR and k-means++. This is attributed to the sketching step being performed only once and the efficient inference provided by AMP.
  • Hyperparameter Tuning: The integration of EM with SHyGAMP provides a practical way to tune the hyperparameters of the GMM and the sketch, further enhancing the algorithm's performance.

Key Results

  • Sketch Length: CL-AMP achieved the lowest SSE when $M \ge 2KN$, while CL-OMPR required $M \ge 10KN$ for comparable SSE. For sufficiently large $M$, both CL-AMP and CL-OMPR outperformed k-means++ in SSE.
  • Classification Error Rate (CER): CL-AMP achieved near-zero CER with $M \ge KN$, whereas k-means++ had an error rate of $\approx 0.2$. CL-OMPR also required $M \ge 10KN$ for low CER.
  • Runtime: For large $T$, CL-AMP was faster than k-means++ and CL-OMPR. When sketching time was included, CL-AMP's runtime scaled linearly with $T$. Without sketching time, the runtimes of CL-AMP and CL-OMPR were relatively invariant to $T$.
  • Frequency Estimation: CL-AMP demonstrated a higher empirical probability of recovery than CL-OMPR in a challenging multi-dimensional frequency estimation task, especially for closely spaced frequencies.

Limitations and Future Work

  • Computational Complexity of Estimation Steps: The authors acknowledge that the estimation steps within CL-AMP are still the most computationally intensive part of the algorithm. Future work could focus on reducing this complexity.
  • Theoretical Analysis: While the paper provides numerical evidence, a more rigorous theoretical analysis of CL-AMP's behavior using state-evolution approaches is suggested.
  • New Sketch Variations: The authors propose investigating how CL-AMP can be adapted to new variations of sketching techniques as they emerge.
  • Robustness to Hyperparameter Tuning: While the EM-SHyGAMP approach is effective, further investigation into reducing the complexity of hyperparameter tuning is mentioned. The paper notes that using a subset of terms in the EM objective can substantially reduce tuning complexity without significant loss in accuracy.

Summary updated

Abstract

In sketched clustering, a dataset of T samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Its advantages include 1) reduced storage complexity and 2) centroid extraction complexity independent of T. For the sketching methodology recently proposed by Keriven et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when T is large.
BibTeX
@article{byrne2019sketched,
  author = {Evan Byrne and Antoine Chatalic and Rémi Gribonval and Philip Schniter},
  title = {{Sketched Clustering via Hybrid Approximate Message Passing.}},
  journal = {IEEE Trans. Signal Process.},
  year = {2019},
  url = {https://openreview.net/forum?id=c1uBC5SRYAR},
}
Figure