🤖 machine learning

CQD-SHAP: Explainable Complex Query Answering via Shapley Values

Het artikel stelt CQD-SHAP voor, een nieuw raamwerk dat Shapley-waarden uit de coöperatieve speltheorie benut om verklaarbare beantwoording van complexe queries over incomplete kennisgrafen te bieden door de bijdrage van elk deel van de query aan de rangschikking van antwoorden te kwantificeren, waarmee de interpreteerbaarheidsbeperkingen van bestaande black-box en neurosymbolische modellen worden aangepakt.

Oorspronkelijke auteurs: Parsa Abbasi, Stefan Heindorf

Gepubliceerd 2026-06-23

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Parsa Abbasi, Stefan Heindorf

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

Het Grote Plaatje: De "Black Box" Detective

Stel je voor dat je een enorme, rommelige bibliotheek hebt (een Knowledge Graph) waar boeken met elkaar verbonden zijn door touwtjes. Soms ontbreken er pagina's of zelfs hele boeken in de bibliotheek (het is onvolledig).

Wanneer je een simpele vraag stelt zoals: "Wie heeft Harry Potter geschreven?", kan een computer het antwoord meestal vinden door simpelweg langs de touwtjes te lopen. Maar wat als je een complexe vraag stelt zoals: "Welke medicijnen behandelen diabetes EN veroorzaken niertoxiciteit?"

Om dit te beantwoorden, moet de computer twee dingen doen:

Langs de touwtjes lopen (Symbolische benadering): Zoeken naar medicijnen die definitief diabetes behandelen en definitief niertoxiciteit veroorzaken in de bestaande bibliotheek.
Ontbrekende links raden (Neurale benadering): Omdat de bibliotheek onvolledig is, gebruikt de computer een "slimme gokker" (een neuraal netwerk) om verbindingen af te leiden die er zouden moeten zijn, maar nog niet in de bibliotheek staan genoteerd.

Het probleem? De "slimme gokker" is een black box. Het geeft je een lijst met antwoorden (zoals "Insuline"), maar het vertelt je niet waarom het dat antwoord heeft gekozen. Heeft de computer voor Insuline gekozen omdat de bibliotheek dat expliciet zei? Of heeft de computer het geraden omdat de computer denkt dat Insuline gerelateerd is aan niertoxiciteit, ook al staat dat feit niet in de bibliotheek?

CQD-SHAP is een nieuwe tool die is ontworpen om die black box te openen en precies uit te leggen hoeveel elk deel van de vraag heeft bijgedragen aan het uiteindelijke antwoord.

De Kern van het Idee: De "Teamscore" Analogie

De auteurs gebruiken een concept uit de speltheorie genaamd Shapley-waarden. Denk hierbij aan een groepsproject waarbij een team van studenten (de atomen van de vraag) samenwerkt om een cijfer te halen (de ranking van het antwoord).

In ons voorbeeldvraag ("Medicijnen voor diabetes EN niertoxiciteit") zijn er twee "studenten" (atomen):

Student A: "Medicijnen voor diabetes."
Student B: "Medicijnen voor niertoxiciteit."

Het uiteindelijke cijfer (de ranking van "Insuline") hangt af van hoe goed beide studenten presteren. Maar hoeveel credit verdient Student A versus Student B?

CQD-SHAP werkt als een eerlijke scheidsrechter. Het voert duizenden mini-experimenten uit om de score te bepalen:

Scenario 1: Student A doet het werk via de "Bibliotheekwandeling" (Symbolisch), en Student B gebruikt de "Slimme gokker" (Neuraal).
Scenario 2: Student A gebruikt de "Slimme gokker", en Student B gebruikt de "Bibliotheekwandeling".
Scenario 3: Beiden gebruiken de "Bibliotheekwandeling".
Scenario 4: Beiden gebruiken de "Slimme gokker".

Door deze scenario's te vergelijken, berekent CQD-SHAP exact hoeveel de "Slimme gokker" de uiteindelijke score voor elke student heeft verbeterd.

