Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

O artigo propõe o método LSMR, que aproveita a localidade induzida por modelos para reduzir drasticamente o custo computacional da valoração de dados via valor de Shapley, retraindo apenas os subconjuntos de dados verdadeiramente influentes para cada instância de teste.

O essencial

Imagine que você tem uma equipe gigante de 100.000 pessoas trabalhando juntas para criar um único projeto (um modelo de Inteligência Artificial). No final do projeto, o chefe quer saber: quem foi o mais importante? Quem trouxe a ideia genial? Quem fez o trabalho duro? Quem foi apenas "enfeite"?

A ciência de dados tem uma ferramenta matemática chamada Valor de Shapley para responder a essa pergunta de forma justa. Ela calcula a contribuição de cada pessoa olhando para todas as combinações possíveis de equipes que poderiam ser formadas.

O Problema:
O problema é que, com 100.000 pessoas, o número de combinações possíveis é tão grande que é impossível calcular. Seria como tentar provar todas as receitas possíveis do mundo para ver qual é a melhor, uma a uma. Levaria mais tempo do que a vida do universo.

A Solução Criativa (O "Pulo do Gato"):
Os autores deste artigo perceberam algo genial: nem todo mundo influencia todo mundo.

Pense em uma receita de bolo. Se você está avaliando o sabor do bolo, a quantidade de farinha importa muito. Mas a quantidade de sal no prato de comida do vizinho (que você nem conhece) não importa absolutamente nada para o seu bolo.

Na Inteligência Artificial moderna, isso acontece o tempo todo:

• Se o modelo é um K-Nearest Neighbors (como um vizinho que olha para quem está perto), apenas os "vizinhos" mais próximos do ponto de teste importam. O resto do mundo é irrelevante.
• Se é uma Árvore de Decisão, apenas os dados que caíram na mesma "folha" da árvore importam.
• Se é uma Rede Neural em Grafos, apenas os nós conectados diretamente importam.

Os autores chamam isso de "Localidade Induzida pelo Modelo". Basicamente, o modelo diz: "Ei, para prever este resultado específico, eu só preciso olhar para este pequeno grupo de dados. O resto é ruído."

A Grande Inovação: LSMR e LSMR-A

Com essa ideia em mente, eles criaram dois métodos para resolver o problema de forma rápida e justa:

1. LSMR (O Organizador Perfeito):
   Imagine que você tem várias equipes diferentes para avaliar. Em vez de cada equipe reescrever o mesmo relatório do zero, o LSMR cria um sistema inteligente.

   • Ele identifica quais grupos de dados são únicos.
   • Ele treina o modelo uma única vez para cada grupo único.
   • Depois, ele reutiliza esse resultado para todas as pessoas que precisam daquela avaliação.
   • Analogia: É como se você fizesse um bolo para a festa. Em vez de cada convidado fazer seu próprio bolo, você faz um grande bolo e serve fatias. Ninguém desperdiça ingredientes. O resultado é matematicamente perfeito (exato), mas feito em uma fração do tempo.

2. LSMR-A (O Adivinho Inteligente):
   Às vezes, o grupo de dados relevante ainda é grande demais para calcular tudo. Então, eles usam um método de "amostragem" (como tirar uma amostra de um prato gigante para ver o tempero).

   • O método comum (Monte Carlo) pega uma amostra, testa, joga fora, pega outra, testa, joga fora... muito desperdício.
   • O LSMR-A é como um cozinheiro esperto: se ele já provou um tempero específico em uma amostra, ele guarda esse resultado e o usa para todas as outras pessoas que precisam daquele mesmo tempero.
   • Isso torna a estimativa muito mais rápida e precisa, porque ele não repete o trabalho desnecessário.

Por que isso é importante?

• Economia de Tempo e Dinheiro: O que antes levava dias ou semanas para calcular, agora leva minutos ou horas.
• Justiça: Eles conseguem dizer exatamente quem contribuiu para o sucesso do modelo, sem ter que simular o impossível.
• Aplicação Real: Isso é crucial para mercados de dados. Se uma empresa quer comprar dados de outra, precisa saber o valor real desses dados. Com essa técnica, podemos calcular esse valor de forma justa e rápida, mesmo com milhões de dados.

