Resumo Técnico: Estimativa Aproximada do Valor de Shapley Usando Amostragem Sem Reposição e Novos Estimadores de Variância por Bootstrap

1. Enunciado do Problema

O framework clássico KernelSHAP (Lundberg e Lee, 2017) visa reduzir o custo computacional da estimativa do valor de Shapley amostrando um subconjunto de coalizões em vez de avaliar a função de contribuição para todos os $2^p$ subconjuntos possíveis. No entanto, as implementações existentes tipicamente amostram coalizões com reposição. Esta abordagem introduz desafios estatísticos específicos:

1. Ineficiência de Amostragem: A amostragem com reposição leva a uma versão ponderada do Problema do Colecionador de Cupons, onde obter coalizões únicas torna-se cada vez mais difícil à medida que o tamanho da amostra cresce, particularmente para coalizões de baixo peso.
2. Limitações na Estimativa de Variância: Métodos tradicionais de bootstrap assumem amostras independentes e identicamente distribuídas (i.i.d.). Essa premissa é violada quando se amostra sem reposição de uma população finita (o conjunto de todas as coalizões possíveis). Consequentemente, as técnicas de bootstrap padrão podem gerar estimativas de variância incorretas para os valores de Shapley, falhando em considerar a restrição de população finita onde a variância deveria teoricamente aproximar-se de zero se todas as coalizões fossem avaliadas.

O artigo aborda esses problemas propondo um framework que utiliza amostragem sem reposição e introduz novas metodologias de bootstrap compatíveis com a teoria de populações finitas para estimar com precisão a variância dos valores de Shapley aproximados.

2. Metodologia

2.1 Amostragem Sem Reposição via Distribuição de Wallenius

O algoritmo proposto modifica o procedimento KernelSHAP para amostrar coalizões sem reposição. O processo envolve duas etapas principais:

1. Estratificação: As coalizões são agrupadas pelo número de características (tamanho) que contêm.
2. Determinação dos Tamanhos de Amostra: Em vez de amostrar coalizões uma a uma estocasticamente, o algoritmo calcula o número esperado de coalizões a serem extraídas de cada grupo usando a distribuição hipergeométrica não central de Wallenius. Esta distribuição modela a amostragem enviesada sem reposição onde os itens possuem pesos diferentes.
   • O algoritmo utiliza os valores esperados desta distribuição, arredondados para o inteiro mais próximo, para determinar o número de coalizões a serem amostradas de cada estrato.
   • Uma vez determinados os contagens, as coalizões são amostradas sem reposição dentro de cada grupo.
   • Estratégia de Emparelhamento: Para reduzir ainda mais a variância, o método emprega uma estratégia de emparelhamento (Kroese et al., 2013). Se uma coalizão $S$ é amostrada, seu complemento $S^c$ também é incluído na computação, garantindo que a soma das características nos grupos emparelhados permaneça constante.

2.2 Estimativa de Variância via Métodos de Bootstrap

O artigo avalia três abordagens para estimar o desvio padrão dos valores de Shapley sob o novo design de amostragem:

1. Método Intuitivo Inválido: Um estimador de variância de Horvitz-Thompson padrão aplicado diretamente ao problema de mínimos quadrados ponderados. O autor demonstra que este é inválido porque falha em considerar as dependências específicas introduzidas pela estratégia de emparelhamento e a estrutura da matriz $Z^T W Z$ no contexto do KernelSHAP.
2. Doubled Half Bootstrap (Antal e Tillé, 2014): Um método conhecido para populações finitas onde as unidades são selecionadas via amostragem de Bernoulli, e as unidades não selecionadas são selecionadas duas vezes aleatoriamente. Este método é implementado para comparação.
3. Symmetric Bootstrap (Nova Contribuição): Um novo método de bootstrap desenvolvido especificamente para este contexto.
   • Mecanismo: Em cada amostra de bootstrap, cada unidade da amostra original pode aparecer 0, 1 ou 2 vezes.
   • Simetria: O método garante que o número total de unidades que aparecem 0 vezes seja igual ao número total de unidades que aparecem 2 vezes.
   • Probabilidades: As probabilidades para uma unidade $k$ aparecer $S_k$ vezes são definidas como:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • Propriedades: Esta construção garante que o valor esperado $E(S_k) = 1$ e a variância $Var(S_k) = 1 - \frac{n}{N}$, satisfazendo as condições necessárias para uma estimativa de variância válida em amostragem de população finita (consistência de Horvitz-Thompson).
   • Tratamento de Não-Inteiros: Quando o número esperado de ocorrências "0" ou "2" não é um inteiro, uma variável aleatória de Bernoulli é introduzida para alternar entre valores inteiros adjacentes, garantindo que o procedimento permaneça totalmente automático.

