Approximation-Free Differentiable Oblique Decision Trees

Resumen Técnico: Árboles de Decisión Oblícuos Diferenciables sin Aproximación

Enunciado del Problema
Los Árboles de Decisión (AD) son altamente valorados en dominios críticos para la seguridad (por ejemplo, diagnóstico médico) por su interpretabilidad y eficacia en datos tabulares. Sin embargo, entrenar AD oblicuos precisos (donde las divisiones son combinaciones lineales de características en lugar de estar alineadas con los ejes) es computacionalmente desafiante debido a la naturaleza NP-dura del espacio de búsqueda. Aunque los enfoques diferenciables recientes permiten el entrenamiento basado en gradientes, dependen de aproximaciones que comprometen la integridad del proceso de aprendizaje:

1. AD Suaves: Utilizan fronteras "suaves" probabilísticas (por ejemplo, activaciones Sigmoide) para hacer los árboles diferenciables, pero convertir estas a decisiones "duras" a menudo degrada la precisión.
2. Estimadores Straight-Through (STE): Se utilizan en métodos como DGT e ICCT para aproximar gradientes a través de decisiones duras no diferenciables. Esto crea una discrepancia semántica entre el paso hacia adelante (evaluación) y el paso hacia atrás (optimización). En tareas de regresión, esta discrepancia conduce a actualizaciones de gradientes sesgadas, inestabilidad estructural y la subutilización de nodos hoja, ya que los parámetros internos se actualizan basándose en todos los regresores mientras que solo se selecciona uno.

Metodología: DTSemNet
Los autores proponen DTSemNet, una arquitectura de red neuronal novedosa que proporciona una representación invertible y semánticamente equivalente de AD oblicuos duros. A diferencia de trabajos anteriores, DTSemNet permite el entrenamiento de extremo a extremo utilizando descenso de gradiente estándar sin aproximaciones.

• Arquitectura: DTSemNet codifica un AD con $m$ nodos internos y $n$ hojas en una red neuronal utilizando activaciones ReLU y operaciones lineales.
  • Nodos Internos: Representados por capas lineales que calculan $\langle A_i, x \rangle + b_i$.
  • Ramificación: Utiliza activaciones ReLU para separar resultados positivos ($\top$) y negativos ($\bot$), asegurando que exactamente una rama esté activa para cualquier entrada (excepto en fronteras de medida cero).
  • Hojas: Una capa lineal de peso fijo agrega las ramas activas para producir logits para cada hoja.
• Equivalencia Semántica: El Teorema 1 demuestra que para cualquier entrada $x$, la hoja seleccionada por el AD duro es idéntica a la hoja con el logit de salida máximo en la red DTSemNet. Por lo tanto, la función de evaluación (paso hacia adelante) y la función de optimización (paso hacia atrás) son semánticamente idénticas.

Estrategia de Regresión: Top-k Recocido
Mientras que la clasificación se alinea naturalmente con esta formulación (vía argmax), la regresión requiere optimizar conjuntamente el enrutamiento (nodos internos) y los regresores de hoja. Los autores identifican que el uso de un único STE (como en su trabajo anterior de conferencia) causa inestabilidad porque actualiza los nodos internos basándose en todos los regresores mientras actualiza solo un regresor por paso.

Para resolver esto, el artículo introduce un método Top-k Recocido:

1. Mecanismo: En lugar de una selección Top-1 dura durante el entrenamiento, el modelo utiliza inicialmente un selector Top-$k$ ($k \ge 2$) combinado con un Softmax escalado por temperatura. Esto permite que el modelo enrute las entradas a múltiples expertos (hojas) simultáneamente, proporcionando gradientes informativos.
2. Recocido: El valor de $k$ se reduce gradualmente desde $k \ge 2$ hasta $k=1$ a lo largo de las épocas de entrenamiento.
3. Beneficios:
   • Consistencia del Gradiente: A diferencia del STE, los pasos hacia adelante y hacia atrás comparten la misma semántica en cada paso $k$.
   • Actualizaciones Equilibradas: Los parámetros del nodo interno se actualizan basándose solo en los regresores seleccionados en el top-$k$, evitando la influencia desestabilizadora de hojas lejanas no seleccionadas.
   • Exploración: Múltiples regresores se actualizan para una sola muestra, permitiendo que el modelo se adapte si la decisión de enrutamiento cambia más adelante en el entrenamiento.
