Jak od podstaw zbudować drzewo regresyjne

W poprzednim artykule zbudowaliśmy klasyfikator oparty na drzewie decyzyjnym, który przewidywał, czy pacjent ma chorobę serca. Drzew decyzyjnych można też używać do regresji: zamiast kategorii przewidują wtedy liczbę — pensję, temperaturę albo cenę domu. W tym artykule weźmiemy zbiór Hitters i zbudujemy drzewo, które przewiduje pensję zawodnika na podstawie liczby rozegranych sezonów i trafień w poprzednim sezonie.

W klasyfikatorze każdy podział wybierały nieczystość Giniego i przyrost informacji. W regresji zastępujemy nieczystość Giniego wariancją. Zamiast pytać, jak bardzo wymieszane są etykiety, pytamy, jak rozrzucone są wartości docelowe. Dobry podział zmniejsza ten rozrzut, który będziemy mierzyć jako spadek całkowitego błędu kwadratowego.

Kryterium podziału i wartość przechowywana w liściu to dwie strony tej samej decyzji. Nieczystość węzła jest błędem treningowym odpowiedzi, którą dałby jego liść. Gini mierzy koszt przewidywania proporcji klas dla grupy etykiet; wariancja mierzy koszt przewidywania średniej dla grupy pensji. Gdy zmienia się predykcja liścia, musi się też zmienić właściwa miara błędu.

Generowanie kandydatów, rekurencyjne dzielenie i reguła stopu pozostają bez zmian. Zmienić trzeba tylko obliczanie nieczystości i predykcję liścia.

Pokażemy też ograniczenie, które ujawnia się dopiero wtedy, gdy celem jest liczba. Każda odpowiedź drzewa regresyjnego jest średnią pensji z danych treningowych. Niezależnie więc od liczby sezonów czy trafień drzewo nie przewidzi pensji wyższej niż najwyższa w zbiorze treningowym. Klasyfikator nie ma takiego problemu: odpowiada etykietami, a poza etykietą nie istnieje żadne „dalej”. Liczby mają ciąg dalszy, lecz drzewo nie potrafi do niego dotrzeć.

Ten sam mechanizm

Algorytmem nadal jest CART: binarne drzewo, w którym każdy węzeł zadaje jedno pytanie typu tak–nie i ma dokładnie dwoje dzieci. Podczas budowy generujemy pytania kandydujące, zadajemy każde z nich wszystkim wierszom i dzielimy je na dwie grupy — te, które odpowiedziały True, i te, które odpowiedziały False. Następnie oceniamy, ile nieczystości usuwa każdy podział, zachowujemy najlepszy i powtarzamy procedurę po obu stronach, dopóki żadne pytanie nie przynosi poprawy.

Kandydatów generujemy dokładnie tak jak wcześniej: łączymy każdą cechę z każdą wartością, jaką przyjmuje ona w bieżących wierszach. Każda para tworzy pytanie; kolumna liczbowa używa >=, a kategoryczna ==. Zmienił się jedynie typ kolumny docelowej, podczas gdy predyktory nadal mogą być liczbowe albo kategoryczne. Generator nie wie i nie musi wiedzieć, co zawiera cel: pięć wierszy z dwiema kolumnami o czterech różnych wartościach daje osiem kandydatów niezależnie od tego, czy przewidujemy chorobę, czy pensję.

Musimy zmienić miarę grupy — sposób określania, jak bardzo jej wiersze różnią się od siebie. W klasyfikatorze robiła to funkcja gini, mierząca wymieszanie etykiet. Przy celu liczbowym zastępuje ją variance, która mierzy odległość pensji od ich średniej.

Co ciekawe, wzór na przyrost informacji nie wymaga żadnej innej zmiany. Tak ocenialiśmy podział w klasyfikatorze:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

A tak wygląda regresor — ta sama funkcja ze zmienioną jedną nazwą:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

Odejmowanie działa tak samo jak w artykule o klasyfikatorze: bierzemy nieczystość grupy początkowej i odejmujemy nieczystość każdego dziecka, ważoną udziałem wierszy, które do niego trafiły. Wzór nie pyta, co znajduje się w kolumnie docelowej; potrzebuje jedynie miary różnic między wierszami każdej grupy. Z funkcją gini dostajemy przyrost informacji, a z variance — spadek błędu kwadratowego, tym razem w dolarach do kwadratu.

Gdy cel jest liczbą, znaczenie tego kryterium można wyrazić jeszcze prościej. Wrócimy do tego po zbudowaniu miary nieczystości.

