Technische Samenvatting: Distributie-vrije Changepoint Lokalisatie na Sequentiële Veranderingsdetectie

Probleemstelling

Het artikel behandelt het fundamentele probleem van sequentiële changepoint lokalisatie in een willekeurige observatieruimte $\mathcal{X}$. Terwijl er een enorme hoeveelheid literatuur bestaat over het ontwerpen van stopregels (bijv. CUSUM, Shiryaev–Roberts, conformal test martingalen) om te detecteren wanneer een distributionele verandering plaatsvindt, is er een gebrek aan rigoureuze methoden om statistisch valide betrouwbaarheidssets voor de onbekende changepoint $T$ te construeren nadat een alarm is afgegaan.

Bestaande methoden voor inferentie na detectie (bijv. Ding, 2003a; Wu, 2007; Saha en Ramdas, 2026) vereisen doorgaans restrictieve aannames:

1. Bekende Distributies: De pre-change ($F_0$) en post-change ($F_1$) distributies moeten bekend zijn of behoren tot specifieke parametrische families (bijv. exponentiële families).
2. Disjuncte Klassen: De verzamelingen van mogelijke pre- en post-change distributies moeten vooraf bekend en disjunct zijn.
3. Asymptotische Garanties: Veel methoden bieden slechts asymptotische dekking-garanties.

De auteurs streven ernaar om betrouwbaarheidssets voor $T$ te construeren die voldoen aan finite-sample dekking-garanties zonder enige distributionele aannames op $F_0$ en $F_1$, met uitzondering van de aanname dat zij verschillend zijn. Het doel is om conditionele dekking te bereiken:
$$P_{F_0,T,F_1}(T \in C \mid \tau \ge T) \ge 1 - \alpha$$
waarbij $\tau$ de stoptijd is van een sequentiële detector.

Methodologie

Het voorgestelde framework ontkoppelt de detectiefase van de lokalisatiefase. Het fungeert als een "wrapper" rondom elk bestaand algoritme voor sequentiële veranderingsdetectie (ongeacht of de detector zelf distributie-vrij is). De kernmethodologie berust op conformal test martingalen en de uitwisselbaarheid van datasegmenten.

1. Kernaannames

• Uitwisselbaarheid: Het pre-change segment $X_1, \dots, X_{T-1}$ is uitwisselbaar (Aanname 2), en het post-change segment $X_T, X_{T+1}, \dots$ is uitwisselbaar (Aanname 1).
• Black-Box Toegang: De lokalisatieprocedure heeft toegang tot de stoptijd $\tau$ en de datareeks tot $\tau$, maar behandelt het detectiealgoritme als een black box.
• Distributie-vrije Schatting: Een onbevooroordeelde (of negatief bevooroordeelde) estimator $\hat{r}_t$ voor de waarschijnlijkheid van geen vals alarm tot tijd $t$ ($P_{F_0, \infty}[\tau \ge t]$) is vereist. Dit kan worden geschat via Monte Carlo-simulatie met i.i.d. data uit elke gemakkelijke distributie, mits de verdeling van de stoptijd van de detector onder de nulhypothese onafhankelijk is van de specifieke $F_0$ (Aanname 3).

2. Constructie van Betrouwbaarheidssets

De methode construeert eenzijdige betrouwbaarheidssets afzonderlijk en snijdt deze om een tweezijdige interval te vormen.

Lagere Betrouwbaarheidsset ($C^{\alpha}_{low}$)

