🤖 machine learning

Backward Compatibility in Tree-Based Explanations and Enhanced CART Algorithm

Cet article introduit la métrique Backward Compatibility Loss in Tree-based eXplanations (BCLTX) et un algorithme léger correspondant, CART-BCTX, afin de garantir que les mises à jour des modèles d'arbres de décision maintiennent des explications structurelles cohérentes tout en préservant la précision des prédictions et l'efficacité computationnelle.

Auteurs originaux : Hirofumi Suzuki

Publié 2026-08-11

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Hirofumi Suzuki

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 êtes un détective résolvant un mystère. Vous avez un carnet rempli d'indices et un ensemble de règles que vous avez rédigées pour identifier le coupable. Ces règles sont comme une carte : « Si le suspect a été vu près de la boulangerie, vérifiez l'alibi ; s'il était au parc, vérifiez la météo. » C'est ainsi qu'un Arbre de Décision fonctionne dans le monde des ordinateurs. C'est un outil populaire pour prendre des décisions car il est très transparent ; vous pouvez regarder l'arbre et voir exactement pourquoi il a fait un choix. C'est comme un organigramme que n'importe qui peut lire.

Mais voici la partie délicate : le monde change. De nouveaux indices apparaissent, les anciens deviennent flous, et parfois le coupable change ses habitudes. Le détective doit donc mettre à jour son carnet avec de nouvelles règles. C'est ce qu'on appelle la Mise à jour de Modèle. Le problème est que si vous jetez simplement le vieux carnet pour en écrire un tout nouveau de zéro, les règles pourraient changer complètement. Soudain, le suspect qui était autrefois innocenté parce qu'il était à la boulangerie devient le principal suspect parce que les nouvelles règles disent « vérifiez la boulangerie en priorité ». Cela déroute les personnes qui comptent sur le détective. Ils avaient confiance en l'ancienne logique, et maintenant, la nouvelle logique ressemble à une trahison. C'est le problème de la Compatibilité Ascendante (Backward Compatibility) : faire en sorte que, lorsque vous mettez à jour votre système, vous ne brisiez pas la confiance ou la logique sur laquelle les utilisateurs comptent déjà.

Le Puzzle des Règles Changeantes

Dans l'article « Backward Compatibility in Tree-Based Explanations and Enhanced CART Algorithm », Hirofumi Suzuki s'attaque à ce casse-tête précis. L'auteur pose une question simple mais vitale : lorsque nous mettons à jour un arbre de décision avec de nouvelles données, comment pouvons-nous nous assurer que les raisons qu'il donne pour ses décisions ne changent pas radicalement ?

Considérez un arbre de décision comme une partie de « 20 Questions ». L'arbre pose des questions comme « Est-ce que le nombre est plus grand que 5 ? » pour restreindre les réponses. L'« explication » est le chemin spécifique de questions que l'arbre a emprunté pour arriver à la réponse. Si vous mettez à jour l'arbre, vous pourriez changer entièrement les questions. Peut-être que le nouvel arbre demandera : « Est-ce que le nombre est pair ? » au lieu de cela. Pour l'ordinateur, les deux peuvent être corrects, mais pour un humain essayant de comprendre la logique, ce changement est brutal.

L'article soutient que simplement mettre à jour un arbre pour qu'il soit plus précis ne suffit pas. Si le nouvel arbre donne une « histoire » différente pour expliquer son choix, cela peut être dangereux, surtout dans des domaines à enjeux élevés comme la santé ou la finance, où les gens ont besoin de faire confiance à la logique. L'auteur suggère que nous avons besoin d'un moyen de mesurer à quel point l'« histoire » change, puis de construire un nouvel arbre qui garde l'histoire sensiblement la même, tout en apprenant de nouvelles choses.

Le Nouvel Outil : Une Fiche de Notation de « Compatibilité »

Pour résoudre cela, l'auteur invente une nouvelle règle de mesure appelée BCLTX (Backward Compatibility Loss in Tree-based eXplanations). Imaginez que vous ayez deux cartes de la même ville : l'ancienne et la nouvelle. Le BCLTX est un score qui indique à quel point les rues diffèrent entre les deux cartes.

L'article propose quatre façons différentes de calculer ce score, mais elles reviennent toutes à vérifier deux choses :

Quelles caractéristiques comptent ? L'arbre a-t-il commencé à prêter attention à des indices différents (comme passer de la « boulangerie » au « parc ») ?
Quelle est la largeur des règles ? Les limites des règles ont-elles bougé ? (Par exemple, la règle est-elle passée de « boulangeries dans un rayon de 1 mile » à « boulangeries dans un rayon de 5 miles » ?)

