Résumé technique : Quotient Semivalues pour l'attribution de données résistante aux fausses identités

1. Énoncé du problème

Les méthodes d'évaluation des données, telles que Data Shapley, sont conçues pour allouer des paiements et auditer la contribution des données d'entraînement aux pipelines d'apprentissage automatique. Cependant, ces méthodes supposent généralement un ensemble fixe de contributeurs passifs. Sur les marchés de données réels, les contributeurs sont des agents stratégiques capables de manipuler le mécanisme d'attribution pour gonfler leur part.

L'article identifie la manipulation par fausse identité comme un mode de défaillance critique. Un seul fournisseur latent peut :

• Diviser un jeu de données entre plusieurs identités pseudonymes (attaques Sybil).
• Dupliquer des exemples à haute valeur ou créer des quasi-doublons (paraphrases, augmentations, variantes synthétiques).
• Blanchir des variantes synthétiques pour exploiter l'ensemble de validation de l'évaluateur.

Le problème central est que l'attribution équitable Shapley standard sur les identités déclarées n'est pas compatible avec les incitations. Parce que la valeur des données est souvent non additive et complémentaire, diviser un jeu de données en plusieurs identités peut augmenter la somme des valeurs Shapley reçues par l'attaquant par rapport à la valeur reçue par une seule identité honnête.

2. Méthodologie

2.1 Modèle formel

Les auteurs formalisent le cadre comme un problème de conception de mécanisme sur les fournisseurs latents ($N$) et les identités soumises ($m$).

• Jeu de valeur des données : Un jeu monotone où la valeur d'une coalition est l'utilité de l'apprenant entraîné sur l'union des charges utiles de cette coalition.
• Classes de manipulation :
  • Division par fausse identité : Remplacer une identité par $k \ge 2$ identités détenant une partition ou une réplication des données originales.
  • Attaque par variante : Soumettre des copies transformées (doublons, paraphrases, données synthétiques) sous une ou plusieurs identités.
• Métrique de gain : Le gain additif ou multiplicatif qu'un attaquant réalise en manipulant la structure des identités par rapport à une déclaration honnête.

2.2 Résultat d'impossibilité

