Classifier-Based Nonparametric Sequential Hypothesis Testing

1. Formulazione del Problema

Il lavoro affronta il problema del test di ipotesi sequenziale non parametrico in un contesto in cui le distribuzioni sotto l'ipotesi nulla ($H_0$) e le alternative ($H_1$) non sono specificate analiticamente, ma sono definite indirettamente attraverso dati offline (storici).

• Contesto: Si dispone di un dataset offline composto da osservazioni provenienti da $L+1$ distribuzioni $\{P_0, P_1, \dots, P_L\}$.
• Obiettivo: Data una nuova stream di dati non etichettati $\{X_t : t \ge 1\}$ generata i.i.d. da una distribuzione sconosciuta $P_\theta$, decidere tra:
  • $H_0: \theta = 0$ (Ipotesi nulla).
  • $H_1: \theta \in [L] := \{1, \dots, L\}$ (Ipotesi alternativa, che può essere una qualsiasi delle $L$ distribuzioni alternative).
• Vincoli: Il test deve soddisfare il criterio livello-$\alpha$ e potenza-uno:
  • Livello-$\alpha$: La probabilità di fermarsi in tempo finito sotto $H_0$ deve essere $\le \alpha$.
  • Potenza-uno: La probabilità di fermarsi in tempo finito sotto qualsiasi $H_1$ deve essere 1.
• Sfida: A differenza dei test classici parametrici, qui le distribuzioni sono sconosciute e complesse (es. immagini, testo), rendendo impossibile la stima diretta della verosimiglianza. L'unico accesso alle distribuzioni è tramite i dati di addestramento offline.

2. Metodologia Proposta

Gli autori propongono un approccio basato su un classificatore multiclasse addestrato sui dati offline, che funge da meccanismo di riduzione della dimensionalità, mappando lo spazio complesso dei dati in uno spazio discreto di etichette.

A. Costruzione del Test (E-processo)

Il cuore del metodo è la costruzione di un e-processo (un processo di ricchezza basato sul paradigma "testing-by-betting") che accumula evidenza contro l'ipotesi nulla.

1. Addestramento: Si addestra un classificatore $g \in \mathcal{G}$ sui dati offline $\{T^N_\vartheta\}$ per distinguere tra le $L+1$ distribuzioni.
2. Fase Online: A ogni istante $t$, il dato $X_t$ viene passato al classificatore $g$, producendo una previsione $g(X_t) \in \{0, \dots, L\}$.
3. Aggiornamento del Martingala: Si costruisce un processo di ricchezza $W_n$ basato sul confronto tra la previsione corrente e una stima della classe più frequente osservata finora ($\hat{j}_t$).
   • Se $H_0$ è vera, le previsioni si concentrano sull'etichetta 0, mantenendo $W_n$ basso.
   • Se $H_1$ è vera, le previsioni si concentrano su un'etichetta alternativa $\theta$, facendo crescere $W_n$ esponenzialmente.
4. Regola di Arresto: Il test si ferma al primo istante $\tau$ in cui $W_n \ge 1/\alpha$.

B. Condizione di Separabilità

Il metodo richiede che le distribuzioni appartengano a una famiglia distinguibile ($\mathcal{P}_{sep}$). Formalmente, deve esistere un classificatore $g$ tale che per ogni distribuzione $P_\theta$, la probabilità che $g$ predica correttamente $\theta$ sia strettamente maggiore della probabilità di predire qualsiasi altra etichetta $m \neq \theta$. Questo "margine di separabilità" ($\Delta_\theta$) è cruciale per la velocità di convergenza.

3. Contributi Chiave e Risultati Teorici

Garanzie Statistiche

• Controllo dell'Errore di Tipo I: Grazie alla disuguaglianza di Ville, il test garantisce che $P_0(\tau < \infty) \le \alpha$, indipendentemente dalla distribuzione sottostante, purché il classificatore sia separabile.
• Potenza Uno: Sotto $H_1$, il test si ferma quasi certamente in tempo finito.
• Identificazione dell'Alternativa: Il metodo non solo rifiuta $H_0$, ma identifica quasi certamente l'indice della vera distribuzione sottostante ($\theta$) man mano che il test procede.

