PaperlayerView exact revision on arXiv

Source-linked AI summary

Scan $B$-Statistic for Kernel Change-Point Detection

Shuang Li, Yao Xie, Hanjun Dai, Le Song

arXiv:1507.01279v5cs.LGmath.STstat.MLstat.TH

TL;DR

Change-point detection seeks to identify when a sample sequence shifts from distribution P to Q, and kernel approaches offer a nonparametric option. This paper develops offline and online scan B-statistics and change-of-measure approximations for their false-alarm rates. The approximations are reported as accurate, with numerical validation and good performance on real-data examples.

  • Problem

    Change-point detection seeks to identify a shift from i.i.d. samples with distribution P to samples with distribution Q, while kernel-based nonparametric statistics are used to reduce distributional assumptions and handle multidimensional real data.

    Source: §1 · p. 1

  • Method

    The paper adapts kernel MMD B-statistics into offline and online scan statistics and uses change-of-measure analysis to approximate their false-alarm rates.

    Source: §1 · p. 2

  • Results

    The paper reports accurate false-alarm approximations, validates their accuracy numerically, and demonstrates good performance on speech and human-activity data.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The approximations address offline significance levels and online average run lengths, providing a basis for false-alarm control in both settings.

    Source: §1 · p. 2

    The developed algorithms assume i.i.d. data from a null distribution before the change and an alternative distribution afterward; dependent data are left as a possible extension.

    Source: §8 · p. 15

Abstract

from arXiv · show

Detecting the emergence of an abrupt change-point is a classic problem in statistics and machine learning. Kernel-based nonparametric statistics have been used for this task which enjoy fewer assumptions on the distributions than the parametric approach and can handle high-dimensional data. In this paper we focus on the scenario when the amount of background data is large, and propose two related computationally efficient kernel-based statistics for change-point detection, which are inspired by the recently developed $B$-statistics. A novel theoretical result of the paper is the characterization of the tail probability of these statistics using the change-of-measure technique, which focuses on characterizing the tail of the detection statistics rather than obtaining its asymptotic distribution under the null distribution. Such approximations are crucial to control the false alarm rate, which corresponds to the significance level in offline change-point detection and the average-run-length in online change-point detection. Our approximations are shown to be highly accurate. Thus, they provide a convenient way to find detection thresholds for both offline and online cases without the need to resort to the more expensive simulations or bootstrapping. We show that our methods perform well on both synthetic data and real data.

1. INTRODUCTION

The paper targets single change-point detection under broad distributional settings, adapting kernel-based B-statistics for offline and online scans. It addresses false-alarm control despite dependence among overlapping scans, and distinguishes its direct tail approximations from analyses based on null asymptotic distributions.

1. INTRODUCTION

  • The problem is to detect one change from i.i.d. samples with distribution P to samples with distribution Q, either at a fixed horizon or as new observations arrive.Offline detection tests whether a change exists; online detection seeks to detect its emergence as soon as possible.Source: §1 · p. 1
  • The proposed scan B-statistics adapt kernel MMD tests to offline and online detection, reusing post-change samples while constructing multiple disjoint reference blocks.This reuse induces dependence among averaged MMD statistics, and scanning overlapping blocks adds further dependence.Source: §1 · p. 2
  • Change-of-measure analysis approximates scan B-statistic false-alarm rates because overlapping scans create correlations that rule out the cited central-limit approaches.The resulting false-alarm quantities correspond to offline significance levels and online average run lengths.Source: §1 · p. 2
  • A closed-form variance estimator supports scan-statistic calculation, while skewness correction improves approximation accuracy; numerical examples and speech and human-activity data validate the approach.The paper reports good performance on the real-data examples.Source: §1 · p. 2

1.1. Related Work

  • Unlike classic kernel U-statistic analyses that establish a null limit for the sample path, scan B-statistics use B-test block averaging and directly approximate the statistic’s null tail.The block structure and scan-induced correlation make the analysis more challenging than in those classic works.Source: §1.1 · p. 3
  • The change-of-measure framework directly approximates false-alarm tails for both offline and online detection, while large-deviation analyses provide exponential rates that may omit polynomial terms and constants.The paper contrasts this approach with methods seeking an asymptotic null distribution and with large-deviation techniques [Dembo and Zeitouni (2009)].Source: §1.1 · p. 3

