🤖 machine learning

PINE: Pruning Boosted Tree Ensembles with Conformal In-Distribution Prediction Equivalence

L'article présente PINE, une nouvelle méthode d'élagage pour les ensembles d'arbres qui exploite l'étalonnage conforme pour garantir l'équivalence des prédictions au sein d'une région in-distribution contrôlable, atteignant des taux de compression jusqu'à 30 % supérieurs aux techniques d'élagage fidèles existantes tout en maintenant une précision de prédiction comparable.

Auteurs originaux : Haruki Yajima, Yusuke Matsui

Publié 2026-05-28

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Haruki Yajima, Yusuke Matsui

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez une équipe de 30 détectives experts (un « ensemble d'arbres ») travaillant ensemble pour résoudre une énigme. Ils sont incroyablement précis, mais ils sont aussi lents, coûteux à maintenir sur la paie et occupent beaucoup d'espace de bureau. Vous voulez licencier certains d'entre eux pour économiser de l'argent, mais vous êtes terrifié à l'idée que si vous laissez partir le mauvais détective, l'équipe pourrait commencer à donner de mauvaises réponses.

C'est le problème que PINE résout.

Voici l'histoire du fonctionnement de PINE, en utilisant des analogies simples :

Le Problème : Le « Parfait » contre le « Pratique »

Actuellement, il existe deux façons de réduire cette équipe de détectives :

L'Approche « Priorité à la Précision » : Vous licenciez les détectives qui semblent les moins utiles. Cela économise beaucoup d'argent (forte compression), mais parfois l'équipe restante commence à commettre des erreurs qu'elle n'aurait pas commises auparavant. C'est comme licencier un spécialiste qui ne se présente qu'une fois par an, pour réaliser ensuite qu'il était le seul à savoir gérer cette urgence spécifique.
L'Approche « Fidèle » (L'Ancienne Méthode) : Vous promettez que la nouvelle équipe, plus petite, donnera la réponse exacte que la grande équipe donnerait pour chaque scénario possible dans l'univers, même ceux qui ne sont jamais arrivés et ne le seront jamais.
- Le Problème : Pour tenir cette promesse, vous ne pouvez pas licencier beaucoup de détectives. Vous devez garder toute l'équipe au cas où un scénario étrange et impossible (comme un détective qui est à la fois « marié » et « jamais marié » en même temps) se présenterait. Cela se traduit par des économies très faibles.

La Solution PINE : La Garantie « Réaliste »

PINE (Pruning with In-Distribution Equivalence) dit : « Arrêtons de nous inquiéter des scénarios impossibles. »

Au lieu de promettre que l'équipe sera parfaite pour toute possibilité théorique, PINE promet qu'elle sera parfaite uniquement pour les scénarios réalistes — le genre de cas qui se produisent réellement dans le monde réel.

Le « Score de Plausibilité » (Le Contrôle de Réalité)

PINE utilise un outil spécial appelé un arbre de Chow-Liu pour agir comme un « Contrôle de Réalité ».

