2025-11-15T14:04:11.886865

Probabilistic Explanations for Linear Models

Subercaseaux, Arenas, Meel
Formal XAI is an emerging field that focuses on providing explanations with mathematical guarantees for the decisions made by machine learning models. A significant amount of work in this area is centered on the computation of "sufficient reasons". Given a model $M$ and an input instance $\vec{x}$, a sufficient reason for the decision $M(\vec{x})$ is a subset $S$ of the features of $\vec{x}$ such that for any instance $\vec{z}$ that has the same values as $\vec{x}$ for every feature in $S$, it holds that $M(\vec{x}) = M(\vec{z})$. Intuitively, this means that the features in $S$ are sufficient to fully justify the classification of $\vec{x}$ by $M$. For sufficient reasons to be useful in practice, they should be as small as possible, and a natural way to reduce the size of sufficient reasons is to consider a probabilistic relaxation; the probability of $M(\vec{x}) = M(\vec{z})$ must be at least some value $δ\in (0,1]$, for a random instance $\vec{z}$ that coincides with $\vec{x}$ on the features in $S$. Computing small $δ$-sufficient reasons ($δ$-SRs) is known to be a theoretically hard problem; even over decision trees--traditionally deemed simple and interpretable models--strong inapproximability results make the efficient computation of small $δ$-SRs unlikely. We propose the notion of $(δ, ε)$-SR, a simple relaxation of $δ$-SRs, and show that this kind of explanation can be computed efficiently over linear models.
academic

Probabilistische Erklärungen für lineare Modelle

Grundinformationen

  • Paper-ID: 2501.00154
  • Titel: Probabilistic Explanations for Linear Models
  • Autoren: Bernardo Subercaseaux (Carnegie Mellon University), Marcelo Arenas (PUC Chile, IMFD Chile, RelationalAI), Kuldeep S. Meel (Georgia Institute of Technology, University of Toronto)
  • Klassifizierung: cs.AI (Künstliche Intelligenz), cs.CC (Rechenkomplexität)
  • Veröffentlichungsdatum: 3. Januar 2025
  • Paper-Link: https://arxiv.org/abs/2501.00154

Zusammenfassung

Diese Arbeit untersucht das Berechnungsproblem der „hinreichenden Gründe" in der formalen erklärbaren KI (Formal XAI). Gegeben ein Modell M und eine Eingabeinstanz x ist ein hinreichender Grund eine Merkmalsteilmenge S von x, sodass jede Instanz z, die mit x auf S übereinstimmt, M(x)=M(z) erfüllt. Um die Größe der hinreichenden Gründe zu reduzieren, betrachten die Autoren eine probabilistische Relaxation: Es wird gefordert, dass die Wahrscheinlichkeit, dass eine zufällige Instanz z mit x auf der Merkmalsmenge übereinstimmt und M(x)=M(z) erfüllt, mindestens δ∈(0,1] beträgt. Die Berechnung kleiner δ-hinreichender Gründe (δ-SRs) ist theoretisch schwierig, mit starken Nicht-Approximierungsergebnissen selbst für „interpretierbare" Modelle wie Entscheidungsbäume. Die Arbeit führt das Konzept (δ,ε)-SR ein, eine einfache Relaxation von δ-SRs, und beweist, dass solche Erklärungen auf linearen Modellen effizient berechnet werden können.

Forschungshintergrund und Motivation

  1. Kernproblem: Wie können Entscheidungen von Maschinenlernmodellen mit mathematischen Garantien durch kleine Erklärungen begründet werden. Traditionelle hinreichende Gründe erfordern 100% Sicherheit, führen aber oft zu übermäßig großen Erklärungen, die für menschliches Verständnis ungeeignet sind.
  2. Problemrelevanz:
    • Miller (1956) zeigte, dass Erklärungen mit mehr als 9 Merkmalen für Menschen möglicherweise zu groß sind
    • Empirische Studien deuten darauf hin, dass Erklärungen prägnant sein sollten (Narayanan et al., 2018; Lage et al., 2019)
    • In praktischen Anwendungen interessieren sich Benutzer mehr für die Größe der Erklärung als für kleine Unterschiede in probabilistischen Garantien
  3. Einschränkungen bestehender Methoden:
    • Die Berechnung minimaler δ-SRs ist selbst für Entscheidungsbäume NP-schwer
    • Für lineare Modelle ist die exakte Wahrscheinlichkeitsberechnung #P-schwer
    • Es existieren starke Nicht-Approximierungsergebnisse: Keine guten Approximationsverhältnisse in Polynomialzeit möglich
  4. Forschungsmotivation:
    • Benutzer sind empfindlicher gegenüber der Größe von Erklärungen als gegenüber kleinen Änderungen in probabilistischen Garantien
    • Es ist notwendig, ein Gleichgewicht zwischen theoretischer Handhabbarkeit und praktischer Anwendbarkeit zu finden
    • Die spezielle Struktur linearer Modelle könnte effiziente Algorithmen ermöglichen