L'auteur appelle cela une « métrique de perte » (loss metric), ce qui est simplement une façon sophistiquée de dire « un score pour mesurer à quel point nous avons échoué par rapport à l'ancienne logique ». L'objectif est de maintenir ce score le plus bas possible.

La Solution : CART-BCTX

L'article présente ensuite un nouvel algorithme appelé CART-BCTX. Si vous savez comment les ordinateurs apprennent, vous connaissez peut-être CART (Classification and Regression Trees), qui est la méthode standard et de référence pour construire ces arbres de décision. C'est comme la recette standard pour faire un gâteau.

CART-BCTX est comme une version « survitaminée » de cette recette. C'est le même gâteau, mais le pâtissier (l'algorithme) a une nouvelle règle : « Pendant que vous cuisez le gâteau, assurez-vous de ne pas trop changer sa forme par rapport au précédent. »

L'algorithme fonctionne en examinant chaque division possible dans l'arbre et en se demandant : « Si je fais cette coupe, cela m'aidera-t-il à mieux prédire, mais est-ce que cela maintiendra aussi l'explication similaire à l'ancien arbre ? » Il équilibre ces deux objectifs en utilisant un bouton réglable appelé $\lambda$ (lambda).

Si vous tournez le bouton vers zéro, il agit comme le CART normal, ignorant complètement l'ancien arbre.
Si vous tournez le bouton vers le haut, il devient très obstiné à vouloir conserver l'ancienne logique, même si cela signifie que les nouvelles prédictions ne sont pas tout à fait aussi parfaites.

L'auteur a testé cela sur 10 jeux de données réels, allant de la classification d'e-mails comme spam à la prédiction de la quantité de vin dans une bouteille. Les résultats sont prometteurs. L'article suggère que le CART-BCTX peut trouver un « juste milieu » où l'arbre devient meilleur pour prédire les choses sans réécrire complètement sa propre histoire.

Ce que l'article dit (et ne dit pas)

Les expériences montrent que cette nouvelle méthode fonctionne bien. Plus précisément, l'article constate que :

Elle est rapide : Le nouvel algorithme prend environ le même temps que l'algorithme CART standard pour s'exécuter. Il ne ralentit pas significativement les processus, même avec les calculs supplémentaires.
Elle maintient la cohérence de l'histoire : En utilisant cette nouvelle « métrique de perte », les explications (les chemins à travers l'arbre) restent beaucoup plus stables que si l'on mettait simplement à jour l'arbre normalement.
Elle aide aussi les prédictions : Curieusement, en gardant les explications stables, le nouvel arbre a également tendance à maintenir ses prédictions stables pour les éléments qu'il réussissait déjà auparavant. C'est un effet secondaire heureux.

L'article compare également cette méthode aux Arbres de Décision Incrémentaux (comme VFDT et HAT), qui sont conçus pour apprendre une donnée à la fois, comme un flux continu. Les résultats suggèrent que si ces arbres de flux sont bons pour gérer les nouvelles données au fur et à mesure qu'elles arrivent, ils ne maintiennent pas nécessairement la cohérence de l'« histoire » sur le long terme lorsqu'on regarde des lots de données. Le CART-BCTX semble mieux réussir à maintenir cette compatibilité ascendante lors de la mise à jour du modèle complet en une seule fois.

Cependant, l'auteur prend soin de ne pas prétendre qu'il s'agit d'une solution miracle. L'article note que trouver l'arbre parfait est mathématiquement impossible à réaliser rapidement, donc cette méthode utilise une approche « gloutonne » (greedy, faisant le meilleur choix local à chaque étape). Il admet également qu'ils n'ont pas pleinement testé la manière dont cela fonctionne lorsque le monde change radicalement (dérive de concept ou concept drift) ou comment les humains réagissent réellement à ces changements lors d'une étude utilisateur.

Ce qu'il faut retenir

En résumé, cet article propose une manière pratique de mettre à jour les « cartes logiques » que les ordinateurs utilisent, en garantissant que lorsque la carte change, les points de repère ne disparaissent pas. Il suggère qu'en ajoutant un simple « contrôle de compatibilité » au processus standard de construction d'arbres, nous pouvons mettre à jour nos modèles d'IA sans confondre les personnes qui comptent sur eux. C'est un pas vers un apprentissage automatique où les mises à jour ressemblent moins à une surprise et davantage à une évolution naturelle.

Résumé Technique : Compatibilité Ascendante dans les Explications Basées sur les Arbres et l'Algorithme CART Amélioré

1. Énoncé du Problème

