Máquina de vectores de soporte

En aprendizaje automático , las máquinas de vectores de soporte ( SVMs , también redes de vectores de soporte ^[1] ) son modelos supervisados ​​de margen máximo con algoritmos de aprendizaje asociados que analizan datos para clasificación y análisis de regresión . Desarrolladas en AT&T Bell Laboratories ^{[1] [2]} , las SVM son uno de los modelos más estudiados, y se basan en marcos de aprendizaje estadístico de la teoría VC propuesta por Vapnik (1982, 1995) y Chervonenkis (1974).

Además de realizar una clasificación lineal , las SVM pueden realizar de manera eficiente una clasificación no lineal utilizando el truco del núcleo , representando los datos solo a través de un conjunto de comparaciones de similitud por pares entre los puntos de datos originales utilizando una función del núcleo, que los transforma en coordenadas en un espacio de características de dimensión superior . Por lo tanto, las SVM utilizan el truco del núcleo para mapear implícitamente sus entradas en espacios de características de alta dimensión, donde se puede realizar una clasificación lineal. ^[3] Al ser modelos de margen máximo, las SVM son resistentes a datos ruidosos (por ejemplo, ejemplos mal clasificados). Las SVM también se pueden utilizar para tareas de regresión , donde el objetivo se vuelve sensible.${\displaystyle \epsilon }$

El algoritmo de agrupamiento de vectores de soporte ^[4] , creado por Hava Siegelmann y Vladimir Vapnik , aplica las estadísticas de los vectores de soporte, desarrolladas en el algoritmo de máquinas de vectores de soporte, para categorizar datos no etiquetados. ^{[ cita requerida ]} Estos conjuntos de datos requieren enfoques de aprendizaje no supervisado , que intentan encontrar la agrupación natural de los datos en grupos y luego mapear nuevos datos de acuerdo con estas agrupaciones.

La popularidad de los SVM se debe probablemente a su facilidad para el análisis teórico y a su flexibilidad para ser aplicados a una amplia variedad de tareas, incluidos los problemas de predicción estructurada . No está claro que los SVM tengan un mejor rendimiento predictivo que otros modelos lineales, como la regresión logística y la regresión lineal . ^{[ cita requerida ]}

La clasificación de datos es una tarea común en el aprendizaje automático . Supongamos que algunos puntos de datos dados pertenecen a una de dos clases, y el objetivo es decidir en qué clase estará un nuevo punto de datos . En el caso de las máquinas de vectores de soporte, un punto de datos se ve como un vector dimensional (una lista de números), y queremos saber si podemos separar dichos puntos con un hiperplano dimensional . Esto se llama clasificador lineal . Hay muchos hiperplanos que podrían clasificar los datos. Una opción razonable como el mejor hiperplano es el que representa la mayor separación, o margen , entre las dos clases. Por lo tanto, elegimos el hiperplano de modo que se maximice la distancia desde él hasta el punto de datos más cercano en cada lado. Si existe un hiperplano de este tipo, se lo conoce como hiperplano de margen máximo y el clasificador lineal que define se conoce como clasificador de margen máximo ; o equivalentemente, el perceptrón de estabilidad óptima . ^{[ cita requerida ]}${\displaystyle p}$${\displaystyle p}$${\displaystyle (p-1)}$

Más formalmente, una máquina de vectores de soporte construye un hiperplano o un conjunto de hiperplanos en un espacio de dimensión alta o infinita, que se puede usar para clasificación , regresión u otras tareas como la detección de valores atípicos. ^[5] Intuitivamente, una buena separación se logra mediante el hiperplano que tiene la mayor distancia al punto de datos de entrenamiento más cercano de cualquier clase (el llamado margen funcional), ya que, en general, cuanto mayor sea el margen, menor será el error de generalización del clasificador. ^[6] Un error de generalización menor significa que es menos probable que el implementador experimente sobreajuste .

Aunque el problema original puede plantearse en un espacio de dimensión finita, a menudo sucede que los conjuntos a discriminar no son linealmente separables en ese espacio. Por esta razón, se propuso ^[7] que el espacio de dimensión finita original se mapeara en un espacio de dimensión mucho mayor, presumiblemente haciendo más fácil la separación en ese espacio. Para mantener la carga computacional razonable, las asignaciones utilizadas por los esquemas SVM están diseñadas para asegurar que los productos escalares de pares de vectores de datos de entrada se puedan calcular fácilmente en términos de las variables en el espacio original, definiéndolos en términos de una función kernel seleccionada para adaptarse al problema. ^[8] Los hiperplanos en el espacio de dimensión mayor se definen como el conjunto de puntos cuyo producto escalar con un vector en ese espacio es constante, donde dicho conjunto de vectores es un conjunto ortogonal (y por lo tanto mínimo) de vectores que define un hiperplano. Los vectores que definen los hiperplanos pueden elegirse para que sean combinaciones lineales con parámetros de imágenes de vectores de características que aparecen en la base de datos. Con esta elección de un hiperplano, los puntos en el espacio de características que se mapean en el hiperplano se definen por la relación Nótese que si se vuelve pequeño a medida que se aleja de , cada término en la suma mide el grado de cercanía del punto de prueba al punto de base de datos correspondiente . De esta manera, la suma de kernels anterior se puede utilizar para medir la cercanía relativa de cada punto de prueba a los puntos de datos originados en uno u otro de los conjuntos a discriminar. Nótese el hecho de que el conjunto de puntos mapeados en cualquier hiperplano puede ser bastante convolucionado como resultado, permitiendo una discriminación mucho más compleja entre conjuntos que no son convexos en absoluto en el espacio original.${\displaystyle k(x,y)}$${\displaystyle \alpha _{i}}$ ${\displaystyle x_{i}}$${\displaystyle x}$${\displaystyle \textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.}$${\displaystyle k(x,y)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x_{i}}$${\displaystyle x}$

