Resumen Técnico: Árbol de Particiones: Estimación de Densidad Condicional sobre Espacios de Resultados Generales

Enunciado del Problema

Los árboles de decisión son ampliamente valorados por su interpretabilidad y eficiencia en la predicción puntual (clasificación y regresión). Sin embargo, extender los métodos basados en árboles a la estimación de densidad condicional sobre espacios de resultados generales (que soportan variables continuas y categóricas simultáneamente) sigue siendo un desafío. Los enfoques existentes enfrentan limitaciones específicas:

• Suposiciones Paramétricas: Métodos como CADET emplean densidades condicionales paramétricas en los nodos hoja, lo cual puede no capturar distribuciones complejas y no gaussianas.
• Escalabilidad: Métodos como CDTree, que optimizan conjuntamente las divisiones y los histogramas nodo a nodo, pueden ser computacionalmente exigentes, limitando su aplicabilidad a conjuntos de datos grandes.
• Formulación Unificada: Existe una falta de un marco unificado que trate la clasificación y la regresión como casos específicos de estimación de densidad condicional sin imponer restricciones paramétricas sobre la distribución objetivo.

Metodología

1. Marco Teórico: Formulación Basada en la Teoría de la Medida

Los autores proponen el Árbol de Particiones, un marco fundamentado en la teoría de la medida.

• Particionamiento del Espacio Conjunto: A diferencia de los árboles tradicionales que particionan solo el espacio de covariables $X$, el Árbol de Particiones construye una partición $\pi_N$ adaptativa a los datos del espacio conjunto de covariables y resultados $Z = X \times Y$.
• Estimación Constante a Trozos: La densidad condicional $f(y|x)$ se modela como una función constante a trozos definida sobre estas particiones.
• Derivada de Radon–Nikodym: El método define la densidad condicional mediante la derivada de Radon–Nikodym con respecto a una medida producto $\nu = P_X \otimes \mu_Y$, donde $\mu_Y$ es una medida de referencia (medida de conteo para resultados discretos, Lebesgue para continuos).
• Estimador: Para una celda $A = A_X \times A_Y$ en la partición, la estimación de densidad es:
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  donde $n_{XY}$ y $n_X$ son conteos empíricos. Esta formulación maneja naturalmente resultados de tipo mixto y permite que la clasificación y la regresión surjan como casos especiales.

2. Algoritmo de Construcción del Árbol

El árbol se desarrolla utilizando una estrategia voraz, mejor primero que minimiza directamente la log-verosimilitud condicional negativa.

• Objetivo: El criterio de división maximiza la ganancia empírica en la pérdida logarítmica:
  $$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$
• Tipos de División:
  • Divisiones de Covariables ($X$): Refinan el espacio de covariables (divisiones estándar de árboles).
  • Divisiones de Resultados ($Y$): Refinan los contenedores de resultados dentro de una región de covariables fija. Esto permite que el árbol construya histogramas adaptativos para la distribución de resultados.
• Eficiencia: El algoritmo utiliza técnicas eficientes de ordenación y suma de prefijos para evaluar divisiones candidatas en un tiempo $O(d_Z N \log N)$ (o $O(d_Z N \log^2 N)$ para árboles equilibrados), igualando la escalabilidad del CART estándar.
• Truncamiento: Para resultados continuos no acotados, el método emplea un truncamiento dependiente de los datos (caja min-max) para asegurar una medida finita, con garantías teóricas de que el truncamiento captura asintóticamente toda la masa de probabilidad.

3. Bosque de Particiones

Para mejorar la estabilidad y el rendimiento predictivo, los autores introducen el Bosque de Particiones, un método de conjunto. Promedia las estimaciones de densidad condicional de múltiples Árboles de Particiones entrenados en muestras bootstrap (bagging), opcionalmente con muestreo aleatorio de características.

4. Garantías Teóricas

El artículo establece condiciones suficientes para la consistencia en $L^1(\nu)$ del estimador. La consistencia está garantizada si la secuencia de particiones satisface:

1. El número de celdas crece sublinealmente en relación con $N$.
2. La función de crecimiento de la familia de particiones satisface límites específicos de dimensión VC.
3. El diámetro de las celdas se reduce a cero.
4. El número de proyecciones distintas de covariables crece lo suficientemente lento en relación con $\sqrt{\log N / N}$.

