Experiments with Optimal Model Trees

Cet article propose des formulations de programmation linéaire en nombres entiers pour construire des arbres de modèles optimaux avec des machines à vecteurs de support linéaires dans les feuilles, démontrant que cette approche globale permet d'obtenir des arbres plus petits et aussi précis que les méthodes gloutonnes ou d'autres algorithmes d'apprentissage automatique sur un large éventail de jeux de données.

L'essentiel

Voici une explication simple et imagée de cette recherche, conçue pour être comprise par tout le monde, même sans bagage technique.

Imaginez que vous essayez d'apprendre à un ami à reconnaître des objets ou à prédire le temps qu'il fera demain. Vous avez deux façons principales de lui expliquer les règles.

1. Le problème : L'arbre de décision classique (Le "Guide Touristique" paresseux)

Habituellement, les ordinateurs utilisent des arbres de décision. C'est comme un guide touristique qui vous donne des instructions simples :

• "Si le ciel est gris, prenez un parapluie."
• "Si le ciel est bleu, mettez des lunettes de soleil."

Dans les arbres classiques, à la fin de chaque chemin (la feuille de l'arbre), le guide vous donne une réponse fixe : "Il va pleuvoir" ou "Il va faire beau". C'est simple à comprendre, mais parfois un peu bête. Si le ciel est gris mais que vous êtes en montagne, la pluie est moins probable qu'en ville. Le guide classique ne fait pas cette nuance.

Pour obtenir de meilleures réponses, les arbres classiques doivent devenir énormes et complexes, avec des milliers de détours. Résultat : c'est difficile à lire et à comprendre pour un humain. C'est comme un livre de règles de 500 pages pour savoir s'il faut prendre un parapluie.

2. La solution proposée : L'arbre de décision "Modèle" (Le "Chef Cuisinier" intelligent)

Les auteurs de cette étude, Sabino et Eibe, proposent une idée géniale : au lieu de donner une réponse fixe à la fin de chaque chemin, donnons une formule mathématique simple (une petite équation).

Imaginez que, dans chaque petite pièce de l'arbre, au lieu de dire "Il va pleuvoir", le guide dit :

"Prenez 20% de chance de pluie si le ciel est gris, mais ajoutez 50% si vous êtes en montagne."

C'est ce qu'on appelle un arbre de modèle.

• Avantage : L'arbre peut être beaucoup plus petit (moins de pièces) tout en étant plus précis.
• Défi : Trouver la meilleure façon de couper l'arbre et la meilleure formule pour chaque pièce est un casse-tête mathématique énorme.

3. La méthode : Le "Super-Solveur" (MILP)

Jusqu'à présent, les ordinateurs construisaient ces arbres de manière égoïste (on appelle ça "gourmand"). Ils prenaient la meilleure décision immédiate sans regarder plus loin. C'est comme si vous choisissiez le chemin le plus court pour aller à la boulangerie, sans vous rendre compte que ce chemin vous mène dans une impasse plus loin. Cela crée des arbres géants et imparfaits.

Les auteurs utilisent une méthode appelée MILP (Programmation Linéaire Mixte en Nombres Entiers).

• L'analogie : Imaginez que vous avez un puzzle géant. La méthode "gourmande" essaie de placer les pièces une par une au hasard. La méthode MILP, c'est comme avoir un super-ordinateur qui regarde toutes les pièces en même temps et calcule le placement parfait pour tout l'ensemble d'un coup.
• C'est beaucoup plus lent à calculer (comme résoudre un Sudoku de 1000x1000), mais le résultat est un arbre parfaitement optimisé : le plus petit possible pour la précision la plus grande.

4. Ce qu'ils ont découvert (Les résultats)

Ils ont testé cette méthode sur 25 jeux de données différents (comme prédire des maladies, le prix des maisons, ou si un email est un spam).

• Précision : Les arbres "modèles" optimisés sont souvent plus précis que les arbres classiques, même s'ils sont beaucoup plus petits.
• Taille : Ils ont réussi à créer des arbres avec très peu de branches (parfois moins de 10) qui battent des arbres géants créés par des méthodes classiques. C'est comme réussir à expliquer un concept complexe en 5 phrases au lieu de 500.
• Le compromis : La méthode est lente. Parfois, l'ordinateur met une heure à trouver la solution parfaite. Mais même si on l'arrête avant la fin, le résultat reste souvent excellent.

5. Pourquoi c'est important ? (L'Intelligence Artificielle "Transparente")

