Classifier-Based Nonparametric Sequential Hypothesis Testing

Probleemstelling

Het artikel adresseert het probleem van het opstellen van sequentiële hypothesetoetsen waarbij de nulhypothese ($H_0$) en de alternatieve hypothesen ($H_1$) niet expliciet worden gedefinieerd door parametrische modellen, maar indirect worden gespecificeerd via historische of offline data.

• Context: Gegeven is een offline dataset bestaande uit observaties van $L+1$ verdelingen $\{P_0, P_1, \dots, P_L\}$.
• Doel: Het is de taak om te beslissen tussen de nulhypothese $H_0: \theta = 0$ (waarbij data uit $P_0$ komt) en de alternatieve hypothese $H_1: \theta \in \{1, \dots, L\}$ (waarbij data uit een onbekende $P_\theta$ komt).
• Uitdaging: De onderliggende verdelingen zijn onbekend en kunnen complex zijn (bijv. tekst of beelden), waardoor klassieke likelihood-ratio tests niet direct toepasbaar zijn. De auteurs focussen op een niet-parametrische setting met een power-one criterium: de test moet de nulhypothese met kans 1 verwerpen als deze onwaar is, terwijl de kans op een valse alarm (stoppen in eindige tijd onder $H_0$) begrensd is door een niveau $\alpha$.

Methodologie

De kern van de voorgestelde methode is het gebruik van een meerklassificator (multi-class classifier) die is getraind op de offline dataset om een sequentiële test te sturen.

1. Trainingsfase:

   • Een classifier $g$ wordt getraind op de offline data $\{T^N_\vartheta\}$ om te leren onderscheid maken tussen de $L+1$ verdelingen.
   • Er wordt een scheidbaarheidscriterium (separability condition) geïntroduceerd: de classifier $g$ moet zodanig zijn dat voor elke verdeling $P_\theta$, de kans dat $g(X) = \theta$ groter is dan de kans op elke andere label $m \neq \theta$.

2. Sequentiële Testfase (Online):

   • De test verwerkt een stroom van nieuwe, ongelabelde data $\{X_t\}$.
   • De classifier $g$ voorspelt voor elke observatie $X_t$ een label $g(X_t)$.
   • Er wordt een e-proces (e-process) geconstrueerd, gebaseerd op het "testing-by-betting" paradigma. Dit is een martingaal dat de bewijslast tegen de nulhypothese kwantificeert.
   • Het e-proces: De "vermogens" (wealth) $W_n$ wordt bijgewerkt door te wedden op de voorspellingen. Als de voorspelling van de classifier afwijkt van de meest voorkomende voorspelling in het verleden (of de nul-label), wordt er gewed.
   • Stopregel: De test stopt en verwerpt $H_0$ zodra het e-proces een drempel van $1/\alpha$ overschrijdt: $\tau = \inf \{n \ge 1 : W_n \ge 1/\alpha\}$.

3. Identificatie:

   • Naast het verwerpen van de nulhypothese, identificeert de procedure bijna zeker (almost surely) de ware onderliggende verdeling $\theta$ door de meest frequente voorspelling $\hat{j}_t$ te volgen.

Belangrijkste Bijdragen

• Algemene Framework: Een methode om sequentiële power-one tests te ontwerpen voor niet-parametrische problemen met behulp van offline getrainde classifiers, zonder sterke aannames over de verdelingen.
• Theoretische Garanties:
  • Bewijs dat de stopregel voldoet aan het niveau-$\alpha$ criterium (gecontroleerd door Ville's ongelijkheid).
  • Bewijs van power-one (kans 1 op stoppen onder $H_1$).
  • Afleiding van een niet-asymptotische bovengrens voor de verwachte stoptijd, die afhankelijk is van de "scheidingskloof" ($\Delta_\theta$) van de classifier.
  • Bewijs dat de procedure de ware index van de verdeling bijna zeker identificeert.
• Analyse van Trainingsdata:
  • Afleiding van voldoende en noodzakelijke voorwaarden voor de grootte van de offline dataset ($N$) om een scheidende classifier te garanderen.
  • Een minimax ondergrens voor de type-II fout (staartwaarschijnlijkheid van de stoptijd), die de invloed van de datasetgrootte en de capaciteit van de classifier-familie kwantificeert.
• Extensies:
  • Train-Test Mismatch: Analyse van het geval waarin de testdata verschilt van de trainingsdata (distributieverplaatsing). De test blijft geldig zolang de mismatch binnen bepaalde grenzen blijft die worden bepaald door de scheidbaarheid van de classifier.
  • Sequentiële Changepoint Detectie: Toepassing van de methode om plotselinge veranderingen in een datastroom te detecteren.

Resultaten

• Theoretisch: De verwachte stoptijd wordt bepaald door $O\left(\frac{\log(1/(\alpha \Delta_\theta))}{\Delta_\theta^2}\right)$. Dit betekent dat hoe beter de classifier de klassen kan scheiden (groter $\Delta_\theta$), hoe sneller de test stopt.
• Empirisch:
  • Experimenten met synthetische data (Gaussische verdelingen) en real-world data (CIFAR-10 met VGG16 en MLP) bevestigen dat de empirische stoptijden overeenkomen met de theoretische schalingstrends.
  • De methode toont robustheid bij kleine distributieverplaatsingen tussen training en testen.
  • Ensemble Effect: Het gebruik van een mengsel van meerdere classifiers (parallelle e-processen) resulteert in een kortere gemiddelde stoptijd dan het gebruik van een enkele classifier, wat suggereert dat heterogeniteit in classifiers kan worden benut voor betere prestaties.

Significantie

Dit werk is significant omdat het een brug slaat tussen machine learning (classificatie) en sequentiële statistiek. Traditionele sequentiële tests vereisen vaak kennis van de exacte verdelingen, wat in de praktijk (bijv. bij het detecteren van AI-generatie of anomalieën in beelden) zelden het geval is.

Door classifiers te gebruiken als een "dimensiereductie"-mechanisme, maakt het papier het mogelijk om robuuste, adaptieve tests uit te voeren op complexe, hoge-dimensionale data zonder parametrische aannames. De focus op offline training maakt het toepasbaar in scenario's waar historische data beschikbaar is, maar geen online trainingsdata (in tegenstelling tot eerdere werken die online training vereisen). De resultaten bieden een theoretisch onderbouwd kader voor het gebruik van moderne ML-modellen in strikte statistische toetsingsprocedures.