Kernbeiträge

  1. Einführung des Konzepts (δ,ε)-minimale hinreichende Gründe: Eine Relaxation, die zulässt, dass probabilistische Garantien im Bereich δ-ε, δ+ε variieren
  2. Beweis der Handhabbarkeit auf linearen Modellen: Bereitstellung eines Polynomialzeit-Algorithmus zur Berechnung von (δ,ε)-min-SR mit Laufzeit Õ(n/ε²δ²)
  3. Etablierung von Trennungsergebnissen: Beweis, dass das Problem auf Entscheidungsbäumen weiterhin schwierig ist, was die Besonderheit linearer Modelle unterstreicht
  4. Beweis der lokalen Minimalitätsäquivalenz: Für lineare Modelle ist jeder lokal minimale δ-SR ein teilmengeminimaler δ-SR
  5. Analyse des Approximationsgaps: Beweis, dass kleine Änderungen des probabilistischen Parameters zu exponentiellen Unterschieden in der Erklärungsgröße führen können

Methodische Details

Aufgabendefinition

Eingabe:

  • Lineares Modell L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta), wobei w∈Qn\mathbf{w} \in \mathbb{Q}^n, θ∈Q\theta \in \mathbb{Q}
  • Instanz x∈{0,1}n\mathbf{x} \in \{0,1\}^n
  • Wahrscheinlichkeitsschwelle δ∈(0,1)\delta \in (0,1) und Fehlertoleranz ε∈(0,1)\varepsilon \in (0,1)

Ausgabe:

  • Wert δ∗∈[δ−ε,δ+ε]\delta^* \in [\delta-\varepsilon, \delta+\varepsilon]
  • Minimaler δ∗\delta^*-hinreichender Grund y\mathbf{y}

Nebenbedingungen:

  • L(x)=1\mathcal{L}(\mathbf{x}) = 1 genau dann, wenn x⋅w≥θ\mathbf{x} \cdot \mathbf{w} \geq \theta
  • Teilinstanz y⊑x\mathbf{y} \sqsubseteq \mathbf{x} mit ⋆\star für unbekannte Werte

Modellarchitektur

1. Merkmalsbewertungsmechanismus

Für ein lineares Modell L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta) und eine Instanz x\mathbf{x} wird die Bewertung des Merkmals ii definiert als:

si=wi⋅(2xi−1)⋅(2L(x)−1)s_i = w_i \cdot (2x_i - 1) \cdot (2\mathcal{L}(\mathbf{x}) - 1)

Das Vorzeichen der Bewertung zeigt an, ob das Merkmal die Klassifizierung „hilft" (+1) oder „schadet" (-1), die Größe ist proportional zum Merkmalsgewicht.

2. Gierige Merkmalsauswahl

Schlüssellemma: Für lineare Modelle ist die Auswahl von Merkmalen in absteigender Reihenfolge ihrer Bewertungen unter gleichmäßiger Verteilung optimal.

Konkret, wenn y(0),…,y(n)\mathbf{y}^{(0)}, \ldots, \mathbf{y}^{(n)} Teilinstanzen sind, die durch die Top-k-Merkmale mit höchster Bewertung definiert sind, dann:

Pr⁡z∼U(y(k+1))[L(z)=L(x)]≥Pr⁡z∼U(y(k))[L(z)=L(x)]\Pr_{z \sim U(\mathbf{y}^{(k+1)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})] \geq \Pr_{z \sim U(\mathbf{y}^{(k)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})]

3. Monte-Carlo-Schätzung

Verwendung der Hoeffding-Ungleichung für Wahrscheinlichkeitsschätzung:

Für m=log⁡2n2ε2δ2log⁡2log⁡nβm = \frac{\log 2n}{2\varepsilon^2\delta^2} \log\frac{2\log n}{\beta} Stichproben gilt:

Pr⁡[∣p^(m)−p∣≤εδ/log⁡n]≥1−β/log⁡n\Pr[|\hat{p}(m) - p| \leq \varepsilon\delta/\log n] \geq 1 - \beta/\log n

Technische Innovationen

  1. Randomisierte Wahrscheinlichkeitsschwelle: Der Algorithmus wählt zufällig δ∗∼U([δ−ε,δ+ε])\delta^* \sim U([\delta-\varepsilon, \delta+\varepsilon]), um schwierige Instanzen zu vermeiden
  2. Binäre Suchstrategie: Nutzung der Wahrscheinlichkeitsmonotonie für effiziente Suche
  3. Relaxation mit theoretischen Garantien: Erhaltung der Praktikabilität bei polynomialer Zeitkomplexität

Experimentelle Einrichtung

