Co oznacza „hałas Laplace'a”?

9

Obecnie piszę algorytm różnicowej prywatności za pomocą mechanizmu Laplace'a.

Niestety nie mam doświadczenia w statystyce, dlatego wiele terminów jest mi nieznanych. Więc teraz potykam się o termin: hałas Laplace'a . Aby ustawić różnicowanie zbioru danych jako prywatne, wszystkie artykuły mówią tylko o dodaniu szumu Laplace'a zgodnie z rozkładem Laplace'a do wartości funkcji.

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

(k jest różnicową wartością prywatną, f zwróconą wartością przez funkcję oceny, a Y hałasem Laplace'a)

Czy to oznacza, że ​​tworzę losowe zmienne z rozkładu Laplace'a zgodnie z tą funkcją, którą mam z wikipedii https://en.wikipedia.org/wiki/Laplace_distribution ?

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

AKTUALIZACJA: Narysowałem do 100 losowych zmiennych narysowanych z powyższej funkcji, ale to nie daje mi rozkładu Laplace'a (nawet bliskiego). Ale myślę, że powinien modelować rozkład Laplace'a.

AKTUALIZACJA 2:

Oto moje definicje:

(Mechanizm Laplace'a). Biorąc pod uwagę dowolną funkcję f:N|X|Rk , mechanizm Laplace'a jest zdefiniowany jako: ML(x,f(·),ϵ)=f(x)+(Y1,...,Yk) gdzie Y są zmiennymi losowymi iid pochodzącymi z Lap(f/ϵ)

Jak również:

Aby wygenerować Y (X), powszechnym wyborem jest użycie rozkładu Laplace'a ze średnią zero i parametrem skali Δ (f) / ε

Lotte
źródło
Drugie równanie, które masz, to CDF zamiast PDF. Chcesz próbkować z pliku PDF. Oto kod Pythona do pobrania z dystrybucji Laplace'a (biexponential) ( docs.scipy.org/doc/numpy-1.9.3/reference/generated/… )
Luca
1
Czy możesz podać dokładne odniesienie, które wspomina o „hałasie Laplace'a”? Myślę, że mają na myśli dodanie rv Y do X, gdzie Y następuje po rozkładzie Laplace'a. Jako o swoim aktualizacji, metoda ta ma pracę - muszą dokonaniu błąd w kodzie, czy jest to po prostu fakt, że wykonane tylko 100 czerpie z niego, jeśli próbuje 5000 lub więcej myślę, że to zacząć szukać więcej " Laplace "...
Tim
Myślę, że moja fabuła wygląda bardziej jak CDF, dodałem ją powyżej, a także mój kod. Oto linki do cytatów: 1 2
Lotte
Widziałem też kod, którego używam wcześniej i nie wiem, dlaczego daje mi to taki wynik. Wykres pokazuje mój kod, zapętlony 1000 razy dla f = 1 i eps = 1. Myślę jednak, że moim głównym celem jest, jeśli dobrze zrozumiałem „szum Laplace'a”. Kod mogę w jakiś sposób ćwiczyć.
Lotte,

Odpowiedzi:

14

Masz rację, dodanie szumu Laplace'a oznacza, że ​​do zmiennej dodajesz zmienną która podąża za rozkładem Laplace'a . Istnieje wiele powodów, dla których nazywa się to hałasem . Najpierw pomyśl o przetwarzaniu sygnału, w którym wiadomość jest wysyłana przez jakiś kanał, a ze względu na niedoskonały charakter kanału odbierany sygnał jest zaszumiony, więc musisz odizolować sygnał od szumu. Po drugie, w kryptografii mówimy również o hałasie pseudolosowym, a prywatność różnicowa jest związana z kryptografią. Po trzecie, w statystyce i uczeniu maszynowym możemy również mówić o szumie statystycznym, modele statystyczne obejmują terminy hałasu lub błędów itp. (Jest nawet książka o prognozowaniu nazwXYSygnał i hałas Nate Silver). Używamy więc hałasu jako dokładniejszego synonimu niejednoznaczności losowości .

Jeśli chodzi o generowanie losowe, istnieje wiele sposobów rysowania wartości losowych po rozkładzie Laplace'a, na przykład:

  1. Metoda transformacji odwrotnej opisana na Wikipedii:
f <- function(n) {
   u <- runif(n, -0.5, 0.5)
   sign(u)*log(1-2*abs(u))
}
  1. Jeśli i są niezależnymi zmiennymi losowymi po rozkładzie wykładniczym, wówczas następuje po rozkładzie Laplace'a :UVY=UV
g <- function(n) { rexp(n)-rexp(n) }
  1. Jeśli zgodne z rozkładem Laplace'a, tonastępuje rozkład wykładniczy , więc:Y|Y|
h <- function(n) { rexp(n)*sample(c(-1,1), n, replace = TRUE) }

Na poniższych wykresach widać rozkład próbek narysowanych przy użyciu każdej funkcji z towarzyszącą gęstością Laplace'a (czerwona linia).105

wprowadź opis zdjęcia tutaj

Aby uprościć przykłady, używam standardowego rozkładu Laplace'a ze skalą = 1, ale można łatwo zmienić wyniki, mnożąc wyniki przy użyciu innego współczynnika skalowania.

Tim
źródło
Dzięki! Odpowiadając na moje pytanie, po prostu byłem bardzo zdezorientowany terminem „hałas” i nie mogłem znaleźć właściwego wyjaśnienia.
Lotte
Narysowałem histogram dla mojego kodu i wygląda dobrze :)
Lotte
2

Rozkład Laplace'a lub podwójny wykładniczy spada wykładniczo w lewo i prawo wokół jakiejś średniej. Zasadniczo jest to wykładniczy odbicie w drugiej stronie.

  • Jeśli chcesz mieć prawdopodobieństwo, użyj prawdopodobieństwa wykładniczego i dodaj abs () do obserwowanej wartości. Prawdopodobieństwo dziennika jest po prostu abs () reszt, pomnożone przez współczynnik wykładniczy.

  • Aby próbkować, najłatwiej jest narysować z -1,1 i pomnożyć przez losowanie z rozkładu wykładniczego, który jest dostępny w większości języków programowania. Alternatywnie, jak wspomniano powyżej, znajdziesz także bezpośrednie implementacje Laplace'a, ale może to wymagać nieco więcej wyszukiwania.

Florian Hartig
źródło