1 Machine learning Lecture 4Marcin Wolter IFJ PAN 7 kwietnia 2017 Uporzadkowac Dodac przykłady Support Vector Machines (SVM). Omówienie zadania zaliczeniowego.

2 Support Vector MachinesGłówne założenie: należy zbudować model używając minimalną liczbę wektorów z danych treningowych (Support Vectors). Przestrzeń: może modelować dowolną funkcję. Funkcjonalnie algorytm podobny do sieci neuronowej, metod jądrowych Parzena itp.

3 Trochę historii Wczesne lata sześćdziesiąte – została opracowana metoda “support vectors” w celu konstruowania hiperpłaszczyzn do rozpoznawania obrazu ( Vapnik i Lerner 1963, Vapnik i Czervonenkis 1964) – liniowa SVM. Początek lat 1990-siątych: uogólnienie metody pozwalające na konstruowanie nieliniowych funkcji separujących (Boser 1992, Cortes i Vapnik 1995). 1995: dalsze rozszerzenie pozwalające otrzymać estymację funkcji ciągłej na wyjściu – regresja (Vapnik 1995).

4 Klasyfikator Liniowy f  yest x f(x,w,b) = sign(w*x - b) oznacza +1Każda z tych linii (klasyfikatorów) jest dobra... ...ale która najlepiej oddziela sygnał od tła?

5 Ta z największym marginesem! f x yest f(x,w,b) = sign(w•x - b) oznacza yi=+1 oznacza yi=-1 “Maximum margin linear classifier” Najprostszy rodzaj SVM, zwany LSVM (liniowa SVM) Support Vectors -punkty ograniczające margines, czyli te na których on się wspiera. Intuicyjnie najlepiej. Nieczuły na błędy w położeniu klasyfikatora. Separacja zależy tylko od wektorów wspierających. Działa w praktyce! ∀ 𝑖 𝑦 𝑖  𝑤  ⋅ 𝑥 𝑖  𝑏−10 𝑤  ⋅ 𝑥  𝑏=0𝑟ó𝑤𝑛𝑎𝑛𝑖𝑒𝑝𝑟𝑜𝑠𝑡𝑒𝑗 𝑚𝑎𝑟𝑔𝑖𝑛= 2 ∣ 𝑤  ∣

6 Trochę matematyki oznacza yi=+1 oznacza yi=- 1 Support Vectors Warunek jaki musi spełniać prosta: opisana wzorem: Margines określony jest wzorem: Musimy maksymalizować margines, czyli minimalizować |w|2. ∀ 𝑖 𝑦 𝑖  𝑤  ⋅ 𝑥 𝑖  𝑏−10 𝑤  ⋅ 𝑥  𝑏=0 𝑚𝑎𝑟𝑔𝑖𝑛= 2 ∣ 𝑤  ∣ Klasyfikator zależy tylko od części danych – wektorów wspierających. Używamy tylko podzbioru wszystkich danych aby zoptymalizować separację.

7 Co zrobić jeśli dane nie są separowalne?Dodajemy dodatkowy człon do naszych równań (“slack variable”): I uzyskujemy: Dla klasyfikatora liniowego (prostej) gdzie C jest arbitralnym parametrem. Funkcja straty jest liniowa, nie kwadratowa!  𝑖 =0  𝑖 =𝑜𝑑𝑙𝑒𝑔ł𝑜ść 𝑥 𝑖 𝑝𝑜𝑝𝑟𝑎𝑤𝑛𝑖𝑒𝑠𝑘𝑙𝑎𝑠𝑦𝑓𝑖𝑘𝑜𝑤𝑎𝑛𝑒 𝑥 𝑖 𝑠𝑘𝑙𝑎𝑠𝑦𝑓𝑖𝑘𝑜𝑤𝑎𝑛𝑒𝑛𝑖𝑒𝑝𝑜𝑝𝑟𝑎𝑤𝑛𝑖𝑒 ∀ 𝑖 𝑦 𝑖  𝑤  ⋅ 𝑥 𝑖  𝑏−1𝐶  𝑖 0 𝑤  ⋅ 𝑥  𝑏=0 𝑚𝑖𝑛𝑖𝑚𝑎𝑙𝑖𝑧𝑢𝑗: 1 2 ∣ 𝑤  ∣ 2 𝐶 𝑖  𝑖 oznacza +1 oznacza -1

