1 Machine learning Lecture 2Marcin Wolter IFJ PAN 9 March 2017 Uporzadkowac Dodac przykłady Proste metody nieliniowe jak naiwny klasyfikator bayesowski, metoda k-najbliższych sąsiadów, metody jądrowe Parzena. Wzmocnone drzewa decyzyjne – Boosted Decision Trees (BDT)

2 Naiwny klasyfikator bayesowskiDane Klasyfikator Nazywany także metodą rzutowanych prawdopodobieństw, ,,projected likelihood''. Rzut na oś X Rzut na oś Y Oparty na założeniu o wzajemnej niezależności zmiennych (dlatego ,,naiwny''): Wynikowe prawdopodobieństwo, że sygnał (tło) jest iloczynem prawdopodobieństw dla poszczególnych zmiennych. Szybki i stabilny, w wielu przypadkach dobrze sprawdza się przy klasyfikacji danych.

3 Identyfikacja tau w eksperymencie ATLASSzereg zmiennych identyfikujących, żadna z nich nie daje „dobrej” identyfikacji => metody wielu zmiennych, informacja ze wszystkich zmiennych. Przykładowe zmienne identyfikujące.

4 Identyfikacja tau – zastosowane metodyCięcia – powszechnie znane. Likelihood (Naive Bayes) – właśnie omówione. Boosted Decision Trees (BDT) –omówimy niebawem

5 Jądrowe estymatory gęstościAproksymacja nieznanego rozkładu prawdopodobieństwa jako sumy funkcji jądrowych (kernel) umieszczonych w punktach xn zbioru treningowego (Parzen, lata 1960-te). Typowe funkcje jądrowe: Gauss, 1/xn itp. Proste pojęciowo, ale użycie tej metody wymaga dużo czasu procesora i pamięci. 𝐷 𝑥 = 𝑃 𝑆 𝑃 𝑆 +𝑃 𝐵 Aproksymowana gęstość prawdopodobieństwa (niebieska) porównana z prawdziwą gęstością prawdopodobieństwa (zielona) w zależności od szerokości funkcji Gaussa użytej jako jądro. Widzimy, że parametr określający jej szerokość, pełni rolę parametru wygładzającego.

6 Pakiet QUAERO z eksperymentu D0Phys. Rev. Lett. 87 (2001) ,

7 Metoda PDE_RS – rozwinięcie metod Parzena*metoda opublikowana przez T. Carli, B. Koblitz, NIM A 501 (2003) Zlicza przypadki sygnału (ns) i tła (nb) w N-wymiarowej kostce dookoła klasyfikowanego przypadku – potrzeba tylko kilku przypadków ze zbioru treningowego. Rozmiary kostki – swobodne parametry metody. Dyskryminator D(x) : Prosta analiza. Przypadki zapisane w drzewie binarnym – szybciej znajdywane są sąsiednie przypadki. Szczególny przypadek metody Parzena – funkcja jądrowa: 𝐷𝑥= 𝑛 𝑆 𝑛 𝑆  𝑛 𝑏 𝑓 𝑥 = 1 𝑥 ≤𝑑 0 𝑥 >𝑑

8 Identyfikacja leptonów τ w eksperymencie ATLASπ+ π0 Przypadki 3-prong Dane do analizy: hadronowe rozpady τ zrekonstruowane za pomocą algorytmu tau1p3p (z danych Monte- Carlo). Żadna ze zmiennych samodzielnie nie zapewnia dobrej separacji sygnału i tła – konieczność użycia metody wielu zmiennych.

9 Identyfikacja z użyciem Sieci Neuronowej oraz PDE_RSSieć neuronowa PDE_RS 3-prong 3-prong Znaczna poprawa odrzucania tła względem analizy z użyciem cięć.

10 Metoda kNN k najbliższych sąsiadówzaproponowana już w 1951 roku zaliczamy obiekt do tej klasy, do której należy większość z jego k najbliższych sąsiadów, lub też określamy prawdopodobieństwo zaliczenia do danej klasy jako:

11 Boosting, bagging, BDT... czyli o łączeniu klasyfikatorów

