Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies

Uthsav Chitra, Kimberly Ding, Jasper C. H. Lee, Benjamin J. Raphael

Introduction

Maximum Likelihood Estimation (MLE) is the standard tool for identifying structured anomalies in datasets, but it often "over-reports" the size of an anomaly, leading to high false-positive rates. This paper proves that MLE bias is fundamentally tied to the complexity of the anomaly's structure. To resolve this, the authors propose a new, asymptotically unbiased estimator based on Gaussian Mixture Models (GMMs) that outperforms MLE in both simulations and real-world datasets, such as disease outbreaks and traffic patterns.

The Problem: MLE Bias in Structured Anomalies

In anomaly estimation, the goal is to find a subset of data points that differ from the "normal" background. Usually, we assume these anomalies have a specific structure—for example, a contiguous time interval in a sequence, a submatrix, or a connected subgraph in a social network.

Examples of structured anomaly families including intervals, submatrices, and connected subgraphs.

The standard approach is to use the Maximum Likelihood Estimator (MLE). However, researchers recently noticed that for complex structures (like networks), the MLE is often biased. It tends to include many normal points in its "anomalous" set, making the anomaly look much larger than it actually is. This paper seeks to answer why the MLE is biased for some structures but not others, and how we can build a better estimator that avoids this "bloating" effect.

Methods

The authors analyze the problem using the Anomalous Subset Distribution (ASD), where most data points come from a standard normal distribution, but a hidden subset (the anomaly) comes from a distribution with a higher mean.

The Theoretical Breakthrough

The authors link bias to the "size" or complexity of the anomaly family. They prove that if the number of possible sets containing the true anomaly grows sub-exponentially with the total number of data points (like simple time intervals), the MLE is unbiased. However, if that number grows exponentially (like connected subgraphs in a dense network), the MLE becomes biased.

The New Estimator: NetMix

To fix this, they propose a GMM-based approach:

  1. GMM Fitting: They treat the data as a two-component Gaussian Mixture Model and use the Expectation-Maximization (EM) algorithm to estimate the proportion of anomalous points ($\alpha$) and their mean ($\mu$).
  2. Responsibility Maximization: Instead of the standard MLE objective, they look for a set in the anomaly family that maximizes the sum of "responsibilities" (the probability that a point belongs to the anomalous component) while constraining the set's size to match the estimated $\alpha$.

Datasets

The paper evaluates the new estimator on several benchmarks:

  • Synthetic Families: Intervals, Submatrices, Connected Subgraphs, and Unstructured (power set) families.
  • Lollipop Graphs: A specialized synthetic graph used to demonstrate the transition from sub-exponential to exponential complexity.
  • NEast USA Benchmark: A dataset of 244 counties in the Northeastern US used to simulate disease outbreaks.
  • LA Highway Traffic: Data from 1,868 sensors in Los Angeles County.
  • Manhattan Breast Cancer: Census block data used to identify clusters of high cancer incidence.

Key Insights

  • The Complexity Threshold: The core insight is that bias isn't a flaw of the MLE algorithm itself, but a property of the search space. When there are too many ways to "fit" an anomaly into a structure, the MLE inevitably picks up random noise that happens to look slightly anomalous, causing the estimated set to grow.
  • GMMs as a Grounding Mechanism: While the ASD (fixed number of anomalous points) and GMM (probabilistic membership) are different models, they converge as the dataset grows. The GMM parameters can be estimated without bias, providing a reliable "anchor" for the true size of the anomaly.
  • Linearity Wins: The GMM-based objective is linear (summing responsibilities), whereas the MLE objective is non-linear. This makes the GMM estimator computationally more efficient for many complex structures using techniques like Integer Linear Programming (ILP).

Key Results

The proposed GMM estimator successfully mitigates the bloating effect seen in standard MLE approaches.

Comparison of bias between MLE (A, B) and the proposed GMM estimator (C, D) across different structures.
  • Unbiased Performance: As shown in the evaluations, the GMM estimator remained asymptotically unbiased across all tested structures, even when the MLE showed significant bias (e.g., in connected subgraphs and unstructured families).
  • Disease Outbreak Accuracy: In the NEast simulation, the MLE was highly "bloated," identifying 59 false positives (F-measure 0.24). The GMM estimator identified the anomaly with only 1 false positive (F-measure 0.73).
  • Real-World Intensity: On traffic and cancer data, the GMM estimator consistently found smaller, more "intense" clusters. For example, in the Manhattan cancer data, it found a cluster with a 20% higher incidence rate than the one found by the standard graph scan statistic (MLE).

Limitations and Future Work

  • Signal Strength: The theoretical guarantees for the GMM estimator require a "sufficiently large" mean difference ($\mu$). If the anomaly is too subtle, even this estimator may struggle.
  • Single Anomaly Assumption: The current work focuses on finding one primary anomaly. The authors suggest that future work could extend this to multiple anomalies by using $k$-component GMMs.
  • Distributional Variety: While the paper focuses on Gaussian data, many real-world anomalies are count-based (Poisson). The authors provided a brief adaptation for Poisson data, but a more rigorous theoretical treatment for non-Gaussian distributions remains an open path.

Summary updated

Abstract

Anomaly estimation, or the problem of finding a subset of a dataset that differs from the rest of the dataset, is a classic problem in machine learning and data mining. In both theoretical work and...
BibTeX
@inproceedings{chitra2021quantifying,
  author = {Uthsav Chitra and Kimberly Ding and Jasper C. H. Lee and Benjamin J. Raphael},
  title = {{Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=6_AkiMc7Fy},
}

Loading related content...

Figure