Classifier-Based Nonparametric Sequential Hypothesis Testing

Titre : Tests d'hypothèses séquentiels non paramétriques basés sur des classifieurs

1. Problématique

Le papier aborde le problème de la construction de tests séquentiels de puissance un (power-one tests) où les classes d'hypothèses nulle ($H_0$) et alternative ($H_1$) ne sont pas définies par des modèles paramétriques explicites, mais sont spécifiées indirectement via des données historiques ou hors ligne (offline).

• Contexte : On dispose d'un jeu de données hors ligne provenant de $L+1$ distributions $\{P_0, P_1, \dots, P_L\}$.
• Objectif : À partir d'un flux de données non étiquetées $\{X_t\}_{t \ge 1}$ i.i.d. $\sim P_\theta$, décider entre :
  • $H_0 : \theta = 0$ (la distribution est $P_0$).
  • $H_1 : \theta \in \{1, \dots, L\}$ (la distribution est l'une des alternatives).
• Contraintes : Les distributions réelles sont inconnues et complexes (images, texte, etc.), rendant l'estimation empirique directe impossible ou coûteuse. L'approche doit être non paramétrique et s'adapter dynamiquement au nombre d'échantillons nécessaires.
• Critère de performance : Le test doit satisfaire le critère niveau-$\alpha$ et puissance un :
  • Probabilité de rejeter $H_0$ à tort (sous $H_0$) $\le \alpha$.
  • Probabilité de rejeter $H_0$ correctement (sous $H_1$) = 1 (arrêt presque sûr).

2. Méthodologie

Les auteurs proposent un cadre général basé sur l'apprentissage automatique, utilisant un classifieur multi-classes entraîné sur les données hors ligne pour guider le test séquentiel.

A. Condition de Séparabilité
Le cadre repose sur l'hypothèse qu'il existe un classifieur $g$ (appartenant à une famille $\mathcal{G}$) capable de distinguer les distributions. Pour une distribution $P_\theta$, la probabilité que $g(X) = \theta$ doit être strictement supérieure à la probabilité que $g(X) = m$ pour tout $m \neq \theta$.

B. Construction du Test (Processus e)
Le test utilise le paradigme du "testing-by-betting" (test par paris) pour construire un processus e (e-process), qui est une martingale non négative sous l'hypothèse nulle.

1. Phase d'entraînement : Un classifieur $g$ est entraîné sur les données hors ligne $\{T^N_\vartheta\}$ pour prédire l'étiquette (hypothèse) d'un échantillon.
2. Phase de test séquentiel :
   • À chaque instant $t$, un échantillon $X_t$ est observé et passé dans le classifieur pour obtenir une prédiction $g(X_t)$.
   • On maintient une estimation empirique $\hat{j}_t$ de la classe la plus fréquente parmi les prédictions passées.
   • On construit un processus de richesse $W_n$ (le processus e) en comparant la prédiction actuelle à la classe nulle ($0$) et à la classe majoritaire estimée ($\hat{j}_t$).
   • La mise de fonds (betting) est ajustée dynamiquement via un mélange de paramètres de pari $\lambda \in (-1, 0]$.
3. Règle d'arrêt : Le test s'arrête au premier instant $\tau$ où le processus de richesse dépasse un seuil $1/\alpha$ :
   $$\tau = \inf \{ n \ge 1 : W_n \ge 1/\alpha \}$$
   Si $\tau < \infty$, on rejette $H_0$.

C. Identification de la distribution
Le mécanisme permet non seulement de rejeter $H_0$, mais aussi d'identifier l'index de la distribution sous-jacente $\theta$ presque sûrement lorsque le nombre d'échantillons augmente.

3. Contributions Clés et Résultats Théoriques

A. Garanties du Test (Théorème 3.2)

• Contrôle d'erreur : Sous l'hypothèse nulle, la probabilité d'arrêt est bornée par $\alpha$ (grâce à l'inégalité de Ville).
• Puissance un : Sous toute hypothèse alternative, le test s'arrête presque sûrement.
• Temps d'arrêt attendu : Les auteurs établissent une borne supérieure non asymptotique pour le temps d'arrêt attendu sous l'alternative :
  $$E_\theta[\tau] = O\left( \frac{\log(1/(\alpha \Delta_\theta))}{\Delta_\theta^2} \right)$$
  où $\Delta_\theta$ est le gap de séparabilité (la différence entre la probabilité de prédire la bonne classe et la meilleure classe erronée). Plus le classifieur est performant (grand $\Delta_\theta$), plus le test est rapide.

B. Analyse de la Phase d'Entraînement (Section 3.2)

• Attainabilité empirique : Ils démontrent qu'un classifieur séparable peut être obtenu empiriquement via la minimisation du risque empirique (ERM) si la taille de l'échantillon d'entraînement $N$ est suffisamment grande.
• Bornes inférieures : Ils établissent une borne inférieure nécessaire sur $N$ en fonction de la difficulté de séparation des distributions (divergence de Kullback-Leibler). Plus les distributions sont proches, plus il faut de données d'entraînement.
• Limite minimax : Une borne inférieure minimax sur le temps d'arrêt est établie, montrant l'impact conjoint de la taille des données d'entraînement ($N$) et de la capacité de la famille de classifieurs ($\mathcal{G}$).

C. Extensions

1. Décalage de distribution (Training-Testing Mismatch) : Le test reste valide si la distribution de test diffère légèrement de celle d'entraînement, à condition que le classifieur reste séparable sur la nouvelle distribution. La robustesse dépend de la force du gap de séparabilité initial.
2. Détection de changement séquentiel (SCD) : Le cadre est adapté pour détecter un changement de distribution à un instant inconnu $T$. Le temps de détection attendu conserve les mêmes propriétés d'optimalité asymptotique.

4. Résultats Empiriques

Les auteurs valident leurs théories sur des données synthétiques (Gaussiennes) et réelles (CIFAR-10 avec VGG16) :

• Validation du temps d'arrêt : La relation entre le niveau de confiance $\alpha$ et le temps d'arrêt moyen suit la tendance quadratique théorique prédite ($O(\log(1/\alpha)/\Delta^2)$).
• Robustesse : Le test maintient ses performances même avec un décalage de distribution modéré, confirmant les bornes théoriques sur la séparabilité.
• Mélange de classifieurs : Une expérience montre que combiner plusieurs classifieurs (via un mélange de processus e) permet de réduire le temps d'arrêt moyen par rapport à un classifieur unique, suggérant une direction future pour l'agrégation adaptative.

5. Signification et Impact

Ce travail est significatif pour plusieurs raisons :

• Première étude non paramétrique séquentielle avec données hors ligne : Contrairement aux travaux antérieurs qui supposaient des modèles paramétriques ou des données d'entraînement en ligne, cette méthode exploite des données historiques fixes pour des tests séquentiels.
• Pont entre ML et Statistiques : L'utilisation de classifieurs modernes (Deep Learning) comme composant central d'un test statistique rigoureux permet de traiter des données de haute dimension (images, texte) là où les méthodes classiques échouent.
• Garanties "Anytime-Valid" : La méthode fournit des garanties de contrôle d'erreur strictes à tout moment, ce qui est crucial pour les applications en temps réel (ex: détection d'anomalies, détection de contenu généré par IA).
• Optimalité : Bien que l'optimalité générale reste une question ouverte, les auteurs prouvent l'optimalité asymptotique pour certaines instances de problèmes, reliant la difficulté du test à la séparabilité du classifieur.

En résumé, ce papier propose un cadre robuste et théoriquement fondé pour effectuer des tests d'hypothèses séquentiels dans des environnements complexes où les modèles de probabilité sont inconnus, en s'appuyant sur la puissance des classifieurs modernes entraînés sur des données historiques.