Sequential Change Detection Under Markov Setup With Unknown Prechange And Postchange Distributions

Titel:

Sequentiële Veranderingdetectie onder Markov-Setup met Onbekende Pre-verandering en Post-verandering Verdelingen

1. Probleemstelling

Het paper adresseert het probleem van sequentiële veranderingdetectie (sequential change detection) in een omgeving waar de statistische verdeling van de data verandert op een onbekend tijdstip.

• Context: De data wordt gegenereerd door een bron die voldoet aan een stationair en ergodisch Markov-proces (met geheugen), in plaats van onafhankelijke en identiek verdeelde (i.i.d.) variabelen.
• Uitdaging: In veel realistische scenario's zijn zowel de pre-verandering verdeling ($\mu_0$) als de post-verandering verdeling ($\mu_1$) onbekend.
• Doel: Ontwikkelen van een test die een verandering zo snel mogelijk detecteert terwijl de kans op valse alarmen (false alarms) onder een bepaalde drempel wordt gehouden, zelfs zonder kennis van de onderliggende verdelingen.

2. Methodologie

De auteurs bouwen voort op eerdere werken (Jacob & Bansal, Malik & Bansal) die i.i.d. bronnen behandelden, en breiden deze uit naar Markov-bronnen. De kern van de methode bestaat uit drie componenten:

A. Schatting van de Pre-verandering Verdeling ($\hat{\mu}_0$)

Omdat $\mu_0$ onbekend is, wordt deze geschat tijdens een trainingsfase van $n_0$ symbolen (voordat de test officieel begint).

• Voor een eerste-orde Markov-proces wordt de empirische verdeling berekend op basis van de frequentie van symbolen en overgangen in de trainingssequentie $x_1, \dots, x_{n_0}$.
• De schatting $\hat{\mu}_0$ wordt gebruikt als vervanging voor de ware $\mu_0$ in de teststatistiek.

B. Gebruik van Universele Codes voor Post-verandering

Voor de post-verandering verdeling ($\mu_1$), die ook onbekend is, wordt geen parametrische schatting gebruikt. In plaats daarvan wordt een universele code (zoals Lempel-Ziv of Context Tree Weighting) ingezet.

• De lengte van de gecodeerde sequentie, $L(x)$, fungeert als een schatting van de negatieve log-waarschijnlijkheid van de post-verandering verdeling.
• Dit maakt de test robuust voor een breed scala aan mogelijke post-verandering verdelingen.

C. De Gewijzigde CUSUM-test

De auteurs introduceren een Gewijzigde Page's CUSUM-test (Test 3). De test start na de trainingsfase ($n_0$). Voor een nieuwe observatie $x_{n_0+1}, \dots, x_{n_0+n}$ wordt de volgende statistiek berekend:
$$\max_{1 \le k \le n} \left( -L(x_{n_0+n}^{n_0+k}) - \log \hat{\mu}_0(x_{n_0+n}^{n_0+k}) - n\lambda \right) \ge \log \gamma$$
Waarbij:

• $L(\cdot)$ de lengte van de universele code is.
• $\hat{\mu}_0$ de geschatte pre-verandering verdeling is.
• $\lambda$ een parameter is die zorgt voor een negatieve drift onder de nulhypothese (geen verandering).
• $\gamma$ de drempelwaarde is die de valse alarmkans bepaalt.

De test stopt en meldt een verandering zodra deze som de drempel $\log \gamma$ overschrijdt.

3. Belangrijkste Bijdragen

1. Extensie naar Markov-bronnen: Het paper generaliseert eerdere resultaten voor i.i.d. bronnen naar stationaire en ergodische Markov-bronnen die voldoen aan Berk's mixing conditions.
2. Onbekende Verdelingen: Het is de eerste werk dat een sequentiële test biedt waarbij zowel de pre- als post-verandering verdeling onbekend zijn, specifiek voor bronnen met geheugen.
3. Asymptotische Optimaliteit: De auteurs bewijzen dat de voorgestelde test asymptotisch optimaal is in het regime waar de snelheid van valse alarmen naar nul gaat.
4. Foutanalyse: Er wordt een nauwkeurige analyse uitgevoerd van de kans op fouten (false alarms) die rekening houdt met de onzekerheid in de schatting van $\mu_0$.

4. Resultaten en Bewijzen

De auteurs leveren wiskundige bewijzen voor de volgende eigenschappen:

• Beperking van Valse Alarmen (Lemma 3): De kans dat de test stopt terwijl er geen verandering is ($\mu_0$), wordt begrensd door een uitdrukking die afhankelijk is van de trainingslengte $n_0$ en de parameter $\lambda$. Naarmate $n_0 \to \infty$, convergeert de foutkans naar de theoretische limiet.
• Zekere Detectie (Lemma 4): Onder de alternatieve hypothese ($\mu_1$) stopt de test met waarschijnlijkheid 1, mits $\lambda < D(\mu_1 || \hat{\mu}_0)$.
• Verwachte Detectievertraging (Theorema 5 & 6):
  • De verwachte tijd tot detectie onder $\mu_1$ wordt gegeven door:
    $$E_1(M(\gamma)) \sim \frac{\log \gamma}{D(\mu_1 || \hat{\mu}_0) - \lambda}$$
  • Door $\lambda$ en de drempel $\gamma$ correct te kiezen, benadert de prestatie van de test de Lorden-ondergrens (de theoretisch beste mogelijke prestatie) met een factor $(1+\vartheta)$, waarbij $\vartheta$ willekeurig klein kan worden gemaakt.
  • Dit betekent dat de test asymptotisch optimaal is.

5. Betekenis en Toekomstperspectief

• Praktische Relevantie: De methode is zeer relevant voor toepassingen zoals industriële kwaliteitscontrole en netwerkbeveiliging, waar data vaak correlaties vertoont (geheugen) en de exacte statistische modellen van fouten of aanvalspatronen niet van tevoren bekend zijn.
• Theoretische Vooruitgang: Het paper sluit een belangrijke lacune in de literatuur door de complexiteit van onbekende verdelingen te combineren met de complexiteit van bronnen met geheugen.
• Toekomstig Werk: De auteurs suggereren dat deze resultaten verder kunnen worden veralgemeend onder het raamwerk van T.L. Lai, waarbij de eis van onafhankelijkheid tussen pre- en post-verandering observaties nog verder kan worden verzwakt. Ook kan de prestatie worden geëvalueerd onder andere criteria dan die van Lorden.

Conclusie: Het paper presenteert een robuust en asymptotisch optimaal algoritme voor het detecteren van veranderingen in Markov-processen met volledig onbekende verdelingen, gebruikmakend van een combinatie van empirische schattingen en universele coderingstechnieken.