Jak zbudować drzewo decyzyjne od zera

Sieci neuronowe świetnie radzą sobie z danymi nieustrukturyzowanymi — pikselami, przebiegami dźwięku, ciągami znaków — takimi, w których pojedyncza wartość wejściowa sama w sobie nic nie mówi. Daj głębokiej sieci wystarczająco dużo takich danych, a nauczy się własnych cech: wzorców pikseli, znaczeń słów i tekstur dźwięku, które bardzo trudno byłoby zaprojektować ręcznie, a potem poprowadzi między klasami dowolnie zawiłą granicę, jakiej wymagają dane.

Ale ogromna część uczenia maszynowego w prawdziwym świecie nie działa na takich danych. Działa na danych tabelarycznych — danych mieszkających w tabeli, w kształcie arkusza kalkulacyjnego albo wyniku zapytania do bazy. Każdy wiersz reprezentuje jedną próbkę albo obserwację — transakcję, pacjenta, dostawę, zawodnika; każda kolumna to cecha z własną nazwą i własnym znaczeniem.

Dobrym przykładem jest badanie chorób serca z Cleveland, gdzie każdy wiersz to pacjent, a ostatnia kolumna to to, co chcemy przewidzieć:

Ostatnia kolumna — podbarwiona powyżej — zawiera zaobserwowane zdarzenie: ten pacjent okazał się mieć chorobę serca, tamten okazał się jej nie mieć. Taka kolumna nazywa się etykietą; każda kolumna przed nią opisuje przypadek, a tylko ta mówi, jak przypadek się skończył. To, czego chcemy się nauczyć, to związek między jednym a drugim — z przypadków, w których etykieta jest już znana, tak by dało się go zastosować do przypadków, w których nie jest. Gdy etykieta jest kategorią, jak tutaj, mamy zadanie klasyfikacji.

Metoda, która najczęściej wygrywa na danych o takim kształcie, to gradient boosting: trenuj jeden mały model po drugim, każdy poprawiający błędy pozostawione przez poprzedników. Przepisowi jest obojętne, czym jest ten mały model, ale w praktyce połączenie gradient boostingu z drzewami decyzyjnymi daje najlepsze wyniki na danych tabelarycznych. Drzewo decyzyjne to model, który przewiduje, zadając pytania o kolumny i podążając za odpowiedziami aż do werdyktu; boosting, podobnie jak las losowy, jest zespołem (ensemble) — setkami drzew, których odpowiedzi łączy się w jedną, co bije każde pojedyncze drzewo.

Zwykle poznaje się gradient boosting pod nazwą implementacji, a nie metody — XGBoost wraz z rodzeństwem LightGBM i CatBoost — i nawet w epoce LLM-ów to one po cichu obsługują pokaźną część produkcyjnego ML. Uber szacuje czasy przyjazdu rozproszonym XGBoostem, Stripe wyłapuje nim siatki oszustów, a Dropbox uruchamia ranker XGBoost wewnątrz swojej firmowej wyszukiwarki opartej na LLM.

Na danych tabelarycznych pojawiają się dwa zadania: klasyfikacja, gdzie odpowiedzią jest kategoria, i regresja, gdzie jest nią liczba — pensja, cena. Drzewo decyzyjne obsługuje oba. Ten artykuł buduje klasyfikator; skieruj ten sam kod na cel liczbowy, zastąp miarę nieczystości wariancją tego celu, a zliczenia etykiet w liściu ich średnią, a otrzymasz model regresyjny przewidujący liczbę — nic więcej w kodzie się nie zmienia, choć sporo zmienia się w powstałym modelu, o czym traktuje artykuł towarzyszący.

Boosting to temat późniejszego artykułu. Ten skupia się na tym, co boosting powtarza setki razy: jak z tabeli wierszy powstaje pojedyncze drzewo decyzyjne — skąd biorą się jego pytania, jak jedno z nich zostaje wybrane spośród pozostałych i kiedy dzielenie się kończy. Piszemy to w czystym Pythonie, bez NumPy i bez scikit-learn, na pięciu wierszach na tyle małych, że każdą liczbę można sprawdzić ręcznie.

Dwa typy węzłów i obszary, które wycinają

Będziemy pracować na pięciu pacjentach z badania chorób serca z Cleveland. Pełna tabela zawiera 303 pacjentów i trzynaście cech (predyktorów), ale użyjemy tylko pięciu wierszy i dwóch cech plus etykiety:

Mając wynik testu wysiłkowego pacjenta i liczbę naczyń, drzewo ma przewidzieć, czy ten pacjent ma chorobę serca — warto więc wiedzieć, co te dwie kolumny zapisują.

stress_test (Thal w pliku źródłowym) to talowy test wysiłkowy, który obrazuje przepływ krwi do mięśnia sercowego w spoczynku i przy wysiłku: normal oznacza, że przepływ wygląda dobrze, ubytek fixed jest niedokrwiony w obu stanach — tkanka już martwa po wcześniejszym zawale — a ubytek reversable jest niedokrwiony tylko przy wysiłku, czyli zwężone, ale wciąż żywe naczynie. vessels (Ca) to liczba głównych naczyń wieńcowych, od 0 do 3, które w fluoroskopii okazały się zmienione chorobowo.

Weźmiemy te pięć wierszy i będziemy dzielić je na coraz mniejsze grupy, używając cech i ich wartości do rozstrzygania, do której grupy trafia każdy wiersz. Sekwencja podziałów rysuje się jako rozgałęziający się diagram — stąd nazwa „drzewo”.

Na tym diagramie są dwa typy węzłów.

Romby to węzły decyzyjne: każdy zawiera jedno pytanie ustalające logikę rozgałęzienia, z dwiema wychodzącymi krawędziami, True i False, a każdy przybywający wiersz zostaje wysłany jedną z nich. W zależności od algorytmu węzeł może mieć więcej niż dwie gałęzie: ID3 i C4.5 dałyby stress_test po gałęzi na wartość i rozdzieliłyby go od razu na trójkę dzieci. My implementujemy CART, który zadaje wyłącznie pytania tak/nie, więc dwie krawędzie to wszystko, co węzeł tutaj kiedykolwiek będzie miał. Tego samego używa każda główna implementacja — podziały binarne oceniane miarą nieczystości — od DecisionTreeClassifier z sklearn po drzewa wewnątrz lasów losowych i XGBoosta.

Prostokąty to liście: ścieżka się tam kończy, nic więcej nie jest pytane, a wszystko, co liść przechowuje, to zliczenie etykiet niesionych przez pacjentów treningowych, którzy przyszli tą samą ścieżką. Te zliczenia są jego odpowiedzią dla każdego nowego pacjenta, który tam wyląduje — dlatego prostokąty powyżej mówią Yes: 2, Yes: 1, No: 1 oraz No: 1: dwoje pacjentów ze zmienionym naczyniem, oboje chorzy; dwoje nieodróżnialnych, którzy się nie zgadzają; jeden czysty przypadek bez choroby. Podziel te zliczenia przez ich sumę, a masz prawdopodobieństwo: 100% Yes w pierwszym liściu, 100% No w ostatnim i 50/50 w środkowym.

