Classifier-Based Nonparametric Sequential Hypothesis Testing

1. Problemstellung

Das Paper adressiert das Problem des sequentiellen Hypothesentestens in einem nichtparametrischen Setting, bei dem die Null- und Alternativhypothesen nicht durch explizite parametrische Modelle definiert sind, sondern indirekt über historische (offline) Daten.

• Gegeben: Ein Offline-Datensatz, der Beobachtungen aus $L+1$ Verteilungen $\{P_0, P_1, \dots, P_L\}$ enthält.
• Ziel: Eine neue, ungelabelte Datenstream $\{X_t : t \ge 1\}$, die i.i.d. aus einer unbekannten Verteilung $P_\theta$ stammt, zu analysieren.
• Hypothesen:
  • $H_0: \theta = 0$ (Nullhypothese).
  • $H_1: \theta \in [L] := \{1, \dots, L\}$ (Alternativhypothese, wobei $\theta$ eine der $L$ anderen Verteilungen ist).
• Herausforderung: Da die wahren Verteilungen unbekannt sind, können klassische likelihood-basierte sequentielle Tests (wie der Wald-Test) nicht direkt angewendet werden. Zudem soll der Test nichtparametrisch sein, d.h. er darf keine starken Annahmen über die Verteilungsfamilie treffen.
• Kriterium: Der Test soll ein Level-$\alpha$ Power-One-Test sein. Das bedeutet:
  1. Unter $H_0$ ist die Wahrscheinlichkeit, in endlicher Zeit zu stoppen (falscher Alarm), $\le \alpha$.
  2. Unter $H_1$ ist die Wahrscheinlichkeit, in endlicher Zeit zu stoppen, gleich 1 (Power = 1).

2. Methodik

Die Autoren schlagen einen allgemeinen Rahmen vor, der Multiklassen-Klassifikatoren nutzt, die auf den Offline-Daten trainiert wurden, um die komplexen Datenräume auf diskrete Labels zu reduzieren.

A. Trennbarkeit (Separability)

Ein zentrales Konzept ist die Trennbarkeitsbedingung. Eine Verteilungstuple $\mathcal{P}$ gehört zur Klasse $\mathcal{P}_{sep}$, wenn es einen Klassifikator $g$ aus einer Familie $\mathcal{G}$ gibt, der die Verteilungen so trennen kann, dass für jede wahre Verteilung $P_\theta$ die Wahrscheinlichkeit, dass $g(X) = \theta$ ist, höher ist als für jede andere Klasse $m \neq \theta$.
$$P_\theta(g(X) = \theta) > \max_{m \neq \theta} P_\theta(g(X) = m)$$

B. Der vorgeschlagene Stopp-Regel (E-Prozess)

Der Test basiert auf dem Testing-by-Betting-Paradigma und konstruiert einen E-Prozess (e-process), der als Martingal unter der Nullhypothese fungiert.

1. Training: Ein Klassifikator $g$ wird auf den Offline-Daten trainiert.
2. Online-Phase: Zu jedem Zeitpunkt $t$ wird ein Datenpunkt $X_t$ durch $g$ geführt, um eine Vorhersage $\hat{y}_t = g(X_t)$ zu erhalten.
3. Schätzung des dominanten Labels: Es wird ein laufender Schätzer $\hat{j}_t$ für das am häufigsten vorhergesagte Label basierend auf der Historie $\{g(X_i)\}_{i=1}^{t-1}$ berechnet.
4. Wettprozess (E-Prozess): Ein Vermögensprozess $W_n$ wird aufgebaut, der das „Wetten" gegen die Nullhypothese simuliert.
   • Wenn $g(X_t) = 0$ (Nullhypothese), bleibt $W_n$ klein.
   • Wenn $g(X_t) \neq 0$ und insbesondere wenn $g(X_t)$ dem geschätzten dominanten Label $\hat{j}_t$ entspricht, wächst $W_n$ exponentiell.
   • Der Prozess wird als Integral über einen Bereich von Wettparametern $\lambda \in (-1, 0]$ definiert, um eine Mischung (Mixture) zu bilden, was die Schranken für die erwartete Stoppzeit verbessert.
5. Stoppregel: Der Test stoppt bei $\tau = \inf \{n \ge 1 : W_n \ge 1/\alpha\}$.

C. Identifikation

Neben dem Verwerfen der Nullhypothese identifiziert das Verfahren fast sicher (mit Wahrscheinlichkeit 1) den wahren Index $\theta$ der zugrundeliegenden Verteilung, sobald genügend Daten vorliegen.

3. Wichtige Beiträge und Ergebnisse

Theoretische Garantien

