sistemas inteligentes - aic.uniovi.esaic.uniovi.es/ssii/ssii-t11-metodoskernel-svm.pdf · centro de...
TRANSCRIPT
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Í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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Kernels (II)
Representamos los datos mediante un matriz cuadrada donde cada elemento mide la similitud entre dos ejemplos
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Funciones kernel: idea
• Representar la similitud entre dos objetos Aproximación General
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Funciones Kernel (II) Si son kernels en entonces también son kernels
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Ejemplos de Funciones Kernel Kernel Lineal
Kernel Polinómico
Kernel Gaussiano Kernel string, kernel booleano,…
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Clasificación por mínima distancia
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Perceptrón (versión sin kernels)
No es kernelizable, no aparecen productos escalares
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Perceptrón (versión dual, kernelizable)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
El espacio de características (I)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
El espacio de características (II)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Ejemplo (I)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Ejemplo (II)
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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”
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
General/Específico: más gráficamente
Atributo 1
Atributo 2 Específica General
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Planteamiento
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
+ + +
+ +
+ + + +
_ _ _
_ _ _
_
_
_ _
+
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
+
Maximización del Margen
_
+ +
+
+ +
+ +
+ _ _
_ _
_ _
_
_
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
¿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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Maximizando el margen geométrico
+ _
+ +
+
+ +
+ +
+ _ _
_ _
_ _
_
_
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
• 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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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.
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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.
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
dado que podemos cambiar esta versión directa por otra equivalente más operativa para calcular sus derivadas
Clasificación: problema primal
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Clasificación: lagrangiana Todas las funciones que intervienen son convexas y diferenciables. Se puede aplicar las condiciones de KKT
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Clasificación: problema dual
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
• 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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
• 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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Margen blando: primal
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Margen blando: lagrangiana
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Margen blando: dual
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Regularización (II)
más bajo intermedio más alto
valor de C
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Regresión
Necesitamos una función de coste para el término regularizador
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Regresión: problema primal
Necesitamos dos variables de holgura para cada ejemplo
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Regresión: lagrangiana
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Regresión: problema dual
Centro de Inteligencia Artificial
Universidad de Oviedo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
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…