¿Cuál es la dimensión VC de un árbol de decisión?

¿Cuál es la dimensión VC de un árbol de decisión con k divisiones en dos dimensiones? Digamos que el modelo es CART y las únicas divisiones permitidas son paralelas a los ejes.

Entonces, para una división, podemos ordenar 3 puntos en un triángulo y luego, para cualquier etiquetado de los puntos, podemos obtener una predicción perfecta (es decir, puntos rotos)

Pero, ¿qué pasa con 2 divisiones, o cualquier k general?

No estoy seguro de que esta sea una pregunta con una respuesta simple, ni creo que sea una pregunta que incluso deba hacerse sobre los árboles de decisión.

Consulte a Aslan et al. , Cálculo de la dimensión VC de los árboles (2009). Abordan este problema haciendo una búsqueda exhaustiva, en árboles pequeños, y luego proporcionando una fórmula aproximada y recursiva para estimar la dimensión VC en árboles más grandes. Luego usan esta fórmula como parte de un algoritmo de poda. Si hubiera habido una respuesta de forma cerrada a su pregunta, estoy seguro de que la habrían proporcionado. Sintieron la necesidad de atravesar incluso árboles bastante pequeños.

$d$$2^d$$2^d$$d$$2^d$$2^d$respuestas Pero nadie se adapta a árboles completos. Por lo general, se sobreajusta y luego se poda con validación cruzada. Lo que obtienes al final es un árbol más pequeño y simple, pero tu conjunto de hipótesis aún es grande. Aslan y col. Trate de estimar la dimensión VC de las familias de árboles isomórficos. Cada familia es una hipótesis establecida con su propia dimensión VC.

$d=3$$(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$$x1$$x2$

La solución de fuerza bruta de Aslan parece funcionar bastante bien, pero lo que obtienen no es realmente la dimensión VC de los algoritmos que usa la gente, ya que estos se basan en la poda y la validación cruzada. Es difícil decir cuál es el espacio de hipótesis en realidad, ya que, en principio, comenzamos con un gran número de árboles posibles, pero luego podemos volver a algo más razonable. Incluso si alguien comienza con una elección a priori de no ir más allá de dos capas, digamos, todavía puede ser necesario podar el árbol. Y realmente no necesitamos la dimensión VC, ya que la validación cruzada va directamente después del error fuera de la muestra.

Para ser justos con Aslan et al., No usan la dimensión VC para caracterizar su espacio de hipótesis. Calculan la dimensión VC de las ramas y usan esa cantidad para determinar si la rama debe cortarse. En cada etapa, utilizan la dimensión VC de la configuración específica de la rama bajo consideración. No miran la dimensión VC del problema en su conjunto.

Si sus variables son continuas y la respuesta depende de alcanzar un umbral, entonces un árbol de decisión básicamente está creando un grupo de perceptrones, por lo que la dimensión VC probablemente sea mayor que eso (ya que debe estimar el punto de corte para hacer la división) . Si la respuesta depende monotónicamente de una respuesta continua, CART la dividirá en varios pasos, intentando recrear un modelo de regresión. No usaría árboles en ese caso, posiblemente gam o regresión.