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

Titolo: Rilevamento Sequenziale di Cambiamenti in Configurazione Markoviana con Distribuzioni Pre- e Post-Cambiamento Sconosciute

1. Problema e Contesto

Il rilevamento sequenziale dei cambiamenti (Change Detection) è fondamentale in applicazioni come il controllo di qualità industriale e il rilevamento di guasti nelle reti di comunicazione. Il problema classico consiste nel rilevare il momento in cui la distribuzione statistica di una sorgente di dati cambia da una distribuzione pre-cambiamento ($\mu_0$) a una post-cambiamento ($\mu_1$).

La maggior parte degli algoritmi classici, come il test CUSUM di Page, richiedono che entrambe le distribuzioni ($\mu_0$ e $\mu_1$) siano note. Tuttavia, in scenari reali, queste distribuzioni sono spesso sconosciute. Lavori precedenti (Jacob & Bansal, Malik & Bansal) hanno affrontato questo problema per sorgenti i.i.d. (indipendenti e identicamente distribuite) utilizzando codici universali per stimare $\mu_1$ e stime empiriche per $\mu_0$.

L'obiettivo di questo lavoro è estendere questi risultati al caso più generale di sorgenti Markoviane stazionarie ed ergodiche di ordine finito, dove le distribuzioni pre- e post-cambiamento sono entrambe sconosciute, mantenendo l'ottimalità asintotica.

2. Metodologia

Gli autori propongono un test CUSUM modificato basato su tre pilastri fondamentali:

• Stima Empirica di $\mu_0$:
  Utilizzando una sequenza di addestramento iniziale di lunghezza $n_0$ (generata prima di qualsiasi cambiamento), viene calcolata una stima empirica della distribuzione pre-cambiamento $\hat{\mu}_0$. Per sorgenti Markoviane di primo ordine, questa stima si basa sulle frequenze di transizione tra simboli e sulle frequenze marginali dei simboli stessi.
• Codici Universali per $\mu_1$:
  Per la distribuzione post-cambiamento sconosciuta, viene utilizzata una funzione di lunghezza di codice universale (come i codici Lempel-Ziv o Context Tree Weighting). La lunghezza del codice $L(x)$ funge da sostituto per il log-verosimiglianza $-\log \mu_1(x)$, sfruttando la proprietà di universalità puntuale forte.
• Test Modificato:
  Il test CUSUM viene ridefinito come:
  $$\max_{1 \le k \le n} \left( -L(x_{n_0+k}^{n_0+n}) - \log \hat{\mu}_0(x_{n_0+k}^{n_0+n}) - n\lambda \right) \ge \log \gamma$$
  dove:
  • $L(\cdot)$ è la lunghezza del codice universale.
  • $\hat{\mu}_0$ è la stima empirica della distribuzione pre-cambiamento.
  • $\lambda$ è un parametro di deriva (drift) scelto per garantire che la statistica del test abbia una deriva negativa sotto l'ipotesi nulla (nessun cambiamento) e positiva sotto l'ipotesi alternativa.
  • $\gamma$ è la soglia di decisione.

Il test si basa sull'ipotesi che la divergenza di Kullback-Leibler tra la distribuzione post-cambiamento e la stima pre-cambiamento sia maggiore di quella tra la distribuzione pre-cambiamento e la sua stessa stima: $D(\mu_1 || \hat{\mu}_0) > D(\mu_0 || \hat{\mu}_0)$.

3. Contributi Chiave

1. Estensione al Caso Markoviano: Il lavoro generalizza i risultati del 2022 (validi per sorgenti i.i.d.) a sorgenti Markoviane stazionarie ed ergodiche che soddisfano le condizioni di mixing di Berk.
2. Gestione dell'Incertezza Bilaterale: Propone un algoritmo che non richiede la conoscenza né di $\mu_0$ né di $\mu_1$, utilizzando una fase di addestramento per $\mu_0$ e codici universali per $\mu_1$.
3. Analisi Asintotica Rigorosa: Dimostra l'ottimalità asintotica del test proposto nel regime in cui il tasso di falsi allarmi tende a zero.
4. Stime di Errore e Tempi di Arresto: Fornisce limiti superiori per la probabilità di errore (falso allarme) e analizza il comportamento del tempo di arresto condizionato alla sequenza di addestramento.

4. Risultati Principali

Gli autori dimostrano teoremi fondamentali riguardanti le prestazioni del test:

• Probabilità di Errore (Falso Allarme):
  Viene dimostrato che la probabilità che il test si arresti erroneamente sotto la distribuzione pre-cambiamento $\mu_0$ è limitata superiormente da una funzione che dipende da $\alpha$ (legato alla soglia) e da termini di errore che tendono a zero man mano che la lunghezza della sequenza di addestramento $n_0$ aumenta.
  $$\mu_0(N(\alpha) < \infty) \le \frac{\alpha}{\beta_1 (2^{\lambda - \log \beta_1} - 1)} \beta_2 + \epsilon_0$$
  dove $\beta_1, \beta_2 \to 1$ e $\epsilon_0 \to 0$ quando $n_0 \to \infty$.

• Terminazione sotto l'Ipotesi Alternativa:
  Il test termina con probabilità 1 quando si verifica un cambiamento ($\mu_1$), purché $\lambda < D(\mu_1 || \hat{\mu}_0)$.

• Ottimalità Asintotica (Criterio di Lorden):
  Il lavoro dimostra che il tempo di rilevamento atteso $E_1(M(\gamma))$ è asintoticamente ottimale rispetto al limite inferiore di Lorden. Nello specifico, per $\gamma \to \infty$:
  $$E_1(M(\gamma)) \sim (1+\vartheta) \inf_{S \in \mathcal{S}_\gamma} E_1(S)$$
  dove $\vartheta$ può essere scelto arbitrariamente vicino a 0. Questo significa che il ritardo di rilevamento del test proposto è quasi uguale a quello del test ottimo (che richiederebbe la conoscenza delle distribuzioni), a patto che la stima empirica $\hat{\mu}_0$ sia sufficientemente accurata (grande $n_0$).

5. Significato e Implicazioni

Questo studio è significativo perché colma un divario teorico importante nel rilevamento dei cambiamenti:

• Realismo Applicativo: Rimuove l'assunzione irrealistica della conoscenza delle distribuzioni, rendendo l'algoritmo applicabile a scenari dinamici complessi come le reti di comunicazione o i sistemi industriali.
• Robustezza: L'uso di codici universali e stime empiriche rende il metodo robusto contro la mancanza di modelli parametrici precisi.
• Fondamento Teorico: Estende la teoria dell'ottimalità di Lorden e i risultati di Lai al contesto Markoviano con parametri sconosciuti, fornendo un quadro matematico solido per futuri sviluppi.

In conclusione, gli autori hanno dimostrato che è possibile ottenere prestazioni ottimali nel rilevamento di cambiamenti anche quando le distribuzioni sono sconosciute e i dati presentano memoria (Markoviani), utilizzando un approccio ibrido di stima empirica e compressione dati universale.