Anomaly Detection for High Cardinality Discrete Spaces using Noise-contrastive Estimation

Abstract

Most traditional unsupervised algorithms for anomaly detection do not work for discrete data, specially when the data dimensions have a very high cardinality. An example of such a multi-dimensional, very high-cardinality discrete data set is CloudTrail event logs, where some of the discrete dimensions, such as the account id, are of the order ~1M. Preliminary experiments using Noise-contrastive Estimation (NCE) based anomaly detection for CloudTrail events suggest that NCE is a good technique for anomaly detection in high-cardinality discrete spaces. The proposed technique models the probability mass function over the discrete space via a deep neural network and uses NCE to estimate the probability mass function; events that have low probabilities are flagged as anomalies. In the internship project, we (1) develop a generalized NCE based deep learning algorithms for anomaly detection over discrete data domains; (2) experimentally validate the performance of the deep learning model; and (3) compare its performance to the current state-of-the-art anomaly detection algorithms.