Las SVM se pueden utilizar para resolver diversos problemas del mundo real:

• Las SVM son útiles en la categorización de texto e hipertexto , ya que su aplicación puede reducir significativamente la necesidad de instancias de entrenamiento etiquetadas tanto en la configuración inductiva como transductiva estándar. ^[9] Algunos métodos para el análisis semántico superficial se basan en máquinas de vectores de soporte. ^[10]
• La clasificación de imágenes también se puede realizar mediante máquinas de clasificación de imágenes. Los resultados experimentales muestran que las máquinas de clasificación de imágenes logran una precisión de búsqueda significativamente mayor que los esquemas de refinamiento de consultas tradicionales después de solo tres o cuatro rondas de retroalimentación de relevancia. Esto también es cierto para los sistemas de segmentación de imágenes , incluidos aquellos que utilizan una versión modificada de la máquina de clasificación de imágenes que utiliza el enfoque privilegiado sugerido por Vapnik. ^{[11] [12]}
• Clasificación de datos satelitales como datos SAR utilizando SVM supervisado. ^[13]
• Los caracteres escritos a mano se pueden reconocer utilizando SVM. ^{[14] [15]}
• El algoritmo SVM se ha aplicado ampliamente en las ciencias biológicas y en otras ciencias. Se ha utilizado para clasificar proteínas con hasta el 90% de los compuestos clasificados correctamente. Se han sugerido pruebas de permutación basadas en pesos SVM como un mecanismo para la interpretación de los modelos SVM. ^{[16] [17]} Los pesos de las máquinas de vectores de soporte también se han utilizado para interpretar modelos SVM en el pasado. ^[18] La interpretación post hoc de los modelos de máquinas de vectores de soporte para identificar las características utilizadas por el modelo para hacer predicciones es un área de investigación relativamente nueva con especial importancia en las ciencias biológicas.

El algoritmo SVM original fue inventado por Vladimir N. Vapnik y Alexey Ya. Chervonenkis en 1964. ^{[ cita requerida ]} En 1992, Bernhard Boser, Isabelle Guyon y Vladimir Vapnik sugirieron una forma de crear clasificadores no lineales aplicando el truco del núcleo a hiperplanos de margen máximo. ^[7] La ​​encarnación de "margen suave", como se usa comúnmente en los paquetes de software, fue propuesta por Corinna Cortes y Vapnik en 1993 y publicada en 1995. ^[1]

Se nos proporciona un conjunto de datos de entrenamiento de puntos de la forma donde son 1 o −1, cada uno indicando la clase a la que pertenece el punto. Cada uno es un vector real de dimensión . Queremos encontrar el "hiperplano de margen máximo" que divide el grupo de puntos para el cual del grupo de puntos para el cual , que se define de modo que se maximice la distancia entre el hiperplano y el punto más cercano de cualquiera de los grupos.${\displaystyle n}$$${\displaystyle (\mathbf {x} _{1},y_{1}),\ldots ,(\mathbf {x} _{n},y_{n}),}$$${\displaystyle y_{i}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle p}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle y_{i}=1}$${\displaystyle y_{i}=-1}$${\displaystyle \mathbf {x} _{i}}$

Cualquier hiperplano puede escribirse como el conjunto de puntos que satisfacen donde es el vector normal (no necesariamente normalizado) al hiperplano. Esto es muy parecido a la forma normal de Hesse , excepto que no es necesariamente un vector unitario. El parámetro determina el desplazamiento del hiperplano desde el origen a lo largo del vector normal .${\displaystyle \mathbf {x} }$$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=0,}$$${\displaystyle \mathbf {w} }$${\displaystyle \mathbf {w} }$${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$${\displaystyle \mathbf {w} }$

Advertencia: la mayor parte de la literatura sobre el tema define el sesgo de manera que$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} +b=0.}$$

Si los datos de entrenamiento son linealmente separables , podemos seleccionar dos hiperplanos paralelos que separen las dos clases de datos, de modo que la distancia entre ellos sea lo más grande posible. La región delimitada por estos dos hiperplanos se denomina "margen", y el hiperplano de margen máximo es el hiperplano que se encuentra a medio camino entre ellos. Con un conjunto de datos normalizado o estandarizado, estos hiperplanos se pueden describir mediante las ecuaciones

${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=1}$(todo lo que se encuentre en este límite o por encima de él es de una clase, con etiqueta 1)

y

${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=-1}$(todo lo que esté en este límite o por debajo de él es de la otra clase, con etiqueta −1).

Geométricamente, la distancia entre estos dos hiperplanos es , ^[19] por lo que para maximizar la distancia entre los planos queremos minimizar . La distancia se calcula utilizando la ecuación de la distancia de un punto a un plano . También tenemos que evitar que los puntos de datos caigan en el margen, agregamos la siguiente restricción: para cada uno o Estas restricciones establecen que cada punto de datos debe estar en el lado correcto del margen.${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$${\displaystyle \|\mathbf {w} \|}$${\displaystyle i}$$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\geq 1\,,{\text{ if }}y_{i}=1,}$$$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\leq -1\,,{\text{ if }}y_{i}=-1.}$$

Esto se puede reescribir como

$${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.}$$

( 1 )

Podemos juntar todo esto para obtener el problema de optimización:

${\displaystyle {\begin{aligned}&{\underset {\mathbf {w} ,\;b}{\operatorname {minimize} }}&&{\frac {1}{2}}\|\mathbf {w} \|^{2}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1\quad \forall i\in \{1,\dots ,n\}\end{aligned}}}$

Los y que resuelven este problema determinan el clasificador final, , donde es la función de signo .${\displaystyle \mathbf {w} }$${\displaystyle b}$${\displaystyle \mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)}$${\displaystyle \operatorname {sgn}(\cdot )}$

Una consecuencia importante de esta descripción geométrica es que el hiperplano de margen máximo está completamente determinado por aquellos que se encuentran más cerca de él (explicado más adelante). Estos se denominan vectores de soporte .${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{i}}$

Para ampliar SVM a casos en los que los datos no son linealmente separables, la función de pérdida de bisagra es útil.$${\displaystyle \max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right).}$$

Tenga en cuenta que es el i -ésimo objetivo (es decir, en este caso, 1 o −1), y es la i -ésima salida.${\displaystyle y_{i}}$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b}$

Esta función es cero si se cumple la restricción en (1) , es decir, si se encuentra en el lado correcto del margen. Para los datos que se encuentran en el lado incorrecto del margen, el valor de la función es proporcional a la distancia desde el margen.${\displaystyle \mathbf {x} _{i}}$

El objetivo de la optimización es entonces minimizar:

$${\displaystyle \lVert \mathbf {w} \rVert ^{2}+C\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right],}$$

donde el parámetro determina la compensación entre aumentar el tamaño del margen y garantizar que se encuentre en el lado correcto del margen (nótese que podemos agregar un peso a cualquiera de los términos en la ecuación anterior). Al deconstruir la pérdida de la bisagra, este problema de optimización se puede simplificar de la siguiente manera:${\displaystyle C>0}$${\displaystyle \mathbf {x} _{i}}$

$${\displaystyle {\begin{aligned}&{\underset {\mathbf {w} ,\;b,\;\mathbf {\zeta } }{\operatorname {minimize} }}&&\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{n}\zeta _{i}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1-\zeta _{i},\quad \zeta _{i}\geq 0\quad \forall i\in \{1,\dots ,n\}\end{aligned}}}$$

Por lo tanto, para valores grandes de , se comportará de manera similar al SVM de margen duro, si los datos de entrada son clasificables linealmente, pero aún aprenderá si una regla de clasificación es viable o no.${\displaystyle C}$

El algoritmo original de hiperplano de margen máximo propuesto por Vapnik en 1963 construyó un clasificador lineal . Sin embargo, en 1992, Bernhard Boser, Isabelle Guyon y Vladimir Vapnik sugirieron una forma de crear clasificadores no lineales aplicando el truco del núcleo (originalmente propuesto por Aizerman et al. ^[20] ) a hiperplanos de margen máximo. ^[7] El truco del núcleo, donde los productos escalares se reemplazan por núcleos, se deriva fácilmente en la representación dual del problema SVM. Esto permite que el algoritmo ajuste el hiperplano de margen máximo en un espacio de características transformado . La transformación puede ser no lineal y el espacio transformado de alta dimensión; aunque el clasificador es un hiperplano en el espacio de características transformado, puede ser no lineal en el espacio de entrada original.

Cabe destacar que trabajar en un espacio de características de mayor dimensión aumenta el error de generalización de las máquinas de vectores de soporte, aunque dadas suficientes muestras el algoritmo aún funciona bien. ^[21]

Algunos núcleos comunes incluyen:

• Polinomio (homogéneo) : . En particular, cuando , se convierte en el núcleo lineal.${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j})^{d}}$${\displaystyle d=1}$
• Polinomio (no homogéneo): .${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j}+r)^{d}}$
• Función de base radial gaussiana : para . A veces se parametriza utilizando .${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\exp \left(-\gamma \left\|\mathbf {x} _{i}-\mathbf {x} _{j}\right\|^{2}\right)}$${\displaystyle \gamma >0}$${\displaystyle \gamma =1/(2\sigma ^{2})}$
• Función sigmoidea ( tangente hiperbólica ): para algunos (no todos) y .${\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x} _{i}\cdot \mathbf {x} _{j}+c)}$${\displaystyle \kappa >0}$${\displaystyle c<0}$

El núcleo está relacionado con la transformación mediante la ecuación . El valor w también está en el espacio transformado, con . Los productos escalares con w para la clasificación se pueden calcular nuevamente mediante el truco del núcleo, es decir .${\displaystyle \varphi (\mathbf {x} _{i})}$${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x_{j}} )}$${\textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i})}$${\textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}$

Calcular el clasificador SVM (de margen suave) equivale a minimizar una expresión de la forma

$${\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.}$$

( 2 )

