🤖 AI

ExplAIner: A Declarative Query Language for Explaining Classification Models

Dieses Paper führt ExplAIner ein, eine deklarative Abfragesprache, die verschiedene Erklärungsbegriffe für Boole'sche Klassifikationsmodelle vereinheitlicht und nachweist, dass deren Evaluierung durch eine feste Anzahl von SAT-Solver-Aufrufen handhabbar ist, während das optimierungsorientierte Fragment Opt-FOIL die Berechnung minimaler Erklärungen mit polynomiellen Aufrufen ermöglicht.

Ursprüngliche Autoren: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

Veröffentlicht 2026-07-08

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

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 haben einen sehr intelligenten, aber geheimnisvollen Roboter, der Entscheidungen trifft. Vielleicht entscheidet er darüber, wer einen Kredit bekommt oder ob ein medizinischer Scan verdächtig aussieht. Sie fragen den Roboter: „Warum hast du bei dieser spezifischen Person ‚Ja‘ gesagt?“

Der Roboter gibt Ihnen nicht einfach nur einen einfachen Grund. In seinem Inneren befindet sich eine Black Box. Um diese zu verstehen, haben Forscher dutzende verschiedene Wege erfunden, Fragen zu stellen: „Was ist der kleinste Grund?“ „Was wäre, wenn wir eine Sache ändern würden?“ „Welche Merkmale waren absolut notwendig?“

Dieses Paper argumenttiert, dass es zu chaotisch ist, so viele verschiedene Arten zu haben, Fragen zu stellen: Es ist, als hätte man tausend verschiedene Schlüssel für tausend verschiedene Schlösser, während man eigentlich nur einen universellen Schlüsselbund braucht. Die Autoren wollen eine universelle Sprache (eine Abfragesprache) erschaffen, mit der Sie all diese Fragen unter Verwendung desselben Regelsatzes stellen können, und sie wollen genau wissen, wie schwierig es für einen Computer ist, sie zu beantworten.

Hier ist die Aufschlüsselung ihrer Reise, unter Verwendung einiger Alltagsanalogien:

1. Das alte Werkzeug: FOIL (Die „kaputte Taschenlampe“)

Die Forscher haben sich zuerst ein bestehendes Werkzeug namens FOIL angesehen. Denken Sie an FOIL als eine Taschenlampe, die Sie benutzen, um in die Black Box des Roboters zu leuchten.

Das Problem: Die Taschenlampe ist zu schwach. Sie kann nicht auf die „kleinsten“ oder „besten“ Gründe leuchten (wie das Finden der minimalen Anzahl an Merkmalen). Es ist, als würde man versuchen, mit einer Taschenlampe, die nur große Felsen zeigt, den kleinsten Kieselstein in einem Haufen Sand zu finden.
Die Gefahr: Schlimmer noch, die Taschenlampe ist auf eine schlechte Weise zu mächtig. Bestimmte Fragen an sie zu stellen, lässt das Gehirn des Computers explodieren. Die Mathematik zeigt, dass der Computer für einige Fragen eine unmögliche Anzahl an Möglichkeiten prüfen müsste, selbst bei einfachen Modellen wie Entscheidungsbäumen. Es ist, als würde man einen Taschenrechner bitten, jedes Sandkorn an einem Strand zu zählen; es dauert zu lange.

2. Das neue Werkzeug: ExplAIner (Die „intelligente, geschichtete Karte“)

Um dies zu beheben, haben die Autoren eine neue Sprache namens ExplAIner entwickelt. Stellen Sie sich dies als eine hochtechnologische, geschichtete Karte des Entscheidungsprozesses des Roboters vor.

