🤖 machine learning

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

Dit artikel presenteert FQTree, een algoritme voor fijnmazige quantization-aware training gecombineerd met het QXXGB hardwaregeneratieframework, dat boosted decision trees optimaliseert voor FPGA-implementatie door het LUT-gebruik met 26–57% te verminderen terwijl de nauwkeurigheid gelijk blijft of wordt verbeterd.

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

Gepubliceerd 2026-08-13

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren beslissingen te nemen, zoals een scheidsrechter in een videogame of een uitsmijter bij een club. Je wilt niet dat de robot een trage, zware denker is; je wilt dat hij razendsnel is en in een fractie van een seconde keuzes maakt zonder te haperen. Dit is de wereld van "Boosted Decision Trees" (BDT's). Denk aan een BDT niet als één groot brein, maar als een team van veel kleine, eenvoudige besluitvormers. Elk teamlid stelt een simpele vraag zoals: "Is de temperatuur boven de 20 graden?" of "Is de snelheid hoger dan 50 mph?". Op basis van het antwoord geven ze het stokje door aan de volgende persoon in de rij. Aan het einde van de rij heeft het hele team hun meningen bij elkaar opgeteld om tot een definitieve beslissing te komen. Deze teams staan erom bekend heel goed te zijn in het herkennen van patronen in rommelige data, maar ze hebben een probleem: ze zijn vaak te zwaar en te traag voor de piepkleine, supersnelle chips (genaamd FPGA's) die real-time systemen aandrijven, zoals zelfrijdende auto's of experimenten in de deeltjesfysica.

De grote uitdaging is dat deze besluitvormingsteams meestal worden getraind met "zwevende" getallen (zoals 3,14159...), die weliswaar precies zijn, maar veel ruimte en energie kosten om op te slaan. Om deze op kleine chips te laten draaien, proberen ingenieurs deze getallen meestal in kleinere, eenvoudigere dozen te persen (zoals gehele getallen). Maar dat is alsof je probeert een enorme, wiebelige gelei in een kleine, stijve doos te proppen: als je ze simpelweg erin perst nadat de gelei al is gestold, breekt het, en begint de robot domme fouten te maken. De oude methode was om de juiste doosgrootte voor iedereen te raden, wat vaak ruimte verspilde of de intelligentie van de robot aantastte.

Dit artikel introduceert een slimme nieuwe methode genaamd FQTree (Fine-grained Quantization Tree) en een bijbehorend hulpmiddel genaamd QXGB die verandert hoe we deze besluitvormingsteams bouwen. In plaats van het team te trainen met grote, zwevende getallen en ze later te proberen in een doos te persen, leert FQTree het team om in kleine, eenvoudige dozen te denken terwijl ze aan het leren zijn. Het is alsof je een turner traint om vanaf dag één een oefening op een smalle balk uit te voeren, in plaats van hem eerst op een brede vloer te laten oefenen en hem dan vlak voor de wedstrijd dwingen om op de balk te staan.

Het geheime ingrediënt is dat FQTree beseft dat niet alle teamleden even belangrijk zijn. De eerste leden, die de grote, voor de hand liggende beslissingen nemen, moeten zeer precies zijn. De latere leden, die slechts kleine aanpassingen maken om kleine fouten te herstellen, hoeven minder precies te zijn. FQTree rekent automatisch uit hoeveel "hersencapaciteit" elk lid nodig heeft. Het geeft de grote denkers meer bits (meer detail) en de kleine denkers minder bits (minder detail), wat een enorme hoeveelheid ruimte bespaart. Het gebruikt ook een truc genaamd "bias folding", wat lijkt op het verschuiven van alle getallen zodat ze allemaal positief zijn, waardoor de hardware het teken-bit kan weglaten en nog eenvoudiger wordt.

