ESERCITAZIONEIng. E. Ritacco

Ing. M. Guarascio

ESERCIZIO 1 Si consideri il seguente data set

Si definisca analiticamente un classificatore SVM, utilizzando il lagrangiano descritto dal vettore 

[0; 0; 0.023802; 0; 0; 0.074711; 0; 0; 0.098512; 0]T

x y U1 0 1 -12 1 4 -13 10 0 14 0 6 -15 0 2 -16 3 10 17 6 6 18 10 10 19 1 5 -1

10 8 9 1

T-SVMS

Le SVMs cercano l’iperpiano di separazione che tende a massimizzare il margine tra le etichette dei campioni.

w

H+

H-

Md

ESERCIZIO 1

Il lagrangiano primale del problema è dato da

Dove w e b caratterizzano l’iperpiano di separazione, e α rappresenta il lagrangiano.

N

ii

Tiip bybL

1

21

2

1,, xwwαw

ESERCIZIO 1

Le condizioni di ottimalità sono date dai valori della funzione che soddisfano:

Niby

Niy

NiLb

L

mjw

L

iT

ii

i

i

p

p

j

p

...1,01

...1,0

...1,0

0

...1,0

xw

ESERCIZIO 1

Semplificando, le condizioni possono essere riscritte in

Niby

Niy

Niby

y

y

iT

ii

i

iT

i

N

iii

N

iiii

...1,01

...1,0

...1,1

01

1

xw

xw

xw

ESERCIZIO 1

L’ultima condizione specifica che, ove αi non sia uguale a 0, allora deve valere la condizione

Nel nostro caso, α è dato dal vettore

[0; 0; 0.023802; 0; 0; 0.074711; 0; 0; 0.098512; 0]T

che caratterizza le tuple x3, x6, x9 come vettori di supporto.

1 by iT

i xw

ESERCIZIO 1

Analiticamente, i coefficienti del decision boundary sono

6364.2

1525455.01363641.0

11025455.03363641.0

1025455.010363641.0

25455.05098512.010074711.000.023802

363641.01098512.03074711.0100.023802

2

1

b

b

b

b

w

w

ESERCIZIO 1

Graficamente

ESERCIZIO 2

Si consideri il seguente dataset:

A B C3 1 X4 2 X4 1 X3 2 X12 1 Y13 2 Y13 3 Y18 7 X16 8 X18 9 X23 7 Y23 8 Y24 9 Y

ESERCIZIO 2 Considerando C come attributo di classe ed A e B

come variabili numeriche continue, calcolare l’entropia del data set e costruire due alberi di decisione:

Discretizzando A e B. Assumendo A e B come attributi numerici.

ESERCIZIO 2

ID A B C1 3 1 X2 4 2 X3 4 1 X4 3 2 X5 12 1 Y6 13 2 Y7 13 3 Y8 18 7 X9 16 8 X10 18 9 X11 23 7 Y12 23 8 Y13 24 9 Y

ESERCIZIO 2

L’entropia dell’intero Dataset è 0.9957.

Si discretizzano A e B secondo i seguenti criteri:

AMB=Molto Basso (X<10)B=Basso (10<=X<15)M=Medio (15<=X<20)A=Alto (20<=X<25)

BB=Basso (X<5) A=Alto (X>=5)

ESERCIZIO 2

ID A B C1 MB B X2 MB B X3 MB B X4 MB B X5 B B Y6 B B Y7 B B Y8 M A X9 M A X10 M A X11 A A Y12 A A Y13 A A Y

ESERCIZIO 2

L’albero di decisione è il seguente:

ESERCIZIO 2 Nell’altro caso invece, occorre scegliere

l’attributo su cui splittare.

Lo split sull’attributo A garantisce un maggior guadagno informativo, rimane però da stabilire la soglia per lo split.

Visto che A assume 8 valori diversi possiamo scegliere fra 7 soglie diverse.

Tramite la seguente tabella calcoliamo il guadagno informativo correlato allo split sulle varie soglie

ESERCIZIO 2

A<  >= <  >= <  >= <  >= <  >= <  >= <  >=

X 2 5 4 3 4 3 4 3 5 2 7 0 7 0Y 0 6 0 6 1 5 3 3 3 3 3 3 5 1G

18 23 24

0,1546 0,36 0,1307 0,0037 0,0349 0,3178 0,0912

4 12 13 16

Risulta conveniente splittare il dataset distinguendo fra valori di A<12 e valori di A>=12.

ESERCIZIO 2

A questo punto splittiamo su B.

Risulta conveniente splittare il dataset distinguendo fra valori di B<7 e valori di B>=7.

B<  >= <  >= <  >= <  >= <  >=

