Abstract
In this paper, we formulate the problem of inferring a Finite Mixture Model from discrete data as an optimal transport problem with entropic regularization of parameter $\lambda\geq 0$. Our method unifies hard and soft clustering, the Expectation-Maximization (EM) algorithm being exactly recovered for $\lambda=1$. The family of clustering algorithms we propose rely on the resolution of nonconvex problems using alternating minimization. We study the convergence property of our generalized $\lambda-$EM algorithms and show that each step in the minimization process has a closed-form solution when inferring finite mixture models of exponential families. Experiments highlight the benefits of taking a parameter $\lambda>1$ to improve the inference performance and $\lambda\to 0$ for classification.
Introduction
Clustering is a cornerstone of unsupervised learning, traditionally divided into two distinct paradigms: hard clustering and soft clustering. Hard clustering, exemplified by the $k$-means algorithm, assigns each data point to a single cluster. Soft clustering, typically implemented via the Expectation-Maximization (EM) algorithm for Gaussian Mixture Models (GMMs), assigns points to clusters probabilistically.
Despite their ubiquity, these methods often exist in isolation. Furthermore, the standard EM algorithm is frequently criticized for its sensitivity to initialization, its tendency to converge to poor local minima, and its vulnerability to overfitting in the presence of outliers. This research introduces a unified mathematical framework that bridges these two approaches using Regularized Optimal Transport (ROT), providing a tunable parameter $\lambda$ to control the "softness" and robustness of the clustering process.
The $\lambda$-EM Framework
The authors reformulate the inference of Finite Mixture Models (FMMs) as an Optimal Transport problem. By introducing Entropic Regularization controlled by a parameter $\lambda \geq 0$, they derive the $\lambda$-EM algorithm. This algorithm utilizes alternating minimization across three primary steps:
- Transport Plan ($\pi$): Determines the assignment of data points to clusters.
- Weights ($\omega$): Updates the relative importance or size of each cluster.
- Parameters ($\eta$): Updates the model parameters (e.g., means and covariances).
A Spectrum of Clustering
The power of this framework lies in the interpretation of the regularization parameter $\lambda$:
- $\lambda \to 0$ (Hard Clustering): The algorithm collapses into a hard assignment scheme, effectively functioning as a variant of $k$-means.
- $\lambda = 1$ (Standard EM): The framework exactly recovers the classic Expectation-Maximization algorithm.
- $\lambda > 1$ (Robust Inference): The algorithm produces more "diffuse" assignments. This acts as a regularizer, preventing the model from prematurely locking onto outliers or local noise, thereby increasing robustness against poor initializations.
For exponential families, such as Gaussians, each step of the $\lambda$-EM algorithm possesses a closed-form solution. This ensures computational efficiency, as the complexity scales with the number of clusters and data points rather than the dimensionality of the feature space.
Experimental Evaluation
The framework was evaluated using both synthetic datasets and real-world high-dimensional data.
Synthetic GMMs
Experiments on 1D and 2D Gaussian Mixture Models demonstrated that $\lambda = 1$ is not always the optimal setting for distribution recovery. Specifically, setting $\lambda \approx 1.1$ consistently led to better recovery of the underlying ground-truth distribution. In trials with 20 different random initializations, the $\lambda=1.1$ configuration showed a significantly lower standard deviation in error compared to standard EM, suggesting superior stability.
MNIST Latent Space
To test real-world applicability, the authors performed clustering on the MNIST dataset. Using a 64-dimensional latent space generated by a pre-trained autoencoder, the $\lambda$-EM algorithm was used for classification. Interestingly, while $\lambda > 1$ was superior for density estimation (inference), the hard clustering limit ($\lambda \to 0$) proved most effective for classification tasks. The proposed method achieved a classification accuracy of 0.666, outperforming the standard EM accuracy of 0.647.
Key Insights
- The Robustness Knob: The ability to tune $\lambda$ allows practitioners to move beyond the limitations of standard EM. Increasing $\lambda$ slightly above 1 provides a "global view" that prevents overfitting to single data points.
- Task-Specific Optimization: The research suggests a dichotomy in optimal settings: use $\lambda > 1$ for robustly inferring the underlying data distribution, but use $\lambda \to 0$ when the goal is discrete classification.
- Dimensionality Independence: The computational burden is decoupled from feature dimensionality, making it suitable for latent spaces of deep generative models.
Conclusion and Future Work
This unified framework provides a rigorous mathematical bridge between $k$-means and EM. While the $\lambda$-EM algorithm remains subject to the non-convex nature of mixture modeling, it offers a more robust path to convergence. Future research directions include extending the framework to hierarchical clustering, exploring unbalanced optimal transport (where mass conservation is not required), and implementing "annealing" strategies where $\lambda$ is dynamically adjusted during the iteration process to optimize both global search and local refinement.
Summary updated