A soma de duas árvores de decisão é equivalente a uma única árvore de decisão?

Suponhamos que temos duas árvores de regressão (árvore A e B) que árvore mapa de entrada a saída . Vamos para a árvore A e para a árvore B. Cada árvore utiliza separações binárias, com hiperplanos como as funções de separação. $x \in \mathbb{R}^d$ $\hat{y} \in \mathbb{R}$ $\hat{y} = f_A(x)$ $f_B(x)$

Agora, suponha que tomemos uma soma ponderada das saídas da árvore:

f_{C} (x) = W_{UMA} f_{UMA} (x) + W_{B} f_{B} (x)

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

A função equivalente a uma única árvore de regressão (mais profunda)? $f_C$ Se a resposta for "às vezes", em que condições?

Idealmente, eu gostaria de permitir hiperplanos oblíquos (ou seja, divisões realizadas em combinações lineares de recursos). Mas, supondo que as divisões de recurso único possam ser aceitáveis se essa for a única resposta disponível.

Exemplo

Aqui estão duas árvores de regressão definidas em um espaço de entrada 2D:

A figura mostra como cada árvore particiona o espaço de entrada e a saída para cada região (codificada em escala de cinza). Os números coloridos indicam regiões do espaço de entrada: 3,4,5,6 correspondem aos nós das folhas. 1 é a união de 3 e 4, etc.

Agora, suponha que calculemos a média das saídas das árvores A e B:

A produção média é plotada à esquerda, com os limites de decisão das árvores A e B sobrepostos. Nesse caso, é possível construir uma árvore única e mais profunda, cuja saída é equivalente à média (plotada à direita). Cada nó corresponde a uma região do espaço de entrada que pode ser construída a partir das regiões definidas pelas árvores A e B (indicadas por números coloridos em cada nó; vários números indicam a interseção de duas regiões). Observe que essa árvore não é única - poderíamos ter começado a construir a partir da árvore B em vez da árvore A.

Este exemplo mostra que existem casos em que a resposta é "sim". Eu gostaria de saber se isso sempre é verdade.

regression machine-learning cart user20160
fonte

Hmm .. Se fosse esse o caso, por que treinaríamos uma floresta aleatória? (Como claramente a combinação linear de 500 árvores pode ser re-expressa como 499 somas ponderadas em pares de 500 árvores) Boa pergunta, +1.

usεr11852 diz Reinstate Monic 23/03

pergunta interessante! Eu assumiria que o espaço de hipótese das árvores de decisão e dos conjuntos de árvores de decisão (combinação linear e dinâmica de árvores) é o mesmo. Ansioso por uma resposta ..

Laksan Nathan 23/03

@ usεr11852 Talvez porque usar uma única árvore muito grande em vez de floresta seja muito mais lento? Assim como nas redes neurais, as redes de uma camada oculta já podem aproximar todas as funções contínuas, mas a adição de camadas torna a rede mais rápida. Não estou dizendo que este é o caso aqui, mas pode ser.

Harto Saarinen 24/03

@HartoSaarinen: Esta é uma maneira interessante de pensar sobre isso, mas eu suspeito que não é fácil. Aceita-se que árvores muito profundas possam se ajustar demais e generalizar mal (suas previsões também são bastante instáveis). Além disso (em relação às considerações de velocidade), árvores mais profundas exigem exponencialmente mais divisões e, portanto, mais tempo de treinamento. (A árvore da profundidade 10 tem no máximo 1023 splits, mas uma árvore de profundidade 20, 1048575 splits Muito mais trabalho.!)

usεr11852 diz Reintegrar Monic

@ usεr11852 Concordo que pode ser totalmente falso e a resposta pode ser algo totalmente diferente. É isso que torna o campo tão interessante neste momento, super muitas coisas a serem descobertas!

Harto Saarinen

Sim, a soma ponderada de uma árvore de regressão é equivalente a uma única árvore de regressão (mais profunda).

Aproximador de função universal

Uma árvore de regressão é um aproximador de função universal (veja, por exemplo, a história ). A maioria das pesquisas sobre aproximações de funções universais é feita em redes neurais artificiais com uma camada oculta (leia este ótimo blog). No entanto, a maioria dos algoritmos de aprendizado de máquina são aproximações de funções universais.

Ser um aproximador universal de funções significa que qualquer função arbitrária pode ser representada aproximadamente. Assim, não importa quão complexa seja a função, uma aproximação universal de função pode representá-la com a precisão desejada. No caso de uma árvore de regressão, você pode imaginar uma infinitamente profunda. Essa árvore infinitamente profunda pode atribuir qualquer valor a qualquer ponto do espaço.

Como uma soma ponderada de uma árvore de regressão é outra função arbitrária, existe outra árvore de regressão que representa essa função.

Um algoritmo para criar essa árvore

$T_1$ $T_2$ $T_2$ $T1$ $T1$ $T2$

O exemplo abaixo mostra duas árvores simples que são adicionadas com peso 0,5. Observe que um nó nunca será alcançado, porque não existe um número menor que 3 e maior que 5. Isso indica que essas árvores podem ser aprimoradas, mas não as tornam inválidas.

Por que usar algoritmos mais complexos

Uma pergunta adicional interessante foi levantada por @ usεr11852 nos comentários: por que usaríamos algoritmos de reforço (ou de fato qualquer algoritmo complexo de aprendizado de máquina) se todas as funções podem ser modeladas com uma simples árvore de regressão?

As árvores de regressão podem realmente representar qualquer função, mas esse é apenas um critério para um algoritmo de aprendizado de máquina. Uma outra propriedade importante é o quão generalizadas elas são. Árvores de regressão profunda são propensas a sobreajuste, ou seja, elas não generalizam bem. Uma floresta aleatória calcula a média de muitas árvores profundas para evitar isso.

Pieter
fonte

A soma de duas árvores de decisão é equivalente a uma única árvore de decisão?

Respostas: