Exerciµii - Alexandru Ioan Cuza Universityciortuz/ML.ex-book/sumar.pdfExerciµii de µare v în...

transcript

Exer iµii de înv µare automat

Liviu Ciortuz, Alina Munteanu, Elena B d r u

ISBN: 978-973-0-30467-1

1. Fundamente:

probabilit µi, variabile aleatoare, teoria informaµiei,

fun µii-nu leu, ³i metode de optimizare

Evenimente aleatoare ³i formula lui Bayes

− fun µia de probabilitate � âteva propriet µi are deriv din de�niµia ei: ex. 1,

ex. 64;

− al ularea unor probabilit µi elementare: ex. 2.a, ex. 61;

− al ularea unor probabilit µi ondiµionate: ex. 2.b, ex. 3, ex. 62.a;

− regula de multipli are: ex. 64.b;

− formula probabilit µii totale: ex. 64.e;

formula probabilit µii totale � varianta ondiµional : ex. 67. d;

− independenµa evenimentelor aleatoare: ex. 4, ex. 5, ex. 62.b ;

− independenµa ondiµional a evenimentelor aleatoare � leg tura dintre forma

�tare� ³i forma �slab � a de�niµiei pentru a east noµiune: ex. 63;

− formula lui Bayes � apli are: ex. 6, ex. 7, ex. 65, ex. 66;

formula lui Bayes � varianta ondiµional : ex. 67.b;

− re apitulare: probabilit µi elementare ³i probabilit µi ondiµionate � âteva

propriet µi (A/F): ex. 8, ex. 67.

Variabile aleatoare

− fun µie de distribuµie umulativ (engl., umulative distribution fun tion, .d.f.),

un exemplu: ex. 27;

− proprietatea de liniaritate a mediei : ex. 9.a;

− varianµa ³i ovarianµa: propriet µi de tip ara terizare: ex. 9.b ;

− ovarianµa ori ror dou variabile aleatoare independente este 0: ex. 10;re ipro a a estei a�rmaµii nu este adev rat în general: ex. 11.a; totu³i ea are

lo da variabilele sunt de tip binar (adi iau doar valorile 0 ³i 1): ex. 11.b,ex. 71;

− o ondiµie su� ient pentru a Var[X + Y ] = Var[X ] + Var[Y ]: independenµa

variabilelor X ³i Y : ex. 19.

• pentru variabile aleatoare dis rete:

− al ularea mediilor ³i a varianµelor � exempli� are: ex. 12, ex. 68, ex. 70.a;

− de�nirea unei variabile-indi ator u ajutorul unui eveniment aleator; al ula-

rea mediei a estei variabile: ex. 69;

− regula de înl nµuire (pt. var. aleat.) � apli are: ex. 13;

− regula de multipli are (pt. var. aleat.), varianta ondiµional � demonstraµie:

ex. 14;

− independenµ : ex. 70.b, ex. 72.a, ex. 73.a;

independenµ ondiµional : ex. 15, ex. 72.b, ex. 73.b, ex. 74.b;

o ondiµie su� ient pentru independenµa ondiµional : ex. 75;

• pentru variabile aleatoare ontinue:

− dat �ind o fun µie are depinde de un parametru real, s se al uleze valoa-

rea respe tivului parametru astfel în ât fun µia respe tiv s �e o fun µie de

densitate de probabilitate (engl., probability density fun tion, p.d.f.): ex. 16.a,

ex. 17, ex. 76;

− dat �ind un p.d.f., s se al uleze o anumit probabilitate: ex. 16. , ex. 77;

− variabile aleatoare dis rete vs. variabile aleatoare ontinue; p.m.f. vs. p.d.f.:

ex. 78;

− variabile aleatoare dis rete ³i variabile aleatoare ontinue; independenµa ³i

al ul de medii: ex. 79;

• ve tor de variabile aleatoare:

o proprietate: matri ea de ovarianµ este simetri ³i pozitiv de�nit : ex. 18;

al ulul matri ei de ovarianµ ând asupra ve torului de variabile aleatoare

oper m transform ri liniare: ex. 80;

• re apitulare: ex. 19, ex. 81.

Distribuµii probabiliste uzuale

• distribuµii dis rete

− distribuµia Bernoulli :

suma de variabile identi distribuite; media sumei: ex. 20;

mixtur de distribuµii Bernoulli: ex. 85;

− distribuµia binomial :

veri� area ondiµiilor de de�niµie pentru p.m.f.: ex. 21.a;

al ulul mediei ³i al varianµei: ex. 21.b ;

al ularea unor probabilit µi (simple ³i respe tiv ondiµionale): ex. 82;

− distribuµia ategorial :

al ularea unor probabilit µi ³i a unor medii: ex. 83;

mixtur de distribuµii ategoriale: al ulul mediei ³i al varianµei: ex. 23;

− distribuµia geometri :

al ularea num rului �a³teptat� / mediu de �observaµii� ne esare pentru a

un anumit eveniment s se produ : ex. 84;

− distribuµia Poisson:

veri� area ondiµiilor de de�niµie pentru p.m.f., al ulul mediei ³i al varianµei:

ex. 22;

• distribuµii ontinue

− distribuµia ontinu uniform :

exemplu de distribuµie ontinu uniform univariat ; al ularea mediei ³i a

varianµei: ex. 87;

