🤖 machine learning

FQTree: Fine-grained Quantization and Hardware Generation of Boosted Decision Trees

Cet article présente FQTree, un algorithme d'entraînement conscient de la quantification à grain fin combiné au cadre de génération matérielle QXXGB, qui optimise les arbres de décision boostés pour le déploiement sur FPGA en réduisant l'utilisation des LUT de 26 à 57 % tout en maintenant ou en améliorant la précision.

Auteurs originaux : Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera, Qijia Tang, Bakhtiar Zadeh, Wayne Luk, Maria Spiropulu

Publié 2026-08-13

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera, Qijia Tang, Bakhtiar Zadeh, Wayne Luk, Maria Spiropulu

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 essayiez d'apprendre à un robot à prendre des décisions, comme un arbitre dans un jeu vidéo ou un agent de sécurité dans une boîte de nuit. Vous ne voulez pas que le robot soit un penseur lent et lourd ; vous voulez qu'il soit fulgurant, prenant des décisions en une fraction de seconde sans hésiter. C'est le monde des « Arbres de Décision Boostés » (BDT). Considérez un BDT non pas comme un seul cerveau géant, mais comme une équipe de nombreux petits décideurs simples. Chacun pose une question simple comme : « La température est-elle supérieure à 20 degrés ? » ou « La vitesse est-elle supérieure à 50 mph ? ». Selon la réponse, l'équipe passe le témoin au suivant dans la file. À la fin de la file, toute l'équipe a additionné ses opinions pour prendre une décision finale. Ces équipes sont célèbres pour leur capacité à repérer des motifs dans des données désordonnées, mais elles ont un problème : elles sont souvent trop lourdes et lentes pour les puces minuscules et ultra-rapides (appelées FPGA) qui alimentent les systèmes en temps réel comme les voitures autonomes ou les expériences de physique des particules.

Le grand défi est que ces équipes de décision sont généralement entraînées avec des nombres « flottants » (comme 3,14159...), qui sont précis mais demandent beaucoup d'espace et d'énergie pour être stockés. Pour les faire fonctionner sur des puces minuscules, les ingénieurs essaient généralement de faire tenir ces nombres dans des boîtes plus petites et plus simples (comme des nombres entiers). Mais c'est comme essayer de faire entrer une énorme gelée tremblotante dans une petite boîte rigide : si vous l'écrasez simplement dedans après que la gelée a déjà pris, elle se brise, et le robot commence à faire des erreurs stupides. L'ancienne méthode consistait à deviner la taille de boîte appropriée pour tout le monde, ce qui gaspillait souvent de l'espace ou ruinait l'intelligence du robot.

Ce document présente une nouvelle méthode ingénieuse appelée FQTree (Arbre de Quantification à Grain Fin) et un outil compagnon nommé QXGB qui change la façon dont nous construisons ces équipes de décision. Au lieu d'entraîner l'équipe avec de grands nombres flottants puis d'essayer de les serrer dans une boîte plus tard, FQTree apprend à l'équipe à penser en petites boîtes simples pendant qu'elle apprend. C'est comme entraîner un gymnaste à effectuer une performance sur une poutre d'équilibre étroite dès le premier jour, plutôt que de le laisser s'exercer sur un large sol pour ensuite le forcer à monter sur la poutre juste avant la compétition.

La recette secrète, c'est que FQTree réalise que tous les membres de l'équipe de décision ne sont pas également importants. Les premiers membres, qui prennent les décisions majeures et évidentes, doivent être très précis. Les membres suivants, qui ne font que de petits ajustements pour corriger de petites erreurs, n'ont pas besoin d'être aussi précis. FQTree détermine automatiquement exactement de quel « espace cérébral » chaque membre a besoin. Il donne plus de bits (plus de détails) aux grands penseurs et moins de bits (moins de détails) aux petits penseurs, économisant ainsi une quantité massive d'espace. Il utilise également une astuce appelée « repliement du biais » (bias folding), qui consiste à décaler tous les nombres afin qu'ils soient tous positifs, permettant au matériel de supprimer le bit de signe et de devenir encore plus simple.

