Sorting out typicality with the inverse moment matrix SOS polynomial

Jean-Bernard Lasserre, Edouard Pauwels

TL;DR

This paper introduces a mathematically elegant way to "shrink-wrap" a cloud of data points using a specific sum-of-squares (SOS) polynomial derived from the inverse of an empirical moment matrix. By leveraging the classical theory of Christoffel functions and orthogonal polynomials, the authors provide a simple, affine-invariant tool that captures complex data shapes and identifies outliers with performance comparable to deep learning models.

What Problem Does This Paper Address?

In machine learning, "capturing the shape" of data is fundamental for tasks like novelty detection, clustering, and density estimation. However, data often lives in high-dimensional spaces with non-standard dependencies (e.g., a fraudulent action might only look suspicious when two "normal" variables are combined in a specific way).

Existing non-parametric methods, like Kernel Density Estimation or Nearest Neighbors, often struggle with computational scaling because their evaluation cost grows with the number of data points ($n$). This paper seeks a method that is computationally efficient, has a rigorous mathematical foundation, and can adapt to complex, non-convex geometries without needing a massive number of parameters.

Methods

The authors propose using a distinguished SOS polynomial ($Q_{\mu,d}$).

  1. The Construction: Given a set of points, you first compute their empirical moments (averages of $x, x^2, xy$, etc.) up to a chosen degree $d$. These are organized into a Moment Matrix ($M_d$). The SOS polynomial is then defined as: $$Q_{\mu,d}(x) = v_d(x)^T M_d(\mu)^{-1} v_d(x)$$ where $v_d(x)$ is a vector of all monomials up to degree $d$.

  2. The Connection: The authors reveal that this polynomial is the reciprocal of the Christoffel function, a classic tool from the theory of orthogonal polynomials.

  3. Variational Formulation: They prove a new theoretical result: this specific polynomial is the unique solution to a convex optimization problem that balances minimizing the average value of the polynomial over the data while preventing it from collapsing to zero.
  4. Computational Efficiency: Unlike kernel methods, once the moment matrix is inverted, the cost of checking if a new point is an outlier is independent of the number of training points. It can also be updated "online" as new data arrives using efficient matrix update formulas (Woodbury updates).

Datasets

  • Synthetic 2D Clouds: Used for visualization to show how the polynomial's sublevel sets adapt to "X" shapes, rings, and clusters of Gaussians.
  • KDD Cup 99 Network Intrusion Dataset: A massive real-world dataset containing millions of network connections. The authors focused on five specific subsets: http, smtp, ftp-data, ftp, and others.

Key Insights and Ideas

  • The "Aha" Visualization: The paper's most striking finding is empirical: the sublevel sets of this polynomial (specifically where the value is $\binom{p+d}{d}$) trace the boundary of the data cloud with remarkable accuracy.
  • Complexity Control: The degree $d$ acts as a "complexity knob." At $d=1$, the method is equivalent to the standard Mahalanobis distance (which assumes the data is an ellipse). As $d$ increases, the "envelope" can bend and twist to fit non-convex shapes like rings or crosses.
  • Affine Invariance: The method is naturally "blind" to stretching, rotating, or shifting the data. If you rotate your data cloud, the SOS polynomial's level sets rotate perfectly with it.
  • Density vs. Outlyingness: The polynomial takes low values in high-density regions and grows rapidly as you move away from the data, making it a natural score for "outlyingness."

Key Results

  • Competitive Performance: On the KDD Cup network intrusion task, the SOS polynomial (using $d=3$) achieved outlier detection performance similar to—and in some cases better than—dedicated methods like Recurrent Neural Networks (RNNs) and mixture models.
  • Efficiency: The authors demonstrate that the method can handle hundreds of thousands of examples easily because the moment matrix size depends on the dimension and degree, not the number of observations.
  • Robustness: In the "others" dataset (the most heterogeneous subset), increasing the degree $d$ from 1 to 3 significantly improved the Area Under the Precision-Recall Curve (AUPR), proving that capturing non-linear shapes is vital for real-world anomaly detection.

Limitations and Future Work

  • The Curse of Dimensionality: The size of the moment matrix grows exponentially with the dimension $p$ and degree $d$. While it works great for "moderate" dimensions (like the 3D features used in the KDD experiment), it would require specialized "sparse" techniques to work on very high-dimensional data like raw images.
  • Numerical Stability: Inverting moment matrices can become numerically unstable if the degree $d$ is set too high or if the data is highly degenerate.
  • Future Directions: The authors suggest exploring the relationship between this method and Maximum Likelihood Estimation, as well as investigating the "asymptotic" behavior—what happens to the shape as the degree $d$ goes to infinity?

Summary updated

BibTeX
@inproceedings{lasserre2016sorting,
  author = {Jean-Bernard Lasserre and Edouard Pauwels},
  title = {{Sorting out typicality with the inverse moment matrix SOS polynomial}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=HkZ4AL-ObS},
}
Figure