• Doel: Identificeren van een tijd $t$ zodanig dat de ware changepoint $T \ge t$.
• Hypothese-test: Voor een kandidaat $t$, test $H_0: T = t$ tegen $H_1: T > t$.
• Mechanisme: Als $T > t$, bevat het segment $X_t, \dots, X_\tau$ een mengeling van pre- en post-change data, wat de uitwisselbaarheid schendt. Als $T = t$, is het segment puur post-change en uitwisselbaar.
• Procedure:
  1. Bereken sequentiële conformal p-waarden $p^j_t$ voor $j \ge t$ gebaseerd op score-vergelijkingen binnen het venster $[t, j]$.
  2. Transformeer p-waarden naar e-waarden via een calibratiefunctie $f_{t,j}(p) = 1 + \lambda_{t,j}(p - 0.5)$.
  3. Agregeer bewijs via een martingale $M_t = \prod f_{t,j}(p^j_t)$.
  4. Behoud $t$ in $C^{\alpha}_{low}$ als de maximale martingale-waarde over het venster de drempel $1/(\alpha \hat{r}_t)$ niet overschrijdt.

Bovenste Betrouwbaarheidsset ($C^{\beta}_{up}$)

• Doel: Identificeren van een tijd $t$ zodanig dat de ware changepoint $T \le t$.
• Hypothese-test: Voor een kandidaat $t$, test $H_0: T = t$ tegen $H_1: T < t$.
• Mechanisme: Vergelijkbaar met de lagere set, maar werkt in de achterwaartse richting. Als $T < t$, bevat het segment $X_1, \dots, X_t$ een mengeling, wat de pre-change uitwisselbaarheid schendt.
• Procedure: Bereken achterwaartse sequentiële conformal p-waarden $q^j_t$ voor $j \le t$, aggregeer via een martingale, en behoud $t$ als de statistiek onder de drempel blijft.

Tweezijdige Betrouwbaarheidsset

De uiteindelijke betrouwbaarheidsset is de doorsnede: $C = C^{\alpha}_{low} \cap C^{\beta}_{up}$. Door de union bound wordt voldaan aan $P(T \in C \mid \tau \ge T) \ge 1 - \alpha - \beta$.

3. Calibrator Leren

Ho'ewel theoretische grenzen uitgaan van een "oracle" calibrator (optimaal gekozen $\lambda$), stelt het artikel voor om online convex optimization (specifiek Online Newton Step met Follow-The-Leading-History) te gebruiken om de sequentie van $\lambda_{t,j}$ adaptief te leren. Dit zorgt voor een logaritmische regret, waarbij de validiteit van de betrouwbaarheidssets behouden blijft terwijl hun grootte wordt geoptimaliseerd.

Belangrijkste Bijdragen

1. Eerste Algemene Distributie-vrije Framework: Het artikel introduceert het eerste framework voor post-detectie changepoint lokalisatie dat finite-sample dekking-garanties biedt zonder kennis van $F_0$ of $F_1$, of het aannemen van disjuncte distributieklassen ($P_0 \cap P_1 = \emptyset$).
2. Ontkoppeling van Detectie en Inferentie: De methode staat toe dat willekeurige sequentiële detectoren (inclusief die gebaseerd op ARL of PFA controle) omwikkeld kunnen worden met een distributie-vrije inferentielaag.
3. Eenzijdige en Tweezijdige Constructies: De auteurs ontwikkelen onderscheidende constructies voor de lagere en bovenste grenzen, waarbij zij de intrinsieke asymmetrie van sequentiële lokalisatie erkennen. Zij bewijzen finite-sample dekking voor beide.
4. Niet-Asymptotische en Asymptotische Grenzen:
   • Finite-Sample: Expliciete grenzen op de conditionele verwachte grootte van de betrouwbaarheidssets zijn afgeleid.
   • Asymptotisch: Onder geschikte regimes (waar de detectievertraging schaalt met de logaritme van de changepoint $T$), wordt getoond dat de verwachte grootte van de betrouwbaarheidsset uniform begrensd blijft (of sub-lineair groeit), zelfs zonder distributionele aannames.
5. Praktische Schatting van Nul-waarschijnlijkheden: Een methode om de cruciale normalisatieterm $\hat{r}_t$ te schatten via Monte Carlo-simulatie met willekeurige i.i.d. data, waardoor de noodzaak voor de specifieke nul-distributie $F_0$ wordt omzeild.

Resultaten

Theoretische Resultaten