2. BACKGROUND

The background introduces kernel MMD as a distribution-comparison statistic and the B-test as a block-averaged way to reduce its computation. It also illustrates the block arrangements used for offline and online change-point detection.

2. BACKGROUND

  • A reproducing kernel Hilbert space represents function evaluation as an inner product with a kernel function, with Gaussian RBF and polynomial kernels among the examples.The paper assumes a Gaussian RBF kernel unless stated otherwise.Source: §2 · p. 4
  • MMD compares distributions through kernel evaluations, and its unbiased U-statistic estimator has O(n^2) computation and a degenerate null distribution when P = Q.The estimator is expected to be small when P = Q and large when the distributions are far apart.Source: §2 · p. 4
  • The B-test averages MMD U-statistics across N non-overlapping blocks of size B, reducing computation to O(nB^2); independent blocks yield asymptotic normality under the null.The figure contrasts offline subdivision of Bmax blocks with online use of a recent B0-sample test block and reference blocks from the pool.Source: §2 · pp. 4–5

3. SCAN B-STATISTICS

The scan B-statistics use kernel MMD to detect sustained distribution changes when reference data are plentiful and post-change samples are few. Offline scanning varies the post-change block size, while online detection uses a fixed sliding window; both use a closed-form variance and threshold-based alarms.

3. SCAN B-STATISTICS

  • With plentiful reference data and few post-change samples, the procedure compares a common test block against multiple disjoint reference blocks using kernel MMD.The setup assumes a sustained change from a pre-change distribution to a different post-change distribution.Source: §3 · p. 5

3.1. Offline Change-Point Detection

  • The offline statistic averages MMD estimates across reference blocks, standardizes each block-size statistic, and takes the maximum over B from 2 to Bmax.A change is detected when this maximum exceeds a prespecified threshold.Source: §3.1 · p. 6

3.2. Online Change-Point Detection

  • Online detection fixes block size B0 and slides the most recent B0 samples as a common test block against N reference blocks sampled from the reference pool.The standardized statistic triggers an alarm when it exceeds threshold b; its variance is independent of time and can be precomputed.Source: §3.2 · pp. 6–7

3.3. Analytical Expression for Var[ZB]

  • A closed-form expression for Var[ZB] under the null supports construction of both offline and online scan statistics.The variance result is stated for block size B ≥ 2 and N reference blocks.Source: §3.3 · p. 7

3.4. Examples of Detection Statistics

  • Examples report online detection delays of 20 time units for a Gaussian-mixture change and 2 for an emerging graph community.A real seismic-signal example illustrates the effect of Gaussian RBF kernel bandwidth.Source: §3.4 · p. 7

4. THEORETICAL APPROXIMATIONS

The paper derives tail-based approximations for offline significance levels and online average run lengths of scan B-statistics. Numerical comparisons show the approximations can calibrate thresholds accurately, with skewness correction improving accuracy in some settings.

4.1. Theoretical Approximation for Significance Level of Offline Scan B-Statistic

  • For offline detection, Theorem 4.1 approximates significance level as b and Bmax grow with b/(Bmax)^1/2 fixed; the derivation uses change of measure for rare threshold exceedances.In synthetic normal data, predicted thresholds match Monte Carlo thresholds across tested Bmax values, with skewness correction improving accuracy at smaller α.Source: §4.1 · pp. 8–9, Table 1 · p. 9

4.2. Theoretical Approximation for ARL of Online Scan B-Statistic

  • For online detection, Theorem 4.2 approximates ARL as b grows, allowing thresholds for target ARL to be obtained without expensive simulations.Across four null distributions, thresholds are reported as quite accurate but tend to be underestimated, especially for small B0; skewness correction improves accuracy.Source: §4.2 · pp. 9–10, Figure 3 · p. 10
  • Theorem 4.2 gives ARL = O(e^b^2), so the threshold grows as O((log ARL)^1/2); Theorem 4.1 gives offline significance level O(e^-b^2).The text relates threshold estimation error linearly to expected detection delay in the online setting.Source: §4.2 · p. 10

