A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Este artigo propõe o método ESENSC_rev2, uma alternativa axiomática e computacionalmente eficiente ao SHAP para atribuição de características, que combina regras de alocação de baixo custo para aproximar com precisão os valores de Shapley em tarefas de alta dimensionalidade, garantindo escalabilidade sem sacrificar fundamentos teóricos.

O essencial

Imagine que você tem um time de futebol (o seu modelo de Inteligência Artificial) e, no final do jogo, o time marcou 3 gols. A pergunta é: quem foi o verdadeiro herói? Foi o goleiro que fez uma defesa milagrosa? O atacante que chutou? Ou o zagueiro que roubou a bola?

Na área de Inteligência Artificial Explicável (XAI), queremos saber exatamente quanto cada "jogador" (cada dado de entrada, como idade, salário ou localização) contribuiu para a decisão final do modelo.

O método mais famoso hoje para fazer essa contagem é chamado de SHAP. Ele é como um árbitro extremamente justo, que calcula a contribuição de cada jogador considerando todas as combinações possíveis de times que poderiam ter sido formados. O problema? Para fazer isso com precisão, o árbitro precisa simular milhões de jogos. Se o time tiver muitos jogadores (muitos dados), o cálculo demora uma eternidade e fica impossível de fazer na prática.

É aqui que entra este novo estudo, que propõe uma alternativa rápida e inteligente chamada ESENSC_rev2.

A Analogia do "Dividendo do Time"

Para entender a proposta dos autores, vamos usar uma analogia de um grupo de amigos dividindo uma conta de jantar ou um prêmio de loteria.

1. O Problema do SHAP (O Cálculo Perfeito, mas Lento):
   O SHAP tenta calcular a contribuição de cada pessoa olhando para cada possível subgrupo de amigos. "O que aconteceria se apenas o João e a Maria comessem juntos? E se fosse só o João? E se fosse todos menos a Maria?" Ele faz isso para todas as combinações. É justo, mas computacionalmente exaustivo.

2. A Solução Rápida (ESENSC_rev2):
   Os autores olharam para a teoria dos jogos (como dividir lucros entre parceiros) e encontraram duas regras antigas e rápidas:

   • Regra do Excedente Igualitário (ES): "Cada um fica com o que ganhou sozinho, e o que sobrou do prêmio total é dividido igualmente entre todos."
   • Regra da Contribuição Não Separável (ENSC): "Vamos começar do fim. Se tirarmos um amigo, quanto o grupo perde? Esse valor é dele. O que sobrar é dividido igualmente."

   A ideia genial do ESENSC_rev2 é pegar a média dessas duas regras. É como dizer: "Vamos olhar para o que você vale sozinho, e também para o quanto o time perde sem você, e tirar a média. Depois, dividimos o resto do bolo de forma justa."

Por que isso é especial?

O estudo traz três grandes novidades, explicadas de forma simples:

1. A Regra do "Jogador Inútil" (Propriedade do Jogador Nulo)

Em algumas regras antigas de divisão de lucros, se um jogador não contribuiu nada, ele ainda podia receber um pedacinho do bolo só porque o bolo era grande demais.
No mundo da IA, isso é um erro. Se um dado (como a cor dos olhos) não mudou a previsão do modelo, ele não pode receber crédito.
Os autores ajustaram a fórmula para garantir que, se um "jogador" não fez nada, ele ganha zero. É como dizer: "Se você não jogou, não ganha prêmio."

2. O Problema do "Sinal Confuso" (Regras Proporcionais)

O estudo também testou outras regras baseadas em proporções (como dividir o bolo baseado no tamanho do prato de cada um). Eles descobriram que, em cenários complexos onde alguns dados ajudam e outros atrapalham (sinais positivos e negativos misturados), essas regras podem ficar malucas e inverter a lógica: dar mais crédito para quem fez menos.
A solução deles (ESENSC_rev2) evita esse caos, mantendo a ordem lógica: quem contribuiu mais, ganha mais.

3. Velocidade vs. Precisão

Os autores fizeram testes com modelos de IA reais (como os usados para prever preços de casas ou riscos de crédito).

