TL;DR
This thesis introduces GradTree and GRANDE, novel frameworks that allow hard, axis-aligned decision trees to be trained using gradient descent rather than traditional greedy algorithms. By making trees differentiable via the "straight-through operator," the author enables decision trees to be integrated directly into modern deep learning and reinforcement learning pipelines, achieving state-of-the-art performance on tabular data and interpretable robotics tasks.
What Problem Does This Paper Address?
Decision trees (DTs) are the "gold standard" for tabular data and high-stakes domains because they are inherently interpretable—you can follow the logic of a decision step-by-step. However, they have two major Achilles' heels:
- Local Optimality: Traditional algorithms like CART are "greedy." They pick the best split for the current node without considering how it affects the rest of the tree. This often leads to suboptimal structures.
- Non-Differentiability: Trees are discrete "if-then" structures. You can't calculate a gradient for them, which means you can't train them using backpropagation. This makes it nearly impossible to use trees as components inside a larger neural network or to train them directly for complex tasks like Reinforcement Learning (RL).
Sascha Marton’s thesis tackles these challenges by reformulating the decision tree into a differentiable architecture that retains the "hard" (discrete) splits that make trees interpretable.
Methods
The core innovation is GradTree, which uses several clever tricks to make trees "gradient-friendly":
- Dense Tree Representation: Instead of a nested structure, the tree is represented as a series of matrix operations. Feature selection and thresholds are stored in matrices, allowing for parallel computation.
- The Straight-Through (ST) Operator: To handle the non-differentiable nature of "hard" splits (e.g., is Age > 25?), the author uses the ST operator. In the forward pass, the model uses the discrete, hard decision. In the backward pass, it skips the discrete step and passes the gradient through a smooth approximation (like a sigmoid or softsign function).
- Softsign Activation: The thesis finds that the
softsignfunction provides a more robust gradient signal than the standardsigmoid, especially when data points are far from the decision threshold. - GRANDE (Ensembles): This extension applies GradTree to ensembles. It introduces a novel instance-wise weighting scheme, where each sample is assigned a different weight for each tree in the forest based on which leaf node it lands in. This allows different trees to "specialize" in different regions of the data.
- SYMPOL: A framework for using these trees in Reinforcement Learning, allowing a symbolic tree policy to be optimized directly using policy gradients.
Datasets
The author validates the approach across a massive range of benchmarks:
- Tabular Data: 22 small-to-medium datasets (from the UCI repository) for single trees and 19 complex binary classification datasets for ensembles.
- Multimodal Data: The PAD-UFES-20 skin lesion dataset, which combines clinical images with tabular patient metadata.
- Reinforcement Learning: Standard control tasks (CartPole, Acrobot, LunarLander, MountainCar) and the MiniGrid environment for testing goal misgeneralization.
Key Insights and Ideas
- Joint Optimization vs. Greedy Search: Because GradTree uses gradient descent, it optimizes all nodes in the tree simultaneously. The thesis demonstrates that this allows the model to find "globally" better splits that greedy algorithms like CART miss.
- Axis-Alignment is a Feature, Not a Bug: While many "soft" tree methods use oblique splits (linear combinations of features), this thesis argues that keeping splits axis-aligned (one feature at a time) provides a crucial inductive bias for tabular data and preserves human readability.
- Eliminating "Information Loss" in RL: Traditionally, to get an interpretable RL policy, researchers train a neural network and then "distill" it into a tree. This usually results in a performance drop. SYMPOL trains the tree directly, solving the environment with no loss in fidelity.
- Interpretability via Instance-Wise Weights: In GRANDE, you can see exactly which tree in an ensemble was most responsible for a specific prediction, providing "local" explanations that are much simpler than standard forest models.
Key Results
- Tabular Superiority: GradTree outperformed CART on 13 out of 22 binary classification datasets. GRANDE (the ensemble version) achieved state-of-the-art results, often outperforming heavyweights like XGBoost and CatBoost on various benchmarks.
- Multimodal Gains: In the skin lesion task, replacing a standard MLP tabular backbone with a GRANDE backbone improved the overall multimodal model's accuracy from 0.791 to 0.823.
- Compact RL Policies: SYMPOL solved complex RL tasks using trees with an average of only 50 nodes. Competing distillation methods often required over 1,000 nodes to reach similar performance levels.
Limitations and Future Work
The author identifies a few areas for improvement:
- Uninformative Gradients: Gradients for feature selection can sometimes be "flat," meaning the model has to rely on trial and error (random restarts) to find the best features to split on.
- Scalability: The dense representation requires memory proportional to the number of features at every node, which can be a bottleneck for extremely high-dimensional datasets.
- High Cardinality: Currently, the method requires categorical features to be numerically encoded (e.g., one-hot), which can explode the feature space.
Future Directions: The thesis suggests exploring "Recurrent Decision Trees" for time-series data and fine-tuning pre-trained greedy trees (like those from XGBoost) using gradient descent to further refine their performance.
Summary updated