SISTEMAS INTELIGENTES - aic.uniovi.esaic.uniovi.es/ssii/SSII-T11-MetodosKernel-SVM.pdf · Centro de Inteligencia Artificia l Universidad de Oviedo Sistemas Inteligentes - T11: Métodos

Centro de Inteligencia Artificial

Universidad de Oviedo

Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte

SISTEMAS INTELIGENTES T11: Métodos Kernel:

Máquinas de vectores soporte {jdiez, juanjo} @ aic.uniovi.es




Índice •  Funciones y métodos kernel

°  Concepto: representación de datos °  Características y ventajas °  Funciones más usadas °  Kernelización de algoritmos

• Máquinas Vectores Soporte (SVM) °  Concepto de Margen: maximización °  Teoría: Optimización de funciones °  Clasificación: caso separable y margen blando °  Regresión




Kernels (I) •  Constituyen un forma estándar de representar

los datos •  Hay datos que no se pueden representar

mediante vectores °  Ejemplo: cadenas genéticas

•  Sustituyen las representaciones vectoriales por otra genérica aplicable a datos no vectoriales

•  Permiten construir algoritmos de aprendizaje genéricos que pueden utilizarse sobre cualquier tipo de dato (vectorial o no)




Kernels (II)

Representamos los datos mediante un matriz cuadrada donde cada elemento mide la similitud entre dos ejemplos




Kernels (III) Atributos

Atr-1 … Atr-n Clase(opcional) ejemplo 1 clase ej-1

… … ejemplo n clase ej-n

Ej 1 … Ej j … Ej n Ej 1 k(x1,x1) k(x1,xj) k(x1,xn)

K … Ej i k(xi,x1) k(xi,xj) k(xi,xn)

… Ej n k(xn,x1) k(xn,xj) k(xn,xn)




Funciones kernel: idea

•  Representar la similitud entre dos objetos Aproximación General




Induce una métrica: (1) norma

(2) distancia Interpretación geométrica: Salvo escala de los vectores, el producto escalar mide la separación geométrica de sus direcciones. Esta medida está comprendida entre -1 y +1:

– Es máxima (+1) cuando coinciden y

– Mínima (-1) cuando son opuestos

– Es 0 cuando son perpendiculares

Producto escalar




Funciones kernel (I) Simétrica Semidefinida positiva Si es simétrica y semidefinida positiva, entonces existe un espacio de Hilbert y una función tal que




Funciones Kernel (II) Si son kernels en entonces también son kernels




Ejemplos de Funciones Kernel Kernel Lineal

Kernel Polinómico

Kernel Gaussiano Kernel string, kernel booleano,…




Métodos Kernel •  Son los métodos de aprendizaje que usan para

representar los ejemplos de entrenamiento a través de matrices calculadas mediante la aplicación de funciones kernel

•  Son métodos genéricos •  Kernelización: siempre que un algoritmo se

puede expresar en términos de productos escalares en el espacio de entrada, se pueden reemplazar por productos escalares en un cierto espacio de características mediante una función kernel




Clasificación por mínima distancia




Perceptrón (versión sin kernels)

No es kernelizable, no aparecen productos escalares




Perceptrón (versión dual, kernelizable)




El espacio de características (I)




El espacio de características (II)




Ejemplo (I)




Ejemplo (II)




Máquinas de Vectores Soporte

•  Introducidas en los 90 por Vapnik

•  Se basan en la Minimización del Riesgo Estructural (SRM)

•  92: maximización del margen y uso de kernels

•  95: margen blando

•  Rápido desarrollo: algoritmos más eficientes, diseño de kernels

“No hay nada más práctico que una buena teoría”




General/Específico: más gráficamente

Atributo 1

Atributo 2 Específica General




Planteamiento




Minimización del Riesgo Estructural •  Minimización del Riesgo Empírico (ERM): podemos interpretarlos

como sistemas que tratan de reducir el error empírico •  Minimización del Riesgo Estructural (SRM): estudian el riesgo

estructural en el espacio de hipótesis

+ + +

+ +

+ + + +

_ _ _

_ _ _

_

_

_ _

+




+

Maximización del Margen

_

+ +

+

+ +

+ +

+ _ _

_ _

_ _

_

_




¿Por qué maximizar el margen? •  Resistencia al ruido

en los datos de entrada

•  Resistencia al error en el cálculo de la función de clasificación

•  Propiedades matemáticas que permiten acotar de manera razonable el error de generalización




Margen funcional y geométrico •  Margen funcional: la menor diferencia entre aplicar la función

a los ejemplos de la clase positiva y negativa

•  Margen geométrico: distancia entre los ejemplos de ambas clases, ed, la suma de la distancia del hiperplano al ejemplo más próximo de cada clase

•  definen el mismo hiperplano. Para maximizar uno de ellos debemos mantener fijo el otro. Si mantenemos fijo el funcional ( ), podemos maximizar el geométrico




Maximizando el margen geométrico

+ _

+ +

+

+ +

+ +

+ _ _

_ _

_ _

_

_




Maximizar el margen: minimizar la norma

•  Resolviendo este problema obtendremos el hiperplano de margen geométrico máximo que clasifica correctamente todos los ejemplos. Para resolverlo aplicaremos métodos conocidos de optimización de funciones




•  Problema primal el objetivo es obtener los valores de las variables primales w que minimizan la función objetivo f. Las solución está sujeta a que dichos valores respeten las restricciones de desigualdad gi.

•  Programación lineal: f y gi lineales

•  Programación cuadrática: f cuadrática y gi lineales •  Conjunto admisible: todos los puntos del dominio que cumplen

las restricciones