Une fois que l'équipe est entraînée de cette manière efficace, le cadre QXGB agit comme un traducteur magique. Il prend l'équipe entraînée et construit instantanément un plan matériel personnalisé pour une puce, sans avoir besoin qu'un ingénieur humain redessine les circuits pour chaque nouveau design. Les résultats sont impressionnants : sur trois tests différents (un pour la reconnaissance de chiffres écrits à la main, un pour repérer des particules de jet en physique, et un pour trouver des intrus sur un réseau), cette méthode a utilisé entre 26 % et 57 % d'espace matériel en moins (spécifiquement des tables de correspondance, ou LUTs) que les meilleures méthodes actuelles, tout en maintenant une précision aussi élevée ou même supérieure. Dans certains cas, elle a même rendu les décisions deux fois plus vite. C'est une situation gagnant-gagnant : le robot devient plus petit, plus rapide et tout aussi intelligent.

Résumé Technique : FQTree – Quantification à Grain Fin et Génération Matérielle d'Arbres de Décision Boostés

Énoncé du Problème

Les arbres de décision boostés (BDT - Boosted Decision Trees) sont largement utilisés dans les applications à latence critique en raison de leurs performances prédictives et de leur taille compacte, ce qui les rend adaptés au déploiement sur FPGA (Field-Programmable Gate Array). Cependant, une implémentation matérielle efficace reste un défi. Les conceptions de BDT existantes orientées FPGA reposent généralement sur des représentations à virgule fixe uniformes ou ajustées manuellement sur l'ensemble du modèle. Cette approche ne tient pas compte des rôles numériques hétérogènes des différents composants du BDT (caractéristiques d'entrée, seuils de division, valeurs de feuilles et logique d'accumulation), ce qui conduit souvent à des coûts matériels inutiles ou à une dégradation évitable de la précision.

De plus, la quantification post-entraînement (PTQ - Post-Training Quantization) directe est souvent inefficace pour les BDT. Contrairement aux réseaux de neurones où la quantification perturbe l'arithmétique de manière continue, la quantification des BDT peut provoquer des changements de routage discrets ; de petites perturbations des caractéristiques ou des seuils peuvent inverser les décisions de branchement, modifiant entièrement la feuille sélectionnée. Cette sensibilité nécessite une approche de quantification consciente de la quantification (QAT - Quantization-Aware Training) qui expose le modèle aux effets de la quantification pendant l'optimisation, permettant aux paramètres numériques de s'adapter à la précision réduite tout en préservant la qualité prédictive.

Méthodologie

L'Algorithme FQTree

Les auteurs proposent FQTree, un algorithme de QAT à grain fin conscient du matériel pour les BDT. Contra-irement à la PTQ, FQTree intègre la quantification directement dans la boucle d'entraînement.