Aujourd'hui, beaucoup d'IA sont des "boîtes noires" : on donne une entrée, on obtient une sortie, mais on ne sait pas pourquoi. C'est dangereux si l'IA refuse un prêt bancaire ou diagnostique une maladie.

Cette recherche montre qu'on peut avoir une IA très précise ET très transparente.

• On peut voir exactement comment l'arbre prend sa décision.
• On peut expliquer à un humain : "J'ai refusé le prêt parce que votre revenu est bas ET que vous avez beaucoup de dettes, selon cette formule précise."

En résumé

Cette étude nous dit : "Arrêtons de construire des murs de briques géants pour expliquer nos décisions. Utilisons des outils mathématiques puissants pour construire de petits ponts élégants qui nous mènent exactement au bon endroit."

C'est une victoire pour l'IA explicable : des modèles plus petits, plus précis, et que n'importe quel humain peut comprendre en regardant le schéma.

Résumé technique

Voici un résumé technique détaillé de l'article « Experiments with Optimal Model Trees » de Sabino Francesco Roselli et Eibe Frank, rédigé en français.

1. Problématique

Les arbres de décision sont des modèles d'apprentissage automatique très populaires pour leur interprétabilité, permettant de tracer le chemin d'une prédiction depuis la racine jusqu'à une feuille. Cependant, les arbres de décision classiques (« classiques ») stockent des valeurs constantes dans leurs feuilles (classes pour la classification, valeurs numériques pour la régression). Cette approche impose souvent des arbres très profonds et complexes pour atteindre une bonne précision, ce qui nuit à l'interprétabilité.

Les arbres de modèles (Model Trees) offrent une alternative en plaçant des modèles linéaires (comme une régression linéaire) dans les feuilles plutôt que des valeurs constantes. Cela permet de représenter des fonctions linéaires par morceaux, améliorant souvent la précision et réduisant la taille de l'arbre.

Le problème central abordé par les auteurs est la méthode d'apprentissage de ces arbres. La plupart des algorithmes actuels (CART, C4.5, M5P) fonctionnent de manière gloutonne (greedy) : ils divisent les données localement à chaque nœud sans considérer l'impact global sur la structure de l'arbre. Cela conduit souvent à des solutions sous-optimales, des arbres trop grands et moins précis.

L'objectif de l'article est d'évaluer empiriquement la construction d'arbres de modèles optimaux (globalement optimaux) pour la classification et la régression, en utilisant la Programmation Linéaire en Nombres Entiers Mixtes (MILP) pour résoudre le problème d'optimisation conjointe de la structure de l'arbre (discrète) et des paramètres des modèles linéaires (continus).

2. Méthodologie

Les auteurs proposent une formulation MILP pour apprendre des arbres de modèles optimaux.

• Modélisation du problème :

  • L'arbre est défini comme un graphe de profondeur fixe $D$.
  • Des variables binaires déterminent si un nœud est une feuille ou un nœud de décision (split).
  • Des variables continues modélisent les coefficients des modèles linéaires dans les feuilles.
  • Pour la régression, les feuilles contiennent des Machines à Vecteurs de Support (SVM) linéaires avec une perte d'erreur absolue (équivalent à une régression linéaire avec régularisation L1).
  • Pour la classification, les feuilles contiennent des SVM linéaires (binaire ou multi-classes).
  • L'objectif est de minimiser une fonction combinant l'erreur de prédiction (résidus) et la complexité du modèle (poids des vecteurs de support), tout en respectant des contraintes de structure d'arbre.

• Types d'arbres étudiés :

  • Univariés : Les splits sont basés sur une seule variable et un seuil (arbres interprétables).
  • Multivariés : Les splits sont basés sur une combinaison linéaire de variables (plus précis, mais moins interprétables).

• Stratégie d'optimisation :

  • Utilisation de solveurs MILP modernes (Gurobi) pour trouver la solution globale.
  • Recherche itérative des hyperparamètres : le coefficient de régularisation $C$ (pour les SVM) et le nombre maximal de splits $S$ (ou profondeur effective).
  • Validation croisée pour sélectionner les meilleurs hyperparamètres avant l'entraînement final sur l'ensemble complet.

• Comparaison :
  Les modèles optimaux (OCMT pour la classification, ORMT pour la régression) sont comparés à :

  • Des arbres de décision optimaux classiques (OCT/ORT) avec des feuilles constantes.
  • Des arbres de modèles gloutons (LMT, M5P).
  • Des arbres optimaux avec recherche locale (LS-OMT).
  • Des méthodes dynamiques (DL8.5, SRT-L).
  • Des forêts aléatoires (RF) et des SVM linéaires standards.

