Diferencias

Muestra las diferencias entre dos versiones de la página.

--- pan:privacidad_diferencial_v2 [2026/01/05 15:04] – thejuanvisu
+++ pan:privacidad_diferencial_v2 [2026/01/06 17:23] (actual) – thejuanvisu
@@ Línea 132: / Línea 132: @@
 Dependiendo de donde se ejecuta el mecanismo $M(D)$ hay 2 modelos generales para la privacidad diferencial:
   * **Privacidad diferencial central**: Hay un agregador de confianza centralizado.
+    * Un mecanismo $M : D$ -> //R// es ε-privadamente diferencial si para todas las salidas $R ⊂$ //R// y todos los pares de bases de datos vecinas $D,D' ∈ D$:
+<WRAP box>
+$Pr(M(D) ∈ R) ≤ Pr(M(D') ∈ R) * e^ε$
+</WRAP>
 {{drawio>pan:pdcentral.png}}
   * **Privacidad diferencial local**: Cada usuario ejecuta el mecanismo y reporta el resultado al analista
+    * Un mecanismo $M : D$ -> //R// es ε-privadamente diferencial si para todas las salidas $R ⊂$ //R// y todos los pares de inputs $X,X'$:
+<WRAP box>
+$Pr(M(x) ∈ R) ≤ Pr(M(x') ∈ R) * e^ε$
+</WRAP>
 {{drawio>pan:pdlocal.png}}
+La definición de la privacidad diferencial se asegura de que correr el mecanismo $M(D)$ en una base de datos vecina producen resultados similares. Normalmente hay 2 definiciones principales para como se definen las bases de datos vecinas en el modelo central:
+  * **Privacidad Diferencial Acotada**: $D$ y $D'$ tienen el mismo número de entradas, pero difieren en el valor de una de ellas (Se modifica el valor de una fila)
+  * **Privacidad Diferencial No Acotada**: $D'$ es obtenida tras eliminar una entrada de $D$ (Se elimina una fila)
+====== Mecanismos de Privacidad Diferencial ======
+Existen varios mecanismos que proveen privacidad diferenciual que pueden ser aplicados en varios sistemas.
+===== Mecanimos Laplaciano (Salida Contínua) =====
+Dada una función $g: D$ -> $R^k$ y dos bases de datos vecinas $D,D' ∈ D$. la $l_1-sensibilidad$ de $g$ es el máximo cambio de salida resultante tras reemplazar $D$ con $D'$:
+<WRAP box>
+$Δ = max_{D,D'}|| g(D) - g(D')||_1$
+</WRAP>
+Dada cualquier función g y Δ, podemos convertirla en un Mecanismo de privadidad diferencial si añadimos ruido laplaciano a su salida. El Mecanimso laplaciano se define como:
+<WRAP box>
+$M(D) = g(D) + [Y_1, Y_2 ..... Y_k]$
+</WRAP>
+Donde cada $Y_i$ tiene una distribución independiente siguiendo $Y_i ~Lap(Δ/ε)$
+==== Mecanismo laplaciano local ====
+En el caso de la privacidad diferencial local, si la función $g : X$ -> $R^k$, entontes dos entradas dadas $X,X' ∈ X$ la $l_1-sensibilidad$ de $g$ es el mayor cambio de la salida que puede resultar de cambiar $X$ por $X'$:
+<WRAP box>
+$Δ = max_{x,x'}||g(X) - g(X')||_1$
+</WRAP>
+===== Mecanismo de Respuesta Aleatorizada (Entrada/salida Binaira) =====
+En este caso tenemos un mecanismo $M : {0,1} -> {0,1}$ para privacidad diferencial local:
+{{drawio>pan:monedilla.png}}
+Se puede realizar una generalización asumiendo una cierta probabilidad de $γ$ de decir la verdad:
+{{drawio>pan:monedillageneralizada.png}}
+==== Respuesta Aleatorizada bajo un prisma de Privacidad Diferencial ====
+Un mecanismo $M : X$ -> $Y$ es ε-privadamente diferencial (ε-DP) si las posibles salidas $y ∈ Y$ y todos los pares de bases de entradas vecias $x, x' ∈ X$:
+<WRAP box>
+$Pr(M(x) = y) ≤ Pr(M(x') = y)* e^ε$
+</WRAP>
+Por lo tanto hay 2 posibles salidas:
+  * **Cuando Y = 0**:
+<WRAP box>
+$\frac{Pr(M(0) = 0)}{Pr(M(1) = 0)} = \frac{γ}{1-γ}$
+</WRAP>
+  * **Cuando Y = 1**:
+<WRAP box>
+$\frac{Pr(M(0) = 1)}{Pr(M(1) = 1)} = \frac{1-γ}{γ}$
+</WRAP>
+  * Si $γ≤1/2$, el más grande de los dos es $(1-γ)/γ$, en caso contrario, γ/(1-γ)
+  * Por lo tanto el nivel de privacidad es el siguiente:
+<WRAP box>
+$ε = max{log(1-γ)γ, log(γ/(1-γ))}$
+</WRAP>
+===== Mecanismo Exponencial (Salidas Discretas) =====
+A veces, añadir ruido laplaciano puede destruir la utilidad del mecanismo. En ocasiones no queremos que las respuestas numéricas sean privadas, pero queremos ser capaces de reportar objetos, clases y categorías. La idea del mecanismo exponencial es que podamos reportar una salida privadamente pero con una probabilidad proporcional a su utilidad.
+Dada una base de datos $D ∈ D$, un set de salidas $H$ y una función de puntuación $S : D x H$ -> //R// el mecanismo exponecial elige una salida $h ∈ H$ con la siguiente probabilidad:
+<WRAP box>
+$Pr(M(D) = h) ∝ exp(\frac{ε * s(D,h)}{2Δ})$
+**Nota**: $∝$ Significa "Proporcional a"
+</WRAP>
+La sensibilidad está dada por:
+<WRAP box>
+$Δ = max_{h∈H} max_{D,D'} |s(D,h) - s(D',h)|$
+</WRAP>
+Para calcular la probabilidad $Pr(M(D) = h)$ necesitamos computar los valores de puntuación para cada $h ∈ H$, lo que puede ser muy costoso. El mecanismo proporcional elige elementos de forma proporcional a la función de puntuación. Las salidas con utilidad van a ser elegidas con mucha mayor probabilidad.
+===== Mecanismo Gaussiano (Privacidad Diferencial Aproximada) =====
+Los mecanismos anteriores proveían una privacidad diferencial exacta, el emcanismo gaussiano la da aproximada. Se usa la $l_2-sensibilidad$ de $g$:
+<WRAP box>
+$Δ = max_{D,D'}||g(D) - g(D')||_2$
+</WRAP>
+El mecanismo gaussiano simplemente añade ruido gaussiano a la salida de la función. El mecanismo Gaussiano es definido como $M(D) = g(D) + [Y_1, Y_2 ... Y_k]$  donde cada $Y_i$ tiene una distribución independiente siguiendo $Y_i ~ N(0,σ^2)$ con:
+<WRAP box>
+$σ^2 = 2log(\frac{1.25}{∂}) * \frac{Δ^2}{ε^2}$
+</WRAP>
+El mecanismo gaussiano provee (ε-∂)-DP
+====== Propiedades de la Privacidad Diferencial ======
+===== Resistencial al post-procesado =====
+Sea $M : D$ -> $γ$ un mecanismo (ε-∂)-DP y $F : Y$ -> $Z$ una aplicación posiblemente aleatoria, entonces $F o M$ es (ε-∂)-DP. Esto significa  que el procesado nunca decrementa la privacidad, pero puede incrementarla. Esto tiene sentido si consideramos que en caso contrario, el adversario podría diseñar una aplicación $F$ que parcialmente revierta $M$. Es muy importante que $F$ no de depnda de $D$ más allá de $γ$.
+===== Privacidad Grupal =====
+Sea $M : D$ -> $R$ un mecanismo que provee ε-DP para $D,D'$ que difieren en una entrada. Entonces provee kε-DP para los datasets D,D' que difieren en k entradas. Esto es fácil de provar construiyendo una secuencia de k datasets que difieran en más de una entrada.
+===== Composición Secuencial =====
+Composición ingénua: Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mecanismos donde $M_i$ es $(ε_i,∂_i)-DP$. Entonces $M$ es $(Σ^k_{i=1}ε_i, Σ^k_{i=1}∂_i)$
+  * Esto significa que ejecutar k mecanismos en el mismo dataset sen sible y publicando todos los k resultados, la privacidad se decremente según se van publicando más resultados.
+Composición Avanzada: Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mecanismos donde $M_i$ es $(ε_i,∂_i)-DP$. Entonces $M$ es $(ε\sqrt{8k*log(1/∂')}, k∂+∂)-DP$
+===== Composición Paralela =====
+Sea $M = {M_1, M_2 ... M_k}$ una secuencia de mencanismos donde $M_i$ es $ε_i-DP$. Sean $D_1, D_2 .... D_k$ una partición determinística de $D$. Publicar las salidas $M_1(D_1), M_2(D_2), ... , M_k(D_k)$ satisface $(max ε_i)-DP$

Knoppia

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página