PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Representations of Ultrahigh-dimensional Data for Random Distance-based Outlier Detection

Guansong Pang, Longbing Cao, Ling Chen, Huan Liu

arXiv:1806.04808v1cs.LGcs.AIcs.DBstat.ML

TL;DR

Ultrahigh-dimensional outlier detection needs representations tailored to irregularities, whereas existing unsupervised methods mainly preserve regularity and operate independently of detectors. RAMODO jointly learns detector-specific low-dimensional representations, instantiated by REPEN for random distance-based detection. Across eight real-world data sets, REPEN improved AUC and speed, outperformed four representation-learning competitors, and gained up to 32% AUC from less than 1% labeled outliers.

  • Problem

    Existing unsupervised representations preserve data regularity and are learned independently of outlier detectors, limiting detector-specific and application-specific outlier representation.

  • Method

    RAMODO uses a ranking-model framework that jointly learns low-dimensional representations and random distance-based outlier detection, with REPEN targeting Sp.

  • Results

    Across eight real-world ultrahigh-dimensional data sets, REPEN produced better AUC and two orders of magnitude speedup, outperformed four competitors, and achieved up to 32% AUC improvement with less than 1% labeled outliers.

  • Takeaways & Limitations

    Detector-tailored representations can provide more effective and stable random distance-based outlier detection while using very little labeled prior knowledge.

  • Takeaways & Limitations

    REPEN underperformed CoP on R8 and HLLE on News20 for structural or neighborhood-dependent outliers, motivating other RAMODO instances.

Abstract

from arXiv · show

Learning expressive low-dimensional representations of ultrahigh-dimensional data, e.g., data with thousands/millions of features, has been a major way to enable learning methods to address the curse of dimensionality. However, existing unsupervised representation learning methods mainly focus on preserving the data regularity information and learning the representations independently of subsequent outlier detection methods, which can result in suboptimal and unstable performance of detecting irregularities (i.e., outliers). This paper introduces a ranking model-based framework, called RAMODO, to address this issue. RAMODO unifies representation learning and outlier detection to learn low-dimensional representations that are tailored for a state-of-the-art outlier detection approach - the random distance-based approach. This customized learning yields more optimal and stable representations for the targeted outlier detectors. Additionally, RAMODO can leverage little labeled data as prior knowledge to learn more expressive and application-relevant representations. We instantiate RAMODO to an efficient method called REPEN to demonstrate the performance of RAMODO. Extensive empirical results on eight real-world ultrahigh dimensional data sets show that REPEN (i) enables a random distance-based detector to obtain significantly better AUC performance and two orders of magnitude speedup; (ii) performs substantially better and more stably than four state-of-the-art representation learning methods; and (iii) leverages less than 1% labeled data to achieve up to 32% AUC improvement.

1 INTRODUCTION

Ultrahigh-dimensional data makes outlier detection difficult, while existing representations often preserve general regularity rather than detector-specific irregularities. RAMODO unifies representation learning with random distance-based detection, and REPEN achieves stronger, more stable, faster results while using limited labels.

  • Motivation: Ultrahigh-dimensional applications with thousands to millions of features face significant outlier-detection challenges from the curse of dimensionality.Examples include abnormal bioactivities, corporate fraud, and malicious URLs.
  • Motivation: Existing unsupervised representations preserve regularity information for tasks such as clustering or compression, rather than information tailored to outlier detection.They also have difficulty incorporating application-specific knowledge such as labeled outliers.
  • Contributions: RAMODO unifies representation learning and random distance-based outlier detection to learn customized low-dimensional features for the targeted detectors.The framework can incorporate application-specific knowledge to learn more expressive and relevant representations.
  • Contributions: REPEN instantiates RAMODO for the random nearest-neighbor distance-based detector Sp, whose scalable scoring guides customized representation learning.Sp is selected as a state-of-the-art effective and efficient random distance-based method.
  • Empirical Results: Two orders of magnitude speedup and significantly better AUC performance were obtained for the original distance-based detector on eight real-world data sets.The experiments also compared REPEN with four state-of-the-art representation learning competitors.
  • Empirical Results: Up to 32% AUC improvement was achieved by leveraging less than 1% labeled outliers as prior knowledge.REPEN also performed more stably than four competitors.