Pięciu zawodników

Nasz zbiór to pięciu zawodników z badania Hitters — dwa predyktory liczbowe i jeden liczbowy cel:

years oznacza liczbę sezonów rozegranych w najwyższej lidze, hits — liczbę trafień w poprzednim sezonie, a salary — pensję w sezonie 1987, w tysiącach dolarów. Są to prawdziwe wiersze z badania, sprawdzone z pełnym plikiem.

Mierzenie rozrzutu zbioru

Aby porównać podziały, potrzebujemy miary rozrzutu pensji. Użyjemy wariancji, czyli sumy błędów kwadratowych podzielonej przez liczbę wierszy. Tak jak wcześniej wygrywa pytanie, które usuwa najwięcej błędu.

Załóżmy, że trzeba wskazać, która z dwóch list płac jest bardziej rozrzucona:

Drużyna B pochodzi z naszego rzeczywistego zbioru — to pensje pięciu zawodników powyżej. Drużyna A jest hipotetycznym klubem, w którym wszyscy zarabiają podobnie.

Możemy zacząć od umieszczenia obu zestawów na wykresie:

Jeden rzut oka wystarcza, by zauważyć większy rozrzut drugiej drużyny. Wyszukiwanie podziału potrzebuje jednak liczby, którą da się obliczyć. Pierwszym kandydatem jest średnia, zaznaczona na wykresie linią przerywaną — w obu drużynach wypada dokładnie w tym samym miejscu.

Średnia nie może więc mierzyć rozrzutu: w obu przypadkach wynosi 420. Zamiast tego zmierzmy odległość każdej pensji od średniej:

Nie możemy użyć tych odchyleń bezpośrednio, bo w obu zestawach sumują się do zera. To własność średniej: jest punktem równowagi zbioru, więc wszystko powyżej dokładnie znosi wszystko poniżej.

Potrzebujemy zatem samych wielkości, bez znaków. Można wziąć wartości bezwzględne albo podnieść odchylenia do kwadratu. Zaczniemy od kwadratów, czyli konwencjonalnego wyboru, z dwóch powodów: funkcja kwadratowa jest wszędzie gładka i różniczkowalna, podczas gdy wartość bezwzględna ma załamanie w zerze, a ponadto znacznie silniej karze jeden duży błąd niż kilka małych. Wartości bezwzględne są jednak prawdziwą alternatywą; później zobaczymy, jak ich wybór zmienia model.

Po podniesieniu odchyleń do kwadratu i zsumowaniu otrzymujemy SSE. Dzieląc wynik przez liczbę obserwacji, dostajemy wariancję:

SSE to całkowity rozrzut grupy, a wariancja to rozrzut średni — ten sam wynik podzielony przez liczbę wierszy. Obie wielkości mają jednostki podniesione do kwadratu, dlatego liczby są tak duże. Po dodaniu zawodników SSE rośnie, natomiast wariancja pozostaje na podobnym poziomie. Obie miary mówią o tych drużynach to samo: 200.00 dla A i 86,207.50 dla B. Szersza lista płac otrzymuje wynik 431 razy większy.

Zapis wzoru na wariancję wygląda tak:

gdzie $n$ jest liczbą wierszy w grupie, $y_i$ pensją jednego z nich, a $\bar{y}$ ich średnią. Wyrażenie $y_i - \bar{y}$ jest więc odchyleniem jednego wiersza, takim jak w tabeli powyżej.

Po usunięciu $\frac{1}{n}$ zostaje $\sum_{i=1}^{n}(y_i - \bar{y})^2$, czyli SSE.

Zbudowany właśnie wzór jest znany jako wariancja populacji. Obok niego można znaleźć drugi wariant, wariancję z próby, różniący się mianownikiem:

Drzewo zawsze dzieli przez $n$ — używa postaci populacyjnej, $\sigma^2$, gdzie $n$ jest liczbą wierszy w grupie. Często nie dzieli wcale i pracuje na sumach; wrócimy do tego później. Wariancja z próby używa $n-1$, ponieważ szacuje rozrzut większej populacji z garści pobranych z niej wierszy. Liść będzie odpowiadał średnią dokładnie tych wierszy, więc nieczystość musi być kosztem dokładnie tej odpowiedzi. Korekta Bessela usuwa obciążenie takiego oszacowania, lecz węzeł nie ma żadnej populacji do oszacowania.

Dlaczego to właściwa miara nieczystości

