La privacidad diferencial (DP) se erige como el estándar de oro para proteger la información del usuario en el aprendizaje automático a gran escala y el análisis de datos. Una tarea crítica dentro de DP es selección de partición—El proceso de extraer de forma segura el mayor conjunto posible de elementos únicos de conjuntos de datos masivos que confían en el usuario (como consultas o tokens de documentos), mientras se mantiene estrictas garantías de privacidad. Un equipo de investigadores de la investigación del MIT y Google AI presentan algoritmos novedosos para la selección de partición diferencialmente privada, que es un enfoque para maximizar el número de elementos únicos seleccionados de una unión de conjuntos de datos, al tiempo que preserva estrictamente la privacidad diferencial de nivel de usuario.
El problema de selección de partición en privacidad diferencial
En su núcleo, la selección de partición pregunta: ¿Cómo podemos revelar tantos elementos distintos como sea posible de un conjunto de datos, sin arriesgar la privacidad de cualquier individuo? Los elementos que solo conocen un solo usuario deben permanecer en secreto; Solo aquellos con suficiente soporte de “crowdsourcing” se pueden revelar de manera segura. Este problema sustenta aplicaciones críticas como:
- Vocabulario privado y extracción N-Gram para tareas de PNL.
- Análisis de datos categóricos y cálculo de histograma.
- Aprendizaje de preservación de la privacidad de incrustaciones sobre elementos proporcionados por el usuario.
- Anónimo de consultas estadísticas (por ejemplo, para motores de búsqueda o bases de datos).
Enfoques y límites estándar
Tradicionalmente, la solución de referencia (implementada en bibliotecas como PYDP y el kit de herramientas de privacidad diferencial de Google) implica tres pasos:
- Pondering: Cada elemento recibe una “puntuación”, generalmente su frecuencia entre los usuarios, con la contribución de cada usuario estrictamente limitada.
- Adición de ruido: Para ocultar la actividad precisa del usuario, se agrega ruido aleatorio (generalmente gaussiano) al peso de cada elemento.
- Umbral: Solo se liberan elementos cuya puntuación ruidosa pasa un umbral establecido, calculado a partir de parámetros de privacidad (ε, δ).
Este método es simple y altamente paralelo, lo que le permite escalar a gigantescos conjuntos de datos utilizando sistemas como MapReduce, Hadoop o Spark. Sin embargo, sufre de ineficiencia fundamental: los artículos populares acumulan un exceso de peso que no ayuda a la privacidad, mientras que los artículos menos comunes pero potencialmente valiosos a menudo se pierden porque el exceso de peso no se redirige para ayudarlos a cruzar el umbral.
Ponderación adaptativa y el algoritmo MaxAdaptiveGree (MAD)
La investigación de Google presenta El primer algoritmo de selección de partición adaptativo y paralelo–MaxAdaptiveGree (loco)—Y una extensión múltiple MAD2R, diseñada para conjuntos de datos verdaderamente masivos (cientos de miles de millones de entradas).
Contribuciones técnicas clave
- Revisión adaptativa: MAD identifica elementos con peso muy por encima del umbral de privacidad, redirige el exceso de peso para aumentar los artículos menos representados. Esta “ponderación adaptativa” aumenta la probabilidad de que se revelen elementos raros pero inquieto, maximizando así la utilidad de salida.
- Garantías de privacidad estrictas: El mecanismo de cambio de ruta mantiene el Requisitos exactos de sensibilidad y ruido como ponderación uniforme clásica, asegurando la privacidad diferente a nivel de usuario (ε, δ) bajo el modelo DP central.
- Escalabilidad: MAD y MAD2R requieren solo un trabajo lineal en el tamaño del conjunto de datos y un número constante de rondas paralelas, lo que los hace compatibles con sistemas de procesamiento de datos distribuidos masivos. No necesitan ajustarse a todos los datos en memoria y admitir una ejecución eficiente de múltiples máquinas.
- Mejora de ronda múltiple (MAD2R): Al dividir el presupuesto de privacidad entre las rondas y el uso de pesos ruidosos desde la primera ronda para sesgar el segundo, MAD2R aumenta aún más el rendimiento, lo que permite extraer aún más elementos únicos, especialmente en distribuciones de cola larga típica de los datos del mundo real.
Cómo funciona Mad: detalles algorítmicos
- Ponderación del uniforme inicial: Cada usuario comparte sus elementos con una puntuación inicial uniforme, asegurando límites de sensibilidad.
- Exceso de truncamiento de peso y cambio de ruta: Los elementos por encima de un “umbral adaptativo” tienen su exceso de peso recortado y redirigido proporcionalmente a los usuarios contribuyentes, quienes luego redistribuyen esto a sus otros elementos.
- Ajuste de peso final: Se agrega un peso uniforme adicional para compensar pequeños errores de asignación inicial.
- Adición y salida de ruido: Se agrega el ruido gaussiano; Los elementos por encima del umbral ruidoso son salidas.
En MAD2R, las salidas de primera ronda y los pesos ruidosos se utilizan para refinar en qué elementos deben centrarse en la segunda ronda, con sesgos de peso que no garantizan una pérdida de privacidad y maximizando aún más la utilidad de salida.
Resultados experimentales: rendimiento de vanguardia
Experimentos extensos en nueve conjuntos de datos (de Reddit, IMDB, Wikipedia, Twitter, Amazon, todo el camino hasta Common Crawl con casi un billón de entradas) Show:
- Mad2r supera a todas las líneas de base paralelas (Básico, DP-SIPS) en siete de nueve conjuntos de datos en términos de número de elementos salidas en parámetros de privacidad fijos.
- En el Rastreo común conjunto de datos, Mad2r extrajo 16.6 millones de 1.800 millones de elementos únicos (0.9%), pero cubierto 99.9% de usuarios y 97% De todos los pares de visitas al usuario en los datos, evitando una notable utilidad práctica mientras mantiene la línea de privacidad.
- Para conjuntos de datos más pequeños, MAD aborda el rendimiento de los algoritmos secuenciales no escalables, y para conjuntos de datos masivos, claramente gana tanto en velocidad como en utilidad.
Ejemplo concreto: brecha de servicios públicos
Considere un escenario con un elemento “pesado” (muy comúnmente compartido) y muchos elementos “ligeros” (compartidos por pocos usuarios). La selección básica de DP sobrepesas el elemento pesado sin levantar los elementos ligeros lo suficiente como para pasar el umbral. MAD estratégicamente rehública, aumentando la probabilidad de salida de los elementos de luz y resultando en hasta un 10% más de elementos únicos descubiertos en comparación con el enfoque estándar.
Resumen
Con una ponderación adaptativa y un diseño paralelo, el equipo de investigación lleva la selección de particiones DP a nuevas alturas en escalabilidad y utilidad. Estos avances garantizan que los investigadores e ingenieros puedan hacer un uso más completo de datos privados, extrayendo más señal sin comprometer la privacidad individual del usuario.
Mira el Blog y Documento técnico aquí. No dude en ver nuestro Página de Github para tutoriales, códigos y cuadernos. Además, siéntete libre de seguirnos Gorjeo Y no olvides unirte a nuestro Subreddit de 100k+ ml y suscribirse a Nuestro boletín.
Asif Razzaq es el CEO de MarktechPost Media Inc .. Como empresario e ingeniero visionario, ASIF se compromete a aprovechar el potencial de la inteligencia artificial para el bien social. Su esfuerzo más reciente es el lanzamiento de una plataforma de medios de inteligencia artificial, MarktechPost, que se destaca por su cobertura profunda de noticias de aprendizaje automático y de aprendizaje profundo que es técnicamente sólido y fácilmente comprensible por una audiencia amplia. La plataforma cuenta con más de 2 millones de vistas mensuales, ilustrando su popularidad entre el público.