•  Óptimo w*: para otro w del cjto admisible

Optimización de funciones




Convexidad: óptimos globales (I) •  Def #1. Un dominio es convexo si y solo si el segmento de la

recta que une cualquier par de puntos del dominio también está incluido en el dominio si el dominio es convexo, las restricciones lineales no eliminan la convexidad del cjto admisible

•  Def #2. Una función es convexa si

•  Def #3. Una función doblemente diferenciable es convexa si su matriz Hessiana es semidefinida positiva

•  Def #4. Si tanto el dominio, como la función objetivo y las restricciones son convexas, entonces el problema se dice que es convexo




Convexidad: óptimos globales (II) •  Prop #1. Si una función es convexa, entonces

cualquier mínimo local es también global Demostración: Para cualquier v ≠ w*, por definición de mínimo local, existirá un θ suficientemente cerca de 1 tal que, para cualquier v y por tanto w* mínimo global




Teoría de Lagrange: función lagrangiana Dado el problema de optimización: se define la función langragiana como

donde los αi se denominan multiplicadores de Lagrange (o variables duales) y deben tener un valor no negativo. Indican la importancia de cada restricción




Dualidad (I) •  Def #5. El problema dual del problema primal

planteado es: bajo ciertas condiciones, al resolver el problema dual (restricciones más simples) obtenemos también la solución del problema primal asociado.




Dualidad (II) •  Teorema. sea w una solución admisible del problema primal y α

del dual, entonces W(α) ≤ f(w)

•  El valor del problema dual está acotado superiormente por el primal

•  Si f(w*)=W(α*) respetándose las restricciones, entonces w* y α* son, respectivamente, las soluciones del primal y dual.




Condiciones de Karush-Kuhn-Tucker (KKT) •  Teorema. Dado el problema de optimización

primal planteado, si es convexo, las condiciones necesarias y suficientes para que w* sea óptimo es que exista α* tal que




Lectura de las condiciones KKT Los valores de las variables primales y duales que alcanzan los óptimos están relacionadas por las ecuaciones de las condiciones KKT

–  Las derivadas parciales de la lagrangiana respecto a las variables primarias han de ser cero

–  Condición complementaria: las restricciones activas, aquellas que valen exactamente cero, su multiplicador de Lagrange podrá ser mayor o igual que cero. Sin embargo, para las condiciones inactivas, las que valgan estrictamente menos que cero, el multiplicador asociado debe ser cero (dispersión de la solución)

–  Estos valores han de cumplir las restricciones del primal y el dual

Consecuencia (KKT). Se puede solucionar el problema primal a través de una solución del problema dual. Este punto de vista es a veces interesante cuando el problema dual es más fácil de resolver que el primal




dado que podemos cambiar esta versión directa por otra equivalente más operativa para calcular sus derivadas

Clasificación: problema primal




Clasificación: lagrangiana Todas las funciones que intervienen son convexas y diferenciables. Se puede aplicar las condiciones de KKT




Clasificación: problema dual




•  La solución w* es una combinación lineal de los ejemplos de entrenamiento

•  No intervienen todos (dispersión), sólo los que tienen un multiplicador de Lagrange distinto de cero (vectores soporte)

•  En el caso separable, los vectores soporte son los ejemplos que estén justo en el margen de cada clase (condición KKT)

•  La variable primal b no aparece en el problema dual, se debe calcular a partir de w*

Clasificación: análisis




•  Margen: Obtenemos la solución que, desde un punto de vista estructural, tiene menor posibilidad de cometer errores futuros

•  Convexidad: la solución se obtiene resolviendo un programa de optimización cuadrática, convexo, sin mínimos locales y resoluble en tiempo polinomial

•  Dualidad y kernels: el problema dual depende de productos escalares entre los ejemplos. Podremos sustituirlo por el producto escalar en un espacio de características mediante un kernel

•  Dispersión: la solución depende de los vectores soporte

Clasificación: conclusiones




Margen blando: primal




Margen blando: lagrangiana




Margen blando: dual




Regularización •  Las SVMs seleccionan la función que cumple la siguiente

condición:

•  El primero sumando representa la complejidad de la hipótesis elegida, se prefiere la más simple (Ockham)

•  El segundo sumando sirve para controlar el coste de la hipótesis elegida, medido sobre los datos de entrenamiento utilizados

•  La constante C es la que nos permite regular la solución de compromiso entre ambos términos, complejidad y coste

•  La determinación del valor adecuado para C en una aplicación real es quizás más difícil que decidir el kernel a emplear, ya que éste en muchos casos puede venir dado por los datos




Regularización (II)

más bajo intermedio más alto

valor de C




Regresión

Necesitamos una función de coste para el término regularizador




Regresión: problema primal

Necesitamos dos variables de holgura para cada ejemplo




Regresión: lagrangiana




Regresión: problema dual




Resumen •  Maximización del margen •  Problema de Optimización cuadrática:

°  convexidad °  no hay mínimos locales °  resoluble en tiempo polinomial °  sequiential minimal optimization (smo) para cjtos

grandes

•  Dualidad: permite el uso de kernels °  Podemos transformar el espacio de entrada original en

un espacio de mayor dimensión

•  Dispersión: sólo son necesarios los puntos cerca del margen (vectores soporte)

•  Las SVM se pueden emplear para: clasificación, regresión, clustering, aprendizaje de preferencias…

Documents

SISTEMAS INTELIGENTES - aic.uniovi.esaic.uniovi.es/ssii/SSII-T11-MetodosKernel-SVM.pdf · Centro de Inteligencia Artificia l Universidad de Oviedo Sistemas Inteligentes - T11: Métodos