Po zbudowaniu drzewa każdy liść przechowuje średnią swojej grupy. Podczas predykcji jest to pensja przypisywana każdemu nowemu zawodnikowi, który do niego trafi — jedna liczba dla wszystkich. Gdy wartości w grupie są szeroko rozrzucone, ta jedna liczba będzie mocno błędna dla wielu wierszy. Dlatego wyszukiwanie podziału dąży do grup o jak najmniejszym rozrzucie.

Załóżmy, że drzewo w ogóle się nie podzieliło: mamy jeden liść zawierający całą drużynę, który każdemu zawodnikowi przewiduje średnią pensję 420.0.

Dla drużyny A jest to dobra odpowiedź: nikt nie zarabia o więcej niż 20 mniej lub więcej, więc największy błąd liścia wynosi 20. Dla drużyny B odpowiedź jest zła: Robidoux zarabia 67.5, Moseby 787.5, a obaj dostają predykcję 420.0 — błędy wynoszą odpowiednio 352.5 i 367.5. Po podniesieniu ich do kwadratu i uśrednieniu wracamy do wartości z tabeli: 200.00 i 86,207.50. Te same wariancje można teraz odczytać jako błędy liści. Rozrzut wewnątrz węzła jest zatem błędem odpowiedzi tego węzła. Właśnie tę liczbę porównuje drzewo przy wyborze pytania, preferując takie, którego dwie grupy pozostawiają najmniej błędu.

Cała ta zależność znajduje się już we wzorze $\frac{1}{n}\sum_{i=1}^{n}(y_i - \bar{y})^2$. Tutaj $\bar{y}$ jest predykcją 420.0, którą liść zwraca wszystkim trafiającym do niego wierszom. Każde $(y_i - \bar{y})$ to błąd jednego zawodnika: $-352.5$ dla Robidoux, $+367.5$ dla Moseby i najwyżej $\pm20$ dla każdego w drużynie A. Po podniesieniu tych błędów do kwadratu i uśrednieniu otrzymujemy 86,207.50 oraz 200.00. Wariancja jest więc średnim kwadratowym błędem treningowym liścia przewidującego średnią — błędem, który pozostałby nawet najlepszemu liściowi o stałej wartości.

Klasyfikacja i regresja korzystają z tej samej struktury. Liść przechowuje najlepszą stałą predykcję, a nieczystość mierzy jej błąd. W klasyfikacji są to proporcje klas i nieczystość Giniego; w regresji — średnia i wariancja. Nieczystość jest obliczana dla każdego kandydata w każdym węźle, więc jej zmiana może przesunąć każdy podział drzewa. Statystyka liścia jest używana dopiero po zakończeniu podziałów: określa, co gotowe drzewo przewiduje, a nie jaki ma kształt.

Średnia czy mediana: wybór kryterium

Wybraliśmy błąd kwadratowy, gdy trzeba było pozbyć się znaków odchyleń i podnieśliśmy je do kwadratu zamiast brać wartości bezwzględne. Jest to ustawienie domyślne bibliotek; na przykład scikit-learn używa criterion="squared_error", jeśli nie podamy innej wartości. Nie jest to jednak jedyna możliwość. Wybór ma dalsze konsekwencje, niż mogłoby się wydawać: funkcja straty używana do oceny podziałów określa też wartość przechowywaną w liściu, ponieważ oba zadania odpowiadają na to samo pytanie — jaka pojedyncza stała minimalizuje tę stratę.

• Minimalizacja błędu kwadratowego → liść przechowuje średnią.
• Minimalizacja błędu bezwzględnego → liść przechowuje medianę.

Weźmy liść z wartościami [10, 12, 14, 16, 200], gdzie 200 jest obserwacją odstającą albo błędem w danych:

Każda stała wygrywa dla własnej funkcji straty. Zwróćmy jednak uwagę na średnią: 50.40 jest większe od czterech z pięciu wartości liścia. Jedna obserwacja odstająca odciągnęła predykcję od niemal każdego punktu, któremu ma służyć. Mediana całkowicie ją ignoruje.

O tym, jaką stałą przechowuje liść, decyduje zatem nieczystość. Dlatego poniższe dwie funkcje zawsze występują razem.

def mean(rows):
    return sum(row[-1] for row in rows) / float(len(rows))

def variance(rows):
    targets = [row[-1] for row in rows]
    m = sum(targets) / len(targets)
    return sum((t - m) ** 2 for t in targets) / len(targets)

Funkcja variance służy do oceny węzła, a mean daje wartość przechowywaną przez liść — taką parę wyznacza błąd kwadratowy. Błąd bezwzględny wymagałby sumy bezwzględnych odchyleń i mediany. Mamy już liczbę opisującą pojedynczy węzeł, regresyjny odpowiednik Giniego. Następny krok to zamiana jej w ocenę podziału, odpowiednik przyrostu informacji.