2 RELATED WORK

Related work includes conventional distance-based detectors and unsupervised methods for reducing representation dimensionality. Prior approaches address scalability, robustness, or labeled knowledge, but remain limited for ultrahigh-dimensional outlier detection.

  • Distance-based Outlier Detection: Traditional nearest-neighbor distance-based methods have quadratic time complexity in data size, although indexing or distributed computing can make it nearly linear.Random distance-based and ensemble methods offer similar time-complexity reductions with additional benefits discussed in the paper.
  • Representation Learning: Unsupervised representation learning spans spectral methods, neural networks, manifold learning, and random projection for reducing high-dimensional data.Examples include PCA, autoencoders, locally linear embedding, and sparse random projection.
  • Robust Representation Learning: Robust PCA and robust autoencoders reduce outlier-induced bias, while coherent pursuit and combined robust methods address additional issues but can be unscalable.The latter methods involve costly eigen analysis or alternative optimization for large ultrahigh-dimensional data.
  • Knowledge-guided Detection: Some labeled-outlier methods incorporate application-specific knowledge into graph outlier detection, but converting ultrahigh-dimensional data remains a challenge.Unsupervised detectors may identify noise or uninteresting objects when prior knowledge of irregularities is absent.

3 THE PROPOSED FRAMEWORK: RAMODO

RAMODO learns a low-dimensional space in which random distance-based detectors can more effectively rank outliers. It uses ranking-based representation learning, optional labeled knowledge, and detector-guided optimization to retain task-relevant information while reducing computation.

  • 3.1 Problem Statement: The goal is to learn f: X 7→ R^M, with M ≪ D, so random distance-based scores rank outliers above inliers in the learned space.The scoring function uses distances to objects in a random subsample.
  • 3.2 Ranking Model-based Representation Learning Framework: RAMODO partitions data into inlier and outlier candidate sets, then constructs meta-triplets from inlier queries, a positive inlier, and an outlier candidate.This generalized pairwise ranking model provides the framework’s sampling structure.
  • 3.2 Ranking Model-based Representation Learning Framework: RAMODO can incorporate labeled inliers or outliers into candidate sets when application-specific labels are available.In the unsupervised setting, candidate outliers can also be generated using existing detectors and Chebyshev’s inequality.
  • 3.2 Ranking Model-based Representation Learning Framework: The representation is optimized with a random distance-based score and loss so the outlier candidate receives a larger score than the positive example.The supplied formulation identifies ϕ as the random distance-based scoring function and L as a loss function.
  • 3.2 Ranking Model-based Representation Learning Framework: Detector-guided representations retain information most relevant to ϕ, enabling comparable or better accuracy in spaces with M ≪ D.The framework targets random distance-based scoring, including KNN detectors based on K-th or average nearest-neighbor distances.
  • 3.2 Ranking Model-based Representation Learning Framework: Lower-dimensional representations can accelerate distance computation and nearest-neighbor search when indexing methods become effective.The paper gives M ≤ 30 as an example of a significantly lower-dimensional space.

4 A RAMODO INSTANCE: REPEN

REPEN instantiates RAMODO by learning low-dimensional representations customized for the random nearest-neighbor detector Sp. It uses outlier rankings, thresholded candidate sets, score-based triplet sampling, and a ranking loss to guide efficient representation learning.

  • 4 A RAMODO INSTANCE: REPEN: REPEN customizes representations for Sp, a random nearest-neighbor distance-based outlier detector.RAMODO can also be customized for other random distance-based methods.
  • 4.1 Outlier Thresholding: An ensemble of Sp produces an initial outlier ranking, which is thresholded with Cantelli’s inequality into inlier and outlier candidate sets.The default α = 1.732 corresponds to a 25% false-positive upper bound.
  • 4.2 Triplet Sampling: Triplets combine query sets and positive examples from inliers with negative examples sampled from the outlier candidate set.Importance sampling favors representative inliers as queries and likely outliers as negatives, while uniform sampling diversifies positive examples.
  • 4.3 Representation Learning: A single hidden layer maps D-dimensional inputs to M-dimensional representations because ultrahigh-dimensional settings often have N ≪ D and make deep training costly.The representation uses a fully connected layer with an activation function ψ and parameters Θ.
  • 4.4 Ranking Loss: REPEN minimizes a hinge ranking loss that makes pseudo outliers have larger nearest-neighbor distances than pseudo inliers in the query set.The margin parameter c controls the desired distance difference, and the loss penalizes ranking-order violations.
  • 4.4 Ranking Loss: With infinitely many triplets, REPEN optimizes Sp’s precision at top |O|, while its representation dimension M is not learned automatically.The algorithm outputs X′ = fΘ(X) after iterative gradient-based optimization.

