When lookout sees crackle: Anomaly detection via kernel density estimation

1. Problem Statement

The paper addresses the limitations of the original Lookout algorithm (Kandanaarachchi & Hyndman, 2022) for anomaly detection. While the original algorithm successfully used Kernel Density Estimation (KDE) combined with Persistent Homology (specifically Rips death diameters) to identify outliers, it suffered from several theoretical and practical weaknesses:

• Inconsistent Bandwidth Selection: The original method selected bandwidth based on the largest gap in Rips death diameters ($d^*$). The authors prove theoretically that this choice does not guarantee a consistent KDE estimator, particularly for distributions with heavy tails (e.g., power-law distributions), where the bandwidth may fail to converge to zero.
• Lack of Robustness: The original algorithm relied on min-max scaling, which is highly sensitive to outliers, and used a diagonal bandwidth matrix that ignored correlations between variables.
• Unconstrained Distribution Fitting: The fitting of the Generalized Pareto Distribution (GPD) to the "surprisals" (negative log-density) did not account for the theoretical bounds of KDE estimates, leading to potential instability in shape parameter estimation.

2. Methodology

The authors propose Lookout v2, a modified algorithm grounded in rigorous theoretical guarantees derived from Extreme Value Theory (EVT) and Topological Data Analysis (TDA). The methodology involves three core modifications:

A. Robust Multivariate Scaling

Instead of min-max scaling, the new algorithm uses the Orthogonalized Gnanadesikan-Kettenring (OGK) estimator.

• Process: The data is centered using medians and scaled/rotated using the Cholesky decomposition of the robust covariance matrix.
• Goal: This transforms the data such that the covariance matrix is approximately the identity matrix. This removes variable correlations and ensures robustness against outliers, leading to more efficient KDEs.

B. Theoretical Bandwidth Selection via Quantiles

The authors analyze the asymptotic behavior of Rips death diameters ($d_n$).

• Theoretical Finding: They prove that for heavy-tailed distributions, the largest gap ($d^*$) used in the original algorithm does not necessarily converge to zero, violating the conditions for a consistent KDE.
• Solution: The new algorithm selects the bandwidth ($h_n$) based on an upper quantile of the Rips death diameters, specifically $d_{\gamma(n-1)}$ where $\gamma \in (0, 1)$ (e.g., the 98th percentile).
• Guarantee: Theorem 14 proves that $d_{\gamma(n-1)}$ is an admissible bandwidth (converging to 0 while $n h_n^{m/2} \to \infty$) for a wide class of distributions, including those with fat tails, ensuring the consistency of the KDE.

C. Constrained GPD Fitting

The algorithm fits a Generalized Pareto Distribution (GPD) to the negative logarithms of the KDE values (surprisals).

• Constraint: Since KDE estimates are bounded above, the negative log-density is bounded below. According to EVT, the limiting distribution of these extremes for bounded variables is a Weibull distribution, which corresponds to a Generalized Extreme Value (GEV) distribution with a negative shape parameter ($\xi < 0$).
• Action: The GPD fitting step constrains the shape parameter $\xi$ to be non-positive ($\xi \leq 0$), improving the stability and accuracy of the tail estimation.

3. Key Contributions

1. Theoretical Consistency: The paper provides the first theoretical proof that the original Lookout bandwidth choice is inconsistent for heavy-tailed distributions and establishes that a quantile-based bandwidth choice yields a consistent KDE estimator under mild conditions.
2. Algorithmic Improvements: The introduction of robust scaling and constrained GPD fitting significantly enhances the algorithm's stability and performance across diverse data types.
3. Mathematical Bounds: The authors derive upper and lower bounds for quantile death times ($d_{\gamma(n-1)}$), showing they are of order $O(n^{-1/m})$, which justifies the bandwidth selection rate.
4. Implementation: The updated algorithm is implemented in the lookout R package.

4. Results

The authors conducted extensive experiments comparing Lookout v2 against the original Lookout and other state-of-the-art methods (HDoutliers, Stray, KDEOS, RDOS).

• Synthetic Data Experiments:
  • Gamma Distributions: Lookout v2 outperformed the original version, particularly when anomalies were subtle (low separation).
  • Normal Distributions: Both versions performed similarly when anomalies were well-separated, but v2 showed superior True Positive Rates and lower False Negative Rates when anomalies were close to the main cluster (boundary cases).
  • High Dimensions: In a 20-dimensional unit cube experiment, v2 successfully identified anomalies that were indistinguishable in 2D projections, demonstrating robustness to the "curse of dimensionality" when combined with dimension reduction.
• Real-World Data:
  • Old Faithful Geyser: v2 identified more low-density anomalies and fewer false positives near the main cluster compared to v1.
  • Wine Reviews: v2 provided a "substantial improvement," identifying fewer spurious anomalies at the extremes and focusing on genuine low-density regions.
• Comparison with Other Methods: Lookout v2 consistently achieved competitive or superior performance in terms of AUC, F-measure, and G-mean compared to EVT-based and KDE-based competitors.

5. Significance

This paper represents a significant theoretical and practical advancement in anomaly detection:

• Bridging TDA and Statistics: It rigorously connects Persistent Homology (Topological Data Analysis) with Kernel Density Estimation, moving from heuristic bandwidth selection to mathematically guaranteed consistency.
• Robustness: By addressing the sensitivity to outliers in scaling and bandwidth selection, the algorithm is more reliable for real-world data which often contains noise and heavy tails.
• Probabilistic Framework: The method provides principled probabilistic anomaly scores based on Extreme Value Theory, allowing for interpretable threshold selection rather than arbitrary cutoffs.
• Applicability: The algorithm is versatile, suitable for continuous multivariate data up to moderate dimensions (~20), and can be adapted for image or functional data via feature extraction.

Limitations: The computational complexity is dominated by the calculation of 0-dimensional Vietoris-Rips persistent homology ($O(n \log n)$), which may be prohibitive for massive datasets without subsampling. Additionally, like all KDE methods, it faces challenges in very high-dimensional spaces without prior dimension reduction.