Approximation-Free Differentiable Oblique Decision Trees

Technische Samenvatting: Benaderingsvrije Differentieerbare Obliq Decision Trees

Probleemstelling
Decision Trees (DTs) worden in veiligheidskritieke domeinen (bijvoorbeeld medische diagnose) zeer gewaardeerd om hun interpreteerbaarheid en effectiviteit op tabulaire data. Het trainen van nauwkeurige obliq DTs (waarbij splitsingen lineaire combinaties van kenmerken zijn in plaats van langs de assen gericht) is echter computationeel uitdagend vanwege de NP-moeilijke aard van de zoekruimte. Hoewel recente differentieerbare benaderingen gradient-based training mogelijk maken, vertrouwen deze op benaderingen die de integriteit van het leerproces in gevaar brengen:

1. Soft DTs: Gebruiken probabilistische "zachte" grenzen (bijvoorbeeld Sigmoid-activaties) om bomen differentieerbaar te maken, maar het converteren van deze naar "harde" beslissingen leidt vaak tot een afname van de nauwkeurigheid.
2. Straight-Through Estimators (STE): Worden gebruikt in methoden zoals DGT en ICCT om gradiënten door niet-differentieerbare harde beslissingen te benaderen. Dit creëert een semantisch verschil tussen de forward pass (evaluatie) en de backward pass (optimalisatie). Bij regressietaken leidt dit verschil tot bevooroordeelde gradiëntupdates, structurele instabiliteit en een onderbenutting van leaf-nodes, omdat interne parameters worden bijgewerkt op basis van alle regressors terwijl er slechts één wordt geselecteerd.

Methodologie: DTSemNet
De auteurs stellen DTSemNet voor, een nieuw neurale netwerk-architectuur die een semantisch equivalente, inverteerbare representatie van harde obliq DTs biedt. In tegenstelling tot eerdere werken maakt DTSemNet end-to-end training mogelijk met standaard gradient descent zonder benaderingen.

• Architectuur: DTSemNet codeert een DT met $m$ interne knopen en $n$ bladeren in een neurale netwerk met behulp van ReLU-activaties en lineaire operaties.
  • Interne Knopen: Worden weergegeven door lineaire lagen die $\langle A_i, x \rangle + b_i$ berekenen.
  • Vertakking: Gebruikt ReLU-activaties om positieve ($\top$) en negatieve ($\bot$) uitkomsten te scheiden, waarbij ervoor wordt gezorgd dat voor elke invoer exact één tak actief is (behalve op grenzen met maat nul).
  • Bladeren: Een lineaire laag met vaste gewichten aggregeert de actieve takken om logits voor elk blad te produceren.
• Semantische Equivalentie: Stelling 1 bewijst dat voor elke invoer $x$ het blad dat door de harde DT wordt geselecteerd, identiek is aan het blad met de hoogste output-logit in het DTSemNet-netwerk. De evaluatiefunctie (forward pass) en de optimalisatiefunctie (backward pass) zijn derhalve semantisch identiek.

Regressiestrategie: Annealed Top-k
Hoewel classificatie van nature aansluit bij deze formulering (via argmax), vereist regressie een gezamenlijke optimalisatie van het routing (interne knopen) en de leaf-regressors. De auteurs identificeren dat het gebruik van een enkele STE (zoals in hun vorige conferentiewerk) instabiliteit veroorzaakt omdat hierbij interne knopen worden bijgewerkt op basis van alle regressors, terwijl er per stap slechts één regressor wordt bijgewerkt.

Om dit op te lossen, introduceert het artikel een Annealed Top-k methode:

1. Mechanisme: In plaats van een harde Top-1 selectie tijdens het trainen, gebruikt het model aanvankelijk een Top-$k$ selector ($k \ge 2$) gecombineerd met een temperatuur-geschaalde Softmax. Dit stelt het model in staat invoer tegelijkertijd naar meerdere experts (bladeren) te routeren, waardoor informatieve gradiënten worden verkregen.
2. Annealing: De waarde van $k$ wordt geleidelijk verlaagd van $k \ge 2$ naar $k=1$ over de trainings-epochs.
3. Voordelen:
   • Gradiëntconsistentie: In tegenstelling tot STE delen de forward en backward pass op elke stap $k$ dezelfde semantiek.
   • Gebalanceerde Updates: Interne knopenparameters worden uitsluitend bijgewerkt op basis van de top-$k$ geselecteerde regressors, waardoor de destabiliserende invloed van verre, niet-geselecteerde bladeren wordt voorkomen.
   • Exploratie: Meerdere regressors worden bijgewerkt voor een enkel voorbeeld, waardoor het model zich kan aanpassen als de routingbeslissing later in het trainingsproces verschuift.
