Resumo Técnico: Semivalores Quociente para Atribuição de Dados Resistente a Falsas Identidades

1. Declaração do Problema

Métodos de valoração de dados, como o Data Shapley, são projetados para alocar pagamentos e auditar a contribuição dos dados de treinamento para pipelines de aprendizado de máquina. No entanto, esses métodos geralmente assumem um conjunto fixo de contribuidores passivos. Em mercados de dados do mundo real, os contribuidores são agentes estratégicos que podem manipular o mecanismo de atribuição para inflar sua participação.

O artigo identifica a manipulação por falsa identidade como um modo de falha crítico. Um único provedor latente pode:

• Dividir um conjunto de dados entre múltiplas identidades pseudônimas (ataques Sybil).
• Duplicar exemplos de alto valor ou criar quase-duplicatas (paráfrases, ampliações, variantes sintéticas).
• Branquear variantes sintéticas para explorar o conjunto de validação do avaliador.

A questão central é que a atribuição justa baseada em Shapley padrão sobre identidades reportadas não é compatível com incentivos. Como o valor dos dados é frequentemente não aditivo e complementar, dividir um conjunto de dados em múltiplas identidades pode aumentar a soma dos valores de Shapley recebidos pelo atacante em comparação com o valor recebido por uma única identidade honesta.

2. Metodologia

2.1 Modelo Formal

Os autores formalizam o cenário como um problema de design de mecanismos sobre provedores latentes ($N$) e identidades submetidas ($m$).

• Jogo de Valor de Dados: Um jogo monotônico onde o valor de uma coalizão é a utilidade do aprendiz treinado na união das cargas úteis dessa coalizão.
• Classes de Manipulação:
  • Divisão por falsa identidade: Substituir uma identidade por $k \ge 2$ identidades que detêm uma partição ou replicação dos dados originais.
  • Ataque por variante: Submeter cópias transformadas (duplicatas, paráfrases, dados sintéticos) sob uma ou mais identidades.
• Métrica de Ganho: O ganho aditivo ou multiplicativo que um atacante obtém ao manipular a estrutura de identidade em comparação com o reporte honesto.

2.2 Resultado de Impossibilidade

O artigo prova um teorema fundamental de impossibilidade: A atribuição exatamente justa segundo Shapley sobre identidades reportadas é incompatível com a prova irrestrita contra falsas identidades.
Mesmo em jogos de valor binário e monotônicos (por exemplo, jogos de unanimidade), um provedor pode aumentar seu pagamento total dividindo seus dados em múltiplos pseudônimos. Por exemplo, em um jogo de unanimidade de dois jogadores onde $v(\{A, B\}) = 1$, o provedor $A$ recebe $1/2$. Se $A$ se dividir em $A_1, A_2$ de modo que o valor exija todos os três ($A_1, A_2, B$), os novos valores de Shapley são $1/3$ cada, resultando em um total de $2/3$ para $A$. Essa vulnerabilidade estrutural estende-se a semivalores gerais (Banzhaf, Beta-Shapley), embora a magnitude do ganho varie.

2.3 O Mecanismo de Semivalor Quociente

Para resolver isso, os autores propõem o mecanismo de Semivalor Quociente, que desloca a unidade estratégica de identidades submetidas brutas para clusters de atribuição respaldados por evidências.

