Un nouveau cadre d’agrégation différentiellement privé – Google AI Weblog

Confidentialité différentielle Les algorithmes d’apprentissage automatique (DP) protègent les données des utilisateurs en limitant l’effet de chaque level de données sur une sortie agrégée avec une garantie mathématique. Intuitivement, la garantie implique que la modification de la contribution d’un seul utilisateur ne devrait pas modifier de manière significative la distribution de sortie de l’algorithme DP.

Cependant, les algorithmes DP ont tendance à être moins précis que leurs homologues non privés automobile satisfaire DP est un pire cas exigence : il faut ajouter du bruit pour « masquer » les changements dans n’importe quel potentiel level d’entrée, y compris les « factors peu probables » qui ont un influence significatif sur l’agrégation. Par exemple, supposons que nous voulions estimer en privé la moyenne d’un ensemble de données et que nous sachions qu’une sphère de diamètre, Λ, contient tous les factors de données possibles. La sensibilité de la moyenne à un seul level est bornée par Λ, et il suffit donc d’ajouter un bruit proportionnel à Λ à chaque coordonnée de la moyenne pour assurer DP.

Une sphère de diamètre Λ contenant tous les factors de données possibles.

Supposons maintenant que tous les factors de données sont « amicaux », ce qui signifie qu’ils sont proches les uns des autres, et que chacun affecte la moyenne d’au plus 𝑟, ce qui est beaucoup plus petit que Λ. Pourtant, la manière traditionnelle de garantir DP nécessite d’ajouter du bruit proportionnel à Λ pour tenir compte d’un ensemble de données voisin qui contient un level « inamical » supplémentaire qui est peu inclined d’être échantillonné.

Deux ensembles de données adjacents qui diffèrent par une seule valeur aberrante. Un algorithme DP devrait ajouter du bruit proportionnel à Λ à chaque coordonnée pour masquer cette valeur aberrante.

Dans « FriendlyCore : agrégation différentiellement privée pratique», présenté à ICML 2022, nous introduisons un cadre général pour le calcul des agrégations différentiellement privées. Le framework FriendlyCore prétraite les données, en extrayant un sous-ensemble « convivial » (le noyau) et en réduisant par conséquent l’erreur d’agrégation privée observée avec les algorithmes DP traditionnels. L’étape d’agrégation privée ajoute moins de bruit puisque nous n’avons pas besoin de tenir compte des factors hostiles qui ont un influence négatif sur l’agrégation.

Dans l’exemple de la moyenne, nous appliquons d’abord AmicalCore pour supprimer les valeurs aberrantes, et dans l’étape d’agrégation, nous ajoutons du bruit proportionnel à 𝑟 (pas Λ). Le défi consiste à rendre notre algorithme international (élimination des valeurs aberrantes + agrégation) différentiellement privé. Cela contraint notre schéma de suppression des valeurs aberrantes et stabilise l’algorithme de sorte que deux entrées adjacentes qui diffèrent d’un seul level (valeur aberrante ou non) produisent une sortie (amicale) avec des probabilités similaires.

Cadre FriendlyCore

Nous commençons par formaliser quand un jeu de données est considéré amical, qui dépend du kind d’agrégation nécessaire et doit capturer les ensembles de données pour lesquels la sensibilité de l’agrégat est faible. Par exemple, si l’agrégat fait la moyenne, le terme amical devrait capturer des ensembles de données avec un petit diamètre.

Pour faire abstraction de l’software particulière, nous définissons la convivialité à l’aide d’un prédicat 𝑓 qui est positif sur les factors 𝑥 et 𝑦 s’ils sont « proches » l’un de l’autre. Par exemple, dans l’software de calcul de moyenne, 𝑥 et 𝑦 sont proches si la distance qui les sépare est inférieure à 𝑟. Nous disons qu’un ensemble de données est amical (pour ce prédicat) si chaque paire de factors 𝑥 et 𝑦 sont tous deux proches d’un troisième level 𝑧 (pas nécessairement dans les données).

Une fois que nous avons fixé 𝑓 et défini quand un ensemble de données est convivial, il reste deux tâches. D’abord, nous construisons l’algorithme FriendlyCore qui extrait un grand sous-ensemble convivial (le noyau) de l’entrée de manière steady. AmicalCore est un filtre satisfaisant à deux exigences : (1) il doit supprimer les valeurs aberrantes pour ne conserver que les éléments proches de nombreux autres dans le noyau, et (2) pour les ensembles de données voisins qui diffèrent par un seul élément, 𝑦, le filtre génère chaque élément sauf 𝑦 avec presque la même probabilité. De plus, l’union des cœurs extraits de ces jeux de données voisins est conviviale.

L’idée sous-jacente AmicalCore est easy : la probabilité que nous ajoutions un level, 𝑥, au noyau est une fonction monotone et steady du nombre d’éléments proches de 𝑥. En particulier, si 𝑥 est proche de tous les autres factors, il n’est pas considéré comme une valeur aberrante et peut être conservé dans le noyau avec une probabilité de 1.

Dans un second temps, nous développons le DP amical algorithme qui satisfait une notion plus faible de confidentialité en ajoutant moins de bruit à l’agrégat. Cela signifie que les résultats de l’agrégation sont garantis similaires uniquement pour les ensembles de données voisins 𝐶 et 𝐶’ tels que le syndicat de 𝐶 et 𝐶’ est amical.

Notre théorème principal stipule que si nous appliquons un algorithme d’agrégation DP amical au noyau produit par un filtre avec les exigences énumérées ci-dessus, alors cette composition est différentiellement privée au sens régulier.

Clustering et autres functions

