Máquinas de vectores soporte

En el aprendizaje automático, las máquinas de vectores de soporte (SVM, también redes de vectores de soporte) son modelos de aprendizaje supervisado con algoritmos de aprendizaje asociados que analizan datos para clasificación y análisis de regresión. Desarrollado en AT&T Bell Laboratories por Vladimir Vapnik con colegas (Boser et al., 1992, Guyon et al., 1993, Cortes and Vapnik, 1995, Vapnik et al., 1997) Las SVM son uno de los métodos de predicción más robustos, basándose en marcos de aprendizaje estadístico o teoría VC propuesta por Vapnik (1982, 1995) y Chervonenkis (1974). Dado un conjunto de ejemplos de entrenamiento, cada uno marcado como perteneciente a una de dos categorías, un algoritmo de entrenamiento SVM construye un modelo que asigna nuevos ejemplos a una categoría u otra, convirtiéndolo en un clasificador lineal binario no probabilístico (aunque métodos como Platt existen escalas para usar SVM en una configuración de clasificación probabilística). SVM asigna ejemplos de entrenamiento a puntos en el espacio para maximizar el ancho de la brecha entre las dos categorías. Luego, los nuevos ejemplos se mapean en ese mismo espacio y se predice que pertenecen a una categoría según el lado de la brecha en el que se encuentran.

Además de realizar una clasificación lineal, las SVM pueden realizar de manera eficiente una clasificación no lineal mediante lo que se denomina el truco del núcleo, asignando implícitamente sus entradas a espacios de características de alta dimensión.

Cuando los datos no están etiquetados, el aprendizaje supervisado no es posible y se requiere un enfoque de aprendizaje no supervisado, que intenta encontrar un agrupamiento natural de los datos en grupos y luego asignar nuevos datos a estos grupos formados. El algoritmo de agrupación de vectores de soporte, creado por Hava Siegelmann y Vladimir Vapnik, aplica las estadísticas de vectores de soporte, desarrolladas en el algoritmo de máquinas de vectores de soporte, para categorizar datos sin etiquetar.

Motivación

H₁ no separa las clases. H₂ Sí, pero sólo con un pequeño margen. H₃ los separa con el margen máximo.

La clasificación de datos es una tarea común en el aprendizaje automático. Suponga algunos puntos de datos dados cada uno pertenece a una de dos clases, y el objetivo es decidir qué clase a nuevo El punto de datos estará dentro. En el caso de las máquinas vectoriales de soporte, se considera un punto de datos como ${displaystyle p}$-dimensional vector (una lista de ${displaystyle p}$ números), y queremos saber si podemos separar tales puntos con un ${displaystyle (p-1)}$- 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 separación más grande, o margen, entre las dos clases. Así que elegimos el hiperplano para que la distancia de él al punto de datos más cercano de cada lado sea maximizada. Si existe tal hiperplano, se conoce como el hiperplano de máx. y el clasificador lineal que define es conocido como clasificatorio de máximo nivel; o equivalentemente, el perceptron de estabilidad óptima.

De manera más formal, 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 la clasificación, la regresión u otras tareas, como la detección de valores atípicos. Intuitivamente, una buena separación la logra 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 es el margen, menor es el error de generalización del clasificador.

Máquina de kernel

