RS-ORT: Neuer Branch-and-Bound-Algorithmus für optimale Regressionsbäume

Mixed-Integer-Programming (MIP) hat sich als leistungsstarkes Werkzeug für die Konstruktion optimaler Entscheidungsbäume etabliert. Bisher beschränken sich MIP‑Ansätze für Regressionsaufgaben jedoch häufig auf ausschließlich binäre Merkmale oder werden bei kontinuierlichen, großskaligen Datensätzen schnell unhandlich. Durch die Naiv‑Binarisierung kontinuierlicher Features geht dabei oft die globale Optimalität verloren und die resultierenden Bäume werden unnötig tief.

Die neue Methode RS-ORT (Reduced‑Space Optimal Regression Trees) löst das Problem, indem sie das Training als zweistufiges Optimierungsproblem formuliert und einen Branch‑and‑Bound‑Algorithmus einsetzt, der ausschließlich an baustrukturellen Variablen grenzt. Diese spezielle Struktur garantiert die Konvergenz des Algorithmus und macht ihn unabhängig von der Anzahl der Trainingsproben.

Um die Laufzeit weiter zu reduzieren, nutzt RS-ORT mehrere Bound‑Tightening‑Techniken: geschlossene Formeln für Blattvorhersagen, empirische Diskretisierung von Schwellenwerten und exakte Analyse von Teilbäumen der Tiefe 1. Diese Methoden werden mit dekomponierbaren oberen und unteren Schranken kombiniert, die die Trainingsgeschwindigkeit signifikant erhöhen.

Dank der knotenweisen Zerlegung lässt sich der Algorithmus trivial parallelisieren, was die Rechenintensität bei Datensätzen mit Millionen von Beobachtungen weiter senkt. In umfangreichen Benchmarks, die sowohl binäre als auch kontinuierliche Merkmale enthalten, übertrifft RS-ORT die führenden Verfahren in Training und Testleistung. Besonders beeindruckend ist die Fähigkeit, bei bis zu 2 Millionen kontinuierlichen Daten ein garantiert optimales Ergebnis mit einem einfacheren Baustruktur zu liefern.