Te dwa typy węzłów to cały model: węzły decyzyjne kierują wiersz, liście na niego odpowiadają, a każdy pacjent wchodzący u góry kończy dokładnie w jednym liściu. Drzewo decyzyjne dzieli wiersze tabeli na grupy — a te grupy można narysować jako obszary przestrzeni wszystkich możliwych par (test wysiłkowy, liczba naczyń). Narysowane, nadają drzewu jego charakterystyczny wygląd: każda granica to cięcie równoległe do osi, bo każde pytanie wskazuje jedną kolumnę i jedną wartość. Poniżej stoi ono obok trzech innych sposobów rozdzielenia tych samych punktów — prostej linii, gładkiej krzywej, którą wygięłaby przez nie sieć neuronowa, oraz poszarpanego konturu, jaki daje metoda k najbliższych sąsiadów, w której każde miejsce jest odpytywane przez najbliższe mu punkty treningowe.

Czego więc naprawdę trzeba, żeby coś takiego zbudować? Potrzebne są dwie rzeczy.

• Sposób generowania pytań kandydujących z tabeli, bo drzewo musi je skądś wziąć.
• Sposób oceniania tych kandydatów, żeby dało się wybrać najlepszego — węzeł decyzyjny zawiera jedno pytanie i ani jednego więcej.

Poza tym potrzebna jest reguła, kiedy przestać, bo zwykle nie chcemy dzielić aż do momentu, gdy każdy wiersz ma własny liść. Zostawiony sam sobie algorytm właśnie tam dochodzi, bo dzielenie kończy się dopiero wtedy, gdy żadne pytanie nie dzieli już stosu. Takie drzewo zapisało tabelę, zamiast się z niej nauczyć: liść z jednym pacjentem treningowym może tylko powtórzyć wynik tego pacjenta, więc każdy nowy pacjent tam skierowany dostaje wynik jednej osoby zamiast wzorca widzianego u wielu.

Od wierszy do pytań

Każdy węzeł decyzyjny zawiera pytanie, więc budowanie drzewa oznacza wybieranie pytań. Aby zbudować listę kandydatów, połącz każdą cechę z każdą wartością, jaką ta cecha przyjmuje w danych — każda para to jedno pytanie. Typ kolumny wybiera porównanie. Kolumna kategoryczna wymaga dokładnego dopasowania — Is stress_test == fixed? jest prawdą dla pacjentów z ubytkiem fixed i dla nikogo więcej. Kolumna liczbowa zadaje zamiast tego próg — Is vessels >= 1? jest prawdą dla pacjenta z 1 zmienionym naczyniem i dla każdego powyżej, co czyni tę wartość punktem cięcia na osi liczbowej, a nie nazwą do dopasowania.

To parowanie stanowi cały generator, więc warto rozpisać je w całości. Dla naszego zbioru mamy dwie kolumny po trzy różne wartości, więc kończymy z listą sześciu par:

Jedna kolumna, jedna wartość, jedno porównanie: tym zawsze jest pytanie, tutaj i na dowolnym innym zbiorze danych. CART nigdy nie łączy dwóch warunków w jedno pytanie, np. stress_test == normal AND vessels >= 1, nigdy nie waży jednej kolumny przeciw drugiej i nigdy nie używa wartości nieobecnej w zbiorze — żadnego vessels >= 1.5 między dwiema zaobserwowanymi liczbami ani żadnego vessels >= 3, bo 3 nie pojawia się w naszym pięciowierszowym zbiorze.

Te sześć to wszystko, o co to drzewo może zapytać — i nie wszystkie trafią do gotowego drzewa. Większość kandydatów jest próbowana, oceniana i odrzucana; tutaj tylko dwa dożywają do bycia pytaniami w drzewie, które zbudujemy, a pozostałe cztery zostają ocenione i odrzucone. A lista jest skończona — nigdy nie dłuższa niż liczba różnych wartości w tabeli — dlatego następny krok może po prostu wypróbować je wszystkie.

W kodzie pytania definiuje jedna mała klasa. Question przechowuje indeks kolumny i wartość, a jego metoda match decyduje, które z dwóch porównań zastosować, patrząc na typ znalezionej wartości:

class Question:
    def __init__(self, column, value):
        self.column = column
        self.value = value

    def match(self, example):
        val = example[self.column]
        if is_numeric(val):
            return val >= self.value      # numeric: threshold
        else:
            return val == self.value      # categorical: equality

    def __repr__(self):
        condition = ">=" if is_numeric(self.value) else "=="
        return "Is %s %s %s?" % (header[self.column], condition, str(self.value))

def is_numeric(value):
    return isinstance(value, int) or isinstance(value, float)

Tę logikę dopasowania da się zaimplementować na kilka sposobów. Nasz to trzylinijkowa gałąź is_numeric wewnątrz match i to właśnie dzięki niej to drzewo obsługuje kolumnę tekstową i liczbową obok siebie zupełnie bez preprocessingu. Biblioteki nie wszystkie idą tą drogą.

Drzewo ze scikit-learn wymaga wejścia liczbowego, więc stress_test trzeba najpierw zakodować metodą one-hot — po jednej kolumnie 0/1 na wartość:

Drzewo pyta wtedy is_fixed >= 0.5 tam, gdzie nasze pyta stress_test == fixed — ten sam podział, rozłożony na trzy kolumny. Samo 0.5 nie ma znaczenia: kolumna zawiera tylko 0 i 1, więc dowolne cięcie między nimi rozdziela te same wiersze, a sklearn stawia progi w połowie odległości między dwiema sąsiednimi wartościami. Kolumna z czterema kategoriami stałaby się po prostu czterema takimi kolumnami 0/1, o każdej wciąż pytaną przy 0.5 — kodowanie rośnie wszerz, a każde pytanie pozostaje testem tak/nie na jednej wartości.

LightGBM, CatBoost i XGBoost dzielą po podzbiorach: testują grupę kategorii naraz, co wciąż jest jednym pytaniem o jedną kolumnę — różnica polega na tym, że testowaną wartością jest zbiór, a nie pojedyncza kategoria:

ours:    Is stress_test == fixed?
theirs:  Is stress_test in {normal, reversable}?

Mierzenie różnorodności zbioru danych

Wiemy już, jak zbudować listę pytań kandydujących, więc kolejną rzeczą do zrozumienia jest jak je oceniać i rozstrzygnąć, które zostanie pytaniem węzła. Do tego potrzebujemy miary tego, jak wymieszany jest stos etykiet, zwanej nieczystością Giniego, oraz sposobu oceny każdego pytania po tym, ile rozmieszania cofa — o ile mniej wymieszane wychodzą jego dwa stosy niż stos, z którego pochodzą. Ta ocena nazywa się przyrostem informacji i wygrywa pytanie, które ma go najwięcej.

Spójrzmy najpierw na nieczystość Giniego, czyli miarę tego, jak wymieszany jest zbiór — jedną liczbę mówiącą, czy rzeczy w nim są jednego rodzaju, czy stanowią mieszankę wielu.

Załóżmy, że masz powiedzieć, który z dwóch zbiorów jest bardziej wymieszany. Jedno spojrzenie na obrazek poniżej wystarczy, by stwierdzić, że drugi zbiór jest bardziej różnorodny: cztery rodzaje zamiast dwóch i rozłożone równiej. Oko rozstrzyga to natychmiast.