Mientras que el problema original se puede decir en un espacio finito-dimensional, a menudo sucede que los conjuntos para discriminar no son linealmente separables en ese espacio. Por esta razón, se propuso que el espacio original de dimensiones finitas se mapee en un espacio mucho más alto, presumiblemente haciendo la separación más fácil en ese espacio. Para mantener la carga computacional razonable, los mapas utilizados por los esquemas SVM están diseñados para asegurar que los productos de puntos de pares de vectores de datos de entrada puedan ser calculados fácilmente en términos de las variables en el espacio original, definiéndolos en términos de una función del núcleo ${displaystyle k(x,y)}$ seleccionado para adaptarse al problema. Los hiperplanos en el espacio de mayor dimensión se definen como el conjunto de puntos cuyo producto de punto con un vector en ese espacio es constante, donde tal 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 se pueden elegir para ser combinaciones lineales con parámetros ${displaystyle alpha _{i}$ de imágenes de vectores de características ${displaystyle x_{i}}$ que ocurre en la base de datos. Con esta elección de un hiperplano, los puntos ${displaystyle x}$ en el espacio de características que se mapean en el hiperplano se definen por la relación ${displaystyle textstyle sum _{i}alpha _{i}k(x_{i},x)={text{constant}}.}$ Note que si ${displaystyle k(x,y)}$ se hace pequeño ${displaystyle y}$ crece más lejos de ${displaystyle x}$, cada término en la suma mide el grado de cercanía del punto de prueba ${displaystyle x}$ al punto de base de datos correspondiente ${displaystyle x_{i}}$. De esta manera, la suma de los kernels anteriores se puede utilizar para medir la proximidad relativa de cada punto de prueba a los puntos de datos originados en uno o el otro de los conjuntos a ser discriminados. Note el hecho de que el conjunto de puntos ${displaystyle x}$ mapped into any hyperplane can be quite convoluted as a result, allowing much more complex discrimination between sets that are not convex at all in the original space.

Aplicaciones

Las SVM se pueden usar para resolver varios problemas del mundo real:

• Los 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 estándar como transductora. Algunos métodos para la perspicacia semántica poco profunda se basan en máquinas vectoriales de soporte.
• La clasificación de imágenes también se puede realizar utilizando SVMs. Los resultados experimentales muestran que los SVM logran una precisión de búsqueda significativamente mayor que los esquemas tradicionales de refinamiento de consultas después de sólo tres a cuatro rondas de comentarios relevantes. Esto también es cierto para los sistemas de segmentación de imágenes, incluyendo aquellos que utilizan una versión modificada SVM que utiliza el enfoque privilegiado como sugiere Vapnik.
• Clasificación de datos satelitales como datos SAR usando SVM supervisado.
• Los caracteres manuscritos a mano pueden ser reconocidos usando SVM.
• El algoritmo SVM ha sido ampliamente aplicado en las ciencias biológicas y otras ciencias. Se han 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 mecanismo de interpretación de modelos SVM. Los pesos de la máquina vectorial de soporte también se han utilizado para interpretar modelos SVM en el pasado. La interpretación poshoc de los modelos de máquinas vectoriales de apoyo para identificar las características utilizadas por el modelo para hacer predicciones es un área relativamente nueva de investigación con especial importancia en las ciencias biológicas.

Historia

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

MVS lineal

Hiperplano y márgenes máximo para un SVM entrenado con muestras de dos clases. Las muestras al margen se llaman vectores de soporte.

Se nos da un conjunto de datos de entrenamiento ${displaystyle n}$ puntos de la forma

$${displaystyle (mathbf {x} _{1},y_{1}),ldots(mathbf {x} _{n},y_{n}),}$$

${displaystyle Y...$

${displaystyle mathbf {x} _{i}$

${displaystyle mathbf {x} _{i}$

${displaystyle p}$

${displaystyle mathbf {x} _{i}$

${displaystyle Y...$

${displaystyle Y...$

${displaystyle mathbf {x} _{i}$

Cualquier hiperplano se puede escribir como el conjunto de puntos ${displaystyle mathbf {x}$ satisfacción

$${displaystyle mathbf {w} {fnMithsf {T}mathbf {x} -b=0,}$$

${displaystyle mathbf {w}$

${displaystyle mathbf {w}$

${displaystyle {tfrac {}{fnMitbf} {}}$

${displaystyle mathbf {w}$

Margen rígido

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 la mayor 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} {fnMithsf {f}mathbf {x} -b=1}$ (todo en o por encima de este límite es de una clase, con etiqueta 1)

y

${displaystyle mathbf {w} {fnMithsf {f}mathbf {x} -b=-1}$ (todo en o debajo de este límite es de la otra clase, con etiqueta −1).

Geométricamente, la distancia entre estos dos hiperplanos es ${displaystyle {tfrac {2}{fnMitbf} {}}$, para maximizar la distancia entre los aviones que queremos minimizar ${displaystylefnMitbf {f}fnh}$. La distancia se calcula utilizando la distancia de un punto a una ecuación de avión. También tenemos que evitar que los puntos de datos caigan en el margen, agregamos la siguiente limitación: para cada uno ${displaystyle i}$ o

$${displaystyle mathbf {w} {f}mthbf {x} _{i}-bgeq 1,{text{ if{ if{ if Sí.$$

$${displaystyle mathbf {w} {fnMithsf {f}mathbf {x} ¿Por qué? Sí.$$

Esto se puede reescribir como

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

()1)

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

${fnMicrosoft {fnMicrosoft} {fnMicrosoft} {f}fnMicrosoft} {f}} {fnMicrosoft} {f}fnMicrosoft} {f}fnMicrosoft} {f}fnMicrosoft} {minimize} } {fnMitbf} {fnMitbf {fnMitbf {fnh} {fnMitbf {f}mathbf {x}gn}gnf}fnMitbf {fnh}gnf}fnfnMitsn}n}fnfnfn}f}f}fn}}}}}}fnfnfnfn}}}}fnfnfnfnfn}}\fnKfnfn}}\n\\\\\\\\\\\\\\\fnK\\\fn\\\\\\\\\\\\\\\\\\\\\\\\\\\$

El ${displaystyle mathbf {w}$ y ${displaystyle b}$ que resuelve este problema determina nuestro clasificador, ${displaystyle mathbf {x} mapsto operatorname {sgn}(mathbf {w} ^{mathsf {T}mathbf {x} -b)}$ Donde ${displaystyle operatorname {sgn}(cdot)}$ es la función de señal.

Una consecuencia importante de esta descripción geométrica es que el hiperplano max-margin está completamente determinado por aquellos ${displaystyle mathbf {x} _{i}$ que está más cerca. Éstos ${displaystyle mathbf {x} _{i}$ se llaman vectores de apoyo.

Margen suave

Para extender SVM a casos en los que los datos no son linealmente separables, la función pérdida de bisagra es útil

$${displaystyle max left(0,1-y_{i}(mathbf {w} ^{mathsf {T}mathbf {x} _{i}-b)right). }$$

Note que ${displaystyle Y...$ es i- el objetivo (es decir, en este caso, 1 o −1), y ${displaystyle mathbf {w} {fnMithsf {f}mathbf {x} ¿Qué?$ es i- la salida.

Esta función es cero si la limitación 1) está satisfecho, en otras palabras, si ${displaystyle mathbf {x} _{i}$ se encuentra en el lado correcto del margen. Para datos en el lado equivocado del margen, el valor de la función es proporcional a la distancia del margen.

Entonces, el objetivo de la optimización es minimizar

$${displaystyle lambda lVert mathbf {w} Vert ^{2}+left [{frac {1}{n}sum ¿Por qué?$$

donde el parámetro ${displaystyle lambda }$ determina la compensación entre aumentar el tamaño del margen y asegurar que el ${displaystyle mathbf {x} _{i}$ miente en el lado correcto del margen. Desconstruyendo la pérdida de bisagra, este problema de optimización se puede masajear en los siguientes:

${displaystyle {begin{aligned} {fnK} {fnMimize}} {fnMimize}}} {fnMimize}}} {\fnMitbf {f}}} {fnMimize}}}} {fnMitbf} {2}+Csum ¿Qué? ¿Por qué? _{i},quad zeta ¿Por qué?$

Así, por grandes valores ${displaystyle C}$, se comportará similar al SVM hard-margin, si los datos de entrada son linealmente clasificables, pero todavía aprenderá si una regla de clasificación es viable o no. ()${displaystyle lambda }$ está inversamente relacionado con ${displaystyle C}$, por ejemplo LIBSVM.)

Núcleos no lineales

Máquina de kernel

El algoritmo de hiperplano de margen máximo original 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.) a hiperplanos de margen máximo. El algoritmo resultante es formalmente similar, excepto que cada producto escalar se reemplaza por una función kernel no lineal. Esto permite que el algoritmo se ajuste al 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 con suficientes muestras, el algoritmo sigue funcionando bien.

Algunos núcleos comunes incluyen:

• Polynomial (homogeneous): ${displaystyle k(mathbf {x} _{i},mathbf {x})=(mathbf {x} ¿Qué?$. Particularmente, cuando ${displaystyle d=1}$, esto se convierte en el núcleo lineal.
• Polynomial (inhomogeneous): ${displaystyle k(mathbf {x} _{i},mathbf {x})=(mathbf {x} ¿Qué?$.
• Función de base radial gausiana: ${displaystyle k(mathbf {x} _{i},mathbf {x} _{j})=exp left(-gammaleft eternamentemathbf {x} ¿Por qué?$ para ${displaystyle gamma >0}$. A veces parametrizado usando ${displaystyle gamma =1/(2sigma ^{2}}$.
• Función sigmoide (tangente hiperbólico): ${displaystyle k(mathbf {x_{i}mathbf {x_{j})=tanh(kappa mathbf {x} _{i}cdot mathbf {x} _{j}+c)}}}$ para algunos (no todos) ${displaystyle kappa }$ y ${displaystyle c realizadas0}$.

El núcleo está relacionado con la transformación ${displaystyle varphi (mathbf {x} _{i})}$ por la ecuación ${displaystyle k(mathbf {x} _{i},mathbf {x} _{j})=varphi (mathbf {x} _{i})cdot varphi (mathbf {x_{j})}}}}$. El valor w está también en el espacio transformado, con ${textstyle mathbf {w} =sum _{i}alpha - Sí.$. Productos de punto con w para la clasificación puede ser computada de nuevo por el truco del núcleo, es decir. ${textstyle mathbf {w} cdot varphi (mathbf {x}=sum _{i}alpha - Sí.$.

Cálculo del clasificador SVM

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

$${displaystyle left[{frac {1}{n}sum ¿Por qué? "Perfecto".$$

()2)

Nos centramos en el clasificatorio de color suave ya que, como se señaló anteriormente, elegir un valor suficientemente pequeño para ${displaystyle lambda }$ produce el clasificador de hard-margin 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. Luego se discutirán enfoques más recientes como el descenso del subgrado y el descenso de coordenadas.

Primaria

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

Para cada uno ${displaystyle iin {1,,ldots,n}$ presentamos una variable ${displaystyle zeta _{i}=max left(0,1-y_{i}(mathbf {w} ^{mathsf {T}mathbf {x} _{i}-b)right)}$. Note que ${displaystyle zeta ¿Qué?$ es el menor número no negativo que satisface ${displaystyle y_{i}(Mathbf {w} ¿Qué? _{i}$

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

$${displaystyle {begin{aligned} {text{minimize }{frac {1}{n}}sum} {fn} {fn} {fn}}}} {fn}}}}} {fn}}} {fn}}}}}}} {fn}}}}}} {fn}}}}}}}}}}} {f}}}}}}}}}}}}}}}}}}}}}} {f} {f}}}}}}}}} {b}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {f}}}} {b}}}}}}}}}}}}}}}}}}} {b}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} - ¿Por qué? _{i}+lambda eternamathbf {w} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}$$

