Máquina de Soporte Vectorial SVM

Vladimir Naumovich Vapnik publica la primera versión de “Теория статистического обучения, Statistical Learning Theory” en 1.979, es la que muchos llaman el inico de las SVM (Support Vector Machines, Máquinas de Soporte Vectorial) que culmina con la publicación, junto con Corinna Cortés en 1.995, de “Support-Vector Networks”, que es la descripción de una máquina de aprendizaje estadístico para problemas de clasificación de dos grupos de datos. Vapnik dice en “Statistical Learning Theory” que fue R. A. Fisher quién sujirió, en 1.936, el primer algoritmo para el reconocimiento de patrones llamado “Discriminant analysis”.

Corinna Cortés
Cortés
Vladimir Naumovich Vapnik
Vapnik

 

Una máquina SVM es un algoritmo de aprendizaje automático supervisado que puede emplearse para fines de clasificación y regresión de dos grupos de datos. Comprende la máquina de soporte vectorial para la clasificación (SVC) y la máquina de soporte vectorial para la regresión (SVR).  Dado un conjunto de ejemplos de entrenamiento,  marcados como pertenecientes a una de dos categorías, el algoritmo de entrenamiento SVM construye un modelo que predice si un nuevo ejemplo cae en una categoría u otra.

 

Operativamente SVM se basa en la idea de encontrar la mejor línea, plano o hiperplano (según la dimensión) que divida un conjunto de datos en dos clases y para ello utiliza los siguientes conceptos:

 

  1. El hiperplano. Es una plano que separa y clasifica linealmente un conjunto de datos.
  2. Los vectores de apoyo. Son los puntos críticos de datos más cercanos a la línea del hiperplano y que al eliminarse alterarían la posición del hiperplano.
  3. El margen. Es la distancia entre el hiperplano y el dato más cercano de cualquiera de los conjuntos.
  4. Dimensión VC (Vapnik-Chervonekis). VC es el conjunto de funciones disponibles y la dimensión es la cantidad máxima de puntos que se pueden separar de todas las formas posibles mediante el conjunto VC. Cuanto mayor sea la dimensión, menor será el error del conjunto de entrenamiento y la confianza crecerá.
  5. Núcleo (Kernel). Es el conjunto de funciones matemáticas utilizadas para transformar los datos de entrada en la forma deseada. Ofrecen un puente entre la linealidad y la no linealidad de las SVM.  Su utilidad se ve claramente cuando los datos forman una forma curva y no habrá una línea / plano / hiperplano que separe completamente las dos clases.
    Representación datos de entrada 2D y transformados SVM
    Representación datos de entrada 2D y transformados

     

A pesar de las muchas ventajas de las SVM y de que son excelentes para conjuntos de datos pequeños, existe algún que otro problema. La problemática de este tipo de algoritmo reside en, cómo dividir las dos clases de datos y cómo encontrar la posición del hiperplano. Los datos se representan como puntos y los más distantes, del hiperplano, son los que han sido clasificados correctamente. Debemos elegir un hiperplano con el mayor margen entre el hiperplano y cualquier punto dentro del conjunto de entrenamiento, esto ofrece la mayor posibilidad de que los nuevos datos se clasifiquen rápida y correctamente.

 

 

Para encontrar un buen hiperplano candidato tenemos que resolver cómo obtener el margen máximo, este margen se obtiene con programación cuadrática (QP) que trae consigo un problema encubierto que es el del tamaño de la matriz QP. El tamaño de la matriz QP es directamente proporcional al número de puntos de entrenamiento, este es el “talón de Aquiles” de SVM  y provoca una carga computacional alta y que la complejidad en el aprendizaje aumente linealmente en función del aumento del número de muestras. El peor problema que nos podríamos encontrar sería el de tener tantos vectores de soporte como muestras en el conjunto de entrenamiento.

Representación de datos 3D con hiperplano
Representación de datos 3D con hiperplano SVM

 

Según la forma de la función de error, los modelos de SVM se pueden clasificar en:

  • Clasificación C-SVC
  • Clasificación nu-SVC
  • Clasificación LinearSVC
  • Regresión  epsilon-SVR
  • Regresión  nu-SVR
  • Regresión LinearSVR

 

 

 

 

 

 

 

 

 

 

Johan A. K. Suykens
Suykens
Joos Vandewalle
Vandewalle

LS-SVM ( Least squares support vector machines, Máquina de soporte vectorial de mínimos cuadrados). Es una versión de SVM basada en el método de mínimos cuadrados. Fue propuesta por Johan A. K. Suykens. y Joos Vandewalle en 1.998 en el artículo “Least squares support vector machine classifiers”. Las LS-SVM son preferibles para problemas a gran escala porque resuelve ecuaciones lineales en lugar de usar programación cuadrática que es el inconveniente de las SVM.

 

 

 

A continuación relacionamos algunas de las herramientas que facilitan en trabajo con las SVM:

 

Algoritmos y Herramientas para SVM
Año Acrónimo  Autor Comentario
2.017 UV BMRM Julien Prados Liibrería “Bundle Methods for Regularized Risk Minimization”. Incluye soluciones para: Predicción estructurada, SVM lineal, SVM multiclase, optimización f-beta, optimización ROC, regresión ordinal, regresión por cuantiles, regresión insensible a épsilon, media cuadrática, regresión logística, regresión por mínima desviación absoluta, …
2.012 UV BSVM BSVMChih-Wei Hsu, Chih-Jen Lin, K.M. Chung, W.C. Kao, T. Sun, C.P. Lee y otros Librería de código abierto para la solución de grandes problemas de clasificación y regresión que se apoya en LIBSVM y TRON. Los principales módulos son:

  • Clasificación multiclase One usando formulación restringida
  • Clasificación multiclase usando la formulación de Crammer y Singer.
  • Regresión utilizando formulación restringida
2.006 GEPSVM

Olvi L. MangasarianEdward W. Wild

Olvi L. Mangasarian y Edward W. Wild)

Algoritmo “Generalized Eigenvalue Proximal Support Vector Machines”
2.011 GEPSVR Reshma KhemchandaniAnuj KarpatneSuresh Chandra

Reshma Khemchandani,

Anuj Karpatne y Suresh Chandra

Algoritmo “Generalized Eigenvalue Proximal Support Vector Regression”
2.013 IGEPSVM

Yuan-Hai-ShaoNai-Yang-DengWei-Jie-Chen. Zhen-Wang

Yuan-Hai Shao, Nai-Yang Deng, Wei-Jie Chen y Zhen Wang

Algoritmo “Improved generalized eigenvalue proximal support vector machine”
2.013 UV LIBSVM

Chih-Jen LinChih-Jen Lin y Chih-chung chang

Librería de código abierto en C++ y Java. Dispone de diferentes modelos de SVM con distintos tipos de kernels. Posibilita el enlace con otros lenguajes de programación como: Python, R, Perl, Ruby,  etc. Soporta clasificación (C-SVC, nu-SVC), regresión (épsilon-SVR, nu-SVR) y distribución de la estimación.
2.012 UV mlpy

Davide Albanese , Roberto Visintainer , Stefano Merler , Samantha Riccadonna , Giuseppe Jurman , Cesare Furlanello

Librería “Machine Learning Python”, como su nombre indica está escrita en Python y es de libre disposición. En regresión utiliza: Mínimos cuadrados, Regresión de Ridge, SVR, etc. En Clasificación: Análisis discriminante lineal (LDA), perceptrón básico, red elástica, regresión logística, máquinas de vectores de apoyo (Kernel) (SVM), etc.
2.017 UV NBSVM

Sida I. Wang

Sida I.Wang y Christopher D. Manning

Algoritmo que combina el clasificador Naive Bayes con SVM. Lo hace a través de la multiplicación  de los elementos de los vectores de características por las proporciones de clase de los recuentos de registros NB. Dichos vectores se usan luego como entradas para el clasificador SVM. Existen múltiples herramientas de libre disposición.
Pegasos

Shai-Shalev-ShwartzYoram SingerNathan-Srebro

Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro y Andrew Cotter

Algoritmo “Primal Estimated sub-GrAdient SOlver” que reduce la cantidad de iteraciones necesarias para obtener una solución de precisión ϵ es O (1 /ϵ), donde cada iteración opera en un solo ejemplo de entrenamiento. Para un kernel lineal, el tiempo total de ejecución es O (d / (λϵ)), donde d es un límite en el número de características no cero en cada ejemplo y λ es el parámetro de regularización de SVM. Dado que el tiempo de ejecución no depende directamente del tamaño del conjunto de entrenamiento, el algoritmo es especialmente adecuado para aprender grandes conjuntos de datos.
PSVM

Edward Y. Chang, Kaihua Zhu, Hao Wang, Hongjie Bai, Jian Li, Zhihuan Qiu y Hang Cui

Algritmo “Parallelizing Support Vector Machines on Distributed Computers”

ReGEPSVM Panos M. PardalosM. R.Guarracino, Claudio Cifarelli, O. Seref y Panos M. Pardalos (2007) Algoritmo “Regularized GEPSVM”
ReGEPSVR Regularized Generalized Eigenvalue
Support Vector Regressor
RSVM

Yuh-Jye LeeOlvi L. Mangasarian

Yuh-Jye Lee y  Olvi L. Mangasarian

Algoritmo “Reduced Support Vector Machines” que reduce los tiempos de cómputo y el uso de memoria respecto de un SVM convencional que usa el conjunto de datos completo.
SSVM

Yuh-Jye LeeOlvi L. Mangasarian

Yuh-Jye Lee y  Olvi L. Mangasarian

Librería “Smooth Support Vector Machines” para clasificación de patrones con un núcleo completamente arbitrario. Utiliza una versión del algoritmo de Newton-Armijo.
SVMlight,
SVMstruct  SVMperf SVMrank
 

Thorsten Joachims

Librerias que implementan la máquina de Vapnik en lenguaje C,  para el reconocimiento de patrones, regresión y para aprendizaje de una función de clasificación. Es de uso libre para investigación. Los fuentes y ejecutables están disponibles para Linux, Windows y Mc.
TWSVM Jayadeva, Khemchandani and Chandra (2007) Algoritmo “Twin support vector machine”
UV:  Última Versión

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

trece + quince =