8 Przykład jednowymiarowySuper łatwe!!! Wektor wspierający Wektor wspierający

9 Trudniejszy przykład jednowymiarowyTe dane nie są liniowo separowalne! ??? x=0

10 A może przejść do przestrzeni 2-wymiarowej?x -> (x, x2) W tej przestrzeni punkty są liniowo separowalne! x=0

11 W przestrzeni 2-wymiarowejTeraz mamy separację x=0

12 Jeśli dane nie są linioweNależy dokonać transformacji do przestrzeni o większej liczbie wymiarów, gdzie dane będą liniowo separowalne. W naszym przykładzie dane separowalne przez krzywą eliptyczną w R2 będą separowalne liniowo w R3. Potrzebna jest uniwersalna metoda transformacji do przestrzeni o większej liczbie wymiarów.

13 Mnożniki Lagrange'a (przypomnienie)Mnożniki Lagrange’a – metoda obliczania ekstremum warunkowego funkcji różniczkowalnej wykorzystywana w teorii optymalizacji. Dla przypadku dwuwymiarowego problem optymalizacji polega na maksymalizacji L(x, y) przy spełnieniu warunku G(x, y)= 0. W tym celu wprowadzamy nową zmienną α zwaną mnożnikiem Lagrange’a oraz budujemy funkcję pomocniczą: F(x, y, α) = L(x, y) + αG(x, y) . Wszystkie punkty, które mogą być ekstremami warunkowymi są rozwiązaniami układu równań: Problem n zmiennych z k więzami jest redukowany do problemu n+k zmiennych bez więzów.

14 Trochę matematyki Wprowadzamy Lagrangian i mnożniki Lagrange'a:Lagrangian musi być minimalizowany ze względu na w i b oraz maksymalizowany ze względu na αi. w punkcie ekstremum: podstawiamy do L i mamy maksymalizację funkcji W(α) w przestrzeni αi 𝐿 𝑤  ,𝑏,   = 1 2 ∣𝑤∣ 2 − 𝑖  𝑖  𝑦 𝑖 𝑤  , 𝑥  𝑏 −1  𝑖 ≥0 𝑦 𝑖 𝑤  , 𝑥  𝑏 −1≥0𝑛𝑎𝑠𝑧𝑒𝑤𝑖ę𝑧𝑦 𝑦 𝑖 𝑤  , 𝑥  𝑏 −10  𝑖 =0𝑏𝑒𝑧𝑧𝑛𝑎𝑐𝑧𝑒𝑛𝑖𝑎 𝑦 𝑖 𝑤  , 𝑥  𝑏 −1=0𝑠𝑢𝑝𝑝𝑜𝑟𝑡𝑣𝑒𝑐𝑡𝑜𝑟𝑠 ∂𝐿 ∂𝑏 =0, ∂𝐿 ∂ 𝑤  =0  𝑖  𝑖 𝑦 𝑖 =0 𝑤  = 𝑖  𝑖 𝑦 𝑖 𝑥 𝑖  𝑊   = 𝑖  𝑖 − 1 2 𝑖 𝑗  𝑖  𝑗 𝑦 𝑖 𝑦 𝑗 𝑥 𝑖  , 𝑥 𝑗   𝑖 ≥0, 𝑖 𝑦 𝑖  𝑖 =0 𝑓 𝑥  =𝑠𝑔𝑛 𝑤  , 𝑥  𝑏=𝑠𝑔𝑛  𝑖  𝑖 𝑦 𝑖 𝑥 𝑖  , 𝑥  𝑏 W tej przestrzeni W jest funkcją iloczynów xi*xj f – funkcja dyskryminująca

15 Trik – zastosowanie jądra (kernel)Funkja Ф przeprowadza przestrzeń wektorów wejściowych do nowej przestrzeni w której dane są separowalne przez hiperpłaszczyznę: Wtedy I możemy używać tych samych równań. Nie musimy znać funkcji Ф, wystarczy znać jądro (kernel) i można pracować w nowej przestrzeni. 𝑥:𝑖𝑛𝑝𝑢𝑡 ℜ 𝑛  ℜ 𝑁 𝑁≥𝑛 𝑥 𝑖 , 𝑥 𝑗   𝑥 𝑖 , 𝑥 𝑗  =𝐾 𝑥 𝑖 , 𝑥 𝑗  𝑊   = 𝑖  𝑖 − 1 2 𝑖 𝑗  𝑖  𝑗 𝑦 𝑖 𝑦 𝑗 𝐾 𝑥 𝑖  , 𝑥 𝑗    𝑖 ≥0, 𝑖 𝑦 𝑖  𝑖 =0 𝑓 𝑥  =𝑠𝑔𝑛  𝑖  𝑖 𝑦 𝑖 𝐾 𝑥 𝑖  , 𝑥  𝑏

