🤖 AI

ExplAIner: A Declarative Query Language for Explaining Classification Models

Dit artikel introduceert ExplAIner, een declaratieve querytaal die diverse verklarende concepten voor Booleaanse classificatiemodellen verenigt en vaststelt dat de evaluatie ervan tractabel is via een vast aantal SAT-solver-aanroepen, terwijl het optimalisatiegeoriënteerde fragment, Opt-FOIL, het berekenen van minimale verklaringen met polynomiale aanroepen mogelijk maakt.

Oorspronkelijke auteurs: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

Gepubliceerd 2026-07-08

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer slimme, maar mysterieuze robot hebt die beslissingen neemt. Misschien beslist hij wie een lening krijgt, of of een medische scan verdacht lijkt. Je vraagt de robot: "Waarom heb je 'ja' gezegd tegen deze specifieke persoon?"

De robot geeft je niet zomaar een simpele reden. Hij heeft een black box van binnen. Om dit te begrijpen, hebben onderzoekers tientallen verschillende manieren uitgevonden om vragen te stellen: "Wat is de kleinste reden?" "Wat als we één ding veranderen?" "Welke kenmerken waren absoluut noodzakelijk?"

Dit artikel betoogt dat het hebben van zoveel verschillende manieren om vragen te stellen rommelig is. Het is alsof je duizend verschillende sleutels hebt voor duizend verschillende sloten, terwijl je eigenlijk gewoon één universele sleutelbos nodig hebt. De auteurs willen een universele taal (een querytaal) creëren waarbij je al deze vragen kunt stellen met dezelfde set regels, en ze willen precies weten hoe moeilijk het voor een computer is om ze te beantwoorden.

Hier is de uiteenzetting van hun reis, gebruikmakend van alledaagse analogieën:

1. Het oude hulpmiddel: FOIL (De "kapotte zaklamp")

De onderzoekers keken eerst naar een bestaand hulpmiddel genaamd FOIL. Zie FOIL als een zaklamp die je gebruikt om in de black box van de robot te kijken.

Het probleem: De zaklamp is te zwak. Hij kan niet schijnen op de "kleinste" of "beste" redenen (zoals het vinden van het minimale aantal kenmerken dat nodig is). Het is alsof je probeert de kleinste kiezelsteen in een hoop zand te vinden met een zaklamp die alleen grote rotsen laat zien.
Het gevaar: Erger nog, de zaklamp is op een slechte manier te krachtig. Het stellen van bepaalde vragen aan deze zaklamp zorgt ervoor dat de hersenen van de computer ontploffen. De wiskunde laat zien dat de computer voor sommige vragen een onmogelijk groot aantal mogelijkheden zou moeten controleren, zelfs voor eenvoudige modellen zoals beslisbomen. Het is alsof je een rekenmachine vraagt om elk korreltje zand op een strand te tellen; het duurt te lang.

2. Het nieuwe hulpmiddel: ExplAIner (De "slimme, gelaagde kaart")

Om dit op te lossen, hebben de auteurs een nieuwe taal gebouwd genaamd ExplAIner. Stel je dit voor als een hoogtechnologische, gelaagde kaart van het besluitvormingsproces van de robot.

Laag 1 (De Atomaire Laag): Dit is de basisgeografie. Het weet hoe het stukjes informatie moet vergelijken (zoals "dit stuk heeft 3 ontbrekende onderdelen, dat andere heeft er 5"). De auteurs hebben bewezen dat deze laag gemakkelijk te lezen is; een computer kan dit direct verwerken.
Laag 2 (De Gekwantificeerde Laag): Deze laag stelt vragen over het gedrag van de robot. "Als ik deze ontbrekende onderdelen invul, zegt de robot dan altijd ja?" of "Zegt hij altijd nee?" Deze laag is iets moeilijker, maar nog steeds beheersbaar (het valt onder de categorie NP, wat betekent dat het moeilijk is maar oplosbaar met een slimme zoektocht).
Laag 3 (De Volledige ExplAIner): Dit is de bovenste laag waar je alles combineert. Je kunt complexe vragen stellen zoals: "Is er een reden die zowel minimaal is als kenmerk X bevat?"
De Magie: De auteurs hebben bewezen dat de computer, zelfs met deze complexe vragen, niet door het lint gaat. De computer kan ze beantwoorden door een "helper" (een SAT-solver, wat een soort super-slimme puzzeloplosser is) een vast aantal keren te vragen. Het is alsof je een bibliothecaris hebt die elk boek in de bibliotheek kan vinden door de hoofdbibliothecaris precies drie vragen te stellen, ongeacht hoe groot de bibliotheek is.