Het "Aha!" Moment: Waarom dit ertoe doet

Het paper beweert dat deze methode iets verrassends onthult. Soms doet de "Slimme gokker" al het zware werk, en soms werkt het de resultaten zelfs in de weg.

De Analogie van de "Luidruchtige Buurman":
Stel je voor dat je probeert een specifiek huis te vinden (het antwoord).

De Bibliotheekwandeling is als het lezen van het officiële adresboek. Het is accuraat, maar als het adresboek oud is, staat het huis er misschien niet in.
De Slimme gokker is als het vragen aan een buurman die de buurt kent. Die weet misschien dat het huis bestaat, ook al staat het niet in het adresboek.

CQD-SHAP kan je vertellen:

"Voor het antwoord 'Insuline' kreeg het deel van je vraag over 'Niertoxiciteit' een enorme boost (+450 punten) omdat de Slimme gokker de verbinding raadde. Echter, het deel over 'Diabetes' kreeg juist een lichte straf (-10 punten) omdat de Slimme gokker in de war raakte en wat verkeerde buren suggereerde."

Zonder CQD-SHAP zou je alleen "Insuline" bovenaan de lijst zien en aannemen dat de computer er 100% zeker van is. Met CQD-SHAP besef je: "Wacht even, de computer is vooral aan het gokken over het niergedeelte. Ik moet dat feit even dubbelchecken."

Hoe ze het hebben getest (De "Stress Test")

De auteurs hebben dit getest op echte datasets (zoals Freebase en NELL) met diverse soorten complexe vragen (sommigen met "EN"-verbindingen, anderen met "OF"-verbindingen).

Ze vergeleken hun methode met andere manieren om te raden welk deel van de vraag belangrijk was (zoals het eerste deel kiezen, het laatste deel, of het deel met de laagste score).

De Resultaten:

Noodzakelijke Verklaringen: Als je de "Slimme gkoker" verwijdert uit het belangrijkste deel van de vraag, zou de rangorde van het antwoord aanzienlijk moeten dalen. CQD-SHAP was veel beter in het identificeren van deze cruciale delen dan de andere methoden.
Voldoende Verklaringen: Als je alleen de "Slimme gokker" gebruikt op het belangrijkste deel van de vraag, zou de rangorde van het antwoord aanzienlijk moeten stijgen. Opnieuw won CQD-SHAP.

In simpele termen: CQD-SHAP is de enige methode die consistent naar het juiste deel van de vraag wijst om uit te leggen waarom een antwoord hoog of laag in de lijst staat.

Belangrijkste Punten

Het gaat niet alleen om het antwoord, maar om het "Waarom": Het legt uit waarom een complexe query een specifiek resultaat teruggaf door de bijdrage van elke logische stap te ontleden.
Het meet "Gokkracht": Het kwantificeert specifiek hoeveel het vermogen van het neurale netwerk om ontbrekende feiten te "raden" heeft geholpen (of geschaad) in vergelijking met alleen het kijken naar bestaande feiten.
Het is wiskundig eerlijk: Het gebruikt een strikte wiskundige formule (Shapley-waarden) om ervoor te zorgen dat de "credit" eerlijk wordt verdeeld over de onderdelen van de vraag.
Het vangt fouten op: Het kan onthullen wanneer een hooggeplaatste antwoord eigenlijk gebaseerd is op een zwakke of ruisige gok, wat gebruikers helpt om het systeem minder blindelings te vertrouwen.

Wat het NIET is (Gebaseerd strikt op het paper)

Het beweert niet ziekten te genezen of patiënten te diagnosticeren. Het "medicijn" voorbeeld is slechts een metafoor voor hoe het systeem werkt.
Het zegt niet dat dit artsen of advocaten zal vervangen. Het is een tool om te helpen begrijpen hoe een AI-model denkt.
Het claimt niet het "black box" probleem voor alle AI op te lossen, maar alleen voor dit specifieke type complexe vraagbeantwoordsystemen.

