Was ist mit "Laplace-Lärm" gemeint?

9

Ich schreibe derzeit einen Algorithmus für differenzielle Privatsphäre unter Verwendung des Laplace-Mechanismus.

Leider habe ich keinen statistischen Hintergrund, daher sind mir viele Begriffe unbekannt. Jetzt stolpere ich über den Begriff: Laplace-Lärm . Um ein Dataset-Differential privat zu machen, sprechen alle Papiere nur über das Hinzufügen von Laplace-Rauschen gemäß der Laplace-Verteilung zu den Funktionswerten.

k(X)=f(X)+Y(X)

(k ist der private Differenzwert, f der von der Bewertungsfunktion zurückgegebene Wert und Y das Laplace-Rauschen)

Bedeutet dies, dass ich Zufallsvariablen aus der Laplace-Verteilung gemäß dieser Funktion aus Wikipedia https://en.wikipedia.org/wiki/Laplace_distribution erstelle ?

Y=μb sgn(U)ln(12|U|)

UPDATE: Ich habe bis zu 100 Zufallsvariablen aus der obigen Funktion gezeichnet, aber dies gibt mir keine Laplace-Verteilung (nicht einmal in der Nähe). Aber ich denke, es sollte eine Laplace-Distribution modellieren.

UPDATE2:

Das sind die Definitionen, die ich habe:

(Der Laplace-Mechanismus). Bei jeder Funktion f:N|X|Rk ist der Laplace-Mechanismus definiert als: ML(x,f(·),ϵ)=f(x)+(Y1,...,Yk) wobei Y iid Zufallsvariablen sind, die aus Lap(f/ϵ)

Ebenso gut wie:

Um Y (X) zu erzeugen, wird häufig eine Laplace-Verteilung mit dem Mittelwert Null und dem Skalenparameter Δ (f) / ε verwendet

Lotte
quelle
Die zweite Gleichung, die Sie haben, ist die CDF und nicht die PDF. Sie möchten aus dem PDF probieren. Hier ist ein Python-Code aus der Laplace-Distribution ( biexponential ) ( docs.scipy.org/doc/numpy-1.9.3/reference/generated/… )
Luca
1
Können Sie die genaue Referenz angeben, die das "Laplace-Rauschen" erwähnt? Ich denke, dass sie bedeuten, rv Y zu X hinzuzufügen, wobei Y der Laplace-Verteilung folgt. Was Ihr Update betrifft, funktioniert diese Methode - Sie müssen einen Fehler in Ihrem Code gemacht haben, oder es ist nur die Tatsache, dass Sie nur 100 Draws daraus gemacht haben, wenn Sie 5000 oder mehr versuchen, würde es wahrscheinlich mehr aussehen. " Laplace "...
Tim
Ich denke, meine Handlung sieht tatsächlich eher wie eine CDF aus, ich habe sie oben hinzugefügt, sowie meinen Code. Hier sind die Links zu den Zitaten: 1 2
Lotte
Ich habe auch den Code gesehen, den ich zuvor verwendet habe, und ich weiß nicht, warum er mir ein solches Ergebnis liefert. Die Darstellung zeigt meinen Code, der 1000-mal für f = 1 und eps = 1 wiederholt wurde. Aber ich denke, mein Hauptpunkt ist, wenn ich "Laplace-Rauschen" richtig verstanden habe. Den Code kann ich irgendwie trainieren.
Lotte

Antworten:

14

Sie haben Recht. Wenn Sie Laplace-Rauschen hinzufügen, bedeutet dies, dass Sie Ihrer Variablen die Variable hinzufügen , die der Laplace-Verteilung folgt . Es gibt mehrere Gründe, warum es als Rauschen bezeichnet wird . Stellen Sie sich zunächst die Signalverarbeitung vor, bei der die Nachricht über einen Kanal gesendet wird und das empfangene Signal aufgrund der Unvollkommenheit des Kanals verrauscht ist. Sie müssen also das Signal vom Rauschen isolieren. Zweitens sprechen wir in der Kryptographie auch über pseudozufälliges Rauschen, und die unterschiedliche Privatsphäre hängt mit der Kryptographie zusammen. Drittens können wir in Statistik und maschinellem Lernen auch über statistisches Rauschen sprechen . Statistische Modelle enthalten Rauschen oder Fehlerbegriffe usw. (es gibt sogar ein Buch über die Vorhersage von NamenXYSignal und Rauschen von Nate Silver). Deshalb verwenden wir Rauschen als genaueres Synonym für mehrdeutige Zufälligkeit .

In Bezug auf die Zufallsgenerierung gibt es eine Reihe von Möglichkeiten, wie Sie nach der Laplace-Verteilung Zufallswerte zeichnen können, zum Beispiel:

  1. Die in Wikipedia beschriebene inverse Transformationsmethode :
f <- function(n) {
   u <- runif(n, -0.5, 0.5)
   sign(u)*log(1-2*abs(u))
}
  1. Wenn und sind unabhängige Zufallsvariablen folgende Exponentialverteilung, dann folgt Laplace - Verteilung :V Y = U - V.UVY=UV
g <- function(n) { rexp(n)-rexp(n) }
  1. Wenn der Laplace-Verteilung folgt, dannfolgt der Exponentialverteilung , also:| Y |Y|Y|
h <- function(n) { rexp(n)*sample(c(-1,1), n, replace = TRUE) }

In den folgenden Darstellungen sehen Sie die Verteilung von Proben, die mit jeder der Funktionen mit der zugehörigen Laplace-Dichte (rote Linie) gezogen wurden.105

Geben Sie hier die Bildbeschreibung ein

Um die Beispiele zu vereinfachen, verwende ich die Standard-Laplace-Verteilung mit scale = 1, aber Sie können die Ergebnisse leicht ändern, indem Sie die Ergebnisse mit verschiedenen Skalierungsfaktoren multiplizieren.

Tim
quelle
Vielen Dank! Das beantwortet meine Frage, ich war nur sehr verwirrt über den Begriff "Lärm" und konnte keine richtige Erklärung finden.
Lotte
Ich habe das Histogramm für meinen Code gezeichnet und es sieht gut aus :)
Lotte
2

Die Laplace- oder doppelte Exponentialverteilung fällt um einen Mittelwert exponentiell nach links und rechts ab. Es ist im Grunde das Exponential, das auf die andere Seite gespiegelt wird.

  • Wenn Sie die Wahrscheinlichkeit möchten, verwenden Sie die Wahrscheinlichkeit des Exponentials und fügen Sie dem beobachteten Wert ein abs () hinzu. Die logarithmische Wahrscheinlichkeit ist einfach die abs () der Residuen, multipliziert mit der Rate des Exponentials.

  • Zum Abtasten ist es am einfachsten, aus -1,1 zu zeichnen und mit einem Zug aus der Exponentialverteilung zu multiplizieren, die in den meisten Programmiersprachen verfügbar ist. Wie oben erwähnt, finden Sie alternativ auch direkte Implementierungen des Laplace, für die jedoch möglicherweise etwas mehr Suche erforderlich ist.

Florian Hartig
quelle