Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

Resumen Técnico: Cuantificación de la Sensibilidad para Ensembles de Árboles

Planteamiento del Problema
Los Ensembles de Árboles de Decisión (DTE), como XGBoost y Random Forests, se utilizan ampliamente en dominios críticos para la seguridad, pero plantean desafíos para la verificación formal. Si bien el trabajo existente ha abordado la existencia de sensibilidad (encontrar un único "par sensible" de entradas que difieren solo en características protegidas pero producen salidas diferentes), este artículo argumenta que las comprobaciones binarias de existencia son insuficientes para una comprensión cuantitativa de la equidad del modelo. El problema central abordado es la cuantificación de la sensibilidad: determinar el volumen o la cantidad de regiones de entrada en un DTE donde pequeñas perturbaciones en las características sensibles conducen a una clasificación errónea o a cambios significativos en la salida. Este problema se distingue de la robustez local (comprobar una vecindad de una entrada específica) y es computacionalmente más difícil, clasificándose en la clase de complejidad #P-dura, ya que requiere buscar todo el espacio de entrada para contar las asignaciones satisfactorias en lugar de simplemente encontrar una.

Metodología
Los autores proponen XCount, un marco algorítmico novedoso que combina la compilación de conocimientos, la descomposición composicional y el conteo de modelos aproximado para estimar el número de regiones sensibles con garantías formales.

1. Discretización y Codificación Simbólica:
   El espacio de entrada continuo se discretiza basándose en los predicados de guarda (pares característica-umbral) del DTE. Esto mapea el espacio de entrada a un conjunto finito de vectores booleanos. El comportamiento del modelo se codifica utilizando Diagramas de Decisión Algebraicos (ADD), una extensión cuantitativa de los Diagramas de Decisión Binarios (BDD). Los ADD permiten la representación eficiente de la estructura aditiva del ensemble ($T(x) = \sum T_i(x)$).

2. Descomposición Composicional:
   Compilar directamente un DTE grande en un ADD monolítico es intensivo en memoria y a menudo intratable. Para superar esto, el algoritmo emplea una estrategia de dividir y conquistar:

   • El problema se divide en subproblemas basados en pares de máscaras de bits (asignaciones a características sensibles) que difieren en a lo sumo $d$ bits (distancia de Hamming).
   • Para cada par, las características sensibles se fijan y los árboles de decisión se "poda" para eliminar ramas inalcanzables, resultando en subproblemas más pequeños y tratables.
   • Cada subproblema calcula la diferencia en las salidas entre las dos asignaciones fijas.

3. Conteo Aproximado con Garantías PAC:
   En lugar de realizar un conteo exacto sobre la unión de todas las soluciones de subproblemas (lo que reintroduciría la complejidad de los conjuntos superpuestos), los autores adaptan una técnica de la teoría de bases de datos para aproximar el volumen de una unión de conjuntos en un modelo de flujo continuo.

   • El algoritmo muestrea asignaciones satisfactorias de los subproblemas (representados como BDD) utilizando un enfoque probabilístico.
   • Mantiene un conjunto de muestras y ajusta la probabilidad de muestreo dinámicamente para garantizar que la estimación final $\hat{C}$ satisfaga las garantías Probablemente Correctas Aproximadamente (PAC): $Pr[(1-\epsilon)C \leq \hat{C} \leq (1+\epsilon)C] \geq 1-\delta$.

Contribuciones Clave

1. Formulación Cuantitativa: El artículo define una noción discretizada y cuantitativa de sensibilidad que cuenta el número de regiones de entrada que admiten un par sensible, avanzando más allá de las simples comprobaciones de existencia.
2. Algoritmo Composicional: Introduce una estrategia de división y fusión que descompone el problema global de conteo en subproblemas paralelizables, abordando los problemas de escalabilidad de la compilación monolítica de ADD.
3. Solidez Teórica: El método proporciona garantías teóricas sólidas, asegurando que el conteo aproximado se encuentre dentro de un margen de error definido por el usuario ($\epsilon$) con un nivel de confianza especificado ($1-\delta$).
4. Implementación y Validación: Los autores implementaron la herramienta XCount y la validaron frente a contadores de modelos exactos de última generación (Ganak) y contadores aproximados (ApproxMC), así como frente a una línea base de ADD monolítico.

Resultados Experimentales
Los autores evaluaron XCount en 3.194 instancias de referencia derivadas de 10 conjuntos de datos del mundo real (por ejemplo, Adult, Diabetes, Higgs) con tamaños de ensemble variables (10–100 árboles) y profundidades (3–6).

• Rendimiento: XCount superó significativamente a todas las líneas base. Resolvió 1.552 instancias, en comparación con 721 para Ganak y 579 para ApproxMC. Logró un Tiempo de Ejecución Promedio Penalizado (PAR2) de 1.937 segundos, lo que representa una mejora del 33% sobre el siguiente mejor enfoque y una mejora del 43% sobre la línea base de ADD.
• Precisión: Para las instancias donde estaban disponibles conteos exactos, XCount mantuvo una alta fidelidad, con el 99% de las estimaciones cayendo dentro del margen de error del 10% prescrito ($\epsilon=0.1$).
• Escalabilidad: La herramienta demostró una escalabilidad superior con el aumento del tamaño y la profundidad del ensemble, mientras que el enfoque de ADD monolítico no pudo escalar más allá de instancias pequeñas.

Significado y Aplicaciones
El artículo afirma que XCount proporciona un método escalable, sólido y completo para cuantificar la sensibilidad en DTEs, una tarea previamente considerada intratable para modelos grandes.

• Validación de Regularización: Como una aplicación específica, los autores utilizaron XCount para validar la efectividad de la regularización L1. Demostraron que aumentar el parámetro de regularización $\alpha$ se correlaciona con una disminución en el número de regiones sensibles, lo que sugiere que contar la sensibilidad puede servir como una métrica para evaluar el sobreajuste del modelo y la generalización sin acceso a los parámetros internos de entrenamiento.
• Equidad y Seguridad: Al cuantificar el "volumen" de la injusticia, el enfoque ofrece una métrica más matizada para la equidad individual y la discriminación causal que la verificación binaria, permitiendo a los profesionales ajustar los modelos para cumplir con umbrales regulatorios específicos (por ejemplo, asegurando que la sensibilidad esté por debajo del 1% del espacio de entrada).

Los autores concluyen que, aunque su trabajo se centra en DTEs, las técnicas composicionales y probabilísticas son generalizables, y el trabajo futuro explorará la aplicación de estos conteos de sensibilidad para clasificar modelos y extender el enfoque a otras clases de modelos de aprendizaje automático.