• SHAP Exato: Preciso, mas lento como uma tartaruga em dias de chuva quando o número de dados aumenta.
• SHAP Aproximado (o que as pessoas usam hoje): Rápido, mas às vezes erra a conta e precisa de muitos ajustes manuais.
• ESENSC_rev2 (A Nova Proposta): É rápido como um raio (cresce linearmente com o número de dados, não exponencialmente) e é quase tão preciso quanto o SHAP exato.

A Conclusão em uma Frase

Imagine que você precisa dividir um prêmio milionário entre 100 pessoas.

• O SHAP é o contador que revisa cada centavo de cada possível combinação de pessoas. Demora anos.
• O ESENSC_rev2 é um gerente esperto que usa uma fórmula matemática simples e justa para dividir o prêmio em segundos, garantindo que ninguém que não trabalhou receba nada, e que a divisão seja quase idêntica à do contador.

Resumo da Ópera:
Este paper diz que não precisamos mais escolher entre "ser justo mas lento" ou "ser rápido mas injusto". Eles criaram uma nova regra matemática que é rápida, justa e teoricamente sólida, perfeita para explicar modelos de IA complexos no mundo real, sem precisar de supercomputadores. É como encontrar o "Santo Graal" da explicação de Inteligência Artificial: precisão de luxo com o preço de um café.

Resumo técnico

Título: Uma Alternativa Axiomática de Tempo Polinomial ao SHAP para Atribuição de Recursos

1. O Problema

O campo da Inteligibilidade Artificial (XAI) depende fortemente de métodos de atribuição de recursos aditivos (AFA) para decompor as previsões de modelos complexos em contribuições de nível de recurso. O SHAP (SHapley Additive exPlanations), baseado no valor de Shapley da teoria dos jogos cooperativos, é o padrão da indústria devido à sua fundamentação teórica robusta.

No entanto, o SHAP enfrenta um desafio crítico: custo computacional exponencial. O cálculo exato do valor de Shapley requer a avaliação de $2^n$ coalizões (onde $n$ é o número de recursos), tornando-o inviável para conjuntos de dados com muitas características. Embora existam algoritmos de aproximação (como Kernel SHAP e Permutation SHAP), eles frequentemente:

• Possuem instabilidade na precisão.
• Requerem ajuste de hiperparâmetros (como o número de amostras).
• Não garantem propriedades teóricas desejáveis em todas as situações.

Além disso, os jogos de XAI (XAI-TU games) apresentam características estruturais distintas dos jogos cooperativos tradicionais, como a coexistência de valores de coalizão positivos e negativos e valores de base ($v(\emptyset)$) não nulos, o que pode levar a comportamentos contra-intuitivos em regras de alocação padrão.

2. Metodologia

Os autores abordam o problema através da lente da teoria dos jogos cooperativos, formulando o problema de atribuição de recursos como um jogo de utilidade transferível específico para XAI (XAI-TU game).

Abordagem Proposta:
Em vez de calcular o valor de Shapley, os autores investigam conceitos de solução de baixo custo computacional:

1. Soluções do Tipo Excedente Igualitário (Equal Surplus - ES): Focam em distribuir o excedente residual igualmente entre os jogadores.
2. Soluções do Tipo Alocação Proporcional (Proportional Allocation - PA): Distribuem o excedente proporcionalmente às contribuições marginais.

Desenvolvimento da Regra Proposta (ESENSC_rev2):

• Os autores começam com uma média ponderada (50-50) das soluções Equal Surplus (ES) e Egalitarian Nonseparable Contribution (ENSC).
• Identificam que a média simples viola a propriedade do jogador nulo (um recurso que não afeta a previsão não deve receber atribuição).
• Propõem uma modificação, ESENSC_rev2, que redistribui o excedente residual apenas entre recursos com contribuições marginais não nulas. Isso garante que recursos irrelevantes recebam zero, satisfazendo a propriedade do jogador nulo.
• Para as soluções do tipo proporcional, eles identificam o "problema de reversão de ordem" (onde a ordem de contribuição é invertida devido a sinais conflitantes) e propõem regras híbridas (PARPA) para mitigar isso, embora os resultados empíricos mostrem que essas regras ainda sofrem de instabilidade.