4. Ajuste Fino: Una vez alcanzado $k=1$, los nodos internos se congelan y los regresores de hoja se ajustan finamente utilizando muestras aumentadas para prevenir el sobreajuste.

Contribuciones Clave

1. Arquitectura DTSemNet: Una codificación diferenciable de AD oblicuos que es semánticamente equivalente al árbol duro, permitiendo el entrenamiento exacto por descenso de gradiente sin aproximación para clasificación.
2. Top-k Recocido para Regresión: Un procedimiento de entrenamiento novedoso que elimina la aproximación y el sesgo inherentes a los métodos basados en STE para regresión, asegurando una optimización conjunta estable y precisa de los parámetros de enrutamiento y hoja.
3. Políticas RL Programáticas: Demostración de DTSemNet como una política programática en Aprendizaje por Refuerzo (RL), reemplazando a las Redes Neuronales (RN) estándar en espacios de acción discretos y continuos.

Resultados Experimentales
Los autores evaluaron DTSemNet frente a métodos del estado del arte (TAO, DGT, CRO-DT, CART, ICCT, VIPER) en benchmarks de clasificación, regresión y RL.

• Clasificación: DTSemNet logró el mejor rendimiento en cada conjunto de datos probado, incluyendo árboles concisos y densos. Superó significativamente a los métodos no basados en gradientes (por ejemplo, TAO, CRO-DT) y a las aproximaciones basadas en gradientes (DGT), reduciendo el error de clasificación hasta un 10% en benchmarks desafiantes como Reconocimiento Óptico. Los tiempos de entrenamiento fueron comparables a DGT pero significativamente más rápidos que los métodos de búsqueda global.
• Regresión: DTSemNet con Top-k superó a todos los competidores en casi todos los conjuntos de datos. Logró una mejora promedio del RMSE del 3% sobre TAO-Linear y superó significativamente a DTSemNet-STE (que utilizaba STE). Los estudios de ablación confirmaron que Top-k conduce a una utilización de hojas más equilibrada y una evolución de pesos estable en comparación con STE, que tiende a subutilizar las hojas.
• Aprendizaje por Refuerzo:
  • Acciones Discretas: DTSemNet igualó o superó el rendimiento de las RN y superó significativamente a otras políticas basadas en AD (DGT, ICCT, VIPER) en entornos como LunarLander y Zerglings.
  • Acciones Continuas: Utilizando la estrategia de recocido Top-k con SAC, DTSemNet superó a las líneas base de RN y a los AD basados en STE en LunarLander Continuo y BipedalWalker, demostrando que el entrenamiento sin aproximación produce políticas superiores incluso en control continuo.

Significado y Afirmaciones
El artículo afirma que DTSemNet es la primera arquitectura que logra entrenamiento sin aproximación para AD oblicuos en configuraciones de clasificación y regresión. Al eliminar la discrepancia semántica entre la evaluación y la optimización, supera la inestabilidad y el sesgo de los enfoques basados en STE. Los autores argumentan que esto cierra la brecha entre la interpretabilidad de los modelos simbólicos (AD) y la escalabilidad del entrenamiento basado en gradientes, haciendo viables modelos interpretables de alto rendimiento para aplicaciones críticas para la seguridad y entornos RL complejos.

Limitaciones y Trabajo Futuro
Los autores reconocen que, como AD, DTSemNet no es adecuado para entradas de alta dimensión como imágenes, donde lucha con formas complejas. El trabajo futuro se centrará en desarrollar métodos diferenciables para el crecimiento y la poda adaptativa de árboles, alejándose de las alturas de árbol fijas como hiperparámetros.