5. DETECTION POWER STUDY

The section compares offline detection power and online detection delay for scan B-statistics against parametric methods. Offline scan B-statistics outperform both comparators across the tested cases; online they are competitive for Gaussian changes and detect difficult non-Gaussian changes where Hotelling’s T 2 fails.

5.1. Offline Change-Point Detection: Comparison with Parametric Statistics

  • The scan B-statistic achieves higher offline detection power than Hotelling’s T 2 and GLR in all tested cases.The cases include mean shifts, a local covariance change, and a Gaussian-to-Laplace change.Source: §5.1 · p. 11, Table 2 · p. 12

5.2. Online Change-Point Detection: Comparison with Hotelling’s T 2 Statistic

  • Online scan B-statistics perform competitively with Hotelling’s T 2 for Gaussian mean or covariance changes, and detect Case 4 and Case 5 while Hotelling’s T 2 fails.Table 3 reports EDD with B0 = 20 and thresholds calibrated to ARL = 5000; dashed entries denote EDD longer than 50.Source: Table 3 · p. 12, §5.2 · p. 12

6. SKEWNESS CORRECTION

The section accounts for skewness when approximating scan B-statistic tail probabilities, since the statistic does not become normal even for large block sizes. The correction improves approximation accuracy, and the paper describes an efficient route to estimate skewness.

6. SKEWNESS CORRECTION

  • Although ZB matches a Gaussian distribution to some extent, it does not converge to normal even for large B and retains non-vanishing skewness.The empirical skewness becomes larger for larger B.Source: §6 · pp. 12–13, Figure 4 · p. 13
  • The correction adds a third-cumulant term to the log-moment-generating-function approximation and adjusts the exponent using a B-dependent solution.The paper modifies the leading exponent used in the significance-level and ARL approximations.Source: §6 · p. 13
  • At α = 0.01 and small B0, skewness correction is especially useful offline and can matter for noisy real-data nulls.On real speech data, the threshold accuracy improves significantly with skewness correction.Source: §6 · pp. 13–14
  • Lemma 6.1 expresses ZB’s third moment using moments of kernel h, enabling efficient skewness estimation through simpler tuple-based kernel evaluations.This reduces the estimation to evaluating the kernel statistic on tuples of samples.Source: §6 · p. 14

7. REAL DATA

On speech and human-activity data, scan B-statistics achieved higher overall AUC than the relative density-ratio baseline.

7. REAL DATA

  • AUC was 0.8014 for scan B-statistic versus 0.7578 for the baseline on speech, and 0.8871 versus 0.7161 on human-activity detection.The speech task detects speech emergence from background signals; the activity task detects transitions between activities.Source: §7 · p. 15

8. DISCUSSIONS

The discussion identifies the i.i.d. assumption and high-dimensional performance as boundaries for the current work, and proposes several extensions.

8. DISCUSSIONS

  • The algorithms assume i.i.d. samples from P before the change and Q afterward; extending scan B-statistics to dependent data is proposed as future work.The proposed extension would incorporate ideas for dependent data.Source: §8 · p. 15
  • The authors note that MMD performance degrades as dimensionality increases and suggest exploring high-dimensional extensions and random subsampling for large Gram matrices.They also identify kernel bandwidth as a factor for further study.Source: §8 · p. 15

A. RECURSIVE IMPLEMENTATION OF ONLINE SCAN STATISTIC

This appendix develops recursive computation and probabilistic analysis of the online scan statistic, including variance and covariance calculations and a tail approximation via exponential tilting and change of measure. It also characterizes the local field near and far from the change point.

A. RECURSIVE IMPLEMENTATION OF ONLINE SCAN STATISTIC

  • The online statistic updates each reference and testing block recursively, requiring only the new Gram-matrix entries—specifically the rightmost column and bottom row—to be computed.The update adds a new sample, purges the oldest, and moves the Gram-matrix windows; offline statistics can also be updated recursively by reusing common terms.Source: A. RECURSIVE IMPLEMENTATION OF ONLINE… · p. 18, Figure 5 · p. 18

