Resumo Técnico: Além de Shapley: Computação Eficiente de Valores de Shapley Assimétricos

Declaração do Problema

O artigo aborda os desafios computacionais e de interpretabilidade associados à atribuição de características em IA Explicável (XAI). Embora os valores de Shapley (e sua instanciação de aprendizado de máquina, SHAP) forneçam um método teoricamente fundamentado para distribuir a previsão de um modelo entre as características de entrada, eles sofrem de duas limitações primárias:

1. Intratabilidade Computacional: Calcular valores de Shapley exatos é frequentemente #P-duro, particularmente para modelos expressivos (ex: redes neurais) ou quando a distribuição subjacente dos dados é complexa (ex: distribuições Naive Bayes).
2. Déficits de Interpretabilidade: Os valores de Shapley padrão tratam todas as características de forma simétrica. Isso falha em capturar relações causais, podendo atribuir importância igual a uma causa e seu efeito determinístico, o que obscurece o verdadeiro processo gerador de dados.

Para abordar o segundo problema, os Valores de Shapley Assimétricos (ASV) foram propostos, os quais restringem o cálculo a permutações de características que respeitam um grafo causal dado (um Grafo Acíclico Dirigido ou DAG). No entanto, a complexidade computacional do ASV não havia sido explorada minuciosamente. Este artigo investiga se a incorporação de restrições causais pode, de fato, tornar a computação dos escores de atribuição mais tratável do que os valores de Shapley padrão em contextos específicos.

Metodologia

Os autores propõem um conjunto de algoritmos para calcular o ASV de forma exata e aproximada, aproveitando a estrutura do grafo causal e a distribuição de probabilidade subjacente (modelada como uma Rede Bayesiana).

1. Análise de Tratabilidade Teórica

Os autores estabelecem um resultado teórico sobre a complexidade do ASV sob distribuições Naive Bayes. Eles provam que, enquanto o cálculo de valores de Shapley padrão é intratável para certas famílias de modelos sob distribuições Naive Bayes, calcular o ASV é tratável em tempo polinomial para as mesmas famílias se o grafo causal usado para o ASV for idêntico à estrutura da rede Naive Bayes. Isso sugere que as restrições causais impostas pela distribuição podem quebrar simetrias que, de outra forma, tornariam o problema difícil.

2. Computação Exata via Classes de Equivalência

Para estender a tratabilidade a estruturas causais mais gerais, especificamente árvores dirigidas enraizadas, os autores introduzem um método para reduzir o espaço de busca de permutações:

• Classes de Equivalência: Eles definem uma relação de equivalência sobre o conjunto de ordenações topológicas do grafo causal. Duas ordenações são equivalentes em relação a uma característica $x$ se o conjunto de características que precedem $x$ for idêntico em ambas as ordenações.
• Algoritmo: Em vez de iterar através de todas as ordenações topológicas (que podem ser exponenciais), o algoritmo calcula o conjunto de classes de equivalência ($\Lambda_x^C$) e o tamanho de cada classe. O ASV é então calculado somando as contribuições marginais ponderadas pelo tamanho de cada classe de equivalência.
• Complexidade: Para árvores dirigidas enraizadas, o número de classes de equivalência é limitado por $h \cdot l + 1$ (onde $h$ é a profundidade e $l$ é o número de folhas). Os autores fornecem um algoritmo de tempo polinomial (em termos do número de classes de equivalência) para calcular essas classes e seus tamanhos.

3. Computação Aproximada via Amostragem

Para DAGs causais arbitrários onde a computação exata pode ser inviável, os autores propõem um esquema de aproximação baseado em amostragem.

• Amostragem de Ordenações Topológicas: O método baseia-se na amostragem de ordenações topológicas uniformemente ao acaso. Os autores implementam duas abordagens:
  1. Um algoritmo de contagem recursiva para politrees (grafos com no máximo um caminho entre quaisquer dois nós) que conta ordenações topológicas para ponderar corretamente os nós de origem.
  2. Um algoritmo baseado em caminhada aleatória (baseado em Bubley & Dyer, 1999) para DAGs gerais.
• Limites de Erro: Eles formalizam que, se o amostrador de ordenação topológica estiver $\epsilon_{samp}$-próximo do uniforme e a função característica (valor esperado do modelo) for aproximada com erro $\epsilon_{\nu}$, o estimador ASV resultante possui um erro aditivo de $O(\epsilon_{samp} + \epsilon_{\nu})$.

Principais Resultados

Os autores avaliaram seus métodos em redes Bayesianas do mundo real (Cancer, Child) e estruturas artificiais (árvores balanceadas, Naive Bayes, múltiplos caminhos).

1. Redução no Espaço de Busca: A abordagem de classes de equivalência reduz significativamente a carga computacional em comparação com a enumeração de todas as ordens topológicas. Na rede "Child", o número de ordenações topológicas era de aproximadamente $7,41 \times 10^{11}$, enquanto o número de classes de equivalência foi de apenas $\approx 2003$ em média.
2. Eficiência de Tempo de Execução:
   • O cálculo das classes de equivalência para tamanhos práticos de grafos levou menos de um segundo.
   • O tempo de execução do algoritmo exato estava fortemente correlacionado com o número de classes de equivalência, permitindo que a pré-computação das contagens de classes servisse como um preditor para o custo computacional.
   • A enumeração de todas as ordenações topológicas tornou-se inviável para grafos maiores, enquanto o método de classe de equivalência permaneceu tratável.
3. Desempenho de Amostragem:
   • O algoritmo de amostragem recursiva customizado para politrees foi eficiente, apresentando escalonamento não linear em relação ao número de amostras devido à geração paralela de candidatos.
   • O uso de 1.000 amostras resultou em um erro relativo médio de aproximadamente 8% para os valores de ASV. O erro foi menor para valores de ASV maiores e maior para valores verdadeiros muito pequenos.

Significância e Alegações

O artigo afirma que o ASV é um framework viável e potencialmente superior para explicabilidade quando a estrutura causal é relevante, pois captura dependências que o SHAP padrão perde. A principal contribuição é demonstrar que restrições causais podem transformar um problema intratável em um problema tratável para pares específicos de modelo-distribuição (ex: árvores de decisão sob Naive Bayes).

Os autores enfatizam que, embora o ASV ofereça esses benefícios teóricos e práticos, sua escalabilidade depende fortemente da topologia do grafo causal:

• Para árvores dirigidas enraizadas e politrees, a computação exata é viável via classes de equivalência.
• Para DAGs densos ou grandes, o número de classes de equivalência ainda pode crescer demais, necessitando do uso de aproximações baseadas em amostragem.

O trabalho conclui que o ASV é uma direção promissora para XAI, desde que o grafo causal seja conhecido e a estrutura do grafo permita a enumeração ou amostragem eficiente de ordenações topológicas. Sugere-se que trabalhos futuros generalizem os algoritmos exatos para classes mais amplas de grafos (ex: politrees gerais) e otimizem os mecanismos de amostragem.