Resumo Técnico: Estimativa Aproximada Rápida de Valores de Shapley Condicionais com Explicadores Lineares

Definição do Problema

O artigo aborda o gargalo computacional associado à estimativa de valores de Shapley condicionais para modelos de regressão linear quando as covariáveis são dependentes. Embora os valores de Shapley forneçam uma decomposição game-teórica das contribuições de recursos para uma previsão específica, calcular valores condicionais exige a estimativa da saída esperada do modelo para todas as possíveis coalizões de recursos.

Para um modelo com $p$ preditores, existem $2^p$ coalizões possíveis. Métodos existentes, como as abordagens Sequencial e Iterativa no pacote R shapr, enfrentam desafios significativos:

1. Estimativa Sequencial: Requer o ajuste de $2^p$ modelos de regressão separados, o que se torna computacionalmente intratável à medida que $p$ aumenta.
2. Estimativa Iterativa: Amostra coalizões até que um critério de convergência seja atendido. Embora seja mais rápida quando poucas coalizões são suficientes, ainda pode exigir uma grande fração de todas as $2^p$ coalizões para atingir a convergência, levando a tempos de execução longos (horas) comparáveis ao método sequencial em casos difíceis.
3. Dependência de Recursos: Ao contrário dos valores de Shapley marginais, os valores condicionais devem considerar a estrutura de dependência entre as covariáveis, necessitando de cálculos complexos de expectativa condicional.

Os autores visam desenvolver métodos que possam estimar os coeficientes para todas as $2^p$ sub-estruturas simultaneamente e de forma rápida, aproveitando a esparsidade das estruturas matemáticas subjacentes.

Metodologia

A abordagem proposta utiliza a teoria de Campos Aleatórios de Markov Gaussianos Restritos (GMRF) e álgebra de matrizes esparsas para estimar os coefertos de regressão para todos os submodelos conjuntamente, em vez de sequencialmente. Os autores derivam três algoritmos distintos:

1. O Método de Correção Diagonal (Aproximado)

Este método aproxima a regressão restrita modificando a matriz de precisão ($Q = X^T X$) do modelo completo.

• Mecanismo: Para impor uma restrição onde um coeficiente específico é zero (ou seja, o recurso é excluído de um submodelo), um valor escalar grande $\kappa$ é adicionado ao elemento diagonal correspondente da matriz de precisão.
• Base Teórica: Baseia-se na identidade da matriz de Woodbury, onde adicionar $\kappa A^T A$ (onde $A$ é uma matriz de restrição) aproxima a matriz de covariância condicional conforme $\kappa \to \infty$.
• Implementação: Uma matriz de restrição conjunta $A$ é construída para todos os $2^p$ modelos. O método resolve o sistema linear $(Q_F + \kappa A^T A)^{-1}m$, onde $Q_F$ é uma matriz bloco-diagonal contendo a matriz de precisão do modelo completo repetida $2^p$ vezes.
• Ajuste (Tuning): Requer um parâmetro de ajuste $\kappa$, sugerido como $10^5$ vezes o maior autovalor da matriz de precisão original.

2. O Método de Projeção (Aproximado)

Este método projeta o espaço de parâmetros para remover parâmetros restritos.

• Mecanismo: Uma matriz de projeção $Z = I - A^T A$ é aplicada à matriz de precisão. O modelo restrito é tratado como um GMRF intrínseco. Para garantir estabilidade numérica (positividade definida), um pequeno escalar $\epsilon$ é adicionado ao diagonal da matriz de precisão projetada ($Z Q Z + \epsilon I$).
• Base Teórica: À medida que $\epsilon \to 0^+$, a solução converge para as estimativas restritas exatas.
• Implementação: Resolve o sistema $Z(Z Q_F Z + \epsilon I)^{-1} Z m$.
• Ajuste (Tuning): Requer um pequeno parâmetro de ajuste $\epsilon$ (ex: $10^{-5}$), escolhido para ser pequeno em relação ao menor autovalor de $Q$, mas grande o suficiente para uma decomposição de Cholesky estável.

3. O Método de Transformação Exata (Exato)

Este método fornece uma solução exata sem erros de aproximação ou parâmetros de ajuste.

• Mecanismo: Em vez de trabalhar no espaço de parâmetros completo e forçar coeficientes a zero, o método transforma o problema em um espaço de menor dimensão contendo apenas os parâmetros não nulos.
• Implementação: Uma matriz de mapeamento $E$ é construída para selecionar apenas os parâmetros ativos para cada submodelo. O sistema é resolvido como $(E Q_F E^T)^{-1} E m$.
• Vantagem: Elimina a necessidade de termos de penalidade grandes ($\kappa$) ou termos de regularização pequenos ($\epsilon$), evitando potencial instabilidade numérica ou viés de aproximação.

