Structure Selection for Fairness-Constrained Differentially Private Data Synthesis

Ce papier présente PrivCI, une méthode de synthèse de données différentiellement privée qui intègre des contraintes d'indépendance conditionnelle dans une étape de mesure basée sur un arbre couvrant minimal pour éliminer les biais tout en préservant la fidélité des données.

L'essentiel

Imaginez que vous voulez partager une recette de cuisine secrète avec le monde entier, mais vous avez deux règles strictes à respecter :

1. La règle du secret (Confidentialité) : Vous ne devez révéler aucun détail qui permettrait d'identifier qui a apporté quel ingrédient spécifique.
2. La règle de l'équité (Justice) : Vous ne voulez pas que la recette suggère que certaines personnes (par exemple, celles qui habitent dans un quartier spécifique) sont moins capables de cuisiner que d'autres, simplement à cause de leur adresse.

C'est exactement le défi que rencontrent les scientifiques des données aujourd'hui. Ils veulent créer des données synthétiques (des données factices qui ressemblent aux vraies) pour que les chercheurs puissent travailler sans risquer la vie privée des gens. Mais souvent, ces données factices reproduisent les préjugés cachés des données originales.

Voici une explication simple du papier de recherche PrivCI, présenté par Naeim Ghahramanpour et Mostafa Milani.

1. Le Problème : Le "Miroir" qui déforme la réalité

Imaginez que vous avez un grand miroir (vos données réelles) qui reflète la société. Ce miroir est un peu sale : il y a des taches de café (les biais historiques) qui disent, par exemple, "Les gens du groupe A réussissent moins bien que le groupe B".

Si vous utilisez un outil standard pour copier ce miroir (créer des données synthétiques) tout en protégeant la vie privée, l'outil va copier tout, y compris les taches de café. Résultat : vous obtenez un nouveau miroir qui est privé, mais qui est toujours injuste.

Les chercheurs disent : "Attendez ! Nous savons que la réussite ne devrait dépendre que des compétences (les ingrédients), pas du quartier (l'adresse). Nous devons nettoyer le miroir pendant qu'on le copie, pas après."

