Decision Tree Learning on Product Spaces

Résumé Technique : Apprentissage d'Arbres de Décision sur des Espaces Produit

Énoncé du Problème
L'apprentissage d'arbres de décision est une pierre angulaire du machine learning, prisé pour son interprétabilité et son succès empirique. L'approche pratique standard est l'heuristique gloutonne descendante, qui divise récursivement les nœuds en fonction de la variable la plus « influente » (souvent mesurée par la réduction d'impureté telle que l'entropie ou l'indice de Gini). Bien qu'efficace empiriquement, la compréhension théorique de cette heuristique a été limitée. Les garanties rigoureuses précédentes, telles que celles de Blanc et al. (ITTS, 2020), étaient restreintes à la distribution uniforme sur l'hypercube booléen. Cette hypothèse ne parvient pas à capturer les données réelles, où les caractéristiques suivent souvent des distributions produits hétérogènes et non uniformes. De plus, de nombreux travaux théoriques proposent des algorithmes complexes et non gloutons (par exemple, recherche ascendante ou force brute) qui s'éloignent des implémentations pratiques, laissant un fossé entre la théorie et la pratique.

Méthodologie
Les auteurs étendent l'analyse théorique de l'heuristique gloutonne descendante à des distributions produits arbitraires. Le cadre implique l'apprentissage d'une fonction booléenne $f: \{0, 1\}^n \to \{\pm 1\}$ sous une distribution produit $\mu = \mu_1 \times \dots \times \mu_n$, où chaque bit vaut 1 avec une probabilité $p_i$.

L'algorithme central analysé est BuildTopDownDT, une formalisation de l'approche gloutonne standard :

1. Initialisation : Commencer avec une seule feuille.
2. Notation : À chaque étape, noter chaque feuille $l$ de l'arbre actuel. La note est définie comme la masse de probabilité atteignant la feuille ($p_l$) multipliée par l'influence maximale de n'importe quelle variable sur la sous-fonction à cette feuille ($\max_i \text{Inf}_i(f_l)$).
3. Division : Sélectionner la feuille ayant la note la plus élevée et la diviser selon sa variable la plus influente.
4. Terminaison : Répéter jusqu'à ce que la complétion $f$ de l'arbre (en attribuant l'étiquette majoritaire aux feuilles) soit une $\epsilon$-approximation de $f$.

Pour analyser cela, les auteurs introduisent une fonction de potentiel appelée le coût d'un arbre nu (non étiqueté), défini comme la somme de l'influence totale des sous-fonctions à chaque feuille, pondérée par la probabilité d'atteindre cette feuille. Ils établissent une relation entre ce coût, l'erreur d'approximation et les propriétés structurelles de l'arbre optimal (profondeur maximale $D_{\text{opt}}$ et profondeur moyenne $\Delta_{\text{opt}}$).

Contributions Clés

1. Généralisation aux Distributions Produits : L'article fournit les premières garanties de performance rigoureuses pour l'heuristique gloutonne descendante sous des distributions produits arbitraires, éliminant l'hypothèse restrictive de distribution uniforme des travaux antérieurs.
2. Bornes de Taille Améliorées : Le résultat théorique principal (Théorème 1.1) stipule que pour toute fonction calculable par un arbre optimal de taille $s$, de profondeur maximale $D_{\text{opt}}$ et de profondeur moyenne $\Delta_{\text{opt}}$, l'heuristique gloutonne construit une $\epsilon$-approximation de taille au plus :
   $$\max \left( \left( \frac{e \cdot \Delta_{\text{opt}}}{\epsilon D_{\text{opt}}} \right)^{\Delta_{\text{opt}} D_{\text{opt}}}, e^{\Delta_{\text{opt}} D_{\text{opt}}} \right)$$
   • Régime Équilibré : Pour les arbres binaires complets où $D_{\text{opt}} = \Delta_{\text{opt}} = \log s$, la borne se simplifie en $s^{O(\log s \cdot \log(e/\epsilon))}$. Il s'agit d'une borne quasi-polynomiale qui améliore la borne établie par Blanc et al. (2020) et s'applique à une classe de distributions strictement plus large.
   • Régime de Type Chemin : Pour les arbres fortement déséquilibrés (par exemple, arbres en chemin), $D_{\text{opt}}$ peut être $O(n)$ tandis que $\Delta_{\text{opt}}$ reste une petite constante. La dépendance mixte en $\Delta_{\text{opt}}$ et $D_{\text{opt}}$ produit une borne exponentiellement plus serrée qu'une dépendance uniquement en $D_{\text{opt}}$ (qui serait $e^{O(n^2)}$ contre la $e^{O(n)}$ dérivée).
3. Implémentation Pratique Sans Paramètre : Les auteurs présentent l'Algorithme 2, une implémentation pratique de l'heuristique qui est entièrement sans paramètre. Contrairement aux analyses théoriques précédentes qui supposent la connaissance de la taille ($s$) ou de la profondeur de l'arbre optimal, cet algorithme repose sur une estimation basée sur des échantillons des notes et des erreurs. Il augmente de manière adaptative les tailles d'échantillons pour maintenir la confiance statistique sans connaissance préalable de la complexité de la fonction cible.
4. Robustesse à l'Estimation : Il est démontré que les garanties théoriques tiennent même lorsque l'algorithme sélectionne une feuille dont la note n'est qu'une fraction constante (par exemple, $1/4$) de la note maximale possible, accommodant le bruit inhérent à l'estimation basée sur des échantillons.

Résultats

• Théoriques : L'article démontre que l'heuristique gloutonne atteint des bornes de taille quasi-polynomiales dans le régime équilibré et des bornes significativement meilleures dans les régimes déséquilibrés par rapport aux bornes dépendant uniquement de la profondeur maximale. L'analyse repose sur de nouveaux lemmes reliant le coût de l'arbre à son erreur et établissant des bornes inférieures sur la note de la feuille sélectionnée en fonction de l'erreur actuelle et de la profondeur de l'arbre.
• Empiriques : Les auteurs fournissent une évaluation empirique de leur algorithme sans paramètre (Algorithme 2) sur des cibles d'arbres de décision équilibrées et déséquilibrées sous diverses distributions produits (uniforme, biais modéré, biais lourd). Les résultats confirment que les tailles d'arbres récupérés restent proches des cibles de vérité terrain et bien dans les bornes théoriques, la complexité en échantillons croissant de manière polynomiale en dimension et en $1/\epsilon$.

Signification et Revendications
L'article prétend combler le fossé entre l'analyse théorique de l'apprentissage d'arbres de décision et son application pratique. En analysant l'heuristique gloutonne classique et simple (utilisée dans ID3, C4.5, CART) plutôt que des variantes complexes et non gloutonnes, les auteurs fournissent une justification rigoureuse de la forte performance empirique de ces algorithmes largement utilisés.

La signification réside dans :

• Réalisme : Le passage de la distribution uniforme aux distributions produits arbitraires, qui modélisent mieux les données réelles.
• Praticité : La fourniture d'un algorithme sans paramètre qui ne nécessite pas de connaissance préalable de la taille ou de la profondeur de l'arbre optimal, rendant les garanties théoriques directement applicables aux scénarios réels.
• Précision : La démonstration que la dépendance mixte en profondeur moyenne et maximale produit des bornes strictement plus serrées pour les arbres déséquilibrés, une structure courante dans les arbres de décision.

Les auteurs reconnaissent des limitations, notant que leur analyse se concentre sur les arbres non élagués (car l'analyse rigoureuse de l'élagage est rare) et que la preuve actuelle repose sur des espaces produits discrets. Ils identifient l'extension de l'analyse aux caractéristiques continues et aux divisions basées sur des seuils comme une direction future. Ils notent également que, bien que leur borne soit quasi-polynomiale, des bornes inférieures super-polynomiales existent pour l'apprentissage d'arbres de décision, suggérant qu'une certaine dépendance à la taille optimale $s$ est inévitable.