al ulul unei p.d.f. orelate, pornind de la dou variabile [urmând distribuµii

ontinue uniforme univariate℄ independente; al ulul unei anumite probabili-

t µi, folosind p.d.f. orelat : ex. 24;

exemplu de distribuµie ontinu uniform bivariat ; al ularea unei p.d.f. on-

diµionale; veri� area independenµei elor dou distribuµii marginale; al ulul

mediilor unor p.d.f.-uri ondiµionale: ex. 86, ex. 79;

− distribuµia exponenµial :

veri� area ondiµiilor de de�niµie pentru p.d.f.,

al ulul mediei ³i al varianµei: ex. 25.a;

− distribuµia Gamma:

veri� area ondiµiilor de de�niµie pentru p.d.f., al ulul mediei ³i al varianµei:

ex. 25.b;

− distribuµia gaussian univariat :

veri� area ondiµiilor de de�niµie pentru p.d.f., al ulul mediei ³i al varianµei:

ex. 26;

�standardizare� (i.e., redu erea azului nestandard la azul standard): ex. 27;

− distribuµia gaussian multivariat :

matri e simetri e ³i pozitiv de�nite

o proprietate de tip fa torizare folosind

ve tori proprii : ex. 29;

p.d..f.-ul distribuµiei gaussiane multivariate este într-adev r p.d.f.:

ex. 30;

o proprietate important , în azul în are matri ea de ovarianµ este diago-

nal : p.d.f.-ul orelat este produsul p.d.f.-urilor marginale ( are sunt indepen-

dente): ex. 28;

distribuµia gaussian bivariat : exempli� are; al ularea expli it a p.d.f.-

ului, dat �ind ve torul de medii ³i matri ea de ovarianµ : ex. 88;

o proprietate pentru distribuµia gaussian bivariat : distribuµia ondiµional

a unei omponente în raport u ealalt omponent este tot de tip gaussian;

al ulul parametrilor a estei distribuµii ondiµionale: ex. 31;

− mixturi de distribuµii gaussiane multivariate:

exprimarea ve torului de medii ³i a matri ei de ovarianµ în fun µie de mediile

³i matri ele de ovarianµ ale distribuµiilor omponente: ex. 89;

− mixturi de distribuµii oare are:

al ulul mediilor ³i al varianµelor (în fun µie de mediile ³i matri ele de ova-

rianµ ale distribuµiilor omponente): ex. 90;

− distribuµia Bernoulli ³i distribuµia normal standard:

intervale de în redere, teorema limit entral ; apli aµie la al ulul erorii reale

a unui lasi� ator: ex. 32;

• hestiuni re apitulative ( orespondenµa dintre nume de distribuµii ³i expresiile

unor p.d.f.-uri date): ex. 91.

A³a sunt matri ele de ovarianµ ale variabilelor gaussiene multivariate.

Adi satisfa e ondiµiile din de�niµia noµiunii de p.d.f.

Elemente de teoria informaµiei

− re-des operirea de�niµiei entropiei, pornind de la un set de propriet µi dezi-

rabile: ex. 33;

− de�niµii ³i propriet µi imediate pentru entropie, entropie orelat , entro-

pie ondiµional spe i� , entropie ondiµional medie, â³tig de informaµie:

ex. 34;

exempli� area a estor noµiuni (varianta dis ret ): ex. 35, ex. 36, ex. 92;

un exemplu de al ul pentru entropia unei variabile ontinue (distribuµia ex-

ponenµial ): ex. 37;

o proprietate a entropiei: nenegativitatea: ex. 34.a, ex. 98.a;

o margine superioar pentru valorea entropiei unei variabile aleatoare dis-

rete: ex. 93;

o proprietate a â³tigului de informaµie: nenegativitatea: ex. 38. , ex. 96;

− o apli aµie pentru â³tigul de informaµie: sele µia de tr s turi : ex. 39;

− entropia orelat : forma parti ular a relaµiei de �înl nµuire� în azul varia-

bilelor aleatoare independente: ex. 40, ex. 94, ex. 98. ;

Entropie orelat ³i ondiµionat : formula de �înl nµuire� ondiµional : ex. 95;

− entropia relativ : de�niµie ³i propriet µi elementare; exprimarea â³tigului de

informaµie u ajutorul entropiei relative: ex. 38;

− ross-entropie: de�niµie, o proprietate (nenegativitatea) ³i un exemplu simplu

de al ulare a valorii ross-entropiei: ex. 41;

un exemplu de apli aµie pentru ross-entropie: sele µia modelelor probabiliste:

ex. 97;

− inegalitatea lui Gibbs: un az parti ular; omparaµie între valorile entropiei ³i

ale ross-entropiei: ex. 42.

Fun µii-nu leu

− a�area fun µiei de �mapare� a tr s turilor are orespunde unei fun µii-nu leu

date: ex. 43, ex. 99, ex. 100.a;

omparaµii asupra num rului de operaµii efe tuate la al ularea valorii unor

fun µii-nu leu (în spaµiul iniµial vs. spaµiul nou de �tr s turi�): ex. 100.b;

al ulul distanµelor eu lidiene în spaµii de �tr s turi� folosind doar fun µii-

nu leu: ex. 47;

• teorema lui Mer er (1909): ondiµii ne esare ³i su� iente pentru a o fun µie

s �e fun µie-nu leu: ex. 44.ab;

• rezultate de tip � onstru tiv� pentru [obµinerea de noi℄ fun µii-nu leu: ex. 44. ,45, ex. 46, ex. 101, 103, ex. 52.b;

�normalizarea� fun µiilor-nu leu: ex. 102;

− o inegalitate [derivat din inegalitatea Cau hy-Buniakovski-S hwarz℄, are fur-

nizeaz o margine superioar pentru K(x, x′), valoarea absolut a unei fun µii

nu leu oare are: ex. 104;

− un exemplu de fun µie-nu leu are serve³te la a m sura similaritatea dintre

dou imagini oare are: ex. 48;

− o fun µie-nu leu parti ular , are asigur separabilitate liniar [în spaµiul de

tr s turi℄ pentru ori e set de instanµe de antrenament: ex. 105;

− fun µia-nu leu gaussian / fun µia u baza radial (engl., Radial Basis Fun -

tion, RBF):

• demonstraµia faptului RBF este într-adev r fun µie-nu leu: ex. 49;

◦ fun µia de �mapare� orespunz toare fun µiei-nu leu RBF ia valori într-un

spaµiu [de �tr s turi�℄ de dimensiune in�nit : ex. 50;

◦ propriet µi simple ale nu leului RBF: ex. 51, ex. 106;

• ori e mulµime de instanµe distin te, având ori e eti hetare posibil , este

separabil liniar în spaµiul de �tr s turi� da se folose³te nu leul RBF u

parametrul ales în mod onvenabil: ex. 26.a de la apitolul Ma³ini u ve tori-

suport;

− re apitulare (A/F): ex. 52, ex. 108.

Metode de optimizare în înv µarea automat

− (P0) de�niµii, ara teriz ri ³i âteva propriet µi pentru fun µii onvexe: ex. 53;

− metoda gradientului , metoda lui Newton; exempli� are: ex. 54;

(P1) ondiµii su� iente pentru onvergenµa metodei gradientului: ex. 110;

(P2) o proprietate interesant a metodei lui Newton: în azul ori rei fun µii

de gradul al doilea (de una sau mai multe variabile), apli area a estei metode

de optimizare impli / ne esit exe uµia unei singure iteraµii: ex. 111;

(P3) reparametrizarea liniar a atributelor nu afe teaz [rezultatele obµinute

u℄ metoda lui Newton, îns afe teaz metoda gradientului: ex. 112;

− metoda dualit µii Lagrange:

(P4) demonstrarea propriet µii de dualitate slab : ex. 55;

(P5) demonstrarea unei p rµi din teorema KKT : ex. 56;

exemple de apli are: ex. 57, ex. 58, ex. 113;

un exemplu de problem de optimizare onvex pentru are ondiµiile KKT

nu sunt satisf ute: ex. 114;

− dou variante a algoritmului Per eptron,

pentru are relaµia de a tualizare a

ponderilor se obµine rezolvând [ âte℄ o problem de optimizare [ onvex ℄ u

restri µii;

− hestiuni re apitulative: ex. 109.

Vedeµi problema 16 de la apitolul Reµele neuronale arti� iale.

2. Metode de estimare a parametrilor; metode de regresie

Noµiuni preliminare

− elemente de al ul ve torial (în parti ular, produsul s alar)

³i de al ul matri eal: ex. 29 de la ap. Fundamente;

norma L2 (eu lidian ) ³i norma L1: ex. 14, ex. 47, ex. 49;

al ulul derivatelor parµiale [de ordinul întâi ³i al doilea℄: ex. 17;

reguli de derivare u argumente ve toriale: ex. 12;

− metode de optimizare (în speµ pentru a�area maximului / minimului unei

fun µii reale, derivabile): metoda analiti , metoda gradientului, metoda lui

Newton; exempli� are: ex. 54 de la apitolul de Fundamente;

Estimarea parametrilor unor distribuµii probabiliste uzuale

− distribuµia Bernoulli: ex. 1 (+MAP, folosind distr. Beta), ex. 2, ex. 30 (un

az parti ular), ex. 29 (bias-ul ³i varianµa estimatorului MLE);

− distribuµia ategorial : ex. 31, ex. 32 (+MAP, folosind distr. Diri hlet);

− distribuµia geometri : ex. 33 (+MAP, folosind distr. Beta);

− distribuµia Poisson: ex. 3 (+MAP, folosind distr. Gamma);

− distribuµia uniform ontinu : al ul de probabilit µi ³i MLE:

în R: ex. 4, ex. 34, ex. 35; în R2: ex. 5, ex. 36;

− distribuµia gaussian univariat :

MLE pt. µ, onsiderând σ2 unos ut: ex. 2 (+MAP, folosind distribuµia gaus-

sian ), ex. 38 (+analiza dis riminativ );

MLE pt. σ2, atun i ând nu se impun restri µii asupra lui µ: ex. 8 (+depla-

sare);

MLE pt. σ2, atun i ând µ = 0: ex. 39 (+nedeplasare);

− distribuµia gaussian multivariat : ex. 10, ex. 40 (+MAP, folosind distr.

Gauss-Wishart);

− distribuµia exponenµial : ex. 6, ex. 37 (+MAP, folosind distr. Gamma);

− distribuµia Gamma: ex. 9 ³i ex. 41 (ultimul, folosind metoda gradientului ³i

metoda lui Newton).

• existenµa ³i uni itatea MLE: ex. 11.

Regresia liniar

• prezentarea general a metodei regresiei liniare:

− MLE ³i orespondenµa u estimarea în sens LSE (least squared errors):

ex. 14.A;

parti ularizare pentru azul univariat: ex. 12.ab, ex. 42;

exempli� are pentru azul univariat (ex. 13, ex. 43) ³i pentru azul bivariat

(ex. 45.a, ex. 53);

În mod impli it, în a east se µiune se va onsidera termenul-zgomot este modelat u distribuµia gaussian

(da nu se spe i� altfel, în mod expli it).

− (P1) s alarea atributelor nu s himb predi µiile obµinute (pentru instanµele

de test) u ajutorul formulelor analiti e: ex. 15, 59.a;

− (P2) ad ugarea de noi tr s turi / atribute nu m re³te suma p tratelor ero-

rilor: ex. 48;

− o proprietate surprinz toare a regresiei liniare: ad ugarea âtorva �observa-

µii� suplimentare poate ondu e la modi� area radi al a valorilor optime ale

parametrilor de regresie: CMU, 2014 fall, Z. Bar-Joseph, W. Cohen, HW2,

pr. 4;

− [rezolvarea problemei de℄ regresie liniar folosindmetoda lui Newton: ex. 17;

−MAP ³i orespondenµa u regularizarea de norm L2 (regresia ridge): ex. 14.C;

parti ularizare pentru azul univariat: ex. 12. ;

− regularizarea de norm L1 (regresia Lasso): ex. 47.a;

− (P3) efe tul de diminuare a ponderilor (engl., weight de ay) în azul regu-

lariz rii de norm L2 (respe tiv L1) a regresiei liniare, în omparaµie u azul

neregularizat: ex 47.b;

◦ bias-ul ³i [ o℄varianµa estimatorului regresiei liniare; bias-ul regresiei ridge:

ex. 16;

◦ regresia polinomial [LC: mai general: folosirea a³a-numitelor fun µii de baz ℄:

ex. 14.B;

exempli� are pentru azul bivariat: CMU, 2015 spring, T. Mit hell, N. Bal-

an, HW4, pr. 1;

• azul regresiei liniare u termen de regularizare L2 (regresia ridge):

dedu erea regulilor de a tualizare pentru medoda gradientului as endent:

varianta �bat h� / �steepest des ent�: ex. 18.a;

³i varianta stohasti / se venµial / �online�: ex. 18.b; exemplu de apli are:

ex. 46;

• azul regresiei liniare u termen de regularizare L1 (regresia Lasso):

rezolvare u metoda des re³terii pe oordonate (engl., � oordinate des ent�):

ex. 49;

rezolvare u metoda sub-gradientului (apli are la sele µia de tr s turi): CMU,

2009 fall, C. Guestrin, HW2, pr. 2;

• regresia liniar în azul zgomotului modelat u distribuµia Lapla e (în lo ul

zgomotului gaussian): ex. 19.B;

exempli� are pentru azul bivariat: ex. 45. ;

rezolvare în azul univariat [ hiar parti ularizat℄ u ajutorul derivatei, a olo

unde a easta exist : ex. 50;

◦ regresia liniar ³i over�tting-ul : ex. 22;

◦ regresie liniar folosit pentru lasi� are: exempli� are: ex. 53;

• azul multivaluat al regresiei liniare, redu erea la azul uninomial: ex. 52;

• regresia liniar u regularizare L2 (regresia ridge), kernel-izarea e uaµiilor

�normale�: ex. 20;

(P4) folosind nu leu RBF, eroarea la antrenare devine 0 atun i ând parame-

trul de regularizare λ tinde la 0: ex. 21;

• regresia liniar ponderat :: ex. 19.A;

parti ularizare / exempli� are pentru azul bivariat: ex. 45.b;

o proprietate a regresiei liniare lo al-ponderate [demonstrat în azul univa-

riat℄: �netezirea� liniar : ex. 51; azul multivaluat, u regularizare L2: Stan-

ford, 2015 fall, Andrew Ng, midterm, pr. 2;

◦ regresia liniar (kernelizat ) lo al-ponderat , neparametri :

parti ularizare / exempli� are pentru azul univariat, u nu leu gaussian:

CMU, 2010 fall, Aarti Singh, midterm, pr. 4.

Regresia logisti

− prezentare general ,

(•) al ulul fun µiei de log-verosimilitate, estimarea parametrilor în sens MLE,

folosind metoda gradientului (i.e., dedu erea regulilor de a tualizare a para-

metrilor): ex. 23, 59.b;

parti ularizare pentru azul datelor din R2: ex. 54 (in lusiv regularizare L1 /

estimarea parametrilor în sens MAP, folosind o distribuµie a priori Lapla e);

− (P0) graniµa de de izie pentru regresia logisti : ex. 54.d;

− (P1) fun µia de log-verosimilitate în azul regresiei logisti e este on av (de i

are un maxim global), �ind matri ea hessian este pozitiv de�nit : ex. 24;

Observaµie: Demonstraµia furnizeaz tot e este ne esar pentru obµinerea

[ulterioar a℄ relaµiei de a tualizare a parametrilor la apli area metodei lui

Newton în azul regresiei logisti e;

− (P2) analiza efe tului dupli rii atributelor: ex. 55;

− (P3) efe tul de diminuare a ponderilor (engl., weight de ay) în azul regu-

lariz rii de norm L2 a regresiei logisti e � adi la estimarea parametrilor

în sens MAP, folosind a distribuµie a priori distribuµia gaussian multivari-

at sferi �, în omparaµie u azul estim rii parametrilor în sensul MLE:

ex. 25;

− Variante / extensii ale regresiei logisti e:

regresia logisti lo al-ponderat , u regularizare L2:

(•) al ularea ve torului gradient ³i a matri ei hessiene (ne esare pentru apli-

area metodei lui Newton în a est az): ex. 56;

regresia logisti kernel-izat :

(•) adaptarea metodei gradientului: ex. 26;

regresia logisti n-ar (a³a-numita regresie softmax), u regularizare L2:

(•) al ulul fun µiei de log-verosimilitate, dedu erea regulilor de a tualizare a

ponderilor, folosind metoda gradientului: ex. 27;

− (P4) o [interesant ℄ proprietate omun pentru regresia liniar ³i regresia

logisti : ex. 57;

− întreb ri ( u r spuns A/F) u privire la apli area metodei lui Newton ompa-

rativ u metoda gradientului (în ontextul rezolv rii problemelor de regresie

liniar ³i / sau regresie logisti ): ex. 59. ;

− omparaµii între regresia logisti ³i alµi lasi� atori (Bayes Naiv, ID3): ex. 54. ,

ex. 58.ab.

3. Arbori de de izie

− partiµie a unei mulµimi: ex. 64 de la ap. Fundamente;

− propriet µi elementare ale fun µiei logaritm; formule uzuale pentru al ule u

logaritmi;

• Elemente de teoria informaµiei (vedeµi se µiunea orespunz toare din ap. Fun-

damente):

− entropie, de�niµie: T. Mit hell, Ma hine Learning , 1997 (desemnat în

ontinuare simplu prin artea ML), pag. 57; ex. 2.a, ex. 37.a, ex. 33.a;

− entropie ondiµional spe i� : ex. 15.a;

− entropie ondiµional medie: ex. 2. d, ex. 33. ;

− â³tig de informaµie (de�niµie: artea ML, pag. 58): ex. 2. d, ex. 5.a,

ex. 31, ex. 37.b, ex. 33.e;

− arbori de de izie, v zuµi a stru tur de date: ex. 1, ex. 29

³i, respe tiv, a program în logi a propoziµiilor: ex. 2.e, ex. 36.b ;

• (P0) expresivitatea arborilor de de izie u privire la fun µii boolene: ex. 30;

− spaµiu de versiuni pentru un on ept (de înv µat): ex. 1, ex. 29, ex. 35.

Algoritmul ID3

− pseudo- od: artea ML, pag. 56;

− bias-ul indu tiv : ibidem, pag. 63-64;

− exemple simple de apli are: ex. 2, ex. 3, ex. 5, ex. 34, ex. 35, ex. 37, ex. 38;

− ID3 a algoritm per se:

• este un algoritm de utare;

spaµiul de utare � mulµimea tuturor arborilor de de izie are se pot

onstrui u atributele de intrare în nodurile de test ³i u valorile atribu-

tului de ie³ire în nodurile de de izie � este de dimensiune exponenµial

în raport u num rul de atribute: ex. 1, ex. 3, ex. 29, ex. 35;

ID3 are a obie tiv utarea unui arbore / model are i. s expli e ât mai

bine datele (în parti ular, atun i ând datele sunt onsistente, modelul

trebuie s �e onsistent u a estea), ii. s �e ât mai ompa t, din motive

de e� ienµ la generalizare ³i iii. în �nal s aib o [ ât mai] bun putere

de generalizare;

◦ ID3 ar putea � v zut ³i a algoritm de optimizare;

LC: Alternativ, putem spune algoritmul ID3 produ e o stru tur de tip ierarhie (arbore) între diferite

partiµion ri ale setului de instanµe de antrenament, a east ierarhie �ind generat pe baza orespondenµei dintre

atributul de ie³ire ³i atributele de intrare, are sunt ad ugate la model âte unul pe rând.

LC: Am putea s -l interpret m pe ID3 a �ind un algoritm are aut între diferitele distribuµii probabiliste

dis rete are pot � de�nite pe setul de date de antrenament una are s satisfa erinµa de ierarhizare, ³i pentru

are entropia s �e minimal (vedeµi proprietatea de stru turalitate de la ex. 33 de la ap. Fundamente. Cerinµa

a arborele ID3 s �e minimal ( a num r de niveluri / noduri) este îns mai important , mai pra ti ³i mai

u³or de înµeles.

• greedy ⇒ nu garanteaz obµinerea soluµiei optime d.p.v. al num rului de

niveluri / noduri:

ex. 4, ex. 22.a, ex. 36 (vs. ex. 35.b, ex. 3.b), ex. 44;

• de tip divide-et-impera (⇒ �Iterative Di hotomizer�), re ursiv;

◦ 1-step look-ahead ;

• omplexitate de timp (vedeµi Weka book, 2011, pag. 199):

la antrenare, în anumite ondiµii: O(dm logm); la testare O(d),unde d este num rul de atribute, iar m este num rul de exemple;

− ID3 a algoritm de înv µare automat :

• bias-ul indu tiv al algoritmului ID3:

[dorim a modelul s aib stru tur ierarhi , s �e ompatibil / onsis-

tent u datele da a estea sunt onsistente (adi , ne ontradi torii), iar]arborele [produs de℄ ID3 trebuie s aib un num r ât mai mi de niveluri

/ noduri;

• algoritm de înv µare de tip �eager�;

• analiza erorilor :

la antrenare: ex. 7.a, ex. 10.a, ex. 40;

[a urateµe la antrenare: ex. 6;]la validare: CMU, 2003 fall, T. Mit hell, A. Moore, midterm, pr. 1;

la n-fold ross-validare

la ross-validare leave-one-out (CVLOO): ex. 10.b, ex. 43.b ;

• robusteµe la �zgomote� ³i over�tting : ex. 10, ex. 22.b , ex. 43, ex. 66.b;

• zone de de izie ³i graniµe de separare / de izie pentru arbori de de izie

u variabile ontinue: ex. 10, ex. 42, ex. 43, ex. 44.

Observaµie: Zonele de de izie produse de algoritmul ID3 nu sunt în mod

neap rat uni e, �ind arborele de de izie reat de ID3 nu este determinat

în mod uni (vedeµi proprietatea (P2), mai jos).

Extensii / variante ale algoritmului ID3

− atribute u valori ontinue: ex. 10-12, ex. 15. , ex. 41-45; ap. Înv µare bazat

pe memorare, ex. 11.b;

alte variante de partiµionare a intervalelor de valori pentru atributele ontinue:

ex. 13, ex. 47;

− atribute dis rete u multe valori: ex. 14;

− atribute u valori nespe i� ate / absente pentru unele instanµe;

− atribute u diferite osturi aso iate: ex. 15;

− redu erea ara terului �eager� al înv µ rii: ex. 17;

− redu erea ara terului �greedy� al înv µ rii:

IG u �2-step look-ahead�: ex. 18, ex. 19;

variante de tip �look-ahead� spe i� e atributelor ontinue: ex. 48;

3-way splitting (sau, mai general, n-way splitting) pentru atributele ontinue:

ex. 13, ex. 46;

− folosirea altor m suri de �impuritate� în lo ul â³tigului de informaµie:

Gini Impurity, Mis lassi� ation Impurity: ex. 16;

− redu erea over�tting-ului:

redu ed-error pruning (folosind un set de date de validare):

artea ML, pag. 69-71; A. Cornuéjols, L. Mi let, 2nd ed., pag. 418-421;

rule post-pruning: artea ML, pag. 71-72; ex. 50

top-down vs. bottom-up pruning, folosind un riteriu bazat pe â³tigul de

informaµie: ex. 20, ex. 49;

pruning folosind testul statisti χ2: ex. 21, ex. 51.

Propriet µi ale arborilor ID3

• (P1) arborele produs de algoritmul ID3 este onsistent (adi , în on ordanµ )

u datele de antrenament, da a estea sunt onsistente (adi , ne ontradi -

torii). Altfel spus, eroarea la antrenare produs de algoritmul ID3 pe ori e

set de date onsistente este 0: ex. 2-4, ex. 35-36;

• (P2) arborele produs de algoritmul ID3 nu este în mod neap rat uni : ex. 3,

ex. 35;

• (P3) arborele ID3 nu este neap rat optimal ( a nr. de noduri / niveluri):

ex. 4, ex. 22, ex. 36;

• (P4) in�uenµa atributelor identi e ³i, respe tiv, a instanµelor multiple asupra

arborelui ID3: ex. 8;

◦ (P5) o margine superioar pentru eroarea la antrenare a algoritmului ID3, în

fun µie de num rul de valori ale variabilei de ie³ire): ex. 7.b;

◦ (P6) o aproximare simpl a num rului de instanµe gre³it lasi� ate din totalul

de M instanµe are au fost asignate la un nod frunz al unui arbore ID3, u

ajutorul entropiei (H) nodului respe tiv: ex. 39;

• (P7) graniµele de separare / de izie pentru arborii ID3 u atribute de intrare

ontinue sunt întotdeauna paralele u axele de oordonate: ex. 10, ex. 12,

ex. 42, ex. 43, ex. 44 ³i ap. Înv µare bazat pe memorare, ex. 11.b.

Observaµie: Urm toarele trei propriet µi se refer la arbori de de izie în ge-

neral, nu doar la arbori ID3.

• (P8) adân imea maxim a unui arbore de de zie, ând atributele de intrare

sunt ategoriale: num rul de atribute: ex. 52. ;

◦ (P9) o margine superioar pentru adân imea unui arbore de de zie ând atri-

butele de intrare sunt ontinue, iar datele de antrenament sunt (ne)separabile

liniar: ex. 11;

◦ (P10) o margine superioar pentru num rul de noduri-frunz dintr-un arbore

de de izie, în fun µie de num rul de exemple ³i de num rul de atribute de

intrare, atun i ând a estea (atributele de intrare) sunt binare: ex. 9;

Înv µare automat de tip ansamblist folosind arbori de de izie:

Algoritmul AdaBoost

• Noµiuni preliminare:

distribuµie de probabilitate dis ret , fa tor de normalizare pentru o distribuµie

de probabilitate, ipoteze �slabe� (engl., weak hypotsesis), ompas de de izie

(engl., de ision stump), prag de separare (engl., threshold split) pentru un

ompas de de izie, prag exterior de separare (engl., outside threshold split),

eroare ponderat la antrenare (engl., weighted training error), vot majoritar

ponderat (engl., weighted majority vote), over�tting, ansambluri de lasi�-

atori (vedeµi ex. 64), fun µii de ost / pierdere (engl., loss fun tion) (vedeµi

ex. 63 ³i ex. 23);

− pseudo- odul algoritmului AdaBoost + onvergenµa erorii la antrenare: ex. 23;

− exemple de apli are: ex. 24, 54, 55, 56, 57;

• AdaBoost a algoritm per se:

algoritm iterativ, algoritm de utare (spaµiul de utare este mulµimea ombi-

naµiilor liniare are se pot onstrui peste lasa de ipoteze �slabe� onsiderate),

algoritm de opimizare se venµial (minimizeaz o margine superioar pentru

eroarea la antrenare), algoritm greedy (da la �e are iteraµie se alege ea

mai bun ipotez �slab �).

− înv µabilitate empiri γ-slab :de�niµie: ex. 23.f

exempli� area unor azuri ând nu exist garanµie pentru înv µabilitate γ-slab : ex. 59, 60;

− AdaBoost a algoritm de optimizare se venµial în raport u fun µia de ost

/ �pierdere� negativ-exponenµial : ex. 25;

− marginea de votare: ex. 26;

− sele tarea tr s turilor folosind AdaBoost; apli are la lasi� area de do u-

mente: ex. 61;

− o variant generalizat a algoritmului AdaBoost: ex. 63;

− re apitulare (întreb ri u r spuns adev rat / fals): ex. 28 ³i 65;

• Propriet µi ale algoritmului AdaBoost:

(P0) AdaBoost poate produ e rezultate diferite atun i ând are posibilitatea

s aleag între dou sau mai multe [ ele mai bune℄ ipoteze �slabe�: ex. 24, 54;

(P1) errDt+1(ht) =

2(ex. 23.a);

a o onse inµ , rezult ipoteza ht nu poate � resele tat ³i la iteraµia t+1;ea poate � resele tat la o iteraµie ulterioar ;

(P2) Din relaµia de de�niµie pentru distribuµia Dt+1 rezult

Zt = e−αt · (1− εt) + eαt · εt = 2√

εt(1− εt) ³iεt ∈ (0, 1/2)⇒ Zt ∈ (0, 1) (ex. 23.a).

(P3) Dt+1(i) =1

t′=1 Zt′e−yift(xi)

, unde ft(xi)def.

= −∑t

t′=1 αt′ht′(xi) (ex. 23.b).

Produsul yift(xi) se nume³te margine algebri ;

(P4) errS(Ht) ≤∏t

t′=1 Zt, adi eroarea la antrenare omis de ipoteza ombi-

nat produs de AdaBoost este majorat de produsul fa torilor de normalizare

(ex. 23. );

(P5) AdaBoost nu optimizeaz în mod dire t errS(Ht), i marginea sa superi-

t′=1 Zt; optimizarea se fa e în mod se venµial (greedy): la iteraµia t se

minimizeaz valoarea lui Zt a fun µie de αt, eea e ondu e la αt = ln

1− εtεt

(ex. 23.d);

′) εi > εj ⇒ αi < αj ( onse inµ imediat din relaµia αt = ln

1− εtεt

ex. 23.a;

(P6) O onse inµ din relaµia (120) ³i (P5): Dt+1(i) =

2εtDt(i), i ∈M

2(1− εt)Dt(i), i ∈ C

(P7) errS(Ht) nu neap rat des re³te de la o iteraµie la alta; în s himb, des res

marginile sale superioare:

∏tt′=1 Zt′ ³i exp(−

∑tt′=1 γ

2t′) (ex. 23.e);

(P8) O ondiµie su� ient pentru înv µabilitate γ-slab , bazat pe marginea

de votare: marginea de votare a ori rei instanµe de antrenament s �e de el

puµin 2γ, la ori e iteraµie a algoritmului AdaBoost (ex. 27);

(P9) Ori e mulµime format din m instanµe din R are sunt eti hetate în mod

onsistent poate � ore t lasi� at de tre o ombinaµie liniar format din

el mult 2m ompa³i de de izie (ex. 64.a);

(P10) Ori e mulµime de instanµe distin te [³i eti hetate℄ din R este γ-slabînv µabil u ajutorul ompa³ilor de de izie (ex. 62).

• Alte metode de înv µare ansamblist bazate pe arbori de de izie: Bagging,

Random Forests;

• Alte metode de înv µare automat bazate pe arbori: arbori de regresie (CART).

4. Clasi� are bayesian

− probabilit µi ³i probabilit µi ondiµionate;

− formula lui Bayes: ex. 5.b;

ap. Fundamente, ex. 6, ex. 7, ex. 65, ex. 66;

− independenµa [ ondiµional a℄ evenimentelor aleatoare:

ap. Fundamente, ex. 4, ex. 62, ex. 63;

− independenµa [ ondiµional a℄ variabilelor aleatoare: ex. 9, ex. 10, ex. 12,

ex. 28-35; vedeµi ³i ap. Fundamente, ex. 15, ex. 24, ex. 70.b, ex. 79, ex. 86;

− distribuµii probabiliste orelate, marginale ³i ondiµionale: ex. 8, ex. 10, ex. 12,

ex. 28; vedeµi ³i ap. Fundamente, ex. 13, ex. 14;

− distribuµia gaussian : de la ap. Fundamente, ex. 26, ex. 27 (pentru azul

univariat), ex. 88 (pentru azul bivariat), ex. 18, ex. 28, ex. 29, ex. 30 (pentru

azul multivariat);

− estimarea parametrilor pentru distribuµii de tip Bernoulli, ategorial ³i gaus-

sian (ultimul doar pentru azul lasi� rii bayesiene de tip gaussian);

− ipoteze MAP vs. ipoteze ML:

formulare [ a soluµii la℄ probleme de optimizare:

ex. 22;

exempli� are: ex. 1, ex. 2, ex. 3, ex. 21, ex. 34;

exempli� are în azul arborilor de de izie: ex. 4;

− regresia logisti , hestiuni introdu tive:

de la ap. Estimarea parametrilor;

metode de regresie, ex. 23.

Algoritmi de lasi� are bayesian

− Algoritmul Bayes Naiv ³i algoritmul Bayes Corelat:

formulare a probleme de optimizare / estimare în sens MAP: artea ML,

pag. 167;

pseudo- od: vedeµi slide-uri;

exemple de apli are: ex. 5, ex. 7, ex. 8, ex. 9, ex. 23, ex. 24, ex. 25;

− apli area / adaptarea algoritmului Bayes Naiv pentru lasi� are de texte:

ex. 6, ex. 26;

folosirea regulii �add-one� [a lui Lapla e℄ pentru �netezirea� parametrilor:

ex. 6, ex. 27;

De la ap. Estimarea parametrilor; metode de regresie, pentru estimarea parametrului unei distribuµii Ber-

noulli vedeµi ex. 1 ³i ex. 29.a, pentru estimarea parametrilor unei distribuµii ategoriale vedeµi ex. 31, iar pentru

estimarea parametrilor unei distribuµii gaussiene vedeµi ex. 7, ex. 38, ex. 8, ex. 39 (pentru azul univariat) ³i

ex. 10 (pentru azul multivariat).

Vedeµi artea ML, pag. 156-157.

Vedeµi draftul apitolului suplimentar pentru artea ML a lui T. Mit hell, Generative and dis riminative

lassi�ers: Naive Bayes and logisti regression (în spe ial se µiunea 3).

La se µiunea a easta, pre um ³i la urm toarea se µiune, onsider m (impli it) toate variabilele de intrare

sunt de tip Bernoulli sau, mai general, de tip ategorial. Dup a eea vom onsidera ³i variabile de intrare de tip

ontinuu, în genere de tip gaussian. Variabila de ie³ire se onsider întotdeauna de tip Bernoulli / ategorial.

Atenµie: Noi am folosit ai i versiunea de baz a algoritmului Bayes Naiv; varianta �bag of words� (vedeµi

artea Ma hine Learning a lui Tom Mit hell, pag. 183) difer u³or de a easta.

− al ulul ratei medii a erorilor pentru algoritmii Bayes Naiv ³i Bayes Corelat:

ex. 10, ex. 11, ex. 28, ex. 29, ex. 30, ex. 31, ex. 35;

− evidenµierea gra� a ne on ordanµei predi µiilor f ute de lasi� atorii Bayes

Naiv ³i Bayes Corelat: ex. 12.

Propriet µi ale algoritmilor Bayes Naiv ³i Bayes Corelat

− (P0) da proprietatea de independenµ ondiµional a atributelor de intrare

în raport u variabila de ie³ire se veri� , atun i rezultatele produse de tre

ei doi algoritmi (Bayes Naiv ³i Bayes Corelat) în faza de testare oin id;

− (P1) num rul de parametri ne esari de estimat din date: liniar pentru Bayes

Naiv (2d+1) ³i exponenµial pentru Bayes Corelat (2d+1− 1): ex. 7.e, ex. 25.ab,ex. 30;

− (P2) omplexitatea algoritmului Bayes Naiv:

omplexitatea de spaµiu: O(dn)

omplexitatea de timp:

la antrenare: O(dn)la testare: O(d′),

unde n este num rul de exemple, iar d este num rul de atribute de intrare

[LC: d′ este num rul de atribute de intrare din instanµa de test];

− (P3) algoritmul Bayes Corelat poate produ e eroare [la lasi� are℄ din auza

faptului ia de izia în sensul unui vot majoritar. Algoritmul Bayes Naiv are

³i el a east �surs � de eroare; în plus el poate produ e eroare ³i din auza

faptului lu reaz u presupoziµia de independenµ ondiµional ( are nu

este satisf ut în mod neap rat);

− (P4) a urateµea [la lasi� are a℄ algoritmului Bayes Naiv s ade atun i ând

unul sau mai multe atribute de intrare sunt dupli ate: ex. 10.d, ex. 28.def;

− (P5) în azul �înv µ rii� unei fun µii booleene (oare are), rata medie a erorii

produse la antrenare de tre algoritmul Bayes Corelat (spre deosebire de

Bayes Naiv!) este 0: ex. 30.d;

− (P6) omplexitatea de e³antionare: de ordin logaritmi pentru Bayes Naiv ³i

de ordin exponenµial pentru Bayes Corelat: ex. 13;

− (P7) orespondenµa dintre regula de de izie a algoritmului Bayes Naiv ( ând

toate variabilele de intrare sunt de tip Bernoulli) ³i regula de de izie a regresiei

logisti e ³i, în onse inµ , liniaritatea graniµelor de de izie: ex. 14.

− omparaµii între algoritmul Bayes Naiv ³i alµi algoritmi de lasi� are auto-

mat : ex. 33, ex. 35.

Algoritmii Bayes Naiv ³i Bayes Corelat

u variabile de intrare de tip gaussian

• Apli are: G[N℄B: ex. 15, ex. 36, ex. 40;12 GJB: ex. 37; GNB vs GJB: ex. 16.

• Propriet µi:

Vedeµi ³i ex. 38 de la ap. Estimarea parametrilor; metode de regresie.

− (P0

′) presupunem variabila de ie³ire este boolean , i.e. ia valorile 0 sau 1;

da pentru ori e atribut de intrare, variabilele ondiµionale Xi|Y = 0 ³i

Xi|Y = 1 au distribuµii gaussiene de varianµe egale (σi0 = σi1), atun i regula

de de izie GNB (Gaussian Naive Bayes) este e hivalent ( a form ) u ea a

regresiei logisti e, de i separarea realizat de tre algoritmul GNB este de

form liniar : ex. 17, ex. 36.a;

− (P1

′) similar, presupunem variabila de ie³ire este boolean ;

da variabilele de intrare (notaµie: X = (X1, . . . , Xd)) au distribuµiile [ orelate℄

ondiµionale X |Y = 0 ³i X |Y = 1 de tip gaussian [multivariat℄, u matri ele de

ovarianµ egale (Σ0 = Σ1), atun i regula de de izie a algoritmului �full� / Joint

Gaussian Bayes este ³i ea e hivalent ( a form ) u ea a regresiei logisti e,

de i separarea realizat este tot de form liniar : ex. 18;

− (P2

′) ând variabilele de intrare satisfa ondiµii mixte de tip (P0

′) sau (P7),

atun i on luzia � separare liniar � se menµine: ex. 39.b;

− (P3

′) da în ondiµiile de la propoziµiile (P0

′)-(P2

′) presupoziµia de indepen-

denµ ondiµional este satisf ut , iar num rul de instanµe de antrenament

tinde la in�nit, atun i rezultatul de lasi� are obµinut de tre algoritmul Ba-

yes Naiv gaussian este identi u el al regresiei logisti e: ex. 19.a.

Atun i ând presupoziµia de independenµ ondiµional nu este satisf ut ,

iar num rul de instanµe de antrenament tinde la in�nit, regresia logisti se

omport mai bine de ât algoritmul Bayes Naiv [gaussian℄: ex. 19.b;

− (P4

′) nu exist o orespondenµ 1-la-1 între parametrii al ulaµi de regre-

sia logisti ³i între parametrii al ulaµi de algoritmul Bayes Naiv [gaussian℄:

ex. 20.a;

− (P5

′) atun i ând varianµele distribuµiilor gaussiene are orespund probabili-

t µilor ondiµionale P (Xi|Y = k) depind ³i de eti heta k, separatorul de izionaldeterminat de algoritmul Bayes Naiv gaussian nu mai are forma regresiei lo-

gisti e: ex. 38 (similar, pentru algoritmul Bayes Corelat gaussian, atun i ând

Σ0 6= Σ1: ex 37);

− (P6

′) parametrii algoritmului Bayes Corelat gaussian se pot estima în timp

liniar în raport u num rul de instanµe din setul de date de antrenament:

ex. 20.b.

5. Înv µare bazat pe memorare

− m suri de distanµ , m suri de similaritate: ex. 2;

− norm într-un spaµiu ve torial; [m sura de℄ distanµ indus de tre o norm :

ex. 7;

− k-NN ve in tate a unui pun t din Rd.

Algoritmul k-NN

− pseudo- od: artea ML, pag. 232;

− bias-ul indu tiv: �Cine se aseam n se adun � (sau: �Spune-mi u ine te

împrietene³ti, a s -µi spun ine e³ti�): ex. 15.a;

− exemple (simple) de apli are: ex. 1, ex. 2, ex. 15.b-d;

− omplexitate de spaµiu: O(dn) omplexitate de timp:

la antrenare: O(dn)

la testare: O(dn logn)

la testare: [LC: O(dn k log k) pt. k > 1 (worst ase) ³i O(dn) pt. k = 1 ],

unde d este num rul de atribute, iar n este num rul de exemple;

− arbori kd (engl., kd-trees): Statisti al Pattern Re ognition, Andrew R. Webb,

3rd ed., 2011, Willey, pag. 163-173;

− k-NN a algoritm ML �lazy� (vs. �eager�):

suprafeµe de de izie ³i graniµe de de izie:

diagrame Voronoi pentru 1-NN: ex. 4, ex. 11.a, ex. 18, ex. 19, ex. 20.a;

− analiza erorilor:

• 1-NN pe date onsistente: eroarea la antrenare este 0: ex. 2, ex. 12.a;

• variaµia num rului de erori (la antrenare ³i respe tiv testare) în fun µie

de valorile lui k: ex. 22, ex. 23.ab;k-NN a metod neparametri ; alegerea lui k: CV: ex. 23. ;

• CVLOO: ex. 3, ex. 12.b, ex. 16, ex. 24.a, ex. 20.b;

• sensibilitatea / robusteµea la �zgomote�: ex. 5, ex. 15;

• eroarea asimptoti : ex. 10, ex. 25.

− efe tul tr s turilor redundante sau irelevante;

− alegerea valorii onvenabile pentru k: ex. 21.

Propriet µi ale algoritmului k-NN

• (P0) output-ul algoritmului k-NN pentru o instanµ oare are de test xq de-

pinde de valoarea lui k: ex. 1;

• (P1) pe seturi de date de antrenament onsistente, eroarea la antrenare pro-

dus de algoritmul 1-NN este 0: ex. 2, ex. 12.a;

• (P2) output-ul algoritmului k-NN, pre um ³i suprafeµele de de izie ³i separa-

torii de izionali depind de m sura de distanµ folosit : ex. 7;

• (P3) �blestemul marilor dimensiuni� (engl., the urse of dimensionality): în

anumite ondiµii, num rul de instanµe de antrenament ne esare pentru a avea

un el mai apropiat ve in situat la distanµ rezonabil faµ de instanµa de test

xq re³te exponenµial în fun µie de num rul de atribute folosite: ex. 9;

• (P4) în anumite ondiµii, rata medie a erorii asimptoti e a algoritmului 1-NN este m rginit superior de dublul ratei medii a erorii algoritmului Bayes

Corelat: ex. 10, ex. 25.

Comparaµii u alµi algoritmi de lasi� are automat

− ID3: ex.11.b, ex. 13.ab;

− SVM: ex.12, ex. 13. , ex. 24.b;

− regresia logisti : ex. 24.b;

− 1-NN u mapare u RBF: ex. 14.

Variante ale algoritmului k-NN

− k-NN folosind alte m suri de distanµ (de ât distanµa eu lidian ): ex. 7;

− k-NN u ponderarea distanµelor (engl., distan e-weighted k-NN): artea ML, pag. 236-238 (formulele 8.2, 8.3, 8.4);

− algoritmul lui Shepard: ex.8.

Alte metode de tip IBL

− reµele RBF: artea ML, pag. 238-240;

− raµionare bazat pe azuri (engl., ase-based reasoning): artea ML, pag. 240-

Se tiunea 8.3 din artea ML (pag. 236-238) se refer la regresia [liniar ℄ lo al-ponderat a o form mai

general de aproximare a [valorilor℄ fun µiilor, în raport u ele al ulate de tre algoritmul k-NN atun i ând

se folose³te ponderarea distanµelor.

6. Clusterizare

6.0 Noµiuni de baz

− instanµ neeti hetat vs. instanµ eti hetat (exemplu de antrenament);

− înv µare nesupervizat ( lusterizare) vs. înv µare supervizat ( lasi� are);

− [fun µie / m sur de] distanµ de�nit pe Rd×Rd

: ex. 2 de la apitolul Înv µare

bazat pe memorare;

− luster / grup / grupare / bin (engl.) vs. las ;

− tipuri de lusterizare: ierarhi vs. neierarhi ;

− tipuri de ierarhii: ierarhii (arbori de lusterizare, dendrograme) obi³nuite vs.

ierarhii plate (engl., �at hierar hies);

exemple: ex. 1.a ³i respe tiv ex. 1.b, ex. 6.a;

− tipuri de apartenenµ a unei instanµe la un luster: hard vs. soft (ultima numai

pt. lusterizare neierarhi ).

6.1. Clusterizare ierarhi

6.1.1. Noµiuni spe i� e

− [fun µie de] similaritate între lustere, de�nit pe baza [extinderii℄ noµiunii de

distanµ la P(X)×P(X), unde X ⊂ Rdeste mulµimea de instanµe, iar P(X) este

mulµimea p rµilor lui X;

tipuri de [fun µii de] similaritate:

�single-linkage�:

14 d(A,B) = min{d(x, y)|x ∈ A, y ∈ B}

� omplete-linkage�:

15 d(A,B) = max{d(x, y)|x ∈ A, y ∈ B}

�average-linkage�: d(A,B) =1

|A| |B|

x∈A,y∈B d(x, y)

metri a lui Ward : ex. 30, 31.

În general, putem onsidera sim(A,B) = 1/(1 + d(A,B)) sau hiar sim(A,B) =1/d(A,B) ând ne referim doar la lustere non-singleton;

proprietate / restri µie: sim(A ∪ B,C) ≤ min{sim(A,C), sim(B,C)} pentru ori e

lustere A,B sele tate de algoritmul de lusterizare ierarhi la un pas oare are

[al algoritmului de lusterizare ierarhi ℄ ³i ori e alt luster C;

− [fun µie de] oeziune [intern ℄ a unui luster (sau: între elementele / instanµele

dintr-un luster);

exemplu (pentru lustere non-singleton):

oh(A) =

x,y∈A d(x, y)

x,y∈A d(x, y).

Sau: nearest-neighbour.

Sau: furthest-neighbour.

6.1.2. Algoritmi de lusterizare ierarhi

− tipuri de algoritmi de lusterizare ierarhi :

bottom-up ( lusterizare aglomerativ ) vs. top-down ( lusterizare diviziv );

− pseudo- od: Manning & S hütze, Foundations of Statisti al Natural Language

Pro essing, 2002, pag. 502;

− analiza ( a algoritmi per se): ambii algoritmi sunt iterativi ³i �greedy�; rezul-

tatele (ierarhiile) obµinute nu sunt determinate neap rat în mod uni : ex. 3.b;

− exemple de apli are: ex. 1-5, ex. 25-29 (pentru bottom-up), respe tiv ex. 6

(pentru top-down);

− implement ri: ex. 33, ex. 31, ex. 34.

6.1.3 Propriet µi

− (P0) lusterizarea folosind similaritate de tip �single-linkage� are tendinµa s

reeze lustere alungite; invers, folosind similaritate � omplete-linkage� sau

�average-linkage�, se formeaz lustere de form mai degrab sferi : ex. 5 ³i

ex. 28;

− (P1) num rul maxim de niveluri dintr-o dendrogram (v zut a arbore în

sensul teoriei grafurilor) este n− 1, unde n este num rul de instanµe de lus-

terizat: ex. 4.a; num rul minim de niveluri: ⌈log2 n⌉; ex. 4.b;

− (P2) exist o anumit orespondenµ între lusterizare ierarhi u similaritate

de tip

• �single-linkage� ³i a�area arborelui [de a operire] de ost minim dintr-un

graf: ex. 6;

• � omplete-linkage� ³i a�area unei li i (subgraf maximal omplet) dintr-un

graf (vedeµi Manning & S hütze, op. it., pag. 506-507);

− (P3) algoritmul de lusterizare aglomerativ la al rui pseudo- od am f ut

referire mai sus are omplexitate O(n3): ex. 25; atun i ând se folose³te single-

linkage sau omplete-linkage, exist îns versiuni / algoritmi de omplexitate

O(n2): SLINK (1973) ³i respe tiv CLINK (1976);

− la lusterizare ierarhi aglomerativ u similaritate �average-linkage�:

(P4) da se folose³te a m sur de similaritate între 2 instanµe osinusul

unghiului dintre ve torii are reprezint instanµele ³i se �normalizeaz � a e³ti

ve tori (i.e., se lu reaz u 2 ve tori oliniari u ei, dar de norm egal u 1),atun i al ulul oeziunii [interne a℄ unui luster nou format, pre um ³i al ulul

�distanµei� dintre dou lustere se pot fa e în timp onstant: ex. 32.

6.2. Clusterizare neierarhi ,

folosind asignare �hard� a instanµelor la lustere

6.2.1 Noµiuni spe i� e

− entroid ( entru de greutate) al unui luster,

K-partiµie, K- on�guraµie [iniµial ℄ a entroizilor: ex. 11;

− o fun µie de evaluare a � alit µii� lusterelor (sau: fun µie de � oeziune� /

�distorsiune� / �eroare� total ):

�suma elor mai mi i p trate�: JK(C, µ) =∑

‖xi − µC(xi)‖2, unde C este K-

partiµie, µ este K- on�guraµie de entroizi, iar µC(xi) este entroidul el mai

apropiat de xi: ex. 12.

6.2.2 Algoritmul K-means

− pseudo- od (o versiune [mai℄ general ): Manning & S hütze, op. it., pag. 516;

alternativ, vedeµi enunµul ex. 12 (sau, e hivalent, folosind variabile-indi ator:

ex. 39);

exemple de apli are: ex. 7-11, ex. 15.a, ex.19.a, ex. 20.a, ex. 35, ex. 36.

− exemple de euristi i pentru iniµializarea entroizilor :

iniµializare arbitrar / random în Rdsau în X = {x1, x2, . . . , xn} ⊆ R

d(setul de

date de lusterizat);

apli are în prealabil a unui algoritm de lusterizare ierarhi ;

folosind o anumit distribuµie probabilist de�nit pe X: K-means++ (David

Arthur, Sergei Vassilvitskii, 2007): ex. 43.

− exemple de riterii de oprire:

dup efe tuarea unui num r maxim de iteraµii (�xat iniµial);

ând omponenµa lusterelor nu se mai modi� de la o iteraµie la alta;

ând poziµiile entroizilor nu se mai modi� de la o iteraµie la alta;

ând des re³terea valorii riteriului JK de la o iteraµie la alta nu mai este

stri t sau nu mai este peste un anumit prag ε �xat în prealabil.

− a algoritm per se:

K-means este un algoritm de utare:

spaµiul de utare este mulµimea tuturor K-partiµiilor are se pot forma pe

dataset-ul de intrare;

(P0) întru ât a est spaµiu de utare (de³i este �nit) este exponenµial (Kn),

K-means exploreaz doar parµial spaµiul de utare, pro edând iterativ: el

plea de la o �soluµie� (K-partiµie) aleas eventual în mod arbitrar / aleato-

riu ³i o �îmbun t µe³te� la �e are iteraµie;

(P1) soluµia g sit este dependent de iniµializarea entroizilor: ex. 10;

′) mai mult, hiar la o a eea³i iniµializare, rezultatele pot diferi(!) da

avem instanµe multiple / redundante, situate la egal distanµ de 2 entroizi

la o iteraµie oare are: ex. 12.b;

′′) rezultatele lui K-means sunt dependente [³i℄ de m sura de distanµ fo-

losit : ex. 42.

K-means poate � v zut ³i a algoritm de optimizare � vedeµi riteriul JK de

mai sus;

(P2) strategia de utare / optimizare folosit de K-means este de tipul

des re³tere pe oordonate (engl., oordinate des ent), i.e. des re³tere itera-

tiv , mergând alternativ pe �e are din ele dou oordonate ale riteriului

JK(Ct, µt): ex. 12.a;(P2

′) algoritmul K-means nu garanteaz atingerea optimului global (i.e., mi-

nimul) riteriului JK : ex. 12.b, ex. 40.b.

− a algoritm de înv µare automat :

[urmat de] �generalizare�: o instanµ nou x se aso iaz lusterului având

entroidul el mai apropiat de x;(P3) �graniµele� de separare dintre [pere hile de℄ lustere produse de K-means

sunt [doar℄ liniare, [ el puµin℄ atun i ând se folose³te distanµa eu lidian :

ex. 11.b;

′) este îns posibil s se obµin separatori neliniari da se folose³te o

versiune �kernelizat � a algoritmului K-means: ex. 44;

(P4) rezultatele lui K-means pot � in�uenµate de prezenµa outlier-elor: ex. 10.

− hestiunea alegerii unei valori onvenabile / �naturale� pentru K (pentru un

dataset dat): ex. 38 (³i CMU, 2012f, E. Xing, A. Singh, HW3, ex. 1.de).

− adaptarea algoritmului K-means pentru azul în are în lo ul distanµei eu li-

diene se folose³te distanµa Manhattan: ex. 42;

− implementare: ex. 47.

6.2.3 Alte propriet µi ale algoritmului K-means

− în leg tur u riteriul de�nit mai sus, JK : PK × (Rd)K ← [0,+∞), unde

PK este mulµimea tuturor K-partiµiilor peste mulµimea de instanµe, X ={x1, x2, . . . , xn} ⊆ R

◦ (P5) pentru K > 0 �xat, |PK | = Kn, de i este �nit, ³i exist JK

= minC JK(C,µC);a est minimum (JK) se poate obµine prin explorarea exhaustiv a spaµiului

PK, îns onsumul de timp este prohibitiv în pra ti : ex. 12.b;

◦ (P6) valoarea 0 pentru J este atins , ³i anume atun i ând K = n, C este K-

partiµia de lustere singleton Ci = {xi}, iar µi = xi, pentru i = 1, . . . , n (ex. 38);

◦ (P7) J1 ≥ J2 ≥ . . . ≥ Jn−1 ≥ Jn = 0: ex. 13.

− (P8) da d = 1, de i x1, x2, . . . , xn ∈ R,

◦ ori e K-partiµie (C1, . . . , CK) pentru are se atinge JK este de forma unei

ole µii de �intervale�: C1 = {x1, . . . , xi1}, C2 = {xi1+1, . . . , xi2}, . . ., CK = {xiK−1+1,

. . ., xn}, u i1 < i2 < . . . < iK−1 < iK = n;◦ exist un algoritm [de programare dinami ℄ de omplexitate O(Kn2) are al uleaz JK : ex. 40.

− în leg tur u JK ³i algoritmul K-means:

◦ (P9) JK(Ct−1, µt−1) ≥ JK(Ct, µt) la ori e iteraµie (t > 0) a algoritmului K-

means: ex. 12.a;

◦ (P9′) în onse inµ , da se impune restri µia a la �e are iteraµie inegalita-

tea de mai sus s �e satisf ut în varianta stri t (JK(Ct−1, µt−1) > JK(Ct, µt)),atun i algoritmul K-means termin într-un num r �nit de pa³i;

◦ (P10) în vreme e minimizeaz oeziunea intra- lustere, i.e. o variant pon-

derat a �sumelor elor mai mi i p trate� al ulate pe lustere,

i=1 γik∑n

i=1 γik

‖xi − µk‖2,

unde γik = 1 da xi aparµine lusterului de entroid µk ³i γik = 0 în az ontrar,

algoritmul K-means maximizeaz (în mod aproximativ!) o sum ponderat a

distanµelor dintre lustere:

i=1 γikn

‖µk − x‖2,

unde x este media instanµelor x1, x2, . . . , xn (ex. 39).

6.3. Clusterizare neierarhi ,

folosind asignare �soft� a instanµelor la lustere

6.3.1 Noµiuni preliminare

− variabile aleatoare (dis rete, resp. ontinue);

media, varianµa ³i o-varianµa variabilelor aleatoare;

− ve tor de variabile aleatoare; matri e de ovarianµ pentru un astfel de ve tor;

propriet µi: matri ea de ovarianµ trebuie s �e în mod ne esar simetri ³i

pozitiv de�nit : ex. 18 de la apitolul de Fundamente;

− distribuµie (fun µie de densitate) de probabilitate (p.d.f.);

parametri ai unei distribuµii de probabilitate;

distribuµia gaussian : azurile uni- ³i multivariat;

− mixtur de distribuµii probabiliste:

v zut a o form parti ular de ombinaµie liniar de distribuµii de probabi-

litate π1Ψ1 + π2Ψ2 + . . .+ πkΨk ( u πi ≥ 0 ³i∑k

i=1 πi = 1),de�nit [³i mai spe i� ℄ s riind distribuµia P (X) a o sum ponderat de pro-

babilit µi ondiµionate:

z P (X |Z)P (Z), unde X sunt variabilele �observabile�,

iar variabila Z (eventual multipl ) poate � �neobservabil � / �latent � / �as-

uns �;

exemple: o mixtur de distribuµii ategoriale, respe tiv o mixtur de distri-

buµii Bernoulli: ex. 23 ³i ex. 85 de la apitolul de Fundamente; o mixtur

de distribuµii gaussiene multivariate: ex. 89 de la apitolul de Fundamente; o

mixtur de distribuµii oare are: ex. 90 de la apitolul de Fundamente;

− fun µie de verosimiliate a unui set de date (D), în raport u o distribuµie pro-

babilist dat : L(θ) = P (D|θ), unde prin θ se noteaz parametrii respe tivei

distribuµii. Exempli� are: ex. 1.abd, ex. 2 de la apitolul Estimarea parame-

trilor; metode de regresie;

− MLE (Maximum Likelihood Estimation): estimarea [valorilor℄ parametrilor

unei distribuµii probabiliste în sensul maximiz rii verosimilit µii datelor dis-

ponibile. Exempli� are: apitolul Estimarea parametrilor; metode de regre-

sie, ex. 1-11, ex. 29-40. Apli are în azul distribuµiei gaussiene univariate:

ex. 15.ab de la apitolul Clasi� are bayesian ;

− analiza dis riminativ gaussian : ex. 38 de la apitolul Estimarea parametrilor;

metode de regresie;

− Observaµie: Algoritmul EM este [sau, mai degrab , poate � folosit a℄ o me-

tod de estimare a parametrilor unei mixturi de distribuµii probabiliste. Al-

ternativ, pentru a ela³i obie tiv pot � folosite alte metode, de exemplumetoda

gradientului as endent: ex. 59.

6.3.2 Algoritmul EM pentru lusterizare

prin estimarea parametrilor unui

model de mixturi de distribuµii gaussiene (EM/GMM)

− pseudo- od:

azul unidimensional, varianta ând doar parametrul µ este l sat liber: ex. 48

( f. Ma hine Learning, Tom Mit hell, 1997, pag. 193); apli are: ex. 15.b,

ex. 16;

azul unidimensional, varianta ând toµi parametrii (π, µ ³i σ) sunt l saµi liberi:ex. 17 (apli are: ex. 15. );

alte variante: ex. 49, ex. 50, ex. 51;

azul multidimensional, varianta ând toµi parametrii (π, µ ³i Σ) sunt l saµiliberi: ex. 23; alte variante: ex. 52, ex. 54;

apli area algoritmului EM/GMM, azul bivariat: ex. 19.b, ex. 20.b, ex. 21,

ex. 22, ex. 55, ex. 56, ex. 57;

− s hema algoritmi EM: vedeµi Tom Mit hell, Ma hine Learning book, 1997,

pag. 194-195;

− a algoritm de înv µare statisti :

algoritmul EM poate � v zut a o metod de estimare a parametrilor (engl.,

parameter �tting);

− a algoritm per se:

◦ algoritm iterativ : plea de la o soluµie (instanµiere pentru parametri) aleas

eventual în mod arbitrar / aleatoriu ³i o �îmbun t µe³te� la �e are iteraµie.

Soluµia g sit este dependent de valorile iniµiale ale parametrilor;

◦ algoritm de optimizare:

în esenµ / rezumat, metoda de maximizare a fun µiei de log-verosimilitate

a datelor observabile logP (X |θ) este maximizarea la �e are iteraµie t a unei

fun µii auxiliare Qt, are onstituie o margine inferioar a lui logP (X |θ), ³ianume media fun µiei de log-verosimilitate a datelor omplete în raport u

distribuµia de probabilitate a variabilelor neobservabile la iteraµia t;

a³adar, la �e are iteraµie t se al uleaz fun µia �auxiliar � Qt(θ|θ(t)), are

reprezint media fun µiei de log-verosimilitate a datelor � omplete� ( ele �ob-

servabile� plus ele �neobservabile�), unde θ(0), onstând din valorile iniµi-

ale ale parametrilor mixturii (θ), se alege în mod arbitrar, iar apoi θ(t+1) =argmaxθ Qt(θ|θ

(t));media reprezentat de fun µia Qt se al uleaz în fun µie de distribuµiile on-

diµionale ale variabilelor �neobservabile� Z în raport u datele observabile X³i u θ(t);

(P0) Se poate demonstra fun µia Qt onstituie o margine inferioar pentru

fun µia de log-verosimilitate a variabilelor �observabile�, logP (X |θ): ex. 1 de

la apitolul Algoritmul EM ;

(P1) Teorema de ore titudine (vedeµi ex. 1 ³i în spe ial ex. 2 de la apitolul

Algoritmul EM ) pe de o parte garanteaz faptul la �e are iteraµie a algorit-

mului EM, log-verosimilitatea datelor �observabile�, logP (X |θ(t)) nu des re³te

( i �e re³te, �e r mâne nes himbat ),

dar pe de alt parte nu garanteaz g sirea optimului global al fun µiei de

log-verosimilitate a datelor �observabile�, logP (X |θ), i eventual a unui optim

lo al;

− a algoritm de înv µare automat :

algoritmul EM este o metod de identi� are / înv µare de ipoteze ML (Ma-

ximum Likelihood); vedeµi apitolul / se µiunea 6.4 din artea Ma hine Lear-

ning ;

înv µare în prezenµa unor variabile aleatoare neobservabile(!);

[urmat eventual de] �generalizare�: o instanµ nou x se aso iaz lusterului

(i.e., distribuµiei) j pentru are se atinge maxj′ P (X = x|hj′ )P (hj′ );

(P2) Rezultatele algoritmului EM depind ( a ³i la K-means) de valorile atri-

buite parametrilor la iniµializare (ex. 15. ).

(P3) Anumite valori atribuite iniµial parametrilor algoritmului EM pot pro-

vo a rularea la in�nit a algoritmului, f r a [la pasul M℄ valorile parametrilor

s se modi� e de la o iteraµie la alta: ex. 18. ;

(P4) Spre deosebire de azul algoritmului K-means, suprafeµele / graniµele

de separare reate de algoritmul EM/GMM nu sunt în mod neap rat liniare

(vedeµi de exemplu situaµiile întâlnite la rezolvarea ex. 15. , pag. 556, sau la

ex. 57. ³i ex. 58. ).

− (P5) Comparativ u algoritmul K-means, algoritmul EM/GMM este în ge-

neral mai lent � mi³ area entroizilor poate explora într-o manier mai �n

spaµiul (vedeµi de exemplu ex. 19) �, iar din a est motiv el poate s obµin

uneori rezultate mai bune / onvenabile (vedeµi spre exemplu ex. 20);

EM/GMM este mai robust la in�uenµa outlier-elor;

(P6) Apare un fenomen de �atra µie� re ipro a mediilor gaussienelor (a este

medii �ind e hivalentul entroizilor din algoritmul K-means), datorit faptu-

lui �e are instanµ aparµine ( u o anumit probabilitate) la �e are luster.

Atra µia mediilor este u atât mai puterni u ât varianµele sunt mai mari.

(Vedeµi spre exemplu ex. 15.b.)

6.3.3 Alte propriet µi ale algoritmului EM/GMM

− Pentru distribuµii gaussiene multivariate:

◦ (P7) în azul el mai general (de i ând matri ea Σ nu este neap rat diago-

nal ), datele generate de a est tip de distribuµie se grupeaz în elipse ( orpuri

elipsoidale) u axele de simetrie [desigur, perpendi ulare, dar altfel℄ nerestri -

µionate.

◦ (P7′) da matri ea de ovarianµ Σ este diagonal , atun i distribuµia ga-

ussian respe tiv este e hivalent u un set / ve tor de variabile gaussiene

univariate independente: ex. 28 de la apitolul de Fundamente;

◦ (P7′′) da matri ea Σ este de forma σ2I, unde I este matri ea identitate,

datele generate de respe tiva distribuµie tind s se grupeze în sfere;

◦ (P7′′′) da matri ea Σ este diagonal (f r ni io alt restri µie), datele ge-

nerate se grupeaz în elipse (sau: orpuri elipsoidale) având axele de simetrie

paralele u axele sistemului de oordonate;

− (P8) Leg tura dintre algoritmul K-means ³i algoritmul EM/GMM ( azul mul-

tivariat):

atun i ând Σ = σ2I, iar σ2 → 0 (³i sunt satisf ute în dou restri µii), algo-

ritmul EM/GMM tinde s se omporte a ³i algoritmul K-means: ex. 54;

− O leg tur interesant între algoritmul EM/GMM ³i metoda gradientului as-

endent, în azul în are matri ele de ovarianµ sunt de forma σ2k I: ex. 59;

− O leg tur interesant între lasi� atorul Bayes Naiv gaussian ³i algoritmul

EM/GMM în azul în are matri ele de ovarianµ sunt de forma σ2k I:

o variant semisupervizat a algoritmului EM/GMM: ex. 60.

− S hema algoritmi EM (vedeµi Tom Mit hell, Ma hine Learning book, 1997,

pag. 194-195) are diverse variante ³i apli aµii:

• al ulul parametrilor pentru mixturi de diverse distribuµii [nu doar gaus-

siene℄: vedeµi apitolul Algoritmul EM ;

• al ulul parametrilor pentru gramati i probabiliste independente de ontext

(engl., probabilisti ontext-free grammars, PCFG);

• al ulul parametrilor modelelor Markov as unse (engl., hidden Markov mo-

dels, HMM);

• al ulul parametrilor reµelelor bayesiene (engl., Bayes nets);

• al ulul parametrilor reµelelor de fun µii u baza radial (engl., radial basis

fun tions, RBF), o familie de reµele neuronale arti� iale; et .

− Propriet µi pentru s hema algoritmi EM:

vedeµi ele menµionate mai sus în leg tur u algoritmul EM v zut a algoritm

de optimizare.

7. Algoritmul EM

− estimarea parametrilor unei distribuµii probabiliste în sensul verosimilit µii

maxime (MLE) respe tiv în sensul probabilit µii maxime a posteriori (MAP):

vedeµi apitolul de Fundamente;

− tipuri / lase de distribuµii probabiliste: vedeµi apitolul de Fundamente;

− mixturi de distribuµii probabiliste: vedeµi apitolul de Fundamente ³i apitolul

de Clusterizare;

− metoda � oordinate as ent� pentru rezolvarea problemelor de optimizare: ex. 1;

− metoda multipli atorilor lui Lagrange pentru rezolvarea problemelor de opti-

mizare u restri µii: ex. 5, ex. 7 ³i ex. 15.

S hema algoritmi EM

− pseudo- od: Ma hine Learning, Tom Mit hell, 1997, pag. 194-195;

− fundamentare teoreti : ex. 1 � pentru fun µia F (q, θ), are reprezint o

margine inferioar a fun µiei de log-verosimilitate a datelor omplete, se fa e

maximizarea prin metoda reµerii pe oordonate (engl., oordinate as ent) �

³i ex. 2 (monotonia fun µiei de log-verosimilitate a datelor omplete);

− hestiuni metodologi e (relativ la iniµializarea parametrilor): ex. 22.

EM pentru modelarea de mixturi de distribuµii probabiliste

− varianta general : An Introdu tion to Expe tation-Maximization, Dahua Lin;

− diverse instanµe ale a estei �variante�:

mixturi de distribuµii Bernoulli : ex. 14 ³i ex. 4;

mixturi de distribuµii ategoriale: ex. 5 ³i ex. 15;

mixturi de distribuµii Poisson: ex. 18;

mixturi de distribuµii Gamma: ex. 19.

Alte instanµe / apli aµii ale s hemei algoritmi e EM

− EM pentru estimarea unui parametru [de tip probabilitate℄ pentru o distri-

buµie dis ret [în o urenµ , o distribuµie ategorial ℄, în ondiµiile existenµei

unei variabile �neobservabile�: ex. 3;

similar pentru distribuµia multinomial : ex. 13;

− EM pentru estimarea tuturor parametrilor unei distribuµii ategoriale: ex. 12;

− EM pentru estimarea parametrului unei distribuµii Poisson în ondiµiile în

are o parte din valorile date lipses : ex. 10;

Leg tura u fun µia auxiliar de la iteraµia t: Q(θ | θ(t)) = F (P (z | x, θ(t)), θ)︸︷︷︸

Gt(θ)

−H[P (z | x, θ(t))].

− EM pentru estimarea parametrilor a dou distribuµii probabiliste atun i ând

se dau instanµe are sunt generate de suma elor dou distribuµii:

distribuµii exponenµiale: ex. 8,

distribuµii gaussiene: ex. 20;

− algoritmul Bayes Naiv nesupervizat, i.e. algoritmul EM pentru [modelare℄ de

mixturi de distribuµii ategoriale multivariate, u presupunerea de indepen-

denµ ondiµional a atributelor de intrare în raport u atributul de ie³ire

(eti heta): ex. 7 (varianta de asignare �soft� a instanµelor la luster) ³i ex. 17

(varianta �hard�);

− EM pentru estimarea probabilit µii de sele µie a unei omponente din adrul

unei mixturi [i.e., ombinaµie liniar ℄ de dou distribuµii probabiliste oare are:

ex. 9;

− EM pentru modelul mixturii domeniilor semanti e (engl., topi model) pentru

lusterizare de do umente: [ex. 6 ³i℄ ex. 16;

− EM pentru estimarea [nu în sens MLE, um a fost azul pân ai i, i℄ în sens

MAP: ex. 20.

8. Reµele neuronale arti� iale

− fun µie matemati ; ompunere de fun µii reale;

al ulul valorii unei fun µii pentru anumite valori spe i� ate pentru argumen-

tele / variabilele ei;

− fun µie prag (sau, treapt ), fun µie liniar , fun µie sigmoidal (sau, logisti ),

fun µie sigmoidal generalizat ;

separabilitate liniar pentru o mulµime de pun te din Rd;

− e uaµii aso iate dreptelor în plan / planelor în spaµiu / hiper-planelor în spaµiul

e uaµia dreptei în plan are tre e prin dou pun te date;

semnele aso iate pun telor din semiplanele determinate de o dreapt dat în

− derivate ale fun µiilor elementare de variabil real ; derivate parµiale

− ve tori; operaµii u ve tori, în parti ular produsul s alar al ve torilor;

− metoda gradientului des endent ( a metoda de optimizare); avantaje ³i deza-

vantaje; ex. 54de la ap. Fundamente, ex. 22, ex. 34, ex. 35.

Câteva noµiuni spe i� e

− unit µi neuronale arti� iale (sau, neuroni arti� iali, per eptroni);

tipuri de neuroni arti� iali: neuroni-prag, liniari, sigmoidali;

omponente ale unui neuron arti� ial: input, omponenta de sumare, ompo-

nenta / fun µia de a tivare, output;

fun µia matemati reprezentat / al ulat de un neuron arti� ial;

− reµea neuronal arti� ial ; reµele de tip feed-forward;

niveluri / straturi de neuroni, niveluri as unse, niveluri de ie³ire;

ponderi aso iate onexiunilor dintr-o reµea neuronal arti� ial ;

fun µia matemati reprezentat / al ulat de o reµea neuronal arti� ial ;

graniµe ³i zone de de izie determinate de o reµea neuronal arti� ial ;

fun µia de eroare / ost (engl., loss fun tion).

Câteva propriet µi relative la expresivitatea

reµelelor neuronale arti� iale

− (P0) Toate ele trei tipuri de neuroni arti� iali (prag, liniar, sigmoidal) produ

separatori liniari.

Conse inµ : Con eptul xor nu poate � reprezentat / înv µat u astfel de

�dispozitive� simple de lasi� are.

− (P0

′) Reµelele neuronale arti� iale pot determina graniµe de de izie neliniare

(³i, în onse inµ , pot reprezenta on epte pre um xor).

Observaµie: Reµele de unit µi sigmoidale pot determina graniµe de de izie

urbilinii: ex. 8.

− (P1) Reµele de neuroni diferite ( a stru tur ³i / sau tipuri de unit µi) pot s

al uleze o a eea³i fun µie: ex. 3 ³i ex. 1. vs. ex. 2.

′) Dat o topologie de reµea neuronal (i.e., graf de unit µi neuronale al

ror tip este l sat nespe i� at), este posibil a plasând în noduri unit µi de

un anumit tip s putem reprezenta / al ula o anumit fun µie, iar s himbând

tipul unora dintre unit µi (sau al tuturor unit µilor), fun µia respe tiv s nu

mai pot � al ulat : ex. 4 vs. ex. 33.

− (P2) Ori e unitate liniar situat pe un nivel as uns poate � �absorbit � pe

nivelul urm tor: ex. 32.

− (P3) Ori e fun µie boolean poate � reprezentat u ajutorul unei reµele ne-

uronale arti� iale având doar dou niveluri de per eptroni-prag: ex. 5.

− (P4) Ori e fun µie de�nit pe un interval m rginit din R, are este ontinu

în sens Lips hitz, poate � aproximat ori ât de bine u ajutorul unei reµele

neuronale are are un singur nivel as uns: ex. 7.

Algoritmi de antrenare a neuronilor arti� iali

folosind metoda gradientului des endent

− algoritmul de antrenare a unit µii liniare: ex. 36;

vedeµi T. Mit hell,Ma hine Learning, p. 93, justi� are: p. 91-92; onvergenµa:

p. 95; exemplu de apli are: ex. 10;

varianta in remental a algoritmului de antrenare a unit µii liniare: artea

ML, p. 93-94; despre onvergenµa a estei variante ( a aproximare a variantei

pre edente (�bat h�): artea ML, p. 93 jos;

− algoritmul de antrenare a per eptronului-prag ³i onvergenµa: artea ML, p.

88-89; exemplu de apli are: ex. 11;

− algoritmul de antrenare a per eptronului sigmoidal ³i justi� area sa teoreti :

artea ML, p. 95-97;

− algoritmul Per eptron al lui Rosenblatt; exemplu de apli are: ex. 16, ex. 38;

− dedu erea regulii de a tualizare a ponderilor pentru tipuri parti ulare de per-

eptroni: ex. 12, ex. 24.a, ex. 37, ex. 13.a;

− o justi� are probabilist (gen ipotez de tip maximum likelihood) pentru mi-

nimizarea sumei p tratelor erorilor [la dedu erea regulii de antrenare℄ pentru

per eptronul liniar: ex. 13.b;

− exemple de [folosire a unei℄ alte fun µii de ost / pierdere / penalizare (engl.,

loss fun tion) de ât semisuma p tratelor erorilor: suma osturilor de tip log-

sigmoidal, ex. 14 (pentru per eptronul liniar), o fun µie de tip ross-entropie,

ex. 15 (pentru per eptronul sigmoidal).

Per eptronul Rosenblatt ³i rezultate de onvergenµ

− exemplu de apli are [adi , înv µare u per eptronul Rosenblatt℄: ex. 16.

− âteva propriet µi simple ale per eptronului Rosenblatt: ex. 17.

Problemele 1.d ³i ex. 31 au în vedere o hestiune similar , îns pentru reµele u topologii diferite: o anumit

extensie a fun µiei xor nu poate � reprezentat pe reµele de neuroni-prag are au un singur nivel as uns.

− rezultate de onvergenµ de tip �mistake bound� pentru [algoritmul de antre-

nare pentru℄ per eptronul-prag [în varianta℄ Rosenblatt: ex. 18, ex. 39;

pentru per eptronul-prag ( lasi ): ex. 41;

înv µare online u per eptronul-prag de tip Rosenblatt: ex. 40;

− Per eptronul kernel-izat [dual℄: ex. 23; parti ularizare pentru azul nu leului

RBF: ex. 49.

Antrenarea reµelelor neuronale arti� iale:

algoritmul de retro-propagare pentru reµele feed-forward

− T. Mit hell, Ma hine Learning, p. 98: pseudo- od pentru reµele u unit µi

de tip sigmoidal, u 2 niveluri, dintre are unul as uns; pentru dedu erea

regulilor de a tualizare a ponderilor; în azul mai general al reµelelor feed-

forward (de unit µi sigmoidale) u ori âte niveluri, vedeµi p. 101-103;

ex. 19: dedu erea regulilor de a tualizare a ponderilor în azul reµelelor u 2

niveluri, având îns unit µi u fun µie de a tivare oare are (derivabil );

− apli are: ex. 20, ex. 42, ex. 43;

− prevenirea over�tting-ului:

folosirea unei omponente de tip �moment� în expresia regulilor de a tualizare

a ponderilor: ex. 45;

regularizare: introdu erea unei omponente suplimentare în fun µia de opti-

mizat: ex. 21;

− azul folosirii unei fun µii de a tivare de tip tangent hiperboli : ex. 44;

− azul folosirii unei fun µii de ost / penalizare / eroare de tip ross-entropie:

ex. 47;

− exe uµia manual a unei iteraµii a algoritmului de retro-propagare în azul unei

reµele neuronale simple, având un singur nivel as uns, u unit µi e foloses

fun µia de a tivare ReL: ex. 48.

Reµele neuronale profunde � âteva hestiuni introdu tive

− analiza onvexit µii unor fun µii de ost folosite în înv µarea profund : ex. 54;

− fenomenul de �dispariµie� a gradientului [în azul apli rii algoritmului de

retro-propagare℄ pentru reµele neuronale profunde (engl., deep neural ne-

tworks) are foloses fun µia de a tivare sigmoidal : ex. 26;

− determinarea num rului de parametri ³i de onexiuni din reµeaua neuronal

onvolutiv LeNet: ex. 27;

− determinarea m rimii h rµii de tr s turi de pe un anumit nivel, pre um ³i

a num rului de operaµii în virgul mobil (FLOPs) exe utate la pro esarea

forward într-o reµea neuronal onvolutiv : ex. 55.

9. Ma³ini u ve tori-suport

− elemente [simple℄ de al ul ve torial ; propriet µi elementare ale produsului

s alar al ve torilor din Rn, norma eu lidian (L2) ³i norma L1 în R

n: ex. 1,

ex. 34;

− elemente [simple℄ de geometrie analiti : e uaµia unei drepte din planul eu li-

dian, e uaµia unui plan din R3, e uaµia unui hiper-plan din R

n; e uaµia dreptei

are tre e prin dou pun te date în planul eu lidian: ex. 5. ; panta unei drepte

perpendi ulare pe o dreapt dat : ex. 9.d, ex. 35, ex. 37;

− distanµa ( u sau f r semn) de la un pun t la o dreapt (respe tiv la un plan,

sau mai general la un hiperplan): ex. 5, ex. 6. , ex. 1;

− propriet µi de baz din al ulul matri eal ;

− al ulul derivatelor parµiale [pentru fun µii obµinute prin ompuneri de fun µii

elementare℄;

− metoda lui Lagrange pentru rezolvarea problemelor de optimizare onvex u

restri µii :

ex. 34,

ex. din https://www. s.helsinki.�/u/jkivinen/tea hing/sumale/Spring2014/kkt_example.pdf,

ex. 56, ex. 57 de la apitolul de Fundamente;

− separabilitate liniar , separator optimal,margine geometri : ex. 37, ex. 6.ab ,

ex. 9.

SVM u margine �hard�

− (•) dedu erea formei primale pentru problema SVM ( u margine �hard�),

pornind de la prin ipiul maximizarii marginii geometri e: ex. 2;

− (P0) o form [simpl ℄ e hivalent u forma primal a problemei de optimizare

SVM : ex. 7;

− exempli� area identi� rii separatorului optimal ³i a ve torilor-suport, por-

nind de la ondiµiile din forma primal : ex. 3-5, ex. 35, ex. 37, ex. 38 ³i CMU,

2004 fall, T. Mit hell, Z. Bar-Joseph, HW4, ex. 4.1-4;

− al ularea erorii la ross-validare �leave-one-out� atun i ând se folose³te o

SVM liniar u margine �hard�: ex. 4.d, ex. 36;

− exemple de [fun µii de℄ mapare a atributelor, u s opul de a obµine separabi-

litate liniar : ex. 6.d, ex. 8, ex. 9.b, ex. 9, ex. 39.bd, ex. 40.a;

rezolvarea dire t a problemei SVM primale în [noul℄ spaµiu de tr s turi;

identi� area separatorului neliniar din spaµiul iniµial [de tr s turi℄: ex. 9.de,

ex. 39. e, ex. 40.b-e;

− (•) dedu erea formei duale pentru problema SVM u margine �hard�: ex. 10;

Vedeµi ³i Andrew Ng (Stanford), Le ture Notes, part V, se tion 3.

− exempli� area a dou modalit µi de g sire a formei duale a problemei SVM

u margine �hard� pentru înv µarea unui on ept [reprezentat de un set de

date de antrenament neseparabil în spaµiul �iniµial� de tr s turi℄ folosind o

fun µie de mapare Φ dat : prin optimizare dire t (ex. 11, ex. 41), respe tiv

prin folosirea relaµiilor de leg tur u soluµia problemei primale: ex. 12;

− (P1) efe tul multipli rii valorilor atributelor u o onstant pozitiv asupra

separatorului obµinut de SVM): ex. 27.a;

− vedeµi propriet µile (P4) ³i (P6) enunµate mai jos (la se µiunea despre C-

SVM), are sunt valabile ³i în azul SVM [ u margine �hard�℄;

− (P2) efe tul unui atribut irelevant � în sensul nu afe teaz satisfa erea

restri µiilor de separabilitate liniar a datelor de antrenament ³i, în plus, nu

m re³te marginea de separare � asupra rezultatelor lasi� atorului SVM (³i

respe tiv C-SVM): ex. 48, ex. 56;

− omparaµii între SVM [având, eventual, diferite fun µii-nu leu℄ ³i alµi lasi�-

atori: ex. 56, ex. 44, ex. 45; vedeµi ³i ex. 12 de la apitolul Înv µare bazat

pe memorare.

SVM u margine �soft� (C-SVM):

− (•) dedu erea formei duale pentru problema SVM u margine �soft� (C-SVM):

ex. 13;

− (P3) exprimarea / al ularea distanµei geometri e de la un ve tori-suport

xi pentru are αi = C la hiperplanul-margine orespunz tor eti hetei yi, uajutorul variabilei de �destindere� ξi: ex. 14.a;

− exempli� area noµiunilor de baz : ex. 46, ex. 47 ³i CMU, 2008 fall, Eri Xing,

�nal, ex. 2.2;

un exemplu de al ulare a valorii optime pentru fun µia obie tiv a problemei

de optimizare C-SVM: ex. 14.b;

− exempli� area poziµion rii separatorului optimal determinat de C-SVM (pen-

tru diferite valori ale parametrului C), în prezenµa unui outlier: ex. 16;

− exempli� area efe tului pe are îl are re³terea valorii parametrului de �des-

tindere� C [asupra marginii ³i asupra ex epµiilor la lasi� are℄: ex. 17, CMU,

2010 fall, Aarti Singh, HW3, ex. 3.2;

− un exemplu de situaµie în are forma dual a problemei de optimizare C-SVM

are soluµie uni , dar forma sa primal nu are soluµie uni : ex. 18;

− (P4) o proprietate pentru C-SVM (dar ³i pentru SVM): ex. 15

Da în setul de date de antrenament dou tr s turi (engl., features) sunt

dupli ate (xij = xik pentru i = 1, . . . ,m), atun i ele vor primi ponderi identi e

(wj = wk) în soluµia optimal al ulat de lasi� atorul [C-℄SVM;

− (P5) o margine superioar (engl., upper bound) pentru num rul de erori

omise la antrenare de tre C-SVM: ex. 19;

(C-SVM) ≤1

Rezultatul nu se menµine ³i în azul C-SVM: ex. 27.b.

− (P6) o proprietate pentru C-SVM (dar ³i pentru SVM):

La CVLOO numai ve torii-suport pot � (eventual!) lasi� aµi eronat: ex. 20;

a³adar avem [³i℄ o margine superioar pentru num rul de erori omise la

CVLOO de tre C-SVM:

(C-SVM) ≤#SVs

− (P7) hestiuni legate de omplexitatea omputaµional privind lasi� atorul

C-SVM: ex. 54;

− (•) dedu erea formei duale pentru problema SVM u margine �soft� (C-SVM)

de norm L2: ex. 49;

− (•) o form e hivalent a problemei de optimizare C-SVM, în are nu apar

delo restri µii asupra variabilelor, dar în are se folose³te fun µia de pierdere

/ ost hinge: ex. 21;

exempli� are / apli are (³i omparare u regresia logisti ): ex. 50;

− (•) algoritmul SMO (Sequential Minimal Optimization): dedu erea relaµiilor

de a tualizare a variabilelor Lagrange;

exemple de apli are a algoritmului SMO simpli� at: ex. 23, ex. 51;

− o omparaµie asupra efe tului atributelor irelevante (ai i, în sensul odat

eliminate / ad ugate, n-ar trebui s afe teze rezultatele lasi� rii) asupra

lasi� atorilor 1-NN ³i C-SVM: ex. 56;

SVM / C-SVM ³i fun µiile-nu leu � âteva propriet µi

− exempli� area orespondenµei dintre forma (primal sau dual ) a problemei

C-SVM ³i alegerea valorii parametrului de �destindere� C ³i a fun µiei-nu leu

pe de o parte ³i alura ³i poziµionarea separatorului optimal pe de alt parte:

ex. 24, ex. 52;

− exempli� area efe tului pe are îl are translatarea datelor în raport u o ax

(Oy) asupra poziµiei separatorului optimal (în raport u fun µia-nu leu folo-

sit ): ex. 42;

− C-SVM: ondiµii su� iente asupra parametrului de �destindere� C ³i asupra va-

lorilor fun µiei-nu leu pentru a toate instanµele de antrenament s �e ve tori-

suport: ex. 25;

− SVM u nu leu RBF: âteva propriet µi remar abile

◦ pentru SVM pe un set de date [separabil liniar în spaµiul de tr s turi℄ in-

stanµe foarte dep rtate de separatorul optimal pot � ve tori-suport: ex. 43;

◦ (P8) pentru ori e set de instanµe distin te ³i pentru ori e eti hetare a a es-

tora, exist o valoare a hiper-parametrului nu leului RBF (σ) astfel în ât SVMobµine la antrenare eroare 0: ex. 26. Rezultatul nu este valabil ³i pentru C-

◦ (P9) pentru ori e set de instanµe distin te, pentru ori e eti hetare a a estora

³i pentru ori e valoare a hiper-parametrului nu leului RBF (σ), problema de

tip SVM are impune a toate instanµele s �e ore t lasi� ate ³i la distanµa

1/‖w‖ faµ de separatorul optimal are soluµie: ex. 58;

− avantaje ³i dezavantaje ale folosirii metodelor de lasi� are liniar de tipul

SVM, Per eptron et . ³i versiunile lor kernel-izate: ex. 55.

− hestiuni re apitulative: ex. 28, ex. 27, ex. 66, ex. 57.

Alte probleme [de optimizare℄ de tip SVM

• SVM pentru lasi� are n-ar (SVM multi lass): ex. 29, ex. 59;

• dedu erea formei duale pentru problema one- lass SVM , versiuneaMax Mar-

gin: ex. 30 (varianta u margine �hard�), ex. 61 (varianta u margine �soft�,

folosind ν-SVM);

− leg tura dintre soluµiile problemei one- lass SVM , versiunea Max Margin,

u margine �hard� ³i respe tiv ele ale problemei SVM ( u ³i respe tiv f r

termen liber (engl., bias), tot u margine �hard�: ex. 60;

• dedu erea formei duale pentru problema one- lass SVM , versiunea minimum

en losing ball (MEB): ex. 31 (varianta u margine �hard�), ex. 62 (varianta

u margine �soft�, folosind ν-SVM );

− o ondiµie su� ient pentru a variantele u margine �hard� pentru ele dou

tipuri de probleme de optimizare one- lass SVM, ³i anumeMax Margin ³i mi-

nimum en losing ball (MEB), în forma kernel-izat , s �e e hivalente: ex. 31;

• dedu erea formei duale pentru problema ν-SVM : ex. 32;

• dedu erea formei duale pentru problema SVR (Support Ve tor Regression),

folosind fun µie de ost / pierdere ε-senzitiv : ex. 33 ( u margine �hard�),

ex. 64 ( u margine �soft� ³i (e hivalent) u fun µie de ost ε-senzitiv );exempli� are / apli are: ex. 63;

− teorema de reprezentare: ex. 65.

Exerciµii - Alexandru Ioan Cuza Universityciortuz/ML.ex-book/sumar.pdfExerciµii de µare v în...

Documents