2. La Solution : PrivCI (Le Chef d'Orchestre Intelligent)

Les auteurs proposent un nouvel outil appelé PrivCI. Pour comprendre comment il fonctionne, utilisons une analogie de construction.

L'ancienne méthode (MST) : Le Constructeur de Ponts

Imaginez que vous devez construire un réseau de ponts entre des îles (les différentes données comme l'âge, le salaire, le genre, etc.).

• L'objectif est de relier les îles les plus proches les unes des autres pour créer un réseau efficace.
• L'outil standard choisit les ponts les plus courts pour gagner du temps et de l'énergie.
• Le problème : Il ne regarde pas si un pont relie une île "Genre" à une île "Salaire" d'une manière injuste. Il construit juste le réseau le plus logique statistiquement.

La nouvelle méthode (PrivCI) : Le Constructeur avec Règles

PrivCI est comme un architecte qui a une règle d'or dans sa poche : "Aucun pont ne doit relier directement l'île 'Genre' à l'île 'Salaire' sauf si le pont passe par l'île 'Diplôme'."

En termes simples :

• Si le diplôme explique pourquoi le salaire est élevé, c'est normal.
• Mais si le genre influence le salaire sans passer par le diplôme, c'est du biais, et ce pont est interdit.

3. Comment ça marche ? (L'Analogie du Tri Sélectif)

Le processus se déroule en deux étapes principales, comme un tri sélectif intelligent :

1. L'Étape de Mesure (Le Tri) : Au lieu de regarder toutes les données en même temps, l'outil regarde les liens entre les variables. Mais avant de choisir un lien (un pont), il vérifie : "Si je construis ce pont, est-ce que je vais créer un chemin interdit entre le Genre et le Salaire ?"

   • Si oui : Non, c'est interdit ! On ne le construit pas.
   • Si non : OK, on peut le construire.

2. L'Étape de Reconstruction (La Cuisine) : Une fois que l'architecte a choisi les ponts autorisés, il utilise ces ponts pour recréer une nouvelle version des données. Comme il a éliminé les ponts injustes dès le début, la nouvelle cuisine (les données synthétiques) est à la fois privée et équitable.

4. Pourquoi est-ce mieux que les autres ?

Les chercheurs ont comparé leur méthode (PrivCI) à une méthode précédente (PreFair).

• L'ancienne méthode (PreFair) était un peu comme un jardinier qui coupe toutes les branches d'un arbre avant de commencer, par peur de faire une erreur. C'est sûr, mais l'arbre peut devenir moche et perdre beaucoup de ses fruits (les données deviennent moins précises).
• La nouvelle méthode (PrivCI) est comme un jardinier expert qui coupe seulement les branches précises qui posent problème, tout en gardant le reste de l'arbre intact.

Le résultat ?
Grâce à cette approche plus fine :

• Les données synthétiques sont plus précises (elles ressemblent mieux à la réalité).
• Les modèles d'intelligence artificielle qui utilisent ces données fonctionnent mieux.
• Et surtout, l'injustice est toujours éliminée, car les liens interdits n'ont jamais été construits.

En Résumé

PrivCI est une nouvelle façon de créer des données factices pour l'IA. Au lieu de créer des données et d'essayer de les "réparer" ensuite (ce qui gâche souvent la qualité), cet outil intègre la justice dès la conception.

C'est comme si vous construisiez une maison : au lieu de construire une maison avec des murs de travers et de devoir les redresser plus tard (ce qui affaiblit la structure), vous utilisez un niveau à bulle dès le premier coup de marteau pour vous assurer que tout est droit, solide et équitable, tout en gardant les plans secrets.

C'est une victoire pour la vie privée (les données sont protégées), pour la justice (pas de discrimination) et pour l'efficacité (les données sont plus utiles pour les chercheurs).

Résumé technique

1. Problématique

La génération de données synthétiques sous Différentielle Privée (DP) est devenue une méthode standard pour publier des données tout en garantissant la confidentialité des individus. Cependant, une limitation majeure de cette approche réside dans le fait que les synthétiseurs standards préservent la structure statistique complète des données originales, y compris les corrélations spurious (fausses corrélations) entre les attributs sensibles (ex. : genre, race) et les résultats (ex. : embauche, crédit).

Dans des contextes critiques pour l'équité, ces corrélations peuvent perpétuer des biais historiques ou discriminatoires. Le défi technique est le suivant : comment générer des données synthétiques qui respectent à la fois la Différentielle Privée et des contraintes d'Équité spécifiques, sans gaspiller le budget de confidentialité ni dégrader l'utilité des données ?

L'approche actuelle consiste souvent à appliquer des réparations a posteriori (après la synthèse), ce qui est sous-optimal car cela ignore les distorsions introduites par le bruit de la DP ou gaspille le budget en préservant des dépendances qui seront ensuite supprimées.

2. Méthodologie : PrivCI

Les auteurs proposent PrivCI, un cadre de synthèse de données qui intègre les contraintes d'indépendance conditionnelle (CI) directement dans la phase de mesure (étape de sélection de la structure), plutôt que dans la phase de reconstruction.

A. Formalisation de l'Équité

Le problème est formalisé par une partition des attributs en quatre catégories :

• S : Attributs protégés (sensibles).
• O : Attributs de résultat (outcome).
• A : Attributs admissibles (facteurs légitimes justifiant une dépendance, ex. : qualifications).
• I : Attributs inadmissibles (facteurs de discrimination).

La contrainte d'équité est exprimée comme une Indépendance Conditionnelle (CI) : $O \perp S \mid A$. Cela signifie que, une fois les facteurs admissibles ($A$) pris en compte, le résultat ($O$) doit être statistiquement indépendant de l'attribut protégé ($S$). Graphiquement, cela impose que tout chemin reliant un nœud de $S$ à un nœud de $O$ dans le modèle de dépendance doive passer par au moins un nœud de $A$.

B. Algorithme PrivCI

PrivCI modifie le pipeline standard de synthèse DP en deux étapes (Mesure + Reconstruction) :

1. Phase de Mesure (Sélection de structure) :

   • L'algorithme utilise une variante de l'algorithme de Kruskal pour construire un Arbre Couvrant Maximum (MST) basé sur des scores de dépendance (mesurés de manière privée).
   • Innovation clé : À chaque itération, lors de la sélection d'une arête candidate via le mécanisme exponentiel, un filtre de faisabilité est appliqué. Une arête n'est considérée que si son ajout :
     1. Préserve l'acyclicité du graphe.
     2. Ne crée aucun chemin entre $S$ et $O$ dans le graphe induit par $V \setminus A$ (c'est-à-dire que $A$ sépare toujours $S$ et $O$).
   • Cela garantit que la structure apprise respecte intrinsèquement la contrainte CI.

2. Phase de Reconstruction :

   • Une fois l'arbre de dépendance sélectionné, les marginales 2D correspondantes sont mesurées avec du bruit (mécanisme gaussien).
   • Le module PrivatePGM est utilisé pour reconstruire une distribution jointe cohérente avec ces marginales bruyantes et générer les données synthétiques.

Cette approche conserve les propriétés de composition du budget de confidentialité du pipeline MST standard, tout en intégrant la contrainte d'équité dès le début du processus.

3. Contributions Clés

• Intégration structurelle de l'équité : Contrairement aux méthodes de réparation a posteriori, PrivCI impose les contraintes d'indépendance conditionnelle directement lors de la sélection des dépendances, optimisant ainsi l'utilisation du budget de confidentialité.
• Algorithme de sélection d'arêtes contraint : Développement d'un algorithme glouton (basé sur Kruskal) qui intègre des vérifications de faisabilité CI sous le mécanisme exponentiel, assurant que la structure apprise satisfait $O \perp S \mid A$.
• Meilleur compromis Utilité-Équité : La méthode démontre qu'il est possible d'améliorer la fidélité des données et la performance des modèles en aval tout en respectant strictement les contraintes d'équité, surpassant les approches précédentes qui éliminent arbitrairement des arêtes avant la construction.

4. Résultats Expérimentaux

Les auteurs ont évalué PrivCI sur cinq jeux de données de référence (Adult, COMPAS, Dutch Census, German Credit, Law School) et l'ont comparé à PreFair (l'état de l'art le plus proche) et à MST (sans contrainte d'équité).

• Fidélité Distributionnelle et Utilité :

  • PrivCI obtient des scores de fidélité (mesurés par la divergence KL et la distance TV) supérieurs à PreFair sur la plupart des jeux de données.
  • La performance prédictive en aval (AUC des modèles logistiques) est significativement meilleure avec PrivCI, en particulier sur les jeux de données COMPAS et Law School.
  • PrivCI sélectionne des arbres avec un score total de dépendance (proxy MI) plus élevé que PreFair, indiquant qu'il conserve plus d'informations utiles tout en respectant l'équité.

• Respect de l'Équité :

  • CMI (Information Mutuelle Conditionnelle) : PrivCI réduit efficacement la dépendance entre $S$ et $O$ conditionnellement à $A$, atteignant des niveaux de CMI comparables à PreFair (statistiquement indiscernables dans la plupart des cas), prouvant que la contrainte structurelle est respectée.
  • Equalized Odds (EO) : Les deux méthodes améliorent l'équité par rapport au MST non contraint, bien que les gains varient selon les jeux de données.

• Analyse Statistique :

  • Des tests de Wilcoxon appariés confirment que les améliorations de PrivCI en termes de fidélité (KL, TV) et de performance (AUC) sont statistiquement significatives par rapport à PreFair sur plusieurs jeux de données.

5. Signification et Conclusion

Ce travail démontre que l'imposition de contraintes structurelles d'équité pendant la phase de mesure (et non après) permet d'obtenir un meilleur compromis entre confidentialité, utilité et équité.

• Efficacité du Budget Privé : En évitant de préserver des dépendances interdites pour les corriger plus tard, PrivCI économise le budget de confidentialité pour préserver des dépendances légitimes.
• Supériorité sur l'État de l'Art : PrivCI surpasse PreFair en évitant la suppression prématurée d'arêtes potentiellement utiles, permettant une sélection plus fine des structures de dépendance admissibles.
• Impact : Cette approche offre une voie prometteuse pour la publication de données synthétiques dans des domaines réglementés (finance, santé, justice), où la conformité aux lois sur l'équité est aussi cruciale que la protection de la vie privée.

Les auteurs suggèrent comme travaux futurs l'extension de cette méthode à des contraintes CI multiples ou chevauchantes, et son application à des modèles génératifs profonds sous DP.