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.

Klasyfikator oceniał podziały przez spadek nieczystości Giniego. W regresji z błędem kwadratowym używamy spadku wariancji, a liść przewiduje średnią. Pomnożenie spadku wariancji przez liczbę wierszy rodzica daje zmniejszenie 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.

Pobierz pełny przykład w Pythonie i uruchom python3 hitters_tree.py.

Liść przewidujący średnią ogranicza też ekstrapolację: każda predykcja mieści się w zakresie celów treningowych. Dalsze przykłady pokazują, dlaczego większa głębokość nie pozwala kontynuować rosnącego trendu poza obserwowanym zakresem cechy.

Ten sam mechanizm

Zachowujemy uproszczony algorytm CART z klasyfikatora. Każdy węzeł wewnętrzny wybiera pytanie binarne, ocenia dwie powstałe grupy i uruchamia rekurencję. Liść kończy ją, gdy żaden kandydat nie poprawia wyniku ponad tolerancję numeryczną.

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)

Funkcja odejmuje od wariancji rodzica wariancje dzieci ważone ich liczebnością. Wynik jest spadkiem średniego błędu kwadratowego w tym węźle. Pensje podano w tysiącach dolarów, więc wariancja i SSE mają jednostkę kwadratu tysiąca dolarów.

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

Do oceny kandydatów potrzebujemy miary rozrzutu pensji. Zaczniemy od sumy błędów kwadratowych (SSE), a dzieląc ją przez liczbę wierszy, otrzymamy wariancję.

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.

Podnoszenie do kwadratu zapobiega znoszeniu się odchyleń i zwiększa wagę dużych błędów. Błąd bezwzględny jest alternatywą, ale odpowiada mu predykcja mediany zamiast średniej. Wyszukiwanie podziałów drzewa nie wymaga różniczkowalności.

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

SSE jest sumą, a wariancja to SSE na wiersz. Powielenie każdego wiersza podwaja SSE bez zmiany wariancji. Dodanie dowolnych nowych wierszy może zmienić obie wielkości. Tutaj wariancja drużyny B jest około 431 razy większa: 86,207.50 wobec 200.00.

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:

Używamy mianownika $n$, ponieważ mierzymy średni błąd kwadratowy wierszy w tym węźle. Poprawka $n-1$ służy innemu celowi: estymacji wariancji populacji z próby losowej. Nie jest potrzebna przy obliczaniu tej straty treningowej.

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:

Średnia minimalizuje błąd kwadratowy, a mediana bezwzględny. Zwiększenie największej wartości ponad 200 przesunęłoby średnią, ale pozostawiło medianę równą 14. Ta odporność na skrajną wartość uzasadnia użycie liści opartych na błędzie bezwzględnym przy obserwacjach odstających.

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)

variance ocenia węzeł, a mean wyznacza jego predykcję. Dla błędu bezwzględnego odpowiednią miarą byłoby średnie odchylenie bezwzględne od mediany, a liść przechowywałby medianę.

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.

SSE rodzica jest stałe podczas porównywania kandydatów w jednym węźle. Odjęcie błędu każdego kandydata od tej stałej odwraca ranking: najmniejszy błąd pozostały daje największy przyrost.

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

W dokładnej arytmetyce przyrost dla błędu kwadratowego nie jest ujemny: średnia dziecka jest dla jego wierszy co najmniej tak dobra jak średnia rodzica. Zerowy bieżący przyrost nie oznacza, że dalsze podziały nigdy nie pomogą. Nasza zachłanna implementacja zatrzymuje się przy znikomym przyroście; limit głębokości, minimalny rozmiar liścia i przycinanie dodatkowo kontrolują złożoność.

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 sse(rows):
    m = mean(rows)
    return sum((row[-1] - m) ** 2 for row in rows)

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:

Minimalizacja SSE dzieci, maksymalizacja spadku SSE i maksymalizacja spadku wariancji wybierają ten sam podział w obrębie ustalonego rodzica. Wyniki różnią się stałą lub czynnikiem równym liczbie wierszy rodzica. Kod używa spadku wariancji, zachowując strukturę oceny klasyfikatora.

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

