La somme de deux arbres de décision est-elle équivalente à un seul arbre de décision?

Supposons que nous ayons deux arbres de régression (arbre A et B) que l' arbre d' entrée de carte de sortie y ∈ R . Soit y = f A ( x ) de l' arbre A et f B ( x ) de l' arbre B. Chaque arbre utilise fentes binaire, avec des hyperplans que les fonctions de séparation.$x \in \mathbb{R}^d$$\hat{y} \in \mathbb{R}$$\hat{y} = f_A(x)$$f_B(x)$

Supposons maintenant que nous prenons une somme pondérée des sorties d'arbre:

La fonction équivalente à un seul arbre de régression (plus profond)? $f_C$Si la réponse est "parfois", dans quelles conditions?

Idéalement, je voudrais autoriser les hyperplans obliques (c'est-à-dire les divisions effectuées sur des combinaisons linéaires de caractéristiques). Mais, en supposant que les fractionnements à fonctionnalité unique pourraient être corrects si c'est la seule réponse disponible.

Exemple

Voici deux arbres de régression définis sur un espace d'entrée 2D:

La figure montre comment chaque arborescence partitionne l'espace d'entrée et la sortie de chaque région (codée en niveaux de gris). Les nombres en couleur indiquent les régions de l'espace d'entrée: 3,4,5,6 correspondent aux nœuds foliaires. 1 est l'union de 3 & 4, etc.

Supposons maintenant que nous faisons la moyenne de la sortie des arbres A et B:

Le rendement moyen est tracé sur la gauche, avec les limites de décision des arbres A et B superposées. Dans ce cas, il est possible de construire un arbre unique, plus profond dont la sortie est équivalente à la moyenne (tracé à droite). Chaque nœud correspond à une région d'espace d'entrée qui peut être construite à partir des régions définies par les arbres A et B (indiquées par des nombres colorés sur chaque nœud; plusieurs nombres indiquent l'intersection de deux régions). Notez que cet arbre n'est pas unique - nous aurions pu commencer à construire à partir de l'arbre B au lieu de l'arbre A.

Cet exemple montre qu'il existe des cas où la réponse est "oui". J'aimerais savoir si c'est toujours vrai.

Oui, la somme pondérée d'un arbre de régression équivaut à un seul arbre de régression (plus profond).

Approximateur de fonction universel

Un arbre de régression est un approximateur de fonction universel (voir par exemple cstheory ). La plupart des recherches sur les approximations des fonctions universelles sont effectuées sur des réseaux de neurones artificiels avec une couche cachée (lire ce grand blog). Cependant, la plupart des algorithmes d'apprentissage automatique sont des approximations de fonctions universelles.

Être un approximateur de fonction universelle signifie que toute fonction arbitraire peut être approximativement représentée. Ainsi, quelle que soit la complexité de la fonction, une approximation de la fonction universelle peut la représenter avec la précision souhaitée. Dans le cas d'un arbre de régression, vous pouvez imaginer un arbre infiniment profond. Cet arbre infiniment profond peut attribuer n'importe quelle valeur à n'importe quel point de l'espace.

Puisqu'une somme pondérée d'un arbre de régression est une autre fonction arbitraire, il existe un autre arbre de régression qui représente cette fonction.

Un algorithme pour créer un tel arbre

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

L'exemple ci-dessous montre deux arbres simples qui sont ajoutés avec un poids de 0,5. Notez qu'un nœud ne sera jamais atteint, car il n'existe pas un nombre inférieur à 3 et supérieur à 5. Cela indique que ces arbres peuvent être améliorés, mais cela ne les rend pas invalides.

Pourquoi utiliser des algorithmes plus complexes

@ Usεr11852 a soulevé une question supplémentaire intéressante dans les commentaires: pourquoi utiliserions-nous des algorithmes de renforcement (ou en fait un algorithme d'apprentissage automatique complexe) si chaque fonction peut être modélisée avec un arbre de régression simple?

Les arbres de régression peuvent en effet représenter n'importe quelle fonction mais ce n'est qu'un critère pour un algorithme d'apprentissage automatique. Une autre propriété importante est la façon dont ils se généralisent. Les arbres de régression profonde ont tendance à sur-ajuster, c'est-à-dire qu'ils ne se généralisent pas bien. Une forêt aléatoire fait en moyenne beaucoup d'arbres profonds pour éviter cela.