Optimized Sequential Testing for Binary Ensemble Classifiers

Énoncé du problème
Les classifieurs d'ensemble, tels que les forêts aléatoires, combinent les prédictions de plusieurs modèles de base (par exemple, des arbres de décision) via un vote majoritaire pour atteindre une grande précision. Cependant, les ensembles plus volumineux entraînent des coûts computationnels importants lors de l'inférence, ce qui est problématique pour les appareils à faible puissance ou les applications à haute fréquence. Le problème central abordé est la manière de réduire le coût de calcul au moment du test des classifieurs d'ensemble binaires sans dégrader significativement leur précision. Plus précisément, les auteurs étudient des stratégies consistant à interrompre l'évaluation des modèles de base de manière séquentielle dès qu'une « majorité claire » émerge, plutôt que d'exécuter l'ensemble des $N$ modèles. L'objectif est de minimiser le nombre attendu de modèles de base exécutés (temps d'exécution) tout en contrôlant strictement le « taux de désaccord » — la probabilité que l'ensemble à arrêt précoce produise un résultat différent de celui de l'ensemble complet.

Méthodologie
Le document formalise le problème de l'arrêt précoce comme une tâche de test séquentiel où l'état est défini par $(i, j)$, représentant $i$ modèles de base exécutés et $j$ votes positifs. Les auteurs supposent que les modèles de base sont exécutés dans un ordre aléatoire, permettant l'utilisation d'une distribution hypergéométrique pour modéliser la probabilité d'atteindre un état donné, sans supposer l'indépendance entre les modèles de base.

Pour trouver des stratégies d'arrêt optimales, les auteurs proposent trois cadres d'optimisation distincts, tous formulés sous forme de programmes linéaires (PL) pour garantir l'efficacité computationnelle :

1. Minimax : Minimise le pire cas du temps d'exécution attendu sous une contrainte de pire cas du taux de désaccord. Cette approche ne nécessite aucune connaissance préalable de la distribution des votes positifs ($n$).
2. Minimean : Minimise le temps d'exécution attendu sous une contrainte de taux de désaccord attendu, en supposant une distribution $\hat{D}$ connue ou estimée pour $n$.
3. Minimixed : Minimise le temps d'exécution attendu sous une contrainte de taux de désaccord dans le pire des cas, en supposant une distribution pour $n$.

Les auteurs démontrent que les problèmes d'optimisation non linéaires originaux peuvent être reformulés en utilisant des variables de décision de probabilité conditionnelle ($p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$). Cette reformulation transforme le problème en un programme linéaire avec $O(N^3)$ variables de décision, soluble efficacement même pour des ensembles comprenant des centaines d'arbres. Les stratégies résultantes sont largement déterministes, suivant une règle simple d'« enveloppe » : s'arrêter si le nombre de votes positifs dépasse un seuil supérieur ou tombe en dessous d'un seuil inférieur à une étape $i$ spécifique.

Contributions clés

• Formulation théorique : Le papier fournit un cadre mathématique rigoureux pour l'arrêt précoce dans les ensembles de vote majoritaire, définissant formellement les stratégies d'arrêt et les métriques (temps d'exécution et taux de désaccord).
• Solutions de programmation linéaire optimales : Les auteurs montrent que les stratégies d'arrêt optimales pour trois notions différentes d'optimalité (minimax, minimean, minimixed) peuvent être trouvées en résolvant des programmes linéaires. Cela contraste avec les travaux antérieurs qui reposaient souvent sur des heuristiques ou supposaient l'indépendance entre les modèles de base.
• Absence d'hypothèse d'indépendance : Contrairement aux méthodes de test séquentiel pour les ensembles (par exemple, Schwing et al., 2011), cette approche ne suppose pas que les modèles de base soient indépendants, ce qui la rend directement applicable aux forêts aléatoires où les prédictions des arbres sont corrélées.
• Stratégies précalculables : Les auteurs ont précalculé des stratégies optimales pour diverses tailles d'ensembles et taux de désaccord admissibles (ADR), permettant une application immédiate sans ré-optimisation pour chaque nouveau jeu de données (particulièrement pour l'approche minimax).

Résultats empiriques
Les méthodes ont été évaluées sur 27 jeux de données réels provenant du dépôt UCI Machine Learning Repository et des benchmarks proposés par Grinsztajn et al., en utilisant des forêts aléatoires avec $N=101$ arbres.

• Accélération : Sur la plupart des jeux de données, les méthodes proposées ont obtenu des accélérations de 4x ou plus (réduisant le temps d'exécution à 10–20 % de l'ensemble complet) tout en maintenant un taux de désaccord de 0,1 % ($10^{-3}$).
• Variance de la performance : L'approche Minimean (utilisant un ensemble de calibration pour estimer la distribution des votes) a généralement offert les accélérations les plus élevées, suivie de Minimixed, le Minimax étant le plus conservateur.
• Caractéristiques des jeux de données : L'efficacité de l'arrêt précoce est corrélée à la distribution des votes des arbres. Les jeux de données où les arbres votaient massivement pour une classe (distribution bimodale) ont permis un arrêt précoce agressif. À l'inverse, les jeux de données avec des taux d'erreur de base élevés et des distributions de votes centralisées (ex: « Dota2 » et « Hospitalization ») ont montré des accélérations plus faibles, car le consensus était plus difficile à atteindre tôt.
• Comparaison : Les méthodes proposées ont surpassé la méthode de référence de Schwing et al. (2011), qui repose sur des bandes de confiance binomiales et des hypothèses d'indépendance.

Signification et affirmations
Le papier affirme présenter la première méthode permettant d'obtenir des stratégies d'arrêt précoce provablement optimales pour les classifieurs d'ensemble binaires basés sur le vote majoritaire sans supposer l'indépendance entre les modèles de base. Les auteurs soulignent que leur approche permet aux utilisateurs d'entraîner des ensembles plus grands et plus précis, et de compter sur la stratégie d'arrêt pour n'utiliser que les ressources computationnelles nécessaires pour chaque inférence spécifique.

Le papier note modestement ses limites : la méthode est restreinte à la classification binaire et aux ensembles de vote majoritaire non pondérés. Elle ne peut pas être appliquée directement aux problèmes multi-classes, à la régression, ou aux ensembles où les modèles de base ont des poids spécifiques ou des ordres d'exécution requis. De plus, les auteurs suggèrent que bien que la méthode soit compatible avec l'élagage (pruning), les gains pourraient être moins spectaculaires pour les forêts élaguées, car l'élagage vise à réduire la redondance (votes corrélés) qui rend l'arrêt précoce efficace. Des travaux futurs sont suggérés pour étendre la théorie aux ensembles multi-classes et pondérés.