PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Regression Models for Scan Statistics

Gazi Abdur Rakib, Tristan Ashton, Ryan A. Loomis, Brian S. Mason, Eric J. Murphy, Ci Xue, Jeff M. Phillips

arXiv:2608.22201v1stat.MEcs.LG

TL;DR

The paper addresses interval-anomaly detection when real-valued signals have non-stationary backgrounds that constant models fit poorly. It introduces regression-based scan statistics and efficient algorithms, with NWKR providing a nonparametric GLR analog. The methods are presented as effective for synthetic anomalies and radio-telescope platforming, while NWKR lacks the maximum-likelihood and Neyman–Pearson guarantees available for the polynomial model.

  • Problem

    Interval-anomaly scan statistics need to model smoothly varying, non-stationary backgrounds rather than relying only on constant fits.

  • Method

    The paper fits polynomial or kernel regression models within a scan-statistic framework and develops width-bounded efficient algorithms, including NWKR-based scoring.

  • Results

    The proposed models and algorithms are demonstrated on synthetic anomalies and radio-telescope platforming anomalies, with NWKR highlighted as especially effective.

  • Takeaways & Limitations

    Regression-based scan statistics extend interval-anomaly detection to smoothly varying signals and support a real radio-telescope quality-control application.

  • Takeaways & Limitations

    NWKR is nonparametric, so its score is not a maximum-likelihood estimate and does not inherit Neyman–Pearson optimality; KRR remains computationally slow.

Abstract

from arXiv · show

We introduce a new class of regression models for scan statistics on real-valued signals. These allow for improved fitting of non-stationary signals to contrast with the interval anomalies identified by the scan statistics. Our models can represent generalized likelihood ratio statistics. While these methods naively require $O(n^4)$ for a length $n$ signal, we provide algorithmic improvements which lead to linear time algorithms (with assumptions on max interval width). Our methods, especially ones based on Nadaraya-Watson kernel regression, are demonstrated as especially effective in detecting both synthetically planted anomalies, and for identifying a real ``platforming'' issue in interferometric astronomy.

1 Introduction

The paper develops regression-based scan statistics for anomalous intervals in real-valued signals, extending beyond constant background models. It also provides efficient algorithms and evaluates the models on synthetic data and radio-telescope platforming anomalies.

  • Contributions: The paper formulates scan statistics that fit polynomial or kernel-based regression models to the background while retaining normal-noise assumptions.These models extend constant-value background models for interval-anomaly detection.
  • Contributions: The polynomial regression anomaly score reduces to a log-likelihood ratio and inherits Neyman–Pearson optimality for the associated detection problem.This applies under the assumed generative and noise models.
  • Contributions: The Nadaraya-Watson model provides a generalized-likelihood-ratio analog for detecting local departures with controlled dependence between consecutive signal values.The dependence is governed by the kernel bandwidth, within a fully nonparametric setting.
  • Contributions: Restricting candidate intervals to width at most w yields scan algorithms running in O(nwd^3) for degree-d polynomials and O(nwr) for NWKR.Here r is the width of a truncated kernel; direct implementations would take O(n^4).
  • Evaluation: The methods are evaluated on synthetic and real-world data, including radio-telescope bandpass platforming anomalies.The NWKR variant is highlighted as especially efficient and effective.

2 Basics of Scan Statistic Model via Regression Families

The scan-statistic framework compares a global regression fit with separate inside/outside fits for every candidate interval. Different regression families preserve this scoring structure, while the resulting statistical interpretation and computational costs depend on the family.

  • Scan-statistic framework: For each candidate interval, the null fits one function to the full signal, while the alternative fits separate functions inside and outside the interval.The interval is anomalous when the split fit improves substantially over the global fit.
  • Scan-statistic framework: The Gaussian log-likelihood ratio is monotone in the reduction from the global SSE to the combined inside and outside SSEs.The normalized score lies in [0, 1], approaching 0 without improvement and tending toward 1 when the split fit is much better.
  • Regression families: The framework supports constant, fixed-degree polynomial, kernel ridge, and Nadaraya–Watson kernel regression families without changing the score derivation.The family determines which functions are optimized under the null and alternative hypotheses.
  • Regression families: Polynomial regression allows gentle global drift, whereas Nadaraya–Watson regression is fully nonparametric and has no parameters to optimize.The polynomial model uses coefficients obtained by unregularized least squares for small degree; NWKR uses localized kernel weighting.
  • Statistical interpretation: The scan maximum is an exact generalized likelihood ratio statistic for fixed function family and variance, supporting a principled omnibus test for any anomalous region.The Neyman–Pearson optimality statement applies to the polynomial score under its specified model.
  • Statistical interpretation: NWKR lacks a maximum-likelihood interpretation, so Neyman–Pearson optimality does not apply to its corresponding score.It remains a natural generalized-likelihood-ratio analog for the nonparametric smoother.