Nos centraremos en el clasificador de margen blando, ya que, como se ha señalado anteriormente, la elección de un valor suficientemente pequeño para da como resultado el clasificador de margen duro para datos de entrada clasificables linealmente. El enfoque clásico, que implica reducir (2) a un problema de programación cuadrática , se detalla a continuación. A continuación, se analizarán enfoques más recientes, como el descenso por subgradiente y el descenso por coordenadas.${\displaystyle \lambda }$

La minimización de (2) se puede reescribir como un problema de optimización restringida con una función objetivo diferenciable de la siguiente manera.

Para cada uno introducimos una variable . Nótese que es el número no negativo más pequeño que satisface${\displaystyle i\in \{1,\,\ldots ,\,n\}}$${\displaystyle \zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)}$${\displaystyle \zeta _{i}}$${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}.}$

Por lo tanto, podemos reescribir el problema de optimización de la siguiente manera

$${\displaystyle {\begin{aligned}&{\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|\mathbf {w} \|^{2}\\[0.5ex]&{\text{subject to }}y_{i}\left(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\right)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.\end{aligned}}}$$

Esto se llama el problema primal .

Al resolver el dual lagrangiano del problema anterior, se obtiene el problema simplificado

$${\displaystyle {\begin{aligned}&{\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\mathbf {x} _{i}^{\mathsf {T}}\mathbf {x} _{j})y_{j}c_{j},\\&{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}}$$

Esto se denomina problema dual . Dado que el problema de maximización dual es una función cuadrática sujeta a restricciones lineales, se puede resolver de manera eficiente mediante algoritmos de programación cuadrática .${\displaystyle c_{i}}$

Aquí, las variables se definen de tal manera que${\displaystyle c_{i}}$

$${\displaystyle \mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\mathbf {x} _{i}.}$$

Además, exactamente cuando se encuentra en el lado correcto del margen y cuando se encuentra en el límite del margen, se deduce que se puede escribir como una combinación lineal de los vectores de soporte.${\displaystyle c_{i}=0}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle 0<c_{i}<(2n\lambda )^{-1}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {w} }$

El desplazamiento, , se puede recuperar encontrando un en el límite del margen y resolviendo${\displaystyle b}$${\displaystyle \mathbf {x} _{i}}$$${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-y_{i}.}$$

(Tenga en cuenta que desde .)${\displaystyle y_{i}^{-1}=y_{i}}$${\displaystyle y_{i}=\pm 1}$

Supongamos ahora que queremos aprender una regla de clasificación no lineal que corresponde a una regla de clasificación lineal para los puntos de datos transformados. Además, se nos da una función kernel que satisface .${\displaystyle \varphi (\mathbf {x} _{i}).}$${\displaystyle k}$${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})}$

Sabemos que el vector de clasificación en el espacio transformado satisface${\displaystyle \mathbf {w} }$

$${\displaystyle \mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\varphi (\mathbf {x} _{i}),}$$

donde, se obtienen al resolver el problema de optimización${\displaystyle c_{i}}$

$${\displaystyle {\begin{aligned}{\text{maximize}}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k(\mathbf {x} _{i},\mathbf {x} _{j})y_{j}c_{j}\\{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}&=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}}$$

Los coeficientes se pueden resolver utilizando programación cuadrática, como antes. Nuevamente, podemos encontrar un índice tal que , de modo que se encuentre en el límite del margen en el espacio transformado, y luego resolver${\displaystyle c_{i}}$${\displaystyle i}$${\displaystyle 0<c_{i}<(2n\lambda )^{-1}}$${\displaystyle \varphi (\mathbf {x} _{i})}$

$${\displaystyle {\begin{aligned}b=\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {x} _{i})-y_{i}&=\left[\sum _{j=1}^{n}c_{j}y_{j}\varphi (\mathbf {x} _{j})\cdot \varphi (\mathbf {x} _{i})\right]-y_{i}\\&=\left[\sum _{j=1}^{n}c_{j}y_{j}k(\mathbf {x} _{j},\mathbf {x} _{i})\right]-y_{i}.\end{aligned}}}$$

Finalmente,

$${\displaystyle \mathbf {z} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {z} )-b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k(\mathbf {x} _{i},\mathbf {z} )\right]-b\right).}$$

Los algoritmos recientes para encontrar el clasificador SVM incluyen el descenso por subgradiente y el descenso por coordenadas. Ambas técnicas han demostrado ofrecer ventajas significativas sobre el enfoque tradicional cuando se trabaja con conjuntos de datos grandes y dispersos: los métodos por subgradiente son especialmente eficientes cuando hay muchos ejemplos de entrenamiento y el descenso por coordenadas cuando la dimensión del espacio de características es alta.

Los algoritmos de descenso de subgradiente para el SVM funcionan directamente con la expresión

$${\displaystyle f(\mathbf {w} ,b)=\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.}$$

Nótese que es una función convexa de y . Como tal, los métodos tradicionales de descenso de gradiente (o SGD ) se pueden adaptar, donde en lugar de dar un paso en la dirección del gradiente de la función, se da un paso en la dirección de un vector seleccionado del subgradiente de la función . Este enfoque tiene la ventaja de que, para ciertas implementaciones, el número de iteraciones no escala con , el número de puntos de datos. ^[22]${\displaystyle f}$${\displaystyle \mathbf {w} }$${\displaystyle b}$${\displaystyle n}$