B.1. Variance of Scan B-Statistics.

B.2. Covariance of Offline Scan B-Statistics.

  • For offline scan statistics, the covariance calculation combines the different-block-size lemmas with the variances of Z_B and Z_(B+v) to obtain equation (4.3).Source: §B.2 · p. 21

B.3. Covariance of Online Scan B-Statistics

  • For online statistics at fixed block size, the covariance analysis accounts for overlap between observations in successive MMD windows and obtains equation (D.2).Source: §B.3 · pp. 22–23

C. PROOF OF THEOREM 4.1

  • The proof of Theorem 4.1 proceeds through exponential tilting, a likelihood-identity change of measure, analysis of local and global terms, and localization.It uses asymptotic independence of the global log-likelihood term and the local process.Source: C. PROOF OF THEOREM 4.1 · p. 23

C.1. Step One: Exponential Tilting

  • For standard Gaussian Z′_B under the null, choosing tilt parameter θ = b shifts its mean to b while preserving unit variance, uniformly across B.Source: §C.1 · p. 23

C.2. Step Two: Change-of-Measure

  • The change of measure expresses the exceedance tail as e^(−b^2/2) times conditional expectations under a mixture of exponentially tilted measures.The conditional terms involve a likelihood-ratio weight and a ratio of the defined maximum and sum.Source: §C.2 · pp. 24–25

C.3. Step Three: Establish Properties of Local and Global Terms

  • Under the tilted measure, the global term has mean zero and variance b^2, while local-field covariance is b^2(1 + r_s1,s2 − r_s1,B − r_s2,B); the terms are asymptotically independent.Source: §C.3 · p. 25
  • As |s − B| → ∞, E_B[ℓ_s − ℓ_B] converges to −b^2 and Var_B[ℓ_s − ℓ_B] converges to 2b^2.Source: §C.3 · p. 26
  • Near the change point, the local field is approximated by a two-sided Gaussian random walk with drift μ^2/2 and increment variance μ^2.Source: §C.3 · p. 26

C.4. Step Four: Approximation Using Localization Theorem

The localization argument separates the global term from a local field, reducing the tail approximation to their respective asymptotic behavior. It verifies the theorem’s conditions and obtains a limiting local ratio and a local central limit approximation for the global term.

C.4. Step Four: Approximation Using Localization Theorem

  • Under b → ∞ and Bmax → ∞ with b^2/Bmax fixed positive, the localization conditions are checked using Gaussian-field and likelihood-ratio arguments.The analysis uses a local region of size g(κ) = cb^-2 and verifies the martingale-based tail bound for the maximization term.Source: §C.4 · pp. 26–29
  • Localization approximates the maximization and summation near B, where their ratio becomes asymptotically independent of the global term.The localized ratio has a finite positive limiting expectation, while the global term can be analyzed separately using a local central limit theorem.Source: §C.4 · p. 27
  • The limiting expected localized ratio is the Mills-ratio expression exp(−2 Σ_{j=1}^∞ Φ(−j^1/2 μ/2)), with an easier numerical approximation given in terms of ν(μ).The passage relates the Mills ratio to the Laplace transform of the overshoot of Gaussian-field maxima over threshold b.Source: §C.4 · p. 28
  • A local central limit theorem approximates the global-term density near zero by 1/(2πb^2)^1/2, enabling calculation of the remaining conditional expectation.The argument takes the scaled global term to have mean 0 and variance 1 as κ = b^2 grows.Source: §C.4 · pp. 28–29

D. PROOF OF THEOREM 4.2

The online stopping time is shown to be uniformly integrable and asymptotically exponentially distributed under the null. The proof uses a change of measure and localization, with a generalized Poisson approximation to handle dependent threshold-crossing events.

