Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

Enunciado del Problema
Los bosques aleatorios (RF) son un método dominante para la predicción de datos tabulares, ofreciendo alta precisión y eficiencia computacional. Sin embargo, su aplicación en dominios sensibles (por ejemplo, atención sanitaria, finanzas) se ve obstaculizada por el riesgo de filtrar información sobre registros individuales de entrenamiento. Aunque la Privacidad Diferencial (DP) proporciona un marco riguroso para mitigar estos riesgos, los enfoques existentes para imponer DP en bosques aleatorios sufren una degradación severa de la utilidad.

Los métodos actuales generalmente se dividen en dos paradigmas, ambos con limitaciones significativas:

1. Construcción Ávida de Árboles: Adaptar los algoritmos estándar de árboles de decisión (que seleccionan divisiones basándose en criterios de impureza dependientes de los datos) al entorno de DP requiere inyectar ruido en el proceso de selección de divisiones. Este ruido se acumula rápidamente, dando lugar a estructuras de árbol deficientes y baja utilidad.
2. Árboles Completamente Aleatorios: Inspirados en los "Extra Trees", estos métodos generan estructuras de árbol independientes de los datos, utilizando los datos únicamente para etiquetar las hojas. Aunque esto evita gastar el presupuesto de privacidad en el aprendizaje de la estructura, estos árboles son altamente sensibles a la profundidad. Los árboles poco profundos resultan en hojas excesivamente grandes, mientras que los árboles profundos producen hojas con muestras insuficientes para predicciones privatizadas fiables. Además, sin una parada dependiente de los datos, a menudo no logran capturar estructuras informativas en el espacio de características, colapsando hacia predicciones de la clase mayoritaria.

Metodología: Lumberjack
El artículo presenta Lumberjack, un nuevo algoritmo de bosque aleatorio con privacidad diferencial diseñado para cerrar la brecha entre la expresividad de los árboles profundos y las restricciones de la privacidad diferencial. La innovación central es un proceso de dos etapas: construir árboles completamente aleatorios grandes y luego aplicar una poda agresiva que preserva la privacidad para retener únicamente los nodos suficientemente poblados.

• Construcción Aleatorizada: Lumberjack construye árboles aleatorios profundos (similares a los Extra Trees) donde las divisiones se eligen uniformemente al azar desde el espacio de características, independientemente de los datos. Esto evita el alto costo de ruido asociado con la selección ávida de divisiones.
• Poda con Preservación de la Privacidad mediante Detección de "Heavy Hitters": El desafío crítico es determinar qué nodos contienen suficientes puntos de datos para ser retenidos sin violar la privacidad. Lumberjack enmarca esto como un problema de detección de heavy hitters sobre una estructura de árbol jerárquica. El objetivo es identificar nodos donde la cuenta de puntos de datos supera un umbral $\tau$.
• Nuevo Algoritmo de Heavy Hitter: Los autores proponen un nuevo algoritmo $(\epsilon, \delta)$-DP para detectar heavy hitters en árboles de altura $h$.
  • Mecanismo: En lugar de un recorrido ingenuo de arriba hacia abajo que incurre en una sensibilidad $\ell_2$ que escala como $\sqrt{h}$, el algoritmo realiza búsquedas binarias ruidosas estructuradas y superpuestas. Consulta nodos en una capa intermedia, marcándolos como "Pesados" (Heavy) o "Ligeros" (Light).
  • Propagación: Debido a la naturaleza monótona de las cuentas en los árboles (la cuenta de un padre es la suma de la de sus hijos), un nodo "Pesado" implica que todos sus ancestros son Pesados, y un nodo "Ligero" implica que todos sus descendientes son Ligeros. Esto permite al algoritmo omitir grandes porciones del árbol.
  • Reducción de Sensibilidad: Al explotar esta estructura, el algoritmo reduce la sensibilidad $\ell_2$ de $O(\sqrt{h})$ a $O(\sqrt{\log h})$.
  • Integración de Histogramas Dispersos: Para manejar la inviabilidad computacional de consultar todos los nodos en árboles profundos (la mayoría de los cuales están vacíos), el algoritmo integra técnicas de estimación de histogramas dispersos. Mapea determinísticamente las consultas con conteos suficientemente pequeños a "Ligero" (vacío) y solo añade ruido gaussiano a las consultas que podrían no estar vacías.
