Diferencias

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

--- pan:privacidad_diferencial_v2 [2026/01/06 14:56] – thejuanvisu
+++ pan:privacidad_diferencial_v2 [2026/01/06 17:23] (actual) – thejuanvisu
@@ Línea 178: / Línea 178: @@
 </WRAP>
-===== Mecanismo de Respuesta Aleatoria (Entrada/salida Binaira) =====
+===== 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