Curs 1. Introducere - Tehnici de învățare automată (PDF)

Curs 1. Introducere Tehnici de învățare automată Cristian Flutur Departamentul de Automatică şi Ingineria Sistemelor Facultatea de Automatică şi Calculatoare Universitatea Politehnica Bucureşti 16 octombrie 2024 Cuprins 1 Generalități 2 Tipuri de învăţare 3 Algoritm de învăţare 4 Învăţare supervizată Cuprins 1 Generalități Tematică şi definiţii Ce este învăţarea? Utilitate 2 Tipuri de învăţare 3 Algoritm de învăţare 4 Învăţare supervizată Generalități Tematică şi definiţii Generalități Tematică Cursul adresează tematica învăţării automate, cunoscută sub numele de Machine Learning (ML). Programăm calculatorul astfel încât să poată ”învăţa” din inputul disponibil. Învăţarea presupune procesul de conversie a experienţei în expertiză sau cunoştinţe. inputul unui algoritm de învăţare - datele de antrenare (experienţa) outputul - expertiza, care ia forma unui alt program care poate realiza o anumită sarcină Definiţii Învăţarea automată este domeniul de studii care dă calculatoarelor abilitatea de a învăţa fără a fi programate explicit (Samuel, 1959). Problemă de învăţare ”bine-pusă”: spunem despre un program că învăţă din experienţa E în raport cu o sarcină T şi o măsură a performanţei P, dacă performanţa pe sarcina T, măsurată de P, se îmbunătăţeşte cu experienţa E (Mitchell, 1998). C. Flutur Curs 1. Introducere 16 octombrie 2024 1 / 14 Generalități Tematică şi definiţii Exemplu Program ce monitorizează care mail-uri sunt sau nu marcate ca spam şi învaţă cum să filtreze mai bine mail-urile spam. Care dintre următoarele reprezintă sarcina T ? 1 Clasificarea mail-urilor ca spam sau non-spam. 2 Monitorizarea etichetării mail-urilor ca spam sau non-spam. 3 Numărul (sau procentul) de mail-urilor corect clasificate ca spam/non-spam. 4 Nicio variantă din cele de mai sus. Aceasta nu este o problemă de învăţare automată. Care variantă reprezintă experienţa E ? Dar măsura de performanţă P ? C. Flutur Curs 1. Introducere 16 octombrie 2024 2 / 14 Generalități Ce este învăţarea? Ce este învăţarea? Ce presupune a învăţa? Bait shyness Şobolanii învaţă să evite mâncarea otrăvită. când dau de hrană cu aspect şi miros nou, consumă cantităţi mici consumul ulterior depinde de gust şi de efectele fiziologice dacă hrana produce stări de rău, aceasta este adesea asociată cu boală, iar consumul ulterior va fi evitat Animalul foloseşte experienţa anterioară cu un anume tip de hrană pentru achiziţia de expertiză în detectarea hranei sigure. Dacă experienţa anterioară a fost etichetată negativ, animalul prezice că efectul negativ va apărea şi în viitor. Cum se poate formula o soluţie la problema de filtrare a mail-urilor spam, ţinând cont de exemplul de mai sus? Cât de ”bun” ar fi un astfel de algoritm? Raţionament inductiv Lipseşte abilitatea de a eticheta mail-urile pe care algoritmul nu le-a mai întâlnit. Un algoritm de învăţare de succes ar trebui să fie capabil să progreseze de la exemple individuale la generalizare mai largă. Altfel spus, algoritmul trebuie să fie capabil de raţionament inductiv sau inferenţă inductivă. C. Flutur Curs 1. Introducere 16 octombrie 2024 3 / 14 Generalități Ce este învăţarea? Ce este învăţarea? Ce presupune a învăţa? Raţionamentul inductiv poate conduce la concluzii false. Superstiţia porumbeilor Psihologul american B.F. Skinner realizează următorul experiment: porumbeii dintr-o cuşcă primesc hrană la intervale fixe de timp, cu ajutorul unui mecanism automat, fără intervenţie umană hrana este livrată fără vreo legătură cu comportamentul păsărilor momentul apariţiei hranei surprinde păsările angajate în diverse activităţi (întoarcerea capului, dat din aripi etc.) Experimentatorii observă că apariţia hranei întăreşte acţiunea specifică a fiecărei păsări fiecare pasăre tinde să petreacă mai mult timp făcând acţiunea respectivă creşte astfel şansa ca următoarea livrare de hrană să surprindă fiecare pasăre angajată în activitatea respectivă Rezultă un lanţ de evenimente care întăreşte asocierea dintre livrarea hranei şi acţiunea întâmplătoare pe care fiecare pasăre o realiza la momentul primei livrări. C. Flutur Curs 1. Introducere 16 octombrie 2024 4 / 14 Generalități Ce este învăţarea? Ce este învăţarea? Ce presupune a învăţa? Mecanism de învăţare Ce diferenţiază mecanismele de învăţare care conduc la superstiţie de învăţarea utilă? Oamenii se pot baza pe ”bun simţ” pentru a filtra concluzii întâmplătoare şi lipsite de sens. Algoritmul de învăţare trebuie să primească principii clare, bine-definite, care să-l protejeze de concluzii inutile şi lipsite de sens. Bait shyness vs. pigeon superstition consumul de hrană urmat de un stimul neplăcut (şoc electric sau sunet puternic) nu produce nicio condiţionare, iar şobolanii continuă să consume hrana aceştia par să ştie a priori faptul că, deşi corelaţia temporală dintre hrană şi starea de rău poate fi cauzală, este puţin probabil să existe relaţie cauzală între consumul de hrană şi şocuri electrice Caracteristica distinctivă o reprezintă cunoştinţele anterioare, care distorsionează mecanismul de învăţare, fenomen numit şi distorsiune inductivă (inductive bias). C. Flutur Curs 1. Introducere 16 octombrie 2024 5 / 14 Generalități Ce este învăţarea? Overfitting vs. underfitting Overfitting Overfitting (supraînvăţarea) apare atunci când un model învață prea bine detaliile și particularitățile setului de date de antrenament, inclusiv zgomotul și anomaliile. În loc să învețe modele generale care să funcționeze și pe date noi, modelul devine prea complex și ajunge să memoreze caracteristici specifice din datelor de antrenament. Un model cu supraînvăţare va avea o performanță excelentă pe datele de antrenament, dar va eșua să generalizeze bine pe seturi de date noi, necunoscute. Underfitting Underfitting (subînvăţarea) apare atunci când un model este prea simplu pentru a surprinde tiparele și relațiile din date. Modelul nu reușește să învețe suficient de bine din datele de antrenament și, ca urmare, performanța sa este slabă atât pe datele de antrenament, cât și pe cele de testare. Un model cu subînvățare va avea o performanță slabă pe toate seturile de date, deoarece nu poate surprinde structura de bază din date. Acest fenomen poate apărea când modelul este fie prea simplu, fie antrenat necorespunzător. C. Flutur Curs 1. Introducere 16 octombrie 2024 6 / 14 Generalități Utilitate Utilitate Când avem nevoie de învăţare automată, în loc să programăm direct sarcinile de îndeplinit? Aspectele care cer programe capabile de învaţare şi îmbunătăţire în baza experienţei lor sunt: complexitatea problemei. Sarcini realizate de oameni/animale. Sarcini realizate ca rutină, dar asupra cărora nu avem o introspecție suficient de elaborată, prin urmare nu putem extrage un program bine-definit: condus, recunoaştere de voce, înţelegerea imaginilor. Sarcini ce depăşsesc capacitatea umană. Analiza unui volum foarte mare şi complex de date: date astronimice, transformarea arhivelor medicale în cunoştinţe medicale, prognoză meteo, analiza genomului, motoare de căutare. nevoia de adaptabilitate. Rigiditatea programelor este o limitare: odată scrise şi instalate, rămân neschimbate. Aplicaţii: recunoaşterea scrisului de mână, detectarea mail-urilor spam, recunoaştere vocală. C. Flutur Curs 1. Introducere 16 octombrie 2024 7 / 14 Cuprins 1 Generalități 2 Tipuri de învăţare 3 Algoritm de învăţare 4 Învăţare supervizată Tipuri de învăţare Tipuri de învâţare Taxonomia paradigmelor de învăţare. Învăţare activă vs. pasivă Un mecanism activ de învăţare interacţionează cu mediul în timpul antrenării: face interogări, experimente. Un mecanism pasiv de învăţare observă informaţia oferită de mediu, fără a o influenţa sau direcţiona (filtru de spam). Ajutorul de la instructor Procesul de învăţare în cazul unui copil mic sau al unui student la şcoală implică adesea un instructor care ajută, care furnizează informaţiile cele mai utile pentru scopul învăţării. Când un om de ştiinţă studiază fenomele naturale, ”instructorul” este pasiv. Un astfel de scenariu de învăţare are datele de antrenament (experienţa) generate de un proces aleator. Scenariile de acest tip constituie structura de baza pentru învăţare statistică. Cazul instructorului advers. C. Flutur Curs 1. Introducere 16 octombrie 2024 8 / 14 Tipuri de învăţare Tipuri de învăţare Lot de antrenament vs. învăţare online Entitatea care învaţă trebuie să folosească expertiza pe parcursul antrenamentului: un broker ia zilnic decizii, bazate pe experienţa de până în momentul respectiv. Entitatea care învaţă foloseşte expertiza acumulată abia după ce a procesat un volum mare de date: data mining. Învăţare supervizată vs. nesupervizată supervizată: scenariu în care experienţa, exemplele de antrenare conţin informaţie semnificativă, care lipseşte din exemplele de test. scopul este ca expertiza acumulată să ducă la predicţia informaţiilor lipsă, în datele de testare. nesupervizată: nu există distincţie între datele de antrenament şi cele de test. algoritmul procesează date intrare cu scopul de a construi un sumar sau o versiune comprimată a acestor date (ex.: clustering - gruparea obiectelor în submulţimi de obiecte similare). C. Flutur Curs 1. Introducere 16 octombrie 2024 9 / 14 Cuprins 1 Generalități 2 Tipuri de învăţare 3 Algoritm de învăţare 4 Învăţare supervizată Algoritm de învăţare Componentele unui algoritm de învăţare Orice algoritm de învăţare automată are 3 componente principale. Modelul: o reprezentare matematică sau computaţionlă a relaţiei dintre datele de intrare şi ieşirea dorită. Acesta defineşte felul încare algoritmul face predicţii sau ia decizii. Alegerea modelului depinde de sarcina de învăţare specifică şi poate varia de la modele liniare simple la reţele neuronale complexe sau arbori de decizie. Evaluarea performanţei: are loc printr-o funcţie obiectiv (sau funcţie cost), care cuantifică eroarea de nepotrivire dintre predicţiile modelului şi valorile reale. Returnează o valoare scalară care ne spune cât de bine funcţionează modelul pe datele de antrenare. Scopul este minimizarea acestei funcţii cost prin ajustarea parametrilor modelului, în timpul antrenării. Optimizarea: un algoritm responsabil cu actualizarea parametrilor modelului pentru minimizarea funcţiei cost. Defineşte procesul de învăţare determinând felul în care modelul învaţă din date. Metodele de gradient sunt exemple populare de algoritmi de optimizare. Procesul de antrenare Modelul face predicţii bazate pe datele de intrare; funcţia cost calculează eroarea dintre predicţii şi valorile reale; algoritmul de optimizare ajustează parametrii modelului pentru a minimiza eroarea, îmbunătăţind iterativ performanţa modelului. C. Flutur Curs 1. Introducere 16 octombrie 2024 10 / 14 Cuprins 1 Generalități 2 Tipuri de învăţare 3 Algoritm de învăţare 4 Învăţare supervizată Regresie liniară Învăţare supervizată Regresie liniară Noţiuni generale Algoritmul de învăţare are acces la următoarele Mulţimea domeniu: o mulţime arbitrară, X , formată din obiectele pe care le dorim etichetate. Punctele din acest domeniu sunt reprezentate ca vectori de caracteristici. Aceste puncte vor mai fi numite instanţe, iar X se mai numeşte spaţiu al instanţelor. Mulţimea de etichete, Y: este mulţimea în care funcţia care face predicţia ia valori. Aceste valori pot fi categoriale (în cazul clasificării) sau numerice (în cazul regresiei). Datele de antrenare: constituie o secveţă finită de perechi din X × Y, de forma S = ((x(1) , y(1) ),... , (x(m) , y(m) )), formată din instanţe etichetate. Un element din mulţimea de antrenament se numeşte exemplu. Algoritmul de învăţare are ieşirea: Regulă de predicţie, h : X → Y. Această funcţie se mai numeşte predictor, ipoteză sau clasificator şi are rolul de etichetare a noi puncte din domeniu. C. Flutur Curs 1. Introducere 16 octombrie 2024 11 / 14 Învăţare supervizată Regresie liniară Regresie liniară Reprezentarea ipotezei Pentru un set de antrenare S algoritmul de învăţare trebuie să obţină o ipoteză h de forma h(x) = θ0 + θ1 x1. Tipic, nu se foloseşte o singură caracteristică, iar x ∈ X este adesea multidimensional. ∑ n hθ (x) = θj xj = θT x, θ, x ∈ Rn+1 , j=0 unde n este numărul de caracteristici în raport cu care se realizează predicţia (considerăm T x0 = 1). Elementele vectorului θT = θ0... θn se numesc parametri. C. Flutur Curs 1. Introducere 16 octombrie 2024 12 / 14 Învăţare supervizată Regresie liniară Regresie logistică Problemele de clasificare în învăţarea automată constituie un tip de sarcină de învăţare supervizată în care scopul este plasarea în categorii sau etichetarea datelor de intrare, conform cu mai multe clase sau categorii predefinite. Sarcina algoritmului este să atribuie o etichetă unei instanţe, bazat pe caracteristicile acesteia. Problema de clasificare binară Evităm utilizarea regresiei liniare. Valoarea lui y(i) poate fi 0 sau 1: hθ (x) ∈ [0, 1] 1 1 hθ (x) = g(θT x) = g(z) = , 1 + e−θT x 1 + e−z unde g(z) se numeşte funcţie sigmoid sau funcţie logistică. Funcţia sigmoid are proprietatea: g′ (z) = g(z)(1 − g(z)). C. Flutur Curs 1. Introducere 16 octombrie 2024 13 / 14 Învăţare supervizată Regresie liniară Indici de performanţă Senzitivitatea Senzitivitatea unei predicţii măsoara abilitatea modelului de a prezice corect instanţele pozitive: pozitive adevărate senzitivitate =. pozitive adevărate + negative false O senzitivitate mai mare indică un model care surprinde mai uşor cazurile pozitive, dar poate rezulta în mai multe cazuri fals pozitive. Specificitatea Specificitatea unei predicţii măsoară abilitatea modelului de a prezice corect instanţele negative: negative adevărate specificitate =. negative adevărate + pozitive false O specificitate mai mare indică un model mai bun la evitarea alarmelor false pentru instanţele negative. C. Flutur Curs 1. Introducere 16 octombrie 2024 14 / 14 Curs 2. Învăţare supervizată. Regresie Tehnici de învățare automată Cristian Flutur Departamentul de Automatică şi Ingineria Sistemelor Facultatea de Automatică şi Calculatoare Universitatea Politehnica Bucureşti 16 octombrie 2024 Cuprins 1 Noţiuni generale şi notaţii 2 Regresie liniară 3 Regresie local ponderată 4 Interpretare probabilistică Cuprins 1 Noţiuni generale şi notaţii 2 Regresie liniară 3 Regresie local ponderată 4 Interpretare probabilistică Noţiuni generale şi notaţii Noţiuni generale Algoritmul de învăţare are acces la următoarele Mulţimea domeniu: o mulţime arbitrară, X , formată din obiectele pe care le dorim etichetate. Punctele din acest domeniu sunt reprezentate ca vectori de caracteristici. Aceste puncte vor mai fi numite instanţe, iar X se mai numeşte spaţiu al instanţelor. Mulţimea de etichete, Y: este mulţimea în care funcţia care face predicţia ia valori. Aceste valori pot fi categoriale (în cazul clasificării) sau numerice (în cazul regresiei). Datele de antrenare: constituie o secveţă finită de perechi din X × Y, de forma S = ((x(1) , y(1) ),... , (x(m) , y(m) )), formată din instanţe etichetate. Un element din mulţimea de antrenament se numeşte exemplu. Algoritmul de învăţare are ieşirea: Regulă de predicţie, h : X → Y. Această funcţie se mai numeşte predictor, ipoteză sau clasificator şi are rolul de etichetare a noi puncte din domeniu. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 1 / 18 Noţiuni generale şi notaţii Noţiuni generale Presupunem că instanţele apar conform cu o distribuţie de probabilitate D, peste X. Presupunem că există o funcţie de etichetare ”corectă”, f : X → Y, iar y(i) = f(x(i) ), ∀i. Algoritmul de învăţare nu ”ştie” nimic nici despre distribuţia de probabilitate D nici despre clasificatorul corect f. Fiecare pereche din setul de antrenare S este generată eşantionând întâi un punct x(i) în acord cu D şi etichetându-l apoi prin f. Măsura performanţei Eroarea clasificatorului h este probabilitatea ca predicţia făcută de acesta pe un punct aleator extras din X conform cu distribuţia D să nu fie corectă. Altfel spus, eroarea lui h este probabilitatea de a extrage o instanţă aleatoare x, în acord cu D, astfel încât h(x) ̸= f(x). def def JD,f (h) = P [h(x) ̸= f(x)] = D({x : h(x) ̸= f(x)}). x∼D C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 2 / 18 Cuprins 1 Noţiuni generale şi notaţii 2 Regresie liniară Alegerea parametrilor Gradient descendent Gradient descendent stochastic Forma normală a regresiei liniare 3 Regresie local ponderată 4 Interpretare probabilistică Regresie liniară Regresie liniară Reprezentarea ipotezei Pentru un set de antrenare S algoritmul de învăţare trebuie să obţină o ipoteză h de forma h(x) = θ0 + θ1 x1. Tipic, nu se foloseşte o singură caracteristică, iar x ∈ X este adesea multidimensional. X n hθ (x) = θj xj = θT x, θ, x ∈ Rn+1 , j=0 unde n este numărul de caracteristici în raport cu care se realizează predicţia (considerăm T x0 = 1). Elementele vectorului θT = θ0... θn se numesc parametri. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 3 / 18 Regresie liniară Alegerea parametrilor Alegerea parametrilor Alegem θ astfel încât hθ (x) să fie cât mai apropiat de y pentru exemplele din setul de antrenare. Altfel spus, vrem soluţia problemei de optim 1X m 2 minimizează J(θ) = hθ (x(i) ) − y(i) θ 2 i=1 Optimizare Rezolvăm problema de minimizare folosind metoda de gradient descendent. Iniţializează vectorul θ Actualizează θ pentru a reduce valoarea lui J(θ) θ := θ − α∇θ J(θ) ∂ θj := θj − α J(θ), j = 1 : n. ∂θj α se numeşte rată de învăţare. Gradientul descendent −∇θ J(θ) dă direcţia celei mai abrupte coborâri. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 4 / 18 Regresie liniară Gradient descendent Gradient descendent Folosim notaţia T ∂J(θ) ∂J(θ) ∂J(θ) [∇θ J(θ)]T =... ∂θ0 ∂θ1 ∂θn C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 5 / 18 Regresie liniară Gradient descendent Optimizare - Gradient descendent Derivata parţială a funcţiei cost în raport cu fiecare parametru ∂ 1X m ∂ J(θ) = (hθ (x(i) ) − y(i) )2 ∂θj ∂θj 2 i=1 X m ∂ = (hθ (x(i) ) − y(i) ) (hθ (x(i) ) − y(i) ). i=1 ∂θj Ipoteza hθ are forma hθ (x(i) ) = θT x(i) = θ0 + θ1 x1 +... + θn x(i) (i) n. Derivata parţială a funcţiei cost devine ∂ X m (i) J(θ) = hθ (x(i) ) − y(i) xj. ∂θj i=1 C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 6 / 18 Regresie liniară Gradient descendent Optimizare - Gradient descendent Actualizarea parametrilor Pasul de actualizare al parametrilor θj devine m X (i) θj := θj − α hθ (x(i) ) − y(i) xj , i=1 pas ce trebuie repetat până se atinge convergenţa. Convergenţa Funcţia cost J(θ), aşa cum este formulată pentru regresia liniara, este convexă şi are un singur punct de minim. Prin urmare, algoritmul de optimizare converge în toate situaţiile. Rata de învăţare Metaparametrul α ∈ (0, 1) se alege experimental, după mai multe încercări. O rată de învăţare prea mare va accelera căutarea minimului, dar pot apărea depăşiri ale optimului (observăm că funcţia cost creşte, în loc să scadă). C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 7 / 18 Regresie liniară Gradient descendent stochastic Gradient descendent pe eşantion vs. gradient descendent stochastic Metoda de optimizare cu gradient descendent parcurge întreg setul de antrenament la fiecare pas, ceea ce poate deveni costisitor pentru dimensiuni mari. Numim această variantă a metodei gradient descendent pe eşantion. Gradient descendent stochastic Alternativ, se poate folosi următoarea variantă Repetă până la ”convergenţă” Pentru i = 1 : m Actualizează fiecare θj după formula ( ) (i) (i) (i) θj := θj − α hθ (x ) − y xj Algoritmul parcurge setul de antrenare, iar de fiecare dată când întâlneşte un exemplu, parametrii θj se actualizează doar în raport cu respectivul exemplu de antrenare. Algoritmul poate să nu conveargă la minim, iar parametrii θ vor oscila în jurul minimului lui J(θ). Gradientul descendent stochastic duce parametrii θ ”aproape” de minim mult mai rapid decât gradientul descendent pe eşantion. 1 Pentru α = m obţinem o rapiditate egală cu cea a gradientului descendent pe eşantion. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 8 / 18 Regresie liniară Forma normală a regresiei liniare Forma normală a regresiei liniare Cazul regresiei liniare permite o formulă închisă pentru parametrii optimi θ∗. Metoda de căutare nu mai este una iterativă. Reluăm funcţia cost 1X m 2 J(θ) = hθ (x(i) ) − y(i) 2 i=1 Notaţii şi proprietăţi Definim o matrice X ∈ Rm×(n+1) , iar liniile acesteia reprezintă exemplele de antrenare:     (x(1) )T (x(1) )T θ       hθ (x(1) )      (2) T   (2) T  ..  X =  (x )  , deci Xθ =  (x ) θ  = .  ..  ..  .  .  hθ (x )(m) (x(m) )T (x(m) )T θ C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 9 / 18 Regresie liniară Forma normală a regresiei liniare Notaţii şi proprietăţi Pentru o matrice A ∈ Rm×n şi o funcţie f : Rm×n → R definim ∇A f(A)   ∂f(A) ∂f(A) ∂f(A)...  ∂a11 ∂a12 ∂a1n       ∂f(A) ∂f(A) ∂f(A)    ∇A f(A) =   ∂a21 ∂a22...  ∂a2n  ∈ R m×n ........  .  ...   ∂f(A) ∂f(A) ∂f(A) ... ∂am1 ∂am2 ∂amn Pn Pentru A ∈ Rn×n avem tr A = i=1 aii. Pentru f(A) = tr AB avem ∇A f(A) = BT. Pentru un vector x ∈ Rn şi o funcţie f(x) = bT x avem ∇x f(x) = b. Pentru un vector x ∈ Rn şi o funcţie f(x) = xT Ax avem ∇x f(x) = 2Ax. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 10 / 18 Regresie liniară Forma normală a regresiei liniare Forma normală a regresiei liniare Definim un vector cu valorile estimărilor YT = y(1) y(2)... y(m). Rescriem funcţia cost în forma 1X m 2 1 J(θ) = hθ (x(i) ) − y(i) = (Xθ − Y)T (Xθ − Y). 2 i=1 2 Gradientul funcţiei cost 1 ∇θ J(θ) = ∇θ (Xθ − Y)T (Xθ − Y) 2 1 1 = ∇θ (θT XT Xθ − θT XT Y − YT Xθ + YYT ) = (XT Xθ + XT Xθ − XT Y − XT Y) 2 2 Funcţia cost J(θ) este pătratică şi convexă, deci în punctul de minim avem ∇θ J(θ∗ ) = 0 sau XT Xθ∗ = XT Y, deci parametrii optimi sunt −1 θ ∗ = XT X XT Y. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 11 / 18 Cuprins 1 Noţiuni generale şi notaţii 2 Regresie liniară 3 Regresie local ponderată 4 Interpretare probabilistică Regresie local ponderată Regresie local ponderată Putem folosi regresie liniară pentru modele neliniare. h(x) = θ0 + θ1 x + θ2 x2. Alegem x1 := x şi x2 := x2. √ √ 18 h(x) = θ0 + θ1 x + θ2 x. Alegem x1 := x şi x2 := x. 4.5 4.5 4.5 4 4 4 3.5 3.5 3.5 3 3 3 2.5 2.5 2.5 y y y 2 2 2 1.5 1.5 1.5 1 1 1 0.5 0.5 0.5 0 0 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 x x x Instead, if we had added an extra feature x2 , and fit y = ✓0 + ✓1 x + ✓2 x2 , then we obtain a slightly better fit to the data. (See middle figure) Naively, it might seem that the more features we add, the better. However, there is also a danger in adding too many features: P The rightmost figure is the result of fitting a 5-th order polynomial y = 5j=0 ✓j xj. We see that even though the C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 12 / 18 Regresie local ponderată Regresie local ponderată Tehnici de învăţare parametrice vs. neparametrice Tehnicile de învăţare parametrice interpolează un set fix de parametri, în raport cu datele. Odată calculaţi parametri, nu mai folosim nimic din setul de antrenare. La tehnicile neparametrice, cantitatea de parametri/date necesare pentru predicţie creşte (liniar) cu dimensiunea datelor. Regresie liniară Pentru estimarea valorii lui h pe un anumit punct x se interpolează parametrii θ pentru a minimiza J(θ). Regresie local ponderată Pentru estimarea lui h(x) se alege o vecinătate a lui x pe care se realizează interpolarea. Calculăm parametrii θ care minimizează o funcţie cost modificată 1 X (i) (i) 2 m T (i) (x(i) − x)2 J̃(θ) = w y −θ x , w = exp − (i) 2 i=1 2τ 2 C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 13 / 18 Regresie local ponderată Regresie local ponderată Funcţia de ponderare Funcţia cost modificată J̃ are fiecare termen eroare y(i) − θT x(i) ponderat cu funcţia de ponderare (x(i) − x)2 w(i) = exp −. 2τ 2 w(i) are formă de curbă gaussiană, de lăţime τ , şi arată cât de relevante pentru predicţie sunt punctele din vecinătatea lui x x reprezintă punctul pentru care se face predicţia valorile lui w(i) se apropie de 1 când exemplul de antrenare x(i) este aproape de x valorile lui w(i) se apropie de 0 când exemplul de antrenare x(i) este departe de x Algoritmul se pretează unui set de antrenare cu număr de caracteristici relativ mic. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 14 / 18 Cuprins 1 Noţiuni generale şi notaţii 2 Regresie liniară 3 Regresie local ponderată 4 Interpretare probabilistică Densitate de probabilitate Alegerea parametrilor Interpretare probabilistică Interpretare probabilistică Minimizarea funcţiei cost formulată ca problemă de tip ”cele mai mici pătrate” are semnificaţie probabilistică. Asumpţii Presupunem că fiecare valoare prezisă este formată din ”valoarea adevărată” peste care se adaugă o eroare ce cuantifică efectele nemodelate şi/sau zgomot aleator y(i) = θT x(i) + ε(i) Presupunem că eroroarea ε(i) este distribuită normal între 0 şi σ 2 ε(i) ∼ N (0, σ 2 ) Densitatea de probabilitate a variabilei aleatoare ε(i) este  2  1  ε(i)  P(ε(i) ) = √ exp −  2πσ 2σ 2 Presupunem că termenii ε(i) sunt distribuiţi identic şi independent. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 15 / 18 Interpretare probabilistică Interpretare probabilistică Densitatea de probabilitate a variabilei prezise y(i) condiţionată de variabila din setul de antrenare x(i) , parametrizată de θ, este  2  T (i) 1  y(i) − θ x  P(y(i) |x(i) ; θ) = √ exp − , 2πσ 2σ 2 unde σ este abaterea distribuţiei gaussiene, iar θT x(i) este media distribuţiei. Altfel spus, fiind daţi x(i) parametrizaţi de θ, probabilitatea valorii prezise y(i) este y(i) |x(i) ; θ ∼ N (θT x(i) , σ 2 ). Notaţii Reluăm notaţiile de la ecuaţia normală, unde X ∈ Rm×(n+1) este o matrice ale cărei rânduri constituie exemplele (x(i) )T din setul de antrenament, iar Y ∈ Rm este vectorul cu valorile prezise. C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 16 / 18 Interpretare probabilistică Densitate de probabilitate Densitatea maximă de probabilitate Reformularea problemei Fiind date matricea X şi parametrii θ, care este distribuţia valorilor y(i) ? Probabilitatea datelor este dată de P(Y|X; θ), care este o funcţie de Y, pentru θ fixat. Ne interesează să vedem P(Y|X; θ) ca o funcţie de θ. Funcţia de verosimilitate Folosim funcţia de verosimilitate (likelihood) L(θ) = L(θ; X, Y) = P(Y|X; θ), definită ca probabilitatea datelor y(i) condiţionate de exemplele de antrenare x(i) , parametrizate de θ. Datorită presupunerii de distribuţie independentă a ε(i) şi, implicit, a y(i) condiţionaţi de x(i) , putem scrie Ym Ym 1 (y(i) − θT x(i) )2 L(θ) = P(Y|X; θ) = P(y(i) |x(i) ; θ) = √ exp −. i=1 i=1 2πσ 2σ 2 C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 17 / 18 Interpretare probabilistică Alegerea parametrilor Alegerea parametrilor Avem modelul probabilistic ce relaţionează y(i) de x(i). Cum alegem cei mai buni parametrii θ? Principiul verosimilităţii maxime spune că parametrii trebuie aleşi astfel încât datele prezise să fie cât mai probabile. Trebuie, deci, să maximizăm L(θ). Maximizarea funcţiei de verosimilitate Nu vom maximiza L(θ), ci funcţia ℓ(θ) = log(L(θ)), cele două probleme de optim fiind echivalente. Ym X m 1 (y(i) − θT x(i) )2 1 (y(i) − θT x(i) )2 ℓ(θ) = log √ exp − = log √ exp − i=1 2πσ 2σ 2 i=1 2πσ 2σ 2 1 1 X (i) 2 m 1 = m log √ − 2 · y − θT x(i). 2πσ σ 2 i=1 Maximizarea funcţiei ℓ(θ) echivalează cu minimizarea funcţiei 1 X (i) 2 m y − θT x(i) , 2 i=1 i.e., funcţia cost J(θ). C. Flutur Curs 2. Învăţare supervizată. Regresie 16 octombrie 2024 18 / 18 Curs 3. Învăţare supervizată. Regresie logistică Tehnici de învățare automată Cristian Flutur Departamentul de Automatică şi Ingineria Sistemelor Facultatea de Automatică şi Calculatoare Universitatea Politehnica Bucureşti 16 octombrie 2024 Cuprins 1 Regresie logistică 2 Metoda lui Newton 3 Algoritm de învăţare cu perceptron 4 Clasificare multiclasă Cuprins 1 Regresie logistică 2 Metoda lui Newton 3 Algoritm de învăţare cu perceptron 4 Clasificare multiclasă Regresie logistică Regresie logistică Problemele de clasificare în învăţarea automată constituie un tip de sarcină de învăţare supervizată în care scopul este plasarea în categorii sau etichetarea datelor de intrare, conform cu mai multe clase sau categorii predefinite. Sarcina algoritmului este să atribuie o etichetă unei instanţe, bazat pe caracteristicile acesteia. Problema de clasificare binară Evităm utilizarea regresiei liniare. Valoarea lui y(i) poate fi 0 sau 1: hθ (x) ∈ [0, 1] 1 1 hθ (x) = g(θT x) = g(z) = , 1 + e−θT x 1 + e−z unde g(z) se numeşte funcţie sigmoid sau funcţie logistică. Funcţia sigmoid are proprietatea: g′ (z) = g(z)(1 − g(z)). De ce să nu aplicăm regresie liniară la clasificare? C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 1 / 14 Regresie logistică Funcţia sigmoid 1 g(z) = 1 + e−z 1/( 1+exp(-x)) 1 0.8 0.6 0.4 0.2 0 -4 -3 -2 -1 0 1 2 3 4 x C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 2 / 14 Regresie logistică Regresie logistică Asumpţii şi notaţii Vom spune că hθ (x) estimează probabilitatea ca ieşirea y, codiţionată de instanţa x, parametrizată de θ, să fie 1: P(y = 1|x; θ) = hθ (x) P(y = 0|x; θ) = 1 − hθ (x) Din cauză că y ∈ {0, 1} putem scrie P(y|x; θ) = [hθ (x)]y [1 − hθ (x)]1−y Estimarea verosimilităţii maxime Reamintim funcţia de verosimilitate Y m Ym y(i) 1−y(i) L(θ) = P(Y|X; θ) = P y(i) |x(i) ; θ = hθ (x(i) ) 1 − hθ (x(i) ) i=1 i=1 C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 3 / 14 Regresie logistică Estimarea verosimilităţii maxime Estimarea maximului funcţiei L(θ) echivalează cu estimarea maximului funcţiei ℓ(θ) = log L(θ): m h X i ℓ(θ) = y(i) log hθ (x(i) ) + 1 − y(i) log(1 − hθ (x(i) )) i=1 Problema de optim Pentru maximizarea funcţiei ℓ(θ) vom folosi metoda gradientului ascendent, cu regula de actualizare a parametrilor ∂ θ := θ + α∇θ ℓ(θ) θj := θj + α ℓ(θ) ∂θj ∂ℓ(θ) X (i)m (i) = y − hθ (x(i) ) xj ∂θj i=1 Funcţia ℓ(θ) este concavă şi are doar un maxim global. Există o formă normală care dă direct θ optim, similar cu regresia liniară? C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 4 / 14 Regresie logistică Comparaţie cu regresia liniară Regresie liniară 1 Pm 2 Minimizarea funcţiei J(θ) = hθ (x(i) ) − y(i) cu actualizarea 2 i=1 m X (i) θj := θj − α hθ (x(i) ) − y(i) xj , i=1 unde hθ (x) = θT x (funcţie liniară). Regresie logistică Maximizarea funcţiei m h X i ℓ(θ) = y(i) log hθ (x(i) ) + 1 − y(i) log(1 − hθ (x(i) )) i=1 cu actualizarea m X (i) θj := θj + α y(i) − hθ (x(i) ) xj , i=1 T unde hθ este o funcţie neliniară de θ x. C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 5 / 14 Cuprins 1 Regresie logistică 2 Metoda lui Newton 3 Algoritm de învăţare cu perceptron 4 Clasificare multiclasă Metoda lui Newton Metoda lui Newton Algoritmul de optimizare bazat pe metoda lui Newton converge mai repede decât metoda de gradient descendent. Zerourile unei funcţii Pentru o funcţie f(θ) metoda lui Newton găseşte θ∗ pentru care f(θ∗ ) = 0. Pentru f de variabilă reală avem Iniţializează căutarea în θ(0) f(θ(t) ) Actualizează θ(t+1) := θ(t) − f ′ (θ(t) ) Problema de optimizare Dacă o funcţie ℓ(θ) are un punct de optim θ∗ , atunci ℓ′ (θ∗ ) = 0. Folosim metoda lui Newton pentru găsirea zerourilor derivatei lui ℓ(θ). Pentru f(θ) = ℓ′ (θ) avem ℓ′ (θ(t) ) θ(t+1) := θ(t) − ℓ′′ (θ(t) ) C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 6 / 14 Metoda lui Newton Metoda lui Newton Pentru ℓ funcţie de mai multe variabile, i.e., θ este un vector din Rn+1 , avem regula de actualizare θ(t+1) := θ(t) − H−1 ∇θ ℓ(θ), unde H ∈ R(n+1)×(n+1) se numeşte matricea Hessiană şi are forma 2 ∂ ℓ(θ) H= ∂θi ∂θj i,j Metoda lui Newton garantează convergenţă pătratică, dar necesită inversarea matricei Hessiene. C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 7 / 14 Cuprins 1 Regresie logistică 2 Metoda lui Newton 3 Algoritm de învăţare cu perceptron 4 Clasificare multiclasă Algoritm de învăţare cu perceptron Algoritm de învăţare cu perceptron Importanţă mai degrabă istorică. Perceptronul este un model simplu pentru funcţionarea neuronilor. Funcţia de decizie Clasificatorul se bazează pe o funcţie de decizie mai ”rudimentară ” decât funcţia sigmoid. ( 1, z ≥ 0 g(z) = 0, z < 0 Actualizarea parametrilor (i) θj := θj + α y(i) − hθ (x(i) ) xj y(i) − hθ (x(i) ) = 0 dacă hθ a clasificat corect y(i) − hθ (x(i) ) = 1 dacă hθ a clasificat incorect C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 8 / 14 Cuprins 1 Regresie logistică 2 Metoda lui Newton 3 Algoritm de învăţare cu perceptron 4 Clasificare multiclasă Clasificare multiclasă Clasificarea multi-clasă Considerăm o problemă de clasificare în care variabila răspuns y poate lua k valori, y ∈ {1, 2,... , k}. Eticheta este tot discretă, dar poate lua mai mult de două valori. Modelăm y ca fiind distribuită în acord cu o distribţie multinomială, e.g., p(y|x; θ). Numerele Φ1 , P Φ2 ,... , Φk reprezintă probabilitatea fiecărui rezultat şi trebuie să îndeplinească ki=1 Φi = 1. Introducem k grupuri de parametri θ1 , θ2 ,... , θk , fiecare fiind un vector din Rd. Vrem ca θiT x să reprezinte Φi , probabilitatea P(y = i|x; θ), cu i = 1 : k. Apar două probleme: θiT x nu se află neapărat în intervalul [0, 1] şi suma tuturor θi x nu dă neapărat 1. T Folosim funcţia softmax pentru a transforma vectorul θ1T x θ2T x... θkT x într-un vector de probabilităţi nenegative a căror sumă este 1. C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 9 / 14 Clasificare multiclasă Clasificarea multi-clasă T Fie un vector t = t1 t2... tk   et1  Pk eti     i=1..  softmax(t) =  .      etk  Pk ti i=1 e Aplicăm funcţia softmax pe vectorul cu elemtenele θiT x, iar rezultatele obţinute vor fi P(y = i|x; θ).   exp(θ1T x)     T   P k T  P(y = 1|x; θ) θ1 x  i=1 exp(θi x)  ..   .  ..  .  = softmax ..  =  .     P(y = k|x; θ) T θk x  T exp(θk x)  Pk T i=1 exp(θi x) C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 10 / 14 Clasificare multiclasă Clasificare multi-clasă Dacă notăm exp(ti ) Φi = P k , j=1 exp(tj ) putem spune că probabilitatea ca eticheta y a instanţei x să fie i este exp(θiT x) P(y = i|x; θ) = Φi = Pk T. j=1 exp(θj x) Calculăm log-verosimilitatea pentru un singur exemplu (x, y). ! exp(θyT x) log p(y|x; θ) = log Pk. j=1 exp(θjT x) Funcţia cost este dată de log-verosimilitatea negativă a setului de antrenare, i.e., C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 11 / 14 Clasificare multiclasă Exemplu de clasificare Obiectiv: Clasificarea animalelor ca fiind reptile sau nu, pe baza unor caracteristici. Caracteristici Cheie: Depune ouă Are solzi Este cu sânge rece Otrăvitor Numărul de picioare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Cobra Da Da Da Da 0 Reptilă Rattlesnake Da Da Da Da 0 Reptilă C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 12 / 14 Clasificare multiclasă Exemplu de clasificare Obiectiv: Clasificarea animalelor ca fiind reptile sau nu, pe baza unor caracteristici. Caracteristici Cheie: Depune ouă Are solzi Este cu sânge rece Otrăvitor Numărul de picioare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Cobra Da Da Da Da 0 Reptilă Rattlesnake Da Da Da Da 0 Reptilă Boa Constrictor Nu Da Da Nu 0 Reptilă C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 12 / 14 Clasificare multiclasă Exemplu de clasificare Obiectiv: Clasificarea animalelor ca fiind reptile sau nu, pe baza unor caracteristici. Caracteristici Cheie: Depune ouă Are solzi Este cu sânge rece Otrăvitor Numărul de picioare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Cobra Da Da Da Da 0 Reptilă Rattlesnake Da Da Da Da 0 Reptilă Boa Constrictor Nu Da Da Nu 0 Reptilă Găină Da Da Nu Nu 2 Nu C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 12 / 14 Clasificare multiclasă Exemplu de clasificare Obiectiv: Clasificarea animalelor ca fiind reptile sau nu, pe baza unor caracteristici. Caracteristici Cheie: Depune ouă Are solzi Este cu sânge rece Otrăvitor Numărul de picioare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Cobra Da Da Da Da 0 Reptilă Rattlesnake Da Da Da Da 0 Reptilă Boa Constrictor Nu Da Da Nu 0 Reptilă Găină Da Da Nu Nu 2 Nu Aligator Da Da Da Nu 4 Reptilă C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 12 / 14 Clasificare multiclasă Provocări în Clasificare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Piton Da Da Da Nu 0 Reptilă C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 13 / 14 Clasificare multiclasă Provocări în Clasificare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Piton Da Da Da Nu 0 Reptilă Somon Da Da Da Nu 0 Nu C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 13 / 14 Clasificare multiclasă Provocări în Clasificare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Piton Da Da Da Nu 0 Reptilă Somon Da Da Da Nu 0 Nu Dart Frog Da Nu Da Da 4 Nu C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 13 / 14 Clasificare multiclasă Provocări în Clasificare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Piton Da Da Da Nu 0 Reptilă Somon Da Da Da Nu 0 Nu Dart Frog Da Nu Da Da 4 Nu Dificultate: Nu putem distinge între un Piton și un Somon doar pe baza acestor caracteristici. C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 13 / 14 Clasificare multiclasă Recapitulare Animal Depune ouă Are solzi Cu sânge rece Otrăvitor Număr picioare Etichetă Cobra Da Da Da Da 0 Reptilă Rattlesnake Da Da Da Da 0 Reptilă Boa Constrictor Nu Da Da Nu 0 Reptilă Găină Da Da Nu Nu 2 Nu Aligator Da Da Da Nu 4 Reptilă Piton Da Da Da Nu 0 Reptilă Somon Da Da Da Nu 0 Nu Dart Frog Da Nu Da Da 4 Nu Concluzii Clasificarea eficientă depinde de alegerea caracteristicilor potrivite. Modelul rafinat îmbunătățește acuratețea în identificarea reptilelor. Înțelegerea compromisurilor în clasificare este esențială pentru aplicațiile de învățare automată. C. Flutur Curs 3. Învăţare supervizată. Regresie logistică 16 octombrie 2024 14 / 14 Curs 4. Overfitting. Regularizarea funcţiei cost Clasificatori cu margine optimală Tehnici de învățare automată Cristian Flutur Departamentul de Automatică şi Ingineria Sistemelor Facultatea de Automatică şi Calculatoare Universitatea Politehnica Bucureşti 12 noiembrie 2024 Cuprins 1 Regularizarea funcţiei cost 2 Algoritmi cu vectori suport Cuprins 1 Regularizarea funcţiei cost 2 Algoritmi cu vectori suport Regularizarea funcţiei cost Interpolare polinomială Pentru evidenţierea fenomenelor de overfitting şi underfitting folosim un set de date generate ”artificial” de către o funcţie cunoscută, Γ(x) = sin(2πx), perturbată de zgomot aleator. Considerăm un set de antrenare S = ((x(1) , y(1) ),... , (x(m) , y(m) )), în care fiecare y(i) = Γ(x(i) ) + ε(i) , cu m = 10 şi ε(i) distribuit gaussian după antrenarea funcţiei predictor pe acest set, aceasta trebuie să poată prezice valoarea ŷ pentru un punct nou x̂, care nu P se află în setul S folosim interpolare polinomială hθ (x) = nj=0 θj xj = θ0 + θ1 x + θ2 x2 +... θn xn T funcţia hθ (x), deşi polinomială în x, este liniară în θT = θ0 θ1... θn 1 Pm 2 Parametrii θ se obţin prin minimizarea funcţiei cost J(θ) = hθ (x(i) ) − y(i) 2 i=1 C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 1 / 18 Regularizarea funcţiei cost Overfitting în figură vedem interpolarea datelor cu polinomul hθ (x) de grad 0, 1, 3 şi 9 polinoamele de grad 0 şi 1 interpolează slab datele, prin urmare constituie aproximări slabe ale funcţiei sin(2πx) polinomul de grad 9 trece prin toate cele m = 10 puncte din setul de antrenare J(θ∗ ) = 0, dar constituie e aproximare foarte slabă pentru sin(2πx) C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 2 / 18 Regularizarea funcţiei cost Regularizare cu cât gradul polinomului hθ (x) creşte, coeficienţii devin tot mai mari intuitiv, cu cât polinomul devine mai ”flexibil” (cu grad mai mare), cu atât tinde să se acordeze mai bine cu zgomotul de pe valorile de antrenare Cum gestionăm overfitting-ul? Reducerea complexităţii modelului prin reducerea numărului de caracteristici. Aplicarea unei regularizări: se adaugă un termen de penalizare funcţiei cost pentru a descuraja coeficienţii de la a atinge valori mari 1X m 2 λ T J(θ) = hθ (x(i) ) − y(i) + θ θ 2 i=1 2 C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 3 / 18 Regularizarea funcţiei cost Regularizare Parametrul θ0 este, de regulă, omis de la regularizare. Funcţia cost penalizată se minimizează pentru obţinerea parametrilor θ. Punctul de optim se poate obţine cu o formă normală. Dacă λ este prea mare coeficienţii devin prea penalizaţi, iar polinomul tinde către o dreaptă paralelă cu axa orizontală (underfitting). Dacă λ este prea mic penalizarea nu reuşeşte să scadă coeficienţii, iar problema de overfitting persistă. pentru polinomul de grad 9 se poate vedea că fenomenul de overfitting a fost atenuat, cu log λ = −18 (stânga). C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 4 / 18 Regularizarea funcţiei cost Regresie liniară regularizată Pentru regresia liniară regularizată folosim funcţia cost cu penalizare 1X λX 2 m n 2 J(θ) = hθ (x(i) ) − y(i) + θj 2 i=1 2 j=1 Actualizarea parametrului θ0 rămâne neschimbată m X (i) θ0 := θ0 − α hθ (x(i) ) − y(i) x0 i=1 Parametrii θj (j > 0) se actualizează după regula m X (i) θj := θj (1 − α · λ) − α hθ (x(i) ) − y(i) xj i=1 Forma normală a optimului este θ∗ = (λIn+1 + XT X)−1 XT Y C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 5 / 18 Regularizarea funcţiei cost Regresia logistică regularizată Pentru regresia logistică regularizată folosim funcţia cost cu penalizare m h X i λX n J(θ) = − y(i) log hθ (x(i) ) + 1 − y(i) log(1 − hθ (x(i) )) + θj2 i=1 2 j=1 Parametrii θj (j > 0) se actualizează după regula m X (i) θj := θj (1 − α · λ) − α hθ (x(i) − y(i) ) xj i=1 C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 6 / 18 Cuprins 1 Regularizarea funcţiei cost 2 Algoritmi cu vectori suport Clasificatori cu margine optimală Algoritmi cu vectori suport Algoritmi cu vectori suport. Support vector machines SVM sunt consideraţi printre cei mai buni algoritmi de învăţare supervizată. Probleme de clasificare cu graniţa de decizie neliniară. Putem folosi regresie logistică, dar nu direct pe setul de caracteristici dat de problemă. Se mapează setul de caracteristici x într-un alt set Φ(x), de dimensiune mai mare, care conţine combinaţii neliniare între caracteristicile din x.   x1  x2    x1  x21  x= Φ(x) =   x2  x1 x2   ... SVM ne dă o metodă de a mapa un spaţiu de caracteristici n-dimensional într-un spaţiu de dimensiune mult mai mare, e.g., nd , sau chiar infinit dimensional. Problema reformulată în noul spaţiu de caracteristici se pretează clasificatorilor liniari. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 7 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificatori cu margine optimală Vom considera probleme de clasificare binară, în care seturile de date sunt liniar separabile, i.e., există cel puţin un hiperplan în raport cu care toate clasificările sunt corecte. Clasificare binară Avem un clasificator obţinut cu regresie logistică hθ (x) = g(θT x). prezice 1 pentru θT x > 0 sau hθ > 0.5 prezice 0 pentru θT x ≤ 0 sau hθ ≤ 0.5 Corectitudinea şi siguranţa predicţiei dacă y(i) = 1, predicţia este mai de încredere cu cât θT x(i) > 0 este mai departe de 0 dacă y(i) = 0, predicţia este mai de încredere cu cât θT x(i) < 0 este mai departe de 0 Spunem despre clasificatorul hθ (x) că are o margine funcţională mare în raport cu exemplul x(i). C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 8 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificatori cu margine optimală Margine geometrică Clasificatorul liniar care separă clasele nu este unic. Ne interesează distanţele dintre clasificator şi exemplele ce mai apropiate de acesta. Notaţii Variabila de output y a clasificatorului poate lua valorile y ∈ {−1, +1} ( 1, dacă z ≥ 0 g(z) = −1, dacă z < 0. Funcţia clasificator are forma T hw,b (x) = g(wT x + b), x, w ∈ Rn , xT = x1 x2... xn , unde w este vectorul cu parametrii, iar b ţine loc de θ0 Exemplele x(i) pentru care wT x(i) + b > 0 se vor numi exemple pozitive, iar cele pentru care wT x(i) + b < 0 se vor numi exemple negative. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 9 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Margine funcţională Marginea funcţională măsoară gradul de încredere cu care se realizează fiecare predicţie. Parametrii (w, b) descriu un hiperplan care separă exemplele pozitive de cele negative. Definiţie Marginea funcţională a hiperpanului definit de (w, b), în raport cu exemplul (x(i) , y(i) ) are forma γ̂ (i) = y(i) (wT x(i) + b). Dacă y(i) = 1 am vrea ca wT x(i) + b ≫ 0, pentru ca predicţia să fie sigură. Dacă y(i) = −1 am vrea ca wT x(i) + b ≪ 0 pentru ca predicţia să fie sigură. Altfel spus, am vrea ca γ̂ (i) ≫ 0 pentru ca predicţia să fie sigură. Pentru ca predicţia să fie corectă este suficient ca γ̂ (i) > 0. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 10 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Margine funcţională Definiţie Marginea funcţională a hiperplanului definit de (w, b), în raport cu tot setul de antrenare este γ̂ = min γ̂ (i) , i=1:n i.e., cât de bine ”merge” algoritmul pe cel mai ”slab” exemplu de antrenare. Scalarea marginii funcţionale Marginea funcţională este uşor de ”păcălit” prin scalarea parametrilor: dacă substituim w := 2w şi b := 2b atunci obţinem şi γ̂ := 2γ̂. Marginea funcţională creşte artificial, fără să crească şi performanţa clasificării. Soluţie: în loc de (w, b) folosim versiunile lor scalate cu norma euclidiană a w b vectorului w ,. ∥w∥ ∥w∥ C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 11 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Margine geometrică Marginea geometrică măsoară distanţa dintre hiperplan şi exemplul de antrenare. Definiţie Marginea geometrică a hiperplanului definit de (w, b), în raport cu un exemplu de antrenare (x(i) , y(i) ) este y(i) (wT x(i) + b) γ (i) =. ∥w∥ Se observă că marginea geometrică este egală cu cea funcţională scalată cu norma euclidiană a vectorului de caracteristici: γ̂ (i) γ (i) =. ∥w∥ Definiţie Marginea geometrică a hiperplanului definit de (w.b), în raport cu tot setul de antrenare este γ = min γ (i). i=1:m C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 12 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificator cu margine optimală Clasificatorul cu margine optimală y = g(wT x + b) este o versiune foarte simplificată a SVM. Scopul este găsirea parametrilor (w, b) pentru minimizarea marginii geometrice γ. Problema de optim max γ γ,w,b y(i) (wT x(i) + b) cu constrângerile ≥γ i=1:m ∥w∥ constrângerea ne spune că fiecare exemplu (x(i) , y(i) ) are marginea geometrică ≥ γ pe γ îl vrem cât mai mare, i.e., maximizăm cea mai slabă margine geometrică numărătorul constrângerii este marginea funcţională Problemă neconvexă C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 13 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificator cu margine optimală Problema de optim max γ γ,w,b y (wT x(i) + b) (i) cu constrângerile ≥γ i=1:m ∥w∥ y(i) reprezintă eticheta; pentru clasificare binară y(i) ∈ {−1, +1} x(i) reprezintă vectorul de caracteristici ale exemplului i w este vectorul cu ponderi, b este termenul de bias, iar (w, b) reprezintă parametri modelului √ ∥w∥ este norma Euclidiană a vectorului w, i.e., ∥w∥2 = wT w constrângerea y(i) (wT x(i) + b) ≥ γ∥w∥ impune marginii funcţionale (produsul dintre eticheta clasei și scorul funcției liniare) pentru fiecare exemplu să fie proporțională cu norma vectorului de ponderi. Acest lucru asigură o marjă consistentă față de hiperplan pentru exemple. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 14 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificator cu margine optimală Problema de optim Problema de optim este greu de rezolvat din următoarele motive nelinearitate: constrângerea y(i) (wT x(i) + b) ≥ γ · ∥w∥ este neliniară din cauza termenului γ · ∥w∥. Spre deosebire de o constrângere liniară, cum ar fi y(i) (wT x(i) + b) ≥ γ, care ar fi mai ușor de tratat, aici dependența de ∥w∥ introduce o interacțiune între w și γ ce complică problema de optimizare. problema de scalare: dacă modificăm mărimea lui w , afectăm automat și valoarea lui γ în constrângere, deoarece ∥w∥ influențează direct constrângerea. Practic, maximul lui γ depinde de scalarea lui w , ceea ce face dificilă izolarea unei soluții optime fără o reformulare. neconvexitate: constrângerea de inegalitate γ · ∥w∥ ≤ y(i) (wT x(i) + b) este neconvexă, deoarece ∥w∥ este o funcție normă, iar produsul cu γ rezultă într-o expresie care nu respectă proprietățile necesare pentru optimizare convexă. Problemele neconvexe sunt adesea greu de rezolvat direct, deoarece pot avea multiple minime locale și nu există garanția că metodele standard vor găsi soluția globală. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 15 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Convexitate Funcţie convexă O funcție f : Rn → R este convexă dacă, pentru orice două puncte x, y ∈ Rn și pentru orice α ∈ [0, 1] are loc relaţia f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y) Această inegalitate arată că valoarea funcției la orice punct de pe segmentul dintre x și y este mai mică sau egală cu media ponderată a valorilor funcției la punctele x și y. Geometric, aceasta înseamnă că graficul funcției este “sub” sau “pe” linia dreaptă care unește punctele (x, f(x)) și (y, f(y)). Mulţime convexă O mulţime (un domeniu) C ⊆ Rn este convexă dacă, pentru orice două puncte x, y ∈ Rn și pentru orice α ∈ [0, 1] combinația liniară αx + (1 − α)y aparține mulțimii C. Cu alte cuvinte, mulțimea C este convexă dacă, pentru orice două puncte din mulțime, întregul segment de dreaptă care le unește se află în interiorul mulțimii. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 16 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Clasificator cu margine optimală Problema de optim reformulata în termenii marginii funcţionale Această problemă este dificil de rezolvat direct, din cauza dependenței de ∥w∥. Pentru a o simplifica, o reformulăm prin eliminarea dependenței de ∥w∥. În general, putem seta ∥w∥ = 1 (prin normalizare) sau reformula constrângerea astfel încât să maximizăm γ/∥w∥. γ̂ max γ̂,w,b ∥w∥ cu constrângerile y(i) (wT x(i) + b) ≥ γ̂ i=1:m γ̂ maximizăm γ = cu astfel încât toate marginile funcţionale să fie cel puţin γ̂ ∥w∥ scalarea marginii funcţionale nu modifică graniţa de decizie introducem o constrângere de scalare: marginea funcţională obţinută pentru parametrii (w, b) să fie γ̂ = 1 γ̂ 1 maximizarea lui = este echivalentă cu minimizarea lui ∥w∥2 ∥w∥ ∥w∥ C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 17 / 18 Algoritmi cu vectori suport Clasificatori cu margine optimală Problema echivalentă Problema de optim echivalentă convexă 1 min ∥w∥2 w,b 2 cu constrângerile y(i) (wT x(i) + b) ≥ 1 i=1:m funcția obiectiv 1 2 ∥w∥2 minimizează norma w , adică lungimea vectorului w. maximizarea marginii geometrice dintre clase, deoarece minimizarea normei w echivalează cu creșterea distanței dintre punctele (exemplele) de pe margine și hiperplanul de separare. Constrângerea y(i) (wT x(i) + b) ≥ 1 impune ca fiecare exemplu să fie clasificat corect 1 și să se afle la o distanță de cel puțin ∥w∥ de hiperplanul de separare. problema de optimizare este convexă, întrucât funcția obiectiv este convexă (pătratul normei), iar constrângerile sunt inegalități liniare în w și b. C. Flutur Curs 4. Overfitting. Regularizarea funcţiei cost 12 noiembrie 2024 18 / 18 Curs 5. Funcţii Kernel. Algoritmi cu vectori suport Tehnici de învățare automată Cristian Flutur Departamentul de Automatică şi Ingineria Sistemelor Facultatea de Automatică şi Calculatoare Universitatea Politehnica Bucureşti 12 noiembrie 2024 Cuprins 1 Scrierea parametrilor în funcţie de atribute 2 Funcţii Kernel 3 Algoritmi cu vectori suport Cuprins 1 Scrierea parametrilor în funcţie de atribute 2 Funcţii Kernel 3 Algoritmi cu vectori suport Scrierea parametrilor în funcţie de atribute Dimensiunea spaţiului de caracteristici Clasificatorii cu margine optimală se pretează problemelor cu număr rezonabil de trăsături. Clasificatorul are forma y = g(wT x + b) y(i) = g(wT x(i) + b), pentru fiecare exemplu (x(i) , y(i) ) din setul de antrenare. w ∈ Rn este vectorul cu parametrii, iar funcţia g(z) = sgn(z). Φ : Rd → Rp este un operator (o aplicaţie) între spaţiul de atribute şi cel de caracteristici.   [ ] x1 x1  x2  x= Φ(x) =    x2 x21  x1 x2 Vom numi elementele din x atribute, iar elementele din Φ(x) caracteristici. Problema de optimizare devine foarte greu de rezolvat, dacă dimensiunea lui Φ(x) este foarte mare. C. Flutur Curs 5. Funcţii Kernel. Algoritmi cu vectori suport 12 noiembrie 2024 1 / 19 Scrierea parametrilor în funcţie de atribute Cele mai mici pătrate cu caracterstici Gradient descendent Exemplele trebuie acum interpolate cu funcţia θT Φ(x), in loc de θT x, cu θ ∈ Rp. m ( ∑ ) θ := θ − α θT Φ(x(i) ) − y(i) Φ(x(i) ) i=1 Gradient stochastic descendent ( ) θ := θ − α θT Φ(x(i) ) − y(i) Φ(x(i) ) C. Flutur Curs 5. Funcţii Kernel. Algoritmi cu vectori suport 12 noiembrie 2024 2 / 19 Scrierea parametrilor în funcţie de atribute Rescrierea parametrilor w Se poate demonstra că parametrii w se pot scrie sub formă de combinaţie liniară a exemplelor de antrenare. ∑ m w= αi y(i) x(i). i=1 Justificare Pentru fiecare exemplu pozitiv de antrenare avem că g(wT x(+) + b) = 1 wT x(+) + b > 0 Pentru fiecare exemplu negativ de antrenare avem că g(wT x(−) + b) = −1 wT x(−) + b < 0 Organizăm toate exemplele pozitive, pe linii, într-o matrice X+ şi toate exemplele negative, pe linii, într-o matrice X−. C. Flutur Curs 5. Funcţii Kernel. Algoritmi cu vectori suport 12 noiembrie 2024 3 / 19 Scrierea parametrilor în funcţie de atribute Rescrierea parametrilor w Pentru toate exemplele obţinem inegalităţile     1 1 .  .  X+ w − b ..  > 0 X− w − b ..  < 0 1 1 sau sistemele liniare de ecuaţii        1 c1 1 d1 .  ..  .  ..  X+ w − b ..  − . =0 X− w − b ..  + .  = 0. 1 cd 1 dd Rescriem ecuaţiile X+ w − b+ = 0 X− w − b− = 0 [ ] [ ] X+ b+ w= sau Xw = B X− b− C. Flutur Curs 5. Funcţii Kernel. Algoritmi cu vectori suport 12 noiembrie 2024 4 / 19 Scrierea parametrilor în funcţie de atribute Rescrierea parametrilor w Xw = B este un sistem liniar supradeterminat, cu X ∈ Rm×d dacă X este matrice monică, putem folosi o compresie de rang pentru a scrie [ ] [ ] X1 B1 w= , deci w = X−1 1 B1. 0 B2 [ ] X+ putem spune că fiecare wj este o combinaţie liniară de elemente din. X− Problema de optimizare primală 1 T min w w w,b 2

Curs 1. Introducere - Tehnici de învățare automată (PDF)

Document Details

Tags

Related

Summary

Full Transcript