Jak udoskonalić algorytm drzew decyzyjnych?

Słowem przypomnienia, drzewo decyzyjne jest strukturą, która może być użyta do podzielenia dużej liczby obserwacji (rekordów) na kolejne mniejsze zbiory poprzez zastosowanie sekwencji prostych reguł decyzyjnych, które można zapisać w formie „jeżeli.. to..” Z każdym kolejnym podziałem, poszczególne grupy stają się coraz bardziej jednorodne ze względu na badane zjawisko, czyli zmienną objaśnianą. Co istotne, wszystkie reguły podziału można zaprezentować w graficznej formie drzewa, co znacznie ułatwia interpretację wyników, a także samego działania algorytmu.

Drzewa decyzyjne jako algorytm miały swoje początki już w latach 70[1]., jednak podobieństwa w sposobie klasyfikacji możemy doszukać się już u się u Karola Linneusza, który dokonał znanego podziału istot żywych na królestwa, gromady, klasy, rodziny, rodzaje i gatunki  już w latach 30. XVIII wieku[2]. Jednak od tego czasu powstało wiele form budowy tego typu modeli, opartych na różnych miarach. Obecnie często wykorzystuje się ten klasyczny algorytm jako podstawę do budowy bardziej zaawansowanych algorytmów z dziedziny uczenia maszynowego. Mimo, że drzewa decyzyjne to bardzo skuteczna metoda, to niestety jak większość algorytmów nie jest pozbawiona wad. Jednym z głównych problemów, z jakimi możemy się spotkać opierając swoją predykcję o drzewo decyzyjne, może być niestabilność wyników. Oznacza to, że model drzewa decyzyjnego jest wrażliwy na specyfikę zbioru danych i nawet jego niewielka modyfikacja może prowadzić do rozwinięcia zupełnie innego drzewa. Stąd pomysł udoskonalenia tego klasycznego modelu z dziedziny data mining.

Agregacja Bootstrapowa (bagging)

Takiej próby rozwiązania problemu niestabilności drzew decyzyjnych podjął się w 1996 roku Breiman, proponując rozwiązanie, które jednocześnie wykorzystuje moc predykcyjną nie jednego, lecz wielu modeli drzewa, nazywając je Agregacją Bootstrapową. Sposób działania baggingu, bo tak inaczej nazywana jest agregacja bootstrapowa, polega na wytworzeniu kilku podzbiorów uczących z pierwotnego zbioru danych. Każdy z tych podzbiorów jest wybierany z oryginalnego poprzez losowanie ze zwracaniem. Przy tego typu losowaniu,  część obserwacji nie zostaje wybrana do próby uczącej, w związku z czym pełni rolę zbioru walidacyjnego (Out of Bag). Inaczej mówiąc, idea polega na wielokrotnym losowaniu i w efekcie wielokrotnym podziale danych na zbiór uczący i testowy. Stąd nie ma potrzeby dzielić pierwotnego zbioru na uczący i walidacyjny - jest to element integralny działania algorytmu.

Następnym krokiem działania algorytmu jest zbudowanie modeli drzewa na każdej z wylosowanych prób. Na ostateczny wynik predykcji mają wpływ wszystkie drzewa użyte do wytrenowania modelu, a jest on wybierany za pomocą głosowania. Głosowanie w przypadku problemów klasyfikacyjnych może oznaczać, że finalną odpowiedzią algorytmu jest ta, która została wskazana przez największą liczbę pojedynczych drzew. Opierając wynik predykcji o wskazania wielu drzew budowanych na zróżnicowanych zbiorach, sprawiamy, że wzorce zawarte w danych stają się bardziej uniwersalne i nie dadzą uwieść się specyfice konkretnych danych. 

Bagging (agregacja bootstrapowa) 

Co zatem było nie tak z metodą baggingu, skoro Breiman zauważył potrzebę stworzenia nowego algorytmu? Odpowiedzią na to pytanie jest sam sposób działania drzew decyzyjnych. Konkretyzując, jeśli do budowy każdego drzewa w baggingu wykorzystywane są dokładnie te same predyktory, to w przypadku zmiennych bardzo silnie skorelowanych z objaśnianym zjawiskiem może zdarzyć się tak, że każde drzewo wybierze do pierwszego podziału tę samą zmienną, mimo, że inne zmienne mogą być tylko nieznacznie słabiej skorelowane ze zmienną objaśnianą.

To z kolei będzie miało wpływ na dalsze podziały. Do tego wszystkiego dochodzi wątek potencjalnego użycia dużej liczby zmiennych, w efekcie czego uzyskanie ostatecznego wyniku staje się bardzo skomplikowane i czasochłonne. W rezultacie tych ograniczeń, pomimo zbudowania wielu drzew, nie uzyskamy satysfakcjonująco stabilnego modelu ze zdolnością do uogólniania wyników na dane znajdujące się poza naszym zbiorem danych ze względu na podobną strukturę pojedynczych klasyfikatorów.

