Multivariate Triangular Quantile Maps for Novelty Detection

Jingjing Wang, Sun Sun, Yaoliang YuNeurIPS 2019

Overview

This paper introduces a unified framework for novelty detection by extending the concept of univariate quantile functions to the multivariate setting using Triangular Quantile Maps (TQM). By combining deep autoencoders with flow-based density estimation and a multi-objective optimization strategy, the authors create a robust, end-to-end system that outperforms state-of-the-art methods without requiring manual hyperparameter tuning.

The Challenge of Novelty Detection

Novelty detection—identifying "unusual" data points in a stream—is a cornerstone of machine learning with applications ranging from medical diagnosis to network security. Traditionally, this is done by finding low-density regions of a distribution.

However, two major hurdles exist:

  1. The Curse of Dimensionality: Estimating density in high-dimensional spaces (like images) is notoriously difficult.
  2. Algorithmic Fragmentation: Existing methods are often specialized. Some use "density scoring" (how likely is this point?), while others use "quantile scoring" (is this point in the extreme tail of the distribution?).

Furthermore, many deep learning approaches rely on a two-stage process (train an autoencoder, then fit a density estimator), which is often sub-optimal because the latent features learned in the first stage might not be the most "informative" for the second stage.

Methodology: Triangular Quantile Maps

The authors propose a general framework that centers on the Multivariate Triangular Quantile Map (TQM).

1. The Multivariate Quantile

In 1D, a quantile function maps a uniform distribution to your data distribution. To do this in multiple dimensions, the authors use "triangular maps." In a triangular map, the $j$-th component of the output depends only on the first $j$ coordinates of the input. This structure allows for efficient computation of inverses and determinants, which are essential for density estimation.

2. End-to-End Architecture

The model consists of:

  • A Feature Extractor ($f$): A deep autoencoder that compresses high-dimensional input into a lower-dimensional latent representation.
  • A TQM ($Q$): Implemented using Sum-of-Squares (SOS) flows, which learns the probabilistic structure of that latent space.

3. Multi-Objective Optimization (MGDA)

Instead of manually tuning a weight ($\lambda$) to balance the reconstruction loss (from the autoencoder) and the likelihood loss (from the TQM), the authors use the Multiple Gradient Descent Algorithm (MGDA). This treats the two losses as a multi-objective optimization problem, automatically finding a "Pareto-optimal" balance at every training step. This makes the implementation effectively hyperparameter-free.

Core Innovations

  • Unification: The authors show that classical algorithms like One-Class SVM and SVDD are actually special cases of their TQM framework when the latent dimension is set to one.
  • Dual Scoring: Because they learn the TQM, they can perform both density-based scoring (NLL) and quantile-based scoring (thresholding the map) simultaneously at no extra cost.
  • Quantile Control: Quantile scoring is particularly powerful because it allows practitioners to precisely control the Type-I error (the probability of falsely flagging a normal sample as novel).
  • Joint Training Wins: The paper demonstrates that training the autoencoder and the density estimator together using MGDA is significantly more effective than the common "train then fit" two-stage heuristic.

Experimental Results

The framework was evaluated on four diverse datasets: image data (MNIST and Fashion-MNIST) and tabular/non-image data (KDDCUP and Thyroid).

Image Data Performance: On MNIST and Fashion-MNIST, the TQM approach consistently outperformed or matched state-of-the-art baselines like DAGMM, DSEBM, and GPND. For example, on MNIST, the Ours-NLL variant achieved an average AUROC of 0.973, beating most competitors.

AUROC performance on MNIST and Fashion-MNIST datasets

Tabular Data Superiority: On the Thyroid dataset, the TQM method achieved an F1 score of 0.7527, representing a massive leap over the baseline RAW-OC-SVM (0.3887) and DAGMM (0.4782).

Precision, Recall, and F1 scores on tabular datasets (Thyroid and KDDCUP)

Stability: The MGDA optimization successfully eliminated the need to search for the "perfect" trade-off between reconstruction and density estimation, leading to more stable and reliable training.

Limitations and Future Directions

  • Latent Dimension Sensitivity: While the autoencoder helps with high dimensions, the performance still depends on choosing an appropriate latent dimension $m$.
  • Ordering: Triangular maps are sensitive to the ordering of input coordinates. While this didn't seem to hinder results in this paper, exploring permutation-invariant maps (like those based on optimal transport) is a noted area for future research.
  • Broader Applications: The authors suggest that the multivariate TQM could be useful for other probabilistic modeling tasks beyond just novelty detection, such as generative modeling or risk assessment.

Summary updated

BibTeX
@inproceedings{wang2019multivariate,
  author = {Jingjing Wang and Sun Sun and Yaoliang Yu},
  title = {{Multivariate Triangular Quantile Maps for Novelty Detection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure