Support Vector Machine (SVM)
TÉCNICAS ESTADÍSTICAS PARA EL APRENDIZAJE II
Máster Universitario en Estadística Computacional
y Ciencia de Datos para la Toma de Decisiones
Curso 2021/22
José Luis Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
Ejemplo del problema
Buscamos separar dos tipos de datos mediante un hiperplano, de tal
forma que unos ‘estén a un lado del hiperplano’ y otros al otro.
Además, queremos que la distancia de los puntos extremos de ambos
conjuntos al hiperplano esté balanceada. La cuestión es, ¿cuál es dicho
hiperplano?
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
Ejemplo del problema
De forma más formal: El Support Vector Machine (Vector de apoyo
de soporte) consiste en formular un hiperplano que separe de
forma óptima a los puntos de una clase de la de otra, de forma
que exista la máxima distancia o margen entre los puntos más
cercanos al mismo.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Dado que maximizar el margen, es
decir, max 2/||w||k es equivalente a
minimizar ||w||k, podemos definir el
problema de obtención del Vector
Soporte wx – b como el siguiente
problema de optimización:
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
Definición formal del problema
que es conocido como Generalized SVM. Obsérvese que
• yi es conocido, e indica la clase a la que pertenece cada
observación i (valores -1 o 1)
• xij, son conocidos y representan los valores de la matriz de
observaciones (i los individuos y j las variables)
• los w’s y la b son las incógnitas del problema cuyo valor
queremos conocer y que nos dan el hiperplano buscado
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
que es conocido como Generalized SVM. Obsérvese que
• yi es conocido, e indica la clase a la que pertenece cada
observación i (valores -1 o 1)
• xij, son conocidos y representan los valores de la matriz de
observaciones (i los individuos y j las variables)
Por tanto, la resolución de dicho problema nos proporcionará los
valores de wj y b, es decir, los valores que caracterizan el
hiperplano soporte buscado.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Dependiendo de la distancia o norma Lk empleada, la resolución
de dicho problema presentará mayor o menor dificultad,
utilizándose distintos métodos de resolución.
Si como norma se emplea L1, es decir, la distancia de Manhattan
o valor absoluto, el problema resultante es:
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Ejercicio-Ejemplo: la siguiente tabla presenta los datos relativo
a la edad y los salarios de los clientes de una empresa, así como
si le han comprado (compra=1) o no un relativo producto
(compra=0).
Plantea el problema, basado en la distancia de Manhattan, para
obtener la función discriminante SVM que diferenciaría entre los
clientes que compran y los que no compran.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Mediante determinadas transformaciones (wj = w+j - w-j) podemos
obtener un problema Programación Lineal:
que es lineal y por tanto resoluble utilizando el método Simplex.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Ejercicio-Ejemplo: la siguiente tabla presenta los datos relativo
a la edad y los salarios de los clientes de una empresa, así como
si le han comprado (compra=1) o no un relativo producto
(compra=0).
Plantea el problema, basado en la distancia de Manhattan y que
sea completamente lineal, para obtener la función discriminante
SVM que diferenciaría entre los clientes que compran y los que
no compran.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Si en cambio utilizásemos la norma L2, o distancia Euclidea,
resultaría el problema:
que ya no es lineal, empleándose entonces otros métodos para
su resolución como operadores de Lagrange, o incluso trucos
como el llamado truco del núcleo
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Ejercicio-Ejemplo: la siguiente tabla presenta los datos relativo
a la edad y los salarios de los clientes de una empresa, así como
si le han comprado (compra=1) o no un relativo producto
(compra=0).
Plantea el problema, basado en la distancia euclídea, para
obtener la función discriminante SVM que diferenciaría entre los
clientes que compran y los que no compran.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM con errores de clasificación
Dado que la clasificación normalmente no es perfecta, se han de
tener en cuenta los errores o el problema resultará infactible. Así,
la función objetivo pasa a ser de la forma:
Este modelo siempre es factible. Aquellos individuos cuyo εi
resultase no nulo, serían individuos erróneamente clasificados.
El parámetro c (coste) que multiplica el error es elegible por el
usuario, pudiendo realizarse varias pruebas para elegir el mejor.
SVM constituye un campo de investigación de innovación
continua.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM
Ejercicio-Ejemplo: la siguiente tabla presenta los datos relativo
a la edad y los salarios de los clientes de una empresa, así como
si le han comprado (compra=1) o no un relativo producto
(compra=0).
Plantea el problema, basado en la distancia de Manhattan, para
obtener la función discriminante SVM que diferenciaría entre los
clientes que compran y los que no compran.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM con más de dos categorías
En el caso de querer clasificar en k>2 categorías, precisaremos
obtener k-1 Hiperplanos Soporte, existiendo diversos métodos.
Uno de dichos métodos, el llamado uno frente al resto,
consistiría en utilizar k-1 clasificadores con valores 1 si el
individuo pertenece a un grupo determinado, y 0 si pertenece al
resto.
En caso de que el discriminador asigne un individuo a dos o más
grupos, decidirá el valor absoluto del discriminador más alto.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM con más de dos categorías
En el caso de querer clasificar en k>2 categorías, precisaremos
obtener k-1 Hiperplanos Soporte, existiendo diversos métodos.
Uno de dichos métodos, el llamado uno frente al resto,
consistiría en utilizar k-1 clasificadores con valores 1 si el
individuo pertenece a un grupo determinado, y 0 si pertenece al
resto.
En caso de que el discriminador asigne un individuo a dos o más
grupos, decidirá el valor absoluto del discriminador más alto.
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación
SVM con más de dos categorías
Ejemplo: si para clasificar en tres categorías, se han construido
dos con la siguiente codificación:
Obtén la asignación de los siguientes 5 individuos cuyos valores
en los clasificadores es:
José L. Sainz-Pardo – [Link]-pardo@[Link] Reglas de Asociación