Support Vector Machines e apprendimento statistico per l'analisi non parametrica della regressione: nuovi sviluppi teorici, software e applicazioni finanziarie

38Capitolo 4. Support Vector Machines
Spazio
Spazioφ
delle
di origine
caratteristiche
dei dati
y’
Regressione lineare
Figura 4.1: La struttura di un modello SVM.
4.1.1 Derivazione del problema di ottimo
d
,y),...,(x,y) con x
Consideriamo un campione di n dati (x∈ Re
11nni
y∈R. Per generare il processo di apprendimento, la SVM opera una tra-
i
sformazione non lineare dei dati di input xsecondo una mappaturaφ in
i
uno spazio di dimensionalità superiore definito a priori, detto spazio delle
caratteristiche,chepuòancheesseredidimensionein finita. Non indaghe-
remo per il momento la natura di tale trasformazione. Per semplicità, nei
successivi problemi di programmazione quadratica utilizzeremo la notazione
D
¯ x∈ Rper i vettoriφ(x) trasformati, dove d ¿ D ≤∞.N e l l os p a -
ii
zio delle caratteristiche così definito viene quindi stimata una regressione
d
lineare. Essa risulta non lineare nello spazioRdi partenza e deve fornire
una buona approssimazione dello scalare yassociato. La figura 4.1 illustra
i
schematicamente questo approccio.
Formalmente è possibile formulare il problema come la stima della se-
guente regressione lineare nello spazio delle caratteristiche
0
f(w,¯ x,b)=¯ xw+b(4.1.1)
i
i
dove
• xè un generico vettore colonna d-dimensionale,
i
• ¯ xè un generico vettore colonna D-dimensionale ottenuto dalla tra-
i
sformazione non lineare dix,
i
• w è un vettore colonna D-dimensionale di coefficienti angolari,
• b è l’intercetta scalare.
4.1. La struttura dei modelli SVM39
Il problema previsivo sarà quello di individuare dei parametri della re-
gressione che garantiscano buone proprietà sia in termini di rischio empi-
rico che in termini di errore di generalizzazione, in modo da ottenere un
approssimatore con un basso rischio atteso associato.
Per quanto riguarda la componente di rischio empirico, la funzione di
perdita utilizzata per misurare la differenza fra approssimazione e target è
la funzioneε-insensitive (1.3.4).
|y−f(w,¯ x,b)|
ii
ε
Per comprendere la maniera in cui i modelli SVM gestiscono l’errore di
generalizzazione è necessario considerare il seguente Teorema, desumibile
2
dall’impianto teorico proposto da Vapnik.
D
Teorema 4.1.1 Sia f(w,¯ x,b),w∈W, una funzione di regressione linea-
i
re definita nello spazio delle caratteristiche e k¯ xkD<∞. Allora la capacità
`
2
2
della funzione f(w,¯ x,b) è direttamente proporzionale a kwk.
D
i
`
2
Osservazione 4.1.2 Una volta stabilita la trasformazione non lineare da
applicare ai dati, è quindi possibile gestire la relazione inversa fra errore
empirico ed errore di generalizzazione illustrata nella figura 3.1 ponendo un
vincolo superiore alla norma del vettore dei coefficienti angolari. Al suo au-
mentare, la funzione considerata presenterà una misura di capacità (funzione
di crescita, dimensione VC, dimensione fat shattering) crescente, quindi una
maggiore complessità. Di conseguenza l’errore empirico valutato sui dati at-
traverso i quali il modello viene stimato tenderà a diminuire, mentre l’errore
di generalizzazione, direttamente dipendente dalla misura di capacità della
funzione, tenderà ad aumentare.
Fissata la funzione di perdita con cui misurare l’errore empirico, nel
nostro caso la funzioneε-insensitive, possiamo quindi applicare il princi-
2
3
pio SRM imponendo vincoli crescenti al valore che kwkpuò assumere.
D
`
2
In questo modo siamo in grado di generare una struttura ammissibile di
sottoinsiemi di funzioni con misura di capacità crescente.
Cortes e Vapnik [7] introducono il problema mediante un’impostazione
2
analogamapiùsemplice,inserendoilvaloredikwkDdirettamentenellafun-
`
2
zione obiettivo da minimizzare e non come vincolo superiore al valore della
norma del vettore di coefficienti angolari w del modello lineare (4.1.1). Per
stimare un modello SVM occorre quindi minimizzare la seguente funzione
obiettivo
Ã!
nn
XX
1C1C
∗0∗00∗
Φ(w,ξ,ξ)=ww+ξ+ξ=ww+u(ξ+ξ)
ii
2n2n
i=1i=1
(4.1.2)
2
Vapnik [26] pag. 413.
3
Vapnik [26] pag. 428.
40Capitolo 4. Support Vector Machines
dove
• C è uno scalare positivo assegnato a priori che misura il peso relativo
tra rischio empirico e rischio di generalizzazione del modello,
• u è un vettore colonna n-dimensionale di unità,
∗
•ξeξ sono vettori colonna n-dimensionali di variabili di scarto i cui
elementi misurano l’errore di stima mediante la funzioneε-insensitive
nel modo seguente.
½
0se y−f(w,¯ x,b)≤ε
ii
∗
ξ=(4.1.3)
i
y−f(w,¯ x,b)−ε altrimenti
ii
½
0se f(w,¯ x,b)−y≤ε
ii
ξ=(4.1.4)
i
f(w,¯ x,b)−y−ε altrimenti
ii
L’utilizzodellafunzionediperditaε-insensitivepermisurareladifferenza
fra output del modello e target implica la costruzione intorno a quest’ultimo
di una banda di insensibilità di ampiezza 2ε dettaε-tubo. Vengono consi-
derati affetti da errore solamente gli output che cadono all’esterno di tale
banda.
All’aumentare della capacità della SVM considerata è possibile ridurre
il rischio empirico valutato sui dati di training e sappiamo dal Teorema
2
4.1.1 che la capacità dipende dal valore della norma kwk. Nella funzione
D
`
2
obiettivo(4.1.2)ilvalorediC serveproprioacontrollaretalenorma. Infatti,
all’aumentare del valore di C, sarà sempre maggiore il peso attribuito al
0
w per ridurne il
rischio empirico e quindi converrà aumentare il valore di w
valore. Al contrario, al diminuire del valore di C, sarà sempre maggiore il
peso attribuito al rischio di generalizzazione e quindi converrà diminuire il
0
valore di ww per ridurne il valore. Un valore molto elevato di C significa
chiedere al modello una perfetta approssimazione dei dati di training forniti.
Per ottenere l’espressione analitica di un modello SVM occorre dunque
risolvere il problema di ottimo quadratico

PP
1Cn∗n
0
minww +(ξ+ξ)
ii
2ni=1i=1



∗0

ξ≥y−¯ xw−b−εi=1,...,n
i
ii


0
ξ≥¯ xw +b−y−εi=1,...,n(4.1.5)
i
i
i



∗

ξ≥ 0i=1,...,n

i




ξ≥ 0i=1,...,n
i
4.1. La struttura dei modelli SVM41
che può essere riscritto in forma matriciale

1C∗
00
minww +u(ξ+ξ)
2n



∗

¯
ξ=y−Xw−bu−εu


¯
ξ=Xw +bu−y−εu(4.1.6)



∗

ξ= [0]





ξ= [0]
dove
• X è la matrice di ordine (n,d)deidatiditrainingdelmodellonelloro
spazio di origine,
¯
•X è la matrice di ordine (n,D) dei dati di training del modello ”map-
pati” nello spazio delle caratteristiche,
• yèilvettorecolonnan-dimensionale dei target associati ai dati di
trainingX osservati.
Ognirigadellematricicorrispondeadunvettoredidatixe¯ xcomposto
ii
rispettivamente da dedaD elementi esplicativi. Ogni elemento del vettore
y corrisponde al target osservato yassociato ad ogni riga diX.
i
Assumiamo che il problema sia ammissibile e che quindi esista sempre
∗
una soluzione. Siccome la funzione obiettivoΦ(w,ξ,ξ) è quadratica e con-
vessa ed è definita su un insieme convesso di disequazioni lineari, il minimo
assoluto sarà sempre unico.
Costruiamo la funzione Lagrangiana
1C
∗∗∗00∗
L(w,ξ,ξ,b,α,α,γ,γ)=ww+u(ξ+ξ)+
2n
¡¢
∗0∗
¯
+αy−Xw−bu−εu−ξ+
¡¢
0∗0∗0
¯
+αXw+bu−y−εu−ξ−γξ−γξ
(4.1.7)
dove
∗∗
•α,α,γ,γ sono vettori colonna n-dimensionali di moltiplicatori di
Lagrange non negativi.
Siccome non è molto agevole risolvere direttamente il problema (4.1.6)
attraverso la sua funzione Lagrangiana, si preferisce considerare il suo pro-
blema duale. Definiamo quindi la funzione duale
∗∗∗∗∗
W(α,α,γ,γ)= infL(w,ξ,ξ,b,α,α,γ,γ).
∗
w,ξ,ξ,b
42Capitolo 4. Support Vector Machines
Perricavarlaanaliticamenteoccorreimporrel’azzeramentodellederivate
prime rispetto alle variabili argomento dell’inf.
∂L
0∗
¯
=w−X(α−α)=[0]
∂w
∂LC
∗∗
=u−α−γ=[0]
∗
∂ξn
∂LC
=u−α−γ=[0]
∂ξn
∂L
∗00
=−αu+αu=0
∂b
Tali condizioni del primo ordine possono essere riscritte nel modo se-
guente.
0∗
¯
w =X(α−α)
CC
∗∗∗∗∗
Cu=α+γ=⇒α=u−γ=⇒α5u
nn
(4.1.8)
CC
Cu=α+γ=⇒α =u−γ =⇒α5u
nn
0∗0
αu =αu
Sostituendo la prima delle condizioni (4.1.8) all’interno della funzione
Lagrangiana, si ottiene la funzione duale.
1
0
∗∗∗0∗∗∗0∗0
¯¯
W(α,α,γ,γ)=(α−α)XX(α−α)+(α+γ)ξ+(α+γ)ξ +
2
0
∗0∗0∗∗0∗0∗0∗
¯¯
+αy−αXX(α−α)−bαu−εαu−αξ+
0
00∗000
¯¯
−αy +αXX(α−α)+bαu−εαu−αξ +
∗0∗0
−γξ−γξ
∗
Dopo le opportune semplificazioni i moltiplicatoriγeγ scompaiono la-
sciando l’espressione
1
0
00
∗∗0∗∗∗
¯¯
W(α,α)=−(α−α)XX(α−α)+(α−α)y−ε(α+α)u.
2
(4.1.9)
Considerando le ultime tre condizioni (4.1.8) ed il vincolo di non nega-
tività sui moltiplicatori di Lagrange, si perviene infine al problema duale.

0
100
∗0∗∗∗
¯¯
max−(α−α)XX(α−α)+(α−α)y−ε(α+α)u
2



0
∗

(α−α)u=0
(4.1.10)
∗C

[0]5α5u

n



C
[0]5α5u
n
4.1. La struttura dei modelli SVM43
Poiché abbiamo assunto che il problema primale sia solubile, lo è anche il
problema duale. Per ottenere la soluzione occorrerà trovare i valori degli ele-
∗
menti dei vettoriαeα che massimizzano la prima equazione del problema
duale (4.1.10) ed il valore dell’intercettab. In letteratura sono stati proposti
differenti algoritmi di ottimo per risolvere questo problema. Nel capitolo
successivo illustreremo il metodo studiato e implementato in questo lavoro.
4.1.2 Alcune caratteristiche fondamentali
Riprendiamo la funzione Lagrangiana (4.1.7) ed applichiamo le condizioni
4
di Karush-Kuhn-Tucker (KKT) al nostro problema. Nel punto di ottimo
devono valere le condizioni
∗∗
γˆξ=0,i =1,...,n(4.1.11)
ii
ˆγξ=0,i =1,...,n(4.1.12)
ii
³´
∗0∗
ˆ
¯
αˆy−Xˆ w−b−ε−ξ=0,i =1,...,n(4.1.13)
ii
ii
³´
0∗
¯ˆ
αˆXˆ w +b−y−ε−ξ=0,i =1,...,n(4.1.14)
ii
ii
¯¯
doveXèlai-esima riga della matriceX ed il simbolo ˆ indica i parametri
i
ottenuti risolvendo il problema (4.1.6).
Una volta stimato un modello SVM possiamo trovarci di fronte a tre casi
differenti.
¯
1. La stima fornita per una generica osservazioneXmappata nello spa-
i
zio delle caratteristiche cade all’interno dell’ε-tubo ed il valore dei
∗
moltiplicatori di Lagrange ˆαe ˆαè zero.
i
i
∗∗
ˆ
¯
y−Xˆ w−b−ε< 0,ξ=0 =⇒ ˆα=0
ii
ii
¯ˆ
Xˆ w +b−y−ε< 0,ξ=0 =⇒ ˆα=0
iii
i
¯
2. LastimafornitaperunagenericaosservazioneXmappatanellospazio
i
delle caratteristiche cade sul margine superiore dell’ε-tubo o sopra ad
∗
esso (sovrastima) ed il valore del moltiplicatore di Lagrange ˆαè zero
i
mentre quello di ˆαpuò essere positivo.
i
∗∗
¯ˆ
y−Xˆ w−b−ε< 0,ξ=0 =⇒ ˆα=0
ii
ii
ˆ
¯
Xˆ w +b−y−ε−ξ=0,ξ≥0=⇒ ˆα≥ 0
iii
ii
¯
3. LastimafornitaperunagenericaosservazioneXmappatanellospazio
i
delle caratteristiche cade sul margine inferiore dell’ε-tubo o sotto ad
4
Vapnik [26] pag. 393-394.
44Capitolo 4. Support Vector Machines
esso (sottostima) ed il valore del moltiplicatore di Lagrange ˆαè zero
i
∗
mentre quello di ˆαpuò essere positivo.
i
∗∗∗
ˆ
¯
y−Xˆ w−b−ε−ξ=0,ξ≥0=⇒ ˆα≥ 0
ii
iii
¯ˆ
Xˆ w+b−y−ε< 0,ξ=0 =⇒ ˆα=0
iii
i
Solo quei vettori di dati che generano una stima sul margine o all’esterno
∗
dell’ε-tubo possono quindi avere associati moltiplicatori di Lagrangeαo
i
αdiversi da zero. Tali vettori sono chiamati vettori di supporto (support
i
vectors) e, come vedremo in seguito, la costruzione dell’algoritmo SVM è
∗
basata solamente su di essi. I vettori associati a moltiplicatori ˆα=ˆα=0
i
i
sono invece irrilevanti nella costruzione del processo di apprendimento. Non
∗
può mai comunque accadere cheα6=0eα6=0 , poiché una stima non può
i
i
ovviamente stare contemporaneamente al di sopra ed al di sotto dell’ε-tubo.
Prendiamo una stima che cade esattamente su un margine dell’ε-tubo,
ad esempio quello superiore. Considerando lo scarto (4.1.4), le condizioni di
KKT (4.1.12) e (4.1.14) e la terza fra le condizioni (4.1.8), si ricava che
¯ˆ
Xˆ w +b−y−ε=0,ξ=0 =⇒ ˆα≥ 0, ˆγ≥ 0
iii
ii
CC
ˆα=− ˆγ=⇒ ˆα≤
ii
i
nn
Per una stima che cade invece oltre un margine dell’ε-tubo, ad esempio
quello superiore, otteniamo
¯ˆ
Xˆ w+b−y−ε−ξ=0,ξ>0=⇒ ˆα≥ 0, ˆγ=0
iii
iii
CC
ˆα=− ˆγ=⇒ ˆα=
ii
i
nn
Con la stessa procedura è possibile ricavare risultati analoghi per il margine
inferiore dell’ε-tubo.
Di conseguenza, i vettori di dati che generano stime all’interno dell’ε-
∗
tubo avranno associati moltiplicatori ˆα=ˆα=0 , quelli che generano stime
i
i
oltre il margine dell’ε-tubo avranno associati un moltiplicatore nullo ed un
(∗)
C
moltiplicatore ˆα=, quelli che generano stime esattamente sul margine
in
avranno associati un moltiplicatore nullo ed uno che può assumere valori
(∗)
C
0≤ ˆα≤.
i
n
Per i problemi di regressione SVM la percentuale di vettori di sup-
porto viene regolata dal valore diε all’interno della funzione di perdita
ε-insensitive. Infatti, all’aumentare diε aumenterà l’ampiezza dell’ε-tubo
ed un numero sempre maggiore di stime cadrà al suo interno, dove il rischio
empiricoèazzerato. Questocorrispondealcaso1precedentementeillustrato
e quindi comporterà una riduzione della percentuale di vettori di supporto
rispetto all’ampiezza campionaria.
A causa della presenza dei vettori di supporto, il problema di ottimo
SVM si definisce sparso. Solo una parte del campione rappresentato dalle
4.1. La struttura dei modelli SVM45
righe della matrice X viene infatti utilizzato all’interno del processo SVM.
Questositraduceinnanzituttoinunariduzionedellacomplessitàalgoritmica
del problema e quindi dello ”sforzo” computazionale necessario per stimare
imodelli.
Vapnik introduce un’altra proprietà derivante dalla sparsità attraverso il
5
seguente risultato. Esso è riferito a problemi di classificazione e riguarda le
proprietàdigeneralizzazionediunmodellocostruitomediantevettoridisup-
porto. Nonesiste in letteratura un adattamento per problemi di regressione,
ma esso risulta comunque indicativo, tenendo conto che la regressione SVM
nonèaltrocheunageneralizzazionedellateoriaespostaperlaclassificazione
binaria.
Teorema 4.1.3 Se un campione di ndatiditrainingvengonoseparaticor-
rettamente da un modello di classificazione SVM, allora il valore atteso della
probabilità di commettere un errore su un dato di test è vincolato superior-
mente dal rapporto fra il valore atteso del numero di vettori di supporto ed
il numero di dati di training meno 1.
E(numero di vettori di supporto)
E[(errore di classificazione)]≤
P
n−1
(4.1.15)
La validità di questo Teorema è limitata ai casi in cui esiste perfetta
separabilità dei dati di training, quindi in assenza di errori di classificazione,
di conseguenza la sua rilevanza diretta nelle applicazioni è scarsa. L’inte-
6
resse maggiore deriva dall’ideache, attraverso il controllo del numero dei
vettori di supporto, sia possibile ricavare un metodo ulteriore per gestire la
relazione inversa fra la componente di rischio empirico e quella di rischio di
generalizzazione connesse ad un modello. E’ importante notare come questo
vincolo non dipenda dalla dimensionalità D dello spazio delle caratteristi-
che, né dalla norma dei dati di input k¯ xk, né da quella del vettore di
D
`
2
coefficienti angolari kwk.
D
`
2
Attraverso un numero ridotto di vettori di supporto provenienti dai dati
di training, cioè fissando un valore adeguato diε, è dunque possibile co-
struire un processo di apprendimento per problemi di regressione con buone
capacità di generalizzazione.
4.1.3 L’espressione analitica esplicita
Per ricavare l’espressione analitica esplicita di un modello SVM riscriviamo
la funzione di regressione lineare stimata sul campione di dati
5
Vapnik [25] pag. 135.
6
Vapnik [26] pag. 426.
46Capitolo 4. Support Vector Machines
(x,y),...,(x,y) mappato nello spazio delle caratteristiche (4.1.1) e va-
11nn
lutataperungenericovettorecolonnaD-dimensionaledidati¯ ztrasformato
i
non linearmente.
0
ˆ
f(w,¯ z,b)=¯ zˆ w +b
i
i
Il vettore colonna d-dimensionalezrappresenta un campione di dati osser-
i
vatodelqualevogliamofornireun’approssimazionedeltargetassociato, noti
i parametri del modello SVM ottenuti attraverso i dati di trainingX.
Sostituendo il valore di ˆ w fornito in (4.1.8) si ottiene
¡¢
∗∗0
¯¯ˆ
fα,α,X,¯ z=(ˆα− ˆα)X¯ z+b(4.1.16)
ii
che rappresenta l’espressione analitica esplicita dei modelli SVM. Abbiamo
chiamato esplicita questa formulazione poiché per ricavarla è necessario co-
noscereesplicitamentelatrasforma zione non lineare applicata ai dati. E’
però importante sottolineare che, in realtà, non siamo interessati diretta-
¯
mente alla trasformazione applicata ai dati di trainingX ed all’esempio
¯ z, quanto al valore del loro prodotto interno nello spazio delle caratteristi-
i
che. Calcolarlo in maniera diretta può diventare un’operazione proibitiva,
si pensi al caso di uno spazio delle caratteristiche∞-dimensionale. Come
vedremo, però, esiste una formulazione implicita dei modelli SVM che per-
mette di ricavare il prodotto interno senza conoscere in maniera esplicita la
trasformazione dei vettori di dati nello spazio delle caratteristiche.
4.1.4 Il valore dell’intercettab
Nullaèstatodettofinora sul modo in cui ricavare l’intercettab nella regres-
7
sione (4.1.1). Un sistema molto sempliceconsiste nel prendere una stima
checadeesattamentesuunmarginedell’ε-tubo,adesempioquellosuperiore,
ecalcolare
ˆ
¯
b =y−Xˆ w +ε.(4.1.17)
ii
Vedremo nel capitolo successivo una tecnica più generale per ottenere b,la
quale non richiede la presenza di almeno una stima sul margine.
4.2 La mappatura dei dati nello spazio delle ca-
ratteristiche
Dopo avere visto la derivazione analitica dei modelli SVM e la loro strut-
tura ”architetturale”, consideriamo ora in che modo avviene la mappatura
dei dati nello spazio delle caratteristiche. Attraverso l’applicazione di un
7
Smola [23] pag.9.
4.2. La mappatura dei dati nello spazio delle caratteristiche47
risultato noto in letteratura, è possibile definire una particolare tipologia di
funzioni, dette funzioni kernel, in grado di fornire in maniera implicita il va-
lore del prodotto interno fra vettori di osservazioni campionarie trasformati
nello spazio delle caratteristiche.
4.2.1 Funzioni kernel e Teorema di Mercer
Come accennato in precedenza, sebbene sia possibile calcolare esplicitamen-
te due generiche trasformazione non lineari ¯ xe ¯ zcalcolando successiva-
ii
8
mente il loro prodotto interno, questa procedura risulta molto scomoda e
dispendiosa, soprattutto all’aumentare della dimensionalità dello spazio del-
le caratteristiche. Poiché il nostro effettivo interesse non è rivolto tanto alla
forma esplicita della mappaturaφfralospaziodioriginedeidatielospazio
¯
delle caratteristiche, quanto al valore del prodotto internoX¯ z,èstatain-
i
trodotta una maniera implicita di ricavare tale valore. Per ottenerlo occorre
9
considerare una funzione kernel così definita.
Definizione 4.2.1 Una funzionekernel è una funzionek tale per cui∀x,z∈
n
R
¡¢
0
00
kx,z=φ(x)φ(z)=¯ x¯ z(4.2.1)
n
doveφ rappresenta una mappatura daRad uno spazio delle caratteristiche
C.
L’utilizzo di una funzione kernel permette quindi di calcolare in ma-
niera implicita il valore del prodotto interno fra due vettori nello spazio
delle caratteristiche senza la necessità di conoscerli direttamente. Una fun-
zione kernel richiede infatti come argomenti solo due vettori appartenenti
allo spazio dei dati originari. Siccome i vettori trasformati non linearmente
nonvengonorappresentatiesplicitamente, ilnumerodioperazioninecessario
per calcolare il loro prodotto interno non è necessariamente proporzionale
alla dimensionalità dello spazio delle caratteristiche. L’utilizzo delle funzio-
ni kernel ci permetterà infatti di affrontare agevolmente anche spazi delle
caratteristiche∞-dimensionali.
Ogni funzione kernel k implica una differente mappaturaφ. Siccome
risulta molto difficile scegliere a priori la mappatura attraverso la quale
sviluppare un processo di apprendimento, ricavando solo successivamente
la funzione kernel che la rappresenta, nella pratica si preferisce considera-
re direttamente la funzione kernel e definire implicitamente la mappatura.
Il criterio mediante il quale operare tale scelta è un problema centrale al-
l’interno della tecnica SVM ed è tuttora sottoposto ad un forte dibattito
teorico. Lo spazio delle caratteristiche in cui viene sviluppato il processo
8
Vapnik [26] pag. 422.
9
Cristianini, Shawe-Taylor [8] pag.30.
48Capitolo 4. Support Vector Machines
di apprendimento è infatti determinante per stabilire la capacità previsiva
del modello, poiché la sua misura di capacità è fortemente influenzata dalla
funzione kernel implementata.
Non tutte le generiche funzioni di vettore possono però rappresentare un
prodotto interno nello spazio delle caratteristiche. Occorre quindi definire
10
alcune proprietà fondamentaliche una funzione deve rispettare per essere
considerata una funzione kernel adatta alla tecnica di apprendimento SVM.
Innanzitutto una funzione kernel deve essere simmetrica
¡¢¡¢
00
00
kx,z=φ(x)φ(z)=φ(z)φ(x)=kz,x
e soddisfare la disuguaglianza di Cauchy-Schwarz
¡¢¡¢¡¢
2
000
kx,z≤kx,xkz,z.
Queste due condizioni non sono però sufficienti ad assicurare che una
0
funzione k(x,z) fornisca implicitamente il prodotto interno di due vettori
mappati nello spazio delle caratteristiche. Essa infatti deve soddisfare anche
11
le condizioni del seguente Teorema.
Teorema 4.2.2 (Mercer) Sia k una funzione kernel simmetrica defini-
¡¢
dd
tasuunosp aziom etric oc omp a ttoLX×Xtale per cui l’operatore
∞
integrale
³´³´
dddd
T: LX×X→LX×X
k22
Z
¡¢
0
T: f (·)=k·,zf (z)dµ(z)
k
d
X
sia positivo, cioè
Z
¡¢
0
kx,zf (x)f (z)dµ(x)dµ(z)≥ 0
dd
X×X
¡¢¡¢
dd
∀f∈LX.Siaψ∈LXl’autofunzione diTassociata all’autovalore
22
jk
°°
°°
λ6=0enormalizzatoinmodocheψ=1 . Allora:
j
j
L
2
1. {λ(T)}∈`,
jk1
¡¢°°
d
°°
2.ψ∈LXe supψ<∞,
∞
jj
L
∞
j
P
0
3. k(x,z)=λψ(x)ψ(z).
j
jj
j∈N
10
Cristianini, Shawe-Taylor [8] pag. 32-33.
11
Smola [23] pag. 38. Cristianini, Shawe-Taylor [8] pag.35.
4.2. La mappatura dei dati nello spazio delle caratteristiche49
Una funzione k che soddisfa queste condizioni viene definita funzione
kernel di Mercer. Il punto 3 del Teorema mostra come una funzione ker-
dd
nel di questo tipo fornisca∀x,z∈ X⊆ Ril valore del un prodotto in-
0
ternoφ(x)φ(z) calcolato nello spazio delle caratteristiche attraverso la
mappatura
d
φ :X→`
2
no
©ªp
φ :x→φ(x)=λψ(x)
j
jj
doveφ(x) indica il j-esimo elemento del vettoreφ(x) e j=1,...,D.La
j
relazione fra una funzione kernel di Mercer e lo spazio delle caratteristiche
da essa indotto è inoltre biunivoca. Uno spazio delle caratteristiche così
ricavato è noto nella Teoria della Regolarizzazione come Spazio di Hilbert
12
Riprodotto da Kernel (RKHS).
4.2.2 Polinomio di Vapnik e radial basis
In letteratura esistono numerose funzioni kernel che soddisfano le condizioni
sopra elencate. Qui ci limitiamo ad esporre le due più conosciute ed utilizza-
13
te. Queste funzioni sono state quelle preseinconsiderazione nellosviluppo
del software per le applicazioni empiriche.
Polinomio di Vapnik
Questa funzione kernel corrisponde ad un semplice prodotto polinomiale di
grado q.
¡¢£¤
q
00
kx,z=xz+1(4.2.2)
All’aumentare del grado q aumenta la complessità algoritmica della SVM
polinomialeequindilasuamisuradicapacità,incrementandolacomponente
di rischio di generalizzazione ad essa connessa e diminuendo quella di rischio
empirico. La dimensionalità D dello spazio delle caratteristiche indotto dal
polinomio di Vapnik è sempre finita e direttamente proporzionale al valore
del grado q.
Radial basis
La funzione kernel radial basis è molto nota e viene utilizzata in differenti
ambiti teorici nella ricerca sulle tecniche di apprendimento.
()
2
kx−zkd
¡¢
`
0
2
kx,z=exp−(4.2.3)
2σ
12
Vapnik [26] pag. 490. Evgeniou, Pontil, Poggio [11].
13
Vapnik [26] pag. 430-432.
50Capitolo 4. Support Vector Machines
Analogamente alla funzione kernel polinomiale, al diminuire del parametro
σ aumenta la complessità algoritmica della SVM radial basis e quindi la
sua misura di capacità, incrementando la componente di rischio di gene-
ralizzazione ad essa connessa e diminuendo quella di rischio empirico. La
dimensionalità D dello spazio delle caratteristiche indotto dalla funzione
kernel radial basis è sempre infinita.
Utilizzando una funzione kernel radial basis si presentano quei problemi
connessi alla dimensione VC accennati nel Capitolo 2 e dovuti proprio al
fattochelospaziodellecaratteristichedaessaindottoè∞-dimensionale.
14
Vale infatti il seguente Teorema.
Teorema 4.2.3 SiaD la dimensionalità dello spazio delle caratteristiche in
no
cui opera la funzione di apprendimento SVMf(w,¯ x,b)∈R : kwkD≤B.
i
`
2
Allora la dimensione VC di una funzione di perdita quadratica, laplacia-
na oε-insensitive L(y,f(w,¯ x,b)) è sempre maggiore o uguale a D ed
i
indipendente da B.
E’ chiaro quindi che, utilizzando all’interno di una SVM una funzio-
ne kernel radial basis che mappa i dati in uno spazio delle caratteristiche
∞-dimensionale, la dimensione VC ad essa associata sarà sempre infinita,
indipendentemente dal valore del parametroσ che ne regola la complessità
algoritmica e dal valore del parametroC che gestisce la relazione inversa tra
rischioempiricoerischiodigeneraliz zazione associato. Inoltre, una volta
fissato il valore diε e dei parametri della funzione kernel, una misura di
capacità efficace deve rispettare il Teorema 4.1.1 ed aumentare con il valore
diB. Il Teorema 4.2.3 evidenzia come la dimensione VC presenti dei proble-
mi nel rispettare tali condizioni e non sia adatta per definire una struttura
ammissibile sulla classe degli approssimatori, quindi per un utilizzo all’inter-
no della logica di lavoro legata al principio SRM. Proprio per l’esigenza di
risolvere queste problematiche si è giunti alla proposta di alcune generaliz-
zazioni, fra cui le misure di capacità sensibili alla scala come la dimensione
15
fat shattering. Per essa vale il seguente risultato.
no
Teorema 4.2.4 Siaf(w,¯ x,b)∈R : kwkD≤Buna funzione di appren-
i
`
2
n
dimento SVM nello spazio delle caratteristiche con dominioXnello spazio
di origine dei dati e Sla minima sfera centrata nell’origine di raggio R
R
n
contenente la mappaturaφ(x) di tutti i vettorix∈X.Alloraladimensione
³´
2
BR
fat shattering della SVM è vincolata superiormente da.
γ
La dimensione fat shattering permette quindi di stabilire una struttu-
ra ammissibile sulla classe degli approssimatori SVM e l’applicazione del
14
Evgeniou, Pontil, Poggio [11] e [10].
15
Shawe-Taylor et al. [8] pag. 62.
4.2. La mappatura dei dati nello spazio delle caratteristiche51
principio SRM. Essa è una quantità indipendente dalla dimensionalità dello
spazio delle caratteristiche e permette di valutare la complessità algoritmica
anchedelleSVMoperantisuspazi∞-dimensionali, comenelcasodelleSVM
radial basis.
Una proprietà importante di cui gode la funzione kernel radial basis è
quella di essere invariante rispetto alle traslazioni.
³´
¡¢¡¢
000
kx,z=kx−z,[0]=kkx−zkd,0
`
2
Questa caratteristica permette di considerare la funzione kernel radial basis
come una funzione con dominio unidimensionale.
Nella parte applicativa, l’interesse sarà rivolto verso SVM con funzione
kernel radial basis. Sappiamo dal Teorema 4.1.1 e dall’Osservazione 4.1.2
2
che il valore assunto della norma al quadrato kwkdella regressione linea-
D
`
2
re calcolata nello spazio delle caratteristiche è cruciale per la gestione della
relazione inversa fra errore empirico ed errore di generalizzazione. E’ quindi
molto importante avere la possibilità di operare in uno spazio in cui la retta
stimatapossaapprossimareinmanieraaccurataidatidi trainingmantenen-
do contemporaneamente un’inclinazione non eccessiva, per potere gestire al
meglio questa relazione inversa. La funzione kernel radial basis garantisce
proprio queste condizioni di lavoro, permettendo la stima di una retta di re-
gressione in cui il coefficiente angolare assume un valore relativamente basso
egenerandoSVMconbuonecapacitàprevisiveedicontrollodell’overfitting.
In un contesto di apprendimento agnostico, dove non si assumono informa-
zioni a priori, la scelta di questa funzione kernel appare quindi appropriata
16
ed in grado di fornire buoni risultati.
4.2.3 L’espressione analitica implicita
Attraverso l’utilizzo delle funzioni kernel è possibile giungere alla seguente
espressione analitica implicita di un modello SVM, in cui i prodotti inter-
ni nello spazio delle caratteristiche e la regressione lineare (4.1.1) vengono
calcolati in maniera implicita nello spazio dei dati originari.
∗∗0
ˆ
f (α,α,X,z)=(ˆα− ˆα)K(X,z)+b(4.2.4)
ii
dove
• K(A,B) indica una generica matrice kernel di ordine
(ord(A),ord(B))ilcuielementogenerico(i,j)èdatodallafunzione
rc
¡¢
17j
kernelkA,B,
i
16
Smola [23] pag. 44.
17j
Indichiamo conAlai-esima riga della matriceAeconBj-esima colonna della
i
matriceB.
52Capitolo 4. Support Vector Machines
• l’operatore ord(A) restituisce il numero di righe della matrice A e
r
l’operatore ord(B) restituisce il numero di colonne della matriceB.
c
Grazie alla simmetricità della funzione kernel, anche la matrice kernel
K(A,B) da essa indotta risulta simmetrica. Inoltre, una funzione kernel
che rispetta il Teorema di Mercer garantisce che la relativa matrice kernel
18
sia semi-definita positiva, ribadendo la convessità del problema duale.
E’ possibile esprimere in maniera implicita anche il valore della norma
2
al quadrato kwkdei coefficienti angolari della retta di regressione nello
D
`
2
spazio delle caratteristiche.
¡¢
20∗00∗
kwk=ww=(ˆα− ˆα)KX,X(ˆα− ˆα)(4.2.5)
D
`
2
4.3 Il modello di errore
Unaltroimportanteproblemadaaffrontareriguardailmodellodierroreim-
plicito nell’utilizzo di un processo di apprendimento SVM. Sappiamo infatti
dal paragrafo 1.3.3 che ogni differente funzione di regressione ha associato
un modello di disturbo diverso e che esso dipende dalla funzione di per-
dita utilizzata al suo interno. Lo studio del modello di errore riveste una
grande importanza: minori restrizioni vengono poste sulla forma della sua
distribuzione di probabilità, maggiore sarà la flessibilità del modello e la sua
capacità di adattarsi a situazioni differenti. L’esposizione seguente riassume
il lavoro di Pontil, Mukherjee e Girosi [18].
Consideriamouncampione (x,y),...,(x,y)eriscriviamoilmodello
11nn
di apprendimento (1.3.6)
y=f (x)+δ
iii
con i=1,...,n.
L’obiettivo dell’apprendimento è quello di stimare la funzione f (x) at-
i
traverso i dati. Seguendo un approccio probabilistico è possibile considerare
la funzione f (x) come la realizzazione di un evento casuale di cui forniamo
i
una distribuzione a priori. Il nostro scopo sarà massimizzare la probabilità
nn
a posteriori di f (x) dato un campione (X,y)=(x,y),...,(x,y).
i11nn
Utilizzando il Teorema di Bayes si ottiene
nnnn
{f (x) | (X,y)}∝{(X,y) |f (x)}{f (x)}(4.3.1)
PPP
iii
dove{f (x)} è una distribuzione a priori su f (x) del tipo{f (x)}∝
PP
iii
exp{−αΩ(f)} eΩ(f) è una funzione di penalità per il controllo della gene-
nn
ralizzazione. Laprobabilità{(X,y) |f (x)}essenzialmenterappresenta
P
i
il modello di errore connesso alla funzione approssimatrice.
18
Cristianini, Shawe-Taylor [8] pag. 33.