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”.

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.

   

    

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.

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

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.001	SSVM	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.
2.001	RSVM	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.
2.006	GEPSVM	Olvi L. Mangasarian y Edward W. Wild)	Algoritmo “Generalized Eigenvalue Proximal Support Vector Machines”
2.007	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.
2.007	ReGEPSVM	M. R.Guarracino, Claudio Cifarelli, O. Seref y Panos M. Pardalos	Algoritmo “Regularized GEPSVM”
2.007	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”
2.007	TWSVM	Jayadeva, Khemchandani y Chandra	Algoritmo “Twin support vector machine”
2.011	Pegasos	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.
2.011	GEPSVR	Reshma Khemchandani, Anuj Karpatne y Suresh Chandra	Algoritmo “Generalized Eigenvalue Proximal Support Vector Regression”
2.012 UV	BSVM	Chih-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.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.013	IGEPSVM	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 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.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.017 UV	NBSVM	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.
UV:  Última Versión