Rekurencja kończy się, gdy żaden kandydat nie poprawia dopasowania ponad tolerancję numeryczną. Dla tych pięciu wierszy otrzymujemy:

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

Trzy pensje treningowe są odtworzone dokładnie, a dwaj gracze z identycznymi cechami otrzymują wspólną średnią. To opis dopasowania treningowego; nie zmierzyliśmy jakości dla nowych zawodników.

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.

Wśród 263 zawodników z podaną pensją dziewięć par ma te same wartości (Years, Hits). Największa różnica pensji wynosi 310 000 dolarów, co daje minimalny średni błąd bezwzględny 155 000 dolarów na tej parze przy wspólnej predykcji. Dodatkowe cechy mogą ich rozróżnić. To ograniczenie zapisanych cech, nie dowód, że pensji z natury nie da się przewidzieć.

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.

Widżet dopasowuje do tych wierszy drzewo regresyjne. Przerywane linie oznaczają wyuczone progi, a każdy przedział przyjmuje średnią swoich celów treningowych. Zwiększ limit głębokości, aby zobaczyć więcej przedziałów:

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.

Drzewo może przybliżać zależności nieliniowe i interakcje cech bez wcześniejszego określania ich postaci. Skończone drzewo ze stałymi liśćmi nie odtworzy jednak dokładnie niestałej prostej na ciągłym przedziale; dokładniejsze przybliżenie wymaga większej liczby stopni.

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

Na schodach z jedną cechą każde wejście powyżej największego wyuczonego progu trafia do tego samego skrajnego liścia. Przy wielu cechach zwiększanie jednej ponad wszystkie jej progi przestaje zmieniać decyzje dotyczące tej cechy, ale pozostałe nadal mogą kierować wiersze do różnych liści.

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ą:

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.tree import DecisionTreeRegressor

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

tree = DecisionTreeRegressor(max_depth=3, random_state=0).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.

W zakresie treningowym drzewo również popełnia błędy przybliżenia: dla $x=2$ zwraca 7.45 zamiast 8.00. Niektóre wejścia mogą być przewidziane dokładnie, lecz osiem stałych poziomów nie odtworzy prostej w każdym punkcie.

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ół.

Największa wartość liścia w przykładzie liniowym to 26.5169, poniżej maksimum treningowego 28.0. Drzewo może osiągnąć maksimum, jeśli liść zawiera wyłącznie tę wartość. Dla porównania dopasujmy model do wszystkich 19 cech Hitters, używając 184 wierszy treningowych z podziału 70/30 z random_state=0:

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

W tym dopasowaniu już drzewo o głębokości 2 izoluje najlepiej opłacanego gracza. Zależy to od cech i pozostałych wierszy, nie tylko od skrajności celu. Ograniczenie pozostaje: średnia w liściu nie przekroczy największego celu, który ten liść zawiera.

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

• Trendy. Przy ustalonych pozostałych cechach drzewo przestaje zmieniać predykcję, gdy rosnąca cecha czasu przekroczy wszystkie progi. Może pomóc osobne modelowanie trendu.
• Lasy losowe. Średnia drzew przewidujących średnie pozostaje w zakresie celów treningowych.
• Boosting drzew. Suma drzew może wyjść poza ten zakres, lecz skończony zespół drzew ze stałymi liśćmi nadal jest przedziałami stały. Wzdłuż ustalonego kierunku predykcja przestaje się zmieniać, gdy nie są przekraczane kolejne granice podziałów.

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.

Drzewa regresyjne często są używane w zespołach. Las losowy uczy drzewa na próbkach bootstrapowych i rozważa losowe podzbiory cech przy podziałach, a następnie uśrednia predykcje. Ogranicza to wrażliwość na pojedyncze dopasowane drzewo.

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.

Ani głębsze drzewa, ani dodatkowe rundy boostingu nie gwarantują zerowego błędu treningowego: już tutaj uniemożliwiają go identyczne cechy z różnymi celami. Głębokość, rozmiar liścia i liczbę modeli wybieraj na podstawie walidacji, nie samego dopasowania treningowego.