Abstract
Based on the analysis of variance (ANOVA) decomposition of functions, which relies on the assumption that the function we wish to approximate can be well explained by limited variable interaction, we propose a sparse Gaussian-like mixture model on the high-dimensional torus. We consider three approaches: wrapped Gaussians, diagonal wrapped Gaussians, and products of von Mises distributions. The sparsity of the mixture model is ensured by the fact that its summands are products of Gaussian-like density functions acting on low-dimensional spaces and uniform probability densities defined on the remaining directions. To learn such a sparse mixture model from given samples, we propose an objective function consisting of the negative log-likelihood function and a regularizer that penalizes the number of summands. For minimizing this functional, we combine the Expectation-Maximization (EM) algorithm with a proximal step that takes the regularizer into account. To decide which summands of the mixture model are important, we apply a Kolmogorov-Smirnov test. Numerical examples demonstrate the performance of our approach.
Introduction
In high-dimensional statistics, the "curse of dimensionality" often renders traditional density estimation methods ineffective. As the number of dimensions increases, data becomes increasingly sparse, making it difficult to capture the underlying probability distribution without an overwhelming amount of data. However, many real-world systems exhibit "low-complexity interactions." This means that while a system might exist in a 100-dimensional space, any specific behavior or local density is likely driven by the interaction of only a small subset of variables (e.g., 2 or 3).
This paper introduces a novel approach to high-dimensional density estimation by applying the principles of ANOVA (Analysis of Variance) decomposition to mixture models. By focusing on these low-dimensional interactions, the proposed model can effectively represent complex densities on the torus ($T^d$), which is particularly relevant for periodic data such as orientations, phases, or seasonal cycles.
The Sparse Gaussian-Uniform Mixture Model
The authors propose a mixture model where each component is a hybrid of two distinct parts:
- Active Variables: A Gaussian-like density (wrapped Gaussian, diagonal wrapped Gaussian, or von Mises) acting on a small subset of dimensions.
- Inactive Variables: A uniform density acting on all other dimensions.
By assuming that "inactive" dimensions are uniform, the model treats them as maximum entropy noise. This prevents the model from over-fitting to coincidental patterns in high-dimensional space and focuses the learning process on the meaningful couplings between variables.
Optimization and Structure Learning
Learning the parameters and the structure of such a model requires balancing fit and complexity. The authors minimize an objective function that combines the negative log-likelihood with an $L_0$ "norm" regularizer to penalize the number of active components. The optimization process involves three key pillars:
- Expectation-Maximization (EM) Algorithm: A standard iterative method used to estimate the parameters of the mixture components.
- Proximal Step: A mathematical technique used to handle the non-convex $L_0$ penalty, which effectively "prunes" or zeros out unimportant components during the optimization process.
- Kolmogorov-Smirnov (KS) Test: To solve the combinatorial problem of which variables should be "active" for each component, the authors use the KS test as a statistical heuristic. It checks if the data in a specific dimension is distributed uniformly; if the null hypothesis of uniformity is rejected, that dimension is flagged as an active variable.
Experimental Evaluation
The researchers evaluated the sparse ANOVA-inspired model across several synthetic and benchmark scenarios:
- Synthetic Recovery: In 9-dimensional tests, the algorithm successfully reconstructed the original variable couplings, identifying exactly which variables were linked in the ground-truth density.
- Function Approximation: The model was tested on complex benchmarks like the Friedman-1 function (10 dimensions) and spline-based ANOVA functions, demonstrating its ability to capture non-linear interactions.
- Semi-Supervised Learning: In a 70-dimensional image orientation task (7x10 pixels), the model was used for classification. Remarkably, it achieved 93.6% accuracy using only three labeled samples per class. This suggests that the sparse ANOVA prior acts as a powerful regularizer, allowing the model to learn effectively from extremely limited labeled data.
Discussion and Future Work
The sparse ANOVA-inspired mixture model offers a significant departure from traditional sparse models like PCA-GMMs. While PCA-based models look for low-rank global structures, this approach looks for variable-wise sparsity, identifying specific coordinate interactions.
However, challenges remain. The "full" wrapped Gaussian model faces computational scaling issues as the number of active variables per component increases. Additionally, the selection of active variable sets currently relies on a heuristic (the KS test). Future research may focus on integrating variable selection more deeply into the optimization framework and addressing the mathematical open question of "identifiability"—whether a unique model can be recovered from the data—for wrapped normal distributions on the torus.
Summary updated