Technische Samenvatting: Voorbij Shapley: Efficiënte Berekening van Asymmetrische Shapley-waarden

Probleemstelling

Het artikel behandelt de computationele en interpreteerbaarheidsuitdagingen die gepaard gaan met feature-attributie in Explainable AI (XAI). Hoewel Shapley-waarden (en hun machine learning instantiatie, SHAP) een theoretisch gefundeerde methode bieden voor het verdelen van de voorspelling van een model over de inputfeatures, lijden ze aan twee primaire beperkingen:

1. Computationele Intractabiliteit: Het berekenen van exacte Shapley-waarden is vaak #P-hard, met name voor expressieve modellen (bijv. neurale netwerken) of wanneer de onderliggende datadistributie complex is (bijv. Naive Bayes-distributies).
2. Interpretatiegebreken: Standaard Shapley-waarden behandelen alle features symmetrisch. Dit faalt in het vastleggen van causale relaties, waardoor potentieel een oorzaak en een deterministisch effect een gelijke belangrijkheid krijgen, wat het werkelijke datagenererende proces vertroebelt.

Om het tweede probleem aan te pakken, werden Asymmetrische Shapley-waarden (ASV) voorgesteld, die de berekening beperken tot permutaties van features die een gegeven causaal grafiek (een Directed Acyclic Graph of DAG) respecteren. Echter, de computationele complexiteit van ASV was nog niet grondig onderzocht. Dit artikel onderzoekt of het incorporeren van causale restricties de berekening van attributiewaarden in specifieke contexten daadwerkelijk hanteerbaarder kan maken dan standaard Shapley-waarden.

Methodologie

De auteurs stellen een reeks algoritmen voor om ASV exact en benaderd te berekenen, waarbij gebruik wordt gemaakt van de structuur van de causale grafiek en de onderliggende waarschijnlijkheidsdistributie (gemodelleerd als een Bayesiaans Netwerk).

1. Theoretische Tractabiliteitsanalyse

De auteurs vestigen een theoretisch resultaat met betrekking tot de complexiteit van ASV onder Naive Bayes-distributies. Ze bewijzen dat, terwijl het berekenen van standaard Shapley-waarden intractabel is voor bepaalde modelfamilies onder Naive Bayes-distributies, het berekenen van ASV polynomiaal-tijd hanteerbaar is voor dezelfde families indien de gebruikte causale grafiek voor ASV identiek is aan de Naive Bayes-netwerkstructuur. Dit suggereert dat de causale restricties opgelegd door de distributie symmetrieën kunnen doorbreken die de problemen anders moeilijk zouden maken.

2. Exacte Berekening via Equivalentieklassen

Om de hanteerbaarheid uit te breiden naar algemenere causale structuren, specifiek gewortelde gerichte bomen (rooted directed trees), introduceren de auteurs een methode om de zoekruimte van permutaties te reduceren:

• Equivalentieklassen: Ze definiëren een equivalentierelatie over de verzameling topologische ordeningen van de causale grafiek. Twee ordeningen zijn equivalent met betrekking tot een feature $x$ als de verzameling features die voorafgaan aan $x$ identiek is in beide ordeningen.
• Algoritme: In plaats van alle topologische ordeningen te itereren (wat exponentieel kan zijn), berekent het algoritme de verzameling equivalentieklassen ($\Lambda_x^C$) en de grootte van elke klasse. De ASV wordt vervolgens berekend door de marginale bijdragen te sommeren, gewogen door de grootte van elke equivalentieklasse.
• Complexiteit: Voor gewortelde gerichte bomen wordt het aantal equivalentieklassen begrensd door $h \cdot l + 1$ (waarbij $h$ de diepte is en $l$ het aantal bladeren). De auteurs bieden een polynomiaal-tijd algoritme (in termen van het aantal equivalentieklassen) om deze klassen en hun groottes te berekenen.

3. Benaderde Berekening via Sampling