• Contabilidad Unificada de Privacidad: Los autores realizan un análisis de privacidad unificado para la construcción de todo el bosque en lugar de depender de la composición estándar entre árboles individuales, obteniendo un límite de privacidad más ajustado.

Contribuciones Clave

1. Algoritmo Lumberjack: Un nuevo método de bosque aleatorio DP que combina la construcción de árboles aleatorizados con la poda dependiente de los datos, permitiendo el entrenamiento de árboles profundos y de alta utilidad bajo presupuestos de privacidad estrictos.
2. Detección Novel de Heavy Hitter: Un nuevo algoritmo para la detección de heavy hitters $(\epsilon, \delta)$-DP en datos jerárquicos con una escala de error de $O_{\epsilon, \delta}(\sqrt{\log h})$ para árboles de altura $h$. Los autores señalan que este componente puede ser de interés independiente para otros problemas de datos jerárquicos.
3. Análisis Teórico: Un análisis de privacidad ajustado que evita los límites laxos de los teoremas de composición estándar y establece un límite inferior que demuestra que la escala $O(\sqrt{\log h})$ es casi óptima para métodos que soportan árboles profundos.
4. Estado del Arte Empírico: Una evaluación exhaustiva que demuestra que Lumberjack supera consistentemente a las líneas base existentes de bosques aleatorios DP (incluyendo DiffPrivLib, SNR, Sensibilidad Suave y variantes ávidas) en múltiples conjuntos de datos y regímenes de privacidad.

Resultados
Los autores evaluaron Lumberjack en el conjunto de datos Adult y en cuatro tareas de clasificación binaria del conjunto de datos Folktables (California 2018).

• Rendimiento: Lumberjack superó consistentemente a todos los métodos previos de bosques aleatorios DP en presupuestos de privacidad $\epsilon \in \{0.5, 1, 2, 4, 8\}$.
• Comparación con No Privados: Aunque persiste una brecha en comparación con los Extra Trees no privados, Lumberjack a menudo supera a los árboles de decisión ávidos no privados incluso en niveles de privacidad moderados.
• Problemas de las Líneas Base: El artículo señala que muchas líneas base existentes de RF-DP (particularmente aquellas que utilizan construcción ávida de árboles) contienen fallas de privacidad, como criterios de parada dependientes de los datos o cálculos incorrectos de sensibilidad, que los autores detallan en un apéndice. A pesar de estas fallas en trabajos anteriores, Lumberjack aún supera su rendimiento reportado.
• Escalabilidad: El método maneja con éxito árboles profundos (profundidad hasta 100) sin el colapso de utilidad observado en los enfoques de árboles completamente aleatorios.

Significado y Afirmaciones
El artículo afirma que Lumberjack establece un nuevo estado del arte para los bosques aleatorios con privacidad diferencial. Los autores argumentan que sus hallazgos sugieren que los bosques aleatorios DP cuidadosamente diseñados pueden "cerrar gran parte de la brecha de utilidad" con sus contrapartes no privadas. Destacan que la combinación de construcción aleatorizada con una poda principista y consciente de la privacidad es una dirección prometedora y poco explorada.

Los autores declaran explícitamente que, aunque han abordado la brecha de utilidad para los bosques aleatorizados, diseñar bosques aleatorios DP ávidos de alta utilidad sigue siendo un desafío abierto. Sugieren que el trabajo futuro podría requerir técnicas de composición más refinadas y mecanismos específicos del problema para mejorar aún más la compensación entre privacidad y utilidad. El artículo también sirve como una nota de advertencia sobre el rigor de las pruebas de privacidad en la literatura existente, identificando violaciones de privacidad en más de 10 artículos anteriores.