• Nu S-Au Găsit Rezultate

# MACHINE LEARNING

N/A
N/A
Protected

Share "MACHINE LEARNING"

Copied!
37
0
0
Arată mai multe ( pagini)

Text complet

(1)

## MACHINE LEARNING

(2)

learn from

(3)

(4)

(5)

### A multi-domain view

Intelligence Artificial

(concept learning)

Algorithms Mathematics

Statistics (model fitting)

Machine Learning

Learning

Statistical Pattern

Recognition Mining Data

Engineering Database Systems

(Knowledge Discovery in Databases)

(6)

(7)

(8)

### Bibliography

0. “Exercit¸ii de ˆınv˘at¸are automat˘a”

L. Ciortuz, A. Munteanu E. B˘ad˘ar˘au.

Ia¸si, Romania, 2022

www.info.uaic.ro/∼ciortuz/ML.ex-book/editia-2022f/ex-book.22sept2022.pdf 1. “Machine Learning”

Tom Mitchell. McGraw-Hill, 1997

2. “Support Vector Machines and other kernel-based learning methods”

Nello Cristianini, John Shawe-Taylor. Cambridge University Press, 2000.

3. “Foundations of Statistical Natural Language Processing”

Christopher Manning, Hinrich Sch¨utze. MIT Press, 2002 4. “Machine Learning Foundations”

Teaho Jo. Springer, 2021

5. “A First Course in Machine Learning”

Simon Rogers, Mark Girolami. Chapman and Hall / CRC, 2nd ed., 2016

(9)

### “We are drawning in information but starved for knowledge.”

John Naisbitt, “Megatrends” book, 1982

(10)

h

(11)

(12)

c

i

c

i

c

i

c

i

i

c

c

(13)

(14)

### fntpfp

tp − true positives f p − false positives tn − true negatives f n − false negatives

accuracy: Acc = tp + tn

tp + tn + fp + fn precision: P = tp

tp + fp

recall (or: sensitivity): R = tp tp + fn F-measure: F = 2 P × R

P+R specificity: Sp = tn

tn + fp follout: = fp

tn + fp

Mathew’s Correlation Coefficient:

MCC = tp × tn − fp × fn

q(tp + fp)×(tn + fn)×(tp + fn)×(tn + fp)

(15)

(16)

(17)

### else iterate over the new leaf nodes

(18)

Consider m training examples S = {(x1, y1), . . . ,(xm, ym)}, where xi ∈ X and yi ∈ {−1,+1}.

Suppose we have a weak learning algorithm A which produces a hypothesis h : X → {−1,+1}

given any distribution D of examples.

Begin with a uniform distribution D1(i) = 1

m, i = 1, . . . , m.

At each iteration t = 1, . . . , T,

run the weak learning algo A on the distribution Dt and produce the hypothsis ht; Note (1): Since A is a weak learning algorithm, the produced hypothesis ht at round t is only slightly better than random guessing, say, by a margin γt:

εt = errDt(ht) = Prx∼Dt[y 6= ht(x)] = 1

2 γt.

Note (2): If at a certain iteration t T the weak classifier A cannot produce a hypothesis better than random guessing (i.e., γt = 0) or it produces a hypothesis for which εt = 0, then the AdaBoost algorithm should be stopped.

update the distribution Dt+1(i) = 1

Zt

·Dt(i)·e−αtyiht(xi) for i= 1, . . . , m, (1) where αt

not.= 1

2 ln 1εt

εt

, and Zt is the normalizer.

In the end, deliver HT = signPT

t=1 αtht

as the learned hypothesis, which will act as a weighted majority vote.

(19)

### AdaBoost as an instance of a more general stepwise algorithm

Input: S, T, H, φ, where