Imaginez que les détectives possèdent une carte de la ville montrant où les gens vivent réellement.
Lorsqu'un nouveau cas arrive, PINE vérifie : « Ce cas ressemble-t-il à quelque chose qui appartient à la ville ? »
Si le cas est une situation normale et réaliste (par exemple, une personne avec un emploi et un âge normaux), elle reçoit un « score faible » (c'est plausible).
Si le cas est étrange ou impossible (par exemple, une personne âgée de 200 ans ou ayant 500 années de scolarité), elle reçoit un « score élevé » (c'est improbable).

La « Calibration Conformelle » (Définissant le Filet de Sécurité)

PINE utilise une astuce statistique appelée Prédiction Conformelle pour tracer une ligne dans le sable.

Vous dites à PINE : « Je veux être sûr à 95 % que les cas qui nous importent se trouvent du côté « plausible » de la ligne. »
PINE examine les données passées et trace une frontière. Tout ce qui se trouve à l'intérieur de la frontière est « Monde Réel ». Tout ce qui se trouve à l'extérieur est « Étrange/Impossible ».
La Magie : PINE promet uniquement de maintenir les réponses exactement identiques pour les cas à l'intérieur de cette frontière. Pour les choses étranges à l'extérieur, il ne se soucie pas si les réponses changent.

Le Résultat : Couper le Gras, Garder le Muscle

Parce que PINE ne gaspille pas d'énergie à essayer de gérer des scénarios impossibles (comme une personne qui est à la fois mariée et célibataire), il peut licencier beaucoup plus de détectives que les anciennes méthodes « Fidèles ».

L'Affirmation de l'Article : Dans des tests sur 12 ensembles de données différents, PINE a pu réduire la taille de l'équipe de jusqu'à 30 % de plus que les méthodes « Fidèles » strictes, tout en maintenant la précision sur les données du monde réel tout aussi élevée.
Le Compromis : Vous pouvez ajuster un cadran (appelé $\alpha$ $α$ ).
- Tournez le cadran pour être très strict (faible $\alpha$ ) : Vous gardez une équipe plus grande, mais vous êtes presque certain à 100 % que les réponses sont parfaites pour les cas réels.
- Tournez le cadran pour être plus détendu (élevé $\alpha$ ) : Vous licenciez encore plus de détectives, économisant davantage d'argent, avec un risque légèrement plus élevé (mais toujours contrôlé) d'erreur sur un cas réel.

Résumé

Pensez à PINE comme à un manager intelligent qui dit : « Nous n'avons pas besoin de former notre équipe pour gérer des dragons ou le voyage dans le temps. Ces choses n'existent pas. Licenciions les personnes qui ne savent que combattre des dragons, afin d'économiser de l'argent, tout en promettant que notre équipe résoudra toujours chaque crime réel que nous rencontrons. »

Cela permet aux entreprises de réduire considérablement leurs modèles d'IA coûteux sans briser la confiance que le modèle se comportera correctement sur les données qui comptent réellement.

Résumé technique : PINE – Élagage des ensembles d'arbres boostés avec équivalence de prédiction conformelle in-distribution

1. Énoncé du problème

Les méthodes d'ensembles d'arbres, telles que les forêts aléatoires, les arbres de décision boostés par gradient (GBDT) et XGBoost, sont largement utilisées pour les données tabulaires en raison de leurs fortes performances prédictives et de leur interprétabilité. Cependant, les grands ensembles entraînent des coûts d'inférence élevés et une empreinte mémoire importante, compliquant les tâches en aval telles que la vérification de robustesse et les contrôles d'équité.

L'élagage post-hoc des ensembles est une solution standard, mais les méthodes existantes font face à un compromis entre compression et fidélité (équivalence de prédiction) :

Élagage orienté précision : Les méthodes qui optimisent les compromis précision-compression modifient souvent un sous-ensemble de prédictions. Ce manque de fidélité peut perturber la cohérence décisionnelle dans des domaines à haut risque (par exemple, médecine, finance) où les flux de travail en aval dépendent de sorties spécifiques du modèle.
Élagage fidèle : Des méthodes comme FIPE (Emine et al., 2025) et les ensembles d'arbres Born-Again (Vidal & Schiffer, 2020) garantissent une équivalence de prédiction exacte pour toutes les entrées de l'espace d'entrée entier. Bien que cela assure une cohérence décisionnelle, l'exigence de préserver les prédictions même pour des entrées rares ou hors distribution (OOD) limite sévèrement le taux de compression réalisable.

Le problème central abordé est de savoir comment atteindre des taux de compression plus élevés tout en maintenant une haute fidélité, sans le fardeau restrictif de garantir l'équivalence sur des entrées OOD rarement observées en pratique.

2. Méthodologie : PINE

Les auteurs proposent PINE (Pruning with In-distribution Equivalence), un cadre d'élagage qui garantit l'équivalence de prédiction uniquement au sein d'une région in-distribution (ID) calibrée, $X_{ID}(\alpha)$ .

Concept central

PINE relâche la contrainte de l'élagage fidèle en restreignant la garantie d'équivalence aux entrées qui sont « plausibles » sous la distribution des données. Il introduit un seul hyperparamètre, $\alpha$ (niveau de non-couverture), qui contrôle la taille de cette région. La méthode garantit que pour une future entrée échantillonnée à partir de la même distribution, la probabilité que le modèle élagué corresponde à la prédiction du modèle original est d'au moins $1-\alpha$ .

Pipeline algorithmique

PINE s'appuie sur le cadre itératif Pruner-Oracle utilisé par FIPE, mais modifie l'espace de recherche de l'Oracle :

Définition du score plausible : Une fonction de score $s(x)$ est définie de telle sorte que des scores plus faibles indiquent une plausibilité (probabilité) plus élevée sous la distribution des données. La région in-distribution est définie comme $X_{ID}(\alpha) = \{x \in \mathcal{X} \mid s(x) \leq \tau(\alpha)\}$ .
Score de l'arbre de Chow-Liu : L'article adopte le logarithme négatif de la vraisemblance d'un arbre de Chow-Liu comme score plausible. Les caractéristiques continues sont discrétisées en intervalles, et l'arbre de Chow-Liu approxime la distribution conjointe sous forme d'une structure arborescente. Ce choix est critique car le logarithme négatif de la vraisemblance se décompose en une forme additive (marge de la racine + termes conditionnels des arêtes), permettant d'encoder la contrainte $s(x) \leq \tau(\alpha)$ efficacement sous forme de contrainte de Programmation Linéaire en Nombres Entiers Mixtes (MILP).
Calibration conformelle : En utilisant un ensemble de calibration $D_{cal}$ , le seuil $\tau(\alpha)$ est déterminé via la prédiction conformelle par partition. Cela garantit que, sous l'hypothèse d'échangeabilité, la région $X_{ID}(\alpha)$ couvre les futures entrées avec une probabilité d'au moins $1-\alpha$ .
Élagage itératif :
- Élagueur (Pruner) : Met à jour les poids des arbres pour satisfaire l'équivalence de prédiction sur un ensemble croissant de contraintes.
- Oracle : Recherche des contre-exemples (entrées où les prédictions diffèrent) mais restreint sa recherche uniquement à la région $X_{ID}(\alpha)$ .
- Le processus se répète jusqu'à ce qu'aucun contre-exemple ne soit trouvé dans la région ID.

Garanties théoriques

Équivalence probabiliste : Sous l'hypothèse d'échangeabilité, PINE fournit une borne inférieure de $1-\alpha$ sur la probabilité que la prédiction du modèle élagué corresponde à celle du modèle original pour une future entrée.
Complexité : Le nombre d'états discrets que l'Oracle doit explorer est borné supérieurement par $e^{\tau(\alpha)}$ . Puisque $\tau(\alpha)$ est monotone en $\alpha$ , augmenter $\alpha$ (en permettant un taux de non-couverture plus élevé) réduit exponentiellement l'espace de recherche, facilitant une compression plus élevée.

3. Contributions clés

Cadre PINE : Une méthode d'élagage novatrice qui échange une fidélité globale stricte contre une fidélité in-distribution à haute probabilité, permettant des taux de compression significativement plus élevés que les bases de référence d'élagage fidèle.
Intégration conformelle : La première application de la prédiction conformelle par partition pour définir une région in-distribution garantie pour l'élagage d'ensembles, fournissant une borne probabiliste rigoureuse sur l'équivalence de prédiction.
Encodage MILP du score : La proposition d'utiliser le logarithme négatif de la vraisemblance d'un arbre de Chow-Liu comme score plausible, qui est à la fois expressif pour capturer les dépendances entre caractéristiques et efficace computationnellement pour l'encodage MILP.
Contrôle systématique du compromis : Un mécanisme pour régler systématiquement le compromis fidélité-compression via le paramètre unique $\alpha$ .

4. Résultats expérimentaux

Les auteurs ont évalué PINE sur 12 jeux de données tabulaires publics (par exemple, Adult, COMPAS, Pima-Diabetes) en utilisant des ensembles XGBoost ( $M=30$ arbres, profondeur $D=2$ ).

Compression vs Fidélité : PINE surpasse nettement les bases de référence d'élagage fidèle (FIPE). Alors que $\alpha$ augmente de 0,05 à 0,8, le taux moyen d'élagage passe d'environ 45 % à environ 68 %, tandis que la fidélité moyenne reste élevée (99,15 %–99,96 %). En revanche, FIPE atteint un taux moyen d'élagage d'environ 44 % avec une fidélité de 100 %.
Comparaison avec les méthodes orientées précision : Bien que les méthodes orientées précision (IC, DREP, MDEP) puissent maintenir la précision sur les tests, elles présentent des baisses de fidélité substantielles (souvent <90 %) même au sein de la région in-distribution. PINE maintient une fidélité quasi parfaite au sein de la région calibrée.
Validation de la couverture : La couverture empirique sur les tests $\hat{\pi}_{ID}$ suit étroitement la cible $1-\alpha$ , validant l'efficacité de la calibration conformelle par partition.
Évolutivité : La méthode est plus sensible à la profondeur des arbres ( $D$ ) qu'au nombre d'arbres ( $M$ ). Des arbres plus profonds réduisent la compression réalisable en raison de régions décisionnelles plus localisées, tandis que des ensembles plus grands augmentent principalement le temps d'exécution de l'optimisation.

5. Importance et affirmations

L'article affirme que PINE comble une lacune critique dans la compression de modèles : l'incapacité des méthodes fidèles existantes à compresser efficacement les modèles sans sacrifier la cohérence décisionnelle, et l'incapacité des méthodes d'élagage standard à garantir cette cohérence.

Impact pratique : PINE permet aux praticiens de compresser les modèles jusqu'à 30 % de plus que les bases de référence fidèles tout en préservant la cohérence décisionnelle sur les futures entrées probables. Cela est particulièrement précieux dans les domaines à haut risque où les sorties du modèle déclenchent des flux de travail en aval ou nécessitent une auditabilité.
Limites : Les auteurs reconnaissent modestement que la garantie repose sur l'hypothèse d'échangeabilité (aucun changement de distribution). Si la distribution des données change, la garantie peut s'affaiblir. De plus, le coût computationnel est lié à la résolution de problèmes MILP, ce qui peut être coûteux pour des configurations multi-classes ou des arbres très profonds.
Conclusion : PINE offre une approche vérifiable et probabiliste de l'élagage qui équilibre les objectifs concurrents d'efficacité et de fiabilité, dépassant le choix binaire entre « précis mais incohérent » et « cohérent mais non compressé ».