1. Grafo de Evidências e Agrupamento:
   • Uma função de evidência $e_\theta(u, u')$ determina se duas unidades (exemplos, documentos) são suficientemente similares (com base em hashes, embeddings, proveniência, etc.) para serem tratadas como o mesmo objeto de atribuição.
   • Isso forma um grafo onde os componentes conectados são clusters ($C_1, \dots, C_K$).
2. Operador Representante do Cluster ($R_\theta$):
   • Para prevenir a manipulação via duplicação dentro do cluster (por exemplo, submeter 10 cópias de um exemplo para ponderá-lo mais alto), um operador representante canônico mapeia cada cluster para um conjunto fixo de unidades de treinamento canônicas.
   • Estratégias incluem: colapso de duplicatas exatas, limitação do número de unidades por cluster ou uniões normalizadas por peso.
3. Jogo Quociente:
   • Um novo jogo cooperativo é construído onde os jogadores são os clusters, e não as identidades.
   • O valor de uma coalizão de clusters é a utilidade do aprendiz treinado na união de seus representantes canônicos.
4. Cálculo do Semivalor e Alocação:
   • Semivalores (Shapley, Banzhaf, etc.) são calculados sobre o jogo quociente.
   • Alocação Dentro do Cluster: O pagamento a um cluster é distribuído entre as identidades submetidas dentro dele. O mecanismo exige uma regra de alocação neutra a falsas identidades (por exemplo, alocação proporcional à contagem de unidades canônicas contribuídas por cada identidade) para garantir que a divisão de uma identidade dentro de um cluster não aumente a participação total.

3. Contribuições Principais

1. Modelo Formal: Uma estrutura rigorosa para manipulação de provedores de dados envolvendo provedores latentes, identidades submetidas e ataques de transformação.
2. Teorema de Impossibilidade: Prova de que nenhum mecanismo pode ser simultaneamente exatamente justo segundo Shapley sobre identidades reportadas e irrestritamente à prova de falsas identidades.
3. Mecanismo de Semivalor Quociente: Uma solução construtiva que calcula semivalores sobre clusters respaldados por evidências com um operador representante canônico.
4. Garantias Teóricas:
   • Prova Exata contra Falsas Identidades: Alcançada sob manipulações "estáveis ao quociente" (onde o atacante não pode escapar de seu cluster honesto ou alterar o representante canônico) e alocação neutra a falsas identidades.
   • Garantias Aproximadas: Limites sobre o ganho de manipulação e a perda de justiça em termos de três quantidades mensuráveis: massa de cluster escapado (variantes que formam novos clusters), erro de estimação de valor e distância de agrupamento (desvio no representante).
5. DataMarket-Gym: Um novo benchmark para avaliar mecanismos de atribuição sob ataques estratégicos de provedores, cobrindo duplicatas exatas, quase-duplicatas, branqueamento sintético e divisão Sybil.

4. Resultados Experimentais

Os autores avaliam o mecanismo em conjuntos de dados sintéticos e do mundo real (CIFAR-10, AG News, STL-10, IMDB).

• Classificação Sintética:
  • O Shapley de base sobre identidades brutas mostrou um ganho de manipulação de 1,74 em ataques de duplicata/Sybil.
  • O Shapley Quociente com evidência ao nível de exemplo (similaridade de cosseno $\theta=0,99$) reduziu esse ganho para 0,96, neutralizando efetivamente o ataque e retornando a níveis quase honestos.
  • O mecanismo é robusto à escolha do semivalor (Shapley, Banzhaf, Beta-Shapley).
• Sensibilidade ao Limiar:
  • O limiar de cosseno $\theta$ é crítico. Um limiar muito baixo causa "fusões falsas" (provedores independentes agrupados juntos), o que pode amplificar ganhos Sybil. Um limiar muito alto falha em pegar quase-duplicatas.
  • O artigo identifica uma reversão de limiar específica de domínio:
    • Em domínios de imagem (CIFAR-10), normas altas levam a altas similaridades pareadas; um limiar mais apertado ($\theta \ge 0,90$) é necessário para prevenir ataques de cadeia.
    • Em domínios de texto (AG News), embeddings normalizados por unidade têm similaridades pareadas mais baixas; um limiar mais solto ($\theta \le 0,90$) é ótimo, pois limiares estritos falham em vincular quase-duplicatas.
  • O limiar ótimo é previsível a partir de estatísticas de embedding (p90 pareado e fração de componente misto de piso de cadeia).
• Transferência para o Mundo Real:
  • O mecanismo transfere-se para pipelines de características congeladas (ResNet-18, MiniLM) sem acesso a oráculo, confirmando sua viabilidade prática.
  • Ataques de divisão pura (dados disjuntos sem sobreposição) permanecem indefesos apenas por evidência de similaridade, exigindo proveniência não ao nível de exemplo (por exemplo, vinculação de conta, KYC).

5. Significado e Alegações

O artigo alega que a atribuição de dados justa segundo Shapley não é automaticamente compatível com incentivos quando as identidades são endógenas. O significado do trabalho reside em:

• Deslocamento do Fardo Estratégico: Mover a unidade de atribuição de identidades mutáveis para clusters respaldados por evidências permite uma troca controlada entre justiça ao estilo Shapley e resistência a Sybil.
• Possibilidade Condicional: Embora a justiça exata segundo Shapley seja impossível sob manipulação irrestrita, o mecanismo quociente recupera uma "troca controlada" quando sinais de similaridade e proveniência podem confiavelmente colapsar variantes manipuladas na mesma unidade.
• Implantação Prática: O mecanismo é "agnóstico ao semivalor", o que significa que pode ser implantado com vários backends de valoração (Shapley, Banzhaf, etc.) e é robusto ao ruído do estimador.
• Complementaridade: A abordagem complementa o trabalho existente sobre "Valores de Shapley de Grupo Fiéis" (que defende contra a agregação de empresas de fachada de conjuntos de dados fixos) ao abordar a construção da própria unidade de atribuição quando o conteúdo dos dados pode ser alterado (duplicado, parafraseado, sintetizado).

Os autores concluem que a unidade de atribuição é uma escolha de design de mecanismo, e o semivalor quociente fornece uma estrutura robusta para mercados de dados onde os provedores são estratégicos.