Download sistemas inteligentes - Centro de Inteligencia Artificial

Universidad
de Oviedo
Centro de
Inteligencia Artificial
SISTEMAS INTELIGENTES
T11: Métodos Kernel:
Máquinas de vectores soporte
{jdiez, juanjo} @ aic.uniovi.es
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Í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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Kernels (II)
Representamos los datos mediante un
matriz cuadrada donde cada elemento
mide la similitud entre dos ejemplos
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Kernels (III)
Atributos
Atr-1
…
Clase(opcional)
ejemplo 1
clase ej-1
…
…
ejemplo n
clase ej-n
Ej 1
Ej 1 k(x1,x1)
K
Atr-n
…
Ej j
…
Ej n
k(x1,xj)
k(x1,xn)
k(xi,xj)
k(xi,xn)
k(xn,xj)
k(xn,xn)
…
Ej i k(xi,x1)
…
Ej n k(xn,x1)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Funciones kernel: idea
•  Representar la similitud entre dos objetos
Aproximación
General
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Producto escalar
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Funciones Kernel (II)
Si
son kernels en
entonces también son kernels
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Ejemplos de Funciones Kernel
Kernel Lineal
Kernel Polinómico
Kernel Gaussiano
Kernel string, kernel booleano,…
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación por mínima distancia
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Perceptrón (versión sin kernels)
No es kernelizable, no aparecen productos escalares
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Perceptrón (versión dual, kernelizable)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
El espacio de características (I)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
El espacio de características (II)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Ejemplo (I)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Ejemplo (II)
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Máquinas de Vectores Soporte
“No hay nada más práctico que una buena teoría”
•  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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
General/Específico: más gráficamente
Atributo 2
Específica
General
Atributo 1
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Planteamiento
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
+ + +
+ +
+ + +
_ _
+
_
_
_
+
_
_
_
_ _
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Maximización del Margen
+
+ +
+ +
+ +
+
+
_
_
_
_
_
_
_
_
_
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
¿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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Maximizando el margen geométrico
+
+ +
+ +
+ + +
+
_
_ _
_
_
_
_
_
_
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
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
•  Programación cuadrática:
lineales
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
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,
global
para cualquier
v y por tanto w* mínimo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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.
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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.
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación: problema primal
dado que
podemos cambiar esta versión directa
por otra equivalente más operativa para calcular sus derivadas
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación: lagrangiana
Todas las funciones que intervienen son convexas y
diferenciables. Se puede aplicar las condiciones de KKT
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación: problema dual
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación: análisis
•  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*
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Clasificación: conclusiones
•  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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Margen blando: primal
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Margen blando: lagrangiana
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Margen blando: dual
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Regularización (II)
más bajo
intermedio
valor de C
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
más alto
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Regresión
Necesitamos una función de coste para el término regularizador
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Regresión: problema primal
Necesitamos dos variables
de holgura para cada
ejemplo
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Regresión: lagrangiana
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Regresión: problema dual
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte
Universidad
de Oviedo
Centro de
Inteligencia Artificial
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…
Sistemas Inteligentes - T11: Métodos Kernel: Máquinas de vectores soporte