D’autres functions de notre méthode d’agrégation sont regroupement et apprendre le matrice de covariance d’un Distribution gaussienne. Envisagez l’utilisation de FriendlyCore pour développer un Algorithme de clustering k-means. Étant donné une base de données de factors, nous la divisons en sous-ensembles plus petits aléatoires de taille égale et exécutons un bon non-privé ok– signifie un algorithme de clustering sur chaque petit ensemble. Si l’ensemble de données d’origine contient ok grands clusters, chaque sous-ensemble plus petit contiendra une fraction significative de chacun de ces ok groupes. Il s’ensuit que les tuples (ensembles ordonnés) de ok-les centres que nous obtenons de l’algorithme non privé pour chaque petit sous-ensemble sont similaires. Cet ensemble de données de tuples devrait avoir un grand noyau convivial (pour une définition appropriée de la proximité).

Nous utilisons notre cadre pour agréger les tuples résultants de ok-centres (ok-uplets). Nous définissons deux tels ok-les tuples sont proches s’il existe une correspondance entre eux telle qu’un centre est sensiblement plus proche de son partenaire que de tout autre centre.

Dans cette picture, n’importe quelle paire de tuples rouge, bleu et vert est proche l’une de l’autre, mais aucune d’entre elles n’est proche du tuple rose. Ainsi, le tuple rose est supprimé par notre filtre et n’est pas dans le noyau.

Nous extrayons ensuite la carotte par notre schéma d’échantillonnage générique et l’agrégeons en suivant les étapes suivantes :

1. Choisissez un au hasard ok-uplet 𝑇 du noyau.
2. Partitionnez les données en plaçant chaque level dans un seau en fonction de son centre le plus proche en 𝑇.
3. Moyenne privée des factors dans chaque seau pour obtenir notre finale ok-centres.

résultats empiriques

Voici les résultats empiriques de nos algorithmes basés sur AmicalCore. Nous les avons mis en œuvre dans le Confidentialité différentielle sans focus (zCDP), qui améliore la précision de notre environnement (avec des garanties de confidentialité similaires à celles du plus connu (𝜖, 𝛿)-DP).

Faire la moyenne

Nous avons testé l’estimation moyenne de 800 échantillons d’une gaussienne sphérique avec une inconnu moyenne. Nous l’avons comparé à l’algorithme CoinPress. Contrairement à FriendlyCore, CoinPress nécessite une borne supérieure 𝑅 sur la norme de la moyenne. Les figures ci-dessous montrent l’effet sur la précision lors de l’augmentation de 𝑅 ou de la dimension 𝑑. Notre algorithme de moyennage fonctionne mieux sur les grandes valeurs de ces paramètres automobile il est indépendant de 𝑅 et 𝑑.

Regroupement

Nous avons testé les performances de notre algorithme de clustering privé pour ok-moyens. Nous l’avons comparé à la Chung et Kamath algorithme basé sur la récursivité hachage wise à la localité (LSH-clustering). Pour chaque expérience, nous avons effectué 30 répétitions et présenté les médianes avec les quantiles 0,1 et 0,9. A chaque répétition, on normalise les pertes par la perte de k-signifie++ (où un plus petit nombre est meilleur).

La determine de gauche ci-dessous examine ok-signifie des résultats sur un mélange uniforme de huit gaussiennes séparées en deux dimensions. Pour de petites valeurs de 𝑛 (le nombre d’échantillons du mélange), FriendlyCore échoue souvent et donne des résultats inexacts. Pourtant, augmenter 𝑛 augmente la probabilité de réussite de notre algorithme (automobile les tuples générés se rapprochent les uns des autres) et donne des résultats très précis, tandis que le clustering LSH est à la traîne.

Gauche: ok-signifie que les résultats sont 𝑑= 2 et ok= 8, pour faire varier 𝑛(nombre d’échantillons). Droite: Une illustration graphique des centres dans l’une des itérations pour 𝑛= 2 X 105. Les factors verts sont les centres de notre algorithme et les factors rouges sont les centres du clustering LSH.

FriendlyCore fonctionne également bien sur de grands ensembles de données, même sans séparation claire en clusters. Nous avons utilisé le Fonollosa et Huerta ensemble de données de capteurs de gaz contenant 8 tens of millions de lignes, composé d’un level à 16 dimensions défini par les mesures de 16 capteurs à un second donné. Nous avons comparé les algorithmes de clustering pour varier ok. FriendlyCore fonctionne bien sauf pour ok= 5 où il échoue en raison de l’instabilité de l’algorithme non privé utilisé par notre méthode (il existe deux options différentes pour ok= 5 avec un coût similaire qui fait échouer notre approche puisque nous n’obtenons pas un ensemble de tuples proches les uns des autres).

ok-signifie les résultats sur les mesures des capteurs de gaz dans le temps, variant ok.

Conclusion

AmicalCore est un cadre général pour filtrer les données métriques avant de les agréger en privé. Les données filtrées sont stables et rendent l’agrégation moins wise, ce qui nous permet d’augmenter sa précision avec DP. Nos algorithmes surpassent les algorithmes privés conçus pour la moyenne et le clustering, et nous pensons que cette approach peut être utile pour des tâches d’agrégation supplémentaires. Les premiers résultats montrent qu’il peut réduire efficacement la perte d’utilité lorsque nous déployons des agrégations DP. Pour en savoir plus et voir remark nous l’appliquons pour estimer la matrice de covariance d’une distribution gaussienne, consultez notre papier.

Remerciements

Ce travail a été mené par Eliad Tsfadia en collaboration avec Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, Avinatan Hassidim et Yossi Matias.