2025-11-12T13:34:14.831387

Efficient & Correct Predictive Equivalence for Decision Trees

Marques-Silva, Ignatiev
The Rashomon set of decision trees (DTs) finds importance uses. Recent work showed that DTs computing the same classification function, i.e. predictive equivalent DTs, can represent a significant fraction of the Rashomon set. Such redundancy is undesirable. For example, feature importance based on the Rashomon set becomes inaccurate due the existence of predictive equivalent DTs, i.e. DTs with the same prediction for every possible input. In recent work, McTavish et al. proposed solutions for several computational problems related with DTs, including that of deciding predictive equivalent DTs. The approach of McTavish et al. consists of applying the well-known method of Quine-McCluskey (QM) for obtaining minimum-size DNF (disjunctive normal form) representations of DTs, which are then used for comparing DTs for predictive equivalence. Furthermore, the minimum-size DNF representation was also applied to computing explanations for the predictions made by DTs, and to finding predictions in the presence of missing data. However, the problem of formula minimization is hard for the second level of the polynomial hierarchy, and the QM method may exhibit worst-case exponential running time and space. This paper first demonstrates that there exist decision trees that trigger the worst-case exponential running time and space of the QM method. Second, the paper shows that the QM method may incorrectly decide predictive equivalence, if two key constraints are not respected, and one may be difficult to formally guarantee. Third, the paper shows that any of the problems to which the smallest DNF representation has been applied to can be solved in polynomial time, in the size of the DT. The experiments confirm that, for DTs for which the worst-case of the QM method is triggered, the algorithms proposed in this paper are orders of magnitude faster than the ones proposed by McTavish et al.
academic

Effiziente und korrekte prädiktive Äquivalenz für Entscheidungsbäume

Grundinformationen

  • Paper-ID: 2509.17774
  • Titel: Efficient & Correct Predictive Equivalence for Decision Trees
  • Autoren: João Marques-Silva (ICREA & University of Lleida), Alexey Ignatiev (Monash University)
  • Klassifizierung: cs.AI cs.LG cs.LO
  • Veröffentlichungszeit/Konferenz: Journal of Machine Learning Research 23 (2025) 1-35
  • Paper-Link: https://arxiv.org/abs/2509.17774

Zusammenfassung

Rashomon-Mengen von Entscheidungsbäumen haben wichtige Anwendungswerte. Neuere Forschungen zeigen, dass Entscheidungsbäume, die die gleiche Klassifizierungsfunktion berechnen (d.h. prädiktiv äquivalente Entscheidungsbäume), einen großen Teil der Rashomon-Menge ausmachen können. Diese Redundanz ist unerwünscht, beispielsweise wird die auf Rashomon-Mengen basierende Merkmalswichtigkeit durch das Vorhandensein prädiktiv äquivalenter Entscheidungsbäume ungenau. McTavish et al. schlugen kürzlich eine Lösung für entscheidungsbaumrelevante Rechenproblem vor, einschließlich der Bestimmung prädiktiv äquivalenter Entscheidungsbäume. Ihre Methode nutzt die bekannte Quine-McCluskey (QM)-Methode, um eine minimale DNF-Darstellung des Entscheidungsbaums zu erhalten, die dann zum Vergleich der prädiktiven Äquivalenz von Entscheidungsbäumen verwendet wird. Das Formelminimierungsproblem ist jedoch für die zweite Ebene der Polynomhierarchie schwierig, und die QM-Methode kann exponentielle Laufzeit- und Speicherkomplexität im schlimmsten Fall aufweisen. Dieses Papier zeigt zunächst, dass es Entscheidungsbäume gibt, die die schlimmste exponentielle Komplexität der QM-Methode auslösen, zweitens, dass die QM-Methode die prädiktive Äquivalenz möglicherweise falsch beurteilt, wenn zwei kritische Einschränkungen nicht erfüllt sind, und drittens, dass alle Probleme, die minimale DNF-Darstellungen anwenden, in polynomialer Zeit bezüglich der Größe des Entscheidungsbaums gelöst werden können.

Forschungshintergrund und Motivation

Problemdefinition

Das Kernproblem, das in diesem Papier gelöst werden soll, ist die Effizienz und Korrektheit der Bestimmung prädiktiver Äquivalenz von Entscheidungsbäumen. Prädiktiv äquivalente Entscheidungsbäume sind unterschiedliche Entscheidungsbäume, die für jede Eingabe das gleiche Vorhersageergebnis liefern.

