GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent

2023/05/05 by Sascha Marton, Marton, Sascha, Stefan Lüdtke +5 · 1 citation
Computer Science · #Machine Learning and Data Classification #Explainable Artificial Intelligence (XAI) #Domain Adaptation and Few-Shot Learning

paper · pdf · doi:10.48550/arxiv.2305.03515

Abstract

Decision Trees (DTs) are commonly used for many machine learning tasks due to their high degree of interpretability. However, learning a DT from data is a difficult optimization problem, as it is non-convex and non-differentiable. Therefore, common approaches learn DTs using a greedy growth algorithm that minimizes the impurity locally at each internal node. Unfortunately, this greedy procedure can lead to inaccurate trees. In this paper, we present a novel approach for learning hard, axis-aligned DTs with gradient descent. The proposed method uses backpropagation with a straight-through operator on a dense DT representation, to jointly optimize all tree parameters. Our approach outperforms existing methods on binary classification benchmarks and achieves competitive results for multi-class tasks. The method is available under: https://github.com/s-marton/GradTree

Cited by

• LHT: Statistically-Driven Oblique Decision Trees for Interpretable Classification

Related

• GRANDE: Gradient-Based Decision Tree Ensembles for Tabular Data
• Branches: Efficiently Seeking Optimal Sparse Decision Trees with AO*
• GBDT-MO: Gradient Boosted Decision Trees for Multiple Outputs
• Learning Representations for Axis-Aligned Decision Forests through Input\n Perturbation
• Learning Multi-Layered GBDT Via Back Propagation