3. Het optimalisatietool: Opt-FOIL (De "efficiënte chef")

Er is een addertje onder het gras. Alleen omdat je de vraag kunt stellen (controleren of een reden bestaat), betekent niet dat je ook gemakkelijk de specifieke reden kunt vinden (de eigenlijke reden). Het is alsoken het weten dat er een perfect recept voor een taart bestaat, maar niet weten hoe je die moet bakken zonder de keuken af te branden.

Om dit op te lossen, hebben ze een speciale deelverzameling van hun taal gemaakt genaamd Opt-FOIL.

Het concept: Dit is als een chef die niet zomaar naar elke taart zoekt, maar speciferlijk naar de kleinste taart die nog steeds lekker is, of de taart met de minste suiker.
Het resultaat: Ze hebben bewezen dat de computer voor deze specifieke "best mogelijke" vragen daadwerkelijk het antwoord efficiënt kan vinden. De computer kan dit doen door de "helper" (de puzzeloplosser) een aantal keren te vragen dat redelijk meegroeit met de grootte van het probleem (polynomiale tijd). Het is alsof de chef een stapsgewijze handleiding heeft die garandeert dat er een perfecte taart komt zonder de keuken af te branden.

4. Waarom dit ertoe doet (De "Universele Sleutelbos")

De belangrijkste conclusie is dat de auteurs een gestandaardiseerd kader hebben gecreëerd voor het uitleggen van AI.

Uniformiteit: In plaats van voor elke soort uitleg (abductief, contrastief, kenmerkgebaseerd) een nieuw computerprogramma te schrijven, schrijf je gewoon een query in deze nieuwe taal.
Veiligheid: Ze hebben wiskundig bewezen dat deze queries de computer niet laten crashen. Ze blijven binnen een "veilige zone" van complexiteit, wat betekent dat ze kunnen worden opgelost met standaard, krachtige tools (SAT-solvers) die al in de industrie worden gebruikt.
Flexibiliteit: Je kunt verschillende soorten verklaringen combineren. Je kunt vragen om de kleinste reden, de grootste reden, of een reden die een specifiek kenmerk (zoals geslacht) negeert, allemaal met dezelfde regels.

Samenvattende analogie

Stel je voor dat het AI-model een afgesloten schatkist is.

FOIL was een sleutel die soms niet paste (kon de kleinste reden niet vinden) en soms het slot zo hard blokkeerde dat de deur brak (te complex om te berekenen).
ExplAIner is een meester-sleutelbos. Het heeft verschillende sleutels voor verschillende sloten (verschillende soorten verklaringen), maar ze passen allemaal in hetzelfde mechanisme. De auteurs hebben bewezen dat het gebruik van deze sleutels het slot niet zal breken.
Opt-FOIL is een gespecialiseerd instrument op die sleutelbos dat niet alleen de kist opent, maar ook automatisch het kleinste sleutelgat of de meest waardevolle edelsteen vindt, en dat efficiënt doet.

Het artikel beweert niet dat dit morgen ziektes zal genezen of de aandelenmarkt zal voorspellen. Het zegt simpelweg: "We hebben een betere, veiligere en meer georganiseerde manier gebouwd om 'Waarom?' te vragen aan AI-modellen, en we hebben wiskundig bewezen dat onze nieuwe methode werkt zonder de computer te laten crashen."

Technische Samenvatting: ExplAIner: Een declaratieve querytaal voor het verklaren van classificatiemodellen

1. Probleemstelling

Het veld van Explainable AI (XAI) heeft geleid tot een proliferatie van uiteenlopende verklarende concepten, scores en queries (bijv. abductief, contrastief, kenmerk-noodzakelijkheid, contrafectuals). Vanuit een data management perspectief ontbreekt een verenigd kader bij deze diversiteit. Huidige benaderingen vereisen vaak het ontwerpen van aparte algoritmen voor elke verklarende taak. Het artikel stelt dat een declaratieve querytaal nodig is om deze concepten uniform te specificeren, te combineren en te analyseren.

Bestaande fundamentele talen kampen echter met twee kritieke beperkingen:

