Abstract
We present a novel framework exploiting the cascade of phase transitions occurring during a simulated annealing of the Expectation-Maximisation algorithm to cluster datasets with multi-scale structures. Using the weighted local covariance, we can extract, a posteriori and without any prior knowledge, information on the number of clusters at different scales together with their size. We also study the linear stability of the iterative scheme to derive the threshold at which the first transition occurs and show how to approximate the next ones. Finally, we combine simulated annealing together with recent developments of regularised Gaussian mixture models to learn a principal graph from spatially structured datasets that can also exhibit many scales.
Introduction
Clustering high-dimensional data often involves navigating complex energy landscapes. Traditional methods like $k$-means or standard Expectation-Maximization (EM) for Gaussian Mixture Models (GMMs) are prone to getting trapped in local maxima and require a pre-specified number of clusters ($K$). This paper proposes a framework that treats clustering as a physical process, utilizing simulated annealing to observe a "cascade of phase transitions" as the model temperature (variance) is lowered. By tracking these transitions, researchers can automatically uncover hierarchical structures without needing to know the "correct" number of clusters in advance.
Methodology: Annealing and Stability
The core approach involves slowly decreasing the variance $\sigma^2$ of GMM components, viewing the negative log-likelihood as "free energy." The authors distinguish between two strategies:
- Hard Annealing: A global variance is enforced across all components, which is excellent for identifying the primary scales of a dataset.
- Soft Annealing: An inverse-Gamma prior is introduced on the variances, allowing individual components to adapt their local size while following a global cooling schedule. This is specifically designed for complex cases like overlapping or nested clusters.
Critically, the authors use Linear Stability Analysis to derive the exact threshold ($T_c$) at which the first split (phase transition) occurs. This threshold corresponds to the maximum eigenvalue of the data covariance matrix, providing a rigorous starting point for the annealing process.
Multi-Scale Hierarchical Detection
As the temperature drops, components undergo successive splits, revealing the data's hierarchical structure. The authors track the ratio $\Gamma_k/\sigma^2$ (weighted local covariance over global variance). When this ratio approaches unity, it indicates that a component has resolved a physical structure at that scale. This allows for an a posteriori interpretation: by over-specifying $K$, the annealing process naturally groups components, and the $\Gamma_k/\sigma^2$ metric identifies when real structures are resolved.
Resolving Nested Structures with Soft Annealing
While hard annealing excels at identifying distinct scales, it can struggle with nested clusters (e.g., a dense cluster within a sparse one). Soft annealing addresses this by allowing components to "relax" locally. The paper demonstrates that while hard annealing might fail to distinguish these overlapping densities, soft annealing successfully recovers both the nested structure and the correct variances for both components.
Key Insights and Results
- Clustering as a Phase Transition: The splitting of a cluster into sub-clusters is a physical transition. The first split always occurs along the direction of the data's first principal component.
- Robustness: The method accurately estimated cluster variances even when 70% of the data points were removed in sparse sampling tests.
- Scale Independence: The 2D diagrams produced allow for analysis of the annealing process regardless of the actual dimensionality of the data space.
Conclusion
By framing clustering as a sequence of phase transitions, this method provides a robust, scale-independent way to uncover hierarchical structures. Future work aims to connect these GMM phase transitions to latent representation learning in deep models like Restricted Boltzmann Machines, potentially offering new insights into how neural networks organize information.
Summary updated