Bedeutung des Problems

  1. Rashomon-Mengen-Optimierung: In maschinellem Lernen enthalten Rashomon-Mengen mehrere Modelle mit ähnlicher Leistung. Prädiktiv äquivalente Entscheidungsbäume verursachen Redundanz in dieser Menge und beeinflussen die Genauigkeit der Merkmalswichtigkeitsbewertung.
  2. Anforderungen an Interpretierbarkeit: Entscheidungsbäume werden allgemein als interpretierbare Modelle angesehen, aber selbst optimale Entscheidungsbäume erfordern formale Erklärungen, besonders in hochriskanten Anwendungsszenarien.
  3. Recheneffizienz: Bestehende Methoden sehen sich bei der Verarbeitung großer Entscheidungsbäume mit ernsthaften Rechenbottlenecks konfrontiert.

Einschränkungen bestehender Methoden

Die von McTavish et al. vorgeschlagene Methode basiert auf dem Quine-McCluskey (QM)-Algorithmus und hat folgende Probleme:

  1. Rechenkomplexität: Die QM-Methode löst Σₚ²-schwere Probleme und benötigt im schlimmsten Fall exponentielle Zeit und Speicher
  2. Korrektheitsprobleme: Kann bei Nichterfüllung bestimmter Einschränkungen zu fehlerhaften Ergebnissen führen
  3. Praktische Machbarkeit: Die QM-Methode ist bekannt dafür, bei Problemen mit Dutzenden von Variablen schlecht zu skalieren

Kernbeiträge

  1. Theoretische Analyse: Nachweis, dass es Entscheidungsbäume gibt, die die schlimmste exponentielle Komplexität der QM-Methode auslösen können
  2. Korrektheitanalyse: Offenlegung potenzieller Unkorrektheiten der QM-Methode bei der Bestimmung prädiktiver Äquivalenz
  3. Effizienter Algorithmus: Vorschlag eines Polynomzeit-Algorithmus zur Lösung von Vollständigkeits-, Prägnanz- und prädiktiven Äquivalenzbestimmungsproblemen
  4. Experimentelle Validierung: Der neue Algorithmus ist auf Entscheidungsbäumen, die den QM-Worst-Case auslösen, mehrere Größenordnungen schneller als bestehende Methoden
  5. Theoretische Verbindungen: Etablierung theoretischer Verbindungen zwischen prädiktiver Äquivalenz und logischen Erklärungen sowie Wichtigkeitsmaßen

Methodische Details

Aufgabendefinition

Gegeben seien zwei Entscheidungsbäume T₁ und T₂, bestimme, ob sie prädiktiv äquivalent sind, d.h.:

∀(x ∈ F). (κₜ₁(x) = κₜ₂(x))

wobei F der Merkmalsraum ist und κ die Klassifizierungsfunktion ist.

Technisches Kerngerüst

1. Schwache induktive Erklärungsmethode (WAXp)

Das Papier schlägt einen Polynomzeit-Algorithmus basierend auf WAXp vor:

Algorithmus 1: Pfadkonsistenzprüfung

def ConsistentPath(A, P, T):
    # Prüfe Konsistenz der Teilzuweisung A mit Baumpfad P
    for each feature i:
        combine literals from A and P for feature i
        if inconsistent: return False
    return True

Algorithmus 2: WAXp-Bestimmung

def IsWAXp(A, c, T):
    # Bestimme, ob Teilzuweisung A ein WAXp für Klasse c ist
    for each path P in T:
        if Class(P) != c and ConsistentPath(A, P, T):
            return False  # A ist konsistent mit anderem Klassenpfad
    return True

2. Algorithmus zur Bestimmung prädiktiver Äquivalenz

Algorithmus 5: Bestimmung prädiktiver Äquivalenz

def PredictivelyEquivalent(T1, T2):
    for P1 in Paths(T1):
        c1 = Class(P1)
        A1 = Literals(P1)  # Erstelle Teilzuweisung
        for P2 in Paths(T2):
            c2 = Class(P2)
            if c1 != c2 and ConsistentPath(A1, P2, T2):
                return False  # Finde Beweis für Nicht-Äquivalenz
    return True  # Keine Nicht-Äquivalenz nachgewiesen, daher äquivalent

