PaperlayerView exact revision on arXiv

Source-linked AI summary

Generative Adversarial Active Learning for Unsupervised Outlier Detection

Yezheng Liu, Zhe Li, Chong Zhou, Yuanchun Jiang, Jianshan Sun, Meng Wang, Xiangnan He

arXiv:1809.10816v4cs.LGstat.ML

TL;DR

High-dimensional sparsity can leave classifiers without enough informative potential outliers to separate anomalies from normal data. The paper proposes SO-GAAL and MO-GAAL, using adversarial generators to construct reference distributions, and reports strong performance across synthetic and real-world datasets. MO-GAAL achieves the best average ranking on real-world datasets and handles varied cluster types and high irrelevant-variable ratios.

  • Problem

    In high-dimensional spaces, limited potential outliers sampled from a uniform reference distribution may not provide enough information for a classifier to describe an effective separation boundary.

  • Method

    SO-GAAL uses a generator–discriminator mini-max game to generate informative potential outliers, while MO-GAAL uses multiple generators with different objectives to address mode collapse.

  • Results

    MO-GAAL achieves the best average ranking on real-world datasets, obtains the highest accuracy on six of fourteen datasets, and performs strongly with varied cluster types and high irrelevant-variable ratios.

  • Takeaways & Limitations

    The results support using multiple-objective adversarial generation to form a reference distribution for outlier detection across diverse dataset structures.

  • Takeaways & Limitations

    SO-GAAL lacks prior information for determining when training has generated sufficient potential-outlier information, making its stopping point extremely difficult to select.

Abstract

from arXiv · show

Outlier detection is an important topic in machine learning and has been used in a wide range of applications. In this paper, we approach outlier detection as a binary-classification issue by sampling potential outliers from a uniform reference distribution. However, due to the sparsity of data in high-dimensional space, a limited number of potential outliers may fail to provide sufficient information to assist the classifier in describing a boundary that can separate outliers from normal data effectively. To address this, we propose a novel Single-Objective Generative Adversarial Active Learning (SO-GAAL) method for outlier detection, which can directly generate informative potential outliers based on the mini-max game between a generator and a discriminator. Moreover, to prevent the generator from falling into the mode collapsing problem, the stop node of training should be determined when SO-GAAL is able to provide sufficient information. But without any prior information, it is extremely difficult for SO-GAAL. Therefore, we expand the network structure of SO-GAAL from a single generator to multiple generators with different objectives (MO-GAAL), which can generate a reasonable reference distribution for the whole dataset. We empirically compare the proposed approach with several state-of-the-art outlier detection methods on both synthetic and real-world datasets. The results show that MO-GAAL outperforms its competitors in the majority of cases, especially for datasets with various cluster types or high irrelevant variable ratio.

1 INTRODUCTION

Outlier detection is often treated as one-class classification because labeled anomalies are costly, but sparse high-dimensional data can make randomly generated potential outliers insufficient. The paper proposes SO-GAAL and MO-GAAL to generate more informative reference distributions and evaluates their performance.

  • Labeled anomalies are often prohibitively expensive to obtain, motivating one-class classification under an assumption that the dataset contains only normal instances.
  • Model-based, statistical, regression-based, cluster-based, and reconstruction-based detectors rely on assumptions about how normal data are generated.
  • Uniformly sampled potential outliers may provide too little information for classifiers to describe a clear boundary in high-dimensional space.
  • SO-GAAL uses a generator–discriminator mini-max game to generate informative potential outliers near real data for binary classification.
  • MO-GAAL expands SO-GAAL from one generator to multiple generators with different objectives to address mode collapse and generate a reference distribution for the dataset.

2 RELATED WORK

Related work includes model-based, proximity-based, artificially generated-potential-outlier, and GAN-based approaches. These methods differ in their assumptions, data requirements, and ability to provide informative coverage as dimensionality and data complexity increase.

  • Classic Outlier Detection Methods: Classic model-based methods identify outliers through deviations from fitted normal-data profiles, while their assumptions can limit performance on complex structures.
  • Classic Outlier Detection Methods: Proximity-based methods avoid training and distributional assumptions by measuring point rarity through quantities such as k-nearest-neighbor distance or local reachability density.
  • AGPO-based Methods: Artificially generated-potential-outlier methods create labeled data for a classifier and depend only weakly on distributional assumptions, but limited samples become inadequate as dimensionality increases.
  • GAN-based Methods: GANs learn deep representations through a mini-max game and have consequently attracted attention for outlier detection.

