El mecanismo exponencial es una técnica para diseñar algoritmos privados diferencialmente . Fue desarrollado por Frank McSherry [1] y Kunal Talwar [2] en 2007. Su trabajo fue reconocido como co-ganador del Premio PET 2009 a la Investigación Destacada en Tecnologías de Mejora de la Privacidad. [3]
La mayor parte de la investigación inicial en el campo de la privacidad diferencial giró en torno a funciones de valor real que tienen una sensibilidad relativamente baja al cambio en los datos de un solo individuo y cuya utilidad no se ve obstaculizada por pequeñas perturbaciones aditivas. Una pregunta natural es qué sucede en la situación en la que se quiere preservar conjuntos de propiedades más generales. El mecanismo exponencial ayuda a ampliar la noción de privacidad diferencial para abordar estos problemas. Además, describe una clase de mecanismos que incluye todos los posibles mecanismos diferencialmente privados.
El mecanismo exponencial [4]
Algoritmo
En términos muy genéricos, un mecanismo de privacidad mapea un conjunto de entradas del dominio a un rango . El mapa puede ser aleatorio, en cuyo caso cada elemento del dominio corresponde a una distribución de probabilidad sobre el rango . El mecanismo de privacidad no asume la naturaleza de y aparte de una medida base en . Definamos una función. Intuitivamente, esta función asigna una puntuación al par, dónde y . La partitura refleja el atractivo de la pareja., es decir, cuanto más alta sea la puntuación, más atractiva será la pareja. Dada la entrada, el objetivo del mecanismo es devolver un tal que la función se maximiza aproximadamente. Para lograr esto, configure el mecanismocomo sigue:
Definición: Para cualquier funcióny una medida base encima , definir:
- Escoger con probabilidad proporcional a , dónde .
Esta definición implica el hecho de que la probabilidad de devolver un aumenta exponencialmente con el aumento en el valor de . Ignorando la medida base entonces el valor que maximiza tiene la mayor probabilidad. Además, este mecanismo es diferencialmente privado. Seguirá la prueba de este reclamo. Un tecnicismo que debe tenerse en cuenta es que para definir adecuadamente la debe ser finito.
Teorema (privacidad diferencial): da -Privacidad diferencial.
Prueba: la densidad de probabilidad de a es igual a
Ahora, si un solo cambio en cambios por como máximo entonces el numerador puede cambiar como máximo por un factor de y el mínimo del denominador por un factor de . Por tanto, la relación de la nueva densidad de probabilidad (es decir, con la nueva) y el anterior es como máximo .
Precisión
Lo ideal sería que los sorteos aleatorios de desde el mecanismo para maximizar casi . Si consideramos ser - estar entonces podemos demostrar que la probabilidad de que el mecanismo se desvíe de es baja, siempre que haya una masa suficiente (en términos de ) de valores con valor cerca del óptimo.
Lema: dejar y , tenemos es como máximo . La probabilidad se hace cargo.
Prueba: la probabilidad es como máximo , ya que el denominador puede ser como máximo uno. Dado que ambas probabilidades tienen el mismo término de normalización,
El valor de es como máximo uno, por lo que este límite implica la declaración del lema.
Teorema (precisión): para aquellos valores de, tenemos .
Prueba: se deduce del lema anterior que la probabilidad de que la puntuación sea al menos es . Por hipótesis,. Sustituyendo el valor de obtenemos que esta probabilidad sea al menos . Multiplicando con produce el límite deseado.
Podemos asumir por ser menor o igual a uno en todos los cálculos, porque siempre podemos normalizar con .
Ejemplo de aplicación del mecanismo exponencial [5]
Antes de entrar en los detalles del ejemplo, definamos algunos términos que usaremos extensamente a lo largo de nuestra discusión.
Definición (sensibilidad global): la sensibilidad global de una consulta es su diferencia máxima cuando se evalúa en dos conjuntos de datos vecinos :
Definición: una consulta de predicado para cualquier predicado se define como
Tenga en cuenta que para cualquier predicado .
Mecanismo de liberación
Lo siguiente se debe a Avrim Blum , Katrina Ligett y Aaron Roth .
Definición (utilidad): Un mecanismo [ enlace muerto permanente ] es -util para consultas en clase con probabilidad , Si y cada conjunto de datos , por , .
De manera informal, significa que con alta probabilidad la consulta se comportará de manera similar en el conjunto de datos original y en el conjunto de datos sintéticos .
Considere un problema común en la minería de datos. Suponga que hay una base de datos con entradas. Cada entrada consta de-tuplas de la forma dónde . Ahora, un usuario quiere aprender un medio espacio lineal de la forma. En esencia, el usuario quiere averiguar los valores detal que el número máximo de tuplas en la base de datos satisfaga la desigualdad. El algoritmo que describimos a continuación puede generar una base de datos sintéticalo que permitirá al usuario aprender (aproximadamente) el mismo medio espacio lineal mientras consulta en esta base de datos sintética. La motivación para un algoritmo de este tipo es que la nueva base de datos se generará de manera diferencialmente privada y, por lo tanto, garantizará la privacidad de los registros individuales en la base de datos..
En esta sección mostramos que es posible publicar un conjunto de datos que sea útil para conceptos de una clase polinomial VC-Dimension y al mismo tiempo adherirse a-Privacidad diferencial siempre que el tamaño del conjunto de datos original sea al menos polinomial en la Dimensión VC de la clase de concepto. Para declarar formalmente:
Teorema: para cualquier clase de funciones y cualquier conjunto de datos tal que
podemos generar un -conjunto de datos útil que conserva -Privacidad diferencial. Como mencionamos anteriormente, el algoritmo no necesita ser eficiente.
Un dato interesante es que el algoritmo que vamos a desarrollar genera un conjunto de datos sintéticos cuyo tamaño es independiente del conjunto de datos original; de hecho, solo depende de la dimensión VC de la clase de concepto y el parámetro. El algoritmo genera un conjunto de datos de tamaño
Tomamos prestado el Teorema de convergencia uniforme de la combinatoria y expresamos un corolario que se alinea con nuestra necesidad.
Lema: dado cualquier conjunto de datos existe un conjunto de datos de tamaño tal que .
Prueba:
Sabemos por el teorema de convergencia uniforme que
donde la probabilidad está por encima de la distribución del conjunto de datos. Por lo tanto, si el RHS es menor que uno, entonces sabemos con certeza que el conjunto de datosexiste. Para limitar el RHS a menos de uno, necesitamos, dónde es una constante positiva. Como dijimos anteriormente que generaremos un conjunto de datos de tamaño, entonces usando este límite en obtenemos . De ahí el lema.
Ahora invocamos el mecanismo exponencial.
Definición: para cualquier función y conjunto de datos de entrada , el mecanismo exponencial genera cada conjunto de datos con probabilidad proporcional a .
Por el mecanismo exponencial sabemos que esto conserva -Privacidad diferencial. Volvamos a la demostración del teorema.
Definimos .
Para demostrar que el mecanismo satisface la -utilidad, deberíamos mostrar que genera algún conjunto de datos con con probabilidad . Hay como máximo conjuntos de datos de salida y la probabilidad de que es a lo sumo proporcional a . Por lo tanto, por límite de unión, la probabilidad de generar cualquier conjunto de datos de este tipo es a lo sumo proporcional a . Nuevamente, sabemos que existe un conjunto de datos para cual . Por lo tanto, tal conjunto de datos se genera con una probabilidad al menos proporcional a.
Dejar el evento de que el mecanismo exponencial genera algún conjunto de datos tal que .
el evento de que el mecanismo exponencial genera algún conjunto de datos tal que .
Ahora estableciendo esta cantidad en al menos , encontramos que es suficiente tener
Y por lo tanto probamos el teorema.
El mecanismo exponencial en otros dominios
En el ejemplo anterior del uso del mecanismo exponencial, se puede generar un conjunto de datos sintéticos de manera diferencialmente privada y se puede utilizar el conjunto de datos para responder consultas con buena precisión. Otros mecanismos privados, como el muestreo posterior [6], que devuelve parámetros en lugar de conjuntos de datos, pueden hacerse equivalentes al exponencial. [7]
Aparte de la configuración de la privacidad, el mecanismo exponencial también se ha estudiado en el contexto de la teoría de subastas y algoritmos de clasificación . [8] En el caso de las subastas, el mecanismo exponencial ayuda a lograr un entorno de subasta veraz .
Referencias
- ^ Frank McSherry
- ^ Kunal Talwar
- ^ "Pasados ganadores del premio PET" .
- ^ F.McSherry y K.Talwar. Diseño de Mecanismos vía Privacidad Diferencial. Actas del 48 ° Simposio Anual de Fundamentos de la Ciencia de la Computación, 2007.
- ^ Avrim Blum, Katrina Ligett, Aaron Roth. Un enfoque de la teoría del aprendizaje para la privacidad de bases de datos no interactivas, en las actas del 40 ° simposio anual de ACM sobre teoría de la computación, 2008
- ^ Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, Benjamin Rubinstein. Inferencia Bayesiana Robusta y Privada. Teoría del aprendizaje algorítmico 2014
- ^ Yu-Xiang Wang, Stephen E. Fienberg, Alex Smola Privacidad gratis: muestreo posterior y gradiente estocástico Monte Carlo. Congreso Internacional de Aprendizaje Automático, 2015.
- ^ Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova , Adam Smith. ¿Qué podemos aprender en privado? Actas del 49º Simposio Anual del IEEE de 2008 sobre los fundamentos de la informática. arXiv: 0803.0924
enlaces externos
- Los fundamentos algorítmicos de la privacidad diferencial por Cynthia Dwork y Aaron Roth, 2014.