svm máquinas de vectores de soporte

Aprendizaje Estadístico

Universidad Nacional de Colombia

Betsy Estrada – Carlos Mera

SUPPORT VECTOR MACHINE Betsy Mary Estrada Perea

Carlos Andrés Mera Banguero

Asignatura: Aprendizaje Estadístico

UNIVERSIDAD NACIONAL

DE COLOMBIA




CONTENIDO

LO QUE VAMOS A VER …

Support vector Machine

Introducción

Formalización

SVM para Multiclase

Ventajas y Desventajas

Ejemplo de SVM

Un Ejemplo Simple -> Caso Lineal

Ejemplo usando Matlab

Ejemplo usando WEKA




SUPPORT VECTOR MACHINE

INTRODUCCIÓN





INTRODUCCIÓN:

Las Máquinas de Soporte Vectorial o Máquinas de Vectores de Soporte son un

conjunto de algoritmos de aprendizaje supervisado desarrollados por Vladimir

Vapnik.

Estos algoritmos pueden ser usados en una diversidad de problemas de

aprendizaje, específicamente en Clasificación y Regresión.

Dado un conjunto de ejemplos de entrenamiento (de muestras) podemos etiquetar

las clases y entrenar una SVM para construir un modelo que prediga la clase de

una nueva muestra.





INTRODUCCIÓN:

Aunque son innumerables las aplicaciones de las SVM, a continuación

presentamos algunas de sus aplicaciones:

En Visión Artificial para el reconocimiento de Caracteres, Rostros, Matrículas y

Objetos

En Medicina, para la clasificación de exámenes radiológicos, TAC, y otros para el

diagnóstico de tejido humano.

En Genética para Predicción de Genes

Clasificación de documentos

En Simulación, para la modelación de sólidos

En Interfaces humano-computador

En Identificación de hablantes

En predicción en economía





¿CÓMO FUNCIONAN LAS SVM?






En general, dado un conjunto de datos de entrenamiento, la SVM busca el

hiperplano que separe de forma óptima los puntos de una clase de la de otra.

Consideremos un problema de dos

clases, linealmente separable, como

se ilustra en la figura …

Hay muchas fronteras de decisión

(o hiperplanos) posibles que pueden

separar las clases (toda recta que

separe las clases).

¿Son todas esas fronteras igual de

buenas?





¿CÓMO SE SELECCIONA EL MEJOR HIPERPLANO (O FRONTERA DE DECISIÓN)?






La SVM busca el hiperplano que maximice la distancia (o margen) con los puntos

que estén más cerca de él mismo, razón por la cual también se les conoce a las

SVM como clasificadores de margen máximo.

Margen

Pequeña Margen

Grande Vectores Soporte

Vectores Soporte





EN NOTACIÓN FORMAL …






Cada observación (o dato del conjunto de entrenamiento) contiene un par de datos:

Un Vector

Una etiqueta

Como el hiperplano separa las muestras positivas (+1) de las negativas (-1), los

puntos que están en el hiperplano deben satisfacer la ecuación: wT x + b = 0,

como se ilustra en la siguiente figura …

l,...,1, iRx n

i

}1,1{ iy






Ahora el problema se convierte en un problema de optimización ya que para

encontrar el mejor hiperplano que separa las clases se debe maximizar la margen m.

w

Donde,

El vector W es la normal al hiperplano.

es la distancia perpendicular del

hiperplano al origen.

es la norma del vector W.

es la margen o distancia

entre los hiperplanos positivo y

negativo.

w

b

w

w

2m





El problema es o cual se consigue (matemáticamente)

sujeto a que

Para resolver este problema se usan Multiplicadores de Lagrange, de tal forma que

se debe construir una función Lagrangiana tal que:

Sujeta a que: i 0 y

Finalmente, W se puede calcular gracias a los términos así:

Con

Nota: Los paquetes hacen todo esto por nosotros :)


||||

2max

w

2

2

1min w

nibxwy i

T