• Dekking: Theorem 1 en Theorem 2 stellen vast dat de lagere en bovenste sets een dekking bereiken van ten minste $1-\alpha$ en $1-\beta$, respectievelijk. Corollary 1 breidt dit uit naar de tweezijdige set.
• Grootte-grenzen:
  • Theorem 3 & 4: Voor de lagere betrouwbaarheidsset is de verwachte pre-change lengte $O(1)$ of $O(\log T)$, afhankelijk van de signaalsterkte $\delta$ en het detectievertraging-regime.
  • Theorem 5 & 6: Voor de bovenste betrouwbaarheidsset is de verwachte post-change lengte $O(1)$ onder milde voorwaarden op de stoptijdverdeling van de detector.
  • Theorem 7 & 10: De gecombineerde grootte van de tweezijdige set is uniform begrensd of groeit zeer traag (sub-lineair) in $T$ onder passende asymptotische regimes.
• Adaptief Leren: Theorems 8, 9 en 10 tonen aan dat het gebruik van online learning voor calibratoren (met logaritmische regret) deze grenzen behoudt, met slechts minimale aanpassingen aan de constanten.

Empirische Resultaten

De auteurs valideren de methode op drie datasets:

1. Gaussian Mean Change: Simulaties met $N(-1, 1) \to N(1, 1)$. De methode lokaliseerde de changepoint succesvol met nauwe betrouwbaarheidsintervallen (bijv. breedte $\approx 5$ voor $T=500$).
2. MNIST Digit Change: Een hoog-dimensionale setting waarbij de distributie verschuift van cijfer '3' naar '7' (of gemengde distributies). Gebruikmakend van een vooraf getrainde CNN voor scoring, bereikte de methode scherpe intervallen (bijv. $[395, 400]$ voor $T=400$).
3. Wine Quality Dataset: Een real-world toepassing die een overgang simuleert van witte naar rode wijn. De lagere betrouwbaarheidsgrens werd gevonden op 387 (ware $T=400$), waardoor operators monsters tot tijd 386 kunnen certificeren als "wit" met 90% vertrouwen.

Betekenis en Claims

Het artikel claimt het eerste algemene distributie-vrije framework te bieden voor sequentiële changepoint lokalisatie met valide post-detectie dekking-garanties.

• Motivatie: In real-world systemen (industriële monitoring, netwerkbeveiliging) zijn de mechanismen die data genereren vaak complex, hoog-dimensionaal en slecht gespecificeerd, waardoor betrouwbare distributionele modellering onhaalbaar is. Bestaande methoden die kennis van $F_0/F_1$ of disjuncte klassen vereisen, zijn in dergelijke settings vaak onrealistisch.
• Voordeel ten opzichte van vorig werk: In tegen tegenstelling tot Saha en Ramdas (2026), dat $P_0 \cap P_1 = \emptyset$ vereist, staat dit framework toe dat $P_0 = P_1 = \mathcal{P}$ (het universum van alle distributies), waarbij enkel vereist is dat de specifieke gerealiseerde $F_0 \neq F_1$.
• Praktisch Nut: De lagere betrouwbaarheidsgrens wordt benadrukt als bijzonder nuttig voor kwaliteitscontrole, omdat het een "veilige tijd-drempel" biedt waarna een systeem gegarandeerd in een post-change (potentieel defecte) staat verkeert, wat gerichte isolatie van getroffen producten mogelijk maakt.
• Robuustheid: De validiteit van de procedure rust niet op modelleringsaannames; modellen (zoals voor scoring) beïnvloeden enkel de statistische efficiëntie (de grootte van het interval), niet de validiteit van de dekking-garantie.

De auteurs concluderen dat betrouwbare changepoint lokalisatie mogelijk is zelfs zonder distributionele aannames, wat een conceptueel eenvoudig en breed toepasbaar instrument biedt voor sequentiële analyse. Toekomstig werk wordt gesuggereerd om dit uit te breiden naar multi-stream settings.