Google KI

In den letzten Jahren wurden Fortschritte bei datenschutzfreundlichen Ansätzen für den Umgang mit sensiblen Daten erzielt, z. B. bei der Gewinnung von Erkenntnissen über die menschliche Mobilität und durch den Einsatz von föderierten Analysen wie RAPPOR. Im Jahr 2019 haben wir eine Open-Source-Bibliothek veröffentlicht, die es Entwicklern und Organisationen ermöglicht, Techniken zu nutzen, die differenzielle Privatsphäre bieten, einen starken und weithin akzeptierten mathematischen Begriff der Privatsphäre. Die differenziell-private Datenanalyse ist ein prinzipieller Ansatz, der es Organisationen ermöglicht, aus der Masse ihrer Daten zu lernen und Erkenntnisse freizugeben, während gleichzeitig eine mathematische Garantie gegeben wird, dass diese Ergebnisse keine Unterscheidung oder Re-Identifizierung der Daten einzelner Nutzer zulassen.

In diesem Beitrag betrachten wir das folgende grundlegende Problem: Wie kann man aus einer Datenbank, die mehrere Attribute über Benutzer enthält, sinnvolle Benutzergruppen bilden und deren Merkmale verstehen? Wenn die vorliegende Datenbank sensible Benutzerattribute enthält, wie kann man dann diese Gruppenmerkmale aufdecken, ohne die Privatsphäre der einzelnen Benutzer zu gefährden?

Eine solche Aufgabe fällt unter den weit gefassten Begriff des Clustering, einem grundlegenden Baustein des unüberwachten maschinellen Lernens. Eine Clustering-Methode unterteilt die Datenpunkte in Gruppen und bietet eine Möglichkeit, jeden neuen Datenpunkt einer Gruppe zuzuordnen, der er am ähnlichsten ist. Der k-means Clustering-Algorithmus ist eine dieser einflussreichen Clustering-Methoden. Bei der Arbeit mit sensiblen Datensätzen kann er jedoch möglicherweise wichtige Informationen über einzelne Datenpunkte preisgeben und damit die Privatsphäre des jeweiligen Nutzers gefährden.

Heute stellen wir einen neuen, differentiell privaten Clustering-Algorithmus vor, der auf der privaten Generierung neuer repräsentativer Datenpunkte basiert und unsere Bibliothek für differentiellen Datenschutz ergänzt. Wir bewerten die Leistung dieses Algorithmus anhand mehrerer Datensätze und vergleichen ihn mit den bestehenden Basisverfahren, wobei wir eine konkurrenzfähige oder bessere Leistung feststellen.

K-means-Clustering

Bei einer Menge von Datenpunkten besteht das Ziel des k-means Clustering darin, (höchstens) k Punkte zu identifizieren, die als Clusterzentren bezeichnet werden, um den Verlust zu minimieren, der sich aus der Summe der quadratischen Abstände der Datenpunkte von ihrem nächsten Clusterzentrum ergibt. Dadurch wird die Menge der Datenpunkte in k Gruppen unterteilt. Darüber hinaus kann jeder neue Datenpunkt auf der Grundlage seines nächstgelegenen Clusterzentrums einer Gruppe zugewiesen werden. Die Freigabe der Clusterzentren kann jedoch Informationen über bestimmte Benutzer preisgeben – man denke beispielsweise an ein Szenario, in dem ein bestimmter Datenpunkt sehr weit vom Rest der Punkte entfernt ist, so dass der standardmäßige k-means Clustering-Algorithmus ein Clusterzentrum an diesem einzelnen Punkt zurückgibt und damit sensible Informationen über diesen einzelnen Punkt preisgibt. Um dieses Problem zu lösen, entwickeln wir einen neuen Algorithmus für das Clustering mit dem k-means-Ziel im Rahmen der differentiellen Privatsphäre.

Ein differenziell privater Algorithmus

In „Locally Private k-Means in One Round“, veröffentlicht auf der ICML 2021, haben wir einen differenziell privaten Algorithmus zum Clustern von Datenpunkten vorgestellt. Dieser Algorithmus hatte den Vorteil, dass er im lokalen Modell privat ist, bei dem die Privatsphäre des Benutzers sogar vor dem zentralen Server, der das Clustering durchführt, geschützt ist. Allerdings ist ein solcher Ansatz zwangsläufig mit einem wesentlich größeren Verlust verbunden als Ansätze, die Modelle der Privatsphäre verwenden, die das Vertrauen in einen zentralen Server erfordern.1

