Learning tree-based models with gradient descent

Marton, Sascha

Vorschau

PDF
SaschaMartonDiss.pdf - Veröffentlichte Version
Download (9MB)

URN:	urn:nbn:de:bsz:180-madoc-704810
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2025
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Stuckenschmidt, Heiner
Datum der mündl. Prüfung:	2025
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science II: Artificial Intelligence (Stuckenschmidt 2009-) Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
Fachgebiet:	004 Informatik
Freie Schlagwörter (Englisch):	decision trees , tree-based models , gradient descent
Abstract:	Tree-based models are widely recognized for their interpretability and have proven effective in various application domains, particularly in high-stakes domains. In addition, their hierarchical structure and axis-aligned splits can provide a beneficial inductive bias, especially for heterogeneous tabular data. However, learning decision trees poses a significant challenge due to their combinatorial complexity and discrete, non-differentiable nature. As a result, traditional methods such as CART, which rely on greedy search procedures, remain the most widely used approaches. These methods make locally optimal decisions at each node, constraining the search space and often leading to suboptimal tree structures. Additionally, their demand for custom training methods precludes a seamless integration into modern machine learning approaches, such as those employed in multimodal or reinforcement learning, where optimization is typically achieved via gradient descent and backpropagation. In this thesis, we propose a novel method for learning hard, axis-aligned decision trees through gradient descent. Our approach utilizes backpropagation with a straight-through operator on a dense decision tree representation, enabling the joint optimization of all tree parameters. We further extend this method to tree ensembles including a novel, instance-wise weighting scheme, allowing for a trade-off between performance and interpretability. By introducing gradient-based optimization for hard, axis-aligned decision trees, our method addresses the two primary limitations of traditional decision tree algorithms. First, gradient-based training is not constrained by the sequential selection of locally optimal splits but, instead, jointly optimizes all tree parameters. Second, by leveraging gradient descent for optimization, our approach seamlessly integrates into existing machine learning approaches e.g., for multimodal and reinforcement learning tasks, which inherently rely on gradient descent. These advancements allow us to achieve state-of-the-art results across multiple domains, including interpretable decision trees for small tabular datasets, advanced models for complex tabular data, multimodal learning, and interpretable reinforcement learning without information loss. By bridging the gap between decision trees and gradient-based optimization, our method significantly enhances the performance and applicability of tree-based models across various machine learning domains.
Übersetzter Titel:	Lernen von Entscheidungsbäumen durch Gradientenbasierte Verfahren (Deutsch)
Übersetzung des Abstracts:	Entscheidungsbäume sind weithin für ihre Interpretierbarkeit anerkannt und haben sich in verschiedenen Anwendungsbereichen, insbesondere in kritischen Bereichen, als effektiv erwiesen. Darüber hinaus kann ihre hierarchische Struktur mit achsenparallelen Splits einen vorteilhaften induktiven Bias bieten, insbesondere für heterogene tabellarische Daten. Allerdings stellt das Lernen von Entscheidungsbäumen eine erhebliche Herausforderung dar, da sie eine kombinatorische Komplexität aufweisen und ihre diskrete, nicht differenzierbare Natur eine direkte Optimierung erschwert. Daher sind traditionelle Methoden wie CART, die auf gierigen Suchverfahren basieren, nach wie vor die am häufigsten verwendeten Ansätze. Diese Methoden treffen an jedem Knoten lokal optimale Entscheidungen, wodurch der Suchraum eingeschränkt wird und häufig suboptimale Baumstrukturen entstehen. Zudem erfordern sie spezielle Trainingsverfahren, die eine nahtlose Integration in moderne maschinelle Lernansätze verhindern – etwa in multimodalen Lernverfahren oder Reinforcement Learning, bei denen die Optimierung typischerweise über Gradientenabstieg und Backpropagation erfolgt. In dieser Arbeit stellen wir eine neuartige Methode zur Optimierung diskreter, achsenparalleler Entscheidungsbäume mittels Gradientenabstieg vor. Unser Ansatz nutzt Backpropagation mit einem Straight-Through-Operator auf einer dichten Entscheidungsbaumdarstellung, wodurch eine gemeinsame Optimierung aller Baumparameter ermöglicht wird. Darüber hinaus erweitern wir diese Methode auf Ensembles und führen ein neuartiges, instanzbasiertes Gewichtungsschema ein, das eine Abwägung zwischen Leistung und Interpretierbarkeit erlaubt. Durch die Einführung einer gradientenbasierten Optimierung für diskrete, achsenparallele Entscheidungsbäume adressiert unsere Methode die beiden zentralen Einschränkungen traditioneller Entscheidungsbaumalgorithmen. Erstens ist das gradientenbasierte Training nicht auf die sequentielle Auswahl lokal optimaler Splits beschränkt, sondern optimiert alle Baumparameter gemeinsam. Zweitens ermöglicht die Nutzung des Gradientenabstiegs eine nahtlose Integration in bestehende maschinelle Lernverfahren, beispielsweise für multimodale Lernaufgaben oder Reinforcement Learning, die intrinsisch auf Gradientenabstieg basieren. Diese Fortschritte ermöglichen es uns, in mehreren Anwendungsbereichen State-of-the-Art-Ergebnisse zu erzielen – von interpretierbaren Entscheidungsbäumen für kleine tabellarische Datensätze über fortgeschrittene Modelle für komplexe tabellarische Daten bis hin zu multimodalem Lernen und interpretierbarem Reinforcement Learning ohne Informationsverlust. Indem unsere Methode die Lücke zwischen Entscheidungsbäumen und gradientenbasierter Optimierung schließt, steigert sie die Leistungsfähigkeit und Anwendbarkeit baumbasierter Modelle erheblich in verschiedenen maschinellen Lernbereichen. (Deutsch)