3 Scanning Algorithms

The scanning algorithms fit regression models globally and separately inside and outside each candidate interval, then maximize an anomaly score. Restricting interval width and caching or truncating computations reduces runtime substantially across model families.

  • Basic algorithm: The algorithm fits one global model, scans candidate intervals, fits separate inside and outside models, and returns the interval maximizing S(x; Ia,b).The global fit supplies SRA, while separate fits supply SRI and SRO for each interval.
  • Basic algorithm: O(n^3) is the direct lower-bound runtime because there can be O(n^2) intervals and each score sums over n terms.Kernel models can be slower when evaluating or fitting each candidate requires additional linear-time work.
  • Regression models: Nadaraya-Watson kernel regression uses a weighted neighborhood average with bandwidth r, requiring no parameter optimization.The kernel determines the neighborhood and its degree of local smoothing.
  • Runtime improvements: Precomputation reduces constant-model updates to O(1) and enables an overall O(nw) runtime for F0.The method maintains interval sums and recombines inside and outside terms incrementally.
  • Runtime improvements: For degree-d polynomial regression, updating a score costs O(d^3 + 1), yielding total runtime O(nw(d^3 + 1)).The bound assumes candidate intervals have maximum width w.
  • Runtime improvements: For NWKR, score updates cost O(n), giving O(n^2w) overall, while truncated kernels reduce the score computation to O(nwr).Truncation evaluates only a local neighborhood of radius O(r).

4 Evaluation

The evaluation tests regression scan models on synthetic polynomial and AR(2) signals, comparing anomaly localization across signal-to-noise ratios and widths, alongside runtime scaling and baseline comparisons.

  • Recovering and Localizing Planted Anomalies: The experiments use synthetic polynomial and AR(2) signals, with planted anomalies evaluated by localization score while varying signal-to-noise ratio and anomaly width.Polynomial results are shown in Figure 2 and AR(2) results in Figure 3; experiments use 1,000 generated signals with anomalies of length 50 channels.
  • Recovering and Localizing Planted Anomalies: At low signal-to-noise ratios, NWKR retains near-perfect anomaly localization while mean and polynomial models lose localization ability.At 5×σ, all methods reach localization score 1; as SNR decreases, NWKR remains near-perfect.
  • Recovering and Localizing Planted Anomalies: Change-point and discord-mining baselines perform poorly for small SNR and widths, while LRT, KernelCPD, and BOCDP approach NWKR performance in easier regimes.CPDF variants and TSBAD M2N2 improve in easier regimes but remain less competitive overall than the NWKR family.
  • Runtime Scaling: The optimized regression scan algorithms scale linearly with signal length n and interval width w, while FNWKR also scales linearly with truncation range r.For n = 1000, optimized FNWKR takes about 70 ms and is almost an order of magnitude faster than Fd models; naive FNWKR is nearly 1000× slower.

5 Application: Radio Telescope Spectra Calibration Anomalies

The ALMA application targets platforming anomalies in calibration spectra, where manual review misses about half of cases and existing automated heuristics remain insufficient. The proposed methods, especially NWKR variants, substantially improve interval localization and false-negative performance on 231 confirmed examples.

  • Motivation: About 50% of platforming anomalies were missed by manual inspection, making the process non-scalable for higher-throughput telescopes.Missed anomalies can lead to corrupted data cubes.
  • Existing pipeline: The in-production detector uses masked subbands, local noise statistics, and five threshold tests for phase and amplitude anomalies.It is restricted to baseline-correlator FDM data and excludes atmospheric absorption regions and low-transmission subbands.
  • Dataset: N = 38,881 bandpass calibration solutions were collected, yielding 231 domain-expert-confirmed platforming cases after filtering and trimming.The dataset contains one row per polarization, spectral window, and antenna, with signals having atmospheric interference or fewer than n = 128 channels removed.
  • Localization: At IoU threshold 0.75, F_NWKR Gaussian achieves F1 above 0.95 and outperforms the mean, polynomial, and other baseline methods.The comparison evaluates precision, recall, and F1 across variable IoU thresholds.
  • Score filtering: At score threshold τS = 0.3, both F_NWKR models achieve recall 1.0, with Gaussian precision above 0.54.Fixed-side NWKR variants obtain higher precision, 0.70 and 0.59, but false-negative rates of 0.29 and 0.30.
  • Operational comparison: The proposed method has false-negative rate 0, compared with 0.49 for data reducers and 0.58 for the heuristic, while its false-positive rate is 0.0049.The alternative false-positive rates are 0.0053 and 0.0013, respectively.

