🔢 mathematics

DT-PBO: an Interpretable Tree-based Surrogate Model for Preferential Bayesian Optimization

Der Artikel stellt DT-PBO vor, ein neuartiges interpretierbares baumbasiertes Surrogatmodell für die präferenzbasierte Bayessche Optimierung, das wettbewerbsfähige Leistung und Robustheit bei gleichzeitiger Bereitstellung transparenter Einblicke in die Präferenzen des Entscheidungsträgers erzielt und damit die Interpretierbarkeitsgrenzen traditioneller auf Gauß-Prozessen basierender Ansätze adressiert.

Ursprüngliche Autoren: Nick Leenders, Thomas Quadt, Boris Cule, Roy Lindelauf, Herman Monsuur, Joost van Oijen, Mark Voskuijl

Veröffentlicht 2026-05-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nick Leenders, Thomas Quadt, Boris Cule, Roy Lindelauf, Herman Monsuur, Joost van Oijen, Mark Voskuijl

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, das perfekte Stück Kuchen für einen Freund zu finden. Sie bitten ihn nicht, jeden Kuchen auf einer Skala von 1 bis 10 zu bewerten (weil das schwierig und verwirrend ist). Stattdessen stellen Sie einfache Fragen: „Bevorzugen Sie Schokolade oder Karotte?" „Wie sieht es mit Schokolade oder Vanille aus?"

Das ist der Kern der Präferentiellen Bayes'schen Optimierung (PBO): die Suche nach der „besten" Option durch eine Reihe von „A oder B?"-Fragen.

Lange Zeit haben Computer dies mit Gaußschen Prozessen (GPs) gelöst. Denken Sie an einen GP als einen superklugen, aber mysteriösen Zauberer. Er kann den besten Kuchen mit erstaunlicher Genauigkeit vorhersagen, behält aber seine Überlegungen in einer „Blackbox" versteckt. Wenn Sie den Zauberer fragen: „Warum haben Sie den Schokokuchen gewählt?", könnte er antworten: „Wegen einer komplexen mathematischen Formel, die den Abstand zwischen den Zutaten beinhaltet." Das ist nicht sehr hilfreich, wenn Sie Ihre Wahl einem Arzt, einem Richter oder einem skeptischen Patienten erklären müssen.

Diese Arbeit stellt DT-PBO vor, eine neue Methode zur Lösung dieses Problems. Anstelle eines mysteriösen Zauberers verwendet DT-PBO einen Entscheidungsbbaum.

Die Baum-Analogie: Ein Flussdiagramm der Präferenzen

Stellen Sie sich einen riesigen Flussdiagramm (einen Baum) vor, der an einer Wand hängt.