Expressiviteit: Ze slagen er vaak niet in om centrale optimaliteitsgebaseerde verklarende concepten te vatten (bijv. minimale abductieve verklaringen).
Complexiteit: Hun evaluatieproblemen kunnen onhandelbaar zijn en bereiken hoge niveaus van de polynomiale hiërarchie (PH), wat ze onpraktisch maakt voor implementatie met standaard SAT-gebaseerde engines.

De kernuitdaging is het ontwerpen van een logica die een balans vindt tussen voldoende expressiviteit om een brede familie van verklarende queries te vatten en gecontroleerde evaluatiecomplexiteit (specifiek, handelbaarheid via SAT-solvers, wat overeenkomt met de Booleaanse hiërarchie over NP).

2. Methodologie en Framework

De auteurs ontwikkelen een framework voor het verklaren van Booleaanse modellen (functies $M: \{0, 1\}^n \to \{0, 1\}$ ) door modellen te behandelen als structuren waarover queries worden geëvalueerd. De methodologie verloopt in drie stadia:

2.1 Analyse van FOIL

Het artikel herbekijkt eerst FOIL (First-Order Interpretability Logic), een model-agnostische logica die modellen behandelt als black boxes met toegang tot positieve instanties en de inclusierelatie ( $\subseteq$ ) over partiële instanties.

Beperking in expressiviteit: De auteurs bewijzen dat FOIL niet in staat is om de query voor minimale abductieve verklaringen (mAXp) uit te drukken, zelfs niet wanneer dit is beperkt tot beslissingsbomen. Dit wordt aangetoond met behulp van Ehrenfeucht-Fraïssé-spellen om aan te tonen dat FOIL niet het verschil kan zien tussen modellen waar een minimale verklaring bestaat en modellen waar dat niet het geval is, enkel gebaseerd op subsumptie.
Complexiteitbeperking: De evaluatie van FOIL over beslissingsbomen wordt getoond hard te zijn voor elk niveau van de polynomiale hiërarchie ( $\Sigma^P_k$ -hard). Dit impliceert dat FOIL niet geëvalueerd kan worden met een polynomiaal aantal oproepen naar een NP-oracle, wat het ongeschikt maakt voor praktische SAT-gebaseerde evaluatie.

2.2 Introductie van ExplAIner

Om deze beperkingen aan te pakken, introduceren de auteurs ExplAIner, een gelaagde eerste-orde logica met een uitgebreide vocabulaire.

Uitbreiding van de vocabulaire: ExplAIner voegt een binaire relatie $\preceq$ toe die partiële instanties vergelijkt op basis van het aantal gedefinieerde kenmerken (cardinaliteit). De auteurs bewijzen dat $\subseteq$ en $\preceq$ onafhankelijk zijn; de een kan niet gedefinieerd worden in termen van de ander over beslissingsbomen.
Gelaagde structuur:
1. Atomaire laag: Formules over $\{\subseteq, \preceq\}$ . Deze hangen alleen af van de structuur van partiële instanties, niet van het model. Evaluatie vindt plaats in P (polynomiale tijd) en validiteit is beslisbaar via reductie naar Presburger-rekenkunde.
2. Gekwantificeerde laag: Breidt de atomaire laag uit met predicaten AllPos en AllNeg (controleert of alle voltooiingen van een partiële instantie positief of negatief worden geclassificeerd) en guarded quantifiers. Guarded quantifiers beperken de universele kwantificatie tot partiële instanties met exact één gedefinieerd kenmerk. Als AllPos en AllNeg tractabel zijn (in P) voor een modelklasse, is de evaluatie van deze laag in NP.
3. Volledige ExplAIner-laag: Staat Booleaanse combinaties toe van formules uit de gekwantificeerde laag. Deze laag vangt de gehele Booleaanse Hiërarchie (BH) over NP.

2.3 Introductie van Opt-FOIL

In het besef dat evaluatie (controleren of een instantie een verklaring is) verschilt van computatie (het vinden van een verklaring), definiëren de auteurs Opt-FOIL.

Mechanisme: Opt-FOIL is een fragment van ExplAIner dat is uitgebreid met een minimalisatie-operator (min) over definieerbare strikte partiële orden.
Syntaxis: Een formule $\Psi = \min[\varphi, \rho]$ berekent een instantie $x$ die voldoet aan een logische specificatie $\varphi$ die minimaal is met betrekking tot een strikte partiële orde $\rho$ .
Syntactische beslisbaarheid: Het artikel biedt een algoritme (gebaseerd op Presburger-rekenkunde) om te verifiëren of een gegeven atomaire formule een strikte partiële orde definieert, wat garandeert dat Opt-FOIL een beslisbare syntaxis heeft.

