Source-linked AI summary
Sequential multi-sensor change-point detection
Yao Xie, David Siegmund
TL;DR
The paper studies sequential detection of changes affecting an unknown subset of parallel sensors without spatial structure. It proposes a mixture of sensor-specific GLR statistics using an assumed affected fraction p0, derives ARL and EDD approximations, and finds reasonable approximation accuracy and robustness to fraction misspecification, while noting variable EDD-approximation accuracy.
Problem
Sequential detection must identify a change in an unknown, relatively small subset of parallel sensors while suppressing unaffected-sensor noise and controlling false alarms.
Method
The procedure computes sensor-specific GLR statistics, combines them through a mixture model parameterized by p0, and uses positive-part thresholding to focus on apparently affected streams.
Results
The ARL approximation is reasonably accurate even for N = 1 or 2 in numerical experiments, while EDD-approximation accuracy is variable.
Takeaways & Limitations
The procedure is fairly robust to discrepancies between actual and hypothesized affected fractions, and parallel procedures using multiple hypothesized fractions are suggested.
Takeaways & Limitations
EDD approximations can have quite variable accuracy, particularly because their derivation relies on asymptotic linearization and remainder approximations.
Abstract
from arXiv · showhide
We develop a mixture procedure to monitor parallel streams of data for a change-point that affects only a subset of them, without assuming a spatial structure relating the data streams to one another. Observations are assumed initially to be independent standard normal random variables. After a change-point the observations in a subset of the streams of data have nonzero mean values. The subset and the post-change means are unknown. The procedure we study uses stream specific generalized likelihood ratio statistics, which are combined to form an overall detection statistic in a mixture model that hypothesizes an assumed fraction $p_0$ of affected data streams. An analytic expression is obtained for the average run length (ARL) when there is no change and is shown by simulations to be very accurate. Similarly, an approximation for the expected detection delay (EDD) after a change-point is also obtained. Numerical examples are given to compare the suggested procedure to other procedures for unstructured problems and in one case where the problem is assumed to have a well-defined geometric structure. Finally we discuss sensitivity of the procedure to the assumed value of $p_0$ and suggest a generalization.
1. Introduction.
The paper addresses sequential detection when an unknown, relatively small subset of parallel sensors changes, where unaffected streams can add noise and delay detection. It proposes a mixture procedure using local GLR statistics and an assumed affected fraction, with ARL and EDD approximations evaluated numerically.
- Motivation: The problem is to detect a change affecting an unknown subset of parallel data streams quickly while keeping false alarms rare.The change-point, affected subset, subset size, and change magnitudes are unknown; ARL measures the expected time to a false alarm.
- Motivation: When relatively few sensors are affected, detection should suppress noise from unaffected sensors rather than combine all streams indiscriminately.Existing procedures can include unaffected-sensor noise in the statistic, potentially causing long detection delays.
- Contribution: The proposed mixture procedure handles an unknown affected subset and incompletely specified post-change distributions without assuming spatial structure among streams.It hypothesizes a fraction p0 of affected sensors when combining stream-specific statistics.
- Contribution: The procedure computes sensor-specific GLR statistics, combines them through a mixture model, and compares their sum with a detection threshold.The mixture soft-thresholds local statistics according to the hypothesized affected fraction p0.
- Evaluation: The paper derives ARL and EDD approximations and evaluates their accuracy through numerical comparisons with simulations.It also compares the proposed procedure with alternatives for unstructured problems and considers a structured setting.
2. Assumptions and formulation.
The formulation models independent normal sensor observations with unit variance, allowing a change at an unknown time in an unknown subset through positive mean shifts. The stopping rule seeks low false-alarm frequency and asymptotically minimal conditional detection delay, although uniform optimality over unknown parameters is impossible.
- Model: Sensor observations are mutually independent normal variables with unit variance and zero means before a change.After the change, affected sensors have means µn > 0 while unaffected sensors remain standard normal.
- Model: A change occurs at an unknown time κ in an unknown subset of sensors, with unknown subset size and post-change means.The affected-sensor fraction is p = |N|/N.
- Objective: The stopping rule is required to have ARL at least a prescribed large constant while minimizing conditional expected detection delay asymptotically.Ideally, this minimization would hold uniformly over κ, the affected subset, and the mean shifts.
- Objective: Uniform minimization over all unknown parameters is impossible, so procedures are compared numerically under hypothetical conditions.The comparisons vary the change-point, affected sensors, and mean values.
3. Detection procedures.
The detection procedures build sensor-level likelihood statistics and combine them in several ways, including mixture rules parameterized by p0. Positive-part thresholding is used to reduce the influence of sensors that appear unaffected.
- Mixture procedures: The mixture model assumes each sensor is affected independently with probability p0 and combines sensor likelihood contributions accordingly.This encodes a hypothesized fraction of affected sensors in the global detection statistic.
- Local statistics: A nominal post-change mean δ can be used to construct local likelihood-ratio-based stopping rules.The positive part x+ retains evidence supporting a positive change.
- Local statistics: Positive-part thresholding acts as dimension reduction by limiting attention to sequences that appear affected by the change-point.This is intended to suppress contributions from sensors without positive evidence.
- GLR procedures: Alternatively, the unknown post-change mean can be replaced by its maximum-likelihood estimator to obtain a generalized likelihood-ratio statistic.The resulting GLR is used to define a stopping rule.
- Mixture procedures: When p0 = 1, the mixture rule becomes a global GLR procedure expected to be efficient when a large fraction of sensors is affected.The opposite sparse regime motivates procedures designed for one or very few affected sensors.
- Comparison: The positive-part modification avoids negative drifts from unaffected sensors canceling positive drifts from affected sensors.Without this protection, cancellation can produce a large expected detection delay.
4. Properties of the detection procedures.
The section develops approximations for ARL and EDD, emphasizing T2 and T4, and evaluates their accuracy and robustness through theory and simulation. The ARL approximation is highly accurate, whereas EDD accuracy is more variable and the procedures appear reasonably robust to the choice of p0.
- Performance measures: Theoretical analysis focuses on ARL and EDD for procedures T1–T4, especially T2 and the related T4.ARL is the expected stopping time under no change; EDD is the expected stopping time when the change occurs at κ = 0.
- ARL approximation: For no change, the stopping time is asymptotically exponential, yielding E∞{T} approximately equal to λ^-1 through the ARL approximation.The approximation follows from exponential asymptotics and uniform integrability, and is equivalent to (4.5).
- ARL approximation: The ARL approximation remains roughly correct even for N = 1 or 2, despite the mathematical assumptions involving large N.For p0 = 1, (4.5) gives numerical results similar to those for a generalized likelihood ratio statistic.
- EDD approximation: The first-order expected detection delay is 2b/∆^2 when the maximum window size m1 is large relative to this quantity.The rate follows because the post-change Kullback–Leibler divergence is ∆^2/2; the derivation assumes m1 ≫ 2b/∆^2.
- EDD approximation: EDD approximation accuracy is variable because its derivation depends on asymptotic linearization of g(U + …).A numerical check comparing the exact and linearized expectations can indicate when the approximation is reasonably accurate, and simulation is useful when EDD is small.
- Numerical assessment: The ARL approximation is quite accurate, while the EDD approximation is less accurate and the procedures are reasonably robust to the assumed p0.EDD simulation is less computationally demanding and generally only needs to be known roughly for design; choosing p0 somewhat too large appears less costly than choosing it too small.
5. Numerical comparisons.
The numerical comparisons evaluate detection delays for procedures calibrated to similar ARLs. The mixture procedures T2 and T3 are comparable, while competing procedures perform differently depending on the affected fraction.
- The comparisons use expected detection delays with procedures calibrated to an ARL of approximately 5000.The main numerical setting assumes N = 100 and m1 = 200 where a limited window is appropriate.
- Table 3 reports EDDs for T2(p0) and T4(p0) at ARL approximately 5000, with μ = 1 and m1 = 200.
- T2(p0) uses the generalized likelihood ratio statistic, while T3(p0,δ) is a related procedure with a positive-part modification.The positive part is inserted to avoid problems discussed earlier in the paper.
- The max procedure has the smallest detection delay when p = 0.01 but the largest delay when p exceeds 0.1.
- The T2 and T3 procedures have comparable detection delays, whereas Mei’s procedure performs well for large p and poorly for small p.
6. Parallel mixture procedure.
The parallel procedure combines mixture procedures using different hypothesized affected fractions to improve robustness when the true fraction is uncertain. Simulations indicate smaller delays in many settings, but more accurate ARL theory is still needed for larger problems.
- The parallel procedure combines component procedures using small and large hypothesized affected fractions, declaring detection when at least one reaches its threshold.The component thresholds are selected to give the same ARL.
- For N = 400, p1 = 0.02, p2 = 0.33, b1 = 21.2, and b2 = 87.7, the parallel procedure has a conservative ARL of at least 10,000.The bound follows from the Bonferroni inequality under the reported probabilities.
- The parallel procedure usually has smaller expected detection delays than a single intermediate-p0 procedure, especially for very small or very large p.
- Dependence between the component statistics makes the actual ARL somewhat larger than the Bonferroni approximation.
- A weighted linear combination of statistics for different p0 values is an alternative, but preliminary exploration suggests less EDD improvement than the parallel procedure.
7. Profile-based procedure for structured problems.
The paper extends sequential change-point detection to structured sensor fields by incorporating a parameterized spatial profile into a profile-based likelihood-ratio statistic. In a Gaussian-grid example, the resulting procedure has an analytically approximated ARL and substantially lower EDD under the correct profile, while profile misspecification remains an open concern.
- Profile-based model: The structured procedure models sensor amplitudes through a profile determined by source locations, source strengths, and a known or partially known decay function.The profile may depend on Euclidean distance and can represent multiple unknown sources.
- Profile-based model: Standardizing each profile to unit Euclidean norm removes the non-identifiability between source strength and profile scaling.Without standardization, multiplying source strengths and dividing profiles by the same constant leaves amplitudes unchanged.
- Detection statistic: Maximizing the profile likelihood over the change-point and source location produces a profile-based stopping rule that acts as a matched-filter statistic when the model is correct.The likelihood is first maximized over the signal-strength parameter.
- Theoretical ARL: For a two-dimensional Gaussian profile, the theoretical ARL approximation uses the signal region's area and decay parameter, with an asymptotic-exponential stopping-time argument.The derivation evaluates the relevant integral as |D|/(4β^2).
- Numerical examples: In a 25×25 grid with 625 sensors and approximately p = 0.016 affected sensors, thresholds targeting ARL 5000 gave b = 29.5 analytically versus 26.3 by simulation.The analytic approximation was slightly conservative, while the unstructured comparison used p0 = 0.05.
- Numerical examples: The profile-based procedure was substantially more powerful in EDD under the correctly specified profile, but profile knowledge is often limited and robustness to misspecification remains unresolved.Maximizing over β ∈ [0.5,5] raised the threshold to 33.8, suggesting a relatively moderate efficiency loss from uncertainty in decay rate.
8. Discussion.
The discussion concludes that the proposed unstructured procedures provide accurate ARL and EDD approximations and remain fairly robust to errors in the assumed affected fraction. It also reports large EDD improvements from correct spatial structure while identifying structural misspecification as an open problem.
- Unstructured procedures: The proposed procedures use ARL and EDD approximations that the paper reports as having reasonable accuracy.
- Unstructured procedures: Numerical results indicate fairly robust performance when the actual affected-sensor fraction differs from the hypothesized fraction.The paper suggests a parallel procedure using two or more hypothesized fractions to increase robustness.
- Structured procedures: Correct spatial structure can be incorporated into detection to achieve large improvements in expected detection delay.The extent to which an inadequately hypothesized structure compromises those improvements remains an open question.