X 0 3 0 3 0 3 1 2 2 1Y 1 5 2 4 3 3 4 2 5 1G

9

0,0699 0,152 0,2516 0,0728 0,0248

2 3 7 8

ESERCIZIO 2

L’ultimo split viene fatto nuovamente su A, la scelta della soglia è banale.

ESERCIZIO 3

Si considerino i seguenti classificatori:

ESERCIZIO 3

Qual è il modello migliore?

E se considerassimo la seguente matrice di costo?

Guardare la sola predizione può essere fuorviante, conviene ricorrere all’analisi delle curve di ROC

ESERCIZIO 3FPR TPR

Soglie  Classe reale  TP TN FP FN 1 1

0,1 1 7 0 3 1 1 0,875

0,2 1 6 0 3 2 1 0,75

0,25 1 5 0 3 3 1 0,625

0,3 1 4 0 3 4 1 0,5

0,4 0 4 1 2 4 0,666667 0,5

0,6 0 4 2 1 4 0,333333 0,5

0,7 0 4 3 0 4 0 0,5

0,8 1 3 3 0 5 0 0,375

0,9 1 1 3 0 7 0 0,125

0,9 1 1 3 0 7 0 0,125

0,97 1 0 3 0 8 0 00 0

FPR TPR

Soglie  Classe reale  TP TN FP FN 1 1

0,1 0 7 1 3 0 0,75 1

0,2 1 6 1 3 1 0,75 0,857143

0,3 0 6 2 2 1 0,5 0,857143

0,4 0 6 3 1 1 0,25 0,857143

0,6 1 5 3 1 2 0,25 0,714286

0,7 1 4 3 1 3 0,25 0,571429

0,75 1 3 3 1 4 0,25 0,428571

0,8 1 2 3 1 5 0,25 0,285714

0,85 0 2 4 0 5 0 0,285714

0,9 1 1 4 0 6 0 0,142857

0,97 1 1 4 0 6 0 0,1428570 0

ESERCIZIO 3

ESERCIZIO 3

Dalla convex hull si individuano 3 punti principali: P1(0;0.5),P2(0.25;0.85),P3(0.75;1)

Costo(P1)= 0 x 50 + 4 x 10 = 40

Costo(P2)= 1 x 50 + 1 x 10 = 60

Costo(P3)= 3 x 50 + 0 x 10 = 150

ESERCIZIO 4 Si consideri il seguente data set

Si assuma il seguente modello probabilistico:

Dove, per una generica variabile binaria z, vale

Definire il passo E dell’algoritmo EM Per il modello probabilistico di cui sopra, definire il

passo M

x1 0 1 0 1 0 0 1 1 0 0

x2 0 0 1 1 0 1 0 1 0 1

x3 0 0 1 1 1 1 1 1 0 1

ESERCIZIO 4

Sappiamo che:

1

11

1 1

log | log |

log |

log |

N

ii

N M

k k i kki

N M

k k i ki k

X p x

p x

p x

L

ESERCIZIO 4

Introduciamo le variabili aleatorie yik

Il passo E dell’algoritmo corrisponde al calcolo di:

log L | X ,Y y

iklog p

kx

i, y

ik1,

k k 1

M

i1

N

1 1 1

1

| , 1 1 | , 0 0 | ,

1| ,

g g gik i k ik i k ik i k

g gik i k ik

E y x p y x p y x

p y x

ESERCIZIO 4

1

1

1

1 1

1 1

1

, 1|| ,

|

1| | 1,

1| | 1,

gi ikg g

ik ik i gi

g gik k i ik

Mg g

ij j i ijj

p x yE y x

p x

p y p x y

p y p x y

Ma ricordiamo che

ESERCIZIO 4

Il passo M Definizione dei vincoli:

1

1M

kk

Sempre vero

ESERCIZIO 4

Utilizziamo, quindi, i moltiplicatori di Lagrange

1,1log

1,,

1

)(

1 1

)(

1

)()1(

M

j

gj

N

i

M

kkikik

gik

M

j

gj

g

yxp

Qf

ESERCIZIO 4

Derivando su π

1

1

1

,... 0

1

,1 0

gNir

gir r

Ng g

r iri

Mg

jj

f

f

1

1 1

Ng

irg i

r N Mg

iji j

1

1 1

... 1| , 1M M

g gij ij i

j j

p y x

1

1 Ng g

r iriN

ESERCIZIO 4

Derivando sui parametri di θ, e ricordando che

Allora:

N

i

M

kkikik

gikk

j

yxp1 1

)( 0,1log

N

i

M

k

N

i t

kttik

gikk

jkikik

gikk

j

xpyxp1 1 1

3

1,

)()( 0log,1log