Esto se llama el problema primario.

Doble

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 ¿Qué? {1}{2}sum - ¿Qué? ¿Qué? Y... ¿Por qué? {fnfncncncncncHFF};{text{ for all }i.end{aligned}}}}}$$

Esto se llama dual problema. Puesto que el problema de la doble maximización es una función cuadrática de la ${displaystyle C_{i}$ sujeto a limitaciones lineales, es eficientemente solvable por algoritmos de programación cuadrática.

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

$${displaystyle mathbf {w} = ¿Por qué? {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 madec_{i}traducido(2nlambda)}{-1}$ cuando ${displaystyle mathbf {x} _{i}$ se encuentra en el límite del margen. De ello se desprende que ${displaystyle mathbf {w}$ se puede escribir como una combinación lineal de los vectores de soporte.

La compensación, ${displaystyle b}$, se puede recuperar encontrando un ${displaystyle mathbf {x} _{i}$ en el límite del margen y resolución

$${displaystyle y_{i}(Mathbf {w} Mathbf {x} - ¿Qué? Mathbf {x} - Sí.$$

(Nota eso) ${displaystyle Y...$ desde entonces ${displaystyle Y... 1}$.)

Truco del núcleo

Un ejemplo de entrenamiento de SVM con núcleo dado por φ(a, b) =a, b, a² + b²)

Supongamos ahora que nos gustaría aprender una regla de clasificación no lineal que corresponde a una regla de clasificación lineal para los puntos de datos transformados ${displaystyle varphi (mathbf {x} _{i}).}$ Además, se nos da una función del núcleo ${displaystyle k}$ que satisfice ${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

$${displaystyle mathbf {w} = ¿Qué? (Mathbf {x} _{i}),}$$

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

$${displaystyle {begin{aligned}{text{maximize},f(c_{1}ldots c_{n} ¿Qué? {1}{2}sum - ¿Qué? ¿Por qué? Y... ¿Qué? {1}{2}sum - ¿Qué? ¿Qué? Y... ################################################################################################################################################################################################################################################################ {fnfncncncncncHFF};{text{ for all }i.end{aligned}}}}}$$

Los coeficientes ${displaystyle C_{i}$ se puede resolver para utilizar la programación cuadrática, como antes. De nuevo, podemos encontrar un índice ${displaystyle i}$ tales que ${displaystyle 0 madec_{i}traducido(2nlambda)}{-1}$Así 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 {}varphi (mathbf {x} Y... ¿Qué? (mathbf {x} _{j})cdot varphi (mathbf {x} _{i})right]-y_{i}\\cdot varphi (mathbf {x} _{i})right] ¿Por qué?$$

Finalmente,

$${displaystyle mathbf {z} mapsto operatorname {sgn}(mathbf {w} ^{mathsf {T}varphi (mathbf {z})-b)=operatorname {sgn} left(left[sum ¿Por qué? }$$

Métodos modernos

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

Descenso de subgradiente

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

$${displaystyle f(mathbf {}b)=left[{frac {1}{n}sum} ¿Por qué? "Perfecto".$$

Note que ${displaystyle f}$ es una función convexa de ${displaystyle mathbf {w}$ y ${displaystyle b}$. Como tal, se pueden adaptar los métodos tradicionales de descenso de gradiente (o SGD), 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 ${displaystyle n}$, el número de puntos de datos.

Descenso coordinado

Algoritmos de descenso de coordenadas para el trabajo de SVM a partir del problema dual

$${displaystyle {begin{aligned} {text{maximize},,f(c_{1}ldots C_{n}=sum ¿Qué? {1}{2}sum - ¿Qué? ¿Por qué? Y... ¿Por qué? {fnfncncncncncHFF};{text{ for all }i.end{aligned}}}}}$$

Para cada uno ${displaystyle iin {1,,ldots,n}$, iterativamente, el coeficiente ${displaystyle C_{i}$ se ajusta en la dirección de ${displaystyle partial f/partial C_{i}$. Entonces, el vector resultante de los coeficientes ${displaystyle (c_{1}',,ldots,c_{n}'$ se proyecta sobre el vector más cercano de coeficientes que satisface las limitaciones dadas. (Típicamente se utilizan distancias Euclides.) El proceso se repite hasta que se obtenga un vector casi óptimo de coeficientes. El algoritmo resultante es extremadamente rápido en la práctica, aunque se han demostrado pocas garantías de rendimiento.

Minimización empírica del riesgo

La máquina de vector 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 bisagra. Visto 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 más información sobre cómo y por qué funcionan las SVM y permitirnos analizar mejor sus propiedades estadísticas.

Minimización de riesgos

En el aprendizaje supervisado se da un conjunto de ejemplos de capacitación ${displaystyle X_{1}ldots X_{n}$ con etiquetas ${displaystyle y_{1}ldots y_{n}$, y desea predecir ${displaystyle Y...$ dado ${displaystyle X_{n+1}$. Para hacerlo se forma una hipótesis, ${displaystyle f}$, tal que ${displaystyle f(X_{n+1})}$ es una aproximación "buena" de ${displaystyle Y...$. Una aproximación "buena" generalmente se define con la ayuda de un función de pérdida, ${displaystyle ell (y,z)}$, que caracteriza lo malo ${displaystyle z}$ es como una predicción de ${displaystyle y}$. Entonces nos gustaría elegir una hipótesis que minimiza la riesgo previsto:

$${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}$ Claro. En estos casos, una estrategia común es elegir la hipótesis que minimiza la riesgo empírico:

$${displaystyle {hat {varepsilon}(f)={frac {1}{n}sum} ¿Qué? }$$

Bajo ciertas suposiciones sobre la secuencia de variables aleatorias ${displaystyle ¿Qué?$ (por ejemplo, que son generados por un proceso finito de Markov), si el conjunto de hipótesis que se considera es lo suficientemente pequeño, el minimizador del riesgo empírico aproximará de cerca al minimizador del riesgo esperado como ${displaystyle n}$ crece grande. Este enfoque se denomina minimización del riesgo empírico, o GRI.

Regularización y estabilidad

Para que el problema de minimización tenga una solución bien definida, tenemos que colocar restricciones en el conjunto ${displaystyle {fnMithcal}}$ de hipótesis que se consideran. Si ${displaystyle {fnMithcal}}$ es un espacio normal (como es el caso del SVM), una técnica particularmente eficaz es considerar solamente esas hipótesis ${displaystyle f}$ para la cual ${displaystyle lVert fr Vert _{Mathcal {H}Seguido$. Esto equivale a imponer un penalización de la regularización ${displaystyle {Mathcal {R}(f)=lambda ¿Qué? Vert fr Vert _{Mathcal {H}}$, y resolver el nuevo problema de optimización

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

Este enfoque se llama regularización de Tikhonov.

Más generalmente, ${displaystyle {mathcal {R}(f)}$ puede ser alguna medida de la complejidad de la hipótesis ${displaystyle f}$, por lo que las hipótesis más simples son preferidas.

SVM y la pérdida de bisagra

Recuerda que el clasificatorio SVM (soft-margin) ${displaystyle {hat {mathbf}},b:mathbf {x} mapsto operatorname {sgn}({hat {mathbf {w} ¿Qué?$ es elegido para minimizar la siguiente expresión:

$${displaystyle left[{frac {1}{n}sum ¿Por qué? "Perfecto".$$

A la luz de la discusión anterior, vemos que la técnica SVM es equivalente a la minimización empírica del riesgo con la 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-yzright). }$$

Desde esta perspectiva, el 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 las tres mentiras en la elección de la función de pérdida: las menos cuadras regularizadas equivalen a minimizar el riesgo empírico con la pérdida cuadrada, ${displaystyle ell _{sq}(y,z)=(y-z)^{2}$; regresión logística emplea la pérdida de registro,

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

Funciones objetivo

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

En particular, ${displaystyle y_{x}$ denota ${displaystyle y}$ condicional en el evento que ${displaystyle X=x}$. En la clasificación tenemos:

$${displaystyle Y_{x}={begin{cases}1 }p_{x}\-1 }1-p_{x}end{cases}}$$

El clasificador óptimo es por lo tanto:

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

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

Por otro lado, se puede comprobar que la función de destino para la pérdida de bisagra es exactamente ${displaystyle f^{*}$. Así, en un espacio de hipótesis suficientemente rico, o equivalentemente, para un núcleo elegido apropiadamente, el clasificador SVM convergerá a la función más simple (en términos de función más simple) ${displaystyle {fnMithcal}}$) que correctamente clasifica los datos. Esto extiende la interpretación geométrica de SVM -para clasificación lineal, el riesgo empírico se minimiza por cualquier función cuyos márgenes se encuentran entre los vectores de soporte, y el más simple de estos es el clasificatorio max-margin.

Propiedades

Las SVM pertenecen a una familia de clasificadores lineales generalizados y pueden interpretarse como una extensión del perceptrón. También pueden considerarse un caso especial de regularización de Tikhonov. Una propiedad especial es que simultáneamente minimizan el error de clasificación empírico y maximizan el margen geométrico; de ahí que también se los conozca como clasificadores de margen máximo.

Meyer, Leisch y Hornik han realizado una comparación del SVM con otros clasificadores.

Selección de parámetros

La eficacia de SVM depende de la selección del kernel, los parámetros del kernel y el parámetro de margen suave ${displaystyle lambda }$. Una elección común es un núcleo Gaussiano, que tiene un solo parámetro ${displaystyle gamma }$. La mejor combinación de ${displaystyle lambda }$ y ${displaystyle gamma }$ es a menudo seleccionado por una búsqueda de la red con secuencias de crecimiento exponencial de ${displaystyle lambda }$ y ${displaystyle gamma }$, por ejemplo, ${displaystyle lambda in {2^{-5},2^{-3},dots2^{13},2^{15}}}$; ${displaystyle gamma in {2^{-15},2^{-13},dots2^{1},2^{3}}}$. Por lo general, cada combinación de opciones de parámetro se comprueba mediante validación cruzada, y se seleccionan los parámetros con la mejor precisión de validación cruzada. Alternativamente, el trabajo reciente en la optimización bayesiana se puede utilizar para seleccionar ${displaystyle lambda }$ y ${displaystyle gamma }$ a menudo requieren la evaluación de muchas menos combinaciones de parámetro que la búsqueda de cuadrícula. El modelo final, que se utiliza para la prueba y para la clasificación de nuevos datos, se entrena en todo el conjunto de entrenamiento utilizando los parámetros seleccionados.

Problemas

Los posibles inconvenientes de la SVM incluyen los siguientes aspectos:

• Requiere etiquetado completo de los datos de entrada
• Probabilidades de afiliación de clase no calibradas: SVM se deriva de la teoría de Vapnik que evita estimar probabilidades de datos finitos
• El SVM sólo es directamente aplicable para tareas de dos clases. Por lo tanto, los algoritmos que reducen la tarea de varias clases a varios problemas binarios tienen que ser aplicados; vea la sección SVM de clase múltiple.
• Los parámetros de un modelo resuelto son difíciles de interpretar.

Extensiones

Apoyo a la agrupación de vectores (SVC)

SVC es un método similar que también se basa en las funciones del kernel, pero es adecuado para el aprendizaje no supervisado.

SVM multiclase

Multiclass SVM 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 a múltiples problemas de clasificación binaria. Los métodos comunes para tal reducción incluyen:

• Construyendo clasificadores binarios que distinguen entre una de las etiquetas y el resto (uno-versus-all) o entre cada par de clases (uno-versus-uno). La clasificación de nuevas instancias para el caso único-versus-all se hace por una estrategia ganador-todas, en la que el clasificador con la función de mayor rendimiento asigna a la clase (es importante que las funciones de salida se calibran para producir puntuaciones comparables). Para el enfoque uno-versus-uno, la clasificación se hace por una estrategia de votación de máximo-ganancia, en la que cada clasificador asigna el caso a una de las dos clases, luego el voto de la clase asignada se aumenta por un voto, y finalmente la clase con más votos determina la clasificación de instancia.
• Gráfico acíclico dirigido SVM (DAGSVM)
• Códigos de salida incorrectos

Crammer y Singer propusieron un método SVM multiclase que convierte el problema de clasificación multiclase en un solo problema de optimización, en lugar de descomponerlo en múltiples problemas de clasificación binaria. Véase también Lee, Lin y Wahba y Van den Burg y Groenen.

Máquinas transductivas de vectores de soporte

Las máquinas vectoriales de soporte transductor extienden SVMs porque también podrían tratar datos etiquetados parcialmente en el aprendizaje semisupervisado siguiendo los principios de la transducción. Aquí, además del conjunto de entrenamiento ${displaystyle {fnMithcal}}$, el estudiante también se le da un conjunto

$${displaystyle {fnMithcal {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {f}} {fnMicrosoft} {fnMicrosoft {fnMicrosoft}}}} {f}} {fnMicrosoft {fnMicrosoft} }= {\\\\\\\\\cHFF} ¿Qué? }mid mathbf {x} ¿Qué? }in mathbb {R} {fn} {fn}} {fnK}} {fnK}} {fnK} {fn}}} {fn}}}}}}}}} {fnK}}}} {fn}}}} {f}}}}}}}} {\fn}}}}}}}}}}}} {}}}}}}}}}}}}}}}}} {\\\\\\\}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$$

