Introducción al aprendizaje estadı́stico
Capı́tulo 9: support vector machine
Departamento de Matemática
FIQ - Basado en los slides del curso Introduction to machine learning de Hastie y
Tibshirani
Support vector machines
Aquı́ abordamos el problema de clasificación de dos clases de
manera directa:
Intentamos encontrar un plano que separe las clases en el
espacio de caracterı́sticas.
Si no podemos, nos volvemos creativos de dos formas:
Suavizamos lo que queremos decir con ”separa”, y
Enriquecemos y ampliamos el espacio de funciones para
que sea posible la separación.
¿Qué es un hiperplano?
Un hiperplano en p dimensiones es un subespacio afı́n
plano de dimensión p − 1.
En general, la ecuación para un hiperplano tiene la forma
β0 + β1 X1 + · · · + βp Xp = 0
En p = 2 dimensiones, un hiperplano es una lı́nea.
Si β0 = 0, el hiperplano pasa por el origen, de otra forma
no.
El vector β = (β1 , β2 , . . . , βp ) se denomina vector normal:
apunta en una dirección ortogonal a la superficie de un
hiperplano.
Hiperplano en dos dimensiones
Hiperplano en dos dimensiones
Si f (X) = β0 + β1 X1 + · · · + βp Xp , entonces f (X) > 0
para puntos en un lado del hiperplano y f (X) < 0 para los
puntos del otro.
Si codificamos los puntos coloreados como Yi = +1 para
azul, digamos, y Y1 = −1 para lila entonces si Yi f (Xi ) > 0
para todo i, tenemos que f (X) = 0 define un hiperplano
de separación.
Clasificador de margen máximo
Entre todos los hiperplanos separadores, encuentre el que
tenga la mayor brecha o margen entre las dos clases.
Problema de optimizacion con constraints.
Esto puede reformularse como un programa cuadrático
convexo y resolverse de manera eficiente. La función svm () en
el paquete e1071 resuelve este problema de manera eficiente
Datos no separables
Estos datos no se pueden separar mediante un lı́mite lineal.
Este es a menudo el caso, a menos que N < p.
Datos con mucho ruido
A veces, los datos son separables, pero ruidosos. Esto puede
llevar a mala solución para el clasificador de margen máximo.
El clasificador de support vector machine maximiza un margen
suave.
Clasificación vı́a Support vector
C es un parámetro de regularización
Entendiendo los i
= 0 para los puntos bien clasificados y del lado correcto
del margen.
0 < < 1 para los puntos bien clasificados y del lado
incorrecto del margen.
= 1 para los puntos sobre la frontera
> 1 para los puntos mal clasificados
Las fronteras lineales pueden fayar
En algún momento, un lı́mite lineal simplemente no funcionará,
sin importar el valor de C. Como este ejemplo ¿Qué hacer?
Ampliación de funciones
Ampliar el espacio de caracterı́sticas al incluir
transformaciones; por ejemplo X12 , X13 , X1 X2 , X1 X22 , . . . .
Por lo tanto, pase de un espacio p-dimensional a un
espacio M > p dimensional.
Colocar un clasificador de vectores de soporte en el
espacio ampliado.
Esto da como resultado lı́mites de decisión no lineales en
el espacio original.
Ejemplo: supongamos que usamos (X1 , X2 , X12 , X22 , X1 X2 ) en
lugar de solo (X1 , X2 ). Entonces el lı́mite de decisión serı́a de
la forma
β0 + β1 X1 + β2 X2 + β3 X12 + β4 X22 + β5 X1 X2 = 0
Esto conduce a lı́mites de decisión no lineales en el espacio
original (secciones cónicas cuadráticas).
Polinomios cúbicos
Aquı́ usamos una expansión de base de polinomios cúbicos
De 2 variables a 9
El clasificador de vectores de soporte en el espacio ampliado
resuelve el problema en el espacio de dimensiones inferiores
2 2 3 3 2 2
β0 + β1 X1 + β2 X2 + β3 X1 + β4 X2 + β5 X1 X2 + β6 X1 + β7 X2 + β8 X1 X2 + β9 X1 X2 = 0
No linealidades y kernels
Los polinomios (especialmente los de gran dimensión) se
vuelven salvajes bastante rápido.
Existe una forma más elegante y controlada de introducir
no linealidades en los clasificadores de vectores de
soporte mediante el uso de kernels.
Antes de discutir estos, debemos comprender el papel de
los productos internos en los clasificadores de vectores de
soporte.
Productos internos y support vectors
p
X
< xi , xi0 >= xij xi0 j 0 producto interno entre dos vectores
j=1
El clasificador linear de support vector puede
representarse como
Xn
f (x) = β0 + αi < x, xi > n parametros
i=1
Para estimar los par ámetros α1 , . . . , αn y β0 solo
necesitamos los n2 productos internos < xi , xi0 > entre
todos los pares en las observaciones de entrenamiento
Resulta que la mayorı́a de los α̂i son ceros:
X
f (x) = β0 + α̂i < x, xi >
i∈S
S es el conjunto soporte de ı́ndices i tal que α̂i > 0.
Núcleos y máquinas de vectores de soporte
Si podemos calcular productos internos entre
observaciones, podemos ajustar un clasificador SV. Puede
ser bastante abstracto
Algunas núcleos pueden hacer esto por nosotros. [Link].
p
!d
X
K(xi , xi0 ) = 1 + xij xi0 j
i=1
calcula los productos internos necesarios para polinomios
d dimensionales: p+d
d funciones bases.
Pruebe para p = 2 y d = 2
La solución es de la forma
X
f (x) = β0 + α̂i K(x, xi )
i∈S
Núcleo radial
p
X
K(xi , xi0 ) = exp(−γ (xij − xi0 j )2 )
i=1
X
f (x) = β0 + α̂i K(x, xi )
i∈S
Espacio de caracterı́sticas implı́citas; muy alta dimensional.
Controla la variación aplastando la mayorı́a de las dimensiones
severamente
Ejemplo: datos del corazón
La curva ROC se obtiene cambiando el umbral 0 por el umbral
t en f (X) > t, y registrando tasas de falsos positivos y
verdaderos positivos cuando t varı́a. Aquı́ vemos curvas ROC
en datos de entrenamiento.
Ejemplo continuado : datos del corazón
SVM: ¿más de 2 clases?
El SVM como se define funciona para K = 2 clases. ¿Qué
hacemos si tenemos clases K > 2?
OVA. Uno contra todos. Ajuste K diferentes SVM
clasificadores de 2 clases clasificadores
fˆk (x), k = 1, . . . K.; cada clase contra el resto. Clasifique x
en la clase para la que fˆk (x) es mayor.
OVO. Uno contra uno. Se ajusta a todos los clasificadores
por pares K2 fˆkl (x). Clasifica x en la clase que gana más
competiciones por parejas.
¿Cual elegir? Si K no es demasiado grande, use OVO.
¿Support vector machine versus regresión logı́stica?
Con f (X) = β0 + β1 X1 + . . . βp Xp podemos re-escribir el
problema de optimización del clasificador de support vector:
X n p
X
1
minimize max[0, 1 − yi f (xi )] + λ βj
i=1 j=1
Esto tiene la forma pérdida más penalización. La pérdida se
conoce como pérdida de bisagra. Muy similar a la ”pérdida” en
la regresión logı́stica (probabilidad logarı́tmica negativa).
¿Cuál usar: SVM o regresión logı́stica
Cuando las clases son (casi) separables, SVM lo hace
mejor que regresión logı́stica. También lo hace LDA.
Cuando no, regresión logı́stica (con penalización) y SVM
muy similares.
Si desea estimar probabilidades, regresión logı́stica es la
opción.
Para los lı́mites no lineales, las SVM de kernel son
populares. También puede usar kernels con regresión
logı́stica y LDA, pero los cálculos son más costosos.
¡Muchas gracias!
Liliana Forzani
[Link]@[Link]
