03 · Nadzorowane · 4 min czytania · Interaktywne · aktualizacja
Czym jest zysk informacyjny w drzewie decyzyjnym i jak liczy go XGBoost?
W skrócie
Gain to ocena pytania w drzewie: o ile grupy po podziale są bardziej jednorodne niż przed nim. XGBoost liczy go z gradientów i hesjanów straty, z karami λ i γ.
Co to jest
Gain (zysk podziału) to liczba, którą drzewo decyzyjne przypisuje każdemu kandydującemu pytaniu „cecha ≤ próg”: o ile po podziale dane w dwóch gałęziach są bardziej jednorodne — albo strata jest mniejsza — niż przed nim. Drzewo wybiera podział o największym gain i przestaje dzielić, gdy najlepszy gain jest za mały.
Gdy jednorodność mierzy się entropią, gain nazywa się zyskiem informacyjnym (information gain, algorytmy ID3 i C4.5). W CART częściej używa się nieczystości Giniego, a w boostingu gradientowym (XGBoost, LightGBM) — spadku straty przybliżonej gradientami, z karami za złożoność.
Mechanizm — dlaczego tak działa
Klasycznie: gain = nieczystość(rodzic) − [n_L/n · nieczystość(L) + n_R/n · nieczystość(R)], czyli nieczystość przed podziałem minus średnia ważona nieczystości po nim. Gini dla węzła to 1 − Σ pₖ²: zero, gdy wszystkie przykłady należą do jednej klasy, maksimum przy równych proporcjach. Entropia to −Σ pₖ log₂ pₖ, mierzona w bitach. Podział, który rozdziela klasy na dwie czyste grupy, ma największy gain; podział, po którym obie grupy mają takie same proporcje jak rodzic, ma gain zero.
W XGBoost (Chen i Guestrin 2016) drzewo nie dopasowuje etykiet, lecz poprawkę do obecnych przewidywań. Dla każdego przykładu liczy się gradient gᵢ i drugą pochodną hᵢ straty względem obecnego wyniku. Rozwinięcie Taylora drugiego rzędu daje optymalną wartość liścia w = −G / (H + λ), gdzie G i H to sumy gradientów i hesjanów w liściu, a wkład liścia do spadku straty jest proporcjonalny do G² / (H + λ). Gain podziału = ½ · [G_L² / (H_L + λ) + G_R² / (H_R + λ) − G² / (H + λ)] − γ.
Intuicja: gałąź, w której wszystkie przykłady „ciągną” poprawkę w tę samą stronę (gradienty jednego znaku), ma duże G² i duży zysk; gałąź z gradientami mieszanych znaków ma G bliskie zera i nic nie zyskuje. Kara λ w mianowniku zmniejsza wartości liści z małym H (mało przykładów lub mała pewność), więc drzewo nie ufa małym grupom. Kara γ to stały koszt każdego nowego liścia: podział opłaca się tylko, gdy zysk ją przewyższa — to wbudowane przycinanie.
Zastrzeżenie: wybór jest zachłanny i patrzy jeden krok w przód. Podział bez zysku teraz może umożliwić duży zysk poziom niżej (jak w problemie XOR), czego drzewo nie zobaczy. Gain faworyzuje też cechy o wielu wartościach, bo mają więcej kandydatów na próg — stąd znormalizowany gain ratio w C4.5 i ostrożność wobec ważności cech liczonej z gain.
Na przykładzie
Titanic: 891 pasażerów, przeżyło 38,4%. Nieczystość korzenia: Gini 0,473, entropia 0,961 bitu. Pytanie o płeć dzieli pasażerów na 314 kobiet (przeżyło 74,2%) i 577 mężczyzn (18,9%). Gini spada do średniej ważonej 0,333, więc gain wynosi 0,140; w entropii zysk informacyjny to 0,218 bitu.
Konkurenci wypadają znacznie słabiej. Klasa (1. i 2. przeciw 3.): 55,8% wobec 24,2% przeżyć, gain Giniego 0,049, zysk informacyjny 0,076 bitu. Najlepszy próg ceny biletu (≤ 10,46): 19,8% wobec 49,8%, gain 0,043 i 0,068 bitu. Najlepszy próg wieku (≤ 6 lat): 47 dzieci, z których przeżyło 70,2%, ale reszta grupy prawie się nie zmienia, więc gain to tylko 0,011 i 0,017 bitu. Obie miary wybierają płeć — dlatego DecisionTreeClassifier stawia to pytanie w korzeniu.
Dane: Titanic
W praktyce
- scikit-learn:
criterion="gini","entropy"lub"log_loss";min_impurity_decreaseto minimalny wymagany gain;feature_importances_sumuje ważony gain po cechach (obciążony w stronę cech ciągłych). - XGBoost:
reg_lambda(domyślnie 1),gamma(domyślnie 0),min_child_weight;get_score(importance_type="gain")do ważności; wyższegammaireg_lambdadają prostsze drzewa. - LightGBM: te same wzory pod nazwami
lambda_l2,min_gain_to_split,min_sum_hessian_in_leaf; histogramy progów przyspieszają szukanie. - Ważność z gain pokazuje, czego drzewo użyło, nie co jest przyczynowo ważne; uczciwiej rozdziela wkłady SHAP lub permutacja na walidacji.
- Typowy błąd:
gamma=0i brak limitu głębokości na małych danych — każdy dodatni gain, nawet z szumu, prowadzi do podziału.
Najczęstsze pytania
- Co oznacza gain w XGBoost?
- Spadek straty, przybliżonej gradientami i hesjanami, uzyskany dzięki podziałowi i pomniejszony o karę γ za nowy liść. Większy gain to bardziej opłacalne pytanie. Suma gain po wszystkich podziałach danej cechy daje jej ważność typu „gain”.
- Gini czy entropia — co wybrać?
- W praktyce dają prawie te same drzewa — na Titanicu obie miary wskazały w korzeniu płeć. Gini jest odrobinę szybszy (bez logarytmu) i domyślny w scikit-learn. Różnica w wynikach jest zwykle mniejsza niż wpływ głębokości czy `min_samples_leaf`.
- Co robią parametry lambda i gamma w XGBoost?
- λ (`reg_lambda`) to kara L2 na wartości liści: zmniejsza poprawki z liści o małej sumie hesjanów, czyli z małych grup. γ (`gamma`) to minimalny gain wymagany, by w ogóle zrobić podział — stały koszt każdego liścia. Oba upraszczają drzewa i ograniczają przeuczenie.
Źródła
- Quinlan, J. R. (1986). "Induction of decision trees". Machine Learning 1(1), 81–106.
- Breiman, L., Friedman, J., Olshen, R., Stone, C. (1984). Classification and Regression Trees. Wadsworth.
- Chen, T., Guestrin, C. (2016). "XGBoost: a scalable tree boosting system". KDD, 785–794. arXiv:1603.02754
- Hastie, T., Tibshirani, R., Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed., Springer, rozdz. 9.2.3 "Classification trees", rozdz. 10.10 "Numerical optimization via gradient boosting".
- scikit-learn: "Decision trees — mathematical formulation". https://scikit-learn.org/stable/modules/tree.html#mathematical-formulation