de ejemplos de prueba a clasificar. Formalmente, una máquina de vector de soporte transductivo se define mediante el siguiente problema de optimización primal:

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

$${displaystyle {frac}{2}fnMithbf {w} {2}$$

(para cualquier ${displaystyle i=1,dotsn}$ y cualquier ${displaystyle j=1,dotsk}$)

$${displaystyle {begin{aligned} limity_{i}(mathbf {w} cdot mathbf {x} _{i}-b)gq 1,\c} {m} {m} {mmâtbf {w} cdot mathbf {x} _{j}{star }-b)geq 1,end{aligned}}$$

y

$${displaystyle y_{j}{star }in {-1,1}$$

Vladimir N. Vapnik introdujo las máquinas de vector de soporte transductivo en 1998.

SVM estructurada

Las SVM se han generalizado a SVM estructuradas, donde el espacio de la etiqueta está estructurado y posiblemente tenga un tamaño infinito.

Regresión

Soporte de regresión vectorial (predicción) con diferentes umbrales ε. As ε aumenta, la predicción se vuelve menos sensible a los errores.

Vladimir N. Vapnik, Harris Drucker, Christopher J. C. Burges, Linda Kaufman y Alexander J. Smola propusieron una versión de SVM para la regresión en 1996. Este método se llama regresión de vector 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 han propuesto otra versión de SVM conocida como máquina de vectores de soporte de mínimos cuadrados (LS-SVM).

Entrenar el SVR original significa resolver

minimizar ${displaystyle {tfrac {2}fnhfnhfnK} {fnK}}$

sujeto a ${displaystyle - ¿Qué? -b sufrimientoleq varepsilon }$

Donde ${displaystyle x_{i}}$ es una muestra de entrenamiento con valor objetivo ${displaystyle Y...$. El producto interior más la interceptació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 tienen que estar dentro de un ${displaystyle varepsilon }$ rango de las verdaderas predicciones. Las variables slack se agregan generalmente en lo anterior para permitir errores y permitir la aproximación en el caso de que el problema anterior es infeasible.

MVS bayesiana

En 2011 Polson y Scott demostraron que la SVM admite una interpretación bayesiana mediante la técnica de aumento de datos. En este enfoque, la SVM se ve como un modelo gráfico (donde los parámetros están conectados a través de distribuciones de probabilidad). Esta vista ampliada permite la aplicación de técnicas bayesianas a las 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 de Bayesian SVM, que permite la aplicación de Bayesian SVM a big data. 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.

Implementación

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

Otro enfoque es usar un método de punto interior que usa iteraciones similares a las de Newton para encontrar una solución de las condiciones de Karush-Kuhn-Tucker de los problemas primal y dual. En lugar de resolver una secuencia de problemas fragmentados, este enfoque resuelve directamente el problema por completo. Para evitar resolver un sistema lineal que involucre la matriz kernel grande, a menudo se usa una aproximación de rango bajo 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, lo que elimina la necesidad de un algoritmo de optimización numérica y almacenamiento de matriz. Este algoritmo es conceptualmente simple, fácil de implementar, generalmente más rápido y tiene mejores propiedades de escalado para problemas difíciles de SVM.

El caso especial de las máquinas de vectores de soporte lineal se puede resolver de manera más eficiente mediante el mismo tipo de algoritmos que se utilizan para optimizar su prima cercana, la regresión logística; esta clase de algoritmos incluye el descenso de subgradiente (p. ej., PEGASOS) y el descenso de coordenadas (p. ej., LIBLINEAR). LIBLINEAR tiene algunas propiedades de tiempo de entrenamiento atractivas. Cada iteración de convergencia toma un tiempo lineal en el tiempo necesario para leer los datos del tren, y las iteraciones también tienen una propiedad de convergencia Q-lineal, lo que hace que el algoritmo sea extremadamente rápido.

Las SVM generales del kernel también se pueden resolver de manera más eficiente mediante el descenso de subgradiente (por ejemplo, P-packSVM), especialmente cuando se permite la paralelización.

Los 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 procesamiento previo de los datos (estandarización) para mejorar la precisión de la clasificación. Existen algunos métodos de estandarización, como min-max, normalización por escala decimal, Z-score. La resta de la media y la división por la varianza de cada característica generalmente se usa para SVM.