Ocena podziału

Wiemy już, jak zmierzyć rozrzut jednej grupy. Teraz użyjemy tej miary do oceny pytania. Chcemy ustalić, ile błędu kwadratowego pozostaje po podziale albo — równoważnie — ile błędu podział usunął. Możemy pracować na sumach albo średnich:

Obie metody ustawiają pytania kandydujące w tej samej kolejności, więc wybór nie wpływa na wynik. Rachunki na sumach są prostsze i od nich zaczniemy; kod używa średnich, do których wrócimy po zdefiniowaniu kryterium.

Pytanie dzieli węzeł na dwie grupy, z których każda odpowiada własną średnią — $\bar{y}_L$ po jednej stronie i $\bar{y}_R$ po drugiej. Wzór SSE stosujemy więc osobno do każdej grupy, względem jej własnej średniej. Suma obu SSE daje resztową sumę kwadratów (RSS) — błąd pozostawiony przez podział:

Aby wybrać najlepsze pytanie, obliczamy RSS dla każdego kandydata i wybieramy najmniejszą wartość. To wystarcza do zbudowania drzewa regresyjnego: oceń wszystkich kandydatów, zachowaj najlepszego i powtórz procedurę dla obu utworzonych grup.

RSS nie karze za rozmiar drzewa. Mierzy jedynie, jak dokładnie dwa nowe liście przewidują wiersze bieżącego węzła. Algorytm zachowuje najlepszy podział i wywołuje się rekurencyjnie; nie bierze pod uwagę kosztu całego gotowego drzewa.

Ocena przez błąd usunięty przez podział

SSE można wykorzystać inaczej. Obliczmy je dla grupy rodzica — wierszy przed podziałem, oznaczonych indeksem $P$ — względem jej średniej $\bar{y}_P$. Otrzymamy $\text{SSE}_P = \sum_{i=1}^{n_P}(y_i - \bar{y}_P)^2$, czyli błąd grupy odpowiadającej wszystkim wierszom jedną liczbą. Zamiast pytać, ile błędu podział pozostawia, możemy zapytać, ile go usuwa: od błędu rodzica odejmujemy to, co nadal niosą dzieci.

To ten sam kształt co przyrost informacji — rodzic minus błąd pozostały w dzieciach — zapisany w sumach zamiast ważonych średnich.

Wybór pozostaje taki sam, bo podczas porównywania kandydatów w jednym węźle $\text{SSE}_P$ jest stałe. Odjęcie tej samej liczby od każdego wyniku niczego nie przestawia. Załóżmy, że błąd rodzica wynosi 100, a dwaj kandydaci pozostawiają 60 i 25:

Kandydat, który pozostawia najmniej, usuwa najwięcej. Minimalizacja RSS i maksymalizacja przyrostu opisują ten sam wybór z dwóch stron.

Przyrost nie może być ujemny. Każde dziecko mogłoby zachować średnią rodzica, lecz zamiast tego używa własnej, czyli stałej z definicji minimalizującej jego błąd kwadratowy. Podział jest więc na wierszach treningowych zawsze co najmniej równie dobry. Dlatego gain == 0 oznacza „żadne pytanie nie pomaga”, a nie „niektóre pytania szkodzą”. Z tego samego powodu błąd treningowy nie powie drzewu, kiedy przestać. Bez ograniczeń rekurencja trwa, aż prawie każdy wiersz ma osobny liść. Reguła stopu musi pochodzić spoza kryterium: może to być limit głębokości, minimalna liczba wierszy w liściu albo późniejsze przycinanie.

To samo kryterium zapisane przez wariancję

Przyrost zapisaliśmy w sumach, podczas gdy info_gain — funkcja z artykułu o klasyfikatorze, teraz z variance zamiast gini — operuje na średnich i waży każde dziecko jego udziałem w wierszach:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

p jest częścią wierszy rodzica, które trafiły do lewej grupy. Trzy z pięciu wierszy dają p = 0.6, a prawa grupa dostaje 1 - p = 0.4. Wagi są potrzebne, ponieważ pracujemy na średnich. Sama wariancja nie mówi, ile wierszy ją utworzyło, więc bez wag dziecko z jednym wierszem liczyłoby się tak samo jak dziecko ze stu wierszami. p oraz 1-p przywracają informację o rozmiarze.

W zapisie sumarycznym wagi nie są potrzebne:

def gain_sse(rows, left, right):
    return sse(rows) - (sse(left) + sse(right))

Obie postaci porządkują kandydatów tak samo. Postać uśredniona jest po prostu tym, co mieliśmy już w klasyfikatorze, ponieważ Gini także jest średnią. Łączy je jedna tożsamość: wariancja to SSE przypadające na wiersz.

Po podstawieniu jej dla wszystkich trzech grup przyrost wynosi

a po podzieleniu przez $n_P$ — ponownie stałą dla tego węzła — otrzymujemy postać używaną w artykule o klasyfikatorze i obliczaną przez info_gain:

Wagi, które w postaci uśrednionej mogą wyglądać jak arbitralna decyzja, są po prostu liczebnościami wierszy obecnymi już w sumach. Można więc wybrać dowolną z tych postaci: podają inne liczby, ale ustawiają kandydatów w tej samej kolejności i wybierają to samo pytanie. Postać z przyrostem pozwala zachować kod klasyfikatora bez zmian; RSS częściej pojawia się w podręcznikach i bibliotekach — właśnie dlatego scikit-learn nazywa kryterium squared_error. W tym artykule używamy przyrostu, gdy omawiamy kod, oraz RSS, gdy wyjaśniamy działanie algorytmu.

Ocena kandydatów w korzeniu

Zastosujmy kryterium w pierwszym węźle prawdziwego drzewa — korzeniu, który zawiera wszystkich pięciu zawodników, zanim padnie jakiekolwiek pytanie. Średnia wynosi $2100/5 = 420.0$, a wariancja 86,207.50. Z tożsamości $\text{SSE} = n \cdot \text{Var}$ wynika, że próbujemy zmniejszyć $\text{SSE}_P = 5 \times 86{,}207.50 = 431{,}037.5$. Każde pytanie poniżej oceniamy w postaci uśrednionej — jako gain wypisywany przez kod, czyli $\text{Var}_P$ minus dwie ważone wariancje dzieci — a wynik zwycięzcy odczytamy potem jako RSS.

Pytania kandydujące powstają jak wcześniej: każdą cechę łączymy z każdą przyjmowaną przez nią wartością. Dwie kolumny o czterech różnych wartościach dają osiem kandydatów. Poniżej są ułożeni od najlepszego, choć kod zachowuje jedynie bieżącego zwycięzcę zamiast sortować listę. Dwóch kandydatów w ogóle nie dzieli wierszy:

Dwaj pominięci kandydaci używają najmniejszej wartości w każdej kolumnie: years ma wartości 2, 2, 3, 6, 7, a hits 41, 41, 77, 130, 149. Każdy wiersz odpowiada więc „tak”. Wszystko trafia na stronę True, nic na False, stąd 5 / 0. Nie ma podziału do oceny, więc kandydaci są odrzucani.

Kolumna gain pokazuje wynik kodu, ponieważ podziały ocenia funkcja info_gain. W całkowitym błędzie kwadratowym kryterium widać wyraźniej. Pytanie Is hits >= 77? wysyła Davisa, Marshalla i Moseby’ego na jedną stronę, a dwóch nierozróżnialnych zawodników na drugą:

wobec $431{,}037.50$ w korzeniu. Jedno pytanie usuwa 89% błędu kwadratowego zbioru i żadne inne nie pozostawia mniej. Kolumna przyrostu przedstawia ten sam fakt na obserwację: $76{,}501.0417 \times 5 = 382{,}505.21$ usuniętego błędu, a $431{,}037.5 - 382{,}505.21 = 48{,}532.29$.

Na pierwszym miejscu jest dokładny remis: Is years >= 3? oraz Is hits >= 77? osiągają 76501.0416666667, ponieważ dzielą pięciu zawodników na te same dwie grupy. Operator >= w find_best_split oddaje zwycięstwo kolumnie przeglądanej później, dokładnie jak w klasyfikatorze.

Gotowe drzewo i zawartość jego liści

Po przeprowadzeniu rekurencji do końca algorytm zatrzymuje się, gdy żadnej grupy nie można już podzielić:

Trzy liście zawierają po jednym zawodniku i dokładnie odtwarzają jego pensję. Czwarty zawiera nierozróżnialną parę i odpowiada 81.25, czyli średnią 67.5 oraz 95.0.

Przepuśćmy pięciu zawodników z powrotem przez gotowe drzewo. Każdy idzie za odpowiedziami aż do liścia i przyjmuje przechowywaną przez niego liczbę, tak samo jak zrobiłby nowy zawodnik:

BillyJo Robidoux     wartość    67.5   predykcja   81.25
Jack Howell          wartość    95.0   predykcja   81.25
Alvin Davis          wartość   480.0   predykcja  480.00
Mike Marshall        wartość   670.0   predykcja  670.00
Lloyd Moseby         wartość   787.5   predykcja  787.50

To podręcznikowe zapamiętanie danych: drzewo dzieliło się, aż niemal każdy wiersz dostał własny liść, dokładnie jak klasyfikator i z tego samego powodu — jedyną regułą stopu jest gain == 0.

Wartość 81.25 pokazuje, dlaczego liść przechowuje średnią, a nie na przykład mniejszą albo większą pensję. Liść musi zwrócić jedną liczbę $c$, a minimalizowaną stratą jest błąd kwadratowy. Szukamy więc $c$ minimalizującego $\sum_i(y_i-c)^2$. To gładka funkcja $c$, więc minimum leży tam, gdzie zeruje się pochodna:

Średnia nie jest zatem jedną z kilku rozsądnych możliwości ani umownym wyborem. Jest jedyną stałą spełniającą to równanie i rozwiązaniem tej samej minimalizacji, którą przeprowadza kryterium podziału. Nieczystość i wartość liścia pochodzą z jednej funkcji straty.

Na tym liściu kończą się też możliwości poprawy. Robidoux i Howell mają identyczne years oraz hits, więc żadne pytanie nigdy ich nie rozdzieli. Przy dowolnej głębokości dzielą liść, a każda jego odpowiedź będzie błędna dla co najmniej jednego z nich. Predykcja 81.25 pozostawia $(67.5 - 81.25)^2 + (95 - 81.25)^2 = 378.125$ błędu kwadratowego. Żadne drzewo czytające wyłącznie te dwie kolumny nie zejdzie niżej — to dolna granica błędu treningowego, której większa głębokość nie pokona.

Nie jest to artefakt pięciu wygodnych wierszy: wśród 263 zawodników występuje dziewięć takich par, a pensje w najgorszej z nich różnią się o 310 000 dolarów. Przy tych dwóch kolumnach nawet idealny model pomyliłby się dla tej pary średnio o 155 000 dolarów. Pełny plik ma jeszcze siedemnaście predyktorów, które pozwoliłyby ją rozdzielić. Chodzi o to, że każdy ustalony zestaw cech narzuca dolną granicę, a średnia w liściu pozwala drzewu ją osiągnąć.

Wewnątrz danych: schody

Drzewo regresyjne jest przedziałami stałe: pytania dzielą przestrzeń wejściową na regiony, a każdy punkt w regionie otrzymuje tę samą predykcję. Jako funkcja cech wynik drzewa przypomina płaskie stopnie z pionowymi skokami na progach — bez żadnego nachylenia, niezależnie od głębokości. Poniżej tę własność będziemy nazywać płaskością.

Do jej pokazania użyjemy syntetycznego zbioru zamiast Hitters: 40 wierszy z jedną cechą $x$, równomiernie rozłożonych od 0 do 10, oraz celem biegnącym po gładkiej fali z niewielkim szumem.

Dwie kolumny i zakrzywiona zależność, którą drzewo ma przybliżyć — tyle wystarczy do tego wykresu. Dopasowujemy do wierszy pełny regresor CART. Pionowe linie przerywane oznaczają progi podziałów, więc odcinek między dwiema sąsiednimi liniami jest jednym liściem, narysowanym płasko na poziomie średniej punktów, które zawiera. Zwiększ limit głębokości i obserwuj, jak drzewo tnie zakres na coraz więcej części:

Przy głębokości 1 są dwa stopnie i dopasowanie jest fatalne. Przy głębokości 6 jest ich 27, a błąd kwadratowy spada z 5816 do 89. To błąd całego dopasowania: każdy z 40 punktów przechodzi przez drzewo i jest oceniany względem średniej w swoim liściu. Jest to dokładnie suma nazywana wcześniej RSS, teraz liczona dla 27 liści zamiast dwóch. Drzewo zbliża się do krzywej, ale nigdy się nie wygina — przybliża gładką funkcję coraz węższymi stałymi kawałkami.

To strukturalna różnica względem modelu liniowego i ma dwie strony. Drzewo nie zakłada, że zależność jest liniowa, monotoniczna ani gładka, a interakcje między kolumnami wykrywa automatycznie. Traci za to możliwość zwartego wyrażenia nawet najprostszej ciągłej tendencji: $y=2x$ wymaga jednego współczynnika w modelu liniowym, lecz nieograniczonej liczby stopni w drzewie.

