Análisis de Datos Máquinas de vectores de soporte

Profesor: Dr. Wilfrido Gómez Flores

1

Introducción• En el caso de clases linealmente separables, existen infinitos hiperplanos

de decisión que separan correctamente todos los datos de entrenamiento.

• ¿Cuál es el hiperplano más adecuado para clasificar patrones desconocidos?

‣ Aquel que tenga “más margen” hacia cada uno de sus lados, de modo que un patrón desconocido tenga menor riesgo de ser clasificado incorrectamente.

2

x1

x2

R1

R2

R1

R2

buena generalización

mala generalización

Patrón desconocido

Dos clasificadores que separan correctamente los patrones de entrenamiento.

• La idea básica de la máquina de vectores de soporte (SVM, support vector machine) es construir una única solución que tenga el máximo margen, es decir, un hiperplano que separe los datos y se encuentre más alejado de cualquier patrón de entrenamiento.

3

Conceptos básicos

El entrenamiento de una SVM consiste en encontrar el hiperplano óptimo, esto es, aquel con la máxima distancia z=z++z− hacia los patrones de entrenamiento más cercanos, denominados vectores de soporte (círculos sólidos).

x1

x2

R1

R2

hiperp

lano ó

ptimo

z+

z−

• Partiendo del caso de dos clases, ω1 y ω2, entrenar una SVM a partir de los patrones de entrenamiento (yi,xi), para i=1,…,N y yi∈{−1,1}.

• El hiperplano óptimo de separación

4

Conceptos básicos

g(x) = wTx +w0= 0 (1)

se encuentra dentro de la región definida por dos hiperplanos paralelos (o márgenes)

g +(x) = wTx +w0= 1

y

g −(x) = wTx +w0= −1

(2)

(3)

donde w es el vector de pesos y w0 el bias.

• Entonces el ancho del margen entre los hiperplanos g+(x) y g−(x) es equivalente a

5

Conceptos básicos

z + + z − = 1w

+ 1w

= 2w

(3)

wTx +w0≥ +1 ∀x ∈ω

1

wTx +w0≤ −1 ∀x ∈ω

2

de tal manera que

(4)

x1

x2

z+

z−

direc

ción

2

z−

z+dirección 1

El objetivo del entrenamiento de un clasificador SVM es encontrar la dirección que provea el margen más amplio entre clases, i.e., maximizar (3).

SVM caso separable• Seleccionar los pesos w y w0 tal que el

conjunto de entrenamiento sea descrito como:

6

1w

x1

x2

1w

w

−w0

w +−

wTxi+w

0≥ +1, para y

i= +1

wTxi+w

0≤ −1, para y

i= −1

(5)

lo cual puede combinarse como:

yi(wTx

i+w

0) ≥ 1 (6)

minww , sujeto a y

i(wTx

i+w

0)− 1 ≥ 0, ∀i (7)

• Maximizar el margen es equivalente a minimizar las magnitudes de los pesos:

2w

• Minimizar es equivalente a minimizar , lo cual puede resolverse mediante programación cuadrática.

w 12 w

2

• Para satisfacer las restricciones en la minimización, se necesitan incluir multiplicadores de Lagrange* α, donde αi ≥ 0 ∀i:

7

L(w,w0,αα) = 1

2 w2− α

iyi(wTx

i+w

0)− 1( )

i=1

N

∑

*Estrategia para encontrar el máximo o mínimo local de una función sujeta a restricciones de igualdad. Tutorial: https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/constrained-optimization/a/lagrange-multipliers-single-constraint

(8)

• Derivando (8) con respecto de w y w0 e igualando a cero:∂L∂w

= w − αiyixi

i=1

N

∑ = 0

∂L∂w0

= αiyi

i=1

N

∑ = 0

(9)

(10)

• Eliminando w y w0 en (8) usando las condiciones en (9) y (10) :

L(αα) = αi

i=1

N

∑ − 12

αiαjyiyjxiTxj

i,j

N

∑ , s.a. αi≥ 0 ∀i y α

iyi

i=1

N

∑ = 0

= αi

i=1

N

∑ − 12

αihijαj

i,j

N

∑ , donde hij= y

iyjxiTxj

(11)

SVM caso separable

• La formulación en (11) es la forma dual de la formulación primaria en (7), esto es:

8

maxαα

αi

i=1

N

∑ − 12ααTHαα

⎛⎝⎜

⎞⎠⎟, s.a. α