• Level-$\alpha$ und Power-One: Unter der Trennbarkeitsbedingung erfüllt der Test die Level-$\alpha$-Bedingung (via Ville-Ungleichung) und die Power-One-Bedingung (via Martingal-Konzentrationsungleichungen).
• Erwartete Stoppzeit: Die Autoren leiten eine nicht-asymptotische Obergrenze für die erwartete Stoppzeit unter $H_1$ her:
  $$E_\theta[\tau] = O\left( \frac{\log(1/(\alpha \Delta_\theta))}{\Delta_\theta^2} \right)$$
  wobei $\Delta_\theta$ der „Gap" (die Differenz) zwischen der Wahrscheinlichkeit der korrekten Klassifikation und der besten falschen Klassifikation ist. Je besser der Klassifikator trennt, desto schneller stoppt der Test.
• Identifikation: Es wird gezeigt, dass $\hat{j}_t$ gegen den wahren Index $\theta$ konvergiert.

Rolle des Offline-Trainings

• Ausreichende Stichprobengröße: Es wird eine hinreichende Bedingung für die Größe des Offline-Datensatzes $N$ hergeleitet, damit ein separabler Klassifikator empirisch gefunden werden kann (basierend auf VC-Dimension und ERM-Theorie).
• Notwendige Grenzen: Eine untere Schranke für $N$ wird gezeigt, die von der Divergenz zwischen den Verteilungen abhängt. Je ähnlicher die Verteilungen, desto mehr Trainingsdaten werden benötigt.
• Minimax-Untere Schranke: Eine untere Schranke für die Typ-II-Fehlerwahrscheinlichkeit (bzw. die Stoppzeit) wird etabliert, die die Abhängigkeit von der Trainingsgröße $N$, der Schwellenwert $\alpha$ und der Kapazität der Klassifikatorfamilie $\mathcal{G}$ zeigt.

Erweiterungen

1. Train-Test-Mismatch: Der Test bleibt robust, wenn die Verteilung der Testdaten leicht von den Trainingsdaten abweicht (Distribution Shift), solange die Trennbarkeit des Klassifikators erhalten bleibt. Die Autoren geben eine Bedingung für die maximale erlaubte Abweichung ($\epsilon$) basierend auf dem Trennbarkeits-Gap.
2. Sequentielle Change-Point Detection (SCD): Der Rahmen wird auf die Erkennung von Änderungen in Datenströmen erweitert. Hier wird ein „e-detector" verwendet, der mehrere parallele Tests startet, um einen unbekannten Änderungspunkt zu detektieren.

4. Empirische Validierung

Die Autoren validieren ihre Theorien mit synthetischen Daten (Gaussian-Verteilungen) und realen Daten (CIFAR-10 mit VGG16 und MLP).

• Stoppzeit: Die empirische durchschnittliche Stoppzeit folgt dem theoretisch vorhergesagten Skalierungstrend ($O(\log(1/\alpha)/\Delta^2)$).
• Identifikation: Bei kleinerem $\alpha$ (strengerer Test) steigt die Genauigkeit der Identifikation des wahren $\theta$ gegen 1.
• Robustheit: Bei simuliertem Distribution Shift (Train-Test-Mismatch) bleibt der Test gültig, solange der Shift innerhalb der durch den Trennbarkeits-Gap definierten Grenzen liegt. Die Stoppzeit nimmt erwartungsgemäß zu, wenn die Verteilungen sich überlappen.
• Klassifikator-Mischung: Ein Experiment zeigt, dass die Kombination mehrerer Klassifikatoren (durch Mischen der E-Prozesse) zu einer kürzeren erwarteten Stoppzeit führen kann als die Verwendung eines einzelnen Klassifikators, was auf zukünftige Arbeiten zu adaptiven Gewichtungsmechanismen hindeutet.

5. Bedeutung und Fazit

Dieses Paper schließt eine wichtige Lücke in der sequentiellen Hypothesenprüfung:

1. Brücke zwischen ML und Statistik: Es verbindet moderne Klassifikationsmodelle (Deep Learning) mit rigoroser sequentieller statistischer Inferenz.
2. Praktische Anwendbarkeit: Es ermöglicht Tests in Szenarien, wo keine parametrischen Modelle verfügbar sind, aber große historische Datensätze existieren (z.B. Erkennung von KI-generiertem Text, Bildklassifizierung).
3. Theoretische Fundierung: Es liefert die ersten nicht-asymptotischen Garantien für nichtparametrische sequentielle Tests mit Offline-Daten, einschließlich der Analyse der Auswirkungen von Trainingsdatenmenge und Klassifikator-Komplexität.
4. Robustheit: Die Behandlung von Train-Test-Mismatches macht das Verfahren für reale Anwendungen attraktiv, wo sich Datenverteilungen oft ändern.

Zusammenfassend bietet das Paper einen allgemeinen, theoretisch fundierten und empirisch validierten Rahmen für effiziente sequentielle Entscheidungen in komplexen, datengetriebenen Umgebungen.