Technische Innovationen

  1. Vermeidung exponentieller Komplexität: Direkte Operationen auf der Entscheidungsbaumstruktur, Vermeidung der Erzeugung möglicherweise exponentiell großer BCF-Darstellungen
  2. Polynomzeit-Garantie: Alle Algorithmen haben Zeitkomplexität, die polynomial in der Größe des Entscheidungsbaums ist
  3. Formale Korrektheit: Strenge mathematische Beweise garantieren die Korrektheit der Algorithmen
  4. Parallelisierbarkeit: Der Algorithmus zur Bestimmung prädiktiver Äquivalenz kann parallelisiert werden, um die Effizienz weiter zu verbessern

Experimentelle Einrichtung

Konstruierte Testfälle

Das Papier verwendet spezielle Entscheidungsbaumkonstruktionen basierend auf Theorem 1:

  • Parameter r: Steuert die Komplexität des Baums
  • Knotenzahl: 6r + 3 Knoten
  • Merkmalszahl: 2r + 1 Merkmale
  • BCF-Größe: Für Klasse 1 untere Schranke von 2^r Primimplikanten

Bewertungsmetriken

  1. Laufzeit: Algorithmus-Ausführungszeit (Sekunden)
  2. BCF-Größe: Anzahl der Primimplikanten in der Blake-Standardform
  3. Skalierbarkeit: Fähigkeit, Entscheidungsbäume verschiedener Größen zu verarbeiten

Vergleichsmethoden

  • SymPy QM-Implementierung: Benchmark-Methode, die von McTavish et al. verwendet wird
  • Unabhängige BCF-Erzeugung: Vom Autor implementierte Standard-QM-Primimplikanten-Generierungsschritte

Implementierungsdetails

  • Plattform: Macbook M3 Pro Prozessor
  • Programmiersprache: Python
  • Timeout-Einstellung: QM-Methode mit 150000 Sekunden Timeout-Limit

Experimentelle Ergebnisse

Hauptergebnisse

Verifikation der exponentiellen Komplexität der QM-Methode

rSymPy-Zeit(s)|BCF₀(T)||BCF₁(T)|BCF-Zeit(s)
30,134220,01
40,575460,07
539,606940,84
62789,45719011,28
7>150000,008382161,25

Skalierungsleistung des neuen Algorithmus

rDT-KnotenzahlMerkmalszahl|BCF₁(T)|ein AXpisWAXp?PE?
20012034012²⁰⁰1,71s0,005s3,7s
500300310012⁵⁰⁰26,98s0,032s57,1s
1000600320012¹⁰⁰⁰224,62s0,126s469,0s

Wichtigste Erkenntnisse

  1. Bestätigung exponentiellen Wachstums: Die Größe von BCF₁(T) wächst exponentiell mit r, was die theoretische Analyse bestätigt
  2. Massive Leistungslücke: Für r=200 benötigt der neue Algorithmus nur wenige Sekunden für die Verarbeitung eines Entscheidungsbaums mit 1203 Knoten, während die QM-Methode bei 57 Knoten bereits überschreitet
  3. Praktische Validierung: Der neue Algorithmus kann großskalige Entscheidungsbäume verarbeiten, die in praktischen Anwendungen auftreten können

Verwandte Arbeiten

Rashomon-Mengen-Forschung

  • Grundkonzept: Breiman (2001) führte das Konzept der Rashomon-Mengen erstmals ein
  • Neuere Entwicklungen: Arbeiten von Fisher et al., Semenova et al. im Bereich Merkmalswichtigkeit
  • Prädiktive Äquivalenz: McTavish et al. untersuchten erstmals systematisch die prädiktive Äquivalenz von Entscheidungsbäumen

Logische Grundlagen der erklärbaren KI

  • Formale Erklärungen: Arbeiten von Marques-Silva et al. zu AXp und CXp
  • Rechenkomplexität: Mehrere Studien belegen die Komplexität der Erklärungsberechnung
  • Interpretierbarkeitsmaße: Anwendung von Shapley-Werten und Banzhaf-Werten im maschinellen Lernen

Boolesche Formelminimierung

  • Klassische Methoden: Historische Entwicklung des Quine-McCluskey-Algorithmus
  • Komplexitätstheorie: Etablierung der Σₚ²-Härte
  • Praktische Einschränkungen: QM-Methode zeigt drastischen Effizienzrückgang bei mehr als 8 Variablen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Theoretischer Beitrag: Nachweis, dass die QM-Methode bei Entscheidungsbäumen tatsächlich auf exponentielle Komplexität trifft
  2. Algorithmischer Beitrag: Bereitstellung eines Polynomzeit-Ersatzalgorithmus
  3. Praktischer Wert: Der neue Algorithmus hat erhebliche Vorteile in praktischen Anwendungen
  4. Theoretische Verbindungen: Etablierung von Verbindungen zwischen prädiktiver Äquivalenz und mehreren XAI-Konzepten