Ebene 1 (Die atomare Ebene): Dies ist die grundlegende Geografie. Sie weiß, wie man Informationen vergleicht (wie „dieses Teil hat 3 fehlende Teile, jenes hat 5“). Die Autoren haben bewiesen, dass diese Ebene leicht lesbar ist; ein Computer kann sie sofort verarbeiten.
Ebene 2 (Die quantifizierte Ebene):): Diese Ebene stellt Fragen über das Verhalten des Roboters. „Wenn ich diese fehlenden Teile auffülle, sagt der Roboter dann immer Ja?“ oder „Sagt er immer Nein?“ Diese Ebene ist etwas schwieriger, aber immer noch handhabbar (sie fällt in die Kategorie NP, was bedeutet, dass sie schwer, aber lösbar ist, wenn man eine kluge Suche verwendet).
Ebene 3 (Der vollständige ExplAIner): Dies ist die oberste Ebene, in der Sie alles kombinieren. Sie können komplexe Fragen stellen wie: „Gibt es einen Grund, der sowohl minimal ist als auch Merkmal X beinhaltet?“
Die Magie: Die Autoren haben bewiesen, dass der Computer selbst bei diesen komplexen Fragen nicht durchdreht. Er kann sie beantworten, indem er einen „Helfer“ (einen SAT-Solver, also einen superintelligenten Rätsellöser) eine feste Anzahl von Malen fragt. Es ist, als hätte man einen Bibliothekar, der jedes Buch in der Bibliothek finden kann, indem er dem Cheflibrarian genau drei Fragen stellt, egal wie groß die Bibliothek ist.

3. Das Optimierungswerkzeug: Opt-FOIL (Der „effiziente Koch“)

Es gibt einen Haken. Nur weil man die Frage stellen kann (prüfen, ob ein Grund existiert), bedeutet das nicht, dass man die spezifische Antwort (den eigentlichen Grund) auch leicht finden kann. Es ist, als wüsste man, dass ein perfektes Kuchenrezept existiert, aber man wisse nicht, wie man es backt, ohne die Küche niederzubrennen.

Um dies zu lösen, haben sie eine spezielle Teilmenge ihrer Sprache namens Opt-FOIL erstellt.

Das Konzept: Dies ist wie ein Koch, der nicht nur nach irgendeinem Kuchen sucht, sondern gezielt nach dem kleinsten Kuchen, der noch gut schmeckt, oder dem Kuchen mit dem wenigsten Zucker.
Das Ergebnis: Sie haben bewiesen, dass der Computer für diese spezifischen „bestmöglichen“ Fragen tatsächlich die Antwort finden kann. Er kann dies tun, indem er den „Helfer“ (den Rätsellöser) eine Anzahl von Malen fragt, die angemessen mit der Größe des Problems wächst (Polynomzeit). Es ist, als hätte der Koch eine Schritt-für-Schritt-Anleitung, die garantiert einen perfekten Kuchen liefert, ohne die Küche niederzubrennen.

4. Warum das wichtig ist (Der „universelle Schlüsselbund“)

Die Hauptbotschaft ist, dass die Autoren einen standardisierten Rahmen für die Erklärung von KI geschaffen haben.

Einheitlichkeit: Anstatt für jede Art von Erklärung (abduktiv, kontrastiv, merkmalsbasiert) ein neues Computerprogramm zu schreiben, schreibt man einfach eine Abfrage in dieser neuen Sprache.
Sicherheit: Sie haben mathematisch bewiesen, dass diese Abfragen den Computer nicht zum Absturz bringen. Sie bleiben in einer „sicheren Zone“ der Komplexität, was bedeutet, dass sie mit Standardwerkzeugen, die bereits in der Industrie verwendet werden (SAT-Solver), gelöst werden können.
Flexibilität: Sie können verschiedene Arten von Erklärungen mischen und kombinieren. Sie können nach dem kleinsten Grund fragen, nach dem größten Grund oder nach einem Grund, der ein bestimmtes Merkmal (wie das Geschlecht) ignoriert – und das alles unter Verwendung derselben Regeln.

Zusammenfassende Analogie

Stellen Sie sich das KI-Modell als eine verschlossene Schatzkiste vor.