3 METHODOLOGY

The methodology reframes unsupervised outlier detection as classification against generated potential outliers, then uses adversarial generators to address high-dimensional sparsity and mode collapse. SO-GAAL uses one generator, while MO-GAAL combines multiple objectives and reference distributions to maintain a useful boundary.

  • 3.1 Approaching Outlier Detection as A Classification: AGPO-based detection replaces density estimation with classification by contrasting real data against potential outliers sampled from a uniform reference distribution.The classifier assigns higher scores to original data with higher relative density than the reference distribution.
  • 3.1 Approaching Outlier Detection as A Classification: The classification strategy avoids assumptions about normal-data distributions and requires less computing resources than directly calculating relative density.Minimizing the classifier loss allows C(x) to substitute for the optimal scoring function.
  • 3.1 Approaching Outlier Detection as A Classification: High-dimensional sparsity makes limited potential outliers insufficient for describing a correct boundary, especially when generated points miss anomalies or cluster near normal samples.The paper notes that covering the space may require an exponential number of potential outliers as dimensionality increases.
  • 3.2.1 Single-Objective Generative Adversarial Active Learning (SO-GAAL): SO-GAAL trains a generator and discriminator in a mini-max game, with the generator producing informative potential outliers and the discriminator describing the division boundary.The generator receives noise, while the discriminator estimates whether samples come from real or generated data.
  • 3.2.1 Single-Objective Generative Adversarial Active Learning (SO-GAAL): SO-GAAL can suffer mode collapse at Nash equilibrium, when generated potential outliers concentrate inside or near real data and detection accuracy drops.Because training lacks prior information for selecting the stopping point, the paper expands the model to multiple generators.
  • 3.2.2 Multiple-Objective Generative Adversarial Active Learning (MO-GAAL): MO-GAAL uses k sub-generators trained on equally divided real-data subsets with similar discriminator outputs, producing integrated reference distributions for the whole dataset.Each generator targets a representative subset statistic, while the discriminator continues estimating the probability that samples are real.
  • 3.2.2 Multiple-Objective Generative Adversarial Active Learning (MO-GAAL): MO-GAAL maintains relatively high detection accuracy at Nash equilibrium because its integrated sub-generators provide a reasonable reference distribution.The sub-generators stop when equilibrium is reached, after which discriminator training continues until its parameters barely change.

4.1 Experimental Settings

The experiments evaluate MO-GAAL and competing outlier detectors on synthetic and real-world datasets using AUC-based accuracy assessment and statistical testing. Synthetic data vary in cluster type, dimension, and irrelevant-variable ratio, while real-world evaluation includes benchmark and high-dimensional datasets.

  • Datasets: Experiments use both synthetic and real-world datasets to test the proposed algorithms.Synthetic datasets are generated across several design aspects, while the real-world collection includes benchmark and high-dimensional datasets.
  • Datasets: Synthetic datasets vary by cluster type, data dimension, and irrelevant variable ratio.The cluster types include single-cluster, multi-cluster, multi-density, and multi-shaped datasets.
  • Datasets: The real-world evaluation uses 10 benchmark datasets and 4 high-dimensional datasets with d ≥100.The datasets are converted to outlier-evaluation datasets using a procedure described in prior work.
  • Evaluation: Detection accuracy is measured with the ROC curve and corresponding AUC, supplemented by a Friedman test and posthoc analysis.The ROC and AUC measures are described as insensitive to the number of outliers; Friedman testing evaluates differences among algorithms.
  • Baselines: MO-GAAL is compared with nine representative outlier detection algorithms spanning density-, distance-, angle-, cluster-, one-class-, and active-outlier methods.AGPO and SO-GAAL are additionally compared on real-world datasets to assess the use of multiple generators.
  • Parameterization: The proposed methods use one generator for SO-GAAL and ten sub-generators for MO-GAAL under the stated parameter settings.The generators use three-layer neural networks, while the discriminator uses a single-hidden-layer neural network.