3. Contributions Clés

1. Formulation MILP nouvelle pour la classification : Les auteurs proposent une formulation MILP basée sur les SVM pour les arbres de modèles de classification, qui semble être une première dans la littérature (la version régression étant basée sur des travaux antérieurs [14]).
2. Évaluation empirique exhaustive : L'étude couvre 20 problèmes de classification binaire, 5 problèmes multi-classes et 20 problèmes de régression provenant du dépôt OpenML, offrant une comparaison large contre l'état de l'art.
3. Analyse de la taille vs précision : Démonstration que les arbres de modèles optimaux peuvent atteindre une précision compétitive (voire supérieure) avec des arbres significativement plus petits que les approches gloutonnes ou les arbres classiques optimaux.
4. Étude des splits multivariés : Analyse de l'impact du passage de splits univariés à multivariés, montrant un gain de précision marginal au détriment de l'interprétabilité.

4. Résultats Principaux

• Précision et Taille :

  • Les arbres de modèles optimaux (OCMT/ORMT) surpassent systématiquement les arbres de décision optimaux classiques (OCT/ORT) de même taille, avec des gains de précision allant jusqu'à 30 % dans certains cas de classification.
  • Comparés aux algorithmes gloutons (CART, M5P, LMT) et aux méthodes dynamiques (DL8.5), les arbres optimaux sont aussi précis, voire plus précis, mais considérablement plus petits. Par exemple, les arbres CART peuvent avoir jusqu'à 250 feuilles, tandis que les arbres optimaux restent souvent en dessous de 10 feuilles.
  • Les arbres de modèles optimaux sont particulièrement efficaces pour la régression, surpassant M5P et les autres méthodes dans 9 cas sur 20.

• Performance des splits multivariés :

  • Contrairement à l'hypothèse initiale, les arbres multivariés (OCMT-H, ORMT-H) n'ont pas systématiquement surpassé leurs homologues univariés. Ils ont montré des améliorations significatives seulement sur quelques jeux de données spécifiques (ex: "Parity", "Long"), mais souvent au prix d'une complexité accrue et d'une perte d'interprétabilité.

• Limites de Scalabilité :

  • Le temps de calcul est le principal goulot d'étranglement. Avec une limite de temps de 3600 secondes, le solveur a souvent dépassé le temps limite pour des arbres avec plus d'un split (2 à 3 splits) sur des jeux de données de taille moyenne.
  • Cependant, même lorsque le solveur ne trouve pas l'optimum global (temps écoulé), les solutions retournées restent compétitives par rapport aux méthodes gloutonnes.
  • L'approche est donc viable pour des jeux de données de taille limitée où l'interprétabilité et la précision sont prioritaires.

• Comparaison avec d'autres méthodes :

  • Les Forêts Aléatoires (RF) restent généralement les plus précises, mais elles ne sont pas interprétables.
  • Les SVM linéaires simples servent de borne inférieure (équivalent à un arbre avec une seule feuille).
  • Les arbres optimaux se situent entre les SVM simples et les RF en termes de précision, tout en offrant une interprétabilité supérieure.

5. Signification et Conclusion

Cet article démontre que l'utilisation de la Programmation Linéaire en Nombres Entiers Mixtes (MILP) pour apprendre des arbres de modèles est une approche viable et puissante pour l'IA interprétable.

• Avantage majeur : La capacité à obtenir des modèles compacts (petits arbres) sans sacrifier la précision, ce qui est crucial pour les domaines où la confiance et l'explicabilité sont critiques (santé, finance, sécurité).
• Innovation : L'intégration de modèles linéaires (SVM) dans les feuilles d'arbres optimaux permet de capturer des relations complexes avec très peu de nœuds de décision.
• Perspectives : Bien que le temps de calcul limite l'application à des jeux de données de taille modérée, les résultats suggèrent que cette méthode est idéale pour des scénarios où l'on privilégie la qualité du modèle et son interprétabilité sur la vitesse d'entraînement. Les auteurs suggèrent des travaux futurs sur les méthodes de décomposition pour accélérer le calcul et l'application à des arbres de politiques optimales.

En résumé, cette étude valide que les arbres de modèles optimaux basés sur le MILP constituent une alternative supérieure aux arbres gloutons classiques pour les applications nécessitant un équilibre fin entre précision, taille du modèle et interprétabilité.