Algorithmusbeschreibung

Algorithmus 1: LinearMonteCarloExplainer

Eingabe: Lineares Modell L, Instanz x, Parameter δ, ε, β
1. δ* ← Gleichmäßige Stichprobe aus [δ-ε, δ+ε]
2. Berechne alle Merkmalsbewertungen s_i
3. Konstruiere Teilinstanzsequenz y^(0), ..., y^(n)
4. Setze Stichprobengröße m = (log 2n)/(2ε²δ²) log(2log n/β)
5. Verwende binäre Suche, um minimales k zu finden, sodass geschätzte Wahrscheinlichkeit ≥ δ*
6. Gebe (δ*, y^(k*)) zurück

Theoretische Analyse

Hauptsatz: Gegeben ein lineares Modell L\mathcal{L} und Eingabe x\mathbf{x} kann ein (δ,ε)(δ,\varepsilon)-min-SR in Zeit O~(nε2δ2)\tilde{O}(\frac{n}{\varepsilon^2\delta^2}) mit Wahrscheinlichkeit 1−β1-\beta erfolgreich berechnet werden.

Komplexitätsanalyse

  • Zeitkomplexität: O(log⁡n⋅m⋅n)=O~(nε2δ2)O(\log n \cdot m \cdot n) = \tilde{O}(\frac{n}{\varepsilon^2\delta^2})
  • Raumkomplexität: O(n)O(n)
  • Erfolgswahrscheinlichkeit: 1−β1-\beta

Experimentelle Ergebnisse

Hauptergebnisse

  1. Handlungsbarkeitsvergleich:
    • Lineare Modelle: Polynomialzeit lösbar
    • Entscheidungsbäume: Starke Nicht-Approximierbarkeit (es sei denn, SAT ist in quasi-polynomialer Zeit lösbar)
    • Neuronale Netze: NPPP-schwer
  2. Konkrete Beispielverifikation:
    • Beispiel 2 zeigt, dass 0,999999-SR 251-mal kleiner sein kann als minimales 1-SR
    • Beispiel 3 verifiziert die Korrektheit der gierigen Auswahlstrategie

Theoretische Erkenntnisse

  1. Trennungsergebnisse: Beweis des fundamentalen Vorteils linearer Modelle gegenüber Entscheidungsbäumen
  2. Lokal vs. Global Optimal: Für lineare Modelle ist jeder lokal minimale δ-SR ein teilmengeminimaler δ-SR
  3. Approximationsgap: Kleine Änderungen des probabilistischen Parameters können zu Ω(n1/2−ϵ)\Omega(n^{1/2-\epsilon})-fachen Unterschieden in der Erklärungsgröße führen

Fallstudie

Beispiel 3 Detaillierte Analyse:

  • Instanz: x=(1,0,0,1,1)\mathbf{x} = (1,0,0,1,1)
  • Gewichte: w=(5,1,−3,2,−1)\mathbf{w} = (5,1,-3,2,-1), Schwelle: θ=5\theta = 5
  • Merkmalsbewertungen: (5,−1,3,2,−1)(5,-1,3,2,-1)
  • Optimale 2-Merkmals-Erklärung: {1,3}\{1,3\}, Wahrscheinlichkeit 7/8

Verwandte Arbeiten

Berechnung hinreichender Gründe

  1. Darwiche and Hirth (2020): Erste Formalisierung des Konzepts hinreichender Gründe
  2. Barceló et al. (2020): Etablierung einer Komplexitätshierarchie für verschiedene Modellklassen
  3. Arenas et al. (2022): Beweis der Schwierigkeit von δ-SRs auf Entscheidungsbäumen

Probabilistische Erklärungen

  1. Wäldchen et al. (2021): Einführung des δ-hinreichenden-Gründe-Konzepts
  2. Izza et al. (2023): Untersuchung der Berechnung probabilistischer Bauch-Erklärungen
  3. Kozachinskiy (2023): Etablierung von Nicht-Approximierungsergebnissen für Entscheidungsbäume

Erklärung linearer Modelle

  1. Marques-Silva et al. (2020): Untersuchung linearer Klassifizierer wie Naive Bayes
  2. Blanc et al. (2021): Kleine Erklärungen relativ zur Zertifikatskomplexität

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Theoretischer Durchbruch: Erstmaliger Beweis der Polynomialzeit-Berechenbarkeit probabilistischer Erklärungen auf linearen Modellen
  2. Praktischer Wert: Das Konzept (δ,ε)(δ,\varepsilon)-SR verbessert die Praktikabilität bei Beibehaltung theoretischer Garantien
  3. Modellseparation: Etablierung eines fundamentalen Unterschieds zwischen linearen Modellen und Entscheidungsbäumen in der Komplexität der Erklärungsberechnung

