Árboles de regresión y optimización

Introducción


Fig 1. Función objetivo a modelar (izquierda) y un modelo basado en medias locales (derecha)

Esta presentación introduce dos métodos para aprender/aproximar funciones: (1) Classification and Regression Trees (CARTs) y (2) Convex Partition (CP). Ambos están basados en árboles y comparten el mismo esquema algorítmico, que consiste en dividir progresivamente el dominio en subconjuntos que mapean a valores más homogéneos (Fig. 1).

La única diferencia entre CART y CP es el criterio utilizado para seleccionar el siguiente subconjunto a explorar y partir. CART explora y modela las regiones de mayor incertidumbre, lo que reduce el error entre el modelo (árbol) y la función original. Por otro lado, CP prioriza los subconjuntos que tienen potencial de contener el óptimo global. El algoritmo CP ha sido utilizado con éxito como un método de black-box optimization.


Ejemplo ilustrativo. Considérense los problemas de aproximar y optimizar la función esfera, ilustrada en las Fig. 2-3 y formalmente definida como:
Fig 2. Superficie de la función f Fig 3. Curvas de nivel de f

El algoritmo


Tiempo de animación (segundos):
Modo de selección:
// Sea S una colección de subconjuntos S = { s=(El espacio de búsqueda entero) } // El proceso interativo de partición FOR each (iteration) DO: Seleccionar un subconjunto s de S, y muestrea en él Explorar diferentes formas de dividir s Guardar en S los subconjuntos mejor divididos END FOR

¿Cómo se encontró la partición más homogénea?

Existen mútiples particiones que se pueden definir para dividir una muestra. Cada partición está definida por dos parámetros: el eje y la proporción. Para encontrar la mejor partición, todas particiones posibles son evaluadas usando la suma del error cuadrático como medida de homogeneidad.

Usando los controles siguientes, explore cómo diferentes parámetros definen particiones con errores distintos.
Partir en eje :
Proporción:

¿Cómo seleccionar el siguiente subconjunto a explorar?

La única diferencia entre CART y CP es el criterio usado para seleccionar qué subconjunto debería ser el siguiente en ser muestreado y dividido. CART selecciona los subconjuntos con mayor incertidumbre, por otro lado, CP selecciona los subconjuntos qué son más prometedores de contener el mínimo global. Formalmente,