Analisi di Algoritmi di Classificazione - Tesi Russo Alessio

R

2. I dati di apprendimento, usati dagli algoritmi per estrapolare un modello nella fase di

apprendimento, sono etichettati attraverso un valore numerico . In particolare per

∈

y R

ogni valore diverso di si hanno diverse classi: per esempio identicando con il numero

y T

di classi, allora .

∈ {1, · · · }

y S = , T

3. L'insieme dei dati di apprendimento sono identicati da una matrice , dove

×d

n

∈

X i

i

R

i

identica l' -esima classe di punti , e è il numero di punti per quest'ultima.

⇒ ∈

i i S n

i

Di conseguenza ogni dato può essere visto come un vettore trasposto, quindi riga della

matrice .

X i

Si sono fatte inoltre alcune ipotesi sull'analisi della complessità computazionale: operazioni

quali l'inversione di una matrice, la sua decomposizione attraverso il teorema spettrale o il

calcolo del determinante sono considerate operazioni con costo , con numeri di dati.

3

O(n ) n

Queste possono essere ridotte di complessità facendo uso di decomposizioni quali la decompo-

sizione QR o quella di Cholesky, che ciononostante sono comunque e .

3 2

O(n ) Ω(n )

2.3 Metodo Kernel

In generale la funzione di classicazione risulta avere curve di separazione lineari: risulte-

h

rebbe utile avere un metodo per renderle non lineari.

Una procedura per ottenere ciò è di applicare una trasformazione non lineare d m

→

:

φ R R

sui dati di apprendimento: è possibile che sul nuovo spazio vettoriale questi dati siano

m

R

linearmente separabili, risultando quindi in curve di separazione non lineari nello spazio .

d

R

Solitamente utilizzare questo metodo risulta molto laborioso in termini di tempi di elaborazio-

ne: basti considerare che la trasformazione bisogna eettuarla per ogni dato, e le dimensioni

φ

di questi potrebbero essere elevate.

Attraverso il metodo Kernel si evitano lunghi tempi di elaborazione attraverso alcune osserva-

zioni. 7

Si consideri l'insieme delle funzioni esprimibili come prodotto scalare e sia una di

Ĥ K

queste funzioni, , segue che:

d d

× →

K : R R R hφ(x ), φ(x

K(x , x ) = )i

1

1 2 2 Ĥ

È possibile esprimere senza dover utilizzare la trasformazione ? attraverso la condizione di

K φ

Mercer ciò è possibile sotto alcune ipotesi:

simmetrica.

1. , x ) = K(x , x )

K(x 1 2 2 1

2. K deve essere semi-denita positiva, ovvero deve avere tutti gli autovalori non negativi.

Sotto queste condizioni tale che:

d m

∃φ →

: R R X T d

∀x ∈

, x ) = λ φ(x ) φ(x ) , x

K(x R

i

1 2 1 2 1 2

i

Di conseguenza la funzione Kernel mi induce questa trasformazione .

φ

Il quesito è come si può applicare questo risultato negli algoritmi: in primo luogo si appli-

ca la trasformazione non lineare sui dati usati dal metodo in questione. Successivamente i

vengono sostituiti da , permettendo una riduzione del

prodotti scalari hφ(x ), φ(x )i K(x , x )

1 2 1 2

Ĥ

costo computazionale.

In questo lavoro i principali Kernel utilizzati sono:

, questo Kernel permette di vericare se l'algoritmo

1. Kernel lineare: T

, x ) = x

K(x x

1 2 2

1

è stato implementato in maniera corretta, confrontandone i risultati con l'algoritmo in

forma non Kernel, i quali dovrebbero risultare uguali.

2. Kernel lineare ane: , utile nel caso i dati non siano stati centrati,

T

K(x , x ) = 1 + x x

1 2 2

1

risolve il problema grazie all'oset dato da .

1

3. Kernel polinomiale: , induce delle trasformazioni polinomiali e

T p

K(x , x ) = (1 + x x )

1 2 2

1

permette di avere curve di separazione non lineari.

22

kx −x k

4. Kernel gaussiano (radiale): , induce una trasformazione

K(x , x ) = exp 1 2

1 2 2

2σ

, con di dimensione innita.

d →

φ : H̃ H̃

R 8

Il Kernel gaussiano permette di lavorare in uno spazio a innite dimensioni ed è facilmente

dimostrabile: per semplicità si consideri , segue :

2

2σ = 1

22 T T T

− k −

exp(−kx x ) = exp(−(x x + x x 2x x ))

1 2 1 2 2

1 2 1

Il termine può essere sviluppato grazie alla Serie di Taylor centrata in 0:

T x

exp(2x )

2

1 ∞

1 1

X

T T T 2 T k

x ) =1+ 2x x + (2x x ) + (2x x )