D. PROOF OF THEOREM 4.2

  • The online proof adapts the offline change-of-measure and localization strategy, with different drift parameters because the covariance structures differ.The local field’s mean decreases with |t − s| until the sliding blocks no longer overlap, and nearby values determine the localized maximum and sum.Source: D. PROOF OF THEOREM 4.2 · pp. 29–30
  • Under the null, the stopping time T is uniformly integrable and asymptotically exponentially distributed as b → ∞.For large m, P{T ≤ m} is approximately 1 − exp(−λ0m), and E{T} is asymptotically λ0^-1.Source: D. PROOF OF THEOREM 4.2 · pp. 29–30
  • Near |s − t| = 0, the online local field is approximated by a two-sided random walk, with its covariance specified in Lemma D.2.The covariance is expressed using b^2 and correlations among the scan positions.Source: D. PROOF OF THEOREM 4.2 · p. 30
  • Because online threshold-crossing events are dependent, the proof uses a generalized Poisson limit theorem to approximate their count over disjoint intervals.The stated bound on p2 vanishes when log b ≪ m ≪ b^-1e^(b^2/2), while p3 vanishes because the relevant indicators use non-overlapping observations.Source: D. PROOF OF THEOREM 4.2 · pp. 31–32

E. SKEWNESS CALCULATION

The skewness calculation derives the scan B-statistic’s third-order moments under the null by enumerating combinations of kernel terms. The resulting expression is summarized in Lemma 6.1.

E. SKEWNESS CALCULATION

  • Under the null, only two enumerated term patterns contribute to the raw third-order moment for a single scan statistic.The surviving patterns are the cyclic product across three indices and the repeated product for the same index.Source: E. SKEWNESS CALCULATION · pp. 32–33
  • For mixed terms involving two scan indices, only two patterns remain nonzero under the null.These are the patterns with shared indices and the repeated same-pair terms.Source: E. SKEWNESS CALCULATION · p. 33
  • The final skewness expression for the scan B-statistic is summarized in Lemma 6.1 using Lemmas E.1–E.3.For the product involving three scan indices, the passage likewise identifies two nonzero term patterns under the null.Source: E. SKEWNESS CALCULATION · p. 34

F. ZB DOES NOT CONVERGE TO GAUSSIAN

The appendix argues that Z_B does not converge to a standard normal because its skewness remains nonzero, and reports higher average speech-detection AUC than the baseline.

F. ZB DOES NOT CONVERGE TO GAUSSIAN

  • Z_B does not converge to a standard normal: its third moment and variance scaling leave its skewness constant with B, motivating skewness-aware significance-level and ARL approximations.The appendix shows the moment-generating-function difference from a standard normal remains nonzero.Source: F. ZB DOES NOT CONVERGE TO GAUSSIAN · p. 35

G.1. CENSREC-1-C Speech Dataset

  • The speech evaluation detects noise-to-speech transitions across simulated and recorded settings, using noise reference data and a detection-window tolerance for true alarms.The recordings include restaurant and highway noise; simulated data include multiple noise environments.Source: §G.1 · p. 36
  • AUC averaged across all CENSREC-1-C settings was .8014 for our algorithm versus .7578 for the baseline, which it outperformed on most cases.Both algorithms performed well on simulated clean data, where speech and background differed more than in noisy data.Source: §G.1 · p. 36, Table 5 · p. 36

G.2. HASC Human Activity Dataset

On HASC human-activity data, the scan statistic achieved higher AUC than the baseline; examples include detected activity transitions and an alarm within an activity.

G.2. HASC Human Activity Dataset

  • The evaluation pairs six activity categories using the magnitude of three-axis accelerometer signals, retaining 381 sufficiently long sequences.The categories include walking/jogging, stair and elevator travel, escalator travel, moving walkways, and staying still.Source: §G.2 · pp. 37, 39
  • AUC on 381 HASC sequences was .8871 for our algorithm versus .7161 for the baseline.The sequences pair different activity categories after removing those that were too short.Source: §G.2 · p. 39
  • Examples show detected transitions between walking and stair activity, while an elevator-phase alarm occurs within an activity that includes acceleration and uniform-motion phases.The authors regard that alarm as reasonable given the activity's internal motion phases.Source: §G.2 · p. 39, Figure 9 · p. 39

Related papers

Loading 1507.01279v5…