5 THEORETICAL FOUNDATION OF REPEN

The theoretical analysis bounds REPEN’s representation-learning error through the quality of its pseudo inlier and outlier samples. Cantelli thresholding controls false positives without assuming a specific score distribution, while small query sets can yield small error bounds.

  • 5.1 Upper Error Bound: REPEN’s error analysis replaces the original detector’s nearest-neighbor distances with distances in the learned representation and query set.The resulting expression is treated as an upper error bound for representation learning.
  • 5.1 Upper Error Bound: A sufficiently large γ and small query set Q can make the representation-learning error bound small when pseudo inliers and outliers are genuine.The analysis links small n to a small error bound and guaranteed expressiveness under genuine sampling.
  • 5.2 Reliable Triplet Sampling: Genuine outliers in the outlier candidate set are key to representation learning because the sampling process has a high probability of selecting genuine inliers.A few labeled outliers provide a good guarantee for the error bound.
  • 5.2 Reliable Triplet Sampling: Cantelli’s inequality bounds the probability of scores exceeding µ + αδ using only the score vector’s mean and variance.The threshold yields a false-positive upper bound of 1/(1+α^2) and requires no specific probability-distribution assumption.

6 EXPERIMENTS

The experiments evaluate REPEN on eight real-world ultrahigh-dimensional data sets spanning diverse application domains. They assess downstream Sp detection using AUC and average precision, with repeated runs and statistical testing for sampled settings.

  • 6.1 Data Sets: Eight real-world ultrahigh-dimensional data sets cover malicious URL, cancer, molecular bioactivity, medical diagnosis, text, and Internet advertisement detection.The benchmark spans diverse domains and feature scales.
  • 6.1 Data Sets: URL and Webspam are converted into outlier-detection data sets with 2% outliers by downsampling the smaller or positive class.The same downsampling approach is applied to News20.
  • 6.2 Evaluation: REPEN representations are evaluated by applying Sp in the original or representation space and measuring ranking quality with AUC and average precision.Sp returns a full ranking list from which these performance measures are computed.
  • 6.3 Evaluation Protocol: Paired Wilcoxon signed rank tests examine REPEN against competitors, while sampled algorithms or data sets use AUC averages over 10 independent runs.Runtime is measured on a 2.8GHz Titan cluster with 256GB memory.

6.3 Effectiveness in Real-world Data with Thousands to Millions of Features

REPEN compresses ultrahigh-dimensional data into 20 dimensions while preserving or improving Sp’s AUC and substantially reducing detection runtime.

  • AUC performance: REPEN-enabled Sp significantly outperforms original Sp on eight data sets at the 95% confidence level.The AUC significance test yields p-value 0.0156.
  • Representation efficiency: REPEN retains only 20 dimensions, at most 1.3% of the original dimensionality, while achieving comparable or better AUC.The comparison uses the same detector in the original and representation spaces.
  • AUC performance: 1.5% to 20% AUC improvement is obtained on most data sets with REPEN-enabled Sp.The customized objective preserves information relevant to Sp while reducing irrelevant features.
  • Detection runtime: Two orders of magnitude faster detection is achieved by Sp in REPEN’s 20-D representation space.k-d tree indexing is effective in the representation space but fails on the original ultrahigh-dimensional data.

6.4 Comparing to State-of-the-art Representation Learning Competitors