16 Typowo stosowane jądraJądro musi spełniać warunek: 𝐾 𝑥 𝑖 , 𝑥 𝑗 =𝐾 𝑥 𝑗 , 𝑥 𝑖 

17 Lagrangian Lagrangian w przypadku danych nieseparowalnych:

18 Przykład: SVM z jądrem wielomianowym 2-go stopniaNieliniowe jądro (I) Przykład: SVM z jądrem wielomianowym 2-go stopnia

19 Nieliniowe jądro (II) Jądro: funkcja Gaussa

20 Applet pokazujący działanie SVM

21 Regresja – “ε insensitive loss”L(f,y)    Mamy dane wejściowe: X = {(x1,d1), …., (xN,dN)} Chcemy znaleźć funkcję f(x) która ma odchylenie od wartości d nie większe niż  oraz będącą jak najbardziej “gładką”.

22 Regresja Zadanie: przeprowadzić uogólnienie algorytmu klasyfikacji tak, aby uzyskać regresję. Zachować wszystkie właściwośći SVM Definiujemy funkcję: Minimalizacja: I powtarzamy procedurę przejścia do wyższych wymiarów, stosujemy funkcję jądra itd...

23 SVM w pakiecieTMVA Algorytm SVM został zaimplementowany do pakietu TMVA – Andrzej Zemła, praca magisterska. Dostępne funkcje jądra: Liniowa – zapewnia tylko separację liniową RBF (funkcja Gaussa) – dowolny kształt powierzchni separującej Wielomianowa Rozwiązanie problemu kwadratowego - SMO (Sequential Minimal Optimization - J. Platt, Microsoft) z modyfikacjami Keerthi'ego: rozbicie problemu minimalizacji na wiele małych kroków znalezienie optymalnej pary wektorów, redukcja do problemu dwóch zmiennych i rozwiązanie analityczne iteracyjne powtarzanie procedury aż do znalezienia minimum.

24 Porównanie SMO z innymi algorytmamiZ prezentacji J. Platt

25 Przykład (pakiet TMVA): Identyfikacja leptonów τ w eksperymencie ATLASEksperyment ATLAS – jeden z eksperymentów (CMS, ALICE, LHCb) budowanych obecnie na akceleratorze LHC w laboratorium CERN (start 2008). Dane do analizy: hadronowe rozpady τ zrekonstruowane za pomocą algorytmu tau1p3p (z danych Monte-Carlo) 1-prong (1 ślad hadronowy) 2-prong (2 ślady hadronowe) 3-prong (3 ślady hadronowe) Identyfikacja – zrekonstruowane zmienne: rozpady 1p – 9 zmiennych rozpady 2p i 3p – 11 zmiennych Dane 3-prong Żadna zmienna samodzielnie nie pozwala na dobre rozróżnienie sygnału od tła.

26 Optymalizacja punktu pracy dane 3-prongNauka: trening na części danych, sprawdzenie na pozostałych danych (kontrola przeuczenia). SVM z gaussowską funkcja jądrową – optymalizacja σ funkcji gaussa oraz parametru C. Optymalizacja – wielokrotny trening, wybór „najlepszej” pary {σ,C} (największa całka z krzywej ROC). Zależność odrzucania tła oraz czasu treningu od liczby wektorów treningowych. Dla małych zbiorów treningowych prawie optymalna klasyfikacja (skraca czas treningu, często nie mamy dużych zbiorów danych treningowych).

27 Separacja sygnału i tła dane 3-prongPorównanie SVM z wielowarstwową siecią neuronową Sieć MLP z pakietu TMVA 2 ukryte warstwy mające po 20 nodów Wyniki dla funkcji jądrowych: liniowej, gausa i wielomianowej 9 stopnia. Trening na zbiorze zawierającym po przypadków sygnału i tła. Testowanie: ~62000 p. sygnału ~ p. tła Krzywa ROC Sieć MLP oraz SVM z funkcją jądrową gausa dają zbliżone rezultaty

