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 y ∈ R . Niech Y = F A ( x ) w drzewie i F B ( x ) 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:

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.

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.