L'article démontre un théorème d'impossibilité fondamental : l'attribution exactement équitable Shapley sur les identités déclarées est incompatible avec une preuve absolue contre les fausses identités.
Même sur des jeux binaires et monotones (par exemple, des jeux d'unanimité), un fournisseur peut augmenter son paiement total en divisant ses données en plusieurs pseudonymes. Par exemple, dans un jeu d'unanimité à deux joueurs où $v(\{A, B\}) = 1$, le fournisseur $A$ reçoit $1/2$. Si $A$ se divise en $A_1, A_2$ de sorte que la valeur nécessite les trois ($A_1, A_2, B$), les nouvelles valeurs Shapley sont de $1/3$ chacune, ce qui donne un total de $2/3$ pour $A$. Cette vulnérabilité structurelle s'étend aux semi-valeurs générales (Banzhaf, Beta-Shapley), bien que l'ampleur du gain varie.

2.3 Le mécanisme de Quotient Semivalue

Pour résoudre ce problème, les auteurs proposent le mécanisme Quotient Semivalue, qui déplace l'unité stratégique des identités soumises brutes vers les clusters d'attribution étayés par des preuves.

1. Graphe de preuves et regroupement :
   • Une fonction de preuve $e_\theta(u, u')$ détermine si deux unités (exemples, documents) sont suffisamment similaires (basées sur des hachages, des plongements, une provenance, etc.) pour être traitées comme le même objet d'attribution.
   • Cela forme un graphe où les composantes connexes sont des clusters ($C_1, \dots, C_K$).
2. Opérateur de représentant de cluster ($R_\theta$) :
   • Pour prévenir la manipulation par duplication au sein du cluster (par exemple, soumettre 10 copies d'un exemple pour lui donner plus de poids), un opérateur de représentant canonique mappe chaque cluster vers un ensemble fixe d'unités d'entraînement canoniques.
   • Les stratégies incluent : l'effondrement des doublons exacts, la limitation du nombre d'unités par cluster, ou des unions normalisées par poids.
3. Jeu quotient :
   • Un nouveau jeu coopératif est construit où les joueurs sont les clusters, et non les identités.
   • La valeur d'une coalition de clusters est l'utilité de l'apprenant entraîné sur l'union de leurs représentants canoniques.
4. Calcul de la semi-valeur et allocation :
   • Les semi-valeurs (Shapley, Banzhaf, etc.) sont calculées sur le jeu quotient.
   • Allocation intra-cluster : Le paiement à un cluster est distribué parmi les identités soumises qui le composent. Le mécanisme nécessite une règle d'allocation neutre vis-à-vis des fausses identités (par exemple, une allocation proportionnelle au nombre d'unités canoniques contribué par chaque identité) pour garantir que la division d'une identité au sein d'un cluster n'augmente pas la part totale.

3. Contributions clés

1. Modèle formel : Un cadre rigoureux pour la manipulation par les fournisseurs de données impliquant des fournisseurs latents, des identités soumises et des attaques par transformation.
2. Théorème d'impossibilité : Preuve qu'aucun mécanisme ne peut être à la fois exactement équitable Shapley sur les identités déclarées et totalement résistant aux fausses identités.
3. Mécanisme de Quotient Semivalue : Une solution constructive qui calcule les semi-valeurs sur des clusters étayés par des preuves avec un opérateur de représentant canonique.
4. Garanties théoriques :
   • Preuve exacte contre les fausses identités : Atteinte sous des manipulations « stables par quotient » (où l'attaquant ne peut échapper à son cluster honnête ni altérer le représentant canonique) et une allocation neutre vis-à-vis des fausses identités.
   • Garanties approximatives : Bornes sur le gain de manipulation et la perte d'équité en termes de trois quantités mesurables : masse de cluster échappé (variantes formant de nouveaux clusters), erreur d'estimation de la valeur, et distance de regroupement (dérive du représentant).
5. DataMarket-Gym : Un nouveau benchmark pour évaluer les mécanismes d'attribution sous des attaques stratégiques de fournisseurs, couvrant les doublons exacts, les quasi-doublons, le blanchiment synthétique et la division Sybil.

4. Résultats expérimentaux

Les auteurs évaluent le mécanisme sur des jeux de données synthétiques et réels (CIFAR-10, AG News, STL-10, IMDB).

• Classification synthétique :
  • La valeur Shapley de base sur les identités brutes a montré un gain de manipulation de 1,74 sur les attaques par doublons/Sybil.
  • La valeur Shapley quotient avec des preuves au niveau de l'exemple (similarité cosinus $\theta=0,99$) a réduit ce gain à 0,96, neutralisant efficacement l'attaque et revenant à des niveaux quasi-honnêtes.
  • Le mécanisme est robuste au choix de la semi-valeur (Shapley, Banzhaf, Beta-Shapley).
• Sensibilité au seuil :
  • Le seuil cosinus $\theta$ est critique. Un seuil trop bas provoque des « fusions fausses » (fournisseurs indépendants regroupés), ce qui peut amplifier les gains Sybil. Un seuil trop élevé ne parvient pas à attraper les quasi-doublons.
  • L'article identifie un renversement de seuil spécifique au domaine :
    • Dans les domaines d'images (CIFAR-10), des normes élevées entraînent des similarités par paires élevées ; un seuil plus serré ($\theta \ge 0,90$) est requis pour prévenir les attaques par chaînage.
    • Dans les domaines textuels (AG News), les plongements normalisés par unité ont des similarités par paires plus faibles ; un seuil plus lâche ($\theta \le 0,90$) est optimal, car des seuils stricts échouent à relier les quasi-doublons.
  • Le seuil optimal est prévisible à partir des statistiques des plongements (p90 par paires et fraction de composante mixte de plancher de chaînage).
• Transfert réel :
  • Le mécanisme se transfère aux pipelines à caractéristiques figées (ResNet-18, MiniLM) sans accès à l'oracle, confirmant sa viabilité pratique.
  • Les attaques de division pure (données disjointes sans chevauchement) restent non défendues par la preuve de similarité seule, nécessitant une provenance non au niveau de l'exemple (par exemple, liaison de compte, KYC).

5. Signification et revendications

L'article affirme que l'attribution équitable des données Shapley n'est pas automatiquement compatible avec les incitations lorsque les identités sont endogènes. La signification de ce travail réside dans :

• Déplacement du fardeau stratégique : Le déplacement de l'unité d'attribution des identités modifiables vers des clusters étayés par des preuves permet un compromis contrôlé entre l'équité de style Shapley et la résistance aux Sybil.
• Possibilité conditionnelle : Bien que l'équité exacte Shapley soit impossible sous une manipulation non restreinte, le mécanisme quotient récupère un « compromis contrôlé » lorsque les signaux de similarité et de provenance peuvent fiablement effondrer les variantes manipulées dans la même unité.
• Déploiement pratique : Le mécanisme est « agnostique vis-à-vis de la semi-valeur », ce qui signifie qu'il peut être déployé avec divers backends d'évaluation (Shapley, Banzhaf, etc.) et est robuste au bruit de l'estimateur.
• Complémentarité : L'approche complète les travaux existants sur les « Valeurs Shapley de groupe fidèles » (qui défendent contre l'agrégation de jeux de données fixes par des sociétés écrans) en abordant la construction de l'unité d'attribution elle-même lorsque le contenu des données peut être altéré (dupliqué, paraphrasé, synthétisé).

Les auteurs concluent que l'unité d'attribution est un choix de conception de mécanisme, et que le quotient semivalue fournit un cadre robuste pour les marchés de données où les fournisseurs sont stratégiques.