ESERCITAZIONE
Ing. E. Ritacco
Ing. M. Guarascio
ESERCIZIO 1

Si consideri il seguente data set
x
1
2
3
4
5
6
7
8
9
10


y
0
1
10
0
0
3
6
10
1
8
U
1
4
0
6
2
10
6
10
5
9
-1
-1
1
-1
-1
1
1
1
-1
1
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
T-SVMS
Le SVMs cercano l’iperpiano di separazione che tende a massimizzare il
margine tra le etichette dei campioni.
H+
H-
w
d
M
ESERCIZIO 1

Il lagrangiano primale del problema è dato da


N
1
2
L p w, b, α   w    i yi w T xi  b   1
2
i 1

Dove w e b caratterizzano l’iperpiano di
separazione, e α rappresenta il lagrangiano.
ESERCIZIO 1

Le condizioni di ottimalità sono date dai valori
della funzione che soddisfano:
L p
w j
L p
b
L p
 i
 0, j  1...m
0
 0, i  1...N
yi  0, i  1...N
 i yi w T xi  b   1  0, i  1...N
ESERCIZIO 1

Semplificando, le condizioni possono essere
riscritte in
N
w    i yi xi
i 1
N
 y
i 1

i
i
0

yi w T xi  b  1, i  1...N
yi  0, i  1...N
 i yi w T xi  b   1  0, i  1...N
ESERCIZIO 1

L’ultima condizione specifica che, ove αi non sia
uguale a 0, allora deve valere la condizione


yi w T xi  b  1

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.
ESERCIZIO 1

Analiticamente, i coefficienti del decision
boundary sono
w1  0.023802 10  0.074711 3  0.098512 1  0.363641
w2  0.023802  0  0.07471110  0.098512  5  0.25455
0.36364110  0.25455  0  b  1

0.363641 3  0.25455 10  b  1 b  2.6364
0.3636411  0.25455  5  b  1
ESERCIZIO 1

Graficamente
ESERCIZIO 2

Si consideri il seguente dataset:
A
3
4
4
3
12
13
13
18
16
18
23
23
24
B
1
2
1
2
1
2
3
7
8
9
7
8
9
C
X
X
X
X
Y
Y
Y
X
X
X
Y
Y
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
1
2
3
4
5
6
7
8
9
10
11
12
13
A
3
4
4
3
12
13
13
18
16
18
23
23
24
B
1
2
1
2
1
2
3
7
8
9
7
8
9
C
X
X
X
X
Y
Y
Y
X
X
X
Y
Y
Y
ESERCIZIO 2

L’entropia dell’intero Dataset è 0.9957.

Si discretizzano A e B secondo i seguenti criteri:
A
MB=Molto Basso (X<10)
B=Basso (10<=X<15)
M=Medio (15<=X<20)
A=Alto (20<=X<25)
B
B=Basso (X<5)
A=Alto (X>=5)
ESERCIZIO 2
ID
1
2
3
4
5
6
7
8
9
10
11
12
13
A
MB
MB
MB
MB
B
B
B
M
M
M
A
A
A
B
B
B
B
B
B
B
B
A
A
A
A
A
A
C
X
X
X
X
Y
Y
Y
X
X
X
Y
Y
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
Y
G

4
<
2
0
12
>=
5
6
0,1546
<
4
0
13
>=
3
6
0,36
<
4
1
16
>=
3
5
0,1307
<
4
3
18
>=
3
3
0,0037
<
5
3
23
>=
2
3
0,0349
<
7
3
24
>=
0
3
0,3178
<
7
5
>=
0
1
0,0912
Risulta conveniente splittare il dataset distinguendo fra
valori di A<12 e valori di A>=12.
ESERCIZIO 2

A questo punto splittiamo su B.
B
X
Y
G