Die Äste sind Fragen: Der Baum beginnt oben mit einer Frage wie „Ist der Kuchen Schokolade?"
Die Blätter sind Antworten: Wenn Sie den Ästen folgen, erreichen Sie schließlich ein „Blatt" (das Ende eines Astes). Dieses Blatt gibt Ihnen den „Nutzen" an (wie sehr der Entscheidungsträger diese Art von Kuchen mag) und liefert ein wenig Unsicherheit (z. B. „Wir sind zu 90 % sicher, dass sie dies mögen").

DT-PBO baut diesen Baum direkt aus den „A oder B?"-Antworten auf. Es rät nicht; es betrachtet die Daten und fragt: „Welche Frage trennt die ‚Gewinner' am besten von den ‚Verlierern'?"

Wie es funktioniert (Der Zaubertrick)

Die Splitting-Heuristik (Der Detektiv): Der Algorithmus betrachtet alle Vergleiche. Wenn die meisten Menschen, die „Schokolade" gegenüber „Karotte" bevorzugen, auch „Schokolade" gegenüber „Vanille" bevorzugen, erstellt der Baum einen Ast für „Schokolade". Er verwendet einen speziellen mathematischen Trick namens „Konsistenz-Score", um die logischsten Fragen zu finden, die als Nächstes gestellt werden sollten.
Die Blätter (Die Kristallkugel): Sobald der Baum aufgebaut ist, sind die Enden der Äste (die Blätter) nicht nur einfache „Ja/Nein"-Antworten. Sie enthalten eine Wahrscheinlichkeitsverteilung. Das bedeutet, der Baum kann sagen: „Basierend auf den Daten ist diese Gruppe von Optionen wahrscheinlich die beste, aber es besteht eine kleine Chance, dass wir uns irren." Dies ermöglicht es dem System, weiter zu lernen und bessere Fragen zu stellen.
Der „Straddler"-Trick: Manchmal fällt ein Paar von Gegenständen (wie ein Schokokuchen und ein Karottenkuchen) genau auf die Linie zwischen zwei Ästen. DT-PBO ignoriert diese „Straddler" beim Aufbau der Baumstruktur clever. Warum? Weil die Hauptscheidung (Schokolade vs. Karotte) bereits den Gewinner bestimmt hat. Das Ignorieren hält den Baum klein, einfach und leicht lesbar, ohne wichtige Informationen zu verlieren.

Warum ist das wichtig?

Die Arbeit behauptet drei Hauptpunkte:

Es ist transparent (die „Glaskiste"): Im Gegensatz zum Zauberer (GP) können Sie den Baum betrachten und genau sehen, warum eine Entscheidung getroffen wurde. Sie können den Pfad nachverfolgen: „Das System hat dies gewählt, weil der Nutzer Meeresfrüchte mag, hohe Öligkeit ablehnt und niedrige Preise bevorzugt." Dies ist in hochriskanten Bereichen wie dem Gesundheitswesen oder der Verteidigung entscheidend, wo man nicht einfach einer Blackbox vertrauen kann.
Es ist schnell und robust: Die Autoren haben DT-PBO an acht verschiedenen „Landschaften" (mathematischen Problemen) getestet.
- Auf glatten, einfachen Landschaften schnitt es ähnlich gut wie der Zauberer ab.
- Auf „rauen" Landschaften (wo die beste Antwort in einem zerklüfteten, welligen Terrain verborgen ist), schaffte DT-PBO es tatsächlich besser als der Zauberer.
- Es war auch viel schneller (10- bis 400-mal schneller), da es für jeden einzelnen Schritt keine schweren, komplexen Mathematikberechnungen durchführen muss.
Beweis aus der realen Welt:
- Sushi: Sie nutzten es, um das Lieblings-Sushi einer Person zu finden. Der Baum enthüllte warum (z. B. „Dieser Nutzer liebt Meeresfrüchte, hasst aber hohe Öligkeit"), was eine Blackbox nicht leisten konnte.
- Patientennachrichten: In einem hochriskanten Test mit Patientennachrichten half der Baum Ärzten, dringende Fälle zu priorisieren. Der Baum zeigte, dass „Brustschmerzen" und „Atemnot" die Schlüsselfaktoren für Dringlichkeit waren. Dies ist von entscheidender Bedeutung, da ein Arzt wissen muss, warum eine Nachricht als Notfall markiert wurde, und nicht nur, dass sie es war.

Die Einschränkungen (Die ehrlichen Vorbehalte der Arbeit)

Die Autoren weisen sorgfältig darauf hin, wo ihr Baum Schwierigkeiten haben könnte:

Hohe Dimensionen: Wenn Sie zu viele Merkmale haben (mehr als 7 oder 8), gerät der Baum etwas in die Irre, insbesondere bei glatten Problemen. Der „Zauberer" (GP) ist immer noch besser darin, sehr glatte, hochdimensionale Kurven zu handhaben.
Gleichgültigkeit: Das Modell geht davon aus, dass Sie immer eine Präferenz haben (A ist besser als B). Es kommt mit „Mir ist es egal" (A ist gleich B) noch nicht sehr gut zurecht.

Zusammenfassung

DT-PBO ist wie der Ersatz eines mysteriösen, High-Tech-Navigationsgeräts, das nur sagt „Links abbiegen", durch eine klare, handgezeichnete Karte, die erklärt: „Biegen Sie links ab, weil eine Straßensperre voraus ist." Es findet die beste Lösung genauso gut (und manchmal besser auf schwierigem Gelände), tut dies aber auf eine Weise, die Menschen tatsächlich verstehen, vertrauen und verifizieren können.

Technische Zusammenfassung: DT-PBO – Ein interpretierbares baum-basiertes Surrogatmodell für die präferenzbasierte Bayes-Optimierung

1. Problemstellung

Die präferenzbasierte Bayes-Optimierung (Preferential Bayesian Optimization, PBO) zielt darauf ab, die am meisten bevorzugte Lösung eines Entscheidungsträgers (Decision-Maker, DM) innerhalb eines Suchraums unter Verwendung der geringstmöglichen Anzahl paarweiser Vergleiche (Pairwise Comparisons, PCs) zu identifizieren. Während bestehende PBO-Methoden überwiegend auf Surrogatmodellen mit Gauß-Prozessen (Gaussian Process, GP) basieren, leiden diese Modelle unter einer kritischen Einschränkung: fehlende Interpretierbarkeit. GPs fungieren als Black-Box-Modelle, was es DMs erschwert zu verstehen, warum bestimmte Lösungen bevorzugt werden. Diese Intransparenz stellt eine erhebliche Hürde in hochriskanten Domänen (z. B. Gesundheitswesen, Verteidigung) dar, in denen regulatorische Rahmenwerke (wie die DSGVO der EU) und ethische Leitlinien (z. B. die Strategie für verantwortungsvolle KI der NATO) Erklärbarkeit vorschreiben. Darüber hinaus sind Post-hoc-Erklärungsmethoden für GPs oft nicht treu zum zugrunde liegenden Modell und können potenziell irreführende Erkenntnisse liefern.

Die Arbeit adressiert die Notwendigkeit eines Surrogatmodells, das inhärent interpretierbar ist und gleichzeitig die Fähigkeit zur Modellierung von Präferenzunsicherheit sowie zur Unterstützung des aktiven Lernens (Stichprobeneffizienz) beibehält.

2. Methodik: DT-PBO

Die Autoren schlagen DT-PBO vor, ein neuartiges, auf Entscheidungsbäumen (Decision Tree, DT) basierendes Surrogatmodell, das speziell für PBO entwickelt wurde. Im Gegensatz zu Standard-Entscheidungsbäumen, die auf Klassifikations- oder Ranking-Daten trainiert werden, lernt DT-PBO direkt aus paarweisen Vergleichsdaten. Die Methode folgt der Standard-PBO-Optimierungsschleife (Abbildung 1), ersetzt jedoch das GP-Surrogat durch eine baum-basierte Struktur.

2.1 Partitionierung des Raums (Splitting-Heuristik)

Die Kerninnovation ist eine Konsistenz-Score-Splitting-Heuristik, die entwickelt wurde, um den Merkmalsraum basierend auf beobachteten Präferenzen statt auf Ranking-Tags zu partitionieren.

Mechanismus: Für einen Knoten $A$ , der eine Menge von Vergleichen $D_A$ enthält, bewertet der Algorithmus Kandidatensplits (Merkmalsindex $k$ und Schwellenwert $t$ ).
Konsistenz-Score ( $S_A$ ): Ein Split wird basierend darauf bewertet, wie gut er „Gewinner" von „Verlierern" trennt. Konkret berechnet er den empirischen Mittelwert einer Variable $Z_i(s)$ , die $+1$ ist, wenn der Gewinner auf der einen Seite des Splits und der Verlierer auf der anderen liegt, $-1$, wenn es umgekehrt ist, und $0$, wenn beide auf derselben Seite liegen. Der Score ist der Absolutwert dieses Mittelwerts.
Ausschluss von „Straddlern": Ein wichtiges strukturelles Merkmal ist der Ausschluss von „Straddlern" (Paare, bei denen ein Element in das linke Kind und das andere in das rechte Kind fällt) aus den Datensätzen, die für nachfolgende Splits verwendet werden. Die Autoren beweisen mathematisch, dass Straddler keine Informationen über die interne Struktur der Kindknoten enthalten, sobald der übergeordnete Split etabliert ist. Dieser Ausschluss steuert das Baumwachstum auf natürliche Weise und begünstigt flache, interpretierbare Bäume, ohne eine aggressive Hyperparameter-Optimierung zu erfordern.

2.2 Schätzung der Blattparameter

Sobald die Baumstruktur bestimmt ist, weist das Modell jeder Blattknoten eine probabilistische Schätzung zu, um das aktive Lernen zu unterstützen.

Probabilistische Blätter: Anstelle eines einzelnen Werts wird jedes Blatt $j$ als Gauß-Verteilung mit dem Mittelwert $f_j$ modelliert.
Laplace-Näherung (LA): Die Autoren verwenden einen Bayesschen Ansatz, bei dem die latenten Nutzenwerte über die Blätter hinweg einer gemeinsamen multivariaten Gauß-Prior-Verteilung folgen. Sie verwenden die Laplace-Näherung, um die Maximum-A-Posteriori (MAP)-Schätzung und die Posterior-Kovarianz zu finden.
Identifizierbarkeit: Um die in paarweisen Likelihoods inhärente Translationsinvarianz zu lösen (bei der das Hinzufügen einer Konstante zu allen Nutzenwerten die Präferenzen nicht verändert), wird eine Summe-auf-Null-Bedingung ( $\sum f_i = 0$ ) angewendet. Dies stellt sicher, dass das Modell identifizierbar ist, und entfernt die nicht reduzierbare Varianz in Richtung der konstanten Verschiebung.
Hyperparameter: Das Modell verlässt sich auf das Verhältnis von Rauschvarianz zu Prior-Varianz ( $\sigma^2_{noise}/\sigma^2_{prior}$ ), das sich als der einzige identifizierbare Parameter herausstellt, der die Optimierung steuert.

2.3 Aktives Lernen

Das Modell verwendet die qEUBO-Erwerbsfunktion (Expected Utility of Best Option), um den nächsten informativsten paarweisen Vergleich auszuwählen.

Zwischen-Blatt vs. Innerhalb-Blatt: Während qEUBO Vergleiche zwischen verschiedenen Blättern effektiv auswählt, kollabiert es innerhalb eines einzelnen Blatts (wo der prädiktive Mittelwert konstant ist). Um dies zu adressieren, wenden die Autoren eine Heuristik für die Priorisierung innerhalb von Blättern in diskreten Settings an, wobei die Exploration auf das Blatt fokussiert wird, von dem derzeit angenommen wird, dass es das Optimum enthält.

3. Hauptbeiträge

Baum-basiertes Präferenzlernen: Die Entwicklung eines Algorithmus, der interpretierbare Entscheidungsbäume direkt aus paarweisen Vergleichsdaten unter Verwendung einer neuartigen, konsistenzbasierten Splitting-Heuristik und probabilistischer Blatt-Schätzung lernt.
Numerische Evaluation: Empirische Verifizierung zeigt, dass DT-PBO eine wettbewerbsfähige Konvergenz zu state-of-the-art GP-basierten Modellen (SkewGP und LA-basiertes GP) erreicht, insbesondere bei Funktionen mit rauen Optimierungslandschaften (z. B. De Jong, Holder, Schwefel). Die Methode zeigt deutlich schnellere Rechenlaufzeiten (10–400-mal schneller als GPs).
Fallstudien aus der Praxis: Demonstration der Interpretierbarkeit und Nützlichkeit des Modells in zwei unterschiedlichen Szenarien:
- Sushi-Präferenzen: Zeigt, dass das Modell Benutzerpräferenzen wiederherstellen und auf nicht gesehene Items verallgemeinern kann.
- Patienten-Nachrichten-Ranking (PMR): Eine hochriskante klinische Triage-Aufgabe, bei der das Modell spezifische Merkmale (z. B. „Red-Flag-Syndrom", „Handlungsrelevanz der Nachricht") identifiziert, die Dringlichkeit antreiben, und Erkenntnisse liefert, die für Black-Box-LLM- oder GP-Ansätze intransparent sind.

4. Ergebnisse

Konvergenz: Über acht Benchmark-Funktionen hinweg schneidet DT-PBO wettbewerbsfähig ab. Es schneidet bei glatten, nicht-rauen Funktionen (z. B. Rosenbrock, Hartmann) leicht schlechter ab, übertrifft oder gleicht jedoch GPs bei rauen Funktionen.
Effizienz: DT-PBO ist rechnerisch überlegen, mit Laufzeiten von ca. 12 Sekunden für 200 Iterationen im Vergleich zu Hunderten oder Tausenden von Sekunden für GP-Varianten. Dies wird der Vermeidung der Hyperparameter-Optimierung für Kernel-Längenskalen und der Reduktion der Größe der Hesse-Matrix von der Anzahl der einzigartigen Items ( $m$ ) auf die Anzahl der Blätter ( $m_l$ ) zugeschrieben.
Robustheit: Das Modell ist robust gegenüber Rauschen in den Präferenzen und unempfindlich gegenüber kleinen Änderungen im Hyperparameter-Verhältnis Rauschen/Prior.
Interpretierbarkeit: In Fallstudien liefern die resultierenden Bäume (Tiefe 4–6) klare, für Menschen lesbare Regeln (z. B. „Wenn Brustschmerzen vorhanden sind, priorisieren"), die mit Domänenwissen übereinstimmen, im Gegensatz zu den Black-Box-Ausgaben von GPs oder Large Language Models (LLMs).

5. Bedeutung und Einschränkungen

Die Arbeit behauptet, dass DT-PBO eine viable, inhärent interpretierbare Alternative zu Black-Box-GP-Surrogaten in PBO bietet. Ihre Bedeutung liegt in der Überbrückung der Lücke zwischen stichprobeneffizienter Optimierung und dem Bedarf an Erklärbarkeit in kritischen Entscheidungsdomänen. Durch die Bereitstellung transparenter Modelle ermöglicht es Entscheidungsträgern, ihre Präferenzen mit größerem Vertrauen und Zuversicht zu verfeinern.

Von den Autoren anerkannte Einschränkungen:

Gleichgültigkeit: Das aktuelle Modell kann Gleichgültigkeitsaussagen ( $A \sim B$ ) nicht explizit modellieren.
Hohe Dimensionen: Die Leistung verschlechtert sich bei nicht-rauen Funktionen, wenn die Dimensionalität zunimmt ( $D > 7$ ), wahrscheinlich aufgrund der naturgemäß achsenparallelen Art von Entscheidungssplits, die bei komplexen, diagonalen Entscheidungsgrenzen, die bei hochdimensionalen glatten Funktionen üblich sind, Schwierigkeiten haben.
Merkmalsextraktion: In der PMR-Fallstudie hängt die Qualität des endgültigen Modells von der Zuverlässigkeit des für die Merkmalsextraktion verwendeten LLM ab.

Die Autoren schließen, dass DT-PBO trotz bestehender Einschränkungen erfolgreich demonstriert, dass interpretierbare Surrogatmodelle in PBO wettbewerbsfähige Leistungen erzielen können, insbesondere in Szenarien, in denen Interpretierbarkeit eine Voraussetzung für den Einsatz ist.