Resumen Técnico: Árboles de Decisión Ternarios con Zonas de Incertidumbre Localmente Adaptativas

Enunciado del Problema

Los árboles de decisión estándar, particularmente aquellos basados en el algoritmo CART, particionan el espacio de características utilizando umbrales binarios rígidos. Este mecanismo asigna la misma confianza a las instancias independientemente de su proximidad al límite de decisión. En consecuencia, una instancia ubicada lejos del umbral óptimo $\theta$ se trata con la misma certeza que una situada directamente sobre él. Este "compromiso rígido" crea una debilidad conocida: exagera la certeza para las instancias cercanas a los límites donde la división aprendida es menos fiable, fallando en señalizar a las aplicaciones aguas abajo que una predicción puede ser ambigua.

Los enfoques existentes para abordar la incertidumbre a menudo dependen de especificaciones externas de ruido (por ejemplo, errores conocidos de sensores) o umbrales globales derivados de estadísticas a nivel de conjunto de datos. Estos métodos no se adaptan localmente a la calidad específica de la división o a la distribución de datos en cada nodo. Además, enfoques como los árboles de decisión difusos o los árboles de decisión suaves a menudo carecen de una zona de incertidumbre explícita e interpretable derivada de las estadísticas locales de división.

Metodología

El artículo introduce Árboles de Decisión Ternarios, que aumentan las divisiones binarias estándar con una zona de incertidumbre localmente adaptativa de semiancho $\delta$ centrada en el umbral óptimo $\theta^*$.

La Evaluación Ternaria

Para una característica $x_f$ y un umbral $\theta^*$, la lógica de decisión se define como:

• Verdadero (Decisivo): $x_f > \theta^* + \delta$
• Falso (Decisivo): $x_f \leq \theta^* - \delta$
• Indec (Límite-Incierto): $\theta^* - \delta < x_f \leq \theta^* + \delta$

Las instancias que caen en la zona Indec no se abstienen de predecir. En su lugar, reciben una predicción formada por una mezcla ponderada por distancia de las salidas de probabilidad de ambos subárboles hijos. Crucialmente, estas instancias se marcan como "inseguras en el límite", permitiendo que los sistemas aguas abajo las traten de manera diferente (por ejemplo, enrutamiento para revisión humana) sin retener una predicción de clase.

Cálculo Local de $\delta$

La contribución técnica central es derivar $\delta$ localmente en cada nodo utilizando estadísticas ya calculadas durante la búsqueda de divisiones estándar de CART, sin requerir datos externos ni modelos de ruido. El artículo propone y evalúa cinco métodos:

1. Meseta de Calidad ($\delta_{QP}$): Mide el ancho de la "meseta" en la curva del criterio de división (por ejemplo, ganancia Gini) alrededor de $\theta^*$. Una meseta ancha indica que los datos no restringen con precisión la ubicación óptima de la división.
2. Superposición de Clases ($\delta_{CO}$): Calcula el ancho de la región donde las distribuciones de características condicionales a la clase se superponen, basándose en percentiles empíricos.
3. Relación de Ganancia ($\delta_{GR}$): Escala inversamente el rango de características por la relación de ganancia (Ganancia de Información relativa a la entropía de división). Las relaciones de ganancia bajas indican divisiones ambiguas, lo que lleva a un $\delta$ mayor.
4. Bootstrap de Nodo ($\delta_{NB}$): Mide la desviación estándar del umbral óptimo $\theta^*$ a través de remuestreos bootstrap de los datos de entrenamiento del nodo. Esto cuantifica directamente la inestabilidad del umbral.
5. Margen ($\delta_{M}$): Inspirado en las Máquinas de Vectores de Soporte, define $\delta$ como la distancia desde $\theta^*$ hasta el ejemplo de entrenamiento de clase cruzada más cercano (el "vector de soporte" en ese nodo). Si la división es perfectamente limpia, utiliza la brecha física entre puntos de datos adyacentes.

Arquitecturas de Enrutamiento

Se evaluaron dos arquitecturas para propagar instancias inciertas:

• Enrutamiento Probabilístico: La estructura del árbol permanece binaria. Durante la predicción, las instancias en la zona de incertidumbre se enrutan a ambos hijos con pesos inversamente proporcionales a su distancia del umbral, y las salidas se mezclan.
• Rama Media Rígida: Se añade un tercer nodo hijo a la estructura del árbol, entrenado exclusivamente con instancias dentro de la zona de incertidumbre.
  Los resultados experimentales indicaron que el enrutamiento probabilístico generalmente superó al enfoque de medio rígido, ya que este último elimina ejemplos inciertos de los conjuntos de entrenamiento de las ramas izquierda y derecha, degradando su calidad.

Contribuciones Clave

1. Marco: Introducción de árboles de decisión ternarios que proporcionan una zona de incertidumbre principista y localmente adaptativa para cada división.
2. Cinco Métodos de Estimación: Derivación de cinco métodos distintos para calcular $\delta$ utilizando únicamente estadísticas estándar de división de CART, eliminando la necesidad de modelos de ruido externos.
3. Evaluación de Enrutamiento: Análisis comparativo del enrutamiento probabilístico frente al de medio rígido, demostrando la superioridad de la mezcla probabilística para la mayoría de los métodos.
4. Evaluación Empírica Exhaustiva: Evaluación en 72 conjuntos de datos OpenML-CC18, tres benchmarks sintéticos de Breiman (con errores de Bayes conocidos) y cuatro conjuntos de datos médicos/financieros de alto riesgo.
5. Marco Diagnóstico: Introducción de la relación Indecidido/Bayes (U/B) para evaluar qué tan bien la tasa de señalización de un método se alinea con el error irreducible teórico de un conjunto de datos.

Resultados

Validez Amplia (OpenML-CC18)

En 72 conjuntos de datos, los cinco métodos que utilizan enrutamiento probabilístico superaron significativamente la línea base estándar de CART en Precisión Decidida (precisión restringida a instancias no inciertas) con $p \leq 0.001$.

• Método de Margen: Logró la mejor eficiencia (ganancia de precisión por unidad de tasa de señalización, $\eta = 0.104$). Ganó en 42 de 72 conjuntos de datos, marcó solo el 16.7% de las instancias como inciertas y requirió cero hiperparámetros adicionales.
• Superposición de Clases y Relación de Ganancia: Lograron alta precisión decidida pero marcaron una gran proporción de instancias (71% y 58% respectivamente), resultando en menor eficiencia.
• Bootstrap de Nodo: Funcionó bien pero fue computacionalmente costoso y se excluyó de conjuntos de datos con $N > 20,000$.

Análisis Teórico (Benchmarks de Breiman)

En conjuntos de datos sintéticos con errores de Bayes conocidos:

• Margen: Mostró un comportamiento de auto-calibración en datos geométricamente limpios, marcando muy pocas instancias como inciertas (relaciones U/B < 0.5), comportándose efectivamente como CART cuando el límite es claro.
• Bootstrap de Nodo y Meseta de Calidad: Mostraron calibración proporcional, marcando más instancias en conjuntos de datos más difíciles (mayor error de Bayes), aunque todos los métodos marcaron en exceso en relación con el error de Bayes teórico (U/B > 1).
• Brecha de Calibración: Ningún método logró una relación U/B de 1.0, lo que indica que la incertidumbre del umbral local no corresponde directamente al error de Bayes global.

Aplicaciones de Dominio

• Mamografía: El Bootstrap de Nodo marcó el 10.8% de los casos como inciertos mientras mejoraba la precisión decidida en un 0.71% sobre CART. Esto es valioso para identificar casos que necesitan revisión secundaria.
• Diabetes: El Bootstrap de Nodo logró una ganancia de precisión del +9.8% pero marcó al 63.4% de los pacientes, sugiriendo una compensación entre precisión y tasa de señalización. El método de Margen ofreció un punto de operación más conservador y práctico (+0.4% de ganancia, 9.5% de señalización).
• Limitaciones: En el pequeño conjunto de datos de enfermedad cardíaca de Cleveland ($N=303$), el Bootstrap de Nodo tuvo un rendimiento inferior debido a estimaciones de varianza poco fiables. En el conjunto de datos de crédito alemán, el método de Margen tuvo un rendimiento inferior al de la línea base, sugiriendo limitaciones con interacciones complejas de características económicas.

Significado y Afirmaciones

El artículo afirma establecer el árbol ternario como un primitivo principista para la clasificación consciente de la incertidumbre. Su significado radica en:

• Utilidad Práctica: Proporcionar un mecanismo para marcar predicciones inseguras en el límite sin abstenerse, permitiendo que los sistemas aguas abajo (por ejemplo, cribado médico, suscripción de crédito) apliquen estrategias de manejo diferentes.
• Tractabilidad Computacional: Derivar zonas de incertidumbre de estadísticas de división existentes sin requerir datos externos ni reentrenamiento complejo.
• Fundamentación Teórica: Ofrecer un marco donde el veredicto "Indec" es un calificador sobre la confianza de la predicción en lugar de un rechazo de la predicción en sí misma.

Los autores notan modestamente que, aunque los métodos mejoran la precisión decidida, aún no calibran perfectamente la tasa de señalización al error de Bayes teórico, identificando esta calibración como un problema abierto concreto para trabajos futuros.