i ...11)(





¿QUÉ PASA CUANDO TENEMOS UN CASO COMO COMO EL QUE SIGUE?





SVM CON SOFT-MARGIN

¿Qué hacer cuando solo hay uno pocos datos que no permiten separar linealmente

el conjunto de datos?

¿creamos un modelo COMPLEJO

que no es necesariamente general?

¿creamos un modelo SIMPLE con

algunos errores de clasificación?





SVM CON SOFT-MARGIN

Con el fin de permitir cierta flexibilidad, los SVM manejan un parámetro C que

controla la compensación entre errores de entrenamiento y los márgenes rígidos,

creando así un margen blando (soft-margin) que permita algunos errores en la

clasificación xi.

Nótese que si xi =0, no hay error, así se busca minimizar:

La constante C determina la holgura del margen blando. La elección de este valor y

del tipo de función kernel influyen en el desempeño de las SVM.





SVM CON SOFT-MARGIN

Si C tiene un valor grande, los datos de entrenamiento se clasificarán

correctamente.

Si C tiene un valor pequeño puede ocurrir que haya demasiados datos de

entrenamiento mal clasificados.

Con C apropiado Con C grande





¿Y SI LOS DATOS NO SE PUEDEN SEPARAR LINEALMENTE ?





MODELOS NO LINEALES

Cuando los datos no se pueden separar linealmente se hace un cambio de espacio

mediante una función de transformación que aumenta la dimensionalidad de los

vectores de entrada a un espacio al que se puedan separar linealmente por un

hiperplano. A tal función se llama Kernel.

Al introducir un kernel, los parámetros del vector w se hayan así:





MODELOS NO LINEALES

Existen diferentes tipo de funciones Kernel:

Kernel Polinomial de grado d (muy usado en reconocimiento de imágenes)

Kernel de Base Radial de ancho s

Su espacio de llegada es de dimensión infinita.

Kernel Sinusoidal con parámetros k y q

Problema: No satisface la condición de Mercer (definida positiva) para todo k y

q.





¿CÓMO SE CLASIFICA UN NUEVO DATO?





SVM – CLASIFICACIÓN:

Para clasificar un nuevo punto se usa el signo de la siguiente función:

Donde, si son los vectores soporte, y donde la función de transformación es

definida por el kernel K: (si) (x) = K(si, x).

De tal manera que si se obtiene como resultado de la función f(x), un número

negativo, el punto es clasificado como -1 o su clase equivalente, y si se obtiene un

número positivo el punto es clasificado como +1 o su clase equivalente (más

adelante se presenta un ejemplo).





¿Y QUÉ PASA CUANDO SON MÁS DE DOS CLASES ?





SVM - MULTICLASE

Una clase versus todas las clases, por ejemplo para 3 clases se requiere crear tres

SVM así:

SVM 1 vs. 2+3

SVM 2 vs. 1+3

SVM 3 vs. 1+2

Una clase versus otra clase (solución adoptada por SMO de Weka), por ejemplo

con tres clases:

SVM 1 vs. 2

SVM 1 vs. 3

SVM 2 vs. 3

En este caso, la asígnación de etiqueta se hace usando alguna estrategia de

consenso, por ejemplo, por votación (se asigna la etiqueta con más votos).





SVM: VENTAJAS Y DESVENTAJAS




SUPPORT VECTOR MACHINE - EJEMPLOS

VENTAJAS:

Las SVM tienen ciertas características que las han puesto en ventaja, comparadas

con otras técnicas de clasificación:

Al usar un principio inductivo, que busca la minimización del riesgo estructural,

usando una función kernel, le da la una gran capacidad de generalización, incluso

cuando el conjunto de entrenamiento es pequeño.

El proceso de entrenamiento (o aprendizaje) no depende necesariamente del

número de atributos, por lo que se comportan muy bien en problemas de alta

dimensionalidad.





VENTAJAS:

Existen pocos parámetros a ajustar; el modelo solo depende de los datos con

mayor información.

La estimación de los parámetros se realiza a través de la optimización de una

función de costo convexa, lo cual evita la existencia de un mínimo local.

El modelo final puede ser escrito como una combinación de un numero muy

pequeño de vectores de entrada, llamados vectores de soporte, lo cual se

presenta ya que el Lagrangiano de la mayoría de los vectores es igual a cero.

El compromiso entre la complejidad del clasificador y el error puede ser controlado

explícitamente





DESVENTAJAS:

Algunas de las Desventajas de las SVM son:

Cuando los parámetros son mal seleccionados se puede presentar un problema

de sobre entrenamiento, el cual ocurre cuando se han aprendido muy bien los

datos de entrenamiento pero no se pueden clasificar bien ejemplos nunca antes

vistos .

En gran medida, la solución al problema, así como su generalización depende del

kernel que se use y de los parámetros del mismo.





UN EJEMPLO PARA ENTENDER EL FUNCIONAMIENTO DE UNA SVM





EJEMPLO EN EL CASO LINEAL …

Iniciamos con un ejemplo en el que la función es trivial: supongamos que

tenemos un conjunto de ejemplos positivos y negativos en R2:

Ejemplos Positivos:

{(3,1), (3,-1), (6,1), (6,-1)}

Ejemplos Negativos:

{(1,0), (0,1), (0,-1), (-1,0)}

Ejercicio: Grafique los puntos y encuentre los vectores soporte

Nota: El ejemplo a continuación es una versión simplificada que busca explicar el

funcionamiento de las SVM sin la rigurosidad matemática que implica las mismas.






Graficando los puntos anteriores tenemos …

Buscamos una SVM que nos permita separar con precisión las dos clases. Dado que los datos

son linealmente separables podemos usar un kernel lineal (), que por la sencillez del

problema será la función identidad … de este modo ¿Cuáles serán los vectores soporte?.






Por inspección del gráfico vemos que hay tres vectores soporte:

Vectores Soporte: {s1= (1,0), s2 = (3,1), s3=(3,-1)}






Por inspección del gráfico vemos que hay tres vectores soporte:

Se buscará la mejor solución de entre todas las posibles que maximice m Sin embargo, no

lo hacemos con toda la rigurosidad matemática del caso por ser un ejemplo ilustrativo y se usa

la intuición para resolverlo.

w

2






A continuación aumentamos los vectores soporte con un bias 1 de entrada

(aumento en la dimensión) y tenemos que ahora los vectores soportes

aumentados:

{ŝ1= (1,0,1), ŝ2 = (3,1,1), ŝ3=(3,-1,1)}

Necesitamos hallar la ecuación del hiperplano que separe las clases:

Para obtener wT y b, debemos hacer uso de todos los vectores soporte y resolver el

siguiente sistema de ecuaciones (una ecuación por vector soporte):

0bxwT






Optimizando con respecto a los multiplicadores Lagrange se produce el siguiente

conjunto de ecuaciones, el cual debemos resolver para obtener los coeficientes :

Como en estas ecuaciones estamos usando el kernel, debemos aplicar la función

de transformación definida con el.






Como estamos usando un kernel lineal () que es la función identidad con un bias

adicional, el sistema de ecuaciones se reducen a:

Desarrollando el producto punto, tenemos:

Ahora desarrollamos el sistema de ecuaciones para hallar los valore de . Con un

poco de algebra tenemos: 1 =3.5; 2 = 0.75 y 3 = 0.75.






Una vez tenemos los valores debemos hallar el hiperplano discriminante, tal que:

2

0

1

1

1

3

75.0

1

1

3

75.0

1

0

1

5.3

~

i

iisw






Finalmente, como los vectores fueron aumentados con un bias, podemos igualar

el último termino del vector con el parámetro b del hiperplano, siendo w = ,

de tal manera que su ecuación es:

Resolviendo, la ecuación anterior tenemos que x= 2, así que usando dos puntos

con x1 = 2 tenemos:

w

020

1

x

T

0

1






Hiperplano: 020

1

x

T






¿Cómo se utiliza la ecuación del hiperplano para clasificar un nuevo dato?

Para clasificar un nuevo dato se usan los vectores soporte y el kernel de

transformación así (versión simplificada de la formula presentada antes):

Donde (z) retorna el signo de z.

Con lo anterior como se clasificarían los puntos (1,1) y (5,-1) ?

020

1

x

T

)()()( xsxf

i

ii






Para x = (1,1), tenemos

Por tanto (1,1) es clasificado como NEGATIVO

0.1

25.275.30.7

1

1

1

75.0

75.0

25.2

1

1

1

75.0

75.0

25.2

1

1

1

5.3

0

5.3

1

1

1

1

1

3

75.0

1

1

1

1

1

3

75.0

1

1

1

1

0

1

5.3

1

1

1

375.0

1

1

1

375.0

1

1

0

15.3)1,1(

f





UN DEMO CON MATLAB Y STPRTOOL (STATISTICAL PATTERN RECOGNITION TOOLBOX)





EJEMPLO DE UN DEMO CON MATLAB …

Para correr el demo se debe descargar el ToolBox de Reconocimiento Estadístico

de Patrones (STPRtool) e instalarlo en matlab:

http://cmp.felk.cvut.cz/cmp/software/stprtool/manual/index.html

Una vez instalado, este se ejecuta con el comando demo_svm

http://cmp.felk.cvut.cz/cmp/software/stprtool/manual/index.html





EJEMPLO DE UN DEMO CON MATLAB (EXPLICACIÓN DE LO QUE SE HACE EN

DIRECTO) …

Cuando se ejecuta este demo aparece una pantalla en la que se nos permite

seleccionar el algoritmo y el kernel que será usando para entrenar la SVM, al igual

que cargar un conjunto de datos o realizar nuestro conjunto de prueba en un plano

cartesiano, como se ilustra en la figura de la siguiente diapositiva





Algoritmo

Tipo de Kernel

Parámetros del

Algoritmo y el Kernel

Para entrenar

la SVM

Para cargar o crear los

datos del cto de

entrenamiento





Creamos un conjunto de datos linealmente separable ….





Entrenamos la SVM para ver el resultado de separabilidad …





Creamos un conjunto de datos que NO es linealmente separable ….





Entrenamos usando un Kernel de Base Radial y se explica el rol del parámetro C

en el algoritmo ….





UN EJEMPLO USANDO EL CONJUNTO DE DATOS IRISFISHER EN MATLAB …






Ahora usaremos la línea de comandos para crear una SVM y clasificar un dato

usando el Dataset de Fisher “iris”.

Se han creado dos ejemplos. El primero de ellos solo tiene en cuenta el ancho y

alto del sépalo dado que estos son los atributos más significativos [REF] y se usan

solo dos clases: Setosa y NO Setosa … esto con el fin de visualizar la SVM. El

segundo ejemplo se realiza usando todos los atributos y todas las clases.






Fisheriris (Ejemplo - 1): los datos cargados están modificados de tal forma que

solo se tuvieron en cuenta el ancho y alto del sépalo y solo hay dos categorias:

Setosa y NO setosa, además se usa una SVM-multiclase con una descomposición

“One-Agains-All”

>> data = load('iris'); %Conjunto de Datos

>> options.solver = 'smo'; %Tipo de SVM a usar

>> options.ker = 'rbf'; %Tipo de Kernel a Usar

>> options.arg = 1; % Argumento del Kernel

>> options.C = 10; % Constante de Regularizacion

>> model = oaasvm(data,options ); % Se entrena la

>> figure;

>> ppatterns(data);

>> ppatterns(model.sv.X,'ko',12);

>> pboundary(model);






Fisheriris (Ejemplo - 1): Resultado gráfico obtenido






Fisheriris (Ejemplo - 2): Se usan los datos originales del Dataset con una SVM-

multiclase con una descomposición “One-Agains-All” (Los comandos son los

mismos del modelo anterior)

Nota: Se explica que por la

dimensionalidad en los datos, no es

posible ver gráficamente la función

discriminante





UN EJEMPLO USANDO WEKA





EJEMPLO CON WEKA …

La desventaja de Matlab es que se requiere un conjunto de prueba adicional al de

entrenamiento, mientras que con Weka se pueden usar los diferentes tipos de

validación y además entrega las matrices de confusión y demás …





EJEMPLO CON WEKA …

SVM con un algoritmo

SMO y sus parámetros

Matriz de Confusión

del Modelo





ALGUNAS REFERENCIAS …

C. J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition”,

Kluwer Academic Publishers: http://research.microsoft.com/en-

us/um/people/cburges/papers/svmtutorial.pdf

F. Dmitriy and M. Ilya "Support Vector Machines for Classification" in J. Abello and

G. Carmode (Eds) "Discrete Methods in Epidemiology", DIMACS Series in Discrete

Mathematics and Theoretical Computer Science, volume 70, pp. 13–20, 2006

I. Steinwart and A. Christmann. “Support Vector Machines”. Springer-Verlag, NY,

2008

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and

other kernel-based learning methods. Cambridge University Press, 2000

C. J. C. Burges and B. Sch¨olkopf. Improving the accuracy and speed of support

vector learning machines.In M. Mozer, M. Jordan, and T. Petsche, editors,

Advances in Neural Information Processing Systems 9,pages 375–381, Cambridge,

MA, 1997. MIT Press.

http://research.microsoft.com/en-us/um/people/cburges/papers/svmtutorial.pdf
















ALGUNAS REFERENCIAS …

Corinna Cortes, Vladimir Vapnik, "Support-Vector Networks", Machine Learning,

20, pp.273-297 (1995)

Edgar Osuna, Robert Freund, and Federico Girosi. Training support vector

machines: an application to face detection. In IEEE Conference on Computer Vision

and Pattern Recognition, pages 130 – 136, 1997.

M. Schmidt. Identifying speaker with support vector networks. In Interface ’96

Proceedings, Sydney, 1996.

B. Sch¨olkopf. Support Vector Learning. R. Oldenbourg Verlag, Munich, 1997.




PREGUNTAS

svm máquinas de vectores de soporte

Documents