28 SVM <-> multilayer perceptron (sieć neuronowa) Fundamentalne różniceMLP – stopień skomplikowania kontrolowany poprzez liczbę ukrytych nodów SVM – stopień skomplikowania kontrolowany niezależnie od liczby wymiarów SVM – mapowanie powoduje, że płaszczyzna separująca jest konstruowana w przestrzeni wielo (często nieskończenie) wymiarowej. Problem z wielka liczbą wymiarów jest rozwiązywany poprzez użycie funkcji jądra (kernel). Jianfeng Feng, Sussex University

29 Mocne strony SVM Stopień skomplikowania/pojemność jest niezależny od liczby wymiarów. Dobra podbudowa statystyczna. Znajdowanie minimum. Minimalizujemy funkcję kwadratową co gwarantuje zawsze znalezienie minimum. Algorytm jest wydajny i SVM generuje prawie optymalny klasyfikator. Nie jest tez czuły na przetrenowanie. Dobre uogólnianie dzięki wielowymiarowej “feature space”. Najważniejsze: poprzez użycie odpowiedniej funkcji jądra SVM automatycznie dobiera wszystkie parametry sieci (liczbę ukrytych nodów, wagi). Jianfeng Feng, Sussex University

30 Słabe strony SVM Powolny trening – minimalizacja funkcji, szczególnie dokuczliwy przy dużej ilości danych użytych do treningu. Rozwiązania też są skomplikowane (normalnie >60% wektorów użytych do nauki staje się wektorami wspierającymi), szczególnie dla dużych ilości danych. Przykład (Haykin): poprawa o 1.5% ponad wynik osiągnięty przez MLP. Ale MLP używał 2 ukrytych nodów, SVM 285. Trudno dodać własną wiedzę (prior knowledge) Jianfeng Feng, Sussex University

31 Zadanie dla ambitnych Open Higgs challenge!!!!!!!!!!!!!!https://www.kaggle.com/c/higgs-boson Open Higgs challenge!!!!!!!!!!!!!!

32 Machine Learning and HEP 90’ies - Neural Nets used by LEP experiments  BDT (Adaboost) invented in 97  Machine Learning used extensively at D0/CDF (mostly BDT, also Neural Nets) in the 00’ies  Last years – mostly BDT built in TMVA ROOT package (popular among physicists). Neural Nets and other techniques treated as obsolete.  Not much work within LHC experiments on studying possible better MVA techniques.  Enormous development of Machine Learning in the outside world in the last 10 years (“Big Data”, “Data Science”, even “Artificial Intelligence” is back).  We have to catch up and learn from computer scientists: Make an open Higgs challenge!  Task: identify H->tau tau signal out of background in the simulated data. 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 5

33 How did it work ? ● People register to Kaggle web site hosted https://www.kaggle.com/c/higgs- boson . (additional info on https://higgsml.lal.in2p3.fr). ● …download training dataset (with label) with 250k events ● …train their own algorithm to optimize the significance (à la s/sqrt(b)) ● …download test dataset (without labels) with 550k events ● …upload their own classification ● The site automatically calculates significance. Public (100k events) and private (450k events) leader boards update instantly. (Only the public is visible) ● 1785 teams (1942 people) have participated ● most popular challenge on the Kaggle platform (until a few weeks ago) ● 35772 solutions uploaded Funded by: Paris Saclay Center for Data Science, Google, INRIA 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 8

34 Final leaderboard 7000$ 4000$ 2000$ Best physicist 2015 WilgaHEP meets ML award XGBoost authors Free trip to CERN David Rousseau HiggsML visits CERN, 19th May 2015 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 9

35 The winners ? ● See http://atlas.ch/news/2014/machine-learning-wins-the-higgs-challenge.html ● 1 : Gabor Melis (Hungary) software developer and consultant : wins 7000$. ● 2 : Tim Salimans (Neitherland) data science consultant: wins 4000$ ● 3 : Pierre Courtiol (nhlx5haze) (France) ? : wins 2000$ ● HEP meets ML award: (team crowwork), Tianqi ? Chen (U of Washington PhD student in Data Science) and Tong He (graduate student Data Science SFU). Provided XGBoost public software used by many participants. https://github.com/dmlc/xgboost 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 10