Dans le cycle de vie opérationnel des systèmes d'apprentissage automatique, les mises à jour de modèles sont nécessaires pour maintenir les performances à mesure que les distributions de données évoluent. Cependant, les mises à jour de modèles standards modifient souvent considérablement le comportement du modèle, ce qui peut perturber la prise de décision en aval et éroder la confiance des utilisateurs. Ce problème est particulièrement critique dans les domaines sensibles aux risques (par exemple, la santé, la finance) où l'IA explicable (XAI) est employée.

Bien que la recherche existante sur la compatibilité ascendante (quantifiant la stabilité du comportement d'un modèle à travers les mises à jour) se soit concentrée sur la cohérence des prédictions ou les contributions de caractéristiques basées sur SHAP, ces approches ne parviennent pas à traiter les explications basées sur les arbres. Les arbres de décision offrent une transparence grâce à des règles de type « si-alors-sinon » dérivées d'intervalles de caractéristiques. Lorsqu'un arbre de décision est réentraîné sur de nouvelles données, les points de division (split points) et les sous-espaces de caractéristiques résultants (explications) peuvent changer radicalement, même si la précision prédictive s'améliore. Ce manque de compatibilité ascendante dans les explications peut confondre les utilisateurs qui s'appuient sur des règles logiques cohérentes pour l'aide à la décision. Les méthodes actuelles ne peuvent pas optimiser efficacement la stabilité de ces explications structurées en arbres.

2. Méthodologie

2.1 Métrique Proposée : BCLTX

L'auteur propose la Perte de Compatibilité Ascendante dans les Explications basées sur les Arbres (BCLTX), une métrique de perte conçue pour quantifier la divergence entre les explications d'un ancien arbre de décision ( $T_1$ ) et d'un nouvel arbre de décision ( $T_2$ ) pour les échantillons où l'ancien modèle était correct.

Une explication d'arbre de décision pour une entrée $\mathbf{x}$ est définie comme une conjonction d'intervalles pour des caractéristiques spécifiques, représentée par des vecteurs de bornes inférieures ( $l$ ) et supérieures ( $u$ ). BCLTX mesure la différence entre $T_1$ et $T_2$ en utilisant quatre variantes :

$\delta_{JAC}$ (basée sur Jaccard) : Mesure la différence symétrique dans l'ensemble des caractéristiques contribuant à l'explication (où les bornes sont finies).
$\delta_{JLU}$ (Jaccard Inférieure/Supérieure) : Mesure séparément la différence symétrique dans les caractéristiques contribuant aux bornes inférieures et supérieures.
$\delta_{MAE}$ (Erreur Absolue Moyenne) : Quantifie la différence des intervalles par caractéristique en utilisant l'erreur absolue, normalisée par l'écart-type des caractéristiques et bornée par les plages de données.
$\delta_{MSE}$ (Erreur Quadratique Moyenne) : Quantifie les différences d'intervalles en utilisant l'erreur au carré, de manière similaire normalisée.

2.2 Algorithme : CART-BCTX

Pour optimiser BCLTX, l'auteur propose CART avec Compatibilité Ascendante dans les Explications basées sur les Arbres (CART-BCTX). Il s'agit d'un algorithme gourmand (greedy) et léger qui étend l'algorithme standard CART.

Fonction Objective : L'algorithme minimise une fonction objective combinée :
$f(T_1, T_2, D_2, \lambda) = \frac{1}{|D_2|} \sum \ell(T_2(\mathbf{x}), y) + \frac{\lambda}{|D_s|} \sum \delta(T_1, T_2, \mathbf{x})$
Où $\ell$ est la perte spécifique à la tâche (par exemple, la perte 0-1 ou l'erreur quadratique) et $D_s$ est l'ensemble des échantillons correctement prédits par l'ancien modèle $T_1$ , et $\delta$ est la variante choisie de BCLTX, tandis que $\lambda$ contrôle le compromis entre la performance prédictive et la stabilité de l'explication.
Sélection de Division Gourmande (Greedy Split Selection) : Lors de la croissance de l'arbre, CART-BCTX maintient les bornes actuelles du sous-espace de caractéristiques ( $\hat{l}, \hat{u}$ ) pour chaque nœud. Lors de l'évaluation des divisions candidates, il calcule un « gain » pour la perte de tâche ( $Gain_\ell$ ) et pour la perte de compatibilité ascendante ( $Gain_\delta$ ). La division maximisant la somme pondérée de ces gains est sélectionnée.
- Pour $\delta_{JAC}$ et $\delta_{JLU}$ , le calcul du gain est constant par rapport au choix du point de division pour une caractéristique donnée.
- Pour $\delta_{MAE}$ et $\delta_{MSE}$ , l'algorithme calcule efficacement les changements de gain en utilisant des arbres de recherche binaire auto-équilibrés (pour MAE) ou des mises à jour de sommes simples (pour MSE) lors de la partition des échantillons.
Complexité : La complexité computationnelle de CART-BCTX est comparable à celle de l'algorithme CART standard. Elle est de $O(n m d_2)$ pour les variantes Jaccard, JLU et MSE (où $n$ est le nombre d'échantillons, $m$ le nombre de caractéristiques, $d_2$ la profondeur de l'arbre) et de $O(n m d_2 \log n)$ pour la variante MAE.
Élagage (Pruning) : L'auteur étend l'élagage de complexité de coût (CCP) pour gérer BCLTX en incorporant la fonction de perte combinée dans le critère d'élagage, permettant ainsi de supprimer les sous-arbres qui n'améliorent pas suffisamment le compromis.

3. Principales Contributions

Définition de BCLTX : Le papier introduit les premières métriques de compatibilité ascendante spécifiquement conçues pour les explications basées sur les arbres, capturant les différences dans les ensembles de caractéristiques et les bornes d'intervalles.
Algorithme CART-BCTX : Un algorithme de mise à jour efficace et gourmand qui intègre BCLTX dans le cadre standard de CART sans sacrifier la scalabilité.
Analyse Théorique : Preuve que l'algorithme maintient une complexité de calcul comparable à celle de l'algorithme CART standard, avec une augmentation d'au plus un facteur logarithmique pour certaines variantes de perte.
Validation Empirique : Expérimentations approfondies sur 10 jeux de données réels (5 de classification, 5 de régression) démontrant l'efficacité de l'algorithme.

4. Résultats Expérimentaux

Les expériences ont été menées sur 10 jeux de données provenant des répertoires UCI et KEEL, comparant CART-BCTX aux mises à jour standard de CART et aux arbres de décision incrémentaux (VFDT et HAT).

Compromis Prédiction-BCLTX : CART-BCTX atteint un compromis favorable entre la performance prédictive (taux d'erreur/RMSE) et les valeurs de BCLTX. À mesure que le paramètre de régularisation $\lambda$ augmente, les valeurs de BCLTX s'améliorent (indiquant des explications plus stables) tandis que la dégradation de la performance prédictive est minimale pour un petit $\lambda$ .
Impact sur la Compatibilité des Prédictions : L'utilisation de $\delta_{MAE}$ ou $\delta_{MSE}$ améliore considérablement la Compatibilité Ascendante des Prédictions (BCP), suggérant que la stabilisation des explications stabilise également les prédictions pour les échantillons que l'ancien modèle gérait correctement.
Temps de Calcul : CART-BCTX fonctionne avec des temps de calcul comparables à ceux de l'algorithme CART standard (au plus environ 2x plus lent dans les scénarios les plus défavorables), confirmant son efficacité pratique.
Comparaison avec les Arbres Incrémentaux : Évalué sur une base par lots (batch-wise), CART-BCTX surpasse les arbres incrémentaux (VFDT, HAT) tant en précision prédictive qu'en valeurs de BCLTX. Bien que les arbres incrémentaux maintiennent une certaine compatibilité de prédiction, ils échouent à préserver la stabilité des explications basées sur les arbres sur le moyen à long terme par rapport à la mise à jour par lots de CART-BCTX.

5. Signification et Revendications

Le papier affirme que CART-BCTX fournit une solution pratique pour mettre à jour les arbres de décision dans des environnements où la stabilité de l'explication est aussi critique que la précision prédictive. En supprimant les changements drastiques dans les frontières de décision et les intervalles de caractéristiques, la méthode soutient un déploiement digne de confiance dans les applications sensibles aux risques.

L'auteur souligne que :

Les métriques de compatibilité ascendante existantes (centrées sur SHAP ou la précision de prédiction) sont insuffisantes pour les arbres de décision.
Le cadre proposé permet des mises à jour compatibles avec l'ascendance sans nécesser une refonte complète de l'algorithme d'apprentissage.
Bien que le travail actuel suppose un environnement d'apprentissage par lots (batch learning), le concept de compatibilité ascendante peut être évalué de manière par lots, même dans des contextes d'apprentissage incrémental, où les arbres de décision incrémentaux standards peuvent échouer à préserver la cohérence des explications à long terme.

Limites notées par l'auteur :

L'algorithme est gourmand (greedy) ; trouver l'arbre globalement optimal sous BCLTX est computationnellement intraitable.
La formulation actuelle ne traite pas explicitement les scénarios de dérive de concept (concept drift) où la définition des prédictions « correctes » pourrait changer fondamentalement.
La pertinence pratique des métriques proposées nécessite une validation supplémentaire par des études utilisateur dans des contextes de déploiement réels.