Zodra het team op deze efficiënte manier is getraind, fungeert het QXGB-framework als een magische vertaler. Het neemt het getrainde team en bouwt direct een op maat gemaakt hardware-ontwerp voor een chip, zonder dat er een menselijke ingenieur de circuits opnieuw hoeft te ontwerpen voor elk nieuw ontwerp. De resultaten zijn indrukwekkend: bij drie verschillende tests (één voor het herkennen van handgeschreven cijfers, één voor het opsporen van jet-deeltjes in de fysica, en één voor het vinden van netwerkindringers) gebruikte deze methode 26% tot 57% minder hardwareruimte (specifiek Look-Up Tables, of LUT's) dan de huidige beste methoden, terwijl de nauwkeurigheid net zo hoog bleef of zelfs verbeterde. In sommige gevallen maakte het de beslissingen zelfs twee keer zo snel. Het is een win-win: de robot wordt kleiner, sneller en net zo slim.

Technische Samenvatting: FQTree – Fijnmazige Kwantisatie en Hardwaregeneratie van Boosted Decision Trees

Probleemstelling

Boosted Decision Trees (BDT's) worden veel gebruikt in latency-kritische toepassingen vanwege hun voorspellende prestaties en compacte omvang, wat ze geschikt maakt voor implementatie op Field-Programmable Gate Arrays (FPGA's). De efficiënte hardware-implementatie blijft echter een uitdaging. Bestaande FPGA-georiënteerde BDT-ontwerpen vertrouwen doorgaans op uniforme of handmatig afgestemde fixed-point representaties voor het gehele model. Deze aanpak houdt geen rekening met de heterogene numerieke rollen van verschillende BDT-componenten (input features, splitsingsdrempels, bladwaarden en accumulatie-logica), wat vaak leidt tot onnodige hardwarekosten of vermijdbare degradatie van de nauwkeurigheid.

Bovendien is eenvoudige post-training kwantisatie (PTQ) vaak ineffectief voor BDT's. In tegenstelling tot neurale netwerken, waarbij kwantisatie de aritmetiek continu verstoort, kan BDT-kwantisatie discrete routeringswijzigingen veroorzaken; kleine perturbaties in features of drempels kunnen vertakkingsbeslissingen omdraaien, waardoor de geselecteerde blad volledig verandert. Deze gevoeligheid vereist een Quantization-Aware Training (QAT) aanpak die het model blootstelt aan kwantisatie-effecten tijdens de optimalisatie, zodat numerieke parameters kunnen adapteren aan verminderde precisie terwijl de voorspellende kwaliteit behouden blijft.

Methodologie

Het FQTree Algoritme

De auteurs stellen FQTree voor, een hardware-bewust, fijnmazig QAT-algoritme voor BDT's. In tegenstelling tot PTQ integreert FQTree kwantisatie direct in de trainingslus.

Boosting met Kwantisatie: Tijdens het fasegewijze boostingproces wordt elke nieuw passende boom onmiddellijk gekwantiseerd voordat deze in opeenvolgende trainingsfasen wordt gebruikt. Dit zorgt ervoor dat latere bomen zich aanpassen aan de residuen van het reeds gekwantiseerde ensemble, waardoor zowel taakresiduen als kwantisatie-geïnduceerde vervorming worden gecompenseerd.
Bladwaarde-kwantisatieschema: De kerninnovatie is een hardware-georiënteerde strategie voor de kwantisatie van bladwaarden. In plaats van uniforme precisie, wijst FQTree precisie toe op basis van de magnitude van de bladwaarden:
- Globale Stap & Boom-wijze Verschuiving: Een globale kwantisatiestapgrootte ( $s$ ) wordt gebruikt over het gehele ensemble, gecombineerd met een boom-wijze verschuivingsfactor ( $f(\vec{v})$ ).
- Niet-negatieve Gehele Getal Representatie: Het schema transformeert bladwaarden naar compacte niet-negatieve gehele getallen. Negatieve waarden worden naar nul afgekapt, en een verschuiving wordt toegepast om het tekenbit te verwijderen, wat de datapad vereenvoudigt.
- Bias Folding: De offset die tijdens het herbasen wordt verwijderd, wordt gevouwen in een boom-niveau of klasse-niveau bias-term, die slechts één keer na de accumulatie wordt toegevoegd, in plaats van door elke boom-pad te worden meegedragen.
- Dynamische Bitbreedte: De bitbreedte voor elke boom ( $b_t$ ) wordt bepaald door het dynamische bereik van de gekwantiseerde gehele getalwaarden ( $\lceil \log_2(\max(\vec{v}'_{int}) + 1) \rceil$ ). Vroege bomen, die meer bijdragen aan de uiteindelijke voorspelling, ontvangen van nature meer bits, terwijl latere corrigerende bomen minder bits gebruiken.
Feature/Drempel Kwantisatie: Standaard uniforme kwantisatie wordt toegepast op features en drempels, waarbij hun precisie in hardware natuurlijk wordt uitgelijnd via gesigneerde aftrekkers.

Het QXGB Framework

Om de kloof tussen training en implementatie te overbruggen, introduceren de auteurs QXGB (Quantized XGBoost), een compiler-gebaseerd framework voor automatische hardwaregeneratie.

Dataflow Representatie: De getrainde gekwantiseerde BDT wordt verlaagd naar een uitgebreide Distributed Arithmetic Instruction Set (DAIS) intermediate representation (IR). Deze IR is uitgebreid met een expliciete MUX instructie om de conditionele routering van beslissingsnodes vast te leggen, waarbij BDT-inferentie wordt behandeld als een stateless dataflow kernel.
Automatische Generatie: De compiler volgt de computationele grafiek symbolisch en genereert synthetiseerbare RTL of High-Level Synthesis (HLS) code. Deze flow ondersteunt bit-exacte emulatie en maakt systematische exploratie van de accuracy-latency-resource trade-off mogelijk zonder handmatige herontwerp.

Belangrijkste Bijdragen

FQTree Algoritme: Een fijnmazige QAT-aanpak met een hardware-georiënteerde bladwaarde-kwantisatieformulering die gebruikmaakt van een globale stap, boom-wijze verschuiving en bias folding om compacte, niet-negatieve gehele getal representaties mogelijk te maken.
QXGB Framework: Een schaalbare, compiler-gebaseerde flow voor het genereren van efficiënte, lage-latency FPGA BDT-implementaties voor zowel HLS als RTL, waarbij latency en resourcegebruik worden geminimaliseerd.
Uitgebreide Evaluatie: Demonstratie dat de methode het Look-Up Table (LUT) gebruik met 26–57% vermindert vergeleken met state-of-the-art FPGA-gebaseerde BDT-ontwerpen, terwijl de nauwkeurigheid gelijk blijft of verbetert.

Experimentele Resultaten

De methode werd geëvalueerd op drie datasets: JSC (Jet Substructure Classification in high-energy physics), MNIST (handgeschreven cijferclassificatie) en NID (Network Intrusion Detection).

JSC Dataset: FQTree bereikte 75,7% nauwkeurigheid met 1.652 LUT's en 2 cycli (4,0 ns). Vergeleken met TreeLUT (75,6% nauwkeurigheid, 2.234 LUT's, 3 cycli), verbeterde FQTree de nauwkeurigheid terwijl het LUT-gebruik met ~26% verminderde en de pipeline diepte verkleinde. Op een lager-kosten punt bereikte FQTree 74,8% nauwkeurigheid met slechts 548 LUT's (31% minder dan TreeLUT) en 1 cyclus latency.
MNIST Dataset: De configuratie met de hoogste nauwkeurigheid bereikte 97,7% nauwkeurigheid met 8.147 LUT's en 2 cycli, waarmee het de vorige beste (POLYBiNN, 97,2%) versloeg met aanzienlijk lagere latency en resourcegebruik. Op gematigde punten bereikte FQTree 96,7% nauwkeurigheid met 2.744 LUT's, wat een ~39% reductie in LUT's betekent vergeleken met TreeLUT voor vergelijkbare nauwkeurigheid.
NID Dataset: FQTree bereikte 93,1% nauwkeurigheid met slechts 157 LUT's en 1 cyclus, een ~55% reductie in LUT's vergeleken met TreeLUT (92,7% nauwkeurigheid, 345 LUT's).
PTQ Baseline: Wanneer vergeleken met een Post-Training Quantization baseline die dezelfde kwantizer gebruikte, bood FQTree consequent betere accuracy-resource trade-offs, wat bevestigt dat de winsten voortkomen uit zowel het ontwerp van de kwantizer als het QAT-optimalisatieproces.

Betekenis en Claims

Het artikel claimt de eerste verenigde workflow te bieden voor de FPGA-implementatie van BDT's die hardware-georiënteerde bladwaarde-kwantisatie, quantization-aware training en automatische hardwaregeneratie combineert.

De auteurs benadrukken dat hun aanpak de specifieke uitdagingen van BDT's aanpakt, waarbij kwantisatie de routeringsbeslissingen beïnvloedt, niet alleen de aritmetische precisie. Door fijnmazige precisiecontrole in de training te integreren en de hardwaregeneratie te automatiseren via het QXGB framework, maakt de methode systematische exploratie van de accuracy-latency-resource trade-off mogelijk. De resultaten demonstreren dat FQTree compacte, hoogwaardige implementaties kan identificeren die bestaande state-of-the-art ontwerpen aanzienlijk overtreffen in termen van hardware-efficiëntie (LUT-gebruik) terwijl de voorspellende nauwkeurigheid gelijk blijft of verbetert.