Please enable JavaScript.
Coggle requires JavaScript to display documents.
Support Vector Machine - Coggle Diagram
Support Vector Machine
SVM
imparare l'iperpiano separatore con il margine più alto
Constrained Problem
max M
subject to yi 1/||w|| (w^T xi + b) >= M/2
M è il margine
Rewriting
yi(w^T xi +b)>=1 con M=2/||w||
min 1/2 ||w||^2
subject to yi(w^T xi + b) >= 1
si risolve con i lagrangian multiplers
Lagrangian multiplier
Df(x°)= SUM lambda t Dh_t (x°)
(x°,lambda°) è un punto di sella della funzione
f(x) - SUM (lambda_t h_t (x))
L(w,b,lambda) =
1/2 ||w||^2 - SUM (lambda_i (yi (w^T xi +b) - 1)
mininum (w°,b°) con derivata 0
delta_w L(w,b,lambda) = w- SUM lambda_i yi xi
delta_b L(w,b,lambda) = - SUM lambda_i yi
w° = SUM lambda_i yi xi
SUM lambda_i yi = 0
Unconstrained Problem
Stessa cosa dei constrained
attraverso la KKT
KKT
Karush Kuhn Tucker conditions
se la funzione obiettivo è convessa, la KKT è soddisfatta dalla soluzione (x°,lambda°) del problema primale e Duale
Primale
min f(x)
soggetto a g_t(x)<=0 t=1,...,T
Duale
max_lambda inf_x (f(x) + SUM lambda_t g_t(x) )
soggetto a lambda_t >=0 t=1,..,T
max_lambda (SUM lambdai - 1/2 SUM SUM lambdai lambdaj yj yi xi^T xj)
soggetta a lambda>=0 sum lambda yi=0
matricialmente:
max (1^T LAMBDA - 1/2 LAMBDA^T Q LAMBDA)
Qij =(yi xi)^T (yj xj)
Quadratic Programming Problem
un sacco di metodi per risolverli
interior point
active set
conjugate gradient
gradient projection
KKT condition
lambda°i [yi (xi^T w° + b°) - 1 ] = 0
per ogni i € [1, Ntr]
lambda°i > 0
-->
yi (xi^T w° +b°)=1
l'i-esimo training point è sul margine
lambda°i =0
-->
yi(xi^T w° + b°) > 1
l'i-esimo training point non è sul margine
Support Vectors
punti sul margine
L'iperpiano dipende solo da questi
w° = SUM lambda_i° yi xi
b° = 1 - yi xi^T w° i€SV
Inference
y' = sign (w°^T x' + b° ) =
= sign ( SUM lambdai yi xi^T x' + b° )
non abbiamo bisogno di computare w° esplicitamente
PRO & CONTRO
PRO
massimizzare margine migliora generalizzazione
soluzione dipende da un sottoinsieme di dati di training
CONTRO
può essere applicata solo in task di classificazione binaria
assume che i training data siano linearmente separabili
SVM con Soft-Margin
I training points possono stare dalla parte sbagliata dell'iperpiano
Slack Variable
la definisco per ogni training point,
=0
yi (w^T xi +b)>= 1- SLACK i
SLACK = 0
Come sopra
SLACK > 0
il punto di train può finire nella regione sbagliata
Optimization Problem
min_(w,b) 1/2 ||w|| ^2 + C SUM SLACK i
soggetto a
SLACK i >= 0, yi(w^T xi +b) >= 1- SLACK i
per ogni i € [1, Ntr]
C controlla la quantità
di punti misclassificati
C=0 non ci importa di SLACK i
possiamo misclassificare tutti i punti
C= inf
SLACK i deve essere 0, otteniamo un SVM normale
Soluzione
max_lambda (SUM lambda_i - 1/2 SUM SUM lambdai lambdaj yj yi xi^Txj)
soggetto a 0<=lambda_i<=C, SUM lambda_i yi =0
sempre un quadratic programing problem
KKT condition
lambda°_i (yi (xi^T w° + b°) -(1- SLACK°_i)) =0
(C-lambda°_i)SLACK°_i =0
lambda°_i>0
slack°_i>0 lambda°_i =C
slack°_i =0 0<lambda°_i<C
lambda°_i =0
il training point non è un vettore di supporto
B.S.H.
Best Separating Hyperplanes
Iperpiano
set di punti affini
L={x|w^Tx+b =0}
Vettore normale di iperpiani
n
t.c.
v
€L --> n^T
v
=0
n^T(a-b) = 0
n= w/||w||
Distanza punto iperpiano
proiezione v=(x-x0) lungo la direzione di n
distL(x)=||v||cos(theta)= 1/ ||w|| (w^Tx+b)