Sparse mixture models inspired by ANOVA decompositions

Johannes Hertrich, Fatima Antarou Ba, Gabriele Steidl

TL;DR

This paper introduces a novel sparse mixture model for approximating high-dimensional functions, inspired by ANOVA decompositions. By assuming that only a limited number of variable interactions are important, the model achieves sparsity and is learned using a penalized log-likelihood objective optimized with an EM algorithm and a proximal step.

What Problem Does This Paper Address?

High-dimensional real-world systems often exhibit complexity arising from a small number of low-complexity interactions. Representing functions on high-dimensional data by functions on lower-dimensional spaces is a key challenge. While methods like active subspace and random features exist, this paper is motivated by the Analysis of Variance (ANOVA) decomposition, which breaks down a function into sums of functions acting on different variable combinations. The challenge is to efficiently learn models that capture these sparse, low-dimensional interactions from data, especially when dealing with probability density functions rather than direct function evaluations.

Methods

The core of the paper is a sparse mixture model built upon the idea of ANOVA decomposition. The model's components are designed to act on low-dimensional subspaces of the input space, with the remaining dimensions modeled by uniform densities. Three specific types of Gaussian-like components are proposed:

  • Wrapped Normal Distribution: A generalization of the normal distribution to the torus.
  • Diagonal Wrapped Normal Distribution: A simpler version where the covariance matrix is diagonal.
  • Products of von Mises Distributions: Another option for modeling directional data.

Learning these models involves minimizing a penalized negative log-likelihood function. This objective combines the standard log-likelihood with a sparsity-inducing regularizer that penalizes the number of mixture components. The optimization is achieved through a combination of:

  • Expectation-Maximization (EM) Algorithm: A standard iterative approach for latent variable models.
  • Proximal Step: Used to enforce the sparsity constraint on the mixture component weights.
  • Kolmogorov-Smirnov (KS) Test: Employed to identify important variable interactions and select relevant components.

Datasets

The paper evaluates its approach using synthetic datasets generated from known functions and mixture models. Specifically, they consider:

  • Mixture Models: Used to generate ground truth data for testing the model's ability to recover known structures.
  • Tensor Products of Splines: A function used for high-dimensional approximation benchmarks.
  • Normalized Friedman-1 Function: Another standard benchmark function for high-dimensional regression.
  • Synthetic Image Data: Images generated from five different classes, with the model learning from gradient orientations rather than raw pixel values. This section also introduces a semi-supervised classification task.

Key Insights and Ideas

  • ANOVA Decomposition as a Sparsity Prior: The paper leverages the ANOVA decomposition's insight that complex functions can often be explained by interactions of only a few variables. This naturally leads to a sparse model structure.
  • Gaussian-Uniform Components for Sparsity: By using Gaussian-like densities on low-dimensional subspaces and uniform densities on the rest, the model inherently enforces sparsity in terms of variable interactions.
  • Proximal EM for Sparse Learning: Combining the EM algorithm with a proximal step is a powerful technique for learning sparse models by simultaneously estimating latent variables and enforcing sparsity on model parameters.
  • Kolmogorov-Smirnov Test for Variable Selection: The KS test provides a principled way to assess whether a variable adds significant information to a component, aiding in the selection of relevant interactions.
  • "Opposite" Sparsity: The paper highlights that their approach focuses on sparsity in the "time domain" (i.e., which variables interact) rather than sparsity in the "Fourier domain" (i.e., which frequency components are important), contrasting with some other methods.

Key Results

The paper demonstrates the effectiveness of its proposed sparse mixture models through numerical examples.

  • Accurate Recovery of Couplings: The models successfully recover the underlying sparse structures (i.e., the sets of interacting variables, denoted by $u_k$) in synthetic data.
  • Competitive Log-Likelihood Values: The learned sparse mixture models achieve log-likelihood values comparable to or better than those obtained by other methods, indicating good data fitting.
  • Semi-Supervised Classification Accuracy: In a synthetic image classification task, the model achieves an accuracy of 93.6% on the test set.
  • Efficiency: The proximal step for sparsity enforcement is noted to be computationally efficient, making the overall EM algorithm practical.

Limitations and Future Work

  • Assumption of Known $d_s$: The heuristic for model selection assumes that the maximum number of interacting variables ($d_s$) is known a priori.
  • Computational Complexity for High Dimensions: While the model is designed for high dimensions, the complexity can still grow with the dimensionality of the components, especially for wrapped Gaussian distributions. The paper mentions that for diagonal wrapped Gaussians, the complexity is polynomial in the dimension, which is an advantage.
  • Identifiability of Wrapped Normal Distribution: The paper notes that the identifiability of the multivariate wrapped normal distribution on $T^d$ remains an open problem.
  • Future Work: The paper suggests exploring extensions to other types of distributions and further investigating the theoretical properties of the proposed models. The code for the implementation is made available online.

Summary updated

Abstract

Inspired by the analysis of variance (ANOVA) decomposition of functions, we propose a Gaussian-uniform mixture model on the high-dimensional torus which relies on the assumption that the function that we wish to approximate can be well explained by limited variable interactions. We consider three model approaches, namely 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 of the mixture model and a regularizer that penalizes the number of its summands. For minimizing this functional we combine the Expectation Maximization 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.
BibTeX
@inproceedings{hertrich2021sparse,
  author = {Johannes Hertrich and Fatima Antarou Ba and Gabriele Steidl},
  title = {{Sparse mixture models inspired by ANOVA decompositions}},
  booktitle = {ETNA},
  year = {2021},
  doi = {10.1553/etna\_vol55s142},
}
Figure