36 Rank distribution after bootstrapDistribution of rank of participant of rank i after 1000 bootstraps of the test sample. ! Gabor clearly better rank 1 rank 2 rank 3 rank 4 rank 5 rank 6 rank 7 rank 8 rank 9 David Rousseau HiggsML visits CERN, 19th May 2015 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 11

37 What did we learn from ML experts? Very successful satellite workshop at NIPS (on of the two major Machine Learning conferences) in Dec Montreal: https://indico.lal.in2p3.fr/event/2632/ 20% gain w.r.t. to untuned Boosted Decision Tree from the ● TMVA package ● Deep Neural Nets rule (but marginally better than BDT) Ensemble methods (random forest, boosting) rule ● careful cross-validation - very (human) time consuming ● ...but this could be automatized! ● Complex software suites using routinely multithreading, etc… (e.g. ● XGBoost) 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 12

38 Deep neural network Challenge winning Gabor's deep neural network● Hierarchical feature extraction – first build abstract objects, than find dependencies between them. ● Deep neural network (DNN)- an artificial neural network with multiple hidden layers of units between the input and output layers. ● Extra layers - composition of features from lower layers, potential of modeling complex data with fewer units than a similarly performing shallow network. Challenge winning Gabor's deep neural network (from Gabor's presentation) Remark: Few years ago some experts claimed neural networks are an obsolete tool :) 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 13

39 Automatic optimization of hyperparameters● Manual optimization of NN (or any other method) is time consuming. ● Fortunately the Bayesian optimization methods can rival and surpass human domain experts in finding good hyperparameter settings. ● SMAC, SPEARMINT, TPE (and others) are doing that with great success: 2015 Wilga M. Wolter, Machine learning - how to get more out of HEP data 14

40 Analiza podczas praktyk studenckichPróbowaliśmy powtórzyć HiggsChallenge podczas praktyk studenckich. Udało się za pomocą TMVA (konwersja danych do formatu root) oraz pakietu XGBoost Optymalizacja parametrów XGBoost za pomocą programu hyperopt

41

42 Zadanie drugie ATLAS Z→tau tau selectionDane: mc12/Ztautau.root sygnał Powheg_ttbar.root - tło Wenu.root tło Wmunu.root - tło Wtaunu.root - tło Zee.root tło Zmumu.root tło Zmienne: preselekcja: if(!( evtsel_is_dilepVeto > 0 && evtsel_is_tau > 0 && fabs(evtsel_tau_eta) < 2.47 && evtsel_is_conf_lep_veto == 1 && evtsel_tau_numTrack == 1 && evtsel_lep_pt > 26 && fabs(evtsel_lep_eta) < 2.4 && evtsel_transverseMass < 70)) continue; if (!( evtsel_is_oppositeSign>0 && evtsel_is_mu>0 && evtsel_is_isoLep>0 )) continue;

43 ATLAS Z→tau tau selectionZmienne użyte do treningu: evtsel_tau_et evtsel_dPhiSum evtsel_tau_pi0_n evtsel_transverseMass sum_cos_dphi Spectator vis_mass Program: TMVAClassificationMW.C i TMVAClassificationMW.h Wykonuje podstawowy trening.

44 ATLAS Z→tau tau selectionZainstalować pakiet root i TMVA Ściągnąć dane i przykładowy program: Uruchomić przykładowy program: root -l .L TMVAClassificationMW.C++ TMVAClassificationMW t t.Loop() Zmodyfikować go: Spróbować zoptymalizować parametry wybranej metody Spróbować usunąć jakieś zmienne a może dodać? Spróbować użyć indywidualnych zmiennych wchodzących w skład np. sum_cos_dphi Użyć wszystkich rodzajów tła – użyć wag WeightLumi Zaaplikować wyuczony klasyfikator do danych (data12/Muons.PhysCont.grp14.root), można się wzorować na przykładzie TMVAClassificationApplication dostępnym na stronie TMVA.

45 ATLAS Z→tau tau selectionWykonać tego typu rysunek np. dla masy widzialnej

46 ATLAS Z→tau tau selectionCięcia zastosowane w analizie polaryzacji tau pochodzących z rozpadu Z → taut tau Czy używając uczenia maszynowego udało nam się poprawić wynik?