Los algoritmos de descenso de coordenadas para el SVM funcionan a partir del problema dual

$${\displaystyle {\begin{aligned}&{\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},\\&{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}}$$

Para cada , iterativamente, el coeficiente se ajusta en la dirección de . Luego, el vector de coeficientes resultante se proyecta sobre el vector de coeficientes más cercano que satisface las restricciones dadas. (Normalmente se utilizan distancias euclidianas). Luego, el proceso se repite hasta que se obtiene un vector de coeficientes casi óptimo. El algoritmo resultante es extremadamente rápido en la práctica, aunque se han demostrado pocas garantías de rendimiento. ^[23]${\displaystyle i\in \{1,\,\ldots ,\,n\}}$${\displaystyle c_{i}}$${\displaystyle \partial f/\partial c_{i}}$${\displaystyle (c_{1}',\,\ldots ,\,c_{n}')}$

La máquina de vectores de soporte de margen suave descrita anteriormente es un ejemplo de un algoritmo de minimización de riesgo empírico (ERM) para la pérdida de bisagra . Vistas de esta manera, las máquinas de vectores de soporte pertenecen a una clase natural de algoritmos para la inferencia estadística, y muchas de sus características únicas se deben al comportamiento de la pérdida de bisagra. Esta perspectiva puede proporcionar una mayor comprensión de cómo y por qué funcionan las máquinas de vectores de soporte, y nos permite analizar mejor sus propiedades estadísticas.

En el aprendizaje supervisado, se proporciona un conjunto de ejemplos de entrenamiento con etiquetas , y se desea predecir dado . Para ello, se formula una hipótesis , , tal que es una aproximación "buena" de . Una aproximación "buena" se define habitualmente con la ayuda de una función de pérdida , , que caracteriza lo mala que es una predicción de . Entonces nos gustaría elegir una hipótesis que minimice el riesgo esperado :${\displaystyle X_{1}\ldots X_{n}}$${\displaystyle y_{1}\ldots y_{n}}$${\displaystyle y_{n+1}}$${\displaystyle X_{n+1}}$${\displaystyle f}$${\displaystyle f(X_{n+1})}$${\displaystyle y_{n+1}}$ ${\displaystyle \ell (y,z)}$${\displaystyle z}$${\displaystyle y}$

$${\displaystyle \varepsilon (f)=\mathbb {E} \left[\ell (y_{n+1},f(X_{n+1}))\right].}$$

En la mayoría de los casos, no conocemos la distribución conjunta de los riesgos empíricos. En estos casos, una estrategia habitual es elegir la hipótesis que minimice el riesgo empírico:${\displaystyle X_{n+1},\,y_{n+1}}$

$${\displaystyle {\hat {\varepsilon }}(f)={\frac {1}{n}}\sum _{k=1}^{n}\ell (y_{k},f(X_{k})).}$$

Bajo ciertas suposiciones sobre la secuencia de variables aleatorias (por ejemplo, que se generan mediante un proceso de Markov finito), si el conjunto de hipótesis que se considera es lo suficientemente pequeño, el minimizador del riesgo empírico se aproximará mucho al minimizador del riesgo esperado a medida que aumenta. Este enfoque se denomina minimización del riesgo empírico o ERM.${\displaystyle X_{k},\,y_{k}}$${\displaystyle n}$

Para que el problema de minimización tenga una solución bien definida, tenemos que poner restricciones al conjunto de hipótesis que se están considerando. Si es un espacio normalizado (como es el caso de SVM), una técnica particularmente eficaz es considerar solo aquellas hipótesis para las que . Esto es equivalente a imponer una penalización de regularización y resolver el nuevo problema de optimización.${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle f}$${\displaystyle \lVert f\rVert _{\mathcal {H}}<k}$ ${\displaystyle {\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}}$

$${\displaystyle {\hat {f}}=\mathrm {arg} \min _{f\in {\mathcal {H}}}{\hat {\varepsilon }}(f)+{\mathcal {R}}(f).}$$

Este enfoque se denomina regularización de Tikhonov .

De manera más general, puede ser alguna medida de la complejidad de la hipótesis , de modo que se prefieren las hipótesis más simples.${\displaystyle {\mathcal {R}}(f)}$${\displaystyle f}$

Recuerde que el clasificador SVM (de margen suave) se elige para minimizar la siguiente expresión:${\displaystyle {\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{\mathsf {T}}\mathbf {x} -b)}$

$${\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.}$$

A la luz de la discusión anterior, vemos que la técnica SVM es equivalente a la minimización de riesgo empírico con regularización de Tikhonov, donde en este caso la función de pérdida es la pérdida de bisagra.

$${\displaystyle \ell (y,z)=\max \left(0,1-yz\right).}$$

Desde esta perspectiva, SVM está estrechamente relacionado con otros algoritmos de clasificación fundamentales , como los mínimos cuadrados regularizados y la regresión logística . La diferencia entre los tres radica en la elección de la función de pérdida: los mínimos cuadrados regularizados equivalen a la minimización del riesgo empírico con la pérdida al cuadrado , ; la regresión logística emplea la pérdida logarítmica ,${\displaystyle \ell _{sq}(y,z)=(y-z)^{2}}$

$${\displaystyle \ell _{\log }(y,z)=\ln(1+e^{-yz}).}$$

La diferencia entre la pérdida de bisagra y estas otras funciones de pérdida se expresa mejor en términos de funciones objetivo: la función que minimiza el riesgo esperado para un par dado de variables aleatorias .${\displaystyle X,\,y}$

En particular, denotemos condicional al evento de que . En el contexto de la clasificación, tenemos:${\displaystyle y_{x}}$${\displaystyle y}$${\displaystyle X=x}$

$${\displaystyle y_{x}={\begin{cases}1&{\text{with probability }}p_{x}\\-1&{\text{with probability }}1-p_{x}\end{cases}}}$$

El clasificador óptimo es por tanto:

$${\displaystyle f^{*}(x)={\begin{cases}1&{\text{if }}p_{x}\geq 1/2\\-1&{\text{otherwise}}\end{cases}}}$$

Para la pérdida al cuadrado, la función objetivo es la función de expectativa condicional, ; para la pérdida logística, es la función logit, . Si bien ambas funciones objetivo producen el clasificador correcto, como , nos brindan más información de la que necesitamos. De hecho, nos brindan suficiente información para describir completamente la distribución de .${\displaystyle f_{sq}(x)=\mathbb {E} \left[y_{x}\right]}$${\displaystyle f_{\log }(x)=\ln \left(p_{x}/({1-p_{x}})\right)}$${\displaystyle \operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}}$${\displaystyle y_{x}}$

