La privacidad diferencial (DP) es el estándar más confiable para proteger la información de los usuarios en grandes proyectos de aprendizaje automático y análisis de datos. Una tarea clave dentro de esta área es la selección de particiones: se trata de extraer de manera segura la mayor cantidad posible de elementos únicos de enormes conjuntos de datos aportados por usuarios (como consultas o tokens de documentos), siempre garantizando un nivel estricto de privacidad. Un equipo de investigadores del MIT y Google AI Research ha desarrollado nuevos algoritmos para realizar esta selección de particiones con privacidad diferencial, buscando maximizar el número de ítems únicos seleccionados sin comprometer la privacidad individual de los usuarios.
El problema fundamental de la selección de particiones se puede resumir así: ¿cómo revelar la mayor cantidad de elementos distintos en un conjunto de datos sin poner en riesgo la privacidad de ningún usuario? Los elementos que solo conoce un usuario deben mantenerse confidenciales, mientras que solo aquellos que cuentan con suficiente respaldo comunitario pueden ser divulgados con seguridad. Este problema es clave en muchas aplicaciones, como la extracción privada de vocabulario y n-gramas para tareas de procesamiento de lenguaje natural, el análisis de datos categóricos y creación de histogramas, el aprendizaje privado de embeddings basados en datos de usuarios, o la anonimización de consultas estadísticas, por ejemplo, en buscadores o bases de datos.
Hasta ahora, el enfoque más común, utilizado en librerías como PyDP o en el toolkit de privacidad diferencial de Google, consta de tres pasos. Primero, se asigna un “peso” a cada elemento, generalmente su frecuencia entre los usuarios, controlando el aporte de cada individuo. Luego, para proteger la privacidad, se añade ruido aleatorio (usualmente Gaussiano) a esos pesos. Finalmente, solo se revelan los elementos cuyo peso con ruido supera un umbral ligado a los parámetros de privacidad (ε, δ). Este método es sencillo y altamente paralelo, lo que permite procesar conjuntos de datos enormes con herramientas como MapReduce, Hadoop o Spark. Sin embargo, presenta una limitación importante: los elementos muy populares acumulan un peso excesivo que no mejora la privacidad, y esto impide que elementos menos frecuentes, pero valiosos, puedan alcanzar el umbral y ser divulgados.
Para superar esta limitación, el equipo de Google introdujo el primer algoritmo adaptativo y paralelizable para la selección de particiones llamado MaxAdaptiveDegree (MAD), junto con una extensión de múltiples rondas llamada MAD2R, pensados para manejar datasets gigantescos, con cientos de miles de millones de entradas.
Las principales innovaciones técnicas de MAD son:
- Reponderación adaptativa: MAD identifica los elementos cuyo peso supera ampliamente el umbral y redistribuye ese exceso hacia elementos menos representados. Esta “reponderación adaptativa” aumenta la probabilidad de revelar ítems raros pero compartidos suficientemente, maximizando así la utilidad del resultado.
- Garantías estrictas de privacidad: pese a esta redistribución de pesos, MAD mantiene las mismas condiciones de sensibilidad y ruido que los métodos tradicionales, asegurando la privacidad diferencial a nivel usuario bajo el modelo central.
- Escalabilidad: los algoritmos MAD y MAD2R solo requieren un trabajo lineal respecto al tamaño del dataset y una cantidad constante de rondas paralelas, facilitando su ejecución eficiente en sistemas distribuidos de gran escala. No necesitan cargar toda la data en memoria y permiten un procesamiento multi-máquina.
- Mejora con múltiples rondas (MAD2R): al dividir el “presupuesto” de privacidad entre rondas y utilizar la información ruidosa obtenida en la primera para orientar la segunda, MAD2R logra una mayor eficacia, permitiendo extraer más ítems únicos, algo especialmente útil en distribuciones con una cola larga, típicas de datos reales.
En cuanto al funcionamiento detallado, MAD comienza con una asignación uniforme inicial de pesos para los ítems, respetando los límites de sensibilidad. Luego, los ítems que superan un umbral adaptativo tienen su exceso de peso recortado y este se reatribuye proporcionalmente a otros elementos asociados a los mismos usuarios. Se ajustan después esos pesos para corregir posibles errores derivados de la asignación inicial. Finalmente, se añade ruido Gaussiano y se revelan los elementos cuyo peso con ruido supera el umbral. En MAD2R, los resultados y pesos ruidosos de la primera ronda guían la selección en una segunda vuelta, mejorando aún más el rendimiento sin comprometer la privacidad.
Los experimentos realizados en nueve conjuntos de datos variados (incluyendo Reddit, IMDb, Wikipedia, Twitter, Amazon y Common Crawl, con cerca de un billón de registros) demuestran que MAD2R supera a todos los métodos paralelos existentes en siete de los nueve casos, en cuanto a la cantidad de elementos únicos recuperados bajo parámetros de privacidad fijos. Por ejemplo, en el dataset Common Crawl, MAD2R logró extraer 16.6 millones de elementos únicos de un total de 1.8 mil millones (0.9%), pero cubrió casi al 100% de los usuarios y el 97% de las parejas usuario-elemento, mostrando un valor práctico notable sin sacrificar la privacidad. Para conjuntos de datos pequeños, los resultados de MAD son comparables a los de algoritmos secuenciales y no escalables, mientras que para conjuntos enormes, destacan tanto en velocidad como en utilidad.
Para ilustrar con un ejemplo, imagina que tenemos un “ítem pesado” muy popular y muchos “ítems ligeros” poco frecuentes. Los métodos tradicionales asignan demasiado peso al ítem popular pero no suficiente a los ligeros, que así no alcanzan a superar el umbral y no se revelan. MAD redistribuye el peso excedente, dando más oportunidad a los ítems ligeros y aumentando en hasta un 10% la cantidad de elementos únicos descubiertos en comparación con el enfoque clásico.
En resumen, con la ponderación adaptativa y un diseño paralelo, el equipo de investigación ha llevado la selección de particiones con privacidad diferencial a niveles superiores de escalabilidad y utilidad. Estos avances permiten a investigadores e ingenieros aprovechar más y mejor los datos privados, extrayendo más información útil sin comprometer la confidencialidad individual.