Przy dwóch cechach schody zmieniają się w teren

Jedna cecha daje schody, bo jedną oś zajmują jej wartości, a drugą predykcja. Po dodaniu drugiej cechy obie osie są zajęte, więc predykcja potrzebuje trzeciego wymiaru. Drzewo tnie płaszczyznę na prostokąty, a wysokość stopnia staje się wysokością płaskiego dachu nad każdym z nich.

Oba panele poniżej pokazują ten sam model. Po lewej widzimy podział z góry; predykcję oznaczają odcień i liczba wewnątrz prostokąta — podobnie jak regiony decyzyjne w artykule o klasyfikatorze. Po prawej te same prostokąty są podniesione na wysokość równą predykcji, która na wykresie schodkowym znajdowała się na osi $y$:

Każdy dach jest płaski, a każda ściana pionowa — tak wygląda funkcja przedziałami stała. Zwiększenie głębokości dodaje bloki tak, jak wcześniej dodawało stopnie: 2 regiony, potem 4, 8 i 16. Model zbliża się do kształtu danych płaskimi ścianami, nigdy nachyleniami.

Poza danymi: sufit

Spójrzmy ponownie na wizualizację schodów, na zacieniony obszar po prawej stronie za ostatnim punktem treningowym. Schody się tam nie wznoszą. Pozostają płaskie bez końca, na wartości przechowywanej przez skrajny prawy liść. Każde wejście wykraczające poza wartości ze zbioru treningowego otrzymuje więc ten sam cel.

Mechanizm nie jest charakterystyczny wyłącznie dla regresji. Regiony klasyfikatora również są płaskie, a poza danymi model odpowiada zawartością skrajnego liścia. W regresji ograniczenie widać szczególnie wyraźnie, bo wartości celu mają porządek. Jeśli pensja nadal rośnie poza zakresem treningowym, drzewo nie potrafi za nią podążyć i wciąż zwraca wartość skrajnego liścia. Etykiety nie mają analogicznego kierunku — nie istnieje kategoria powyżej „choroby” — dlatego w klasyfikacji to samo zachowanie jest mniej oczywiste.

Wynika to bezpośrednio ze sposobu predykcji. Wiersz z $x=10^6$ odpowiada „tak” na każde pytanie o próg po drodze, trafia do skrajnego prawego liścia i dostaje średnią wierszy treningowych, które znalazły się w tym liściu. Wartość liścia w żaden sposób nie zależy od tego, jak daleko wejście leży za progiem.

Najostrzejszy przykład to doskonale liniowa zależność bez szumu, $y=2.5x+3$, próbkowana dla $x\in[0,10]$ i dopasowana drzewem o głębokości 3 oraz zwykłą regresją liniową:

X = np.linspace(0, 10, 60).reshape(-1, 1)
y = 2.5 * X.ravel() + 3

tree = DecisionTreeRegressor(max_depth=3).fit(X, y)
linear = LinearRegression().fit(X, y)

Oba modele uczą się na tych samych 60 wierszach, wszystkich w zakresie $x\in[0,10]$. Zapytajmy je o wartości wewnątrz i daleko poza tym zakresem:

Wykres sięga do $x=20$, podczas gdy zakres treningowy kończy się na 10:

Model liniowy dokładnie odzyskuje regułę i podaje poprawny wynik nawet dla $x=1000$. Drzewo odpowiada 26.52 dla $x=12$, $x=50$ i $x=1000$: jedną liczbą dla każdego wejścia wykraczającego poza jego doświadczenie, mimo że dane nie zawierają szumu, a prostą zależność opisują zaledwie dwa parametry.

Nawet wewnątrz zakresu treningowego drzewo nie jest dokładne: podaje 7.45 zamiast 8.00. To ponownie skutek płaskości. Prosta została podzielona na osiem stopni, z których każdy odpowiada własną średnią.

Jeszcze ważniejsze jest ograniczenie zakresu. Liść przechowuje średnią celów treningowych, które do niego trafiły, a średnia nie może leżeć poza uśrednianymi wartościami. Każda predykcja pojedynczego drzewa regresyjnego mieści się więc w zakresie celów treningowych. Bez względu na głębokość i dane drzewo nie przewidzi nowego rekordu w górę ani w dół.