Por otra parte, se puede comprobar que la función objetivo para la pérdida de bisagra es exactamente . Por lo tanto, en un espacio de hipótesis suficientemente rico (o equivalentemente, para un núcleo elegido adecuadamente), el clasificador SVM convergerá a la función más simple (en términos de ) que clasifique correctamente los datos. Esto extiende la interpretación geométrica de SVM: para la clasificación lineal, el riesgo empírico se minimiza con cualquier función cuyos márgenes se encuentren entre los vectores de soporte, y el más simple de estos es el clasificador de margen máximo. ^[24]${\displaystyle f^{*}}$${\displaystyle {\mathcal {R}}}$

Los SVM pertenecen a una familia de clasificadores lineales generalizados y pueden interpretarse como una extensión del perceptrón . ^[25] También pueden considerarse un caso especial de regularización de Tikhonov . Una propiedad especial es que minimizan simultáneamente el error de clasificación empírico y maximizan el margen geométrico ; por lo tanto, también se conocen como clasificadores de margen máximo .

Meyer, Leisch y Hornik realizaron una comparación del SVM con otros clasificadores. ^[26]

La eficacia de SVM depende de la selección del kernel, los parámetros del kernel y el parámetro de margen suave . Una opción común es un kernel gaussiano, que tiene un único parámetro . La mejor combinación de y a menudo se selecciona mediante una búsqueda en cuadrícula con secuencias de y que crecen exponencialmente , por ejemplo, ; . Normalmente, cada combinación de opciones de parámetros se comprueba mediante validación cruzada , y se eligen los parámetros con la mejor precisión de validación cruzada. Alternativamente, se puede utilizar el trabajo reciente en optimización bayesiana para seleccionar y , que a menudo requiere la evaluación de muchas menos combinaciones de parámetros que la búsqueda en cuadrícula. El modelo final, que se utiliza para probar y clasificar nuevos datos, se entrena luego en todo el conjunto de entrenamiento utilizando los parámetros seleccionados. ^[27]${\displaystyle \lambda }$${\displaystyle \gamma }$${\displaystyle \lambda }$${\displaystyle \gamma }$${\displaystyle \lambda }$${\displaystyle \gamma }$${\displaystyle \lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}}$${\displaystyle \gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}}$${\displaystyle \lambda }$${\displaystyle \gamma }$

Las posibles desventajas del SVM incluyen los siguientes aspectos:

• Requiere etiquetado completo de los datos de entrada
• Probabilidades de pertenencia a clases no calibradas : SVM se deriva de la teoría de Vapnik, que evita estimar probabilidades en datos finitos
• El SVM solo es directamente aplicable a tareas de dos clases. Por lo tanto, se deben aplicar algoritmos que reduzcan la tarea multiclase a varios problemas binarios; consulte la sección SVM multiclase.
• Los parámetros de un modelo resuelto son difíciles de interpretar.

El SVM multiclase tiene como objetivo asignar etiquetas a instancias mediante el uso de máquinas de vectores de soporte, donde las etiquetas se extraen de un conjunto finito de varios elementos.

El enfoque dominante para hacerlo es reducir el problema multiclase único a múltiples problemas de clasificación binaria . ^[28] Los métodos comunes para dicha reducción incluyen: ^{[28] [29]}

• Construcción de clasificadores binarios que distinguen entre una de las etiquetas y el resto ( uno contra todos ) o entre cada par de clases ( uno contra uno ). La clasificación de nuevas instancias para el caso de uno contra todos se realiza mediante una estrategia de "el ganador se lleva todo", en la que el clasificador con la función de salida más alta asigna la clase (es importante que las funciones de salida estén calibradas para producir puntuaciones comparables). Para el enfoque de uno contra uno, la clasificación se realiza mediante una estrategia de votación de máximos ganadores, en la que cada clasificador asigna la instancia a una de las dos clases, luego el voto para la clase asignada se incrementa en un voto y, finalmente, la clase con más votos determina la clasificación de la instancia.
• Gráfico acíclico dirigido SVM (DAGSVM) ^[30]
• Códigos de salida de corrección de errores ^[31]