3. Belangrijkste Bijdragen en Resultaten

3.1 Beperkingen van FOIL

Stelling 3.1: Geen enkele FOIL-formule kan de minimale abductieve verklaring-query definiëren over beslissingsbomen.
Stelling 3.4: Voor elk niveau $k$ van de polynomiale hiërarchie bestaat er een vaste FOIL-formule waarvan de evaluatie over beslissingsbomen $\Sigma^P_k$ -hard is.

3.2 Expressiviteit en Complexiteit van ExplAIner

Expressiviteit: ExplAIner slaagt erin een breed scala aan verklarende concepten te coderen, waaronder:
- Zwakke/Abductieve/Minimale Abductieve Verklaringen (wAXp, AXp, mAXp).
- Zwakke/Contrastieve/Maximale Contrastieve Verklaringen (wCXp, CXp, mCXp).
- Minimale Verandering Vereist (MCR) en Maximale Verandering Toegestaan (MCA).
- Noodzakelijke en Relevante Kenmerken (NF, RF).
Complexiteitsgrenzen:
- Atomaire laag: Evaluatie is in P.
- Gekwantificeerde laag: Als AllPos en AllNeg in P zitten, is de evaluatie in NP. Er bestaan queries in deze laag die NP-compleet zijn over beslissingsbomen.
- Volledige laag: Als AllPos en AllNeg in P zitten, is de evaluatie in de Booleaanse Hiërarchie (BH). Specifiek, voor elk niveau $BH_k$ is er een ExplAIner-query die $BH_k$ -hard is over beslissingsbomen.
- Toepasbaarheid: Deze grenzen gelden voor beslissingsbomen, deterministische decomposable negation normal form (d-DNNF) circuits, 2CNF en Horn CNF.

3.3 Computationele Garanties van Opt-FOIL

Stelling 5.3: Als AllPos en AllNeg in P zitten, is het computatieprobleem voor elke Opt-FOIL-formule in FPNP (functies die berekenbaar zijn in polynomiale tijd met een polynomiaal aantal oproepen aan een NP-oracle).
Algoritme: De computatie omvat het construeren van een pad in de strikte partiële orde. Omdat de lengte van dergelijke paden polynomiaal begrensd is (Lemma 5.5), eindigt het algoritme met een polynomiaal aantal SAT-solver oproepen.
Strikte Insluiting: Onder de aanname dat de polynomiale hiërarchie niet instort, is Opt-FOIL strikt gevat in ExplAIner, dat strikt gevat is in FOIL (met uitgebreide predicaten). Dit bevestigt dat Opt-FOIL een deel van de expressieve kracht opoffert (bijv. kan het bepaalde niet-optimaliteitsqueries niet uitdrukken die ExplAIner wel kan) om computationele handelbaarheid voor het vinden van antwoorden te verkrijgen.

4. Betekenis en Claims

Het artikel claimt dat ExplAIner en Opt-FOIL een principieel, declaratief fundament bieden voor formele XAI.

Uniformiteit: Ze bieden een enkele taal om diverse verklarende concepten te specificeren, waardoor het mogelijk is om criteria te combineren (bijv. het vinden van een gemeenschappelijke verklaring voor meerdere instanties).
Handelbaarheid: Door de logica te beperken tot lagen waar evaluatie in de Booleaanse hiërarchie valt en computatie in FPNP, sluit het framework aan bij de capaciteiten van moderne SAT-solvers. Dit is cruciaal omdat formele XAI vaak vertrouwt op SAT-encodings voor modellen zoals beslissingsbomen en d-DNNF circuits.
Scheiding van Zorgen: Het framework scheidt de logische specificatie van verklarende queries van de representatie-afhankelijke complexiteit van de evaluatie. Dit maakt het mogelijk om dezelfde querytaal toe te passen op verschillende modelklassen (bomen, circuits), mits deze efficiënte consistentiechecks (AllPos/AllNeg) ondersteunen.

De auteurs concluderen dat hoewel FOIL dient als een fundamenteel theoretisch instrument, het onvoldoende is voor praktische implementatie vanwege de hoge complexiteit en beperkte expressiviteit met betrekking tot optimaliteit. ExplAIner en Opt-FOIL lossen deze problemen op, waardoor de specificatie en efficiënte computatie van verklaringen voor Booleaanse modellen mogelijk worden.