FOIL war ein Schlüssel, der manchmal nicht passte (konnte den kleinsten Grund nicht finden) und manchmal das Schloss so fest klemmte, dass die Tür brach (zu komplex zu berechnen war).
ExplAIner ist ein Master-Schlüsselbund. Er hat verschiedene Schlüssel für verschiedene Schlösser (verschiedene Arten von Erklärungen), aber sie alle passen in denselben Mechanismus. Die Autoren haben bewiesen, dass die Verwendung dieser Schlüssel das Schloss nicht beschädigt.
Opt-FOIL ist ein spezialisiertes Werkzeug an diesem Schlüsselbund, das nicht nur die Truhe öffnet, sondern auch automatisch das kleinste Schlüsselloch oder den wertvollsten Edelstein darin findet, und das effizient und schnell tut.

Das Paper behauptet nicht, dass dies morgen Krankheiten heilen oder den Aktienmarkt vorhersagen wird. Es sagt lediglich: „Wir haben einen besseren, sichereren und besser organisierten Weg gebaut, um KI-Modellen nach dem ‚Warum?‘ zu fragen, und wir haben mathematisch bewacht, dass unser neuer Weg funktioniert, ohne den Computer zu überlasten.“

Technisches Resümee: ExplAIner: Eine deklarative Abfragesprache zur Erklärung von Klassifikationsmodellen

1. Problemstellung

Das Feld der erklärbaren KI (Explainable AI, XAI) hat eine Flut von unterschiedlichen Erklärungsnotionen, Scores und Abfragen hervorgebracht (z. B. abduktiv, kontrastiv, Merkmalsnotwendigkeit, kontrafaktisch). Aus einer Datenmanagement-Perspektive mangelt es dieser Diversität an einem einheitlichen Rahmenwerk. Derzeitige Ansätze erfordern oft das Design separater Algorithmen für jede Erklärungsaufgabe. Das Paper postuliert, dass eine deklarative Abfragesprache benötigt wird, um diese Notionen einheitlich zu spezifizieren, zu kombinieren und zu analysieren.

Bestehende fundamentale Sprachen stehen jedoch vor zwei kritischen Einschränkungen:

Ausdrucksstärke: Sie versäumen es oft, zentrale optimalitätsbasierte Erklärungsnotionen (z. B. minimale abduktive Erklärungen) zu erfassen.
Komplexität: Ihre Evaluierungsprobleme können intransitiv sein und hohe Ebenen der Polynomialen Hierarchie (PH) erreichen, was sie für die Implementierung mittels Standard-SAT-Engines unpraktikabel macht.

Die Kernherausforderung besteht darin, eine Logik zu entwerfen, die ein Gleichgewicht zwischen ausreichender Ausdrucksstärke zur Erfassung einer breiten Familie von Erklärungsabfragen und kontrollierter Evaluierungskomplexität (speziell der Handhabbarkeit via SAT-Solver, was der Booleschen Hierarchie über NP entspricht) hält.

2. Methodik und Rahmenwerk

Die Autoren entwickeln ein Rahmenwerk zur Erklärung von Booleschen Modellen (Funktionen $M: \{0, 1\}^n \to \{0, 1\}$ ), indem sie Modelle als Strukturen behandeln, über denen Abfragen evaluiert werden. Die Methodik verläuft in drei Stufen:

2.1 Analyse von FOIL

Das Paper reanalysiert FOIL (First-Order Interpretability Logic), eine modellagnostische Logik, die Modelle als Black Boxes behandelt, mit Zugriff auf positive Instanzen und der Subsumptionsrelation ( $\subseteq$ ) über partielle Instanzen.

Einschränkung der Ausdrucksstärke: Die Autoren beweisen, dass FOIL nicht in der Lage ist, die Abfrage für minimale abduktive Erklärungen (mAXp) auszudrücken, selbst wenn sie auf Entscheidungsbäume beschränkt ist. Dies wird durch Ehrenfeucht-Fraïssé-Spiele demonstriert, die zeigen, dass FOIL nicht zwischen Modellen unterscheiden kann, in denen eine minimale Erklärung existiert, und solchen, in denen sie nicht existiert, basierend rein auf der Subsumption.
Komplexitätseinschränkung: Das Evaluierungsproblem für FOIL über Entscheidungsbäume erweist sich als hart für jede Ebene der Polynomialen Hierarchie ( $\Sigma^P_k$ -hart). Dies impliziert, dass FOIL nicht mit einer polynomiellen Anzahl von Aufrufen eines NP-Orakels evaluiert werden kann, was es für die praktische Implementierung mittels SAT-basierten Engines ungeeignet macht.