Crammer y Singer propusieron un método SVM multiclase que convierte el problema de clasificación multiclase en un único problema de optimización, en lugar de descomponerlo en múltiples problemas de clasificación binaria. ^[32] Véase también Lee, Lin y Wahba ^{[33] [34]} y Van den Burg y Groenen. ^[35]

Las máquinas de vectores de soporte transductivas amplían las máquinas de vectores de soporte en el sentido de que también podrían tratar datos parcialmente etiquetados en el aprendizaje semisupervisado siguiendo los principios de la transducción . Aquí, además del conjunto de entrenamiento , el alumno también recibe un conjunto${\displaystyle {\mathcal {D}}}$

$${\displaystyle {\mathcal {D}}^{\star }=\{\mathbf {x} _{i}^{\star }\mid \mathbf {x} _{i}^{\star }\in \mathbb {R} ^{p}\}_{i=1}^{k}}$$

de ejemplos de prueba a clasificar. Formalmente, una máquina de vectores de soporte transductiva se define mediante el siguiente problema de optimización primaria: ^[36]

Minimizar (en )${\displaystyle \mathbf {w} ,b,\mathbf {y} ^{\star }}$

$${\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}$$

sujeto a (para cualquier y cualquier )${\displaystyle i=1,\dots ,n}$${\displaystyle j=1,\dots ,k}$

$${\displaystyle {\begin{aligned}&y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\\&y_{j}^{\star }(\mathbf {w} \cdot \mathbf {x} _{j}^{\star }-b)\geq 1,\end{aligned}}}$$

y

$${\displaystyle y_{j}^{\star }\in \{-1,1\}.}$$

Las máquinas de vectores de soporte transductivos fueron introducidas por Vladimir N. Vapnik en 1998.

La máquina de vectores de soporte estructurada es una extensión del modelo SVM tradicional. Si bien el modelo SVM está diseñado principalmente para tareas de clasificación binaria, clasificación multiclase y regresión, la SVM estructurada amplía su aplicación para manejar etiquetas de salida estructuradas generales, por ejemplo, árboles de análisis, clasificación con taxonomías, alineación de secuencias y muchas más. ^[37]

En 1996, Vladimir N. Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman y Alexander J. Smola propusieron una versión de SVM para regresión . ^[38] Este método se denomina regresión de vectores de soporte (SVR). El modelo producido por la clasificación de vectores de soporte (como se describió anteriormente) depende solo de un subconjunto de los datos de entrenamiento, porque la función de costo para construir el modelo no se preocupa por los puntos de entrenamiento que se encuentran más allá del margen. Análogamente, el modelo producido por SVR depende solo de un subconjunto de los datos de entrenamiento, porque la función de costo para construir el modelo ignora cualquier dato de entrenamiento cercano a la predicción del modelo. Suykens y Vandewalle propusieron otra versión de SVM conocida como máquina de vectores de soporte de mínimos cuadrados (LS-SVM). ^[39]

Entrenar el SVR original significa resolver ^[40]

minimizar${\displaystyle {\tfrac {1}{2}}\|w\|^{2}}$

sujeto a${\displaystyle |y_{i}-\langle w,x_{i}\rangle -b|\leq \varepsilon }$

donde es una muestra de entrenamiento con valor objetivo . El producto interno más la intersección es la predicción para esa muestra y es un parámetro libre que sirve como umbral: todas las predicciones deben estar dentro de un rango de las predicciones verdaderas. Las variables de holgura se agregan generalmente a lo anterior para permitir errores y una aproximación en caso de que el problema anterior sea inviable.${\displaystyle x_{i}}$${\displaystyle y_{i}}$${\displaystyle \langle w,x_{i}\rangle +b}$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$

En 2011, Polson y Scott demostraron que el SVM admite una interpretación bayesiana a través de la técnica de aumento de datos . ^[41] En este enfoque, el SVM se considera como un modelo gráfico (donde los parámetros están conectados a través de distribuciones de probabilidad). Esta vista extendida permite la aplicación de técnicas bayesianas a los SVM, como el modelado de características flexibles, el ajuste automático de hiperparámetros y la cuantificación predictiva de la incertidumbre . Recientemente, Florian Wenzel desarrolló una versión escalable del SVM bayesiano, lo que permite la aplicación de SVM bayesianos a big data . ^[42] Florian Wenzel desarrolló dos versiones diferentes, un esquema de inferencia variacional (VI) para la máquina de vectores de soporte (SVM) del núcleo bayesiano y una versión estocástica (SVI) para la SVM bayesiana lineal. ^[43]

Los parámetros del hiperplano de margen máximo se derivan de la solución de la optimización. Existen varios algoritmos especializados para resolver rápidamente el problema de programación cuadrática (QP) que surge de las máquinas de modelado de ecuaciones diferenciales, que se basan principalmente en heurísticas para dividir el problema en partes más pequeñas y manejables.

Otro enfoque consiste en utilizar un método de punto interior que utiliza iteraciones similares a las de Newton para encontrar una solución de las condiciones de Karush-Kuhn-Tucker de los problemas primal y dual. ^[44] En lugar de resolver una secuencia de problemas descompuestos, este enfoque resuelve directamente el problema en su totalidad. Para evitar resolver un sistema lineal que involucra la matriz kernel grande, a menudo se utiliza una aproximación de bajo rango a la matriz en el truco del kernel.