2.3 Implementação Computacional

A função de contribuição $v(S)$ é estimada via regressão sobre as coalizões amostradas. A implementação utiliza matrizes esparsas e decomposição de Cholesky (pacote Matrix) para lidar com modelos lineares de forma eficiente, sendo capaz de estimar médias de 65.000 modelos lineares em um único núcleo em poucos minutos (Aanes, 2025).

3. Principais Contribuições

1. Framework de Amostragem: Integração da distribuição hipergeométrica não central de Wallenius no framework KernelSHAP para permitir uma amostragem eficiente sem reposição, evitando as ineficiências do Problema do Colecionador de Cupons inerentes à amostragem com reposição.
2. Symmetric Bootstrap: A introdução de um novo método de bootstrap, computacionalmente eficiente, adaptado para amostragem sem reposição em populações finitas. Ele satisfaz as condições de momento necessárias (média e variância) para uma estimativa de variância não enviesada neste contexto.
3. Análise de Estimativa de Variância: Uma comparação rigorosa de estimadores de variância, demonstrando que o bootstrapping padrão é inválido para este design específico e que o novo Symmetric bootstrap supera ou iguala o Doubled half bootstrap existente (Antal e Tillé, 2014).

4. Resultados

Dois estudos de simulação foram conduzidos utilizando o conjunto de dados "Life Expectancy" do Kaggle, comparando o novo método contra o estado da arte do pacote R shapr (versão 1.0.7), que amostra com reposição.

• Estudo de Simulação Pequeno (5 características, 16 coalizões):
  • O novo método de amostragem produziu estimativas de valores de Shapley com desvios padrão comparáveis ao shapr.
  • O Antal-Tillé bootstrap teve um desempenho ruim, resultando frequentemente em matrizes de posto não total ($Z^T W Z$) e estimativas de variância imprecisas.
  • O Symmetric bootstrap apresentou um desempenho significativamente melhor que o Antal-Tillé, embora ocasionalmente tenha produzido desvios padrão ligeiramente "liberais" (menores) em comparação com o ground truth (reamostragem de todas as coalizões).
• Estudo de Simulação Grande (16 características, 402 coalizões):
  • Os métodos Symmetric bootstrap e Antal-Tillé produziram estimativas de desvio padrão indistinguíveis.
  • Ambos os novos métodos de bootstrap performaram ligeiramente melhor que o procedimento de bootstrap integrado no shapr, que tendia a subestimar os desvios padrão para várias variáveis.
  • O novo algoritmo de amostragem (sem reposição) performou de forma semelhante ao método do shapr (com reposição) em termos de precisão das próprias estimativas de valores de Shapley.

5. Significância e Conclusão

O artigo conclui que o algoritmo proposto, que combina a amostragem sem reposição via distribuição de Wallenius com o novo Symmetric bootstrap, oferece uma alternativa robusta às implementações existentes de KernelSHAP.

• Desempenho: O novo método performa "similarmente" ao método de KernelSHAP aprimorado no pacote shapr no que diz respeito às estimativas de ponto.
• Estimativa de Variância: O Symmetric bootstrap é destacado como um método "muito rápido computacionalmente e fácil de entender", que performa bem, particularmente em estudos de simulação maiores. Ele aborda a lacuna na literatura para um método de bootstrap "go-to" para amostragem aleatória sem reposição em populações finitas.
• Limitações: O autor nota modestamente que, no estudo mais pequeno, o Symmetric bootstrap ocasionalmente produziu desvios padrão ligeiramente pequenos (liberais) para certas variáveis, embora tenha capturado consistentemente os maiores desvios padrão.
• Aplicabilidade: O método é projetado para cenários onde a função de contribuição é estimada via modelos lineares ou modelos lineares generalizados (onde as previsões são lineares em uma escala transformada), aproveitando técnicas de computação rápida.

O trabalho estabelece que a teoria de populações finitas pode ser aplicada com sucesso à estimativa de valores de Shapley para melhorar a eficiência da amostragem e fornecer estimativas de variância válidas, superando as limitações teóricas das premissas tradicionais de i.i.d. de bootstrap neste domínio.