12 Co oznacza skrót BDT ??? BDT – Boosted Decision Tree:Decision Tree – algorytm znany od dawna, powszechnie stosowany we wszelakich systemach eksperckich. Jako drzewo decyzyjne formułuje się np. schematy działania przy udzielaniu pierwszej pomocy: jeśli coś to zrób to i to, sprawdź dalej inny warunek itd. Boosted – wzmocniony. Metoda łączenia wielu słabych klasyfikatorów w celu uzyskania mocnego klasyfikatora. Nie musi się ograniczać do drzew decyzyjnych! Choć z nimi jest najchętniej używana.

13 Drzewa decyzyjne Drzewo decyzyjne – szereg następujących po sobie cięć, każdy końcowy „liść” (A,B,C,D,E) ma przypisaną klasyfikację, np.”sygnał” i „tło”. Proste w interpretacji i wizualizacji Odporne na przypadki odstające od innych (outliers). Słabe zmienne są ignorowane. Bardzo szybki trening oraz klasyfikacja. Niestety: czułe na fluktuacje, niestabilne.

14 Budowanie drzewa Zaczynamy budowę drzewa od korzenia.Dzielimy zbiór treningowy na dwa poprzez cięcie „najlepiej separujące” na najlepszej zmiennej. Powtarzamy procedurę aż spełnione zostaną warunki końcowe, np. liczba liści, liczba przypadków w liściu itd. Stosunek S/B w liściu określa klasyfikację (binarnie sygnał, tło lub liczba rzeczywista określająca prawdopodobieństwo, że jest to sygnał). Definicje separacji: indeks Gini: (Corrado Gini 1912, używany np. do mierzenia nierównomierności dochodów) p (1-p) : p= P(sygnał), purity Entropia wzajemna: -(p ln p + (1-p)ln(1-p)) Błędna identyfikacja: 1-max(p,1-p)

15 AdaBoost - łączenie klasyfikatorówProblem: czy mając słaby klasyfikator można go poprawić? Odpowiedź: tak, stosując go wiele razy. Najczęściej używany algorytm: AdaBoost (Freund & Schapire 1996 – nagroda Gödla) Zbuduj drzewo decyzyjne Zwiększ wagi źle sklasyfikowanych przypadków Powtarzaj wiele razy (typowo ) Klasyfikuj przypadki na podstawie „głosowania” wszystkich drzew.

16 AdaBoost Działanie algorytmu AdaBoost dla zbioru dwuwymiarowego. Rysunki pokazują rezultaty działania klasyfikatora po pierwszej, drugiej, trzeciej, piątej, dziesiątej i setnej iteracji. Linia ciągła obrazuje działanie kombinowanego klasyfikatora, linia przerywana granice klas otrzymanych z poszczególnych klasyfikatorów. Dla dwóch ostatnich rysunków linią przerywaną zaznaczono granice otrzymane za pomocą algorytmu bagging (zaraz o tym będzie).

17 AdaBoost Pięć lat po publikacji AdaBoost Friedman pokazał, że algorytm minimalizuje wykładniczą funkcję straty: gdzie f(x) jest odpowiedzią algorytmu t = 1 sygnał, t = -1 tło tn·fm(xn)>0 – poprawnie sklasyfikowany tn·fm(xn)<0 – niepoprawnie sklasyfikowany Funkcja wykładnicza szybko rośnie => duża kara za źle sklasyfikowane punkty, algorytm czuły na pojedyncze odstające od reszty dane. Klasyfikacja staje się gorsza, jeśli dane są słabo separowalne. Może użyć innej funkcji? Friedman w 2000 roku zaproponował kilka innych funkcji straty.

18 AdaBoost in action

19 Algorytm AdaBoost 1. Przypisz wszystkim wektorom ze zbioru treningowego wagę wi=1/N. 2. Dla m = 1,...,M: Wytrenuj klasyfikator ym(x) na zbiorze treningowym minimalizując: Oblicz wielkości: Zmień wartości wag poszczególnych wektorów w zbiorze treningowym: Wynik głosowania dany jest jako: Wszystkie klasyfikatory trenujemy na tym samym zbiorze danych, ale z różnym zestawem wag. Wagi te zależą od wyników poprzedniego treningu, a więc trudno jest trenować równolegle wiele klasyfikatorów.