Todos os três métodos utilizam álgebra de matrizes esparsas (especificamente decomposição de Cholesky) para lidar com a estimativa conjunta de milhares de modelos de forma eficiente. A matriz de precisão conjunta é altamente esparsa porque os modelos são independentes (estrutura bloco-diagonal), e os zeros fora da diagonal indicam independência condicional.

Contribuições Principais

1. Três Novos Algoritmos: O artigo introduz dois métodos aproximados (Correção Diagonal, Projeção) e um método exato (Transformação Exata) para a estimativa conjunta de todos os submodelos em regressão linear.
2. Provas de Convergência: Os autores fornecem provas matemáticas demonstrando que os métodos aproximados convergem para as estimativas condicionais verdadeiras conforme seus respectivos parâmetros de ajuste ($\kappa \to \infty$ e $\epsilon \to 0^+$).
3. Eficiência Computacional: Ao explorar a esparsidade e a estimativa conjunta, os métodos reduzem o tempo de computação de horas (típico do shapr) para segundos ou minutos, mesmo enumerando todas as $2^p$ coalizões.
4. Validação Empírica: Estudos numéricos extensos comparam os novos métodos contra o pacote shapr (versões Sequencial e Iterativa) em três conjuntos de dados: Adult Income, um conjunto de dados Gaussiano Simulado e o conjunto de dados WHO Life Expectancy.

Resultados

Os estudos de caso numéricos yielded os seguintes achados:

• Acurácia: As estimativas dos valores de Shapley produzidas pelos novos métodos são virtualmente idênticas ao método Sequencial em shapr (usado como verdade fundamental para enumeração total).
  • No conjunto Adult ($p=11$), o erro absoluto mediano (MedAE) entre os novos métodos e o método Sequencial foi da ordem de $10^{-9}$.
  • No conjunto Simulado ($p=21$), o MedAE foi da ordem de $10^{-7}$ a $10^{-5}$.
  • No conjunto WHO ($p=16$), o MedAE foi da ordem de $10^{-6}$.
• Velocidade:
  • Conjunto Adult: Os novos métodos rodaram em 2,5 a 9 segundos, enquanto o shapr (Sequencial e Iterativo) levou de 17 a 19 minutos.
  • Conjunto Simulado: Os novos métodos levaram de 1,4 a 2,5 minutos para estimar todos os $2^{21} \approx 2,1$ milhões de modelos. O método Iterativo do shapr foi mais rápido (6,48 segundos), mas estimou apenas 200 coalizões, não o conjunto completo.
  • Conjunto WHO: Os novos métodos levaram de 1,1 a 1,2 minutos. O método Sequencial do shapr levou 131 minutos (2,2 horas), e o Iterativo levou 16 minutos (paralelo) ou 36 minutos (serial).
• Escalabilidade: Os métodos estimaram com sucesso mais de dois milhões de submodelos no estudo simulado dentro de minutos. A principal limitação identificada é a restrição de memória (Maldição da Dimensionalidade) quando $p$ excede ~21 em hardware padrão, embora os autores notem que isso pode ser mitigado com mais RAM ou pacotes de matrizes esparsas especializados.

Significância e Alegações

O artigo afirma que os métodos propostos oferecem uma melhoria substancial na eficiência computacional para a estimativa de valores de Shapley condicionais sem sacrificar a acurácia.

• Superioridade na Enumeração Total: Quando o método Iterativo do shapr requer uma grande fração de coalizões para convergir (como visto nos conjuntos Adult e WHO), os novos métodos são "substancialmente mais rápidos" enquanto mantêm "acurácia igual ou superior".
• Enumeração Abrangente: Ao contrário da abordagem iterativa que amostra coalizões, os novos métodos fornecem uma enumeração total de todas as $2^p$ subestruturas, garantindo que nenhuma informação seja perdida devido à variância de amostragem.
• Recomendação: Os autores recomendam o Método de Transformação Exata para uso prático. Embora todos os três métodos produzam resultados comparáveis, o método Exato não possui parâmetros de ajuste, eliminando a necessidade de seleção de hiperparâmetros e potenciais fontes de erro de aproximação.
• Potencial Futuro: Os autores sugerem que a metodologia pode ser estendida para lidar com splines (ex: do pacote rms) e que a paralelização (ex: via OpenMP) poderia reduzir ainda mais os tempos de execução, embora a implementação atual dependa de execução serial para uma comparação justa com o pacote shapr paralelizado.

O artigo conclui que esses métodos tornam o cálculo exato de valores de Shapley condicionais para modelos lineares com tipos mistos de covariáveis viável em cenários onde anteriormente era computacionalmente proibitivo.