Novelty detection: Unlabeled data definitely help

Clayton Scott, Gilles BlanchardAISTATS 2009 · OpenReview

Abstract

In machine learning, novelty detection typically involves building a detector based on a training sample of nominal data. The standard inductive approach identifies novelties where nominal density is low, effectively reducing the problem to density level set estimation. This paper explores a setting where an unlabeled, potentially contaminated sample is also available during training. We demonstrate that novelty detection can be naturally solved by reduction to a binary classification problem, specifically Neyman-Pearson classification. Unlike inductive methods, this approach yields optimal detectors regardless of the novelty distribution, showing that unlabeled data significantly improves the theoretical properties and performance of decision rules.

Introduction

Novelty detection—the identification of abnormal patterns within a dataset—is critical for applications ranging from fraud detection to biological anomaly identification. Traditionally, this task is approached "inductively": a model is trained exclusively on "nominal" (normal) data, and any point falling into a low-density region of this model is flagged as a novelty.

However, as Scott and Blanchard (2009) argue, this approach relies on the often-flawed assumption that novelties are uniformly distributed. In practice, novelties frequently cluster in specific regions, sometimes even overlapping with high-density nominal areas. This paper proposes a semi-supervised approach that leverages unlabeled data—which contains a mixture of both nominal and novel points—to build more robust and adaptive detectors.

Methodology: The Fundamental Reduction

The core innovation of this work is the "Fundamental Reduction." The authors prove that distinguishing nominal data ($P_0$) from novel data ($P_1$) is mathematically equivalent to distinguishing nominal data ($P_0$) from the mixture found in an unlabeled sample ($P_X$).

Neyman-Pearson Classification

The problem is framed as Neyman-Pearson (NP) classification. Instead of minimizing total error, the goal is to minimize the false negative rate (missing a novelty) while maintaining a fixed constraint on the false positive rate (incorrectly flagging nominal data).

The Hybrid Method and Mixture Estimation

To ensure robustness when the unlabeled sample contains few or no novelties, the authors introduce a "sprinkling" technique, adding a vanishingly small amount of synthetic uniform data. This allows the model to revert to a standard inductive approach if no real novelties are present. Additionally, they provide a learning-theoretic method for estimating the proportion of novelties ($\pi$) within the unlabeled mixture.

Experimental Evaluation

The proposed Semi-Supervised Novelty Detection (SSND) was evaluated against the standard inductive approach using three UCI benchmark datasets: Banana, Splice, and Waveform.

Standout Performance on Overlapping Data

The Splice dataset represents a challenging scenario where novelties significantly overlap with nominal data. As shown in Figure 1, the inductive method fails dramatically, performing worse than random guessing (AUC = 0.42). In contrast, the SSND approach achieves an AUC of 0.94, successfully identifying novelties even in regions of high nominal density.

ROC curve for the Splice dataset ($\pi = 0.5$), comparing semi-supervised and inductive approaches.

Robustness to Low Novelty Proportions

The Waveform dataset was used to test performance when novelties are rare ($\pi = 0.1$). Even with this low proportion, the SSND approach significantly outperformed the inductive method, as seen in Figure 2.

ROC curve for the Waveform dataset ($\pi = 0.1$), demonstrating performance with a low proportion of novelties.

Discussion and Insights

The primary advantage of the semi-supervised approach is its adaptability. While inductive methods are only optimal under specific, unlikely conditions, the SSND approach learns the actual shape of the novelty distribution from the unlabeled mixture. Furthermore, the authors prove that this approach is statistically consistent, meaning it is guaranteed to converge to the optimal decision rule as data volume increases—a claim inductive methods generally cannot make.

Limitations

The effectiveness of this method depends on a "resolvability" condition: novelties must not be a perfect subset of the nominal distribution. Additionally, as the proportion of novelties ($\pi$) decreases, the problem becomes harder, requiring larger unlabeled samples. Finally, the reduction to NP classification can be more computationally demanding than simple density estimation.

Conclusion

Scott and Blanchard provide a rigorous foundation for using unlabeled data in novelty detection. By treating the problem as a specialized form of binary classification, they demonstrate that "unlabeled mess" is not just noise, but a vital source of information that allows models to see what inductive approaches miss.

Summary updated

Abstract

In machine learning, one formulation of the novelty detection problem is to build a detector based on a training sample consisting of only nominal data. The standard (inductive) approach to this problem has been to declare novelties where the nominal density is low, which reduces the problem to density level set estimation. In this paper, we consider the setting where an unlabeled and possibly contaminated sample is also available at learning time. We argue that novelty detection is naturally solved by a general reduction to a binary classification problem. In particular, a detector with a desired false positive rate can be achieved through a reduction to Neyman-Pearson classification. Unlike the inductive approach, our approach yields detectors that are optimal (e.g., statistically consistent) regardless of the distribution on novelties. Therefore, in novelty detection, unlabeled data have a substantial impact on the theoretical properties of the decision rule.
BibTeX
@inproceedings{scott2009novelty,
  author = {Clayton Scott and Gilles Blanchard},
  title = {{Novelty detection: Unlabeled data definitely help}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2009},
  url = {https://openreview.net/forum?id=FbcTCWWwwWO},
}
Figure