2.2 Einführung von ExplAIner

Um diese Einschränkungen zu adressieren, führen die Autoren ExplAIner ein, eine geschichtete First-Order-Logik mit einem erweiterten Vokabular.

Vokabularerweiterung: ExplAIner fügt eine binäre Relation $\preceq$ hinzu, die partielle Instanzen basierend auf der Anzahl der definierten Merkmale (Kardinalität) vergleicht. Die Autoren beweisen, dass $\subseteq$ und $\preceq$ unabhängig sind; keine von beiden kann über die andere über Entscheidungsbäume definiert werden.
Geschichtete Struktur:
1. Atomare Schicht: Formeln über $\{\subseteq, \preceq\}$ . Diese hängen nur von der Struktur partieller Instanzen ab, nicht vom Modell. Die Evaluierung liegt in P (Polynomialzeit) und die Gültigkeit ist via Reduktion auf die Presburger-Arithmetik entscheidbar.
2. Quantifizierte Schicht: Erweitert die atomare Schicht um die Prädikate AllPos und AllNeg (Prüfung, ob alle Vervollständigungen einer partiellen Instanz positiv bzw. negativ klassifiziert werden) sowie bewachte Quantoren. Bewachte Quantoren beschränken die universelle Quantifizierung auf partielle Instanzen mit genau einem definierten Merkmal. Wenn AllPos und AllNeg (für eine Modellklasse) in P liegen, liegt die Evaluierung dieser Schicht in NP.
3. Volle ExplAIner-Schicht: Erlaubt Boolesche Kombinationen von Formeln aus der quantifizierten Schicht. Diese Schicht erfasst die gesamte Boolesche Hierarchie (BH) über NP.

2.3 Einführung von Opt-FOIL

In Anerkennung dessen, dass die Evaluierung (Prüfung, ob eine Instanz eine Erklärung ist) sich von der Berechnung (Finden einer Erklärung) unterscheidet, definieren die Autoren Opt-FOIL.

Mechanismus: Opt-FOIL ist ein Fragment von ExplAIner, das mit einem Minimierungsoperator (min) über definierbare strikte Teilordnungen erweitert wurde.
Syntax: Eine Formel $\Psi = \min[\varphi, \rho]$ berechnet eine Instanz $x$ , die eine logische Spezifikation $\varphi$ erfüllt und minimal bezüglich einer strikten Teilordnung $\rho$ ist.
Syntax-Entscheidbarkeit: Das Paper liefert einen Algorithmus (basierend auf der Presburger-Arithmetik), um zu verifizieren, ob eine gegebene atomare Formel eine strikte Teilordnung definiert, wodurch sichergestellt wird, dass Opt-FOIL eine entscheidbare Syntax besitzt.

3. Zentrale Beiträge und Ergebnisse

3.1 Limitationen von FOIL

Theorem 3.1: Keine FOIL-Formel kann die Abfrage für die minimale abduktive Erklärung über Entscheidungsbäume definieren.
Theorem 3.4: Für jede Ebene $k$ der Polynomialen Hierarchie existiert eine feste FOIL-Formel, deren Evaluierung über Entscheidungsbäume $\Sigma^P_k$ -hart ist.

3.2 Ausdrucksstärke und Komplexität von ExplAIner