Dla prostej powyżej największa możliwa predykcja drzewa wynosi 26.5169, podczas gdy maksimum treningowe to 28.0 — model nie sięga nawet najwyższej widzianej wartości. Nie jest to jednak regułą, co pokazuje Hitters. Po dopasowaniu drzewa do pensji jego sufit wynosi 2127.3, czyli dokładnie tyle co maksimum treningowe, dla każdej głębokości od 2 wzwyż:

głębokość 2      najwyższa możliwa predykcja  2127.3   osiągnięta przez 1 zawodnika
głębokość 3      najwyższa możliwa predykcja  2127.3   osiągnięta przez 1 zawodnika
głębokość 5      najwyższa możliwa predykcja  2127.3   osiągnięta przez 1 zawodnika
pełna głębokość  najwyższa możliwa predykcja  2127.3   osiągnięta przez 1 zawodnika

Najlepiej opłacany zawodnik jest tak skrajną obserwacją, że zachłanne wyszukiwanie poświęca cały podział na odizolowanie go we własnym liściu — nawet w drzewie z czterema liśćmi — ponieważ usuwa to najwięcej błędu kwadratowego. Dla gładkich celów sufit leży ściśle poniżej maksimum; dla pojedynczej wartości skrajnej drzewo może ją wydzielić i osiągnąć.

W obu przypadkach sufit leży na poziomie największego celu treningowego albo niżej — nigdy wyżej, niezależnie od wejścia. Zapytajmy to samo drzewo o głębokości 3 o wycenę zawodnika z dwukrotnie lepszymi wynikami kariery niż najlepszy gracz w zbiorze:

drzewo o głębokości 3  przewiduje   1169.8
regresja liniowa       przewiduje   5836.3

Dla gracza dwukrotnie lepszego od najlepszego w historii drzewo zwraca liczbę, którą już widziało — całkiem zwyczajną pensję, mieszczącą się w obserwowanym zakresie.

Ma to największe znaczenie, gdy zadanie wymaga ekstrapolacji:

• Trendy i szeregi czasowe. Gdy cecha czasu przekroczy wszystkie poznane progi, drzewo wciąż przewiduje ten sam poziom. Jeśli ważny jest sam trend, najpierw go usuń, modeluj drzewem reszty i dodaj trend z powrotem albo użyj modelu zdolnego wyrazić nachylenie.
• Ceny i wzrost. Drzewo nie potrafi kontynuować rosnącego wzorca poza wartościami cech reprezentowanymi przez poznane progi.
• Zespoły. Lasy losowe dziedziczą to samo ograniczenie. Drzewa wzmacniane mogą podawać wartości spoza pierwotnego zakresu celu, ale ich predykcje również stają się stałe, gdy każda cecha przekroczy wszystkie poznane progi.

Ograniczenie wynika z zawartości liścia, a nie ze sposobu podziału. Niektóre warianty drzew dopasowują w każdym liściu model liniowy zamiast stałej. Pozwala to ekstrapolować, choć predykcje daleko poza danymi silnie zależą wtedy od dopasowanego nachylenia.

Od jednego drzewa do zespołu

Przekształcenie klasyfikatora w regresor wymagało tylko dwóch zmian: użycia wariancji do oceny węzłów i przechowywania średniej w każdym liściu. Powstały model jest elastyczny w zakresie treningowym, lecz jego predykcje przedziałami stałe nie potrafią ekstrapolować trendu poza ten zakres.

W praktyce drzewo regresyjne jest zazwyczaj składnikiem większego modelu. Uśrednienie setek drzew, z których każde wyrosło na innej próbce, daje las losowy. Nic nie jest tam optymalizowane wspólnie: każde drzewo minimalizuje własny błąd kwadratowy na własnej próbce, a na końcu wyniki są uśredniane.

Dopasowywanie drzew kolejno do błędów poprzedników daje gradient boosting, w którym minimalizowany jest błąd kwadratowy całego zespołu. Każda runda mierzy to, co dotychczasowy zespół nadal robi źle, i dopasowuje następne drzewo do tych reszt. Każde drzewo wykonuje więc dokładnie wyszukiwanie podziałów opisane w tym artykule, tylko dla celu złożonego z bieżących błędów zamiast surowych pensji. Dlatego drzewa wykonują tę pracę także przy klasyfikacji: dopasowuje się je do kolumny rzeczywistych gradientów, a nie etykiet.

Drzewo z tego artykułu jest podstawową jednostką takich zespołów — i przenosi do nich swoje ostrzeżenie. Rosnące drzewo sprowadza do zera błąd kwadratowy na wierszach treningowych, a boosting robi to samo przez dodawanie kolejnych rund. Dlatego oba mają parametry, których zadaniem jest je zatrzymać.