S = {(x1, y1), . . . ,(xm, ym) is the training dataset, with yi ∈ {−1,+1}

T is the number of iterations to be executed, H is a set of “hypotheses”,

φ(y, y) is a “loss” / “cost” / “risk” function;

Procedure:

Initialize the classifier by taking f0(x) = 0 (the constant function 0), and D1(i) = 1/m for i= 1, . . . , m

for t = 1 to T do:

1. Compute

(ht, αt) = arg minα∈R,h∈HPm

i=1φ(yi, ft−1(xi) +αh(xi)) 2. Update the classifier

ft(x) = ft−1(x) +αtht(x) compyte Dt+1

end for

return the classifier sign(fT(x))

Note: At each step, the algorithm greedily adds a hypothesis h ∈ H to the current combined hypothesis to minimize the φ-loss.

(20)

[MIT, 2003 fall, Tommi Jaakkola, HW4, pr. 2.1-3]

Initialization: W˜i(1) = 1/m and f0(xi) = 0 for i= 1, . . . , m.

Loop: for t = 1 to T do:

Step 1: Find a classifier h(x; ˆθt) performing better than chance wrt the weighted training error:

εt

not.= X

i:yi6=h(xi; ˆθt)

W˜i(t)yih(xi;θ) = 1 2

1 Xm

i=1

W˜i(t)yih(xi; ˆθt) .

Step 1: Note: Minimizing εt is equivalent to finding θˆt that minimizes

∂αJt(α, θt)|α=0 wrt θt, where Jt(α, θt) = 1

m

m

X

i=1

Loss(yift−1(xi) +yiα h(xi;θt)).

Step 2: Set the votes αt for the new component by minimizing the overall empirical loss:

αt = arg min

α≥0Jt(α,θˆt).

Step 3: Recompute the normalized weights for the next iteration according to W˜i(t+1) = −ct ·dL(yift−1(xi) +yiαth(xi; ˆθt)

| {z }

yift(xi)

) for i = 1, . . . , m,

Step 3: where ct is chosen so that Pm

i=1W˜i(t+1) = 1.

Output: fT

(21)

### The Naive Bayes Classifier

• Assume that the attributes < a1, . . . , an > that describe instances are conditionally independent w.r.t. to the given classification:

P(a1, a2. . . an|vj) = Y

i

P(ai|vj)

• Training procedure:

Naive Bayes Learn(examples)

for each value vj of the output attribute Pˆ(vj) ← estimate P(vj)

for each value ai of each input attribute a Pˆ(ai|vj) ← estimate P(ai|vj)

• The decision rule of the Naive Bayes classifier is:

vM AP = argmax

vj∈V

P(vj|a1, a2. . . an) = argmax

vj∈V

P(a1, a2. . . an|vj)P(vj) P(a1, a2. . . an)

= argmax

vj∈V

P(a1, a2. . . an|vj)P(vj) = argmax

vj∈V

Y

i

P(ai|vj)P(vj) not.= vN B

(22)

### Logistic Regression

Given the dataset {(x(1), y(1)), (x(2), y(2)), . . . , (x(n), y(n))}, where each vector x(i) has d features / attributes, and y(i) ∈ {0,1} for i = 1, . . . , n, its complete log-likelihood is:

log-likelihood= ln

n

Y

i=1

P(x(i), y(i)) = ln

n

Y

i=1

(PY|X(y(i)|x(i))PX(x(i)))

= ln

n Y

i=1

PY|X(y(i)|x(i))

!

·

n

Y

i=1

PX(x(i))

!!

= ln

n

Y

i=1

PY|X(y(i)|x(i)) + ln

n

Y

i=1

PX(x(i))not.= ℓ(w) +x.

Note that ℓx does not depend on the parameter w.

P(Y = 0|X =x) = 1σ(z), where σ(z) def.= 1

1 +e−z = ez 1 +ez, z not.= w0 +

d

X

i=1

wixi

not.= w·x, with

w not.= (w0, w1, . . . , wd) Rd+1, assuming x0 = 1.

0 0.5 1

-6 -4 -2 0 2 4 6

sigma(x)

x

It can be shown that the conditional log-likelihood function ℓ(w) can be written as:

ℓ(w) = Xn

i=1

y(i)lnσ(w ·x(i)) + (1−y(i)) ln(1−σ(w · x(i))) wLogR

def.= argmax

w

ℓ(w) = arg min

w (−ℓ(w)). (2)

Note that −ℓ(w) is a cross-entropy.

For a more general result than (2), see Stanford, 2015 fall, Andrew Ng, HW3, pr. 5.c.

(23)

### See the analogy with the sigmoidal perceptron

CMU, 2011 fall, Eric Xing, HW1, pr. 3.3

w1 w2

wn

w0 x1

x2

xn

x0 = 1

. . .

### Σ

net = Σwi xi

i=0 n

1 1 + e-net o = σ(net) =

(24)

### The k -Nearest Neighbor Argorithm

Evelyn Fix, Joseph Hodges, 1951; Thomas Cover, Peter Hart, 1967

Training:

Store all training examples.

Classification:

Given a query/test instance xq,

first locate the k nearest training examples x1, . . . , xk, then estimate fˆ(xq):

• take a vote among its k nearest neighbors fˆ(xq) ← argmax

v∈V

Xk

i=1

1{f(xi)=v}

where 1{ · } is the well-known indicator function.

(25)

### The Bottom-up Hierarchical Clustering Algorithm

Given: a set X = {x1, . . . , xn} of objects a function sim: P(X)× P(X) → R for i = 1, n do

ci = {xi} end C = {c1, . . . , cn} j = n + 1

while | C |> 1

(cn1, cn2) = argmax(cu,cv)∈C×C sim(cu, cv) cj = cn1 ∪cn2

C = C\{cn1, cn2} ∪ {cj} j = j + 1

(26)

### S. P. Lloyd, 1957

Given: a set X = {x1, . . . , xn} ⊆ Rm, a distance measure d on Rm,

a function for computing the mean µ : P(Rm) → Rm,

built k clusters so as to satisfy a certain (“stopping”) criterion (e.g., maxi- mization of group-average similarity).

Procedure:

Select (arbitrarily) k initial centers f1, . . . , fk in Rm; while the stopping criterion is not satisfied

for all clusters cj do cj = {xi | ∀fl d(xi, fj) ≤ d(xi, fl)} end for all means fj do fj ← µ(cj) end

(27)

### K-Means algorithm revisited (I)

Se init¸ializeaz˘a ˆın mod arbitrar centroizii µ1,µ2, . . . ,µK ¸si se ia C ={1, . . . , K}.

Atˆata timp cˆat valoarea criteriului J de- scre¸ste ˆın mod strict, repet˘a:

Pasul 1:

Calculeaz˘a γ astfel:

γij

(1, dac˘a kx

iµjk2 ≤ kx

iµj′ k2, ∀j′ ∈C, 0, ˆın caz contrar.

ˆIn caz de egalitate, alege ˆın mod arbi- trar c˘arui cluster (dintre cele eligibile) s˘a-i apart¸in˘a xi.

Pasul 2:

Recalculeaz˘a µj folosind matricea γ actual- izat˘a:

Pentru fiecare j C, dac˘a Pn

i=1γij > 0, asigneaz˘a

µj Pn

i=1γijxi

Pn

i=1γij

.

Altfel, ment¸ine neschimbat centroidul µj.

Algoritmul de clusterizare K-means poate fi v˘azut [¸si reformulat] ca un algoritm de optimizare, folosind metoda descre¸sterii pe coordonate.

Obiectivul este acela de a minimiza o funct¸ie obiectiv care asoar˘a (indirect) coeziunea intra-clustere:

J(L, µ) =

n

X

i=1

||xi µli||2,

Algoritmul K-means face init¸ializarea centroizilor clus- terelor µ cu anumite valori, dup˘a care procedeaz˘a astfel:

Pasul 1:

astrˆand µ fixat, g˘ase¸ste acea asignare L a instant¸elor la clustere care minimizeaz˘a funct¸ia J(L, µ);

Pasul 2:

astrˆand asignarea L fixat˘a, g˘ase¸ste acea valoare pentru µ pentru care se minimizeaz˘a J(L, µ).

Criteriul de oprire: Dac˘a [aceasta nu este prima iterat¸ie

¸

si] niciuna dintre asign˘arile din listaLnu s-a modificat ˆın raport cu precedenta iterat¸ie, se trece la pasul urm˘ator (Terminare); altfel se repet˘a de la Pasul 1.

Terminare: Returneaz˘a L ¸si µ.

(28)

### K-Means algorithm revisited (II)

(t) 1

(t) (t)

µ = (µ , ..., µ )K

min J(C, )µ

(t+1)

γij = ...

(t+1)

γij

(t+1)

γij xi (t+1)

µj =

ΣΣ

t=0

++t

(t) 1

(t) (t)

µ = (µ , ..., µ )K

min J(C, )µ

C(t+1) J(C, )µ(t)

C

= argmin

(t+1)

J(C , )µ

(t+1)

µ = argmin

µ

t=0

++t

(29)

### The General EM Problem

Given

• observed data X = {x1, . . . , xm} independently generated using the parameterized distribu- tions/hypotheses h1, . . . , hm

• unobserved data Z = {z1, . . . , zm} determine

hˆ that (locally) maximizes P(X|h).

### Approach

Repeatedly

1. Use the observed data X and the current hypothesis h(t) to estimate [the proba- bilities associated to the values of ] the unobserved variables Z, and further on compute their expectations, E[Z].

2. The expected values of the unobserved variables Z are used to calculate an im- proved hypothesis h(t+1), based on max- imizing the mean of a log-likelihood function: E[lnP(Y|h)|X, h(t)], where Y = {y1, . . . , ym} is the complete (observed and unobserved) data, i.e. yi = (xi, zi), for i = 1, . . . , m.

(30)

(t)

(t)

h

(t+1)

P(Z|X; )h(t)

++t

t=0

(31)

(32)

(33)

(34)

P2 T1

### Punctaj

T2 S P1

Test: 6p Test: 6p Seminar: 8p Ex. partial: 10p Ex. partial: 10p Minim: 1.5p

Minim: 1.5p Minim: 2p Minim: 2.5p Minim: 2.5p

Prezenta la seminar: obligatorie!

Penalizare: 0.2p pentru fiecare absenta de la a doua incolo!

Pentru promovare: Nota >= 4.5 Prezenta la curs: recomandata!

Nota = (10 + T1 + T2 + S + P1 + P2) / 5

<=> T1 + T2 + S + P1 + P2 >= 12.5

(35)

### REGULI generale pentru cursul de ˆInv˘ at¸are automat˘ a de la licent¸˘ a

Regulile de organizare a cursului de ˆInv˘at¸are Automat˘a (engl., Machine Learning, ML), sem. I, sunt specificate ˆın fi¸sa disciplinei

http://profs.info.uaic.ro/∼ciortuz/fisa-disciplinei.pdf

• Bibliografie minimal˘a: vezi slide #8

• Planificarea materiei, pentru fiecare s˘apt˘amˆan˘a (curs + seminar):

http://profs.info.uaic.ro/∼ciortuz/what-you-should-know.pdf

• Prezent¸a la curs: recomandat˘a!

• Regula 0: Prezent¸a la seminar: obligatorie!

Pentru fiecare absent¸˘a la seminar, ˆıncepˆand de la a doua absent¸˘a ˆıncolo, se aplic˘a o penalizare/depunctare de 0.2 puncte. (Vezi formula de notare.)

Regulile se aplic˘a inclusiv student¸ilor reˆınmatriculat¸i.

• S˘apt˘amˆanal — mart¸ea, ˆıntre orele 18–20, ˆın C309 — se va t¸ine un seminar suplimentar, destinat pentru acei student¸i care sunt foarte interesat¸i de acest domeniu ¸si c˘arora le plac demonstrat¸iile matematice. (Vedet¸i sect¸iunile “Advanced issues” din documentul http://profs.info.uaic.ro/∼ciortuz/what-you-should-know.pdf.)

(36)

### Regula 1:

Pentru seminarii, nu se admit mut˘ari ale student¸ilor de la o grup˘a la alta, decˆat ˆın cadrul grupelor care au acela¸si asistent / profesor responsabil de seminar.

### Regula 2:

Nu se fac echival˘ari de punctaje pentru student¸ii care nu au promovat cursul ˆın anii precedent¸i.

### Regula 3:

Profesorul responsabil pentru acest curs, Liviu Ciortuz,

NU va r˘aspunde la email-uri care pun ˆıntreb˘ari pentru care raspunsul a fost deja dat – fie ˆın aceste slide-uri,

– fie pe site-ul Piazza dedicat acestui curs:

https://piazza.com/info.uaic.ro/fall2022/ml2022f/home, – fie la curs.

### Recomandare important˘ a (1)

La fiecare curs ¸si seminar, student¸ii vor avea culegerea de Exercit¸ii de ˆınv˘at¸are automat˘a (de L. Ciortuz et al) — v˘a recomand˘am s˘a imprimat¸i capitolele Clasificare bayesian˘a, ˆInv˘at¸are bazat˘a pe memorare, Arbori de decizie ¸si Clus- terizare — ¸si eventual slide-urile pe care le-am indicat ˆın slide-ul precedent.

### Recomandare important˘ a (2)

Consultat¸i s˘apt˘amˆanal documentul

what-you-should-know.pdf din pagina de Resurse, de pe site-ul Piazza dedicat acestui curs.

(37)

### Slide-uri de imprimat

(ˆın aceast˘a ordine ¸si, de preferat, COLOR):

http://profs.info.uaic.ro/∼ciortuz/SLIDES/foundations.pdf

https://profs.info.uaic.ro/∼ciortuz/ML.ex-book/SLIDES/ML.ex-book.SLIDES.ProbStat.pdf https://profs.info.uaic.ro/∼ciortuz/ML.ex-book/SLIDES/ML.ex-book.SLIDES.DT.pdf

https://profs.info.uaic.ro/∼ciortuz/ML.ex-book/SLIDES/ML.ex-book.SLIDES.Bayes.pdf https://profs.info.uaic.ro/∼ciortuz/ML.ex-book/SLIDES/ML.ex-book.SLIDES.IBL.pdf https://profs.info.uaic.ro/∼ciortuz/ML.ex-book/SLIDES/ML.ex-book.SLIDES.Cluster.pdf (Atent¸ie: acest set de slide-uri poate fi actualizat pe parcursul semestrului!)

De imprimat (ALB-NEGRU):

http://profs.info.uaic.ro/∼ciortuz/SLIDES/ml0.pdf http://profs.info.uaic.ro/∼ciortuz/SLIDES/ml3.pdf http://profs.info.uaic.ro/∼ciortuz/SLIDES/ml6.pdf http://profs.info.uaic.ro/∼ciortuz/SLIDES/ml8.pdf http://profs.info.uaic.ro/∼ciortuz/SLIDES/cluster.pdf

Referințe

DOCUMENTE SIMILARE

În schimb, pentru a compara descriptorul Top-Surf al unei imagini cu cei prezenți într-o bază de date, este nevoie în medie de 0.2ms (experiment realizat cu o bază de date de 100

-Prisma dreapt˘ a cu baza: triunghi echilateral, p˘ atrat, dreptunghi, hexagon regulat: descriere, desf˘ a¸surare, aria lateral˘ a, aria total˘ a ¸si volum.. -Piramida triunghiular˘

példa: SzállításiInformációk relációja nincs 2NF-ben, mivel a reláció kulcsa a {SzállID, ÁruID} és fennáll a SzállID → SzállNév, tehát SzállNév függ

Prin date spatiale intelegem acele date statistice ce sunt asociate cu o locatie in spatiu; pentru datele spatio-temporale mai apare si referirea la variabila timp (datele

(Începutul şi sfârşitul subdocumentelor îi corespunde) Comanda obişnuită de trecere la modul Outline View afişează documentul în regim de document principal, după care

• Colangiografia transparietohepatică , deşi creşte riscul de angiocolită sau coleperitoneu, poate preciza sediul stenozei, lungimea şi dilatarea bontului biliar

Pentru a avea o privire mai cuprinz˘ atoare asupra variatei palete de pre- ocup˘ ari a lui Traian Lalescu am ales s˘ a v˘ a propunem spre lectur˘ a ( ˆın form˘ a complet˘ a sau

¸si algoritmul lui Tseng. Ace¸sti algoritmi au fost studiate ˆın detaliu ˆın ... Capitolul trei este dedicat algoritmului primal-dual de divizare pentru rezolvarea problemei

(2003) .A new method for group decision support based on ELECTRE III methodology., European Journal of Operational Research, 148, 14-27.. (2004) .Multi-criteria decision analysis:

Capitolul II: am propus spre rezolvarea cu ajutorul numerelor complexe teoreme ¸si probleme de geometrie.... Aplicat¸ii ale numerelor

Cea mai simpl˘a modalitate de a g˘asi o replicare pentru func¸tia de plat˘a având la dispozi¸tie instrumentele prezen- tate în enun¸t este s˘a folosim urm˘atoarea imagine...

Sebastian Aniţa, International Exploratory Workshop on Differential Equations and Applications in Life Sciences, Iaşi, 5 - 7 septembrie 2008

Propunem un manual exclusiv in limba romini, ce se adreseazi astfel unui public mult mai larg, neselectat in prealabil in functie de limbile striine pe care le

Frecventa studentilor din anii I si II în anul 2003 este obligatorie la toate formele de activitate ( curs, seminar, lucrari, proiect) iar la anii mari este obligatorie

(3) Adeverinţa care atestă calitatea de student (Anexele nr. 9A și 9B) în faţa autorităţilor din afara ţării se eliberează la cerere şi cuprinde următoarele elemente

Comunități  româneşti  din  Canada,  la  Simpozionul  Internațional  Români  majoritari/  Români  minoritari:  interferențe  şi  coabitări  lingvuistice,

Silvia Pitiriciu, Les dérivés verbaux expressifs en langue roumaine actuelle, cu prilejul Colocviului internaţional „Limbă, cultură, civilizaţie”, ediția a X-a,

Alina Crihană, Structures mytho-politiques et satire antitotalitaire dans La Ferme des animaux par George Orwell, în Actele Conferinţei Internaţionale « Paradigma

Medicii străini din state terțe ale Uniunii Europene se pot înscrie la studii de specializare în orice specialitate acreditată de Ministerul Sănătății din

(3) Școlile doctorale din cadrul IOSUD-UMFVBT asigură o cooperare activă cu toate instituțiile colaboratoare ale IOSUD, incluzând Academia Română și alte

De¸si ar putea p˘ area c˘ a am utilizat efectiv relat¸ia care este construita peste R[U ], ˆın fapt nu am facut decˆ at s˘ a modific˘ am schema de realat¸ie R[U ] ¸si s˘

Zero Speed Sensorless Direct Torque Control of Induction Machine Drives – A Sliding

Această amplă activitate de cercetare a fost parţial suportată de un grant naţional (de tip proiect complex cu aplicaţii industriale) de 10 granturi de tip IDEI din cadrul PNCDI II

Selectați limba dvs.

Site-ul web va fi tradus în limba pe care o selectați.

Limbi sugerate pentru dvs:

Alte: