Es la suma de dos árboles de decisión equivalente a la de un árbol de decisión?

Question

Supongamos que tenemos dos árboles de regresión (árbol, y el árbol B) que el mapa de entrada de $x \in \mathbb{R}^d$ salida $\hat{y} \in \mathbb{R}$. Deje $\hat{y} = f_A(x)$ para el árbol de Un y $f_B(x)$ para el árbol B. Cada árbol binario utiliza divisiones, con hyperplanes como la separación de funciones.

Ahora, supongamos que tomamos una suma ponderada de el árbol de salidas:

$$f_C(x) = w_A \ f_A(x) + w_B \ f_B(x)$$

Es la función de $f_C$ equivalente a una sola (más profundo) de árbol de regresión? Si la respuesta es "a veces", entonces bajo qué condiciones?

Idealmente, me gustaría para permitir oblicuo hyperplanes (es decir, se divide a cabo en las combinaciones lineales de funciones). Pero, suponiendo que la función única se divide podría estar bien si esa es la única respuesta disponible.

Ejemplo

Aquí hay dos árboles de regresión se define en 2d espacio de entrada:

La figura muestra cómo cada uno de los árboles de particiones del espacio de entrada, y la salida para cada región (codificado en escala de grises). Números de colores indican las regiones del espacio de entrada: 3,4,5,6 corresponden a los nodos hoja. 1 es la unión de 3 y 4, etc.

Ahora supongamos que el promedio de la salida de los árboles a y B:

El promedio de salida se representa a la izquierda, con la decisión de los límites de los árboles a y B superpuesta. En este caso, es posible construir una sola, más profundo árbol cuya salida es equivalente a la media (que se trazan en el derecho). Cada nodo corresponde a una región del espacio de entrada que puede ser construido a partir de las regiones definidas por los árboles a y B (indicado por los números de colores en cada nodo; varios números indican la intersección de dos regiones). Tenga en cuenta que este árbol no es única, podríamos haber empezado la construcción de árbol B en lugar de árbol A.

Este ejemplo muestra que existen casos donde la respuesta es "sí". Me gustaría saber si esto es siempre cierto.

Answer 1

Sí, la suma ponderada de los árboles de regresión es equivalente a una sola (más profundo) de árbol de regresión.

Función Universal approximator

Un árbol de regresión es una función universal approximator (ver, por ejemplo, cstheory). La mayoría de la investigación en función universal aproximaciones se realiza en artificial redes neuronales con una capa oculta (leído este gran blog). Sin embargo, la mayoría de los algoritmos de aprendizaje automático son universales función de aproximaciones.

Siendo una función universal approximator significa que cualquier función arbitraria puede ser aproximadamente representados. Por lo tanto, no importa lo complejo que se obtiene la función, una función universal aproximación puede representar con cualquier precisión deseada. En el caso de un árbol de regresión se puede imaginar un ser infinitamente profundo. Esta infinitamente profundo árbol puede asignar cualquier valor a cualquier punto en el espacio.

Desde una suma ponderada de un árbol de regresión es otra función arbitraria, existe otro árbol de regresión que representa esa función.

Un algoritmo para crear un árbol

Sabiendo que el tal árbol de existir es grande. Pero también queremos una receta para crear. Tal y algoritmo de combinar dos árboles de $T_1$ $T_2$ y crear uno nuevo. Una solución es copiar-pegar $T_2$ en cada nodo hoja de $T1$. El valor de salida de los nodos hoja del árbol es la suma ponderada de las nodo hoja de $T1$ (en algún lugar en el medio del árbol) y el nodo de hoja de $T2$.

El ejemplo siguiente muestra dos simples árboles que se agregan con el peso de 0.5. Tenga en cuenta que un nodo no se llegue nunca, porque no existe un número que es menor que 3 y más de 5. Esto indica que estos árboles pueden ser mejoradas, pero no la convierte en inválida.

¿Por qué utilizar algoritmos más complejos

Una interesante pregunta adicional fue planteada por @user11852 en los comentarios: ¿por qué hemos de impulsar el uso de algoritmos (o de hecho cualquier máquina compleja algoritmo de aprendizaje) si cada función puede ser modelada con un simple árbol de regresión?

Los árboles de regresión de hecho puede representar cualquier función, pero que es sólo uno de los criterios para una máquina algoritmo de aprendizaje. Una otra propiedad importante es lo bien que generalizar. Profundo de los árboles de regresión son propensos a sobreajuste, es decir, que no generalicen. Un bosque aleatorio de los promedios de los lotes de profundas de los árboles para evitar esto.