Załóżmy teraz, że nie znamy składu żadnego ze zbiorów — żadnych zestawień, żadnej listy rodzajów, tylko możliwość sięgnięcia do środka i wyjęcia czegoś. Czy dałoby się ująć różnorodność liczbą?

Jednym ze sposobów uzyskania takiej liczby byłoby próbkowanie: wyciągnij dwa elementy losowo, zanotuj, czy są tego samego rodzaju czy różnych, odłóż je z powrotem i powtórz. Ułamek par, które wracają różne, jest oszacowaniem wymieszania zbioru i nie wymaga wiedzy o zbiorze poza tym, co pokażą losowania.

Załóżmy, że zrobiliśmy to po dziesięć razy na każdym zbiorze. Oto wynik:

Cztery pary lewego zbioru zawierają dwa różne rodzaje; siedem par prawego. Podziel przez liczbę losowań i masz oszacowanie — daszek nad $\hat{d}$ oznacza wartość oszacowaną z próby, w odróżnieniu od policzonej z całej populacji:

I liczba zachowuje się tak, jak chcieliśmy. Im jest mniejsza, tym częściej dwa losowe wyciągnięcia wracały tego samego rodzaju — tym bardziej jednorodny zbiór. Im większa, tym częściej się różniły — tym bardziej różnorodny zbiór. Oszacowanie wyostrza się też, im dłużej losujesz: dziesięć par już wystarczy, by rozdzielić te dwa zbiory, a sto przygwoździłoby każdą liczbę. Losuj dalej, a ustabilizuje się na jednej dokładnej wartości.

Ogólnie jednak nie trzeba wcale próbkować: gdy wiesz, co zbiór zawiera, odrobina rachunku prawdopodobieństwa daje tę dokładną wartość wprost. Policz szansę, że dwa wyciągnięcia się zgadzają, i odejmij ją od 1.

Weźmy lewy zbiór. Siedem z dziesięciu jego elementów to niebieskie kwadraty, więc pojedyncze wyciągnięcie jest kwadratem z prawdopodobieństwem 0.7 — a prawdopodobieństwo wyciągnięcia dwóch kwadratów pod rząd to $0.7 \times 0.7 = 0.49$. Koła dają $0.3 \times 0.3 = 0.09$. To jedyne dwa sposoby, by wyciągnięcia się zgadzały, więc zgadzają się w $0.49 + 0.09 = 0.58$ przypadków. Ale nam chodzi o przeciwieństwo — jak często dwa wyciągnięcia wracają różne — a ponieważ każde losowanie albo się zgadza, albo nie, to jest to jeden minus szansa zgodności: $1 - 0.58 =$ 0.42.

Prawy zbiór to ten sam rachunek z czterema rodzajami zamiast dwóch:

Dwa wyciągnięcia zgadzają się w 30% przypadków, więc różnią się w 0.70 przypadków — co odpowiada siedmiu na dziesięć z próbkowania, bez ani jednego losowania.

Tę samą logikę można pokazać geometrycznie. Rozłóż każdą uporządkowaną parę wyciągnięć jako komórkę siatki — pierwsze wyciągnięcie w poziomie, drugie w pionie. Dziesięć elementów daje sto komórek, a ta siatka to wszystkie możliwe wyniki:

Ta dokładna wartość ma nazwę. Prawdopodobieństwo, że dwa losowo wyciągnięte ze zbioru elementy są różnych rodzajów, to nieczystość Giniego zbioru, a zapisana wygląda tak:

gdzie $p_k$ to ułamek zbioru należący do rodzaju $k$. Dwie połowy to dwa sposoby powiedzenia tego samego: $\sum_k p_k^2$ to prawdopodobieństwo, że losowania się zgadzają — dla każdego rodzaju szansa, że oba w nim wylądują, zsumowana — a jeden minus to jest szansa, że się różnią.

Nasze dwa zbiory przepuszczone przez ten wzór to arytmetyka sprzed chwili w skróconej formie:

Ta statystyka jest starsza niż uczenie maszynowe i pojawia się w innych dziedzinach pod innymi nazwami — indeks Simpsona w ekologii, indeks Herfindahla-Hirschmana w ekonomii.

Gini na naszych pięciu wierszach

Jesteśmy więc gotowi policzyć nieczystość Giniego dla naszych pięciu wierszy. Najpierw potrzebujemy zestawienia rodzajów, którymi w naszym przypadku są etykiety: tam gdzie powyższe zbiory zawierały kwadraty, koła, trójkąty i gwiazdę, stos wierszy zawiera Yes i No. Policz je więc — ile których etykiet jest w danym stosie — bo każda wielkość w tym artykule wynika z tego słownika.

def class_counts(rows):
    """Counts the number of each type of example in a dataset."""
    counts = {}  # label -> count
    for row in rows:
        label = row[-1]  # the label is always the last column
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    return counts

Pierwszy przebieg po całym zbiorze, class_counts(training_data), daje {'No': 2, 'Yes': 3} — nasi pięcioro pacjentów, policzeni według rodzaju.

Teraz, mając zestawienie pod ręką, możemy policzyć nieczystość Giniego — cztery linijki Pythona:

def gini(rows):
    """Calculate the Gini Impurity for a list of rows."""
    counts = class_counts(rows)
    impurity = 1
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= prob_of_lbl**2
    return impurity

Pętla jest wzorem, po jednym składniku na etykietę — podaj jej stos samych Yes, a zwróci 0.0, podaj jeden Yes i jeden No, a zwróci 0.5. Nasz zbiór treningowy, trzy Yes przeciw dwóm No, startuje z:

gini(training_data) → 0.48

Przejdziemy przez każde pytanie kandydujące i zobaczymy, które zostawia po sobie najmniej wymieszania, więc 0.48 to liczba do pobicia. To także wysoki punkt startowy: przy dwóch etykietach Gini osiąga maksimum 0.5, gdy są podzielone po równo, więc trzy Yes przeciw dwóm No zostawiają nas na 0.48 — mniej więcej tak pomieszanie, jak to możliwe dla pięciu wierszy.

Przyrost informacji — ocena podziału

Naszym celem jest ocenianie pytań, a umiemy już policzyć nieczystość stosu wierszy. Możemy więc wykonać podział pytaniem kandydującym, zmierzyć nieczystość każdego z dwóch powstałych stosów i porównać to z tym, od czego zaczęliśmy. To przepis na przyrost informacji, ocenę, według której sądzimy pytanie.

Zapisany, zajmuje jedną linię:

I ma cztery kroki:

1. podziel stos $S$ pytaniem, dając dwa stosy — $S_L$, wiersze, które odpowiedziały True, i $S_R$, wiersze, które odpowiedziały False;
2. uruchom gini na każdym z nich;
3. połącz te dwie liczby w jedną, ważąc tym, ile wierszy poszło na każdą stronę: $\frac{|S_L|}{|S|}$ daje wagę lewego stosu, a $\frac{|S_R|}{|S|}$ prawego, każda z nich to udział wierszy rodzica, który poszedł w tę stronę;
4. odejmij to od nieczystości rodzica, $\text{Gini}(S)$.

Zostaje nieczystość, którą pytanie usunęło — im wyższa, tym lepsze pytanie.

Czytaj to jak transakcję w niepewności. W słowniku różnorodności z poprzedniej sekcji ważona suma to różnorodność pozostała po podziale, a przyrost to różnorodność usunięta przez zadanie pytania. Przyrost 0 oznacza, że dwa stosy są tak samo wymieszane jak ten, z którego pochodzą, więc pytanie niczego nie rozdzieliło; pytanie, którego oba dzieci wychodzą czyste, usunęło całe wymieszanie, jakie było. Polujemy więc na pytania o największym przyroście — te, które kupują najwięcej usuniętej różnorodności za jedno pytanie, które kosztują.

Warto podkreślić, po co w ogóle jest ważenie z kroku 3, bo bez niego ocenę łatwo oszukać. Dwaj nasi kandydaci, Is stress_test == normal? i Is vessels >= 1?, dzielą pięć wierszy każdy na jedno idealnie czyste dziecko o Gini dokładnie 0 i jedno dziecko wciąż wymieszane. Różnią się tym, ile danych niesie to czyste dziecko: jeden odłupuje pojedynczego pacjenta i zostawia za sobą cztery wymieszane wiersze, drugi wyciąga dwóch i zostawia trzy. Tylko ważenie widzi tę różnicę. Sprawia, że czyste dziecko liczy się dokładnie tyle, ile waży, więc dziecko z jednego wiersza ledwie się rejestruje, a wynik ustala pozostawiony bałagan.

Oto obaj rozpisani w całości, każdy ze swoimi dwoma dziećmi połączonymi na dwa sposoby — liczonymi po równo, a potem ważonymi udziałem wierszy, które każde dziecko trzyma:

Teraz to samo dla drugiego kandydata. Is vessels >= 1? również odkrawa idealnie czyste dziecko, ale to dziecko trzyma dwóch pacjentów, a nie jednego, a stos, który zostawia, ma trzy wiersze zamiast czterech — i jest brudniejszy: 0.444 zamiast 0.375:

Liczby na obu rysunkach pokazują więc coś mocniejszego niż przeskalowanie. Liczone po równo, Is stress_test == normal? daje 0.293, a Is vessels >= 1? daje 0.258, więc wygrywa pierwsze pytanie. Ważone, wychodzą 0.180 i 0.213, i wygrywa drugie. Ważenie nie tylko zmniejsza wyniki — odwraca kolejność, a ponieważ to korzeń, dwie odpowiedzi dają drzewa różniące się aż do samego dołu.

Tak implementujemy podział i jego przyrost informacji, wraz z ważeniem. partition wykonuje krok 1, sortując wiersze do dwóch stosów, jakie tworzy pytanie, a info_gain wykonuje kroki 2–4, oceniając to, co wyszło, względem tego, co weszło:

def partition(rows, question):
    """Split rows into those matching the question, and those that don't."""
    true_rows, false_rows = [], []
    for row in rows:
        if question.match(row):
            true_rows.append(row)
        else:
            false_rows.append(row)
    return true_rows, false_rows

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)

Uruchom je na obu powyższych kandydatach, a zwrócą 0.180 i 0.213 — te same liczby, które rysunki wyliczyły ręcznie, teraz policzone, a nie narysowane.

Mechanizm — podziel, potem rekurencja

Mamy już wszystkie elementy: sposób generowania pytań, sposób mierzenia wymieszania stosu i sposób oceny tego, co pytanie z nim robi. Oto procedura, która je łączy. Drzewo decyzyjne rośnie według jednego przepisu, stosowanego do jednego stosu wierszy treningowych:

1. Wypróbuj każde pytanie, na jakie pozwalają dane — każdą cechę, każdą wartość, jaką ta cecha przyjmuje.
2. Oceń każde pytanie po tym, jak bardzo rozmieszanie etykiet w stosie maleje — to przyrost informacji, zbudowany na nieczystości Giniego, dokładnie tak, jak przed chwilą wyprowadziliśmy.
3. Jeśli żadne pytanie nie pomaga, przerwij: stos staje się liściem, a jego zliczenia etykiet stają się predykcją.
4. W przeciwnym razie użyj najlepszego pytania, by podzielić stos na dwa mniejsze.
5. Uruchom tę samą procedurę na każdym z dwóch stosów.

Ta procedura ma kanoniczną nazwę — rekurencyjny podział binarny — zstępujący, zachłanny algorytm budowania drzew decyzyjnych przez kolejne dzielenie zbioru danych na dwie grupy. Zaczyna od wszystkich danych w korzeniu, ocenia każdą cechę i punkt podziału, by zminimalizować błąd lub zmaksymalizować czystość, i powtarza proces na każdej nowej podgrupie, aż osiągnięty zostanie limit zatrzymania.

Nazwanie algorytmu zachłannym oznacza, że rozstrzyga on każdy podział, patrząc wyłącznie na stos przed sobą. Bierze pytanie, które wypada tam najlepiej, i nigdy do niego nie wraca: wybór nie jest rewidowany, gdy dzieci wypadną kiepsko, i nigdy nie jest koordynowany z podziałami gdzie indziej w drzewie. Lokalnie najlepszy na każdym kroku, bez gwarancji, że gotowe drzewo jest drzewem najlepszym — a następna sekcja pokazuje, jak niewiele trzeba, by obnażyć tę lukę, gdy dwa pytania korzeniowe uzyskują dokładnie ten sam wynik, a wybór między nimi zmienia wszystko poniżej.

Bycie rekurencyjnym to właśnie to, co wycina prostokąty z rysunku ze wstępu: każde wywołanie posiada jeden obszar przestrzeni cech — wiersze, które przetrwały pytania powyżej — i albo dzieli ten obszar, albo pieczętuje go jako liść. Prostokąty to stosy na dnie rekurencji.

Wybór podziału w korzeniu — i remis

Zanim zbudujemy całą rekurencyjną konstrukcję, przyjrzyjmy się szybko implementacji tej części, która działa w pojedynczym węźle — poszukiwaniu najlepszego pytania dzielącego. W korzeniu ten węzeł trzyma wszystkich pięciu pacjentów, a szuka funkcja find_best_split, która próbuje każdej wartości każdej cechy i zachowuje najlepszą.

To dwie zagnieżdżone pętle — każda kolumna na zewnątrz, każda różna wartość, jaką ta kolumna przyjmuje, wewnątrz — a każda wytworzona przez nie para przechodzi cztery kroki:

1. zbuduj Question z kolumny i wartości;
2. partition wierszy nim, na dwa stosy, jakie tworzy;
3. oceń te stosy przez info_gain;
4. porównaj ten wynik z najlepszym dotąd i zachowaj pytanie, jeśli wygrywa.

Gdy obie pętle się kończą, funkcja zwraca pytanie wciąż trzymające najlepszy wynik.

def find_best_split(rows):
    best_gain = 0
    best_question = None
    current_uncertainty = gini(rows)
    n_features = len(rows[0]) - 1

    for col in range(n_features):
        values = set([row[col] for row in rows])
        for val in values:
            question = Question(col, val)
            true_rows, false_rows = partition(rows, question)

            if len(true_rows) == 0 or len(false_rows) == 0:
                continue  # this split doesn't divide the data

            gain = info_gain(true_rows, false_rows, current_uncertainty)

            if gain >= best_gain:
                best_gain, best_question = gain, question

    return best_gain, best_question

Jedno wywołanie w korzeniu ocenia każde pytanie wyprodukowane przez generator i wraca z tym:

Sześć pytań — dwie kolumny po trzy różne wartości — ale liczbę dostaje tylko pięć z nich. Is vessels >= 0? jest prawdą dla każdego pacjenta, bo 0 to najmniejsza wartość, jaką ta kolumna przyjmuje, więc wysyła wszystkie pięć wierszy gałęzią True i żadnego gałęzią False. Jedno dziecko trzyma cały stos, a drugie nic, co nie jest podziałem, lecz kopią — nic nie zostało podzielone, więc nie ma czego oceniać. Zabezpieczenie len(true_rows) == 0 or len(false_rows) == 0 odrzuca je, zanim info_gain je w ogóle zobaczy. Jego przyrost i tak byłby dokładnie 0 — jedno dziecko nic nieważące, drugie będące rodzicem — ale pominięcie zapobiega także zwróceniu nie-podziału jako najlepszego pytania, gdy nic innego nie przekracza zera.

Teraz spójrz na górę tej tabeli, bo to najciekawsza część. Dwa różne pytania wróciły z tym samym wynikiem 0.2133. Remisy i prawie-remisy są na prawdziwych danych częste, a gdy się zdarzą, późniejszy kandydat nadpisuje wcześniejszego. To zachowanie jest szczegółem implementacyjnym, a w naszym algorytmie bierze się z dwóch rzeczy: kolumny są skanowane w kolejności indeksów, więc stress_test (kolumna 0) dociera pierwszy, a potem zostaje po cichu wyparty przez równie dobre vessels (kolumna 1); oraz porównanie jest napisane z >= zamiast >, co w ogóle umożliwia to wyparcie:

if gain >= best_gain:

Remisy i prawie-remisy pojawiają się na prawdziwych danych nieustannie, i to właśnie czyni z tego dziwactwa problem. Nic w danych nie wolało vessels od stress_test — zrobił to operator porównania, a ponieważ to korzeń, wszystko poniżej jest zbudowane na tym wyborze. Drobna zmiana wierszy wystarczy, by odwrócić prawie-remis i przeorganizować całe poddrzewo poniżej. To właśnie czyni z pojedynczego drzewa model o wysokiej wariancji: jego kształt zależy od konkretnej próby, na której je wytrenowano. Wrócimy do tego pod koniec artykułu, gdzie jest to jedna z dwóch porażek tłumaczących, dlaczego jedno drzewo rzadko bywa modelem, który wdrażasz.

Rekurencja — budowanie drzewa

Skoro pojedynczy węzeł potrafi znaleźć swoje pytanie, jesteśmy gotowi zbudować całe drzewo — rekurencję, która uruchamia to poszukiwanie na stosie za stosem i zapisuje, co znajdzie. Do zapisu potrzeba po jednej klasie na typ węzła z otwierającego diagramu: Leaf trzyma zliczenia etykiet tych wierszy, które do niego dotarły, a Decision_Node trzyma pytanie i dwie gałęzie. W słowniku podręcznikowym pytanie to reguła podziału — jeden predykat na jednej cesze — a węzeł decyzyjny to ta reguła wpięta w schemat blokowy, z dwiema gałęziami dającymi jej odpowiedziom tak/nie dokąd pójść. Gotowe drzewo można myśleć jako serię reguł podziału. Zaczynając od góry drzewa i stosując je w drodze w dół — find_best_split uczy się tych reguł, a węzły to miejsce, gdzie mieszkają te wybrane.

class Leaf:
    def __init__(self, rows):
        self.predictions = class_counts(rows)

class Decision_Node:
    def __init__(self, question, true_branch, false_branch):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch

def build_tree(rows):
    gain, question = find_best_split(rows)

    if gain == 0:
        return Leaf(rows)          # base case: no question helps anymore

    true_rows, false_rows = partition(rows, question)
    true_branch = build_tree(true_rows)
    false_branch = build_tree(false_rows)

    return Decision_Node(question, true_branch, false_branch)

Gdy uruchomimy to na pięciu pacjentach, otrzymamy takie drzewo — narysowane ze stosami widocznymi przy każdej gałęzi:

Drzewo wyszło na dwa pytania w głąb, z trzema liśćmi. Przeczytajmy je z góry na dół, zaczynając od korzenia: vessels >= 1, zwycięzca remisu. Każdy pacjent ze zmienionym naczyniem ma chorobę serca, a ta gałąź kończy się natychmiast czystym liściem — oboje, załatwieni jednym pytaniem.

Warto się przy tym zatrzymać: cała grupa wypadła z danych zupełnie bez domieszki — Gini 0, uzyskane jednym pytaniem. Poziom niżej samotny pacjent normal robi to samo — i zauważ, że stress_test ma trzy wartości, a drzewo pyta tylko o jedną z nich. stress_test == fixed? odłupuje pacjentów z ubytkiem fixed, a wszystko, co nie jest fixed, jedzie gałęzią False razem, nierozróżnione. Tutaj akurat jest to pojedynczy pacjent normal, bo obaj pacjenci reversable odeszli już w korzeniu.

Z trzech liści drzewa dwa są czyste; każdy wiersz treningowy poza kolidującą parą trafia do grupy o zerowym wymieszaniu, a rekurencja zatrzymuje się w każdej z nich właśnie dlatego, że nie ma już nieczystości do usunięcia.

Zostaje trzeci liść, trzymający jedną etykietę Yes i jedną No dla identycznego zestawu wartości cech. Żadne pytanie nie mogłoby rozdzielić tych dwóch pacjentów — i żaden inny model też nie, bo to, co by ich odróżniało, w danych w ogóle nie występuje. Dałoby się to rozwiązać, gdybyśmy użyli więcej predyktorów, bo jedenaście odrzuconych kolumn może dobrze zawierać coś, co tych dwóch pacjentów rozdziela.

Ten proces oceniania pytań, dzielenia stosu na zwycięzcy i rekurencji to w istocie procedura treningowa. Architektura sieci neuronowej jest projektowana z góry — liczby warstw, szerokości, połączenia — a spadek gradientu tysiące razy popycha wartości wewnątrz tej ustalonej ramy. Drzewo nie ma ustalonej ramy ani niczego, co byłoby popychane: trening wymyśla, o którą cechę pyta każdy węzeł, przy jakim progu, w jakiej kolejności i jak głęboko. Sieć neuronowa trenuje wartości wewnątrz ustalonej struktury; drzewo trenuje samą strukturę, a jego wartości wypadają jako podsumowania — zliczenia tych wierszy, które akurat przyszły. Nie było epok ani zbieżności: każdy węzeł ocenił swoich kandydatów raz, zachował najwyższego i nigdy nie wrócił do wyboru, więc gdy korzeniowe wywołanie build_tree wróciło, trening był skończony. Model nigdy nie stawał się stopniowo lepszy; był stopniowo budowany.

Klasyfikacja — odczytywanie prawdopodobieństwa z liścia

Predykcja to znowu rekurencja, i krótsza niż kod treningowy:

def classify(row, node):
    if isinstance(node, Leaf):
        return node.predictions

    if node.question.match(row):
        return classify(row, node.true_branch)
    else:
        return classify(row, node.false_branch)

def print_leaf(counts):
    total = sum(counts.values()) * 1.0
    return {lbl: str(int(counts[lbl] / total * 100)) + "%" for lbl in counts}

Każdy Decision_Node przechowuje jedno Question — indeks kolumny plus wartość — a match porównuje z nim wpis wiersza w tej kolumnie, zwracając zwykłe True albo False. Ta wartość logiczna to jedyne, czego potrzebuje classify: True wysyła wiersz w true_branch, False w false_branch, a rekurencja zatrzymuje się, gdy tylko wyląduje na Leaf.

Weźmy dane jednego pacjenta, ['fixed', 0, 'Yes'], i zobaczmy, jak drzewo przewiduje, czy ma on chorobę serca:

1. korzeń pyta Is vessels >= 1?; match odczytuje wpis vessels pacjenta — to 0 — a ponieważ wartość jest liczbowa, oblicza 0 >= 1, dając False, więc wiersz idzie gałęzią fałszywą;
2. ten węzeł pyta Is stress_test == fixed?; match odczytuje wpis stress_test pacjenta — 'fixed' — a ponieważ wartość jest napisem, oblicza 'fixed' == 'fixed', dając True, więc wiersz idzie gałęzią prawdziwą;
3. ta gałąź to Leaf, więc classify zwraca zapisane tam zliczenia: jeden Yes i jeden No.

Te zwrócone przez classify zliczenia są predykcją w surowej postaci. Można je odczytać jako jedną etykietę, biorąc tę częstszą w liściu — tak robi predict w bibliotece takiej jak sklearn, i jest to jednoznaczne w czystych liściach, gdzie {'Yes': 2} znaczy Yes. Można je też odczytać jako prawdopodobieństwo, dzieląc każde zliczenie przez sumę, czyli predict_proba, i to właśnie robi tu print_leaf.

Dla tego konkretnego pacjenta zliczenia są po jednym z każdego, więc dwa odczyty brzmią „brak większości” i „50/50” — ten sam fakt, dwa razy. A 50/50 to właściwa odpowiedź: dwoje pacjentów treningowych ma dokładnie te cechy i się nie zgadza, więc model twierdzący z pewnością siebie kłamałby, co w tej dziedzinie nie jest przenośnią. To błąd nieredukowalny, a zliczenia w liściu raportują go za darmo, bez żadnej dodatkowej maszynerii do niepewności.

Widżet poniżej to nieco większa zabawka — dwie cechy liczbowe, progi zamiast naszych mieszanych typów — ale mechanizm jest identyczny i pokazuje dwa widoki drzewa naraz. Lewy panel to podział; prawy to spacer. Dwa suwaki to wartości cech $x_1$ i $x_2$ — przeciąganie ich układa nowy wiersz i przesuwa go po przestrzeni cech. Moment, w którym ten punkt przecina przerywaną linię, to dokładnie moment, w którym zmienia się ścieżka przez drzewo, bo obszar i liść to ten sam obiekt w innym stroju.

Zauważ też, że to drzewo używa cechy oznaczonej $x_1$ dwa razy — raz w korzeniu i znowu dwa poziomy niżej przy innym progu. To dwa różne pytania o jedną kolumnę — ta sama cecha, inna wartość — bo cecha nie zużywa się przez to, że po niej podzielono: pierwsze cięcie rozdziela, co może, a pozostałe wiersze mogą wciąż być rozdzielalne wzdłuż tej samej osi.

Dlatego liczba węzłów decyzyjnych i liczba cech są niezależne. Cechy dostarczają tylko menu; dane rozstrzygają, które pytania zostaną zadane i jak często — a to menu jest przebudowywane w każdym węźle, a nie ustalone raz dla całego drzewa. find_best_split odczytuje je z wierszy przed sobą, values = set([row[col] for row in rows]), więc lista pytań kandydujących kurczy się razem ze stosami: nasz korzeń może zapytać Is vessels >= 2?, ale węzeł pod nim już nie, bo żaden wiersz, który tam dotarł, nie ma dwójki.

Teraz podajmy mu pięciu pacjentów, których nigdy nie widziało, wszystkich będących prawdziwymi wierszami z tego samego pliku:

patient   2  ['normal',     3]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient   9  ['reversable', 1]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient 266  ['fixed',      0]   Actual: Yes.  Predicted: {'Yes': '50%', 'No': '50%'}
patient  88  ['NA',         0]   Actual: No.   Predicted: {'No': '100%'}
patient 267  ['NA',         0]   Actual: Yes.  Predicted: {'No': '100%'}

Pierwszy wiersz testowy to ['normal', 3, 'Yes'], a liczba vessels równa 3 nigdy nie pojawiła się w treningu — nasi pięcioro pacjentów pokazywali tylko 0, 1 i 2. Mimo to wpada do liścia, bo vessels >= 1 jest progiem, a nie wyszukiwaniem: 3 go przekracza i idzie tą samą ścieżką co 1. Progi uogólniają poza swoje wartości treningowe za darmo.

Z brakującymi wartościami jest inaczej: model po prostu nie obsługuje ich poprawnie. Pacjenci 88 i 267 nie mają zapisanego testu wysiłkowego — w pliku widnieje NA — a ponieważ NA nigdy nie pojawiło się w treningu, test stress_test == fixed? zawodzi i wiersz zsuwa się gałęzią False, przez co pacjent 267 wraca jako {'No': '100%'}, choć chorobę ma.

W praktyce zajęłbyś się tym przed treningiem — usunął niekompletne wiersze, uzupełnił braki albo uczynił z "missing" osobną kategorię.

Ale czyszczenie danych treningowych nie zamyka luki, bo pacjent przybywający jutro wciąż może przynieść wartość stress_test, której drzewo nigdy nie widziało. Porównanie ==, którego match używa na kolumnie kategorycznej, zawodzi, wiersz zsuwa się gałęzią False, a odpowiedź wraca wyglądając dokładnie tak jak dobrze ugruntowana. To milczenie jest prawdziwą wadą — nie to, że drzewo się myli, lecz to, że nic w {'No': '100%'} nie odróżnia trzech pewnych wierszy treningowych od wartości, której model nigdy nie napotkał.

Prawdziwe biblioteki drzew są zaprojektowane tak, by radzić sobie z brakami bez żadnej wstępnej obróbki zbioru. XGBoost uczy się domyślnego kierunku dla każdego podziału, wysyłając wiersze, na które nie potrafi odpowiedzieć, w tę stronę, która lepiej wypadła na danych treningowych, a oryginalne sformułowanie CART trzyma podziały zastępcze — zapasowe pytania skorelowane z głównym, zadawane każdemu wierszowi, który nie potrafi na nie odpowiedzieć.

Dlaczego jedno drzewo to nie koniec historii

Model, który zbudowaliśmy, to prawdziwy CART w około 200 liniach czystego Pythona, i jeśli skierujesz go na prawdziwe dane, wyrośnie ci prawdziwe drzewo. Nasza implementacja ma jednak dwa problemy, a reszta świata drzew istnieje po to, by sobie z nimi radzić.