Ausdrucksstärke: ExplAIner kodiert erfolgreich eine breite Palette von Erklärungsnotionen, darunter:
- Schwache/Abduktive/Minimale abduktive Erklärungen (wAXp, AXp, mAXp).
- Schwache/Kontrastive/Maximale kontrastive Erklärungen (wCXp, CXp, mCXp).
- Minimale Änderung erforderlich (MCR) und Maximale Änderung erlaubt (MCA).
- Notwendige und relevante Merkmale (NF, RF).
Komplexitätsgrenzen:
- Atomare Schicht: Evaluierung liegt in P.
- Quantifizierte Schicht: Wenn AllPos und AllNeg in P liegen, liegt die Evaluierung in NP. Es existieren Abfragen in dieser Schicht, die über Entscheidungsbäume NP-vollständig sind.
- Volle Schicht: Wenn AllPos und AllNeg in P liegen, liegt die Evaluierung in der Booleschen Hierarchie (BH). Für jede Ebene $BH_k$ gibt es eine ExplAIner-Abfrage, die über Entscheidungsbäume $BH_k$ -hart ist.
- Anwendbarkeit: Diese Grenzen gelten für Entscheidungsbäume, deterministische dekomponierbare Negationsnormalformen (d-DNNF) Schaltkreise, 2CNF und Horn-CNF.

3.3 Rechengarantien von Opt-FOIL

Theorem 5.3: Wenn AllPos und AllNeg in P liegen, liegt das Berechnungsproblem für jede Opt-FOIL-Formel in FPNP (Funktionen, die in Polynomialzeit mit einer polynomiellen Anzahl von Aufrufen eines NP-Orakels berechenbar sind).
Algorithmus: Die Berechnung beinhaltet das Konstruieren eines Pfades in der strikten Teilordnung. Da die Länge solcher Pfade polynomiell beschränkt ist (Lemma 5.5), terminiert der Algorithmus mit einer polynomiellen Anzahl von SAT-Solver-Aufrufen.
Strikte Einbettung: Unter der Annahme, dass die Polynomiale Hierarchie nicht kollabiert, ist Opt-FOIL strikt enthalten in ExplAIner, welches wiederum strikt in FOIL (mit erweiterten Prädikaten) enthalten ist. Dies bestätigt, dass Opt-FOIL zugunsten der rechnerischen Handhabbarkeit beim Finden von Antworten (Computation) eine geringere Ausdrucksstärke (z. B. die Unfähigkeit, bestimmte Nicht-Optimalitäts-Abfragen auszudrücken) opfert.

4. Bedeutung und Ansprüche

Das Paper behauptet, dass ExplAIner und Opt-FOIL eine fundierte, deklarative Basis für formale XAI bieten.

Uniformität: Sie bieten eine einzige Sprache zur Spezifikation diverser Erklärungsnotionen, was die Kombination von Kriterien ermöglicht (z. B. das Finden einer gemeinsamen Erklärung für mehrere Instanzen).
Handhabbarkeit: Durch die Beschränkung der Logik auf Schichten, in denen die Evaluierung in der Booleschen Hierarchie und die Berechnung in FPNP liegt, richtet sich das Rahmenwerk nach den Fähigkeiten moderner SAT-Solver. Dies ist entscheidend, da formale XAI oft auf SAT-Kodierungen für Modelle wie Entscheidungsbäume und d-DNNF-Schaltkreise angewiesen ist.
Trennung der Belange (Separation of Concerns): Das Rahmenwerk trennt die logische Spezifikation von Erklärungsabfragen von der repräsentationsabhängigen Komplexität der Evaluierung. Dies ermöglicht die Anwendung derselben Abfragesprache auf verschiedene Modellklassen (Bäume, Schaltkreise), sofern diese effiziente Konsistenzprüfungen (AllPos/AllNeg) unterstützen.

Die Autoren kommen zu dem Schluss, dass FOIL zwar als fundiertes theoretisches Werkzeug dient, aufgrund seiner hohen Komplexität und der begrenzten Ausdrucksstärke bezüglich der Optimalität jedoch unzureichend für die praktische Implementierung ist. ExplAIner und Opt-FOIL lösen diese Probleme und ermöglichen die Spezifikation und effiziente Berechnung von Erklärungen für Boolesche Modelle.