Vectorized Adaptive Histograms for Sparse Oblique Forests

Cet article présente une méthode optimisée par des intrinsèques vectoriels et un basculement dynamique entre histogrammes et tri pour accélérer l'entraînement des forêts aléatoires obliques creuses, offrant des gains de performance de 1,5 à 2,5 fois par rapport aux implémentations existantes sur CPU et GPU.

L'essentiel

🌲 Le Problème : La Forêt qui veut tout voir

Imaginez que vous essayez d'enseigner à un robot à reconnaître des maladies dans des images médicales. Pour cela, vous lui donnez un outil puissant appelé une "Forêt Aléatoire". C'est comme une armée de petits arbres de décision. Chaque arbre pose une série de questions (ex: "Est-ce que la tumeur est ronde ?", "Est-ce que la couleur est rouge ?") pour arriver à une conclusion.

Dans le monde médical, on veut être extrêmement précis. On ne veut pas se tromper. Pour cela, les chercheurs utilisent une version spéciale de ces arbres, appelée "Forêt Oblique Sparse".

La différence ?

• Les arbres classiques posent des questions simples : "Est-ce que la taille est > 5 cm ?" (C'est une ligne droite verticale).
• Les arbres obliques posent des questions complexes : "Est-ce que la taille + la couleur - la température > 10 ?" (C'est une ligne en diagonale, un mélange de plusieurs facteurs).

C'est beaucoup plus intelligent et précis, mais c'est très lent à calculer. C'est comme si chaque arbre devait faire des milliers de calculs de cuisine à chaque étape pour décider de la prochaine question.

⚡ La Solution : Le Chef de Cuisine Adaptatif

L'équipe de chercheurs (de Johns Hopkins et Google) a dit : "Attendez, on perd trop de temps à faire les mêmes calculs de la même manière tout le long de la forêt."

Ils ont développé une nouvelle méthode, un peu comme un chef de cuisine ultra-intelligent qui change de stratégie selon la taille de la foule qu'il doit servir.

Voici les trois astuces magiques qu'ils ont utilisées :

1. Le Choix Dynamique : "Petite foule ou Grande foule ?"

Imaginez que vous devez trier des gens par ordre de taille.

• Si vous avez 10 000 personnes (le haut de l'arbre) : Le mieux est de les faire passer devant un mur avec des cases (des "histogrammes"). C'est rapide, on les jette dans la bonne case, et c'est fini.
• Si vous avez 5 personnes (le bas de l'arbre, les feuilles) : Faire passer ces 5 personnes devant un mur avec des cases prend trop de temps à installer ! Mieux vaut simplement les comparer une par une (trier) pour voir qui est le plus grand.

L'innovation : Au lieu d'utiliser toujours la même méthode, leur logiciel change de tactique en temps réel. S'il y a beaucoup de données, il utilise les cases. S'il y en a peu, il trie directement. C'est comme avoir un interrupteur magique qui choisit l'outil le plus rapide selon la situation.

2. La Vitesse Supersonique (Vectorisation)

Même quand on utilise les "cases" (les histogrammes), il faut savoir dans quelle case mettre chaque personne.

• L'ancienne méthode : C'était comme un garde qui vérifiait chaque case une par une en demandant : "Est-ce que tu es plus grand que 1m50 ? Non. Plus grand que 1m60 ? Non..." C'est lent.
• La nouvelle méthode : Ils utilisent des super-pouvoirs de processeur (appelés SIMD). Imaginez que le garde a maintenant des lunettes de vision nocturne qui lui permettent de voir 16 personnes en même temps et de leur dire instantanément dans quelle case elles vont.
  C'est comme passer d'un seul cheval de course à un train à grande vitesse qui transporte tout le monde d'un coup.

3. L'Équipe Mixte (CPU + GPU)

Ils ont aussi ajouté un super-ordinateur (le GPU, souvent utilisé pour les jeux vidéo) à leur équipe.

• Le processeur principal (CPU) est très bon pour gérer les petites tâches complexes et les détails fins.
• Le GPU est une bête de course, mais il a un "coût de démarrage" (il faut le réveiller). Il ne vaut la peine de l'utiliser que pour les très grosses tâches (les gros nœuds de l'arbre).
  Leur système envoie donc les grosses tâches au GPU et garde les petites pour le CPU. C'est comme envoyer un camion pour déplacer une maison, mais utiliser une voiture pour aller chercher le café.

🚀 Les Résultats : Pourquoi c'est génial ?

Grâce à ces astuces, les chercheurs ont réussi à :

1. Rendre la formation 1,7 à 2,5 fois plus rapide sur les ordinateurs classiques.
2. Gagner jusqu'à 40% de temps en utilisant le GPU sur les très gros jeux de données.
3. Ne pas perdre en précision. La qualité des décisions reste exactement la même, c'est juste que le robot apprend beaucoup plus vite.

💡 En résumé

Imaginez que vous deviez trier des millions de lettres pour les envoyer aux bonnes adresses.

• Avant, vous utilisiez une méthode unique, lente et rigide.
• Maintenant, vous avez un système qui :
  • Change de méthode selon qu'il y a 10 ou 10 000 lettres.
  • Utilise des robots pour trier 16 lettres en une seconde.
  • Fait appel à un camion géant pour les gros paquets et un vélo pour les petits.

Cela permet de traiter des données médicales massives (avec des millions de caractéristiques) en un temps record, rendant possible des diagnostics plus précis et plus rapides pour les patients. C'est une victoire pour l'intelligence artificielle dans la santé !

Résumé technique

1. Problématique et Contexte

Les forêts aléatoires (Random Forests - RF) et les ensembles d'arbres restent des méthodes de référence pour les données tabulaires et biomédicales en raison de leur rapidité d'entraînement, de leur interprétabilité et de leurs performances de pointe. Cependant, les méthodes de forêts obliques éparses (Sparse Oblique - SO) qui améliorent la précision des RF en utilisant des combinaisons linéaires de sous-ensembles de features (projections aléatoires) souffrent de coûts computationnels élevés.

Les défis spécifiques identifiés sont :

• Complexité à l'exécution : Contrairement aux arbres alignés sur les axes (feature axis-aligned), les forêts obliques doivent calculer des combinaisons linéaires de features à chaque nœud, ce qui empêche le pré-tri des données ou l'utilisation de techniques d'optimisation statiques comme la soustraction d'histogrammes.
• Arbres profonds : Pour des applications comme le MIGHT (un algorithme biomédical garantissant des bornes d'incertitude), les arbres sont entraînés jusqu'à la pureté (chaque feuille ne contient qu'une seule classe). Cela génère des arbres très profonds avec de nombreux nœuds de faible cardinalité (peu d'échantillons).
• Inefficacité des méthodes existantes :
  • Le tri (sorting) est efficace pour les grands nœuds mais devient coûteux ($O(n \log n)$) pour les petits nœuds.
  • Les histogrammes sont rapides pour les grands nœuds mais imposent un coût fixe d'initialisation et d'allocation qui domine le temps d'exécution pour les petits nœuds.
• Goulot d'étranglement : L'implémentation actuelle (YDF - Yggdrasil Random Forest) utilise principalement le tri ou des histogrammes statiques, ce qui n'est pas optimal pour la structure variable des nœuds dans les forêts obliques profondes.

2. Méthodologie

Les auteurs proposent une approche hybride et vectorisée pour accélérer l'entraînement des forêts obliques éparses sur l'implémentation YDF.

A. Histogrammes Adaptatifs Dynamiques (Runtime-Adaptive Histograms)

Au lieu d'utiliser une seule stratégie pour tout l'arbre, le système choisit dynamiquement la méthode de division (split) la plus rapide pour chaque nœud en fonction de sa cardinalité (nombre d'échantillons actifs).

• Logique : Un micro-benchmark est exécuté avant l'entraînement pour déterminer le point de basculement (crossover point) entre le tri et les histogrammes sur la machine cible.
• Application :
  • Pour les nœuds à haute cardinalité (racine, niveaux supérieurs) : Utilisation des histogrammes (coût $O(n + k \log k)$).
  • Pour les nœuds à faible cardinalité (feuilles profondes) : Utilisation du tri exact (coût optimisé pour petits ensembles, évitant le surcoût d'initialisation des histogrammes).
• Résultat : Cette adaptation permet d'éviter les surcoûts inutiles tout en maintenant une précision statistiquement équivalente.

B. Vectorisation de la Construction des Histogrammes

L'étape la plus coûteuse pour les grands nœuds est le remplissage des histogrammes. L'implémentation originale de YDF utilise une recherche binaire (std::upper_bound) pour placer chaque échantillon dans un bac (bin), ce qui entraîne des aléas de branchement (branch mispredictions) et des arrêts de pipeline.

• Innovation : Remplacement de la recherche binaire par des comparaisons vectorielles SIMD (Single Instruction, Multiple Data).
• Mécanisme : Pour 256 bacs, l'algorithme utilise deux comparaisons vectorielles larges (16 mots) pour structurer la recherche en deux niveaux (recherche grossière puis fine), similaire à une liste sautante déterministe.
• Gain : Réduction du nombre d'instructions séquentielles et élimination des branchements imprévisibles, utilisant des instructions intrinsèques AVX-512.

C. Implémentation Hybride CPU-GPU

Le système permet de déléguer dynamiquement le traitement des nœuds les plus volumineux à un GPU.

• Stratégie : Invocation noyau par noyau (node-by-node). Les nœuds très grands sont envoyés au GPU, tandis que les petits nœuds profonds restent sur le CPU (évitant ainsi le coût fixe d'initialisation du noyau GPU pour de petites tâches).
• Architecture : Les projections sont calculées et les histogrammes construits en mémoire partagée GPU, suivis d'une évaluation du meilleur split.

3. Contributions Clés

1. Sélection Dynamique de la Méthode de Split : Premier système à basculer automatiquement entre le tri exact et les histogrammes au niveau du nœud, optimisant ainsi l'entraînement des arbres profonds.
2. Accélération Vectorielle (SIMD) : Une nouvelle méthode de remplissage d'histogrammes utilisant des comparaisons vectorielles parallèles, remplaçant la recherche binaire séquentielle.
3. Orchestration CPU-GPU : Une architecture hybride capable de dispatcher intelligemment les tâches de nœuds vers le GPU uniquement lorsque cela est rentable.
4. Optimisation de YDF : Amélioration de l'implémentation YDF pour gérer efficacement les tables larges (nombreuses features) et les projections éparses.

4. Résultats Expérimentaux

Les expériences ont été menées sur des datasets réels (HIGGS, SUSY, Epsilon) et synthétiques (Trunk), avec des tailles allant de 400k à 10M d'échantillons et jusqu'à 4096 features.

• Accélération sur CPU :
  • Par rapport aux forêts obliques existantes : 1,7x à 2,5x plus rapide.
  • Par rapport aux forêts aléatoires standards (axis-aligned) : 1,5x à 2x plus rapide.
  • La combinaison des histogrammes dynamiques et de la vectorisation apporte une réduction de temps d'entraînement de plus de 50% sur les grands datasets.
• Accélération Hybride (GPU) :
  • Gain modeste sur les datasets moyens (jusqu'à 11% pour HIGGS).
  • Gain significatif sur les datasets très larges et volumineux (jusqu'à 40% pour Trunk-10M).
• Précision :
  • Les méthodes dynamiques et vectorisées maintiennent une précision statistiquement indistinguable par rapport aux méthodes exactes ou aux histogrammes statiques.
  • Les courbes de performance (ROC/AUC) sont quasi identiques sur les benchmarks OpenML.
• Passage à l'échelle (Scalability) :
  • L'entraînement est principalement limité par le calcul (compute-bound) sur le CPU, montrant une mise à l'échelle quasi parfaite jusqu'au nombre de cœurs physiques.

5. Signification et Impact

Ce travail résout un goulot d'étranglement computationnel majeur qui limitait l'adoption des forêts obliques éparses pour des applications nécessitant une grande précision et des garanties statistiques (comme le dépistage du cancer via l'algorithme MIGHT).

• Faisabilité : Rend l'entraînement de forêts obliques sur des datasets avec des millions de features et des millions d'échantillons réalisable en pratique.
• Efficacité : Démontre que les compromis classiques entre vitesse (histogrammes) et précision (tri exact) peuvent être levés par une adaptation dynamique et une optimisation matérielle (vectorisation).
• Ouverture : Fournit une base logicielle open-source (basée sur YDF) optimisée pour les architectures modernes (CPU vectoriels et GPU), ouvrant la voie à l'utilisation de modèles non-paramétriques complexes sur des données biomédicales massives.

En résumé, les auteurs ont transformé un algorithme théoriquement puissant mais coûteux en une méthode pratique et rapide, capable de rivaliser avec les méthodes de boosting de gradient tout en offrant des garanties d'incertitude supérieures.