Czy suma dwóch drzew decyzyjnych jest równoważna pojedynczemu drzewu decyzyjnemu?

Załóżmy, że mamy dwóch drzew regresji (drzewie i drzewa B) odwzorowanych wejściowe do wyjścia . Niech w drzewie i na drzewa B. Każde drzewo wykorzystuje dzieli binarnej hiperplaszczyzn jako funkcji oddzielających. $x \in \mathbb{R}^d$ $\hat{y} \in \mathbb{R}$ $\hat{y} = f_A(x)$ $f_B(x)$

Załóżmy teraz, że bierzemy sumę ważoną wyników drzewa:

{fa}_{do} (x) = w_{ZA} {fa}_{ZA} (x) + w_{b} {fa}_{b} (x)

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

Czy funkcja równoważna pojedynczemu (głębszemu) drzewu regresji? $f_C$ Jeśli odpowiedź brzmi „czasami”, to na jakich warunkach?

Idealnie chciałbym zezwolić na skośne hiperpłaszczyzny (tj. Podziały wykonywane na liniowych kombinacjach cech). Ale zakładając, że podziały jednej funkcji mogą być w porządku, jeśli jest to jedyna dostępna odpowiedź.

Przykład

Oto dwa drzewa regresji zdefiniowane w przestrzeni wejściowej 2d:

Rysunek pokazuje, w jaki sposób każde drzewo dzieli przestrzeń wejściową i dane wyjściowe dla każdego regionu (zakodowane w skali szarości). Kolorowe liczby wskazują obszary przestrzeni wejściowej: 3,4,5,6 odpowiadają węzłom liści. 1 to połączenie 3 i 4 itd.

Załóżmy teraz, że uśredniamy wydajność drzew A i B:

Średnia wydajność jest wykreślona po lewej stronie, z nałożonymi granicami decyzyjnymi drzew A i B. W takim przypadku możliwe jest skonstruowanie pojedynczego, głębszego drzewa, którego wynik jest równy średniej (wykreślony po prawej stronie). Każdy węzeł odpowiada regionowi przestrzeni wejściowej, który można zbudować z obszarów zdefiniowanych przez drzewa A i B (oznaczone kolorowymi liczbami na każdym węźle; wiele liczb oznacza przecięcie dwóch regionów). Pamiętaj, że to drzewo nie jest unikalne - moglibyśmy zacząć budować z drzewa B zamiast z drzewa A.

Ten przykład pokazuje, że istnieją przypadki, w których odpowiedź brzmi „tak”. Chciałbym wiedzieć, czy to zawsze prawda.

regression machine-learning cart

— user20160
źródło

Hmm .. Gdyby tak było, to dlaczego mielibyśmy trenować losowy las? (Ponieważ wyraźnie liniową kombinację 500 drzew można ponownie wyrazić jako 499 ważonych parami 500 drzew) Ładne pytanie, +1.

— usεr11852 mówi Przywróć Monic

interesujące pytanie! Zakładam, że przestrzeń hipotetyczna drzew decyzyjnych i zespołów drzew decyzyjnych (wzmocnienie, liniowa kombinacja drzew) jest taka sama. Nie mogę się doczekać odpowiedzi ..

— Laksan Nathan

@ usεr11852 Może dlatego, że użycie jednego bardzo dużego drzewa zamiast lasu jest o wiele wolniejsze? Podobnie jak w sieciach neuronowych, sieci z jedną ukrytą warstwą mogą już przybliżać wszystkie funkcje ciągłe, ale dodanie warstw przyspiesza sieć. Nie mówię, że tak jest tutaj, ale może tak być.

— Harto Saarinen

@ HartoSaarinen: To ciekawy sposób myślenia o tym, ale podejrzewam, że nie jest to łatwe. Przyjmuje się, że bardzo głębokie drzewa mogą słabo się dopasowywać i słabo uogólniać (ich prognozy są również dość niestabilne). Ponadto (pod względem prędkości) głębsze drzewa wymagają wykładniczo większej liczby podziałów, a tym samym dłuższego czasu szkolenia. (Drzewo o głębokości 10 ma co najwyżej 1023 podziałów, ale drzewo o głębokości 20, 1048575 dzieli. Dużo więcej pracy!)

— mówi usεr11852 Przywróć Monic

@ usεr11852 Zgadzam się, że to może być całkowicie nieprawdziwe, a odpowiedź może być zupełnie inna. To właśnie sprawia, że pole jest tak interesujące w tej chwili, wiele rzeczy do odkrycia!

— Harto Saarinen

Tak, ważona suma drzew regresji jest równoważna pojedynczemu (głębszemu) drzewu regresji.

Uniwersalny aproksymator funkcji

Drzewo regresji jest uniwersalnym aproksymatorem funkcji (patrz np. Cstheory ). Większość badań nad przybliżeniami funkcji uniwersalnych odbywa się na sztucznych sieciach neuronowych z jedną ukrytą warstwą (przeczytaj ten świetny blog). Jednak większość algorytmów uczenia maszynowego jest przybliżeniem funkcji uniwersalnych.

Bycie uniwersalnym aproksymatorem funkcji oznacza, że dowolna dowolna funkcja może być w przybliżeniu reprezentowana. Zatem bez względu na stopień złożoności funkcji uniwersalne przybliżenie funkcji może reprezentować ją z dowolną pożądaną precyzją. W przypadku drzewa regresji można sobie wyobrazić nieskończenie głębokie. To nieskończenie głębokie drzewo może przypisać dowolną wartość do dowolnego punktu w przestrzeni.

Ponieważ ważona suma drzewa regresji jest kolejną arbitralną funkcją, istnieje inne drzewo regresji, które reprezentuje tę funkcję.

Algorytm do utworzenia takiego drzewa

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

Poniższy przykład pokazuje dwa proste drzewa dodane o wadze 0,5. Zauważ, że jeden węzeł nigdy nie zostanie osiągnięty, ponieważ nie istnieje liczba mniejsza niż 3 i większa niż 5. Oznacza to, że drzewa te można ulepszyć, ale nie powoduje to ich nieprawidłowości.

Po co używać bardziej złożonych algorytmów

W usłudze @ usεr11852 w komentarzach pojawiło się interesujące dodatkowe pytanie: dlaczego mielibyśmy używać algorytmów wspomagających (lub w rzeczywistości dowolnego złożonego algorytmu uczenia maszynowego), gdyby każdą funkcję można było modelować za pomocą prostego drzewa regresji?

Drzewa regresji mogą faktycznie reprezentować dowolną funkcję, ale jest to tylko jedno kryterium dla algorytmu uczenia maszynowego. Inną ważną właściwością jest to, jak dobrze się uogólniają. Drzewa o głębokiej regresji są podatne na nadmierne dopasowanie, tj. Nie generalizują się dobrze. Losowy las uśrednia wiele głębokich drzew, aby temu zapobiec.

— Pieter
źródło