Lasy Losowe

W odpowiedzi na ten problem, w 2001 roku Breiman zaproponował technikę, o wdzięcznej nazwie Lasy losowe. Algorytm Lasów losowych to jedna z bardziej popularnych i wszechstronnych metod z dziedziny uczenia maszynowego. Algorytm ten, podobnie jak pojedyncze drzewo decyzyjne oraz wcześniej opisywany bagging, jest zdolny do rozwiązywania zarówno problemów regresyjnych, jak i klasyfikacyjnych. Zasada działania algorytmu Lasu losowego jest bardzo podobna do agregacji bootstrapowej, z tą różnicą, że do poszczególnych modeli drzew decyzyjnych wykorzystywane są nie wszystkie dostępne predyktory, a jedynie ich część. Po pierwsze, w algorytmie Lasów losowych, analogicznie jak było to w przypadku baggingu, najpierw losujemy ze zwracaniem interesującą nas liczbę podzbiorów z uwzględnieniem obserwacji służących do walidacji modelu.

Kolejny krok to wybór odpowiednich zmiennych objaśniających dla każdego podzbioru, który powinien odbyć się na zasadzie losowania. W tym algorytmie, analogicznie jak w przypadku baggingu o ostatecznym wyniku predykcji decyduje największa liczba głosów, tzn. wynikiem całego modelu Lasów losowych jest wartość, która została przewidziana przez największą ilość pojedynczych modeli drzew.

Lasy losowe

 Przy całym zachwycie nad powyższym algorytmem, nie należy zapominać, że nic nie jest za darmo. Ceną jaką płacimy za większą stabilność modelu jest dłuższy czas obliczeń niż w przypadku klasycznego (pojedynczego) modelu drzewa oraz trudniejsza interpretacja wyników i bardziej rozbudowane reguły predykcyjne. Na tym etapie, problem z niestabilnością modeli predykcyjnych mamy rozwiązany. A co w takim razie jeśli podczas modelowania dotknął nas inny częsty problem, tym razem dotyczący skuteczności predykcji?

Adaboost

Jedną z metod ulepszania “tego co już mamy” jest łączenie klasyfikatorów, czyli pojedynczych modeli w zespoły. Pod pojęciem zespołu kryje się taki model, w którego skład wchodzą mniej skomplikowane klasyfikatory, na podstawie których podejmowana jest ostateczna decyzja. Jak się później okaże, umiejętne dobieranie zespołu może przynieść wiele korzyści. Ogólną ideą tego typu algorytmów jest zbudowanie złożonego modelu o dużej sile predykcyjnej, na który składa się wiele słabych klasyfikatorów. Słabe w tym kontekście to takie, których celem nie jest osiągnięcie maksymalnej skuteczności przez pojedynczy model drzewa, w związku z czym drzewa nie są tutaj bardzo rozbudowywane. Takim podejściem do analizy cechuje się między innymi algorytm AdaBoost[3], którego nazwa pochodzi od Adaptative Boosting (z ang. Wzmocnienie adaptacyjne). Algorytm ten zdobył uznanie w środowisku analitycznym i stał się pierwowzorem dla rozwoju innych technik wzmacniania. Zasadnicza różnica między AdaBoost, a omawianymi wcześniej Lasami losowymi polega na tym, że Lasy losowe działają w sposób równoległy, tzn. pojedyncze drzewa nie są od siebie zależne, natomiast AdaBoost wręcz przeciwnie. Tutaj podejście jest sekwencyjne, a kolejne klasyfikatory są ze sobą ściśle związane.

AdaBoost

W pierwszej iteracji procesu budowy modelu konstruowany jest bazowy klasyfikator. W drugiej i każdej następnej iteracji, koncentrujemy się na tych obiektach, które zostały źle zaklasyfikowane przez model poprzedni. Poprawa niedoskonałości modelu poprzedzającego odbywa się poprzez dostosowanie wag w następnej iteracji. Precyzując, początkowo wagi dla wszystkich rekordów są jednakowe, a podczas kolejnych iteracji, czyli podczas budowy kolejnych modeli drzew, wagi obserwacji, które zostały błędnie wyestymowane będą zwiększone, a tych z poprawną predykcją zmniejszone. W związku z tym każde kolejne drzewo budowane jest na odpowiednio zbalansowanym zbiorze treningowym, co jest alternatywą dla podejścia wykorzystywanego przy okazji Lasów losowych, a mianowicie losowania podzbiorów dla poszczególnych drzew. Na tym właśnie polega sekwencyjność działania tego algorytmu. W AdaBoost każde kolejne drzewo stara się poprawnie sklasyfikować to co zostało przez wcześniejsze drzewa źle sklasyfikowane. Inaczej mówiąc, staramy się eliminować błędy poprzedniego modelu.