Kortom, CQD-SHAP is een transparantietool die fungeert als een "scorekaart" voor AI-detectives, die laat zien welke aanwijzingen (onderdelen van de query) echte feiten waren en welke slimme gokken waren, zodat je weet wie je kunt vertrouwen.

Technische Samenvatting: CQD-SHAP

Probleemstelling

Complex Query Answering (CQA) op Knowledge Graphs (KGs) gaat verder dan eenvoudige linkvoorspelling en moet queries afhandelen die multi-hop redeneren en logische operatoren (conjunctie, disjunctie) vereisen. Hoewel neurosymbolische benaderingen zoals CQD (Complex Query Decomposition) zijn ontstaan om de incompleetheid van real-world KGs aan te pakken door ontbrekende links te infereren, functioneren zij grotendeels als black-box modellen. Bestaande uitlegmethoden voor linkvoorspelling richten zich op het identificeren van belangrijke triples of paden voor single-hop voorspellingen en zijn niet direct toepasbaar op complexe queries. Bovendien ontbreekt het huidige neurosymbolische CQA-methoden aan transparantie met betrekking tot de specifieke bijdrage van verschillende query-componenten (atomen) aan de uiteindelijke rangschikking van een antwoord. Deze ondoorzichtigheid belemmert het vertrouwen van de gebruiker, debugging en het vermogen van domeinexperts om hiaten in de KG te identificeren of queries te verfijnen.

Methodologie: CQD-SHAP

Het artikel stelt CQD-SHAP voor, een framework dat de resultaten van neurosymbolische CQA-modellen (specifiek CQD) verklaart door de bijdrage van elke query-atoom aan de rangschikking van een specifiek entiteitsantwoord te kwantificeren met behulp van Shapley-waarden uit de coöperatieve speltheorie.

Kerndefinities

Spelers: De atomen (constituerende delen) van een complexe query $Q$ worden behandeld als spelers in een coöperatief spel.
Coalities: Een subset van atomen $S$ wordt uitgevoerd met de neurale benadering (het infereren van ontbrekende links via een link predictor), terwijl de resterende atomen worden uitgevoerd met een symbolische benadering (strikt vertrouwend op geobserveerde feiten in de KG).
Waardefunctie: De waarde van een coalitie $S$ $S$ voor een doelentiteit $e_i$ $e_{i}$ wordt gedefinieerd door de $\Delta$ Rank Quantity of Interest (QoI). Dit meet de verbetering in de rangpositie van $e_i$ $e_{i}$ wanneer de atomen in $S$ $S$ neuraal worden uitgevoerd vergeleken met een puur symbolische uitvoering van de gehele query.
- Formeel: $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$ , waarbij $r_i$ de rang van entiteit $e_i$ is in een gefilterde setting.
Berekening van de Shapley-waarde: De bijdrage van een specifiek atoom $a$ wordt berekend als de gemiddelde marginale bijdrage van dat atoom over alle mogelijke coalities van andere atomen. Dit voldoet aan fundamentele Shapley-axioma's, inclusief efficiëntie (de som van alle atoombijdragen is gelijk aan de totale rangverbetering verkregen door volledige neurale uitvoering).

Uitvoeringsdetails

Neurale uitvoering: Gebruikt een link predictor (bijv. uit CQD) om scores aan entiteiten toe te kennen, wat inferentie over incomplete grafen mogelijk maakt.
Symbolische uitvoering: Voert graafdoorloop uit op de geobserveerde (incomplete) KG, waarbij constante scores worden toegewezen aan bestaande feiten en lage scores aan niet-bestaande feiten.
Exacte berekening: Vanwege het kleine aantal atomen in complexe queries (meestal $\le 4$ ), berekent het artikel exacte Shapley-waarden zonder benadering.

Belangrijkste Bijdragen

