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.
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