4.2 Classificatori bayesiani
4.2.3 Naive Bayes
Normalmente con una sola caratteristica estratta dall’oggetto da classificare non `e possibile ottenere una precisione elevata di classificazione. Fortunatamente le caratteristiche che si possono estrarre da una immagine sono molteplici.
Siano indicate con xj, con j = 1, . . . , m tali caratteristiche. `E molto importante notare che gli eventi osservati xj con cui costruire il classificatore bayesiano devono essere eventi indipendenti (indipendenza condizionale), altrimenti il teorema di Bayes non risulta pi`u valido (uno dei limiti dei classificatori bayesiani): per esempio non si possono unire classificatori che analizzino parti dell’immagine in comune o non si pu`o unire lo stimatore “`e arancione” insieme a “`e non rosso”.
L’assunzione Naive Bayes (o idiot Bayes) sfrutta l’ipotesi semplificativa di indipendenza degli attributi (feature) osservati:
in questo caso date m variabili osservate x1. . . xmla probabilit`a che l’evento yi si verifichi sar`a:
p(x1. . . xm|yi) =
m
Y
j=1
p(xj|yi) (4.12)
4.3 LDA
Un esempio di riduzione delle dimensioni del problema a scopo di classificazione `e la Analisi di Discriminante Lineare Linear Discriminant Analysis (Fisher, 1936).
Se si analizza il funzionamento di PCA (sezione2.10.1), questa tecnica si limita a massimizzare l’informazione non distin-guendo tra loro le eventuali classi che compongono il problema: PCA non considera il fatto che i dati siano rappresentativi di diverse categorie. PCA non `e un vero classificatore ma `e una tecnica utile a semplificare il problema, riducendone le di-mensioni. LDA cerca invece di massimizzare sia l’informazione discriminatoria tra le classi che l’informazione rappresentata dalla varianza.
Nel caso di un problema di due classi, il miglior classificatore bayesiano `e quello che permette di individuare il margine di decisione (decision boundary) formato dall’ipersuperficie lungo la quale la probabilit`a condizionata delle due classi `e uguale.
µ1
µ2
w · x = c
Figura 4.2: Analisi di Discriminante Lineare.
Se si forza l’ipotesi che le due classi del problema binario abbiano distribuzione gaussiana multivariata e uguale matrice di covarianza Σ `e facile dimostrare che il margine di decisione bayesiano, equazione (4.11), diventa lineare.
In LDA viene fatta pertanto l’ipotesi di omoschedasticit`a e, sotto questa ipotesi, si vuole ottenere un vettore w che permetta di proiettare lo spazio n-dimensionale degli eventi in uno spazio scalare che per`o massimizzi la separazione tra le classi e permetta di separarle linearmente attraverso un margine di separazione del tipo
w>x = c (4.13)
Per determinare questa superficie di separazione si possono usare diverse metriche. Sotto il termine LDA attualmente confluiscono diverse tecniche dove la Discriminante di Fisher (Fisher’s Linear Discriminant Analysis) risulta la pi`u diffusa in letteratura.
Si pu`o dimostrare che la proiezione che massimizza la separazione tra le due classi dal punto di vista “statistico”, ovvero l’iperpiano di decisione, si ottiene con
w = Σ−1(µ1− µ2) (4.14)
e il valore di separazione ottimo si trova a met`a strada tra le proiezioni delle due medie
c = w(µ1− µ2)/2 (4.15)
nel caso in cui le probabilit`a a priori dei due insiemi siano identiche.
Questo margine di decisione `e la soluzione alla massima verosomiglianza in caso di due classi con distribuzione uniforme e stessa covarianza.
4.4 SVM
LDA si pone come obiettivo quello di massimizzare la distanza statistica tra le classi ma non cerca di valutare quale sia l’effettivo margine di separazione tra di loro.
w · x + b = −1 w · x + b = +1
Figura 4.3: Iperpiano di separazione tra due classi ottenuto attraverso SVM. I punti sul margine (tratteggiato) sono i Support Vectors.
SVM [CV95], come LDA, permette di ottenere un classificatore lineare basato su una funzione discriminante nella stessa forma mostrata in equazione (4.5). SVM per`o va oltre: l’iperpiano ottimo in Rn viene generato in maniera tale da sepa-rare “fisicamente” (decision boundary) gli elementi del problema di classificazione binario ovvero si pone come obiettivo quello di massimizzare il margine di separazione tra le classi. Questo ragionamento premia molto per quanto riguarda la generalizzazione del classificatore.
Siano pertanto definite come classi di classificazione quelle tipiche di un problema binario nella forma yi= {+1, −1} e si faccia riferimento all’iperpiano di formula (4.4). Supponiamo che esistano dei parametri (w0, b0) ottimi tali che soddisfino il
vincolo
xi· w0+ b0≥ +1 per yi= +1
xi· w0+ b0≤ −1 per yi= −1 (4.16)
ovvero, in forma pi`u compatta:
yi(xi· w0+ b0) − 1 ≥ 0 (4.17)
per ogni (yi, xi) campioni forniti durante la fase di addestramento.
Si pu`o supporre che esistano, per ognuna delle categorie, uno o pi`u vettori xi dove le disuguaglianze (4.17) diventano uguaglianze. Tali elementi, chiamati Support Vectors, sono i punti pi`u estremi della distribuzione e la loro distanza rappresenta la misura del margine di separazione tra le due categorie.
La distanza ρ punto-piano (cfr. eq.(1.49)) vale
ρ = kw · x + bk
kwk (4.18)
Dati due punti di classe opposta che soddisfino l’uguaglianza (4.17), il margine pu`o essere ricavato dall’equazione (4.18), e vale
ρ = 2
kw0k (4.19)
Per massimizzare il margine ρ dell’equazione (4.19) bisogna minimizzare la sua inversa, ovvero min
w,b
1
2kwk2 (4.20)
sotto la serie di vincoli espressi dalla diseguaglianza (4.17). Questo `e quello che viene definito come problema di ottimizzazione primale in forma standard dell’SVM.
Questa classe di problemi (minimizzazione con vincoli come disuguaglianze o primal optimization problem) si risolvono utilizzando l’approccio di Karush-Kuhn-Tucker che `e il metodo dei moltiplicatori di Lagrange generalizzato a disuguaglianze.
Attraverso le condizioni KKT si ottiene la funzione lagrangiana:
L(w, b, α) = 1
2kwk2−X
i
αi(yi(xi· w + b) − 1) (4.21)
da minimizzare in w e b e massimizzare in α. I pesi αi ≥ 0 sono i moltiplicatori di Lagrange. Dall’annullamento delle derivate parziali si ottiene
∂L
∂b = 0 →X
yiαi = 0 (4.22)
∂L
∂w = 0 → w =X
αiyixi (4.23)
Sostituendo tali risultati (le variabili primali) all’interno della lagrangiana (4.21) questa diventa funzione dei soli moltiplica-tori, i dual, da cui la forma duale di Wolfe:
Ψ(α) =X αi−1
2 X
i
X
j
αiαjyiyjxi· xj (4.24)
sotto i vincoli αi ≥ 0 e P αiyi = 0. Il massimo della funzione Ψ calcolato su α sono gli αi associati a ogni vettore di addestramento xi. Tale massimo permette di trovare la soluzione del problema originale.
Su questa relazione sono valide le condizioni KKT tra le quali `e di notevole importanza il vincolo, detto di Complementary slackness,
αi(yi(xi· w + b) − 1) = 0 (4.25)
Questo vincolo dice che il massimo della lagrangiana o `e sul bordo del vincolo (αi6= 0) o `e un minimo locale (αi= 0). Come conseguenza solo gli αi sul limite sono non nulli e contribuiscono alla soluzione: tutti gli altri campioni di addestramento sono di fatto ininfluenti. Tali vettori, associati agli αi> 0, sono i Support Vectors.
Risolvendo il problema quadratico (4.24), sotto il vincolo (4.22) e αi≥ 0, i pesi che presentano αi6= 0 saranno i Support Vectors. Tali pesi, inseriti nelle equazioni (4.23) e (4.25), porteranno a ricavare l’iperpiano di massimo margine.
Il metodo pi`u usato per risolvere questo problema QP `e il Sequential Minimal Optimization (SMO ). Per una trattazione approfondita delle tematiche legate a SVM si pu`o fare riferimento a [SS02].