i≥ 0 ∀i y α

iyi

i=1

N

∑ = 0 (12)

donde H es la matriz hessiana y es positiva definida.

• Una vez encontrados los multiplicadores de Lagrange, los pesos w y w0 se calculan como:

w = αsysxs

s∈S∑

w0= 1Ns

ys− α

mymxmT xs

m∈S∑⎛

⎝⎜⎞⎠⎟s∈S

∑

(13)

(14)

donde los vectores de soporte xs son las muestras xi para los cuales αi>0 y S denota el conjunto de vectores de soporte con Ns elementos.

SVM caso separable

9

Un patrón de prueba se clasificará como:

y = sgn(wTx +w0)

x1

x2R2

R1

− +

(15)

SVM caso separableEntrenamiento SVM

Begin initialize: ε←valor muy pequeño próximo a ceroH←(yTy)(XTX) // Crear matriz hessiana

α*←maxα L(α) // Dado H, computar α* mediante programación cuadrática

S←{xi|αi > ε} // Encontrar el conjunto de vectores de soporte

w← // Computar el vector de pesos

w0← // Computar el bias

return w, w0

end

αsysxss∈S∑

1Ns

ys− α

mymxmT xsm∈S∑( )s∈S∑

*

donde sgn(·) es la función signo, de modo que xxxxx si y=+1 ó xxxxxx si y=−1.

x 2 !1 x 2 !2

• En la función objetivo de la SVM, cada elemento de la matriz hessiana se calcula a partir del producto escalar entre todos los posibles pares de patrones:

10

Producto escalar

hij= y

iyjxiTxj, i, j = 1,…,N (16)

• El producto escalar provee una medida de similitud entre dos vectores a y b en términos del coseno del ángulo entre ellos:

〈a,b〉 = aTb = a ⋅ b = a b cosθ (17)

θ = cos−1 a ⋅ ba b

a

b

• Si dos vectores unitarios son paralelos, el producto escalar es ‘1’; si son perpendiculares, el producto escalar es ‘0’; y si son diametralmente opuestos el producto escalar es ‘−1’.

11

Producto escalar• Al maximizar L(α) se observan los siguientes casos:

1. Si dos patrones xi y xj son ortogonales, su producto escalar es ‘0’ y no contribuyen a L(α).

2. Si dos patrones xi y xj son completamente similares, su producto interno es ‘1’, de modo que se derivan dos subcasos:

a. Si xi y xj predicen el mismo valor de salida yi (ambos −1 ó +1) el valor de L(α) disminuye. Por tanto, patrones similares pertenecientes a la misma clase tienen poca importancia.

b. Si xi y xj predicen diferente valor de salida yi (uno es −1 y el otro +1) el valor de L(α) aumenta. Por tanto, éstos son los patrones que se buscan, que sean parecidos aunque de clases diferentes.

xj

x1

x2

x1

x2

xi

x1

x2

xi

xj

xi

xj

• Durante el entrenamiento, la SVM considera como error de clasificación a un patrón que cae dentro del margen, aún si éste se encuentra del lado correcto del hiperplano.

• Por tanto, sólo los patrones que están fuera del margen y están del lado correcto del hiperplano no contribuyen al conteo de errores.

• Si la clases son linealmente separables se puede encontrar un margen que no genera errores de clasificación.

• Sin embargo, en el caso de clases no linealmente separables aún se puede construir un hiperplano de separación aunque considerando que existirán errores de clasificación.

• Entonces, además de maximizar el ancho del margen se debe minimizar el número de errores.

12

SVM caso no separable

• Para construir un hiperplano entre clases no linealmente separables se puede hacer la siguiente analogía: supóngase que se tienen dos poblaciones cercanas y se desea construir un camino entre ellas que sea lo más ancho posible y que involucre el menor número de casa demolidas por donde pasará el camino.

13

SVM caso no separable

buena generalización

mala generalización

x1

x2• Entonces, el clasificador debe

ser colocado entre dos áreas densamente pobladas y en una región donde los datos están más dispersos.

• Lo anterior estará determinado por la condición de “buena” generalización que el clasificador debe tener.

• Para tratar con clases no linealmente separables, se introduce una variable de “relajación”, ξ, a las restricciones:

14

wTxi+w

0≥ +1 − ξ

i, para y

i= +1

wTxi+w

0≤ −1 + ξ

i, para y

i= −1

(18)

lo cual puede combinarse como:

yi(wTx

i+w

0)− 1 + ξ

i≥ 0

donde ξi≥0, para i=1,…,N.

• A este enfoque se le conoce como SVM de margen suave, ya que datos en el lado incorrecto del margen poseen una penalización que aumenta conforme se alejan del borde del margen.

1w

x1

x2

1w

w

−w0

w +−

− ξw

(19)

SVM caso no separable

• Para reducir el número de errores se define el hiperplano de separación óptimo del L1-SVM, cuyo problema de optimización se expresa como:

15

(20)min 12 w

2+C ξ

ii=1

N

∑ , s.a. yi(wTx

i+w

0)− 1 + ξ

i≥ 0, ∀i

donde el parámetro C es un valor de penalización que controla el balance entre la variable de error y el ancho del margen.

• Introduciendo los multiplicadores de Lagrange αi, se obtiene el problema dual:

maxαα

αi

i=1

N

∑ − 12ααTHαα

⎛⎝⎜

⎞⎠⎟, s.a. 0 ≤ α

i≤C ∀i y α

iyi

i=1

N

∑ = 0 (21)

• Resolviendo el problema dual, los pesos w y w0 se calculan con (13) y (14), respectivamente, a partir de los vectores de soporte.

SVM caso no separable

• Alternativamente, el L2-SVM utiliza la suma de cuadrados de las variables de relajación ξi en la función objetivo en lugar de sumas lineales de ξi.

• Entonces, el problema de optimización es:

16

(22)min 12 w

2+C

2ξi2

i=1

N

∑ , s.a. yi(wTx

i+w

0)− 1 + ξ

i≥ 0, ∀i

• Introduciendo los multiplicadores de Lagrange αi, se obtiene el problema dual:

maxαα

αi

i=1

N

∑ − 12

αihijαj

i,j

N

∑⎛⎝⎜

⎞⎠⎟, s.a. α

i> 0 ∀i y α

iyi

i=1

N

∑ = 0 (23)

donde hij= y

iyj(xiTxj+ δijC )

donde δij=1 para i=j y 0 en otro caso.

SVM caso no separable

17

x2

x1

x2

x1

C=0.2 C=1000

Ejemplo de dos clases no separables y el resultado del clasificador SVM (línea sólida) con sus márgenes asociados (líneas discontinuas). Cuando el valor de C es grande se incluyen menos puntos dentro del margen. Contrariamente, cuando el valor de C es pequeño se admiten más errores.

SVM caso no separable

• El desbalanceo de clases se da cuando una clase tiene mucho más muestras que la otra, y en el caso no separable, el clasificador SVM producirá un hiperplano que favorecerá a la clase mayoritaria.

• Este problema sucede porque se asigna la misma importancia a los errores generados en ambas clases.

• Para corregirlo, se deben asignar costos diferentes para los errores de cada clase, de modo que el costo de clasificación errónea se reemplaza por dos términos:

18

Clases desbalanceadas

C ξi

i=1

N

∑ →C1

ξi

i∈ω1

∑ +C2

ξi

i∈ω2

∑ (24)

donde C1 y C2 son los valores de penalización para las clases ω1 y ω2, respectivamente. Con este esquema se le dará mayor peso a los errores de la clase minoritaria.

• Asumiendo que el número de errores de cada clase es proporcional al número de muestras en cada clase, entonces C1 y C2 se calculan como:

19

Clases desbalanceadas

CN = 2C1N1= 2C

2N2 (25)

donde N1 y N2 son el número de muestras en las clases ω1 y ω2, respectivamente, tal que N1+N2=N.

Clases no separables desbalanceadas clasificadas con L2-SVM. A la izquierda, mismo valor de C para ambas clases, a la derecha, diferentes valores de C.

x2

x2

x1

x1

SVM no lineal• La SVM con margen suave puede tener un desempeño adecuado aún cuando

los datos en clases diferentes presentan un traslape “leve”.

• Sin embargo, existen problemas de clasificación que no pueden ser resueltos adecuadamente usando funciones discriminantes lineales directamente sobre el espacio de características original.

• Para tratar con estos casos, un enfoque consiste en mapear los datos a un espacio de alta dimensionalidad en donde se espera, con alta probabilidad, que las clases sean linealmente separables.

20

x1

x2

x1 x

2

x 12+x 22

Izquierda: un conjunto de datos en R2 no linealmente separable. Derecha: los mismos datos mapeados a R3 con la transformación [x1,x2 ] = [x1,x2,x1

2 + x22 ].

R2

R3

• La dimensionalidad de los datos aumenta explícitamente al incluir características no lineales, es decir, RN → RM con E>D.

• En ese espacio de alta dimensionalidad se construye un hiperplano de decisión utilizando la formulación original de la SVM lineal:

21

SVM no lineal

g(x) = wTΦ(x)+w0

(26)

donde cada patrón ha sido mapeado como .iiiiiiiiiiiii de modo que

hij= y

iyjΦ(x

i)TΦ(x

j), i, j = 1,…,N

maxαα

αi

i=1

N

∑ − 12

αihijαj

i,j

N

∑⎛⎝⎜

⎞⎠⎟, s.a. 0 ≤ α

i≤C ∀i y α

iyi

i=1

N

∑ = 0

• Resolviendo el problema dual en (26), un patrón x se clasifica como:

(27)

(28)

x ! (x)

RD ! RE

22

SVM no lineal

x1

x2

x1 x

2

x 12+x 22

Izquierda: hiperplano de decisión SVM generado en R3. Derecha: la frontera de decisión cuando es transformada a R2 es una función no lineal.

R3

R2

• Aunque este enfoque es atractivo debido a su simplicidad, se deben considerar las problemas computacionales que surgen al aumentar la dimensionalidad de RN a RM (con E>D).

• Por ejemplo, utilizando una transformación polinomial de segundo orden, para un patrón xxxxxx, se genera el siguiente patrón:

23

SVM no lineal

• En general, una función polinomial de orden q realiza un mapeo de un espacio RN a uno -dimensional.

• Por tanto, para conjuntos de datos con alta dimensionalidad, esta transformación explícita se vuelve computacionalmente intratable.

D+qq

⎛⎝⎜

⎞⎠⎟

Φ(x) = 1, 2x1, 2x2,…, 2xD ,x12,x2

2,…,xD2 , 2x1x2, 2x1x3,…, 2x1xD , 2x2x3,… 2x1xD , 2xD−1xD⎡⎣ ⎤⎦

T

Términos cuadráticos cruzados

Términos puramente cuadráticos

Términos lineales

Término constante

RD RE

x 2 RD

RD

24

• Para evitar una transformación explícita del conjunto de datos, se utilizan funciones kernel, las cuales implícitamente transforman los datos a un espacio de alta dimensionalidad RM.

• De este modo, los productos escalares en la matriz hessiana de la SVM se reemplazan por una función kernel, K(a,b) donde xxxxxxxx:

SVM no lineal

hij= y

iyjΦ(x

i)TΦ(x

j)

= yiyjK(x

i,xj), i, j = 1,…,N

(29)

donde la función K(a,b) debe ser semidefinida positiva.

• A este enfoque se le conoce como el “truco del kernel”: existe una versión no lineal de cualquier clasificador lineal si se encuentra una transformación no lineal Φ(a) a un espacio de mayor dimensionalidad provisto de un producto escalar que pueda ser expresado como K(a,b)=Φ(a)⋅Φ(b).

RE

a,b 2 RD

25

SVM no lineal• Considerando la transformación polinomial de segundo orden

para dos patrones xxxxxxxx:Forma explícita Forma implícita

(a ⋅b +1)2 = (a ⋅b)2 + 2a ⋅b +1

= aibii=1

D

∑⎛⎝⎜⎞⎠⎟

2

+ 2 aibii=1

D

∑ +1

= aibiajbjj=1

D

∑ +i=1

D

∑ 2 aibii=1

D

∑ +1

= ai2bi

2

i=1

D

∑ + 2 aibiajbjj=i+1

D

∑ +i=1

D

∑ 2 aibii=1

D

∑ +1

= Φ(a) ⋅Φ(b)

a,b 2 RD

Φ(a) ⋅Φ(b) =

12a12a2:2aDa12

a22

:aD2

2a1a22a1a3:2a1aD2a2a3:2a1aD:

2aD−1aD

⎛

⎝

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎞

⎠

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

•

12b12b2:2bDb12

b22

:bD2

2b1b22b1b3:2b1bD2b2b3:2b1bD:

2bD−1bD

⎛

⎝

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎞

⎠

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

1+

+

+

2 aibi

i=1

D

∑

ai2bi2

i=1

D

∑

2 aiajbibj

j=i+1

D

∑i=1

D

∑

• Las funciones kernel más comunes en la práctica son:

26

SVM no lineal

Función Expresión Parámetros

Lineal ---

Polinomial Orden del polinomio q.

Gaussiana (RBF)

Ancho de la Gaussiana con

Sigmoidal Para algunos valores de

K(a,b) = aTb

K(a,b) = (aTb + 1)q

K(a,b) = exp(−γ a − b 22)

K(a,b) = tanh(α(aTb)+ β)

γ > 0

α> 0 y β > 0

27

SVM no linealEntrenamiento L2-SVM no lineal

Begin initialize: C←penalización, ε←toleranciaK←K(X,X) // Aplicar función kernel al conjunto de datosH←(yTy)(K+I/C) // Crear matriz hessiana

α*←maxα L(α) // Dado H, computar α* mediante programación cuadrática

S←{xi | αi > ε} // Encontrar el conjunto de vectores de soportew←{αsys | s∈S} // Computar el vector de pesosw0← // Computar el biasreturn S, w, w0

end

1Ns

ys− α

mymK(x

m,xs)

m∈S∑( )s∈S∑

Clasificación SVM no lineal Begin:

K←K(S,Xt) /* Aplica función kernel al conjunto de datos de prueba, Xt, dados los vectores de soporte, S */

gt←wTK+w0 // Evalúa la función lineal discriminanteyt←sgn(gt) // Asigna una etiqueta de clasereturn gt, yt

end

*

*

28

SVM no linealq = 3, C = 100 γ = 1 2, C = 100 α = 1 10, β = −1, C = 100

• Mangasarian y Musicant* propusieron un método simple y rápido para resolver el procedimiento de programación cuadrática denominado algoritmo LSVM.

• El programa cuadrático para encontrar los multiplicadores de Lagrange, α, se basa en el siguiente esquema iterativo:

29

Algoritmo LSVM

*O. L. Mangasarian and David R. Musicant; Lagrangian Support Vector Machines, Journal of Machine Learning Research 1, pp. 161-177, 2001.

αα(1) = H−1e

αα(k + 1) = H−1e + f(k) + f(k)

2⎛⎝⎜

⎞⎠⎟

⎧

⎨⎪

⎩⎪

donde |·| indica valor absoluto y el vector f se computa como:

(30)

(31)

donde e es un vector columna con unos y u=1.9/C. El criterio de paro del algoritmo LSVM es o se haya cumplido el número máximo de iteraciones.

αα(k − 1)− αα(k) < θ

f(k) = Hαα(k)− e − uαα(k)

30

k = 1 k = 50 k = 100

k = 150 k = 250 k = 400

Evolución del entrenamiento del L2-SVM mediante el algoritmo LSVM.

Algoritmo LSVM

Selección de hiperparámetros

• El entrenamiento de la SVM requiere definir hiperparámeros, por ejemplo, en la SVM con kernel Gaussiano se debe especificar la penalización C y ancho de banda g.

• Un proceso común de selección de hiperparámetros es mediante búsqueda malla y validación cruzada, donde los hiperparámetros con el menor error de validación cruzada son retornados.

• Proceso de validación cruzada:

1. El conjunto de entrenamiento X es dividido aleatoriamente y de manera estratificada en K conjuntos disjuntos de igual tamaño, X1,…,XK.

2. K ejecuciones de entrenamiento y validación son realizadas. En la i-ésima ejecución, Xi es usado para validar el error de clasificación mientras que la unión de los subconjuntos restantes xxxxxxxxx son usados para entrenar.

3. Finalmente, el promedio de los K errores de clasificación es el error de validación cruzada.

31

[i6=j

Xj

32

Selección de hiperparámetros

2

6664

(C1, 1) (C2, 1) · · · (CA, 1)(C1, 2) (C2, 2) · · · (CA, 2)

......

. . ....

(C1, B) (C2, B) · · · (CA, B)

3

7775

12345

Entrenamiento

Validación

• Para la SVM con kernel Gaussiano se suelen probar secuencias de valores de C y g exponencialmente incrementales: xxxxxxxxxxxxxxxxxx y xxxxxxxxxxxxxxxxxxx.

• Ejemplo de búsqueda malla con validación cruzada de 5 experimentos:

C = 25, 24, . . . , 215 = 215, 214, . . . , 23

Por cada par de hiperparámetros xxxxxx se calcula el error de validación cruzada. Al final, el par de valores óptimos son lo que generaron el menor error.

(Ci, j)