🤖 machine learning

CQD-SHAP: Explainable Complex Query Answering via Shapley Values

Il documento propone CQD-SHAP, un nuovo framework che sfrutta i valori di Shapley della teoria dei giochi cooperativi per fornire risposte spiegabili a query complesse su grafi di conoscenza incompleti, quantificando il contributo di ogni parte della query alle classifiche delle risposte, affrontando così i limiti di interpretabilità dei modelli esistenti di tipo black-box e neurosimbolici.

Autori originali: Parsa Abbasi, Stefan Heindorf

Pubblicato 2026-06-23

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Parsa Abbasi, Stefan Heindorf

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il Quadro Generale: Il Detective della "Scatola Nera"

Immaginate di avere una biblioteca gigante e disordinata (un Knowledge Graph) dove i libri sono collegati da dei fili. A volte, alla biblioteca mancano delle pagine o interi libri (è incompleta).

Quando ponete una domanda semplice come: "Chi ha scritto Harry Potter?", un computer di solito riesce a trovare la risposta semplicemente percorrendo i fili. Ma cosa succede se ponete una domanda complessa come: "Quali farmaci trattano il diabete E causano tossicità renale?"

Per rispondere a questo, il computer deve fare due cose:

Percorrere i fili (approccio simbolico): cercare i farmaci che sicuramente trattano il diabete e che sicuramente causano tossicità renale nella biblioteca esistente.
Indovinare i collegamenti mancanti (approccio neurale): poiché la biblioteca è incompleta, il computer usa un "indovino intelligente" (una rete neurale) per inferire connessioni che dovrebbero esserci, ma che non sono ancora scritte.

Il problema? L' "indovino intelligente" è una scatola nera. Ti fornisce un elenco di risposte (come "Insulina"), ma non ti dice perché ha scelto quella risposta. L'ha scelta perché la biblioteca diceva esplicitamente così? O l'ha scelta perché il computer pensa che l'insulina sia correlata alla tossicità renale, anche se questo fatto manca dalla biblioteca?

CQD-SHAP è un nuovo strumento progettato per aprire questa scatola nera ed esplicare esattamente quanto ogni parte della domanda abbia contribuito alla risposta finale.

L'Idea Centrale: L'Analogia del "Punteggio di Squadra"

Gli autori utilizzano un concetto derivato dalla teoria dei giochi chiamato Valori di Shapley. Pensatelo come un progetto di gruppo in cui un team di studenti (gli atomi della domanda) lavora insieme per ottenere un voto (la classifica della risposta).

Nel nostro esempio di domanda ("Farmaci per il diabete E tossicità renale"), ci sono due "studenti" (atomi):

Studente A: "Farmaci per il diabete."
Studente B: "Farmaci per la tossicità renale."