2
<
0
1
3
>=
3
5
0,0699
<
0
2
7
>=
3
4
0,152
<
0
3
8
>=
3
3
0,2516
<
1
4
9
>=
2
2
0,0728
<
2
5
>=
1
1
0,0248
Risulta conveniente splittare il dataset distinguendo fra
valori di B<7 e valori di B>=7.
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 3
FPR
Soglie
Classe reale
0,1
1
0,2
1
0,25
1
0,3
1
0,4
0
0,6
0
0,7
0
0,8
1
0,9
1
0,9
1
0,97
1
Soglie
Classe reale
0,1
0
0,2
1
0,3
0
0,4
0
0,6
1
0,7
1
0,75
1
0,8
1
0,85
0
0,9
1
0,97
1
TP
TN
7
6
5
4
4
4
4
3
1
1
0
FP
0
0
0
0
1
2
3
3
3
3
3
FN
3
3
3
3
2
1
0
0
0
0
0
1
2
3
4
4
4
4
5
7
7
8
FPR
TP
TN
7
6
6
6
5
4
3
2
2
1
1
FP
1
1
2
3
3
3
3
3
4
4
4
FN
3
3
2
1
1
1
1
1
0
0
0
0
1
1
1
2
3
4
5
5
6
6
TPR
1
1
1
1
1
0,666667
0,333333
0
0
0
0
0
0
1
0,875
0,75
0,625
0,5
0,5
0,5
0,5
0,375
0,125
0,125
0
0
TPR
1
0,75
0,75
0,5
0,25
0,25
0,25
0,25
0,25
0
0
0
0
1
1
0,857143
0,857143
0,857143
0,714286
0,571429
0,428571
0,285714
0,285714
0,142857
0,142857
0
ESERCIZIO 3
1.2
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
1.2
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
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

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

ESERCIZIO 4

Sappiamo che:
 N

log  L  | X    log   p  xi |   
 i 1

 N M

 log     k pk  xi |  k  
 i 1 k 1

M

  log    k pk  xi |  k  
i 1
 k 1

N
ESERCIZIO 4

Introduciamo le variabili aleatorie yik

log L  | X ,Y

   y
N
M
i1 k 1
ik
 
log pk xi , yik  1, k

Il passo E dell’algoritmo corrisponde al calcolo di:



E  yik | xi , k  g 1   1 p yik  1| xi ,k  g 1  0  p yik  0 | xi , k  g 1


 p yik  1| xi ,k  g 1   ik  g 

ESERCIZIO 4
 ik
g
 E  yik | xi ,   g 1  


p xi , yik  1|   g 1

p yik  1|  
M


g 1
 p  x | y  1,   

 p  x | y  1,   
 g 1
p
y

1|

 ij
j 1
Ma ricordiamo che

p xi |   g 1

g 1
k
i
ik
g 1
j
i
ij
ESERCIZIO 4

Il passo M

Definizione dei vincoli:
M

k 1
k
1
Sempre vero
ESERCIZIO 4

Utilizziamo, quindi, i moltiplicatori di Lagrange
M


(g)
( g 1)
f  ,    Q  ,
     j  1
 j 1

N M
 M (g) 
(g)
   ik log  pk xi yik  1, k       j  1
i 1 k 1
 j 1



ESERCIZIO 4

Derivando su π
N
f  ,  
 ir  g 
 ...    g     0
 r
i 1  r
 r
g

1
N



i 1
N
 rg 
g
i 1
N M
g

 ij
i 1 j 1
ir
f  ,   M  g 
  j 1  0

j 1
g

 ir
M
  ij
j 1
g
M


 ...   p yij  1| xi ,  g 1  1
j 1
r
g
1

N
N
g

 ir
i 1
ESERCIZIO 4

Derivando sui parametri di θ, e ricordando che

Allora:


N
M
 
k
j i 1 k 1

 jk
N
M
(g)
ik
  ik
i 1 k 1
(g)
log  p k xi y ik  1,  k   0
log  pk xi yik  1, k  

 jk
N
  ik
i 1
(g)

 3
log   p k xi ,t  tk
 t 1
  0