Contribuciones Clave

1. Marco Unificado: Un único marco no paramétrico para la estimación de densidad condicional que maneja resultados continuos, categóricos y de tipo mixto sin suposiciones paramétricas.
2. Optimización Directa: Un algoritmo de construcción de árboles que optimiza directamente la pérdida logarítmica condicional mediante una búsqueda voraz mejor primero, evitando los cuellos de botella computacionales de la optimización conjunta de división-histograma encontrados en trabajos anteriores.
3. Escalabilidad: Una implementación con complejidad computacional comparable al CART estándar, haciéndola viable para conjuntos de datos grandes.
4. Extensión de Conjunto: La introducción del Bosque de Particiones, que demuestra una mejora en la predicción probabilística sobre árboles individuales.
5. Análisis Teórico: Pruebas rigurosas de consistencia para el estimador propuesto bajo suposiciones estándar de complejidad y reducción.

Resultados Experimentales

Los autores evaluaron el Árbol de Particiones y el Bosque de Particiones en un conjunto diverso de benchmarks de clasificación y regresión, comparándolos con CART, Bosques Aleatorios, CADET y CDTree.

• Clasificación:
  • Árboles Individuales: El Árbol de Particiones superó a CART en la mayoría de los conjuntos de datos (8 de 9) en términos de pérdida logarítmica.
  • Conjuntos: El Bosque de Particiones logró una pérdida logarítmica menor que los Bosques Aleatorios en la mayoría de los conjuntos de datos, demostrando una calibración probabilística superior.
• Regresión:
  • Árboles Individuales: El Árbol de Particiones proporcionó predicciones puntuales competitivas y un fuerte rendimiento probabilístico. Notablemente, superó al CADET paramétrico en conjuntos de datos más grandes (por ejemplo, Air, Power, California, Protein), sugiriendo una mejor escalabilidad y adaptabilidad al tamaño de la muestra.
  • Conjuntos: El Bosque de Particiones superó consistentemente a los Bosques Aleatorios en la mayoría de los benchmarks de regresión (8 de 10) en cuanto a pérdida logarítmica.
• Robustez:
  • Ruido: El método mostró robustez ante ruido tanto homoscedástico como heteroscedástico, con una degradación del rendimiento comparable a CDTree y una estabilidad mejor que CADET.
  • Características Redundantes: Mientras que CDTree mostró una estabilidad ligeramente mejor contra la duplicación de características correlacionadas, el Árbol de Particiones produjo predicciones más consistentes (menor varianza) bajo corrupción de características en comparación con CADET.
• Eficiencia: Las comparaciones de tiempo de ejecución en el conjunto de datos Physicochemical Protein mostraron que el Árbol de Particiones es aproximadamente 5$\times$ más rápido que CADET y 25$\times$ más rápido que CDTree en $N=10,000$.

Significado y Afirmaciones

El artículo afirma que el Árbol de Particiones ofrece una alternativa no paramétrica escalable a los métodos probabilísticos basados en árboles existentes. Su principal significado radica en:

• Flexibilidad: La capacidad de modelar distribuciones condicionales complejas sobre espacios de resultados generales sin asumir una forma paramétrica específica (por ejemplo, Gaussiana).
• Interpretabilidad: Mantener la interpretabilidad intrínseca de los árboles de decisión (mediante la importancia de características basada en ganancia y la visualización de densidad constante a trozos) mientras se proporcionan salidas probabilísticas completas.
• Rendimiento: Demostrar empíricamente que los conjuntos de árboles basados en densidad no paramétricos pueden superar tanto a los conjuntos tradicionales de predicción puntual (Bosques Aleatorios) como a los árboles basados en densidad paramétricos (CADET), particularmente a medida que aumenta el tamaño del conjunto de datos.

Los autores posicionan al Árbol de Particiones como un candidato natural para la integración en pipelines de inferencia causal y otras aplicaciones que requieren estimación de densidad condicional flexible, reconociendo al mismo tiempo que el trabajo futuro podría explorar marcos de impulso (boosting) y estrategias de poda personalizadas.