Eerste Shapley-gebaseerde uitleg voor CQA: Naar weten van de auteurs is dit de eerste benadering die de resultaten van neurale complexe query-beantwoording verklaart met behulp van Shapley-waarden.
Formele definitie van uitleg op atoomniveau: Het artikel definieert een formeel uitlegkader op het niveau van query-atomen, wat onderscheid maakt van triple- of padniveau-uitleg die wordt gebruikt bij linkvoorspelling.
Nieuwe metriek (CQD-SHAP): Introduceert een methode om te kwantificeren hoeveel de neurale uitvoering van een specifiek atoom bijdraagt aan de rangschikking van een doelantwoord vergeleken met symbolische uitvoering.
Herdefinitie van evaluatiecriteria: Breidt de concepten van Noodzakelijke en Voldoende uitleg van linkvoorspelling uit naar het CQA-domein:
- Noodzakelijk: Het vervangen van het belangrijkste atoom door symbolische uitvoering veroorzaakt een significante daling in de rangschikking van het antwoord (gemeten aan de hand van $\Delta$ MRR).
- Voldoende: Het enkel neuraal uitvoeren van het belangrijkste atoom (terwijl anderen symbolisch zijn) verbetert de rangschikking aanzienlijk vergeleken met een volledig symbolische baseline.

Experimentele Resultaten

De auteurs evalueerden CQD-SHAP op FB15k-237, NELL995 en hun moeilijkere varianten (+H) over diverse querytypes (projecties, intersecties, unies).

Prestaties: CQD-SHAP presteerde consistent beter dan alle baselines (First, Last, Random en Score-gebaseerde selectie) in zowel noodzakelijke als voldoende evaluatiescenario's.
- In het Noodzakelijke scenario verminderde CQD-SHAP de Mean Reciprocal Rank (MRR) met tot wel 45,70% (voor 2u queries op NELL995), aanzienlijk meer dan de beste baseline.
- In het Voldoende scenario verhoogde het de MRR met tot wel 58,90% (voor 2u queries op NELL995+H).
Gevoeligheid voor querystructuur: De methode toonde een hogere effectiviteit voor intersectie-queries (bijv. 3i, 4i) vergeleken met projectie-queries. De auteurs schrijven dit toe aan de structurele aard van intersecties (gebruikmakend van t-normen), waarbij een enkele kritieke tak fungeert als een sterke filter, terwijl projectie-queries vaak alternatieve paden hebben.
Efficiëntie: Ondanks het NP-harde karakter van Shapley-waarden, maakte het kleine aantal atomen een exacte berekening mogelijk met een lage latentie (gemiddeld ~30–140 ms per query-antwoord paar, afhankelijk van de dataset).
Inzicht: De analyse onthulde dat het belangrijkste atoom niet altijd een "missing link" is. In sommige gevallen kan een atoom dat overeenkomt met een bestaand feit in de KG de primaire drijfveer van de rangschikking zijn vanwege de nabijheid in embeddings of ruis geïntroduceerd door de neurale uitvoering van andere onderdelen.

Betekenis en Claims

Het artikel beweert dat CQD-SHAP een wiskundig rigoureuze en effectieve manier biedt om de interpretatie van neurosymbolische query-beantwoording te begrijpen. Door aan de Shapley-axioma's te voldoen, garandeert het een eerlijke toeschrijving van krediet aan query-componenten. De auteurs stellen dat deze aanpak:

Helpt domeinexperts bij het identificeren van hiaten in KGs door te onthullen welke query-onderdelen zwaar leunen op geïnfereerde kennis.
Helpt bij het debuggen van queries door te tonen welke atomen de uiteindelijke rangschikking het meest beïnvloeden.
Een transparant beeld geeft van hoe neurale predictors incomplete data gebruiken vergeleken met symbolische retrieval.

De auteurs verklaren expliciet dat dit het eerste werk is dat Shapley-waarden toepast om complexe query-beantwoording te verklaren, waarmee zij voorbijgaan aan de beperkingen van bestaande uitlegmethoden voor linkvoorspelling. Zij merken op dat hoewel het huidige werk zich richt op lokale uitleg (enkele antwoorden), toekomstige richtingen globale uitleg en natuurlijke taalgeneratie omvatten om deze waarden menselijk leesbaar te maken.