REPEN is compared with four unsupervised representation learners using 20-dimensional outputs, and generally delivers stronger and more stable Sp performance.

  • Overall comparison: REPEN performs significantly better than AE and SRP, and comparably better than HLLE and CoP at 20 dimensions.The comparison covers neural network, manifold-learning, random-projection, and robust-PCA approaches.
  • Dataset-level results: 14% to 32% AUC improvement over all competitors occurs on AD, while OT shows 5% to 42% improvement.On URL, REPEN improves AUC by 27% to 33% over AE and SRP.
  • Interpretation: Detector-independent competitors cannot exploit Sp-specific information during representation learning.REPEN uses detector-guided triplet sampling and optimization, whereas the competitors learn representations independently of Sp.
  • Stability: REPEN performs more stably across data sets, ranking first on five and second on the remaining three.Several competitors perform poorly on particular data sets despite achieving isolated best results.
  • Exceptions: CoP outperforms REPEN on R8, while HLLE outperforms REPEN on News20.The paper attributes these cases to structural outliers and the need for a larger neighborhood size, respectively.

6.5 The Capability of Leveraging Labeled Outliers as Prior Knowledge

REPEN incorporates a small number of labeled outliers as prior knowledge, producing rapid AUC gains while the labeled set remains below 1% of the data.

  • AUC gains: 0.5822 to 0.7707 AUC improvement is achieved on News20 using labeled outliers.News20 is described as the more complex data set.
  • AUC gains: 0.7733 to 0.9160 AUC improvement is achieved on URL when labeled outliers are provided.Similar results are observed on Webspam.
  • Data efficiency: Less than 1% labeled data is used while the proportion of labeled and unlabeled outliers remains very small.The experiment varies the number of labeled outliers from 1 to 80.
  • Data efficiency: Up to 18% AUC improvement on URL is obtained when labeled outliers represent only up to 4.50% of unlabeled outliers.News20 achieves more than 32% AUC improvement when the labeled-to-unlabeled outlier ratio is larger.

6.6 Sensitivity Test w.r.t. the Representation Dimension

REPEN’s AUC is stable across representation dimensions from 10 to 100, although labeled-outlier information can make larger representations more effective.

  • Dimension sensitivity: 10 to 100 representation dimensions yield stable REPEN performance across the eight data sets.The sensitivity experiment evaluates dimensions from 1 through 100.
  • Representation capacity: REPEN can theoretically represent up to O(2^10) concepts when M = 10.The paper uses this capacity argument to explain why 10 dimensions may suffice for many data sets.
  • Low-dimensional cases: M = 1 performs as well as larger representations on R8, News20, and URL without labeled outliers.This can occur when inliers and outliers are separable by one decision boundary.
  • Effect of labeled outliers: With l = 80 labeled outliers, 1-D representations underperform 20-D representations on News20 and URL.The reported 1-D AUC values are 0.7201 and 0.8320, respectively, versus 0.7707 and 0.9160 for 20-D representations.

6.7 Scalability Test

The scalability tests vary data size and dimensionality, measuring total training and testing runtime. REPEN scales linearly with both factors while trading speed against simpler baselines and avoiding HLLE’s quadratic data-size cost.

  • The scaleup experiments vary data size from 1,000 to 125,000 in 10,000 dimensions and vary dimensionality at a fixed data size of 10,000.Runtime includes both training and testing.
  • REPEN has linear time complexity with respect to both data size and dimensionality.This supports the complexity analysis reported in Section 4.5.
  • REPEN is much faster than HLLE because HLLE performs nearest-neighbor searching over the entire data set with quadratic data-size complexity.
  • SRP is the most efficient method because it only requires fast random matrix projection.
  • REPEN runs slower than AE because its representation learning requires more distance computations despite having a similar network architecture.

7 CONCLUSIONS

RAMODO unifies representation learning with random distance-based outlier detection to produce customized low-dimensional representations. REPEN reports more stable detection, effective use of limited prior knowledge, and stable performance with very low-dimensional representations, while broader RAMODO instances remain under development.

  • RAMODO unifies representation learning and outlier detection to produce customized representations for random distance-based detectors.
  • REPEN achieves substantially better and more stable detection performance than four state-of-the-art representation learning competitors.
  • REPEN can leverage a few labeled outliers to improve triplet quality and learn more application-relevant representations, yielding up to 32% AUC improvement.
  • REPEN effectively represents ultrahigh-dimensional data with 20-dimensional representations that remain stable across a wide range of representation dimensions.
  • RAMODO is being extended with other instances that use more sophisticated distance-based outlier scoring for more complex data.
Loading 1806.04808v1…