Einschränkungen

  1. Praktische Effizienz: Für hochdimensionale Daten (wie n=500) ist die Berechnung bei ε=0,1, δ=0,01 immer noch teuer
  2. Verteilungsannahmen: Der Algorithmus setzt gleichmäßige Verteilung voraus; die Erweiterung auf Produktverteilungen erfordert neue Techniken
  3. Merkmalstypen: Berücksichtigung nur binärer Merkmale; praktische Anwendungen erfordern Behandlung kontinuierlicher und kategorialer Merkmale

Zukünftige Richtungen

  1. Algorithmusoptimierung: Reduzierung der Abhängigkeit von 1/ε und 1/δ
  2. Verteilungserweiterung: Behandlung von Produktverteilungen und allgemeineren Merkmalsverteilungen
  3. Merkmalstypen: Erweiterung auf gemischte Merkmalstypen in „erweiterten linearen Klassifizierern"
  4. Abfragesprache: Entwurf deklarativer Abfragesprachen für probabilistische Erklärungen

Tiefgreifende Bewertung

Stärken

  1. Bedeutende theoretische Beiträge:
    • Erstmaliger Beweis der Handhabbarkeit probabilistischer Erklärungen auf linearen Modellen
    • Vollständige Komplexitätsanalyse und Algorithmusdesign
    • Beweis wichtiger Trennungsergebnisse
  2. Methodische Innovation:
    • Das Konzept (δ,ε)(δ,\varepsilon)-SR balanciert geschickt Theorie und Praktikabilität
    • Randomisierungstechniken vermeiden effektiv schwierige Instanzen
    • Der Beweis der Optimalität der gierigen Strategie ist elegant und tiefgreifend
  3. Tiefgreifende Analyse:
    • Detaillierte mathematische Beweise
    • Berücksichtigung mehrerer Komplexitätsmaße
    • Klare Verbindungen zu verwandten Arbeiten

Schwächen

  1. Praktische Einschränkungen:
    • Algorithmus ist parameterempfindlich, Effizienz bei hohen Dimensionen schlecht
    • Anwendbar nur auf lineare Modelle mit binären Merkmalen
    • Die Annahme gleichmäßiger Verteilung ist in der Praxis stark
  2. Unzureichende experimentelle Validierung:
    • Fehlende experimentelle Validierung auf großen Datensätzen
    • Keine Vergleiche mit bestehenden heuristischen Methoden
    • Theoretische Ergebnisse benötigen mehr empirische Unterstützung
  3. Skalierungsprobleme:
    • Technische Herausforderungen bei der Erweiterung auf allgemeinere Einstellungen
    • Unklar, wie anwendbar auf praktische ML-Pipelines

Auswirkungen

  1. Theoretische Auswirkungen: Bietet wichtige positive Ergebnisse für das Feld der formalen erklärbaren KI und durchbricht den Fokus des Feldes auf Schwierigkeitsergebnisse
  2. Methodische Inspiration: Randomisierungs- und Relaxationstechniken könnten andere schwierige Probleme inspirieren
  3. Praktischer Wert: Bietet theoretische Grundlagen für die Erklärbarkeit linearer Modelle

Anwendungsszenarien

  1. Finanzielle Risikokontrolle: Erklärung von Kreditentscheidungen mit linearen Bewertungsmodellen
  2. Medizinische Diagnose: Erklärung von Risikobewertungen basierend auf linearer Regression
  3. Empfehlungssysteme: Analyse der Merkmalswichtigkeit in linearen Empfehlungsmodellen
  4. Rechtliche Compliance: Mathematisch garantierte Erklärungen für automatisierte Entscheidungen

Literaturverzeichnis

  1. Darwiche, A. and Hirth, A. (2020). On the Reasons Behind Decisions. ECAI 2020.
  2. Barceló, P., Monet, M., Pérez, J., and Subercaseaux, B. (2020). Model interpretability through the lens of computational complexity. NeurIPS 2020.
  3. Wäldchen, S., MacDonald, J., Hauch, S., and Kutyniok, G. (2021). The computational complexity of understanding binary classifier decisions. JAIR.
  4. Arenas, M., Barceló, P., Romero Orth, M., and Subercaseaux, B. (2022). On computing probabilistic explanations for decision trees. NeurIPS 2022.
  5. Kozachinskiy, A. (2023). Inapproximability of sufficient reasons for decision trees. arXiv:2304.02781.

Diese Arbeit leistet bedeutende theoretische Beiträge im Bereich der formalen erklärbaren KI und beweist erstmals die Handhabbarkeit probabilistischer Erklärungen auf linearen Modellen, was dem Feld seltene positive Ergebnisse bietet. Obwohl es Raum für Verbesserungen in der praktischen Anwendbarkeit gibt, machen ihr theoretischer Wert und ihre methodische Innovation sie zu einer wichtigen Arbeit in diesem Bereich.