Relative Novelty Detection

Alexander J. Smola, Le Song, Choon Hui TeoAISTATS 2009

Introduction

Presented at AISTATS 2009, this research introduces a robust framework for novelty detection that prioritizes relative comparison over absolute density estimation. By comparing target data to a reference dataset, the proposed method achieves coordinate invariance and improved accuracy in identifying "novel" events.

The Problem: Sensitivity to Measure

Traditional novelty detection methods, such as the popular One-Class SVM, typically identify outliers by locating regions of low probability density. However, "density" is fundamentally dependent on the underlying coordinate system. A simple transformation—such as switching from linear to logarithmic scales—can drastically alter which regions are perceived as low-density by the algorithm.

Furthermore, standard methods often neglect available "normal" data that could serve as a baseline. The authors argue that novelty should be defined relative to a known distribution $q(x)$ to ensure consistency across different data parametrizations.

Methodology: Relative Novelty Detection

The core of the proposed approach is moving from absolute density $p(x)$ to the likelihood ratio $p(x)/q(x)$, where $q(x)$ represents a reference distribution of "normal" data.

1. Likelihood Ratio Estimation

Instead of estimating individual densities (a notoriously difficult task), the authors estimate the ratio directly using variational $f$-divergence. Specifically, they employ a Truncated Kullback-Leibler (KL) divergence.

2. Measure Invariance

By utilizing a ratio, any Jacobian resulting from a coordinate transformation affects both the numerator and denominator equally. This cancellation ensures the detection remains "measure invariant," making the algorithm robust to arbitrary feature re-scaling or coordinate mapping.

3. Optimization via DC Programming

The reparametrization required for this approach leads to a non-convex optimization problem. To address this, the authors utilize Difference of Convex (DC) Programming, which allows them to efficiently reach a globally optimal solution. They also incorporate the "$\nu$-trick" from standard SVMs to allow users to specify the expected fraction of novel data to be flagged.

Experimental Results

The method was evaluated against standard benchmarks, including USPS handwritten digits and synthetic image mosaics.

Image Mosaic Comparison

In the image mosaic task, the goal was to identify duplicate patches hidden within a grid of 256 distinct patches. The Truncated KL (TKL) method demonstrated significantly higher precision than the standard One-Class SVM, which produced a much noisier result with numerous false positives.

Detection results using the proposed TKL method, showing clear identification of novel patches with minimal noise.
Detection results using a standard 1-class SVM, which exhibits significantly more false positives (red highlights) compared to the relative approach.

Quantitative Benchmarking

On the USPS digit dataset, TKL consistently outperformed both 1-class SVM and SVMperf. For instance, when identifying "0" digits as novelties at a 2% fraction, TKL's accuracy was often double that of its competitors. The method proved particularly robust at the "leading margin," successfully flagging novelties even when they comprised a very small percentage (e.g., 2-3%) of the total dataset.

Conclusion

Relative Novelty Detection provides a mathematically grounded solution to the coordinate-dependence of traditional density-based methods. While it requires a reference dataset, its superior precision and invariance make it a powerful tool for real-world applications like satellite imagery analysis and anomaly detection in complex feature spaces. Future work may explore the statistical efficiency of various $f$-divergences beyond the truncated KL approach.

Summary updated

BibTeX
@article{smola2009relative,
  author = {Alexander J. Smola and Le Song and Choon Hui Teo},
  title = {{Relative Novelty Detection}},
  journal = {AISTATS},
  year = {2009},
}
Figure