6 Discussion

The paper extends scan statistics to smoothly varying one-dimensional signals by fitting regression backgrounds and provides efficient algorithms, with NWKR offering a particularly effective model. Its main scope boundaries are smooth-background assumptions and runtime dependence on the maximum interval width.

  • Discussion: The proposed scan statistics fit polynomial or NWKR regression models to smoothly varying backgrounds instead of restricting the background to a constant value.The models retain Gaussian-noise assumptions and can represent generalized likelihood ratio statistics.
  • Limitations: If w is unbounded or scales as 0.2 × n, NWKR runtime becomes quadratic in n: O(nwr) = O(n^2r).Thus linear scaling in signal length depends on controlling the maximum window width.
  • Limitations: The models assume a smoothly varying background, so sharp background changes may be confused with anomalies.This is a scope boundary for both the polynomial and NWKR families.

A.1 Benchmarking against Other Methods

The benchmark compares NWKR scans with classical scan statistics, change-point methods, likelihood-based methods, discord mining, and neural detectors after adapting outputs to scoreable intervals. These baselines differ substantially in their modeling assumptions and interval-construction procedures.

  • Comparison protocol: All baselines are compared using the same anomaly score, 1 − (SSEin + SSEout)/SSEall, with a constant-mean reference.This makes scores directly comparable across methods.
  • Change-point baselines: KernelCPD fits a piecewise-constant ℓ2 model with two breakpoints, producing three segments whose highest-scoring segment is returned.Segments wider than w are trimmed around their centers.
  • Change-point baselines: BOCPD recursively updates a posterior over run length using a Normal-Gamma prior and constant hazard, with consecutive run-length drops defining anomaly boundaries.The method is adapted to synthetic interval detection by pairing two changepoints.
  • Likelihood baseline: Gaussian LRT maximizes a two-segment versus one-segment likelihood ratio over windows up to w and runs in O(nw) time via prefix sums.It is the theoretically optimal parametric baseline for rectangular step detection under Gaussian noise.
  • Other baselines: CAPA uses a penalized Gaussian negative-log-likelihood dynamic program, while STUMPY constructs intervals from deep minima of a corrected arc curve.CAPA estimates background location and scale using the median and scaled MAD.
  • Other baselines: CPD NWKR detrends signals with the same truncated NWKR smoother as the proposed scan before applying a two-breakpoint dynamic program to residuals.Neural detectors instead produce per-timestamp scores that are converted into intervals by maximizing contiguous excess score mass.

B Synthetic Dataset Construction

The synthetic benchmarks generate smooth heterogeneous one-dimensional signals with controlled anomalies, noise, and scan-window configurations. This design isolates localization behavior across anomaly width, signal-to-noise contrast, and window choice.

  • Signal construction: Synthetic signals combine slowly varying quadratic trends with low-frequency correlated or AR(2) structure and white noise.The construction targets realistic spectral behavior while retaining controlled background variation.
  • Benchmark design: Signals are grouped by (n, w, N), where n is signal length, w is the scan-window cap, and N is the number of signals per group.Window-sensitivity experiments vary w across a length of 500 while keeping N = 1000.
  • Benchmark design: Anomaly strength is parameterized relative to empirical signal standard deviation to control signal-to-noise ratio.This enables direct comparison across varying anomaly contrasts.
  • Benchmark design: The dataset construction varies anomaly width, anomaly amplitude relative to noise, and scan-window configuration.These factors support controlled analysis of localization behavior.

B.1 Localization Results on Synthetic Data

Synthetic localization performance depends strongly on anomaly width and signal-to-noise ratio. Gaussian NWKR is especially effective at moderate-to-high amplitudes and moderate or large scan-window caps, while narrow windows and weak anomalies limit localization.

  • Scan-window cap: For w ≤3 at n = 100, localization remains modest, and polynomial baselines often outperform NWKR because the scan window under-covers the anomaly.The kernel smoothers cannot capture the full anomalous support when the search window is too narrow.
  • Scan-window cap: For moderate caps, Gaussian NWKR achieves perfect or near-perfect localization with mean Loc ≈1.0, outperforming polynomial baselines.Examples include w ∈{5, 6} for n = 100 and w ∈{10, 12} for n = 200; Laplace NWKR typically matches accuracy at higher computational cost.
  • Scan-window cap: For w ≥20 at n = 100, Gaussian and Laplace NWKR remain stable and achieve perfect localization while simple baselines deteriorate.The result indicates greater robustness to over-large search breadth for kernel-based scanning than for polynomial or mean models.
  • Anomaly amplitude: At 1σ, localization scores are low across all methods, reflecting intrinsic detectability limits rather than model deficiencies.
  • Anomaly amplitude: At 2σ, Gaussian NWKR achieves near-perfect localization even for narrow anomalies, while polynomial methods improve more gradually.At amplitudes ≥4σ, all methods approach perfect localization, with NWKR typically reaching that regime at lower thresholds.

