Máquina de vectores de soporte

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 mayor posible. La región delimitada por estos dos hiperplanos se denomina "margen", y el hiperplano de margen máximo es el 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 sobre este límite o por encima de él pertenece a una sola clase, con la etiqueta 1).

y

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

Geométricamente, la distancia entre estos dos hiperplanos es${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$, ^{[ 21 ]} por lo que para maximizar la distancia entre los planos queremos minimizar${\displaystyle \|\mathbf {w} \|}$La distancia se calcula utilizando la ecuación de 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${\displaystyle i}$cualquiera $${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\geq 1\,,{\text{ si }}y_{i}=1,}$$ o $${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\leq -1\,,{\text{ si }}y_{i}=-1.}$$ Estas restricciones establecen que cada punto de datos debe estar situado en el lado correcto del margen.

Esto se puede reescribir como

Podemos combinar esto para obtener el problema de optimización:

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

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

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

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

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

Esta función es cero si se satisface la restricción en (1) , en otras palabras, si${\displaystyle \mathbf {x} _ {i}}$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 al margen.

El objetivo de la optimización es, por lo tanto, 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${\displaystyle C>0}$determina el equilibrio entre aumentar el tamaño del margen y garantizar que el${\displaystyle \mathbf {x} _ {i}}$se encuentran 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 descomponer la pérdida de bisagra, este problema de optimización se puede formular de la siguiente manera:

$${\displaystyle {\begin{aligned}&{\underset {\mathbf {w} ,\;b,\;\mathbf {\zeta } }{\operatorname {minimizar} }}&&\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{n}\zeta _{i}\\&{\text{sujeto a}}&&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${\displaystyle C}$Se comportará de forma similar a la SVM de margen rígido, si los datos de entrada son clasificables linealmente, pero aun así aprenderá si una regla de clasificación es viable o no.

Minimizar (2) se puede reescribir como un problema de optimización con restricciones y una función objetivo diferenciable de la siguiente manera.

Para cada${\displaystyle i\in \{1,\,\ldots ,\,n\}}$introducimos una variable${\displaystyle \zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)}$. Tenga en cuenta que${\displaystyle \zeta _{i}}$es el número no negativo más pequeño que satisface${\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 conoce como 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 de la${\displaystyle c_{i}}$Sujeto a restricciones lineales, se puede resolver eficientemente mediante algoritmos de programación cuadrática .

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

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

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

El desplazamiento,${\displaystyle b}$, se puede recuperar encontrando un${\displaystyle \mathbf {x} _{i}}$en el límite del margen y resolviendo $${\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${\displaystyle y_{i}^{-1}=y_{i}}$desde${\displaystyle y_{i}=\pm 1}$.)

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

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

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

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

$${\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${\displaystyle c_{i}}$se puede resolver usando programación cuadrática, como antes. Nuevamente podemos encontrar algún índice${\displaystyle i}$de tal manera que${\displaystyle 0<c_{i}<(2n\lambda )^{-1}}$, de modo que${\displaystyle \varphi (\mathbf {x} _{i})}$se encuentra en el límite del margen en el espacio transformado y luego resolver

$${\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 de subgradiente y el descenso de coordenadas. Ambas técnicas han demostrado ofrecer ventajas significativas sobre el enfoque tradicional al trabajar con conjuntos de datos grandes y dispersos: los métodos de subgradiente son especialmente eficientes cuando hay muchos ejemplos de entrenamiento, y el descenso de coordenadas cuando la dimensión del espacio de características es alta.

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

$${\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${\displaystyle X_{n+1},\,y_{n+1}}$directamente. En estos casos, una estrategia común es elegir la hipótesis que minimice el riesgo empírico:

$${\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${\displaystyle X_{k},\,y_{k}}$(por ejemplo, que se generan mediante un proceso de Markov finito), si el conjunto de hipótesis que se consideran es suficientemente pequeño, el minimizador del riesgo empírico se aproximará mucho al minimizador del riesgo esperado como${\displaystyle n}$crece mucho. Este enfoque se llama minimización empírica del riesgo, o ERM.

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

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

Este método se denomina regularización de Tikhonov .

En términos más generales,${\displaystyle {\mathcal {R}}(f)}$puede ser una medida de la complejidad de la hipótesis${\displaystyle f}$, por lo que se prefieren las hipótesis más simples.

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

$${\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}.}$$

En vista de lo anterior, vemos que la técnica SVM es equivalente a la minimización del 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 mínimos cuadrados regularizados y regresión logística . La diferencia entre los tres radica en la elección de la función de pérdida: mínimos cuadrados regularizados equivalen a una minimización del riesgo empírico con la pérdida cuadrática , ${\displaystyle \ell _{sq}(y,z)=(y-z)^{2}}$; la regresión logística emplea la pérdida logarítmica ,

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

La efectividad de SVM depende de la selección del kernel, los parámetros del kernel y el parámetro de margen suave.${\displaystyle \lambda }$Una opción común es un núcleo gaussiano, que tiene un único parámetro.${\displaystyle \gamma }$. La mejor combinación de${\displaystyle \lambda }$y${\displaystyle \gamma }$a menudo se selecciona mediante una búsqueda en cuadrícula con secuencias de crecimiento exponencial de${\displaystyle \lambda }$y${\displaystyle \gamma }$, Por ejemplo,${\displaystyle \lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}}$;${\displaystyle \gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}}$Normalmente, cada combinación de opciones de parámetros se comprueba mediante validación cruzada , y se seleccionan los parámetros con la mejor precisión de validación cruzada. Alternativamente, se puede utilizar trabajo reciente en optimización bayesiana para seleccionar${\displaystyle \lambda }$y${\displaystyle \gamma }$, 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 con todo el conjunto de entrenamiento utilizando los parámetros seleccionados. ^{[ 29 ]}

Entre las posibles desventajas de la SVM se incluyen los siguientes aspectos:

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

El método SVM multiclase tiene como objetivo asignar etiquetas a las 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 en múltiples problemas de clasificación binaria . ^{[ 30 ]} Los métodos comunes para dicha reducción incluyen: ^{[ 30 ] [ 31 ]}

• Construir clasificadores binarios que distingan 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 uno contra todos se realiza mediante una estrategia de "el ganador se lo 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 uno contra uno, la clasificación se realiza mediante una estrategia de votación de "máximo de victorias", 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.
• SVM de grafo acíclico dirigido (DAGSVM) ^{[ 32 ]}
• Códigos de salida de corrección de errores ^{[ 33 ]}

Crammer y Singer propusieron un método SVM multiclase que transforma 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. ^{[ 34 ]} Véase también Lee, Lin y Wahba ^{[ 35 ] [ 36 ]} y Van den Burg y Groenen. ^{[ 37 ]}

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

$${\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 primal: ^{[ 38 ]}

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

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

sujeto a (por cualquier${\displaystyle i=1,\dots ,n}$y cualquier${\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 transductivas fueron introducidas por Vladimir N. Vapnik en 1998.

La máquina de vectores de soporte estructurada es una extensión del modelo SVM tradicional. Mientras que 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 sintáctico, clasificación con taxonomías, alineación de secuencias y muchas más. ^{[ 39 ]}

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 . ^{[ 40 ]} 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 únicamente de un subconjunto de los datos de entrenamiento, ya que la función de coste para construir el modelo no tiene en cuenta los puntos de entrenamiento que se encuentran fuera del margen. De forma análoga, el modelo producido por SVR depende únicamente de un subconjunto de los datos de entrenamiento, ya que la función de coste 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). ^{[ 41 ]}

Entrenar el SVR original significa resolver ^{[ 42 ]}

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

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

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

En 2011, Polson y Scott demostraron que la SVM admite una interpretación bayesiana mediante la técnica de aumento de datos . ^{[ 43 ]} En este enfoque, la SVM se considera un modelo gráfico (donde los parámetros están conectados mediante distribuciones de probabilidad). Esta visión ampliada permite la aplicación de técnicas bayesianas a las SVM, como el modelado flexible de características, el ajuste automático de hiperparámetros y la cuantificación predictiva de la incertidumbre . En 2017, Florian Wenzel desarrolló una versión escalable de la SVM bayesiana , lo que permitió la aplicación de las SVM bayesianas a grandes conjuntos de datos . ^{[ 44 ]} Florian Wenzel desarrolló dos versiones diferentes: un esquema de inferencia variacional (VI) para la máquina de vectores de soporte (SVM) de núcleo bayesiano y una versión estocástica (SVI) para la SVM bayesiana lineal. ^{[ 45 ]}