20

21 Wzmacnianie klasyfikatoraBoosting, bagging – w ,,magiczny'' sposób otrzymujemy silny klasyfikator ze słabego. Przeważnie używane do wzmacniania drzew decyzyjnych – Boosted Decision Trees BDT. Dobre wyniki bez pracochłonnego dopasowywania parametrów: „the best out-of-box classification algorithm”. Stosunkowo odporny na przeuczenie. Obecnie bardzo modny i często stosowany. I to z dobrymi skutkami! Naiwny klasyfikator Wzmocniony bayesowski klasyfikator bayesowski Zastosowanie algorytmu wzmacniania (5 iteracji) do naiwnego klasyfikatora bayesowskiego.

22 Boosting – inne funkcje stratyPrzykłady innych funkcji straty używanych w algorytmach typu boosting: Gradient Boost Zalety: Nie są tak czułe na „odstające” punkty Odpowiednio dobrana „czułość” jest ważna, gdy w danych są obszary gdzie miesza się sygnał i tło (błąd Bayesowski jest duży). Wady: Nie mamy szybkiego i prostego algorytmu minimalizacji jak w AdaBoost => minimalizacja jak w ogólnych przypadkach, np. dopasowywania funkcji.

23 Boosting – różne funkcje stratyDiscrete AdaBoost – opisany poprzednio podstawowy AdaBoost Real AdaBoost, LogitBoost, Gentle AdaBoost- modyfikacje (różne funkcje straty oraz algorytmy minimalizacji) zaproponowane przez Friedmana. Przy większych drzewach wyniki identyczne. STUMP:

24 Przetrenowanie Poprawnie PrzetrenowaniePrzetrenowanie – algorytm “uczy się” poszczególnych przypadków, a nie ogólnych zasad. Efekt występuje we wszystkich metodach uczących się. Remedium – kontrola z użyciem dodatkowego zbioru danych. Poprawnie zbiór treningowy zbiór testowy STOP testowy treningowy Przetrenowanie Przykład z użyciem sieci neuronowej.

25 Odporność na przeuczeniePo zastosowaniu klasyfikatora do zbioru danych treningowych widać, że błąd klasyfikacji spada wykładniczo do zera wraz ze wzrostem liczby użytych drzew decyzyjnych. Tym samym błąd klasyfikacji dla niezależnego zbioru testowego powinien rosnąc (przeuczenie). Jednak nic takiego nie widzimy, dla zbioru testowego błąd pozostaje w zasadzie stały! Efekt nie do końca zrozumiały... Rezultat użycia algorytmu AdaBoost do separacji przypadków mSUGRA od przypadków tt¯ przy energiach LHC

26 20 iteracji 50 iteracji 80 iteracji 320 iteracji Przetrenowaniewzmocnionego drzewa decyzyj-nego (BDT) Algorytm wzmacniania zastosowany do drzew decyzyjnych z jednym rozgałęzieniem. Na koniec dzieli przestrzeń na zbyt drobne obszary - przetrenowanie. 20 iteracji 50 iteracji 80 iteracji 320 iteracji

27 Bagging (Bootstrap AGGregatING)Algorytm zaproponowany przez Leo Breimana w 1994 roku: Losuj N przypadków z N-elementowego zbioru treningowego z powtórzeniami Trenuj na tym zbiorze klasyfikator. Klasyfikuj nowe przypadki poprzez głosowanie wszystkich drzew decyzyjnych. Dla tych danych czerwona linia (średnia ze 100 klasyfikatorów) jest gładsza, stabilniejsza, mniej podatna na przetrenowanie niż każdy z nich. Analogia: uśrednienie wielu kiepsko pasujących funkcji daje dobre dopasowanie