Il voto finale (la classifica dell' "Insulina") dipende da quanto bene lavorano entrambi gli studenti. Ma quanto merito spetta allo Studente A rispetto allo Studente B?

CQD-SHAP agisce come un arbitro imparziale. Esegue migliaia di mini-esperimenti per determinare il punteggio:

Scenario 1: Lo Studente A fa il lavoro usando la "Passeggiata nella Biblioteca" (Simbolico), e lo Studente B usa l' "Indovino Intelligente" (Neurale).
Scenario 2: Lo Studente A usa l' "Indovino Intelligente", e lo Studente B usa la "Passeggiata nella Biblioteca".
Scenario 3: Entrambi usano la "Passeggiata nella Biblioteca".
Scenario 4: Entrambi usano l' "Indovino Intelligente".

Confrontando questi scenari, CQD-SHAP calcola esattamente quanto l' "Indovino Intelligente" ha migliorato il voto finale per ciascuno degli studenti.

Il Momento dell' "Eureka!": Perché Questo è Importante

Il documento sostiene che questo metodo rivela qualcosa di sorprendente. A volte, l' "Indovino Intelligente" sta facendo tutto il lavoro pesante, e altre volte sta effettivamente danneggiando il risultato.

L'analogia del "Vicino Rumoroso":
Immaginate di cercare una casa specifica (la risposta).

La Passeggiata nella Biblioteca è come leggere l'elenco ufficiale degli indirizzi. È accurata, ma potrebbe non elencare la casa se il libro è vecchio.
L'Indovino Intelligente è come chiedere a un vicino che conosce la zona. Potrebbe sapere che la casa esiste anche se non è presente nel libro.

CQD-SHAP potrebbe dirvi:

"Per la risposta 'Insulina', la parte della tua domanda relativa alla 'Tossicità Renale' ha ricevuto un enorme incremento (+450 punti) perché l'Indovino Intelligente ha indovinato la connessione. Tuttavia, la parte sul 'Diabete' ha subito una leggera penalità (-10 punti) perché l'Indovino Intelligente si è confuso e ha suggerito alcuni vicini sbagliati."

Senza CQD-SHAP, vedreste solo "Insulina" in cima alla lista e assumereste che il computer ne sia sicuro al 100%. Con CQD-SHAP, vi rendete conto: "Aspetta, il computer sta principalmente tirando a indovinare sulla parte della tossicità renale. Dovrei ricontrollare questo dato."

Come lo hanno testato (Il "Test di Resistenza")

Gli autori hanno testato il metodo su dataset reali (come Freebase e NELL) utilizzando vari tipi di domande complesse (alcune con "AND", altre con "OR").

Hanno confrontato il loro metodo con altri modi per indovinare quale parte della domanda fosse importante (come scegliere la prima parte, l'ultima parte o la parte con il punteggio più basso).

I Risultati:

Spiegazioni Necessarie: Se rimuovete l' "Indovino Intelligente" dalla parte più importante della domanda, la posizione della risposta nella classifica dovrebbe scendere significativamente. CQD-SHAP è stato molto più bravo a identificare queste parti critiche rispetto agli altri metodi.
Spiegazioni Sufficienti: Se utilizzate l' "Indovino Intelligente" solo sulla parte più importante, la posizione della risposta nella classifica dovrebbe salire significativamente. Anche in questo caso, CQD-SHAP ha vinto.

In parole semplici, CQD-SHAP è l'unico metodo che identifica costantemente la parte corretta della domanda per spiegare perché una risposta è classificata alta o bassa.

Punti Chiave da Ricordare

Non si tratta solo della risposta, ma del "Perché": Spiega perché una query complessa ha restituito un risultato specifico, scomponendo il contributo di ogni passaggio logico.
Misura il "Potere di Indovinare": Quantifica specificamente quanto la capacità della rete neurale di "indovinare" i fatti mancanti abbia aiutato (o danneggiato) la classificazione finale rispetto al semplice consultare i fatti esistenti.
È matematicamente equo: Utilizza una formula matematica rigorosa (i Valori di Shapley) per garantire che il "merito" sia distribuito equamente tra le parti della domanda.
Intercetta gli errori: Può rivelare quando una risposta in cima alla classifica si basa in realtà su un'ipotesi debole o rumorosa, aiutando gli utenti a fidarsi meno ciecamente del sistema.

Cosa NON è (Basandosi strettamente sul documento)

Non afferma di poter curare malattie o diagnosticare pazienti. L'esempio del "farmaco" è solo una metafora di come funziona il sistema.
Non dice che sostituirà medici o avvocati. È uno strumento per aiutare a comprendere come un modello di IA sta ragionando.
Non afferma di risolvere il problema della "scatola nera" per tutta l'IA, ma solo per questo specifico tipo di sistema di risposta a domande complesse.

In sintest, CQD-SHAP è uno strumento di trasparenza che agisce come una "scheda dei punteggi" per i detective dell'IA, mostrando esattamente quali indizi (parti della query) erano fatti reali e quali erano intuizioni intelligenti, in modo da sapere di chi fidarsi.

Riepilogo Tecnico: CQD-SHAP

Definizione del Problema

Il Questioning di Query Complesse (CQA - Complex Query Answering) su Knowledge Graph (KG) va oltre la semplice predizione di link per gestire query che richiedono ragionamento multi-hop e operatori logici (congiunzione, disgiunzione). Sebbene approcci neurosimbolici come CQD (Complex Query Decomposition) siano emersi per affrontare l'incompletezza dei KG reali attraverso l'inferenza di link mancanti, essi funzionano ampiamente come modelli "black-box". I metodi di spiegabilità esistenti per la predizione di link si concentrano sull'identificazione di triple o percorsi importanti per predizioni a singolo hop e non si applicano direttamente alle query complesse. Inoltre, gli attuali metodi CQA neurosimbolici mancano di trasparenza riguardo al contributo specifico di diverse componenti della query (atomi) al ranking di una risposta. Questa opacità ostacola la fiducia dell'utente, il debugging e la capacità degli esperti di dominio di identificare lacune nel KG o di raffinare le query.

Metodologia: CQD-SHAP

Il documento propone CQD-SHAP, un framework che spiega i risultati dei modelli CQA neurosimbolici (specificamente CQD) quantificando il contributo di ogni atomo della query al ranking di una specifica entità risposta utilizzando i valori di Shapley della teoria dei giochi cooperativi.

Definizioni Core

Giocatori: Gli atomi (parti costituenti) di una query complessa $Q$ sono trattati come giocatori in un gioco cooperativo.
Coalizioni: Un sottoinsieme di atomi $S$ viene eseguito utilizzando l'approccio neurale (inferendo i link mancanti tramite un predittore di link), mentre gli atomi rimanenti vengono eseguiti utilizzando un approccio simbolico (affidandosi strettamente ai fatti osservati nel KG).
Funzione di Valore: Il valore di una coalizione $S$ $S$ per un'entità target $e_i$ $e_{i}$ è definito dalla Quantità di Interesse (QoI) $\Delta$ Rank. Questa misura il miglioramento della posizione di ranking di $e_i$ $e_{i}$ quando gli atomi in $S$ $S$ vengono eseguiti neuralmente rispetto a un'esecuzione puramente simbolica dell'intera query.
- Formalmente: $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$ , dove $r_i$ è il rank dell'entità $e_i$ in un contesto filtrato.
Calcolo del Valore di Shapley: Il contributo di un atomo specifico $a$ è calcolato come il contributo marginale medio di quell'atomo attraverso tutte le possibili coalizioni di altri atomi. Questo soddisfa i fondamentali assiomi di Shapley, inclusa l'efficienza (la somma di tutti i contributi degli atomi è uguale al miglioramento totale del rank ottenuto con l'esecuzione neurale completa).

Dettagli di Esecuzione

Esecuzione Neurale: Utilizza un predittore di link (ad esempio, da CQD) per assegnare punteggi alle entità, permettendo l'inferenza su grafi incompleti.
Esecuzione Simbolica: Esegue la traversata del grafo sul KG osservato (incompleto), assegnando punteggi costanti ai fatti esistenti e punteggi bassi a quelli non esistenti.
Computazione Esatta: Grazie al piccolo numero di atomi nelle query complesse (tipicamente $\le 4$ ), il documento calcola i valori di Shapley esatti senza approssimazioni.

Contributi Chiave

Prima Spiegazione basata su Shapley per la CQA: Per quanto ne sappiano gli autori, questo è il primo approccio che spiega i modelli di risposta a query complesse neurali utilizzando i valori di Shapley.
Definizione Formale delle Spiegazioni a Livello di Atomo: Il documento definisce un framework di spiegazione formale a livello di atomi della query, distinguendolo dalle spiegazioni a livello di triple o di percorso utilizzate nella predizione di link.
Nuovo Metrica (CQD-SHAP): Introduce un metodo per quantificare quanto l'esecuzione neurale di un atomo specifico contribuisca al ranking di una risposta target rispetto all'esecuzione simbolica.
Ridefinizione dei Criteri di Valutazione: Estende i concetti di spiegazione Necessaria e Sufficiente dalla predizione di link al dominio CQA:
- Necessaria: Sostituire l'atomo più importante con l'esecuzione simbolica causa un calo significativo del ranking della risposta (misurato tramite $\Delta$ MRR).
- Sufficiente: Eseguire solo l'atomo più importante neuralmente (mentre gli altri sono simbolici) migliora significativamente il ranking rispetto a un baseline puramente simbolico.

Risultati Sperimentali

Gli autori hanno valutato CQD-SHAP su FB15k-237, NELL995 e le loro varianti più difficili (+H) attraverso vari tipi di query (proiezioni, intersezioni, unioni).

Performance: CQD-SHAP ha superato costantemente tutti i baseline (First, Last, Random e selezione basata su punteggio) sia negli scenari di valutazione necessaria che sufficiente.
- Nello scenario Necessario, CQD-SHAP ha ridotto il Mean Reciprocal Rank (MRR) fino al 45,70% (per query 2u su NELL995), significativamente più del miglior baseline.
- Nello scenario Sufficiente, ha aumentato l'MRR fino al 58,90% (per query 2u su NELL995+H).
Sensibilità alla Struttura della Query: Il metodo ha dimostrato una maggiore efficacia per le query di intersezione (es. 3i, 4i) rispetto alle query di proiezione. Gli autori attribuiscono ciò alla natura strutturale delle intersezioni (utilizzando t-norme), dove un singolo ramo critico agisce come un forte filtro, mentre le query di proiezione spesso presentano percorsi alternativi.
Efficienza: Nonostante la natura NP-hard dei valori di Shapley, il piccolo numero di atomi ha permesso la computazione esatta con bassa latenza (media di ~30–140 ms per coppia query-risposta a seconda del dataset).
Insight: L'analisi ha rivelato che l'atomo più importante non è sempre un "link mancante". In alcuni casi, un atomo corrispondente a un fatto esistente nel KG può essere il driver primario del ranking a causa della prossimità degli embedding o del rumore introdotto dall'esecuzione neurale di altre parti.

Significato e Claim

Il documento afferma che CQD-SHAP fornisce un modo matematicamente rigoroso ed efficace per interpretare la risposta a query neurosimboliche. Soddisfacendo gli assiomi di Shapley, assicura un'equa attribuzione del merito alle componenti della query. Gli autori sostengono che questo approccio:

Aiuta gli esperti di dominio a identificare le lacune nei KG rivelando quali parti della query si affidano pesantemente alla conoscenza inferita.
Assiste nel debugging delle query mostrando quali atomi influenzano maggiormente il ranking finale.
Fornisce una visione trasparente di come i predittori neurali sfruttino i dati incompleti rispetto al recupero simbolico.

Gli autori dichiarano esplicitamente che questo è il primo lavoro ad applicare i valori di Shapley per spiegare i risultati di query complesse, andando oltre i limiti dei metodi di spiegazione della predizione di link esistenti. Notano che, mentre il presente lavoro si concentra sulle spiegazioni locali (singola risposta), le direzioni future includono spiegazioni globali e generazione di linguaggio naturale per rendere questi valori leggibili dagli esseri umani.