exp(2x 2 2 2 2

1 1 1 1

2 k!

k=3

Si può quindi trovare una trasformazione siatta:

φ  

1

√

2x

 

 

T ·

φ(x) = exp(−x x)  

2 T

x x

√

 

2 ..

 

.

Grazie allo sviluppo in Serie di Taylor si ha che è una funzione vettoriale di innite compo-

φ

nenti, inducendo quindi uno spazio di dimensione innita.

Possiamo inne notare che ritroviamo il Kernel gaussiano:  

1

√

√ 2x

 

2

 

T T T 2 T ·

− · ···

φ(x ) φ(x ) = exp(−x x x x ) x

2x x

1 √  

1 2 1 2

1 2 1 1

1 2 T

x x

2 √

 

2

2

2 ..

 

.

∞ 1

X

T T T k

− ·

= exp(−x x x x ) (2x x )

1 2 2

1 2 1

k!

k=0

22

− k

= exp(−kx x )

1 2 9

2.4 Regularized Least Squares Classier

Il metodo Regularized Least Square Classier (RLSC) è un discriminante lineare basato sul

loss

metodo dei minimi quadrati. Il metodo dei minimi quadrati fa uso di una funzione di costo (

function l . Il fatto di usare una funzione quadratica permette

) del tipo 2

−

= (y f (x))

(y, f (x))

di avere un'unica soluzione essendo un problema di minimizzazione di una funzione convessa.

Nel caso binario la classicazione risulta essere la miglior funzione che meglio divide i valori

delle due classi dati i punti, possiamo quindi valutare l'appartenenza a una classe guardandone

il segno. Il problema risulta essere il seguente: n

1 X

T T 22

−

x), x

h(x) = sgn(f (x)) = sgn( ŵ ŵ = min (y w ) + λkwk

k k

n

w k=1

è la normale della varietà lineare, una retta nel caso binario, che meglio separa le due classi

ŵ

di punti. Questa viene ricavata attraverso la minimizzazione di un problema convesso: di con-

seguenza il risultato esiste ed è unico.

Si noti che è stato introdotto un termine di regolarizzazione . Questo serve per avere un

λ

parametro con cui controllare il risultato ed evitare problemi quali il sovradattamento.

Per capire le dinamiche di cosa accade si osservi che

nel caso di classicazione binaria misura la

T

||

ŵ xk 2

distanza del punto alla retta di separazione data da

x

, di conseguenza il segno di questa mi da l'appar-

h(x)

tenenza a una delle due classi.

Più articolato risulta il caso di classicazione mul-

ticlasse, la quale risulta fatta con uno dei seguenti

metodi:

Classicazione uno contro tutti

1. : vengono con-

siderati problemi di minimizzazione del caso

T Figura 2.1: RLSC: classicazione

binario sopra citato. Per ogni problema si sce- mi indica l'appartenenza

y(x) = f (x)

glie una classe di punti appartenenti a una pri- a una classe. è l'oset rispetto

w

0

ma categoria, le restanti classi vengono

−

T 1 l'origine.

considerate appartenenti all'altra categoria. Si

ottengono classicatori.

Θ(T )

Classicazione uno contro uno

2. : Si considerano

due classi di punti alla volta e per ognuno di

essi viene ricavato un classicatore. Si ottengono

classicatori.

2

Θ(T ) 10

Entrambi i casi mostrano vantaggi e svantaggi: 1

In termini di tempi di elaborazione il metodo

• vs all risulta più veloce in fase di classicazio-

ne a causa del numero lineare di classicatori

1

rispetto al numero di classi, mentre la tecnica

vs 1 ne ha un numero quadratico.

Discutendo della precisione di classicazione,

• entrambi i metodi hanno zone ambigue di classi-

cazione o non separano correttamente le clas-

si di punti, come in gura 2.2. Ciò è meno

1 vs 1

evidente con la strategia .

Figura 2.2: Classicazione uno contro

tutti: le curve di separazione non sono 1 vs all

Per il progetto si è fatto uso del metodo :

ottimali consideriamo la -esima classe di punti etichettata con

i

come prima classe, per esempio con valore . Le restanti classi di punti sono etichettate come

1

. Si applichi questo ragionamento per ogni classe e si cerchi i classicatori che rendono minima

0

la somma dei singoli problemi binari, si ottiene:

n

T 1

X

X Ti 2 22

− k

(y w x ) + λkw

min k k i

n

,··· ,w

w 1 T i=1 k=1

Si dimostra che questo problema equivale a trovare una matrice tale che:

×d

T

∈

W R

T T · · ·

(X X + nλI )W = X Y, W = w w

w

d 1 2 T

Dove è una matrice con colonne ove

n×T

∈

Y T

R  Se appartiene alla -esima classe

1 x j

 i

Y =

ij altrimenti

0



Inne il classicatore risulta essere: (2.1)

−1

T T T

= arg max W x, W = (X X + nλI ) X Y

h(x) d

i=1,··· ,T

Per quanto riguarda le complessità computazionali si ricava:

1. Costo computazionale in fase di apprendimento per via delle operazioni

2

O(d(dn+d +nT ))

eettuate sulle varie matrici.

2. Costo computazionale in fase di classicazione .

Θ(T d)

11

2.4.1 Kernel Regularized Least Squares Classier

Consideriamo una trasformazione non lineare applicata sui dati in questione.

d →

φ : H

R

La nostra matrice dei punti applicando la trasformazione diventa una nuova matrice,

X φ

denominata . Si ha:

S 1 T

T T −

⇒ S (Y SW)

(S S + nλI )W = S Y W =

d nλ

Ponendo si osserva:

1 −

α = (Y SW)

nλ T T T T T T

⇒

W = S α (S S + nλI )S α = S (SS + nλI )α = S Y

n n

−1

T

α = (SS + nλI ) Y

n

Essendo il classicatore diventa:

T

SS = K −1

T T T T T T

= arg max W x = (x W) = (x S (K + nλI ) Y)

h(x) n

i=1,·&m