Po pierwsze, drzewo przetrenuje się, jeśli nic nie zatrzyma jego wzrostu. Przetrenowanie to zapamiętanie przez model danych treningowych zamiast nauczenia się z nich, a przez to utrata zdolności uogólniania na cokolwiek innego. W sieci neuronowej dzieje się to przez wagi: przy wystarczającej pojemności i zbyt słabej regularyzacji spadek gradientu dostraja je, aż sieć odtworzy swój zbiór treningowy niemal dokładnie. W drzewie dzieje się to przez dzielenie: bez kontroli build_tree tnie dalej, aż niemal każdemu wierszowi treningowemu wręczy własny czysty liść, bo gain == 0 jest jedyną rzeczą, która go zatrzymuje. Oś pojemności to nie „jak długo trenowałeś”, lecz „jak głęboko wyhodowałeś”, dlatego każdy regularyzator dla drzew jest strukturalny — limity głębokości, minimalne rozmiary liści, przycinanie.

Zobaczmy, jak ten problem objawia się na prawdziwym zbiorze danych, używając sklearn jako uczciwego dublera naszego kodu: zostaw DecisionTreeClassifier(criterion="gini") na domyślnych ustawieniach — bez limitu głębokości, bez minimalnego rozmiaru liścia, bez przycinania — a on też nie ma innej reguły stopu niż czystość, więc drzewo, które wyhoduje, to drzewo, które wyhodowałby build_tree, tylko policzone szybciej.

Teraz skierujmy go na zbiór o raku piersi (398 wierszy treningowych, 171 testowych, 30 cech):

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, test_size=0.3, random_state=0
)

unpruned = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_tr, y_tr)
print(unpruned.get_depth(), unpruned.get_n_leaves())
print(unpruned.score(X_tr, y_tr), unpruned.score(X_te, y_te))

for depth in (1, 2, 3, 5, 7):
    pruned = DecisionTreeClassifier(
        criterion="gini", max_depth=depth, random_state=0
    ).fit(X_tr, y_tr)
    print(depth, pruned.score(X_tr, y_tr), pruned.score(X_te, y_te))

Niepohamowane drzewo — to, którego nic nie powstrzymuje — wychodzi tak:

UNPRUNED (what build_tree does)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

Dokładność to tutaj po prostu ułamek wierszy, których przewidziana etykieta zgadza się z zapisaną — mierzony na 398 wierszach, z których drzewo zbudowano, i ponownie na 171, których nigdy nie widziało. Dokładność treningowa 1.000 oznacza zatem, że trafiło wszystkie 398, co osiągnęło dzieląc, aż maruderzy — wiersze, które odmówiły grupowania się z czymkolwiek — usiedli każdy we własnym liściu: to samo zachowanie gain == 0, które oglądaliśmy na pięciu pacjentach, tyle że z 398 wierszami zamiast 5.

Dodajmy teraz jedno pokrętło, którego nasza wersja nie ma — max_depth, twardy limit tego, na ile pytań w głąb drzewo może pójść, zatrzymujący dzielenie niezależnie od tego, czy został jeszcze przyrost do zebrania. Gdy uruchomimy to samo drzewo ograniczone serią głębokości i zbierzemy wyniki, wychodzi to:

Przeczytaj dwa ostatnie wiersze jeden przeciw drugiemu, bo w tym tkwi cała lekcja. Przejście z głębokości 2 na 7 poprawia dokładność treningową z 0.960 do 1.000 i czyni model gorszym — dokładność testowa spada z 0.947 do 0.912. Nieprzycięte drzewo nie jest jedynie rozrzutne. Bije je drzewo o jednej trzeciej jego głębokości, które myli 4% danych treningowych. Te dodatkowe pięć poziomów głębokości to zapamiętywanie 398 konkretnych wierszy, a build_tree nie ma jak się o tym dowiedzieć, bo od środka każdy z tych podziałów zmniejszał nieczystość.

Drugi problem to niestabilność drzewa — zmień dane odrobinę, a może wyjść w innym kształcie. Co sprowadza nas z powrotem do >=, którym porównywaliśmy przyrost każdego kandydata z najlepszym dotąd, oraz do kolejności, w jakiej pętla akurat odwiedza tych kandydatów. Zachłanne ocenianie produkuje remisy i prawie-remisy na prawdziwych danych bez przerwy, a to, która strona wygra, sprowadza się do nieudokumentowanego szczegółu implementacyjnego — widziałeś, jak dzieje się to w korzeniu: dwa pytania o identycznych wynikach i jeden znak rozstrzygający między nimi. Skieruj ten sam kod na pełne badanie z Cleveland — 297 pacjentów bez braków, wszystkie trzynaście predyktorów, 207 wierszy do treningu i 90 odłożonych — a w dziesięciu z 35 węzłów decyzyjnych gotowego drzewa dwa pytania kandydujące uzyskują dokładnie ten sam wynik, tnąc pacjentów na różne stosy. Nic w danych ich nie rozdziela, więc to, które algorytm zachowa, jest arbitralne — a cokolwiek zaburzy wyniki, odwraca wybór i przebudowuje wszystko poniżej.

A koszt spada na prawdziwych pacjentów. Usuń jeden wiersz treningowy i dopasuj ponownie, a drzewo, które wróci, odeśle do domu z inną diagnozą aż 12 z 90 odłożonych pacjentów. Nie zmieniaj zupełnie nic, a predykcje i tak się poruszą — find_best_split odwiedza remisujących kandydatów w kolejności, w jakiej iteruje set, a ta różni się z uruchomienia na uruchomienie, więc dziesięć przebiegów na identycznych pacjentach dało cztery odrębne modele, niezgadzające się ze sobą co do nawet 4 z 90 diagnoz. Dwa przebiegi na tych samych danych wręczają ci dwa różne modele, oba poprawne wedle własnych kryteriów algorytmu.

Te dwa zachowania to dwie strony kompromisu obciążenia i wariancji. W uczeniu statystycznym obciążenie (bias) to błąd wprowadzony przez przybliżanie skomplikowanej rzeczywistości prostszym modelem — model zbyt sztywny, by odwzorować wzorzec, będzie się mylił niezależnie od tego, ile danych mu wręczysz. Wariancja to wielkość, o jaką zmieniłby się dopasowany model, gdybyś oszacował go z innego zbioru treningowego: przetrenuj na innej próbie pacjentów, a metoda o wysokiej wariancji da ci zauważalnie inny model, popełniający zauważalnie inne błędy.

Te dwie wielkości poruszają się w przeciwnych kierunkach wraz ze wzrostem elastyczności metody, a dla drzewa elastycznością jest głębokość. Trzymaj je płytkie, a będzie zbyt proste, by uchwycić wzorzec — wysokie obciążenie — ale stabilne: wytrenuj je na innej próbie i wróci mniej więcej to samo drzewo. Pozwól mu rosnąć, a dopasuje wszystko, włącznie z szumem — niskie obciążenie — kosztem dokładnie tej niestabilności opisanej wyżej, czyli wariancji. Dokładność treningowa nagradza zawsze tylko pierwszą z tych dwóch, bo głębsze drzewo zawsze lepiej dopasowuje własne wiersze, podczas gdy dokładność testowa odpowiada obu — dlatego w tabeli osiąga szczyt przy głębokości 2 i stamtąd zjeżdża. I żadna głębokość nie sprowadzi błędu testowego do zera, bo pod oboma składnikami leży błąd nieredukowalny, którego spotkaliśmy przy liściu 50/50 — ta część wyniku, której cechy po prostu nie determinują.