Boosting avec Quantification : Pendant le processus de boosting par étapes, chaque nouvel arbre ajusté est immédiatement quantifié avant d'être utilisé dans les étapes d'entraînement suivantes. Cela garantit que les arbres ultérieurs s'adaptent aux erreurs résiduelles de l'ensemble déjà quantifié, compensant à la fois les résidus de la tâche et la distorsion induite par la quantification.
Schéma de Quantification des Valeurs de Feuilles : L'innovation centrale est une stratégie de quantification des valeurs de feuilles orientée vers le matériel. Au lieu d'une précision uniforme, FQTree assigne la précision en fonction de la magnitude des valeurs de feuilles :
- Pas Global et Décalage par Arbre : Un pas de quantification global ( $s$ ) est utilisé pour l'ensemble, combiné à un facteur de décalage par arbre ( $f(\vec{v})$ ).
- Représentation Entière Non Négative : Le schéma transforme les valeurs de feuilles en entiers non négatifs compacts. Les valeurs négatives sont écrêtées à zéro, et un décalage est appliqué pour supprimer le bit de signe, simplifiant ainsi le chemin de données.
- Repli du Biais (Bias Folding) : L'offset supprimé lors du rebasage est replié dans un terme de biais au niveau de l'arbre ou de la classe, qui est ajouté une seule fois après l'accumulation, plutôt que d'être transporté à travers chaque chemin d'arbre.
- Largeur de Bits Dynamique : La largeur de bits pour chaque arbre ( $b_t$ ) est déterminée par la plage dynamique de ses valeurs entières quantifiées ( $\lceil \log_2(\max(\vec{v}'_{int}) + 1) \rceil$ ). Les premiers arbres, qui contribuent davantage à la prédiction finale, reçoivent naturellement plus de bits, tandis que les arbres correctifs ultérieurs utilisent moins de bits.
Quantification des Caractéristiques/Seuils : Une quantification uniforme standard est appliquée aux caractéristiques et aux seuils, leur précision étant naturellement alignée dans le matériel via des soustracteurs signés.

Le Framework QXGB

Pour combler le fossé entre l'entraînement et le déploiement, les auteurs introduisent QXGB (Quantized XGBoost), un compilateur pour la génération automatique de matériel.

Représentation de Flux de Données : Le BDT quantifié et entraîné est abaissé vers une représentation intermédiaire (IR) étendue de l'ensemble d'instructions d'arithmétique distribuée (DAIS). Cet IR est étendu avec une instruction MUX explicite pour capturer le routage conditionnel des nœuds de décision, traitant l'inférence BDT comme un noyau de flux de données sans état.
Génération Automatique : Le compilateur trace symboliquement le graphe de calcul et génère du code RTL ou HLS (High-Level Synthesis) synthétisable. Ce flux supporte l'émulation bit-à-bit et permet une exploration systématique du compromis précision-latence-ressources sans redessin manuel.

Contributions Clés

Algorithme FQTree : Une approche QAT à grain fin présentant une formulation de quantification des valeurs de feuilles orientée matériel qui utilise un pas global, un décalage par arbre et un repli de biais pour permettre des représentations entières non négatives compactes.
Framework QXGB : Un flux évolutif basé sur un compilateur pour générer des implémentations BDT sur FPGA efficaces et à faible latence pour HLS et RTL, minimisant la latence et l'utilisation des ressources.
Évaluation Complète : Démonstration que la méthode réduit l'utilisation des tables de correspondance (LUT) de 26 à 57 % par rapport aux conceptions de BDT sur FPGA de pointe tout en égalant ou en améliorant la précision.

Résultats Expérimentaux

La méthode a été évaluée sur trois jeux de données : JSC (Classification de la sous-structure des jets en physique des hautes énergies), MNIST (classification de chiffres manuscrits) et NID (Détection d'intrusion réseau).

Jeu de données JSC : FQTree a atteint une précision de 75,7 % avec 1 652 LUTs et 2 cycles (4,0 ns). Comparé à TreeLUT (75,6 % de précision, 2 234 LUTs, 3 cycles), FQTree améliore la précision tout en réduisant l'usage des LUT et la profondeur du pipeline. À un point de coût inférieur, FQTree atteint 74,8 % de précision avec seulement 548 LUTs (31 % de moins que TreeLUT) et une latence de 1 cycle.
Jeu de données MNIST : La configuration de plus haute précision a atteint 97,7 % de précision avec 8 147 LUTs et 2 cycles, surpassant la meilleure performance précédente (POLYBiNN, 97,2 %) avec une latence et une utilisation de ressources nettement moindres. À des points modérés, FQTree a atteint 96,7 % de précision avec 2 744 LUTs, représentant une réduction d'environ 39 % des LUTs par rapport à TreeLUT pour une précision similaire.
Jeu de données NID : FQTree a atteint 93,1 % de précision avec seulement 157 LUTs et 1 cycle, soit une réduction d'environ 55 % des LUTs par rapport à TreeLUT (92,7 % de précision, 345 LUTs).
Base de Référence PTQ : Comparé à une base de quantification post-entraînement utilisant le même quantificateur, FQTree a systématiquement fourni de meilleurs compromis précision-ressources, confirmant que les gains proviennent à la fois de la conception du quantificateur et du processus d'optimisation QAT.

Signification et Revendications

Le papier affirme fournir le premier flux unifié pour le déploiement sur FPGA des BDT qui combine une quantification des valeurs de feuilles orientée matériel, une quantification consciente de la quantification et une génération automatique de matériel.

Les auteurs soulignent que leur approche répond aux défis spécifiques des BDT, où la quantification affecte les décisions de routage, et non seulement la précision arithmétique. En intégrant un contrôle de précision à grain fin dans l'entraînement et en automatisant la génération de matériel via le framework QXGB, la méthode permet une exploration systématique du compromis précision-latence-ressources. Les résultats démontrent que FQTree peut identifier des implémentations compactes et de haute qualité qui surpassent nettement les conceptions de pointe existantes en termes d'efficacité matérielle (usage des LUT) tout en maintenant ou en améliorant la précision prédictive.