Resumo Técnico: NASH - Agregação Não-linear de Componentes Informativos de SHapley

Declaração do Problema

A seleção de dados visa identificar subconjuntos de alta qualidade de dados de treinamento para otimizar a utilidade do modelo (por exemplo, precisão de validação $u_V$) sob restrições de tamanho. Embora o Data Shapley e suas generalizações (semivalores) sejam fundamentados teoricamente na teoria dos jogos cooperativos para contabilizar interações entre dados, estudos empíricos recentes indicam que eles frequentemente performam de forma ineficaz na prática. Especificamente, selecionar os $m$ pontos de dados superiores com base em valores de Shapley computados em relação a funções de utilidade complexas (como precisão de validação) pode produzir subconjuntos não melhores, ou até piores, do que uma seleção aleatória.

O artigo identifica duas razões primárias para essa falha:

1. Falta de Informatividade de Shapley: Funções de utilidade complexas envolvem múltiplos "papéis" distintos (por exemplo, diferentes classes ou subpopulações no conjunto de validação). Um único valor de Shapley para um dado falha em capturar sua força única através desses papéis. Consequentemente, dados com forças diferentes podem receber pontuações de Shapley idênticas, levando a um tratamento intercambiável apesar de suas contribuições de utilidade distintas.
2. Agregação Inadequada: O objetivo real (por exemplo, precisão de validação) agrega desempenho através desses papéis de forma não-linear. No entanto, a heurística padrão de top-$m$ baseia-se em uma agregação linear (somando valores de Shapley), o que falha em capturar interações sinérgicas onde a contribuição de um dado depende de quais outros dados já foram selecionados (por exemplo, um dado é mais valioso se cobrir um papel sub-representado).

Metodologia: Framework NASH

Os autores propõem o NASH (Agregação Não-linear de Componentes Informativos de SHapley), um framework que decompõe a função de utilidade complexa em componentes mais simples onde os valores de Shapley são eficazes e, em seguida, os agrega de forma não-linear.

1. Informatividade de Shapley e Decomposição

O artigo formaliza a informatividade de Shapley como uma propriedade onde a soma dos valores de Shapley para um subconjunto é indicativa de sua utilidade real. Os autores provam que funções de utilidade arbitrárias geralmente não são informativas de Shapley. No entanto, eles demonstram que funções de utilidade mais simples, especificamente a correção de previsão em um único dado de validação ($u_v$), são comprovadamente informativas de Shapley sob a suposição de "Jogador Consistente" (onde um dado é consistentemente bom ou ruim para um ponto de validação específico).

Em vez de computar valores de Shapley para a precisão agregada de validação $u_V$, o NASH decompõe $u_V$ em componentes individuais $u_v$ para cada dado de validação $v \in V$. Os valores de Shapley $\phi_i(u_v)$ são computados para esses componentes mais simples. Notavelmente, computar esses vetores não incorre em custo de tempo de execução adicional comparado à computação do valor de Shapley para o agregado $u_V$, pois $u_V$ é simplesmente a média de $u_v$.

2. Agregação Não-linear

Para reconstruir o objetivo complexo a partir desses componentes informativos, o NASH evita a soma linear (que recupera a heurística falha de top-$m$ de Shapley). Em vez disso, ele otimiza um objetivo de agregação não-linear:
$$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$$
onde $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$ é a soma dos valores de Shapley para o componente $v$, e $F_T$ é uma função de distribuição acumulada (CDF) inspirada em curvas de aprendizado (por exemplo, uma lei exponencial). Esta função não-linear garante que o processo de seleção priorize dados que ajudam a "cruzar o limiar" para pontos de validação mal previstos (papéis descobertos) em vez de acumular altas pontuações em pontos já bem previstos.

3. Otimização

O objetivo do NASH é otimizado usando um algoritmo ganancioso. Os autores mostram que, quando os valores de Shapley são não-negativos, o objetivo é submodular monótono, garantindo uma aproximação de $(1 - 1/e)$. Mesmo com valores negativos (de dados ruidosos), o algoritmo ganancioso performa bem empiricamente porque os dados prejudiciais (que causam não-submodularidade) são naturalmente despriorizados. O algoritmo introduz custo de tempo de execução adicional mínimo, pois o trabalho pesado (aproximação de Shapley) é compartilhado com métodos existentes.

Contribuições Principais

1. Análise Teórica: O artigo formaliza a propriedade de informatividade de Shapley, explicando por que funções de utilidade complexas de ML (como precisão de validação) falham em satisfazê-la, levando ao desempenho inconsistente do Data Shapley.
2. Componentes Comprovadamente Informativos: Os autores identificam e provam que a correção de previsão em pontos únicos de dados de validação serve como componentes informativos de Shapley sob suposições razoáveis.
3. Framework NASH: Um novo framework de seleção de dados que decompõe objetivos complexos em componentes informativos de Shapley e os agrega de forma não-linear para selecionar subconjuntos de alta qualidade.
4. Validação Empírica: Experimentos extensivos em conjuntos de dados padrão (regressão logística, KNN) e ajuste fino de modelos de linguagem em larga escala (BERT, Llama-2) demonstram que o NASH consistentemente supera o Data Shapley puro, outros semivalores e seleção aleatória.

Resultados

• Seleção Geral de Dados: Em configurações sem ruído injetado (qualidade homogênea), o Data Shapley puro frequentemente não performa melhor que o aleatório. O NASH aumenta substancialmente o desempenho nessas cenários, superando consistentemente as linhas de base em várias razões de seleção.
• Conjuntos de Dados com Qualidade Heterogênea: Em configurações com ruído de rótulo, o Data Shapley puro melhora (pois consegue distinguir dados ruins), mas o NASH ainda o supera consistentemente. Isso sugere que os benefícios do NASH (lidar com interações de papéis) são distintos e complementares à capacidade do Data Shapley de filtrar ruído.
• Compatibilidade: O NASH é compatível com vários semivalores (por exemplo, Beta Shapley, Data Banzhaf) e métodos eficientes de aproximação (por exemplo, amostragem MC, FreeShap), melhorando consistentemente seu desempenho de seleção.
• Robustez: O método é robusto à escolha do hiperparâmetro $\lambda$ na função de agregação e funciona efetivamente com diferentes funções de utilidade (por exemplo, perda de validação, MSE).

Significado

O artigo afirma que o NASH elimina em grande parte a restrição de que o Data Shapley/semivalores são eficazes apenas em conjuntos de dados limitados ou configurações específicas (por exemplo, aqueles com ruído injetado). Ao fornecer um framework que torna a seleção baseada em Shapley consistentemente confiável e robusta através de diversos conjuntos de dados e escalas de modelo, o NASH permite a adoção mais ampla de métodos principledos de valoração de dados. Este avanço apoia pesquisas futuras na melhoria da eficiência de aproximação e seleção de dados para modelos fundamentais, garantindo que os benefícios teóricos dos valores de Shapley (interação não míope e equidade) sejam realizados na prática.