Einschränkungen

  1. Python-Implementierung: Experimente mit Python können die Bewertung absoluter Leistungswerte beeinflussen
  2. Spezielle Konstruktionen: Experimente konzentrieren sich hauptsächlich auf speziell konstruierte Entscheidungsbäume
  3. Parallelisierung: Das Parallelisierungspotenzial des Algorithmus zur Bestimmung prädiktiver Äquivalenz wurde nicht auf großen Clustern validiert
  4. Allgemeinheit: Weitere Validierung auf echten Datensätzen erforderlich

Zukünftige Richtungen

  1. Asymptotisch optimale Algorithmen: Suche nach theoretisch optimalen Algorithmen
  2. Andere Modelltypen: Erweiterung der Methode auf andere interpretierbare Modelle
  3. Praktische Anwendungen: Anwendung in echter Rashomon-Mengen-Optimierung
  4. Parallele Implementierung: Entwicklung großskaliger parallelisierter Implementierungen

Tiefgreifende Bewertung

Stärken

  1. Theoretische Strenge: Vollständige mathematische Beweise und Komplexitätsanalyse
  2. Hoher praktischer Wert: Löst grundlegende Leistungsprobleme bestehender Methoden
  3. Starke Innovation: Erste systematische Analyse von QM-Methodenproblemen bei Entscheidungsbäumen
  4. Umfassende Experimente: Sowohl Validierung theoretischer Konstruktionen als auch Tests in praktischen Größenordnungen
  5. Klare Darstellung: Gute Papierstruktur und klare technische Beschreibungen

Schwächen

  1. Experimenteller Umfang: Validierung hauptsächlich auf konstruierten Testfällen, fehlende Ergebnisse auf echten Datensätzen
  2. Implementierungssprache: Python ist möglicherweise nicht die beste Wahl und beeinflusst die Überzeugungskraft des Leistungsvergleichs
  3. Anwendungsvalidierung: Fehlende Validierung in echten Rashomon-Mengen-Optimierungsaufgaben
  4. QM-Einschränkungsanalyse: Unzureichende Analyse der praktischen Erreichbarkeit von Korrektheitsbeschränkungen der QM-Methode

Auswirkungen

  1. Akademischer Wert: Bietet neue theoretische Werkzeuge für die Entscheidungsbaumforschung
  2. Praktische Bedeutung: Könnte die praktische Methode der Rashomon-Mengen-Analyse verändern
  3. Reproduzierbarkeit: Klare Algorithmusbeschreibung, leicht zu reproduzieren
  4. Erweiterbarkeit: Methode könnte auf andere interpretierbare Modelle anwendbar sein

Anwendungsszenarien

  1. Hochriskante Anwendungen: Medizin-, Finanzbereich und andere Bereiche, die erklärbare KI erfordern
  2. Modellauswahl: Szenarien, in denen aus mehreren äquivalenten Modellen ausgewählt werden muss
  3. Merkmalswichtigkeitsanalyse: Anwendungen, die eine genaue Bewertung der Merkmalswichtigkeit erfordern
  4. Großskalige Entscheidungsbäume: Industrielle Anwendungen zur Verarbeitung komplexer Entscheidungsbäume

Literaturverzeichnis

Das Papier zitiert umfangreiche verwandte Arbeiten, hauptsächlich einschließlich:

  1. Rashomon-Mengen: Breiman (2001), Xin et al. (2022), Fisher et al. (2019)
  2. Logische erklärbare KI: Marques-Silva (2022), Darwiche (2023), Ignatiev et al. (2019)
  3. Boolesche Funktionsminimierung: Quine (1952, 1955), McCluskey (1956), Umans (1998)
  4. Entscheidungsbaumoptimierung: Bertsimas & Dunn (2017), Hu et al. (2019), Demirovic et al. (2022)

Gesamtbewertung: Dies ist ein hochqualitatives Papier, das Theorie und Praxis verbindet. Es offenbart nicht nur grundlegende Mängel bestehender Methoden, sondern bietet auch praktische Lösungen. Die theoretische Analyse ist streng, die experimentelle Validierung umfassend, und das Papier leistet wichtige Beiträge zum Bereich der Entscheidungsbäume und erklärbaren KI.