Support Vector Machine (SVM)
Vctor H. Contreras O. Leonardo Raul Linero.
Universidad Nacional de Colombia
June 19, 2014
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 1 / 33
Indice
1
Introducci on
Que son las SVM?
Principio inductivo de minimizacion del riesgo emprico
Overtting
Minimizaci on del riesgo estructural (SRM)
2
Las SVM: un enfoque te orico
Hiperplano optimo
Calculo del hiperplano optimo caso linealmente separable
Calculo del hiperplano optimo caso linealmente no separable
Clasicadores no lineales
Problema multiclase
3
Ejemplos
Ejemplos
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 2 / 33
Que son las SVM?
Las SVM son un conjunto de algoritmos de aprendizaje basados en la
teora del aprendizaje estadstico. Fueron desarrolladas por Vapnik y
su grupo de investigacion de los laboratorios Bell AT&T a nales de
los a nos 70 y durante los 80. El modelo SVM tal como se conoce
actualmente fue presentado durante la conferencia COLT
1
del a no
1992 por el mismo Vapnik. La idea detras de las maquinas de soporte
vectorial es transformar el vector de entrada x dentro de un espacio
caracterstico de alta dimension a traves de alguna transformaci on no
lineal, elegida a priori. En este espacio es construido un hiperplano de
separaci on optimo (HSO).
1
COmputational Learning Theory
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 3 / 33
Figure 1: Transformacion no lineal a priori
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 4 / 33
Principio inductivo de minimizacion del riesgo
emprico
El problema de aprendizaje generalizado es minimizar el funcional del
riesgo:
R() =
Q(z, )dF(z), (1)
Donde la probabilidad F(z) es desconocida pero las muestras i.i.d
2
,
son dadas:
z
1
, ..., z
(2)
2
Independientes e identicamente distribuidos
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 5 / 33
Para minimizar el funcional (1) con una distribucion de probabilidad
desconocida F(z) el siguiente principio inductivo es aplicado:
i. El funcional del riesgo R() es reemplazado por el llamado
funcional del riesgo emprico.
R
emp
() =
1
i =1
Q(z
i
, ) (3)
Construido con base en el conjunto de entrenamiento (2).
ii. se aproxima la funcion Q(z,
0
) que minimiza el funcional (1) por
la funcion Q(z,
) que minimiza el funcional del riesgo empirico
(3).
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 6 / 33
Overtting
Figure 2: Undertting and Overtting in SVM
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 7 / 33
Minimizacion del riesgo estructural (SRM)
La capacidad del modelo depende de la complejidad de los datos de
entrenamiento usados. Este es un modelo no parametrico partiendo
de este paradigma basico, Vapnik y Chervonenkis, plantearon el
principio inductivo SRM (Structural Risk Minimization). Existen dos
aproximaciones basicas para construir un modelo de maquina de
aprendizaje que tenga una buena habilidad de generalizaci on:
1
Seleccionar una apropiada estructura del modelo (ya sea una red
neuronal articial con el n umero apropiado de neuronas, o en un
sistema difuso la cantidad de reglas difusas) y mantener el error
de estimacion jo mientras se minimiza el error de
entrenamiento.
2
Mantener el error de entrenamiento jo (en cero o en un nivel
aceptable) mientras se minimiza el intervalo de conanza.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 8 / 33
Para el caso de la clasicaci on tenemos que el riesgo emprico es:
R
emp
() =
1
i =1
(y
i
f (x
i
, ))
2
(4)
Una condicion necesaria y suciente para la consistencia del principio
ERM es la dimension VC (Vapnik-Chervonenkins) que es un
n umero natural; es el n umero mas grande de puntos de datos que
pueden ser separados en todas las posibles formas por el conjunto de
funciones f (). La dimensi on VC es una medida de la complejidad
del espacio de hipotesis H.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 9 / 33
Figure 3: Cota Sobre el riesgo (suma del riesgo emprico y el intervalo de
conanza)
El SRM minimiza tanto el riesgo emprico como el intervalo de
conanza, esto se logra maximizando el margen entre las muestras de
entrenamiento y el hiperplano de separaci on.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 10 / 33
El hiperplano de separacion optimo
El hiperplano optimo es aquel que proporciona la maxima separaci on
entre las clases, es decir maximiza el margen . Maximizar el margen
es un problema de programaci on cuadratica (QP) y puede ser
resuelto por su problema dual aplicando multiplicadores de Lagrange.
Desde un punto de vista intuitivo, cuanto mayor sea el margen, mejor
poder de generalizaci on tendra el clasicador. Suponiendo que el
margen existe, la distancia desde cualquier muestra x hasta el
hiperplano de separaci on es | w
x
+ b|/|| w||.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 11 / 33
Sin perdida de generalidad puede asumirse que los datos de
entrenamiento que se encuentran por encima de la linea +1 satisfacen
w x
(+1)
+ b
|| w||
(5)
Entonces, las muestras de entrenamiento por debajo de la linea -1
deben satisfacer
w x
(1)
+ b
|| w||
(6)
Compactando las dos expresiones anteriores en una sola queda la
desigualdad:
y
k
w x
k
+ b
||w||
, k = 1, ..., (7)
donde y
k
{1, 1} y es el n umero de datos de entrenamiento.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 12 / 33
El problema de encontrar el hiperplano optimo se reduce entonces a
encontrar el w que maximiza el margen . Debe resaltase que hay un
n umero innito de soluciones que se diferencian unicamente en un
factor de escala para w. Para limitar las soluciones a una unica, se
ja la condici on || w|| = 1. Por consiguiente, maximizar el margen
equivale a minimizar la norma de w.
Suponiendo un conjunto de entrenaimiento linealmente separable con
m muestras
( x
1
, y
1
), ..., ( x
m
, y
m
), x R
n
, y
k
{+1, 1}k = 1, ..., m (8)
la frontera de separaci on de las dos clases va a ser una funcion lineal
D(x) = w x + b (9)
todas las muestras del conjunto de entrenamiento cumplen,
y
k
( w x
k
+ b) 1, k = 1, ..., m (10)
donde la condici on de igualdad se satisface para los vectores de
soporte.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 13 / 33
Figure 4: Vectores de soporte y margen maximo
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 14 / 33
Calculo del hiperplano optimo
Para calcular el hiperplano de separacion a partir de las muestras de
entrada (8), se requiere determinar los w y b que minimizan el
funcional
( w) =
1
2
||w||
2
(11)
y tal que
y
k
( w x
k
+ b) 1, k = 1, .., m (12)
El problema de optimizaci on se plantea entonces en base a
multiplicadores de Lagrange seg un la expansion (13).
L( w, b, ) =
1
2
|| w||
2
k=1
k
[y
k
( w x
k
+ b) 1] (13)
donde los
k
son los multiplicadores de Lagrange.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 15 / 33
El punto de ensilladura proporciona la solucion al problema de
optimizaci on. La funci on debe minimizarse con relaci on a w y b a la
vez que debe maximizarse con relaci on a
k
0.
Teniendo en cuenta que,
L( w, b, )
w
= w
m
k=1
k
y
k
x
k
= 0 w =
m
k=1
k
y
k
x
k
(14)
L( w, b, )
b
= 0
m
k=1
k
y
k
= 0 (15)
y sustituyendo (14) y (15) en (13), el problema es equivalente a
maximizar
() =
m
k=1
k
1
2
m
i ,j =1
j
y
i
y
j
( x
i
x
j
) (16)
sujeto a las siguientes restricciones
k
0, k = 1, ..., m
m
k=1
k
y
k
= 0
(17)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 16 / 33
El hiperplano de separacion (9), teniendo en cuenta el valor de w
proporcionado por (14) queda expresado como sigue,
D(x) =
m
k=1
k
y
k
(x x
k
) + b (18)
Toda muestra tiene asociado un multiplicador de Lagrange. De todos
los multiplicadores solamente algunos son distintos de cero.
Precisamente aquellas muestras cuyos multiplicadores de Lagrange
son distintos de cero son los vectores de soporte. Por lo tanto la
ecuaci on del hiperplano puede escribirse
D(x) =
vectores soporte
k
y
k
(x x
k
) + b (19)
Para calcular b hacemos uso de la condicion de vector soporte
proporcionada por (10). Si la muestra de entrenamiento (x
vs
, y
vs
) es
un vector soporte cualquiera, se verica,
y
vs
( w x
vs
+ b) = 1 (20)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 17 / 33
Usando nuevamente (14) y despejando b obtenemos
b = y
vs
vectores soporte
k
y
k
( x
k
x
vs
) (21)
La ecuacion (19) representa el modelo obtenido durante el
entrenamiento. A partir de esta expresion se podra determinar la
clase a la que pertenece cualquier muestra que se quiera clasicar con
posterioridad. En realidad solamente se requiere saber el signo de
(19) para asignar la muestra a una clase u otra. As pues, dada una
muestra x
c
, a clasicar
Si sign[D( x
c
)] > 0
x
c
clase(+1)
en otro caso
x
c
clase(1)
(22)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 18 / 33
Clasicador Lineal de margen suave
La frontera que separa las dos clases es lineal pero hay al menos una
muestra de una de las clases que aparece del lado equivocado del
hiperplano de separaci on.
Una muestra de entrenamiento es no separable cuando no satisfase la
ecuaci on (12). Esto signica o bien que la muestra cae en los
margenes o en el lado equivocado del plano de decisi on. Debe
resaltarse la diferencia entre el concepto de muestra no separable y
una muestra mal clasicada. Ver gura (5).
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 19 / 33
Figure 5: Hiperplano de separacion lineal para un problema con patrones
solapados
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 20 / 33
Para encontrar el hiperplano que cometa el mnimo n umero de
errores, se introduce un conjunto de variables no negativas, una por
cada muestra de entrenamiento
k
0, k = 1, ..., m. El calculo del
hiperplano de separaci on requiere determinar los w y b que
minimizan el funcional
( w) =
1
2
|| w||
2
+ C
m
k=1
k
(23)
sujeto a las restriciones
y
k
( w x + b) 1
k
(24)
Donde C es una constante de penalizaci on muy grande. Para aquellas
muestras de entrenamiento que quedan bien clasicadas su
correspondiente variable
k
= 0. Si
k
> 0, la muestra es no
separable y si
k
> 1, entonces la muestra esta mal clasicada.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 21 / 33
El procedimiento seguido para este problema es exactaemte igual al
seguido para el caso linealmente separable. Obtenemos entonces
() =
m
k=1
k
1
2
m
i ,j =1
j
y
i
y
j
( x
i
x
j
) (25)
sujeto a
0
k
C, k = 1, ..., m
m
k=1
k
y
k
= 0
(26)
La construccion del hiperplano frontera entre las dos clases es
exactamente la misma que la del caso separable.
D(x) =
vectores sporte
k
y
k
(x x
k
) + b (27)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 22 / 33
Clasicadores no lineales
Cuando las muestras de entrenamiento no pueden separarse mediante
una funcion lineal, se recurre a transformaciones no lineales que
llevan el espacio de entrada a otro espacio de alta dimensionalidad,
en el que los datos son separables linealmente. A este nuevo espacio
se le denomina espacio de caractersticas.
Mediante una apropiada transformaci on no lineal a una
dimensionalidad sucentemente alta siempre es posible seprar dos
clases mediante un hiperplano en el espacio transformado.
x R
n
(x) = [
1
(x)
2
(x)
M
(x)] R
M
(28)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 23 / 33
Si la frontera es lineal en el espacio de caractersticas signica que
dicha funcion puede expresarse como sigue,
D(x) = (
M
j =1
w
j
j
(x)) + b = w + b (29)
Para este problema hay que minimizar el siguiente funcional
(w) =
1
2
||w||
2
+ C
m
k=1
k
(30)
sujeto a
y
k
(w (x) + b) 1
k
, k = 1, ..., m
k
0, k = 1, ..., m
(31)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 24 / 33
El vector w, de acuerdo con la ecuaci on(14) puede escribirse como
combinaci on lineal de los vectores de soporte en este caso
transformados.
w =
vectores soporte
k
y
k
(x
k
) (32)
y el hiperplano de separaci on resulta ser el siguiente
D(x) =
vectores soporte
k
y
k
((x) (x
k
)) (33)
El calculo del producto (x) (x
k
) puede ser computacionalmente
muy costoso si la dimensionalidad del espacio de caractersticas es
muy grande a este fen omeno se el llama la maldici on de la
dimensionalidad (curse of dimensionality).
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 25 / 33
El truco del Kernel
La maldici on de la dimensionalidad puede ser evitada usando el
truco del kernel (the trick of kernel). El truco del Kernel consiste
en evitar realizar los productos escalares en el espacio de
caractersticas, por medio de la aplicacion de un producto escalar
usando una funci on n ucleo (kernel) ejecutada en el espacio de
entrada:
K(x
i
, x
j
) = (x
i
) (x
j
) (34)
El calculo de los productos escalares en el espacio de gran
dimensionalidad es efectuado indirectamente mediante la evaluaci on
de la funci on K. Las funciones n ucleo permiten la transformacion de
los datos a espacios de altsima dimensionalidad, quizas innita, pero
sin necesidad de manipular las muestras en los espacios
transformados.
3
3
[Link]
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 26 / 33
Expresando el problema de optimizacion en su forma dual, los
multiplicadores de Lagrange a
k
, k = 1, ..., m se pueden obtener
conociendo unicamente el n ucleo, para ello dados los datos de
entrenamiento
(x
1
, y
1
), ..., (x
m
, y
m
), x R
n
, y
k
{+1, 1}k = 1, ..., m (35)
una funcion de n ucleo K y un parametro de penalizaci on C, hay que
minimizar el funcional
() =
m
k=1
k
m
i ,j =1
j
y
i
y
j
K(x
i
, x
j
) (36)
Sujeto a las siguientes restricciones
m
k=1
k
y
k
= 0
0
k
C, k = 1, ..., m
(37)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 27 / 33
No existe hasta el momento teora para determinar un valor optimo
de C. Se suele jar en un valor muy grande, cuando los datos son
separables tipicamente C .
La funcion de decisi on queda expresada como sigue
D(x) =
vectores soporte
k
y
k
K(x, x
k
) + b (38)
No se debe olvidar que en un problema biclase la clasicaci on de una
muestra x
c
, depende unicamente del signo de la funcion anterior.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 28 / 33
Figure 6: Kernel trick
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 29 / 33
Funciones n ucleo mas utilizadas
N ucleo polinomial de grado d
K(x, x
) = [(x x
) + 1]
d
(39)
Base radial (es decir K(x x
) = K(|x x
|) tales como
K(|x x
|) = exp{
|x x
|
2
2
2
} (40)
Perceptron multicapa
K(x, x
) = tanh[(x x
) + a] (41)
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 30 / 33
Problema multiclase
Weston y Watkins proponen una modicaci on de la funcion de
optimizaci on que tiene en cuenta todas las clases, generalizando la
funci on de optimizacion binaria para el n umero deseado N
c
de clases.
min
1
2
N
c
m=1
||w
m
||
2
+ C
N
c
i =1
m=y
i
m
i
(42)
sujeto a
w
y
i
x
i
+ b
y
i
w
m
x
i
+ b
m
+ 2
m
i
,
m
i
0 (43)
Una frente a todas (one-versus-all).
Una frente a una (one-versus-one).
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 31 / 33
Ejemplos
[Link]
[Link]
[Link]
Demostraci on
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 32 / 33
Referencias
Gustavo A. Betancourt.
Las maquinas de soporte vectorial (svms).
Scientia et Technica, (27):67, Abril 2005.
Jaiber Evelio Cardona and Francisco Javier Ibarguen.
Maquinas de soporte vectorial para clasicacion.
Arte imagen, Armenia Quindio, rst edition, 2007.
Jose Hernandez Orello, Ma Jose Rodriguez Quintana, and
Cesar Ferri Ramrez.
Introducci on a la minera de datos.
Pearson- Prentice Hall, Madrid Espa na, rst edition, 2005.
G. Pajares and J. de la Cruz.
Aprendizaje Automatico.
Ediciones de la U and Ra-Ma, Bogota Colombia, rst edition,
2011.
Vctor H. Contreras O., Leonardo Raul Linero. (Universidad Nacional de Colombia) Support Vector Machine (SVM) June 19, 2014 33 / 33