4.2 Experimental Results

MO-GAAL is evaluated on synthetic and real-world datasets, with results emphasizing robustness to complex clusters, irrelevant variables, and large data volumes. Statistical comparisons show MO-GAAL has the strongest overall ranking among the tested methods, while runtime advantages emerge mainly for larger datasets.

  • Synthetic Datasets: AUC is approximately 1 for almost all algorithms on single-cluster synthetic data, but GMM, k-means, and OC-SVM decline as clusters become more complex.GMM and k-means use the correct cluster counts but fail on multi-shaped data; OC-SVM is more susceptible to complex clusters with one global kernel width.
  • Synthetic Datasets: MO-GAAL handles datasets with various cluster types and high irrelevant-variable ratios more effectively than the compared methods.On complex clusters, several model-based methods describe incorrect boundaries, while distance-based methods degrade more rapidly as irrelevant variables increase.
  • Synthetic Datasets: When all variables are correlated, all methods achieve AUC equal to 1, whereas increasing irrelevant-variable ratios reduce performance, especially for distance-based methods.Irrelevant variables mask relevant attributes in neighbor queries, while AGPO-based methods evaluate sample concentration without distance calculation.
  • Synthetic Datasets: MO-GAAL has no runtime advantage on small datasets, but its computational requirement grows linearly with data size, unlike several O(n^2) competitors.The reported complexity is T(n)=O(n) for MO-GAAL versus O(n^2) distance computations and space complexity for kNN, FastABOD, LOF, KDEOS, and OC-SVM.
  • Real-World Datasets: MO-GAAL achieves the highest accuracy on six of fourteen real-world datasets and obtains the best average rank in the Nemenyi comparison.It is statistically better than AO, KDEOS, and OC-SVM at 95% confidence and better than GMM at 90% confidence.
  • Real-World Datasets: MO-GAAL is statistically better than SO-GAAL at the 95% confidence level, supporting multiple generators with different objectives for more stable results.SO-GAAL performs better on Waveform but performs poorly on some other datasets because training may stop after mode collapse.

4.3 Robustness Experiment on Network Structure

The robustness experiment varies the number of sub-generators and network capacity. Performance improves with multiple generators and remains stable across a reasonable range of network structures.

  • Sub-Generator Count: With multiple sub-generators, MO-GAAL’s average result rises from 0.7 to 0.84 and stabilizes once k reaches a sufficient size.The single-generator model, equivalent to SO-GAAL, performs significantly worse because of mode collapse; MO-GAAL is not sensitive to large k.
  • Generator Structure: A two-layer generator performs slightly worse because it generates insufficient informative potential outliers, while excessive depth can also slightly reduce performance.The seven-layer generator is affected by a relatively weak discriminator in the reported network variations.
  • Discriminator Structure: MO-GAAL remains robust when generator and discriminator structures vary within a reasonable range.A discriminator with too few hidden neurons slightly under-fits, while adequate network capacity produces comparable results.

5 CONCLUSIONS AND FUTURE WORKS

The paper introduces SO-GAAL to generate informative potential outliers and extends it to MO-GAAL with multiple objectives to prevent mode collapse. MO-GAAL achieves strong overall performance and robustness, especially on complex-cluster and high-irrelevance datasets, while its runtime advantage is primarily associated with larger datasets.

  • Conclusions: SO-GAAL directly generates informative potential outliers to address information loss caused by the curse of dimensionality.MO-GAAL extends SO-GAAL from one generator to multiple generators with different objectives to prevent mode collapse.
  • Conclusions: MO-GAAL achieves the best average ranking on real-world datasets and shows strong robustness to varying parameters.Synthetic experiments also indicate that it handles various cluster types and high irrelevant-variable ratios.
  • Conclusions: MO-GAAL’s runtime has no advantage for small datasets, while its computing requirement increases linearly with data size.The paper treats the small-dataset runtime limitation as acceptable with increasing computing power.
Loading 1809.10816v4…