Resumo da Ópera:
Os autores pegaram um problema matemático impossível (calcular a importância de todos os dados) e disseram: "Esqueça o impossível. Vamos focar apenas no que realmente importa para cada previsão específica." Eles criaram um sistema que evita repetir o trabalho (reutilização inteligente) e transformou uma tarefa de "impossível" em uma tarefa "super rápida e precisa".

É como se, em vez de tentar ler todos os livros da biblioteca para encontrar uma resposta, você soubesse exatamente em qual prateleira, qual livro e qual página a resposta estava, e só lesse aquilo.

Resumo técnico

Resumo Técnico: Local Shapley

1. O Problema

A valoração de dados é fundamental para mercados de dados, debugging de modelos e aprendizado federado. O Valor de Shapley é o padrão-ouro para essa tarefa, pois atribui a cada ponto de dados sua contribuição marginal justa baseada em todas as combinações possíveis de subconjuntos (coalizões).

No entanto, o cálculo exato do Valor de Shapley é NP-difícil (#P-hard) devido ao espaço exponencial de coalizões ($2^{|D|}$, onde$|D|$ é o tamanho do conjunto de treinamento). As abordagens existentes de aceleração (como Monte Carlo, truncamento ou métodos baseados em influência) ainda operam globalmente, assumindo implicitamente que todo ponto de treinamento pode influenciar qualquer ponto de teste através do retreinamento do modelo.

O artigo identifica que essa suposição é excessivamente pessimista. Modelos modernos exibem esparsidade estrutural: para uma instância de teste específica, apenas um pequeno subconjunto de dados de treinamento participa efetivamente do caminho computacional que determina a previsão (ex: vizinhos em KNN, folhas em árvores de decisão, campos receptivos em GNNs). Ignorar essa estrutura leva a cálculos redundantes e desnecessários.

2. Metodologia

Os autores propõem uma reformulação do problema baseada em duas ideias centrais: Localidade Induzida pelo Modelo e Reutilização Ótima de Subconjuntos.

A. Localidade Induzida pelo Modelo (Support Sets)

• Definição: Para cada ponto de teste $t$, define-se um conjunto de suporte $N(t) \subseteq D$, composto pelos pontos de treinamento que influenciam a previsão de $t$ através da arquitetura do modelo.
• Valoração Local: Em vez de calcular o Valor de Shapley global sobre $D$, calcula-se o Valor de Shapley Local sobre $N(t)$.
• Garantia Teórica: O artigo prova que, quando a localidade é exata (ex: KNN com limiar), o Valor de Shapley Local é idêntico ao Global. Quando é aproximada (ex: SVMs, GNNs), o erro de aproximação é limitado pela massa de interação não local, que decai rapidamente em algoritmos estáveis.

B. Complexidade Intrínseca e Reutilização

• Complexidade de Subconjuntos: Os autores demonstram que a complexidade intrínseca não é governada pelo número total de coalizões, mas pelo número de subconjuntos distintos que influenciam pelo menos uma valoração.
• Redundância: Existem redundâncias intra-suporte (mesmo subconjunto avaliado múltiplas vezes para diferentes pontos dentro do mesmo suporte) e inter-suporte (subconjuntos sobrepostos entre diferentes pontos de teste sendo reavaliados).

C. Algoritmos Propostos

1. LSMR (Local Shapley via Model Reuse): Um algoritmo exato que elimina redundâncias.

   • Mapeamento Bipartido: Constrói um grafo ligando subconjuntos a pontos de teste e treinamento.
   • Agendamento por Pivô: Para cada subconjunto distinto $S$, define-se um "avaliador canônico" (pivô). O modelo é treinado apenas uma vez para $S$ e o resultado é reutilizado para todos os pontos de teste que contêm $S$ em seus suportes.
   • Ótimo: O algoritmo atinge o limite inferior teórico de operações de retreinamento, treinando cada subconjunto distinto exatamente uma vez.

2. LSMR-A (Aproximação Monte Carlo com Consciência de Reuso): Para suportes grandes onde a enumeração exata é inviável.

   • Adapta a amostragem de Monte Carlo para o contexto de reutilização.
   • Em vez de tratar cada amostra de coalizão independentemente, o algoritmo compartilha amostras de subconjuntos entre todos os suportes compatíveis.
   • Propriedades: Mantém a inviés (unbiasedness), possui concentração exponencial (erro decresce exponencialmente com o número de amostras) e reduz a variância ao amortizar a aleatoriedade redundante.

3. Principais Contribuições

1. Abstração Estrutural: Formalização da "Localidade Induzida pelo Modelo" como uma propriedade estrutural de preditores modernos (KNN, SVM, Árvores, GNNs), permitindo projetar o espaço de coalizões em conjuntos de suporte menores.
2. Limite Inferior Teórico: Estabelecimento de um limite inferior de informação sobre o número de operações de retreinamento necessárias, provando que qualquer algoritmo correto deve avaliar cada subconjunto influente distinto pelo menos uma vez.
3. Algoritmos Ótimos: Desenvolvimento do LSMR (exato) e LSMR-A (estocástico), que desacoplam a complexidade de amostragem da complexidade de retreinamento, garantindo reutilização ótima de subconjuntos.
4. Validação Empírica: Demonstração de que a localidade preserva a fidelidade da valoração e que a reutilização estrutural reduz drasticamente os custos computacionais sem sacrificar a precisão.

4. Resultados Experimentais

Os autores avaliaram o framework em quatro famílias de modelos: KNN ponderado (WKNN), SVM com Kernel RBF, Árvores de Decisão e Redes Neurais em Grafos (GNN).

• Fidelidade (RQ1): O Valor de Shapley Local correlaciona-se fortemente com o Global (Pearson $r$ entre 0.53 e 0.84). Em KNN, a correlação é quase perfeita devido à localidade exata.
• Utilidade em Seleção de Dados (RQ2): A valoração local é altamente eficaz para tarefas downstream (como seleção de dados para treinamento). Em KNN, 10% dos dados selecionados localmente alcançaram a mesma precisão que 20-25% selecionados globalmente.
• Eficiência Computacional (RQ3):
  • O LSMR-A reduziu o número de treinamentos de modelos em mais de 3 ordens de magnitude (ex: de 1,126M para 0,9M em KNN) comparado a métodos globais.
  • O tempo de execução foi reduzido em até 5 ordens de magnitude em cenários de grande escala.
  • A complexidade de retreinamento cresceu de forma sublinear em relação ao tamanho do conjunto de dados, confirmando a eficácia da reutilização.
• Sensibilidade ao Tamanho do Suporte (RQ4): A fidelidade melhora com o aumento do suporte, mas a precisão na seleção de dados estabiliza rapidamente, indicando que suportes pequenos já capturam os caminhos de influência dominantes.
• Alinhamento do Modelo (RQ5): A localidade deve ser alinhada à arquitetura do modelo de avaliação. Usar suportes de um modelo para avaliar outro (ex: suporte de GNN para KNN) degrada a performance, mas ainda supera abordagens aleatórias, desde que haja alguma consistência estrutural.

5. Significado e Impacto

Este trabalho transforma a valoração de dados de um problema de enumeração exaustiva para um problema estruturado de processamento de dados. Ao reconhecer que a maioria dos pontos de treinamento é irrelevante para previsões específicas, o método permite:

• Escalabilidade: Torna viável a valoração de dados em conjuntos massivos e modelos complexos onde métodos anteriores eram computacionalmente proibitivos.
• Eficiência de Recursos: Reduz drasticamente o custo energético e de tempo de computação ao eliminar retreinamentos redundantes.
• Fundamentação Teórica: Oferece garantias rigorosas sobre a precisão e a complexidade, estabelecendo novos limites inferiores para a área.

Em suma, o Local Shapley demonstra que a exploração inteligente da estrutura do modelo e a reutilização ótima de cálculos podem resolver o gargalo de escalabilidade da valoração de dados baseada em Shapley, abrindo caminho para aplicações práticas em larga escala.