Istnieją ugruntowane metody radzenia sobie z tymi problemami — limit głębokości, minimalna liczba wierszy na liść, minimalny przyrost warty podziału oraz obcinanie gałęzi po fakcie. W praktyce rzadko stosuje się je do samotnego drzewa; to pokrętła, które kręcisz wewnątrz zespołu — modelu zbudowanego z wielu drzew, których odpowiedzi łączy się w jedną, a właśnie tym są las losowy i gradient boosting.

Przyjrzyjmy się jednemu rozwiązaniu stosowanemu na poziomie pojedynczego drzewa — przycinaniu, które sprowadza się do zastąpienia gain == 0 regułą stopu wiedzącą, kiedy skończyć. Środki zaradcze dzielą się na dwie nazwane rodziny. Wstępne przycinanie (wczesne zatrzymanie) odmawia wzrostu w ogóle: max_depth, minimum wierszy na podział lub na liść, progi minimalnego przyrostu — suwak głębokości powyżej był wstępnym przycinaniem w najprostszej postaci. Jest tanie, ale zachłanne w drugim sensie: słaby podział może być bramą do silnego pod nim, a drzewo zatrzymane wcześnie nigdy się o tym nie dowie (znane jako efekt horyzontu). Przycinanie po fakcie pozwala drzewu urosnąć w pełni, a potem obcina gałęzie, które nie zarabiają na siebie na danych odłożonych; kanoniczna wersja CART to przycinanie koszt-złożoność: oceń drzewo jako jego błąd plus cena za liść i obetnij to, co nie zarabia na swoje utrzymanie. To wreszcie jawnie wypisana funkcja straty drzewa — składnik dopasowania plus kara za złożoność, ten sam kształt, jaki regularyzacja przybiera wszędzie indziej — a sklearn wystawia tę cenę jako ccp_alpha.

Niestabilności zwykle nie naprawia się w obrębie pojedynczego drzewa w ogóle. Zamiast szukać sprytniejszego rozstrzygania remisów, przestajesz polegać na jednym drzewie. Wyhoduj ich wiele, każde na nieco innej próbie wierszy i kolumn, żeby lądowały po różnych stronach remisów, a potem uśrednij ich odpowiedzi: to las losowy, a uśrednianie jest tym, co znosi wariancję. Wyhoduj je zamiast tego w sekwencji, każde poprawiające to, co poprzednie pomyliło, i to jest gradient boosting, zbudowany z tych samych drzew, które właśnie napisaliśmy — z limitem głębokości i innym celem — w From one tree to XGBoost.

Gdzie nasza wersja jest wolniejsza od prawdziwej

W naszej implementacji brakuje jednej ważnej techniki optymalizacyjnej, którą ma każda prawdziwa biblioteka. Wszystko inne zgadza się z tym, co robi implementacja produkcyjna — te same pytania kandydujące, ta sama nieczystość, ten sam przyrost, ten sam wybrany podział — ale find_best_split w postaci, w jakiej go napisaliśmy, to przegląd zupełny w dosłownym sensie.

Pętla przebiega po każdej cesze i każdej różnej wartości, jaką ta cecha przyjmuje, więc liczba kandydatów to cechy × wartości. Każdy kandydat kosztuje potem pełne przejście po danych: partition obchodzi każdy wiersz, by posortować go do dwóch stosów, a info_gain wywołuje gini na każdym stosie, które liczy jego etykiety od zera. To $O(\text{features} \times \text{values} \times \text{rows})$. Na pięciu wierszach z trzema wartościami na kolumnę — niewidoczne. Na cesze ciągłej — powiedzmy cholesterolu — niemal każdy wiersz niesie inną wartość, więc liczba kandydatów rośnie razem z danymi, a każdy kandydat wciąż kosztuje pełny skan: kwadratowo względem liczby wierszy i beznadziejnie przy stu tysiącach.

Weź pięć wierszy kolumny cholesterol — 210 (No), 233 (No), 250 (Yes), 286 (Yes), 300 (Yes). Generator zamienia je w pięć pytań kandydujących, po jednym na zaobserwowaną wartość, z których cztery faktycznie dzielą stos:

Prześledźmy dwóch z nich, >= 233 i >= 250, przez nasz kod.

Dla >= 233 partition obchodzi wszystkie pięć wierszy i wrzuca 210 na listę False, a pozostałe cztery na listę True. info_gain wywołuje potem gini na każdej, a gini obchodzi jednowierszowy stos, licząc etykiety, a potem czterowierszowy stos, licząc etykiety. Pięć odwiedzin na podział, pięć na liczenie. Dla >= 250 zaczyna od nowa od tych samych pięciu wierszy, i tak dalej w dół listy:

>= 233:  partition 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  partition 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  partition 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  partition 5 rows → gini({210,233,250,286}) + gini({300})   = 10 visits

Czterdzieści odwiedzin wierszy, i nic nie jest przenoszone między liniami — mimo że każda para stosów różni się od pary powyżej dokładnie jednym wierszem.

Oto te same pięć wierszy, posortowane po cholesterolu i niosące etykietę disease, jaką każdy pacjent okazał się mieć — tak trzymałaby je prawdziwa implementacja:

Prawdziwe implementacje wyciągają obie odpowiedzi z pierwszego przejścia. Posortuj wiersze po cesze, a potem, oceniając pierwszego kandydata, przejdź przez nie raz, prowadząc bieżące zestawienie widzianych dotąd etykiet — do końca tego jednego przejścia każdy późniejszy kandydat też ma już odpowiedź:

Każda linia to linia powyżej plus etykieta właśnie minionego wiersza: 210 to No, więc zestawienie otwiera się na {No: 1}; 233 to kolejne No, doprowadzające do {No: 2}; 250 to Yes, dodające pierwsze Yes; i tak dalej. Jeden przyrost na wiersz, pięć wierszy, jedno przejście.

Ponieważ wiersze przychodzą w porządku rosnącym, każde z tych zestawień jest też grupą wpadającą poniżej określonego progu — i to właśnie zamienia je w odpowiedź:

Ponieważ wzór na przyrost waży oboje dzieci, potrzebne są obie grupy — ale w trakcie przejścia śledzona jest tylko pierwsza. Grupy na progu lub powyżej nigdy nie trzeba liczyć; da się ją wyprowadzić. Własne sumy węzła zostały policzone przy jego tworzeniu — tutaj {No: 2, Yes: 3} — więc cokolwiek nie jest poniżej progu, jest powyżej. Żadne pytanie niczego nie odczytuje ponownie — po dwa odczyty i odejmowanie na każde, a Gini wynika z czterech liczb całkowitych.

Jedna taka tabela powstaje na cechę, bo każda kolumna ma własne uporządkowanie i własne progi: posortuj po cholesterolu i przejedź go, potem posortuj po wieku i przejedź to, i tak dalej, a najlepsza linia we wszystkich tabelach staje się pytaniem węzła. Na tym polega cała różnica. Nasza wersja płaci jedno pełne przejście na kandydata; przemiatanie płaci jedno przejście na cechę, a potem odczytuje każdego kandydata z tabeli, którą po drodze zbudowało. Przy pięciu wierszach jest to niewidoczne; przy stu tysiącach to różnica między sekundą a tygodniem.