The hunting of the bump: on maximizing statistical discrepancy

Deepak Agarwal, Jeff M. Phillips, Suresh Venkatasubramanian

TL;DR

This paper introduces a novel algorithmic framework for efficiently finding "anomalous" regions in data by maximizing statistical discrepancy functions. They achieve this by reducing the complex problem of maximizing any convex discrepancy function to maximizing a simpler linear discrepancy function, leading to significant speedups over previous methods for various common data distributions.

What Problem Does This Paper Address?

In fields like biosurveillance and environmental monitoring, detecting anomalies is crucial. A common challenge is distinguishing true anomalies from patterns that are simply inherent to the baseline data distribution. Simply finding clusters in observed data might lead to false positives if those clusters are also present in the baseline. To address this, researchers use "discrepancy functions" to quantify how much a specific region of data deviates from the expected baseline. An anomalous region is then defined as one exhibiting high discrepancy. The core problem is efficiently finding the region that maximizes this discrepancy, especially when dealing with complex, high-dimensional data and various statistical distributions.

Methods

The paper's main contribution is a structural theorem that connects statistical discrepancy to combinatorial discrepancy. Essentially, they show that maximizing any convex discrepancy function over a class of shapes (like axis-parallel rectangles) can be achieved by maximizing a linear discrepancy function over the same shapes. This is a powerful reduction because efficient algorithms already exist for maximizing linear discrepancy functions, particularly for axis-parallel rectangles.

They then extend existing algorithms for combinatorial discrepancy (which is a type of linear discrepancy) to handle general linear discrepancy functions. This allows them to approximate the maximum discrepancy for any convex discrepancy function. Furthermore, they derive general discrepancy functions for data generated from one-parameter exponential families, which encompass many common distributions like Poisson, Bernoulli, Gaussian, and Gamma. This allows their algorithms to be applied broadly.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical guarantees rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Convex to Linear" Reduction: The core insight is that maximizing a complex convex discrepancy function can be simplified to maximizing a linear one. This is a significant theoretical breakthrough that unlocks efficient algorithmic solutions.
  • Generalizing Scan Statistics: By framing discrepancy functions within the context of one-parameter exponential families, the authors provide a unified approach to problems like the Kulldorff scan statistic (Poisson), Gaussian scan statistic, Bernoulli scan statistic, and Gamma scan statistic.
  • Approximation Guarantees: The paper provides provable additive and relative approximation guarantees for their algorithms, meaning they can find a region whose discrepancy is close to the true maximum, within a controlled error bound.
  • Bridging Theory and Practice: The work connects theoretical concepts in discrepancy measures with practical applications in anomaly detection, offering algorithms that are both theoretically sound and computationally efficient.

Key Results

The paper presents algorithms with significantly improved worst-case running times compared to previous exact methods. For instance:

  • For the Kulldorff scan statistic (Poisson distribution), they achieve an additive $\epsilon$-approximation in $O(n^2 \log^2 n)$ time, a substantial improvement over the $O(n^4)$ exact algorithms.
  • Similar improvements are shown for Gaussian, Bernoulli, and Gamma distributions.
  • For prospective discrepancy (considering time windows), their algorithms run in $O(n^3 \log^2 n)$ time.
  • The paper also derives novel discrepancy functions for Gaussian data, which they note may be of independent interest.

Limitations and Future Work

  • Approximation vs. Exactness: The algorithms provide approximations, not exact solutions. While the approximation guarantees are strong, there might be scenarios where an exact solution is strictly required.
  • Dimensionality: The algorithms are primarily presented for 2D (axis-parallel rectangles). While they mention extensions to higher dimensions, the complexity increases significantly ($O(n^{2d-2} \log n)$ for linear discrepancy).
  • Specific Distributions: While they cover a broad class of distributions (one-parameter exponential families), there might be other anomaly detection scenarios involving different distributional assumptions.
  • Future Work: The authors suggest that their framework can be extended to other shape classes beyond axis-parallel rectangles and to higher dimensions. They also hint at the potential for further optimization and practical implementation of their algorithms.

Summary updated

Abstract

Anomaly detection has important applications in biosurveilance and environmental monitoring. When comparing measured data to data drawn from a baseline distribution, merely, finding clusters in the measured data may not actually represent true anomalies. These clusters may likely be the clusters of the baseline distribution. Hence, a discrepancy function is often used to examine how different measured data is to baseline data within a region. An anomalous region is thus defined to be one with high discrepancy.In this paper, we present algorithms for maximizing statistical discrepancy functions over the space of axis-parallel rectangles. We give provable approximation guarantees, both additive and relative, and our methods apply to any convex discrepancy function. Our algorithms work by connecting statistical discrepancy to combinatorial discrepancy; roughly speaking, we show that in order to maximize a convex discrepancy function over a class of shapes, one needs only maximize a linear discrepancy function over the same set of shapes.We derive general discrepancy functions for data generated from a one- parameter exponential family. This generalizes the widely-used Kulldorff scan statistic for data from a Poisson distribution. We present an algorithm running in O(1/ε n2 log2n) that computes the maximum discrepancy rectangle to within additive error ε, for the Kulldorff scan statistic. Similar results hold for relative error and for discrepancy functions for data coming from Gaussian, Bernoulli, and gamma distributions. Prior to our work, the best known algorithms were exact and ran in time O(n4).
BibTeX
@inproceedings{agarwal2006hunting,
  author = {Deepak Agarwal and Jeff M. Phillips and Suresh Venkatasubramanian},
  title = {{The hunting of the bump: on maximizing statistical discrepancy}},
  booktitle = {SODA},
  year = {2006},
  url = {https://openreview.net/forum?id=W5iNypNPq},
}
Figure