28 Bagging Random Forest - dalsze rozwinięcie metody Bagging:K razy losujemy N elementów ze zbioru N elementowego Dla każdego zbioru trenujemy drzewo decyzyjne Budując drzewo w każdym rozgałęzieniu używamy tylko m losowo wybranych zmiennych (dodatkowa randomizacja). Boosting przeważnie daje lepsze przewidywania, ale bagging ma tendencję do zachowywania się lepiej w obecności szumu albo przypadków bardzo odstających od reszty (“outliers”). Bauer and Kohavi, “An empirical comparison of voting classification algorithms”, Machine Learning 36 (1999) Bagging jest algorytmem równoległym, boosting sekwencyjnym.

29 Bagging vs. boosting Porównanie zależności błędu dla różnych algorytmów Boosting i Bagging dla klasyfikacji na dwie klasy w funkcji liczby iteracji. Widać, że dla "stumps" (bardzo małych drzew decyzyjnych) zbieżność Discrete AdaBoost jest gorsza, niż Real AdaBoost. Bagging spisuje się gorzej niż boosting [Friedman 2000]. LogitBoost minimalizuje:

30 Małe ćwiczenie z TMVA Separacja dwóch rozkładów Gaussa w 4 wymiarach.10 drzew 100 drzew drzew STUMPS (drzewa o głębokości 1) 10 drzew 100 drzew drzew Drzewa o głębokości 10

31 Identyfikacja hadronowych rozpadów leptonów tau w eksperymencie ATLASSzereg zmiennych identyfikujących, żadna z nich pojedynczo nie daje dobrej identyfikacji. Użycie metod wielu zmiennych zwiększa skuteczność identyfikacji.

32 Zastosowanie do poszukiwań B→l w eksperymencie BaBar11-D data: 10 ciągłych i 1 dyskretna zmienna. Niektóre zmienne są silnie skorelowane ρ(Fisher,acthrust)=0.8 oraz ρ(costheblg,nuEP)=-0.87. Dane Monte Carlo: trening = 500K walidacja = 250K test = 250K

33 Wyniki Znaczenie sygnału (signal significance) uzyskane za pomocą różnych metod klasyfikacji: Trening 50 „boosted decision trees” lub 100 „bagged decision trees” zajął kilka godzin na komputerach SLACu. W1 i W0 są oczekiwanymi liczbami przypadków sygnału i tła przy świetlności 210 fb-1 . Najczystszy sygnał z użyciem „bagging decision trees”. „Bagged decision trees” poprawiają o 14% czystość sygnału w porównaniu do „boosted decision trees”: 8% dzięki użyciu „bagging” zamiast „boosting”. 9% dzięki optymalizacji S/√(S+B) zamiast indeksu Gini.

34 Eksperyment Mini-BooNE – wiązka neutrin

35 Przykładowe przypadki

36 Porównanie drzew decyzyjnych i sieci neuronowejA. Tło: “cocktail events”. Czerwony zmiennych, czarny zmienne. B. Tło: przypadki z Pi0. Czerwony zmienne, czarny - 52 zmienne. Pokazany stosunek: Użycie drzew decyzyjnych dało lepsze wyniki oraz szybszy trening. 𝑅= 𝑁 𝑡ł𝑜 𝑆𝑖𝑒ć𝑁𝑒𝑢𝑟𝑜𝑛𝑜𝑤𝑎 𝑁 𝑡ł𝑜 𝐷𝑟𝑧𝑒𝑤𝑜𝐷𝑒𝑐𝑦𝑧𝑦𝑗𝑛𝑒 Signal efficiency [%]

37 Podsumowanie Boosting, bagging – w „cudowny” sposób można uzyskać silny klasyfikator ze słabego Stosowany przeważnie dla drzew decyzyjnych – bo proste, szybkie w nauce i klasyfikacji. Daje dobrze wyniki, często bez pracochłonnego tuningu parametrów - „the best out-of-box classification algorithm”. Coraz popularniejszy w fizyce wysokich energii Może po prostu modny... Czy należy teraz już tylko stosować BDT: „Jeżeli metoda daje wynik zbliżony do limitu Bayesa, to nie jest możliwe poprawienie wyniku, nawet poprzez stosowanie najbardziej wymyślne metody klasyfikacji.” Harrison B. Prosper