Fundamentação Axiomática:
O artigo estabelece uma caracterização axiomática única para a regra ESENSC_rev2. Eles provam que esta regra é a única solução que satisfaz:

• Eficiência: A soma das atribuições iguala a diferença entre a previsão total e a linha de base.
• Propriedade do Jogador Nulo: Recursos sem impacto recebem zero.
• Marginalidade Diferencial Restrita: Uma versão enfraquecida do axioma de marginalidade diferencial do SHAP, adaptada para o domínio de XAI.
• Propriedade de Jogo Inessencial Intermediário: Uma regra de justiça que considera tanto a perspectiva pessimista quanto a otimista das contribuições marginais.
• Redução da Complexidade Computacional: O cálculo depende apenas de coalizões de tamanho 0, 1, $n-1$ e $n$, evitando a necessidade de avaliar todas as $2^n$ coalizões.

3. Principais Contribuições

1. Formulação de XAI-TU Games: Formalização rigorosa do problema de atribuição de recursos como jogos cooperativos com características específicas (valores de base não nulos e sinais mistos).
2. Algoritmo ESENSC_rev2: Proposta de uma nova regra de atribuição que combina baixa complexidade computacional (tempo polinomial, especificamente $O(n)$ ou $O(n^2)$ dependendo da implementação da função característica) com alta precisão de aproximação.
3. Caracterização Axiomática: Primeira caracterização axiomática de uma regra de atribuição de tempo polinomial que aproxima o SHAP, distinguindo-a teoricamente do valor de Shapley através de axiomas que priorizam a tratabilidade computacional.
4. Análise Comparativa: Demonstração de que soluções do tipo proporcional (PA) sofrem de instabilidade intrínseca em jogos XAI, enquanto soluções do tipo excedente igualitário (ES) oferecem um equilíbrio superior.

4. Resultados Experimentais

Os autores realizaram extensos experimentos em tarefas de previsão tabular (conjunto de dados California Housing) utilizando modelos XGBoost e Redes Neurais, variando o número de recursos de 8 até 512.

• Precisão (Desvio do SHAP Exato):
  • O ESENSC_rev2 apresentou desvios muito pequenos em relação ao SHAP exato, superando consistentemente métodos de aproximação baseados em amostragem como Kernel SHAP e sendo comparável ao Permutation SHAP.
  • As regras do tipo proporcional (PARPA) mostraram desvios significativos e instáveis, confirmando a teoria sobre o problema de reversão de ordem e outras fontes de instabilidade.
• Custo Computacional:
  • O SHAP exato cresce exponencialmente, tornando-se incomputável para $n > 16$.
  • O ESENSC_rev2 escala de forma aproximadamente linear com o número de recursos.
  • O tempo de computação do ESENSC_rev2 é substancialmente menor do que o dos métodos de aproximação baseados em amostragem (Permutation e Kernel SHAP), que exigem milhares de avaliações do modelo.
• Vantagem Prática: Diferente dos métodos de amostragem, o ESENSC_rev2 não requer ajuste de hiperparâmetros (como número de iterações), sendo uma solução "plug-and-play" determinística.

5. Significado e Conclusão

O artigo estabelece o ESENSC_rev2 como uma alternativa viável, teoricamente fundamentada e computacionalmente eficiente ao SHAP.

• Impacto Teórico: Demonstra que é possível sacrificar a força de alguns axiomas clássicos (como a marginalidade diferencial completa) em favor de axiomas que garantem eficiência computacional e propriedades de nulidade, sem perder a qualidade da aproximação.
• Impacto Prático: Oferece uma solução escalável para a explicabilidade de modelos em alta dimensão, eliminando a necessidade de compromissos entre custo e precisão inerentes aos métodos de aproximação atuais.
• Futuro: O trabalho sugere que a perspectiva da teoria dos jogos cooperativos pode levar ao desenvolvimento de mais regras de atribuição adaptadas às estruturas específicas dos jogos de XAI, superando as limitações dos métodos tradicionais.

Em resumo, o papel propõe que, para pipelines de explicabilidade modernos que lidam com muitos recursos, o ESENSC_rev2 oferece o melhor equilíbrio entre rigor teórico, precisão e eficiência computacional.