Otro método común es el algoritmo de optimización mínima secuencial (SMO) de Platt , que divide el problema en subproblemas bidimensionales que se resuelven analíticamente, eliminando la necesidad de un algoritmo de optimización numérica y de almacenamiento matricial. Este algoritmo es conceptualmente simple, fácil de implementar, generalmente más rápido y tiene mejores propiedades de escalamiento para problemas SVM difíciles. ^[45]

El caso especial de las máquinas de vectores de soporte lineales se puede resolver de manera más eficiente con el mismo tipo de algoritmos utilizados para optimizar su primo cercano, la regresión logística ; esta clase de algoritmos incluye el descenso de subgradiente (por ejemplo, PEGASOS ^[46] ) y el descenso de coordenadas (por ejemplo, LIBLINEAR ^[47] ). LIBLINEAR tiene algunas propiedades de tiempo de entrenamiento atractivas. Cada iteración de convergencia toma tiempo lineal en el tiempo que se tarda en leer los datos de entrenamiento, y las iteraciones también tienen una propiedad de convergencia Q-lineal , lo que hace que el algoritmo sea extremadamente rápido.

Las SVM de núcleo general también se pueden resolver de manera más eficiente utilizando el descenso de subgradiente (por ejemplo, P-packSVM ^[48] ), especialmente cuando se permite la paralelización .

Las SVM de kernel están disponibles en muchos kits de herramientas de aprendizaje automático, incluidos LIBSVM , MATLAB , SAS, SVMlight, kernlab, scikit-learn , Shogun , Weka , Shark, JKernelMachines, OpenCV y otros.

Se recomienda encarecidamente el preprocesamiento de datos (estandarización) para mejorar la precisión de la clasificación. ^[49] Existen algunos métodos de estandarización, como mínimo-máximo, normalización por escala decimal y puntuación Z. ^[50] La resta de la media y la división por la varianza de cada característica se utilizan generalmente para SVM. ^[51]

• Tabulación adaptativa in situ
• Máquinas de núcleo
• Núcleo de Fisher
• Escala de Platt
• Núcleo polinomial
• Análisis predictivo
• Perspectivas de regularización en máquinas de vectores de soporte
• Máquina de vectores de relevancia , un modelo probabilístico de núcleo disperso idéntico en forma funcional a SVM
• Optimización mínima secuencial
• Mapeo espacial
• Winnow (algoritmo)

• Bennett, Kristin P.; Campbell, Colin (2000). "Máquinas de vectores de soporte: ¿exageración o aleluya?" (PDF) . SIGKDD Explorations . 2 (2): 1–13. doi :10.1145/380995.380999. S2CID  207753020.
• Cristianini, Nello; Shawe-Taylor, John (2000). Introducción a las máquinas de vectores de soporte y otros métodos de aprendizaje basados ​​en kernel . Cambridge University Press. ISBN 0-521-78019-5.
• Fradkin, Dmitriy; Muchnik, Ilya (2006). "Máquinas de vectores de soporte para la clasificación" (PDF) . En Abello, J.; Carmode, G. (eds.). Métodos discretos en epidemiología . Serie DIMACS en matemáticas discretas y ciencias de la computación teórica. Vol. 70. págs. 13–20.^{[ cita no encontrada ]}
• Joachims, Thorsten (1998). "Categorización de texto con máquinas de vectores de soporte: aprendizaje con muchas características relevantes". En Nédellec, Claire; Rouveirol, Céline (eds.). "Aprendizaje automático: ECML-98" . Lecture Notes in Computer Science. Vol. 1398. Berlín, Heidelberg: Springer. p. 137-142. doi :10.1007/BFb0026683. ISBN. 978-3-540-64417-0. Número de identificación del sujeto  2427083.
• Ivanciuc, Ovidiu (2007). "Aplicaciones de las máquinas de vectores de soporte en química" (PDF) . Reseñas en química computacional . 23 : 291–400. doi :10.1002/9780470116449.ch6. ISBN 9780470116449.
• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2013). "Máquinas de vectores de soporte" (PDF) . Introducción al aprendizaje estadístico: con aplicaciones en R. Nueva York: Springer. pp. 337–372. ISBN. 978-1-4614-7137-0.
• Schölkopf, Bernhard; Smola, Alexander J. (2002). Aprendiendo con Kernels . Cambridge, MA: MIT Press. ISBN 0-262-19475-9.
• Steinwart, Ingo; Christmann, Andreas (2008). Máquinas de vectores de soporte . Nueva York: Springer. ISBN 978-0-387-77241-7.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2009). Reconocimiento de patrones (4.ª ed.). Academic Press. ISBN 978-1-59749-272-0.

• libsvm, LIBSVM es una biblioteca popular entre los estudiantes de SVM
• liblinear es una biblioteca para clasificación lineal grande que incluye algunas SVM
• SVM light es una colección de herramientas de software para el aprendizaje y la clasificación mediante SVM
• Demostración en vivo de SVMJS Archivado el 5 de mayo de 2013 en Wayback Machine es una demostración de GUI para la implementación de JavaScript de SVM