Hier stellen wir einen ähnlich inspirierten Clustering-Algorithmus vor, der nach dem zentralen Modell der differenziellen Privatsphäre arbeitet, bei dem dem zentralen Server vertraut wird, dass er vollständigen Zugriff auf die Rohdaten hat, und das Ziel darin besteht, differenziell private Clusterzentren zu berechnen, die keine Informationen über einzelne Datenpunkte preisgeben. Das zentrale Modell ist das Standardmodell für differentielle Privatsphäre, und Algorithmen im zentralen Modell können leichter anstelle ihrer nicht-privaten Gegenstücke eingesetzt werden, da sie keine Änderungen am Datenerfassungsprozess erfordern. Der Algorithmus geht so vor, dass er zunächst auf differenziell private Weise eine Kernmenge erzeugt, die aus gewichteten Punkten besteht, die die Datenpunkte gut „repräsentieren“. Anschließend wird ein beliebiger (nicht-privater) Clustering-Algorithmus (z. B. k-means++) auf dieser privat generierten Kernmenge ausgeführt.

Im Großen und Ganzen erzeugt der Algorithmus die private Kernmenge, indem er zunächst auf der Grundlage der Zufallsprojektion ein ortsabhängiges Hashing (LSH) in rekursiver Weise2 anwendet, um die Punkte in „Bereiche“ ähnlicher Punkte aufzuteilen, und dann jeden Bereich durch einen einzelnen gewichteten Punkt ersetzt, der den Durchschnitt der Punkte im Bereich darstellt, wobei das Gewicht der Anzahl der Punkte im gleichen Bereich entspricht. Wie bisher beschrieben, ist dieser Algorithmus jedoch nicht privat. Wir machen ihn privat, indem wir jede Operation auf eine private Art und Weise durchführen, indem wir Rauschen sowohl zu den Zählungen als auch zu den Durchschnittswerten der Punkte innerhalb eines Buckets hinzufügen.

Dieser Algorithmus erfüllt die Anforderungen an die differentielle Privatsphäre, da die Beiträge der einzelnen Punkte zu den Eimerzählungen und den Eimerdurchschnitten durch das hinzugefügte Rauschen maskiert werden, so dass das Verhalten des Algorithmus keine Informationen über einzelne Punkte preisgibt. Bei diesem Ansatz gibt es einen Kompromiss: Wenn die Anzahl der Punkte in den Eimern zu groß ist, werden einzelne Punkte nicht gut durch Punkte in der Kernmenge repräsentiert, während bei einer zu geringen Anzahl von Punkten in einem Eimer das hinzugefügte Rauschen (zu den Zählungen und Durchschnittswerten) im Vergleich zu den tatsächlichen Werten signifikant wird, was zu einer schlechten Qualität der Kernmenge führt. Dieser Kompromiss wird mit vom Benutzer bereitgestellten Parametern im Algorithmus realisiert, die die Anzahl der Punkte steuern, die in einem Bucket sein können.

Experimentelle Auswertung

Wir haben den Algorithmus anhand einiger Benchmark-Datensätze evaluiert und seine Leistung mit der des (nicht-privaten) k-means++-Algorithmus sowie einiger anderer Algorithmen mit verfügbaren Implementierungen verglichen, nämlich diffprivlib und dp-clustering-icml17. Wir verwenden die folgenden Benchmark-Datensätze: (i) ein synthetischer Datensatz, der aus 100.000 Datenpunkten in 100 Dimensionen besteht, die aus einer Mischung von 64 Gaußschen Kurven abgetastet wurden; (ii) neuronale Repräsentationen für den MNIST-Datensatz über handgeschriebene Ziffern, die durch Training eines LeNet-Modells gewonnen wurden; (iii) der UC Irvine-Datensatz über Buchstabenerkennung; und (iv) der UC Irvine-Datensatz über CO- und NOx-Emissionen von Gasturbinen.3

Wir analysieren den normalisierten k-means-Verlust (mittlerer quadratischer Abstand zwischen Datenpunkten und dem nächstgelegenen Zentrum), während wir die Anzahl der Zielzentren (k) für diese Benchmark-Datensätze variieren.4 Der beschriebene Algorithmus erreicht in drei der vier betrachteten Datensätze einen geringeren Verlust als die anderen privaten Algorithmen.

Speichere in deinen Favoriten diesen permalink.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.