Tempi di Arresto Atteso

Gli autori derivano un limite superiore non asintotico per il tempo di arresto atteso sotto l'alternativa:
$$E_\theta[\tau] = O\left( \frac{\log(1/(\alpha \Delta_\theta))}{\Delta_\theta^2} \right)$$
Dove $\Delta_\theta$ rappresenta il margine di separabilità del classificatore. Questo risultato mostra che un classificatore più discriminante riduce drasticamente il numero di campioni necessari.

Analisi del Ruolo dei Dati Offline

• Sufficienza: Viene dimostrato che, se la famiglia di classificatori è PAC-learnable e la dimensione del dataset offline $N$ è sufficientemente grande (dipendente dal margine di separabilità e dalla complessità VC), è possibile ottenere un classificatore separabile con alta probabilità.
• Necessità: Vengono stabiliti limiti inferiori (converse) per la dimensione $N$. Se le distribuzioni sono molto simili, è necessario un dataset di addestramento più grande per garantire l'identificabilità uniforme.
• Limite Minimax: Viene fornito un limite inferiore minimax per la probabilità di errore di tipo II (coda del tempo di arresto), che dipende esplicitamente da $N$, dalla famiglia di classificatori e dal livello di confidenza $\alpha$.

4. Estensioni e Applicazioni

Mismatch Training-Testing

Il lavoro analizza il caso in cui la distribuzione dei dati di test ($\tilde{P}$) differisce leggermente da quella di addestramento ($P$). Viene dimostrato che il test rimane valido se lo spostamento (misurato tramite divergenza KL o TV sulle probabilità indotte dal classificatore) è sufficientemente piccolo da non violare la condizione di separabilità.

Rilevamento di Cambiamenti (Change-Point Detection)

Il framework è esteso al problema del Sequential Change-Point Detection (SCD). Il test viene adattato per monitorare un flusso di dati e rilevare un cambiamento improvviso da una distribuzione pre-cambiamento ($P_0$) a una post-cambiamento ($P_\theta$) a un tempo sconosciuto $T$. Vengono forniti limiti sul ritardo di rilevamento atteso.

5. Risultati Sperimentali

Gli autori validano la teoria sia con dati sintetici (distribuzioni Gaussiane) che reali (CIFAR-10 con VGG16).

• Conferma Teorica: I tempi di arresto medi osservati seguono la tendenza di scaling teorica ($O(\log(1/\alpha)/\Delta^2)$).
• Robustezza: Il test mantiene le proprietà anche in presenza di piccoli mismatch tra distribuzione di addestramento e di test.
• Misti di Classificatori: Un esperimento mostra che combinare i processi di scommessa di più classificatori (mixture of e-processes) può ridurre il tempo di arresto atteso rispetto all'uso di un singolo classificatore, suggerendo che l'eterogeneità dei modelli può essere sfruttata per migliorare le prestazioni.

6. Significato e Impatto

Questo lavoro è significativo perché:

1. Colma un vuoto teorico: È uno dei primi studi a formalizzare il test di ipotesi sequenziale non parametrico utilizzando dataset offline fissi, superando le limitazioni dei metodi parametrici classici.
2. Integrazione ML-Statistica: Fornisce un ponte rigoroso tra l'apprendimento automatico (uso di classificatori neurali complessi) e la statistica sequenziale (garanzie di errore rigorose tramite e-processi).
3. Applicabilità Pratica: Offre una soluzione praticabile per scenari reali come la rilevazione di testi generati da LLM o l'analisi di immagini, dove i modelli distributivi esatti sono sconosciuti ma sono disponibili grandi quantità di dati storici.
4. Flessibilità: Il framework è robusto a mismatch distribuzionali e adattabile al rilevamento di anomalie/cambiamenti, rendendolo utile per sistemi di monitoraggio in tempo reale.

In sintesi, gli autori dimostrano che un classificatore addestrato su dati offline può essere utilizzato per costruire test sequenziali con garanzie statistiche rigorose, trasformando un problema di inferenza non parametrica complessa in un problema di scommessa gestibile su spazi discreti.