C.1 Experimental Results

The score-threshold analysis finds FNWKR effective across a wide range of thresholds when IoU requirements vary. This robustness makes threshold selection depend mainly on whether precision or recall is preferred.

  • Score-threshold ablation: Table 5 evaluates F1 while fixing τS = 0.3 and varying τI from 0.5 to 1 in increments of 0.05.
  • Score-threshold ablation: FNWKR is the best-performing choice across the tested score-threshold analysis and remains effective over a wide range of τS values.The authors therefore do not perform a detailed train/test split evaluation for threshold selection.

C.2 Detection with Score and Interval Overlap on Balanced Subset

On the balanced subset, FNWKR combines high anomaly detection and interval-overlap performance across IoU thresholds. Its advantage is especially clear against efficient and non-paper baselines, although runtime trade-offs remain.

  • Balanced subset: Both FNWKR models achieve precision above 0.99 and accuracy and F1 above 0.95 on the balanced N = 500 subset.The Gaussian variant exceeds 0.98 for both accuracy and F1, while no other approach exceeds F1 0.72 or accuracy 0.75.
  • Runtime: CAPA is much faster but has F1 around 0.1, while LRT is about five times faster than FNWKR and has worse performance.FNWKR is slower than these baselines but faster than the other compared methods.
  • Balanced subset: FNWKR Gaussian achieves F1 of at least 0.99 across IoU thresholds at its best score-threshold operating points.FNWKR Laplace is next best; LRT trails Gaussian FNWKR by at least 0.3 F1 and approaches 0.5 at IoU 0.9.

C.3 Detection with Score and Interval Overlap on Full ALMA

On the highly imbalanced full ALMA dataset, FNWKR Gaussian provides the strongest reported balance of precision, recall, and interval localization. Its runtime is competitive, but expert interval labels and the practical use case constrain how interval misses should be interpreted.

  • Full ALMA dataset: On N = 38,881 ALMA rows with 231 positives, FNWKR Gaussian achieves precision 0.544 and recall 0.995 at τI = 0.75 and τS = 0.3.It produces 191 false positives among 38,650 negative signals and misses 3 of 231 true anomalies.
  • Baseline comparison: NWKR-CPD reaches recall approximately 0.45, while deep detectors reach recall 0.40–0.41 at precision below 0.04.
  • Interval overlap: Fixed-left variants fall from recall 0.710 and 0.701 at τI = 0 to 0.009 at τI = 0.75 because their anchored left boundary rarely matches anomaly onset.
  • Runtime: FNWKR Gaussian has median runtime 45 ms per signal, compared with 95 ms for F0 Mean and over 2,214 ms for F1.The measurements used parallelization and may be noisy rather than ideal-runtime estimates.
  • Limitations: Even at τS = 0.1, FNWKR Gaussian does not identify all anomalies because some discrepancies arise from interval mismatch or differing expert markings.The paper notes that platforming signals are normally discarded, so pinpointing the interval is not central to the standard procedure.

D ALMA Examples with Differences in Methods

The examples compare regression-based scan statistics on ALMA and solar-radiation signals, emphasizing anomaly scoring and localization. NWKR-based methods assign higher scores to true-positive rows and localize interval anomalies in smoothly varying signals.

  • ALMA Examples with Differences in Methods: NWKR-based methods assign higher scores to true-positive rows than competing methods in the illustrated spectra.The comparison highlights stronger agreement with the underlying target structure while preserving localization.
  • ALMA Examples with Differences in Methods: NWKR preserves both anomaly localization and scoring, whereas alternative methods more often produce lower scores or misplaced windows.
  • ALMA Examples with Differences in Methods: NWKR Scan Statistics distinguish high-scoring ALMA rows from low-scoring rows that are not platforming anomalies.Low-scoring cases can still yield an anomalous region because of random variation, but the region differs little from the global fit.
  • ALMA Examples with Differences in Methods: Solar-radiation curves provide smoothly varying non-stationary signals in which shadows from clouds, obstructions, or glitches create interval anomalies.
  • ALMA Examples with Differences in Methods: FNWKR localizes the anomaly almost perfectly in five representative solar-radiation examples, outperforming the other methods.The examples are shown in Figures 18 to 22.
Loading 2608.22201v1…