Omówione powyżej sekwencyjne podejście do budowania zespołu modeli zyskało dużą popularność i systematycznie jest rozwijane, tworząc tym samym coraz nowocześniejsze metody z zakresu uczenia maszynowego. Bazując na tym właśnie podejściu oraz czerpiąc inspirację ze sposobu działania sieci neuronowych, powstał nowy sposób minimalizacji błędów pojedynczych modeli w ramach algorytmu. Metodą dopasowania ma być w tym przypadku spadek gradientu, dzięki któremu minimalizujemy reszty, czyli różnicę pomiędzy wartością rzeczywistą a tą przewidywaną przez model. Przykładowo, jeśli naszym celem jest prognoza cen mieszkań, to resztą będzie różnica pomiędzy faktyczną ceną mieszkania, a tą którą wskazał model. Naturalnie zależy nam, aby błędy w klasyfikacji były jak najmniejsze. Zgodnie ze strategią przyrostową stosowaną w metodach gradientowych, jakość budowanego modelu ulega poprawie podczas kolejnych przebiegów. Błędy zmniejszą się z każdą kolejną iteracją, co w praktyce mogłoby doprowadzić do stanu idealnego, w którym ostateczny model nie popełnia żadnego błędu. Nie zapominajmy jednak o konsekwencjach tak dobrego dopasowania. W rzeczywistości, model taki staje się przetrenowany, gdyż jest on dobrze dopasowany, ale tylko do danych uczących. Wobec tego traci zdolność do uogólniania wyników, a tym samym model może mieć ograniczoną użyteczność na nowych danych. Rozwinięciem takiego podejścia podnoszącym efektywność uczenia jest algorytm XGBoost.

XGBoost

XGBoost (Extreme Gradient Boosting), czyli algorytm wzmacniania gradientowego to obecnie jedna z najpopularniejszych metod z dziedziny data mining, zaproponowana w 2016 roku przez Tiangi Chen. W XGBoost ponownie mamy do czynienia z zespołem klasyfikatorów, którymi mogą być modele drzew decyzyjnych. Tutaj również na ostateczną decyzję dotyczącą klasyfikacji poszczególnych obserwacji mają wpływ wszystkie drzewa użyte do budowy algorytmu. Analogicznie jak w algorytmie Friedmana, XGBoost wykorzystuje strategię przyrostową, z uwagi na to, że jest to zadanie mniej skomplikowane i czasochłonne niż wytrenowanie wszystkich drzew jednocześnie. Innowacją w tym podejściu jest natomiast wprowadzenie składnika regularyzacji. Regularyzacja to swego rodzaju kara nakładana na model za zbyt dużą liczbę ostatecznych segmentów obserwacji, czyli liści w drzewie decyzyjnym. W taki sposób kontrolowana jest złożoność modelu. Stąd ogólna postać algorytmu XGBoost składa się z dwóch części. Pierwszy składnik to ten odpowiadający za minimalizację błędu, nazywany funkcją straty, inaczej funkcją kosztu. Drugi zaś, czyli regularyzacja, pomaga zapobiec przetrenowaniu i kontroluje złożoność modelu. Warto pamiętać w tym miejscu o tym, że żadne rozwiązanie nie jest w stu procentach idealne i posiada swoje wady. Resumując dzisiejszy wpis, istnieje wiele algorytmów, które próbują poradzić sobie z niedoskonałościami, jakie niosły ich pierwowzory. Lasy losowe oraz XGBoost to jedne z nich, które bazując na zespołowych metodach uczenia się, mogą przewidywać zarówno  problemy regresyjne i klasyfikacyjne. Omówione metody, przede wszystkim różnią się celem i problemami, na których się koncentrują. Lasy losowe powstały, by zwiększać stabilność predykcji, natomiast XGBoost, aby zwiększyć dokładność przewidywania. Z pewnością jednak nie jest to ostatnie słowo, jeśli chodzi o coraz to lepsze podejście do modelowania. Ze względu na niedoskonałości istniejących algorytmów oraz pojawiające się nowe problemy w analizie danych oraz nowe możliwości techniczne, uczenie maszynowe to dziedzina wiedzy, która rozwija się nadzwyczaj intensywnie. Która z nich jednak jest najlepsza? Na to pytanie, jak to zwykle bywa należy odpowiedzieć: „to zależy”.