Voor willekeurige causale DAG's waar exacte berekening mogelijk onhaalbaar is, stellen de auteurs een sampling-gebaseerd benaderingsschema voor.

• Sampling van Topologische Ordeningen: De methode berust op het uniform willekeurig samplen van topologische ordeningen. De auteurs implementeren twee benaderingen:
  1. Een recursief telalgoritme voor polytrees (grafieken met maximaal één pad tussen twee knopen) dat topologische ordeningen telt om bronknopen correct te wegen.
  2. Een op een random walk gebaseerd algoritme (gebaseerd op Bubley & Dyer, 1999) voor algemene DAG's.
• Foutmarges: Ze formaliseren dat als de topologische ordening sampler $\epsilon_{samp}$-dicht bij uniform is en de karakteristieke functie (verwachte modelwaarde) wordt benaderd met een fout $\epsilon_{\nu}$, de resulterende ASV-schatting een additieve fout heeft van $O(\epsilon_{samp} + \epsilon_{\nu})$.

Belangrijkste Resultaten

De auteurs evalueerden hun methoden op real-world Bayesiaanse netwerken (Cancer, Child) en kunstmatige structuren (gebalanceerde bomen, Naive Bayes, meerdere paden).

1. Reductie van de Zoekruimte: De aanpak met equivalentieklassen vermindert de computationele last aanzienlijk vergeleken met het enumereren van alle topologische ordeningen. In het "Child"-netwerk was het aantal topologische ordeningen $\approx 7,41 \times 10^{11}$, terwijl het aantal equivalentieklassen slechts $\approx 2003$ was gemiddeld.
2. Runtime Efficiëntie:
   • Het berekenen van equivalentieklassen voor praktische grafiekgroottes duurde minder dan één seconde.
   • De runtime van het exacte algoritme was sterk gecorreleerd met het aantal equivalentieklassen, waardoor de pre-computatie van klasse-aantallen kon dienen als voorspeller voor de computationele kosten.
   • Het enumereren van alle topologische ordeningen werd onhaalbaar voor grotere grafieken, terwijl de methode met equivalentieklassen hanteerbaar bleef.
3. Sampling Prestaties:
   • Het aangepaste recursieve sampling-algoritme voor polytrees was efficiënt, met een niet-lineaire schaling ten opzichte van het aantal samples door parallelle kandidaatgeneratie.
   • Het gebruik van 1.000 samples leverde een gemiddelde relatieve fout van ongeveer 8% op voor ASV-waarden. De fout was lager voor grotere ASV-waarden en hoger voor zeer kleine ware waarden.

Betekenis en Claims

Het artikel claimt dat ASV een levensvatbaar en potentieel superieur kader is voor verklaarbaarheid wanneer causale structuur relevant is, aangezien het afhankelijkheden vastlegt die standaard SHAP mist. De primaire bijdrage is het aantonen dat causale restricties een intractabel probleem kunnen transformeren in een hanteerbaar probleem voor specifieke model-distributie paren (bijv. beslissingsbomen onder Naive Bayes).

De auteurs benadrukken dat hoewel ASV deze theoretische en praktische voordelen biedt, de schaalbaarheid sterk afhankelijk is van de topologie van de causale grafiek:

• Voor gewortelde gerichte bomen en polytrees is exacte berekening haalbaar via equivalentieklassen.
• Voor dichte of grote DAG's kan het aantal equivalentieklassen nog steeds te groot worden, wat het gebruik van sampling-gebaseerde benaderingen noodzakelijk maakt.

Het werk concludeert dat ASV een veelbelovende richting is voor XAI, mits de causale grafiek bekend is en de grafiekstructuur efficiënte enumeratie of sampling van topologische ordeningen toelaat. Toekomstig werk wordt gesuggereerd om de exacte algoritmen te generaliseren naar bredere klassen van grafieken (bijv. algemene polytrees) en de sampling-mechanismen te optimaliseren.