4. Fine-tuning: Zodra $k=1$ is bereikt, worden de interne knopen bevroren en worden de leaf-regressors gefine-tuned met vermeerderde voorbeelden om overfitting te voorkomen.

Belangrijkste Bijdragen

1. DTSemNet Architectuur: Een differentieerbare codering van obliq DTs die semantisch equivalent is aan de harde boom, waardoor exacte gradient descent training mogelijk is zonder benadering voor classificatie.
2. Annealed Top-k voor Regressie: Een nieuw trainingsproces dat de benadering en de bias inherent aan STE-gebaseerde methoden voor regressie elimineert, waardoor een stabiele en nauwkeurige gezamenlijke optimalisatie van routing en leaf-parameters wordt gewaarborgd.
3. Programmatic RL Policies: Demonstratie van DTSemNet als programmatic policy in Reinforcement Learning (RL), waarbij standaard Neurale Netwerken (NNs) worden vervangen in zowel discrete als continue actie-ruimtes.

Experimentele Resultaten
De auteurs hebben DTSemNet geëvalueerd tegenover state-of-the-art methoden (TAO, DGT, CRO-DT, CART, ICCT, VIPER) over classificatie-, regressie- en RL-benchmarks.

• Classificatie: DTSemNet behaalde de beste prestaties op elke geteste dataset, inclusief beknopte en dichte bomen. Het presteerde aanzienlijk beter dan niet-gradient methoden (bijvoorbeeld TAO, CRO-DT) en gradient-based benaderingen (DGT), met een vermindering van de classificatiefout tot 10% op uitdagende benchmarks zoals Optical Recognition. De trainingsduur was vergelijkbaar met DGT maar aanzienlijk sneller dan globale zoekmethodes.
• Regressie: DTSemNet met Top-k presteerde beter dan alle concurrenten op bijna alle datasets. Het behaalde een gemiddelde RMSE-verbetering van 3% ten opzichte van TAO-Linear en presteerde aanzienlijk beter dan DTSemNet-STE (dat STE gebruikte). Ablatiestudies bevestigden dat Top-k leidt tot een meer gebalanceerde bladbenutting en een stabiele gewichtsevolutie in vergelijking met STE, wat de neiging heeft bladeren te onderbenutten.
• Reinforcement Learning:
  • Discrete Acties: DTSemNet kwam overeen met of overtrof de NN-prestaties en presteerde aanzienlijk beter dan andere DT-gebaseerde policies (DGT, ICCT, VIPER) op omgevingen zoals LunarLander en Zerglings.
  • Continue Acties: Met behulp van de Top-k annealing strategie in combinatie met SAC, overtrof DTSemNet NN-baselines en STE-gebaseerde DTs op Continuous LunarLander en BipedalWalker, wat aantoont dat benaderingsvrije training superieure policies oplevert, zelfs bij continue controle.

Betekenis en Aanspraken
Het artikel beweert dat DTSemNet de eerste architectuur is die benaderingsvrije training voor obliq DTs bereikt in zowel classificatie- als regressiesettingen. Door het semantische verschil tussen evaluatie en optimalisatie te verwijderen, overwint het de instabiliteit en bias van STE-gebaseerde benaderingen. De auteurs betogen dat dit de kloof overbrugt tussen de interpreteerbaarheid van symbolische modellen (DTs) en de schaalbaarheid van gradient-based training, waardoor hoogpresterende, interpreteerbare modellen levensvatbaar worden voor veiligheidskritieke toepassingen en complexe RL-omgevingen.

Beperkingen en Toekomstig Werk
De auteurs erkennen dat DTSemNet, als DT, niet geschikt is voor hoogdimensionale invoer zoals afbeeldingen, waarbij het moeite heeft met complexe vormen. Toekomstig werk zal zich richten op het ontwikkelen van differentieerbare methoden voor adaptieve boomgroei en -snoei, waarbij wordt afgeweken van vaste boomhoogtes als hyperparameters.