Máquinas de vectores soporte - Support-vector machine

En el aprendizaje automático , las máquinas de vectores de soporte ( SVM , también redes de vectores de soporte ) son modelos de aprendizaje supervisados con algoritmos de aprendizaje asociados que analizan datos para el análisis de clasificación y regresión . Desarrollado en AT&T Bell Laboratories por Vladimir Vapnik con colegas (Boser et al., 1992, Guyon et al., 1993, Vapnik et al., 1997) Las SVM son uno de los métodos de predicción más robustos, ya que se basan en marcos de aprendizaje estadístico o VC teoría 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 de 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 un entorno 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 en función de qué lado de la brecha se encuentran.

Además de realizar una clasificación lineal , las SVM pueden realizar de manera eficiente una clasificación no lineal utilizando lo que se llama el truco del kernel , mapeando implícitamente sus entradas en 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 la agrupación natural de los datos en grupos y luego mapear nuevos datos a estos grupos formados. El algoritmo de agrupamiento de vectores de soporte , creado por Hava Siegelmann y Vladimir Vapnik , aplica las estadísticas de vectores de apoyo, desarrolladas en el algoritmo de máquinas de vectores de apoyo, para categorizar datos sin etiquetar, y es uno de los algoritmos de agrupamiento más utilizados en aplicaciones industriales.

Motivación

H 1 no separa las clases. H 2 lo hace, pero solo con un pequeño margen. H 3 los separa con el margen máximo.

La clasificación de datos es una tarea común en el aprendizaje automático . Suponga que algunos puntos de datos dados pertenecen cada uno a una de dos clases, y el objetivo es decidir en qué clase estará un nuevo punto de datos . En el caso de máquinas de vectores de soporte, un punto de datos se ve como un vector -dimensional (un lista de números), y queremos saber si podemos separar tales puntos con un hiperplano -dimensional . A esto se le llama clasificador lineal . Hay muchos hiperplanos que pueden clasificar los datos. Una elección razonable como mejor hiperplano es la que representa la mayor separación, o margen , entre las dos clases. Así que elegimos el hiperplano para maximizar la distancia desde él hasta el punto de datos más cercano en cada lado. Si existe tal un hiperplano, se conoce como el hiperplano máximo margen y el clasificador lineal que define que se conoce como una de máxima clasificador margen ; o equivalentemente, el perceptrón de estabilidad óptima .

Definición

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 puede usarse para clasificación , regresión u otras tareas como la detección de valores atípicos. Intuitivamente, se logra una buena separación por 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 granos

Mientras que 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 que el espacio original de dimensión finita se mapeara en un espacio de dimensiones mucho más altas, presumiblemente facilitando la separación en ese espacio. Para mantener la carga computacional razonable, las asignaciones utilizadas por los esquemas SVM están diseñadas para garantizar 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 del núcleo seleccionada. para adaptarse al problema. Los hiperplanos en el espacio de dimensiones superiores se definen como el conjunto de puntos cuyo producto escalar 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 que sean combinaciones lineales con parámetros de imágenes de vectores de características que ocurren 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.Nota que si se vuelve pequeño a medida que crece más lejos de , cada término en la suma mide el grado de cercanía del punto de prueba a el punto de base de datos correspondiente . De esta manera, la suma de los núcleos anteriores se puede utilizar para medir la proximidad relativa de cada punto de prueba a los puntos de datos que se originan en uno u otro de los conjuntos que se van a discriminar. Tenga en cuenta el hecho de que, como resultado, el conjunto de puntos mapeados en cualquier hiperplano puede ser bastante complicado, lo que permite una discriminación mucho más compleja entre conjuntos que no son convexos en absoluto en el espacio original.

Aplicaciones

Las SVM se pueden utilizar para resolver varios 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 estándar inductiva como transductiva . Algunos métodos para el análisis semántico superficial se basan en máquinas de vectores de soporte.
  • La clasificación de imágenes también se puede realizar utilizando SVM. Los resultados experimentales muestran que las SVM logran una precisión de búsqueda significativamente mayor que los esquemas tradicionales de refinamiento de consultas 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 los que utilizan una versión modificada de SVM que utiliza el enfoque privilegiado sugerido por Vapnik.
  • Clasificación de datos satelitales como datos SAR utilizando SVM supervisado.
  • Los caracteres escritos a mano se pueden reconocer mediante SVM.
  • El algoritmo SVM se ha aplicado ampliamente en las ciencias biológicas y otras. Se han utilizado para clasificar proteínas con hasta un 90% de los compuestos clasificados correctamente. Las pruebas de permutación basadas en pesos de SVM se han sugerido como un mecanismo para la interpretación de modelos de SVM. Los pesos de máquina de vectores de soporte también se han utilizado para interpretar modelos SVM en el pasado. La interpretación post hoc de modelos de máquinas de vectores de soporte con el fin de 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.

Historia

El algoritmo SVM original fue inventado por Vladimir N. Vapnik y Alexey Ya. Chervonenkis en 1963. En 1992, Bernhard Boser, Isabelle Guyon y Vladimir Vapnik sugirieron una forma de crear clasificadores no lineales aplicando el truco del kernel a hiperplanos de margen máximo. La encarnación del "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.

SVM lineal

Hiperplano de margen máximo y márgenes para una SVM entrenada con muestras de dos clases. Las muestras en el margen se denominan vectores de soporte.

Recibimos un conjunto de datos de entrenamiento de puntos del formulario

donde son 1 o -1, cada uno indica la clase a la que pertenece el punto . Cada uno es un vector real dimensional . 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 la distancia entre el hiperplano y el punto más cercano de cualquier grupo se maximice.

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 .

Margen duro

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 llama "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 pueden describirse mediante las ecuaciones

(todo lo que esté dentro o por encima de este límite es de una clase, con la etiqueta 1)

y

(todo lo que esté dentro o por debajo de este límite es de la otra clase, con la etiqueta −1).

Geométricamente, la distancia entre estos dos hiperplanos es , por lo que para maximizar la distancia entre los planos queremos minimizar . La distancia se calcula utilizando la ecuación de distancia desde 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

, si ,

o

, si .

Estas restricciones establecen que cada punto de datos debe estar en el lado correcto del margen.

Esto se puede reescribir como

Podemos unir esto para solucionar el problema de optimización:

"Minimizar sujeto a para ".

Los y que resuelven este problema determinan nuestro clasificador, donde está la función de signo .

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. Estos se denominan vectores de soporte .

Margen suave

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

Tenga en cuenta que es el i -ésimo objetivo (es decir, en este caso, 1 o -1), y es la i -ésima salida.

Esta función es cero si se satisface la restricción en (1), en otras palabras, si se encuentra en el lado correcto del margen. Para los datos en el lado incorrecto del margen, el valor de la función es proporcional a la distancia desde el margen.

El objetivo de la optimización es minimizar

donde el parámetro determina la compensación entre aumentar el tamaño del margen y asegurar que se encuentre en el lado correcto del margen. Por lo tanto, para valores suficientemente grandes de , se comportará de manera similar a la SVM de margen rígido, si los datos de entrada son clasificables linealmente, pero aún así aprenderá si una regla de clasificación es viable o no. (Este parámetro también se llama C, por ejemplo, en LIBSVM ).

Clasificación no lineal

Máquina de granos

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 kernel (propuesto originalmente por Aizerman et al.) A hiperplanos de margen máximo. El algoritmo resultante es formalmente similar, excepto que cada producto escalar es reemplazado por una función de núcleo 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 gran dimensión; aunque el clasificador es un hiperplano en el espacio de entidades transformadas, puede ser no lineal en el espacio de entrada original.

Es de 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.

Algunos núcleos comunes incluyen:

  • Polinómica (homogénea) : .
  • Polinomio (no homogénea): .
  • Función de base radial gaussiana : para . A veces parametrizado usando .
  • Tangente hiperbólica : para algunos (no todos) y .

El núcleo está relacionado con la transformada por la ecuación . El valor w también está en el espacio transformado, con . Los productos puntuales con w para la clasificación se pueden calcular de nuevo mediante el truco del núcleo, es decir .

Calcular el clasificador SVM

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

Nos enfocamos en el clasificador de margen blando ya que, como se señaló anteriormente, la elección de un valor suficientemente pequeño para da como resultado el clasificador de margen rígido 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 de sub-gradiente y el descenso de coordenadas.

Primitivo

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

Para cada uno introducimos una variable . Tenga en cuenta que es el número no negativo más pequeño que satisface

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

A esto se le llama el problema primordial .

Doble

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

A esto se le llama el problema dual . Dado que el problema de maximización dual es una función cuadrática del sujeto a restricciones lineales, se puede resolver de manera eficiente mediante algoritmos de programación cuadrática .

Aquí, las variables se definen de manera que

.

Además, exactamente cuándo se encuentra en el lado correcto del margen y cuándo se encuentra en el límite del margen. De ello se deduce que se puede escribir como una combinación lineal de los vectores de soporte.

El desplazamiento`` se puede recuperar encontrando un en el límite del margen y resolviendo

(Tenga en cuenta que desde .)

Truco de kernel

Un ejemplo de entrenamiento de SVM con kernel dado por φ (( a , b )) = ( a , b , a 2 + b 2 )

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. Además, se nos da una función del núcleo que satisface .

Sabemos que el vector de clasificación en el espacio transformado satisface

donde, se obtienen resolviendo el problema de optimización

Los coeficientes se pueden resolver usando programación cuadrática, como antes. Nuevamente, podemos encontrar algún índice tal que , de modo que se encuentre en el límite del margen en el espacio transformado, y luego resolver

Finalmente,

Métodos modernos

Los algoritmos recientes para encontrar el clasificador SVM incluyen descenso de sub-gradiente 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 sub-gradiente 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.

Descenso de sub-gradiente

Los algoritmos de descenso de sub-gradiente para SVM funcionan directamente con la expresión

Tenga en cuenta 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 sub-gradiente de la función . Este enfoque tiene la ventaja de que, para ciertas implementaciones, el número de iteraciones no se escala con el número de puntos de datos.

Descenso coordinado

Coordinar algoritmos de descenso para el trabajo de SVM desde el problema dual

Para cada uno , de forma iterativa, 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). A continuación, 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.

Minimización de riesgos empíricos

La máquina vectorial de soporte de margen blando descrita anteriormente es un ejemplo de un algoritmo de minimización de riesgo empírico (ERM) para la pérdida de 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 nos permite analizar mejor sus propiedades estadísticas.

Minimización de riesgos

En el aprendizaje supervisado, uno se le da un conjunto de ejemplos de entrenamiento con etiquetas , y los deseos de predecir dada . Para hacerlo, uno forma una hipótesis , tal que es una "buena" aproximación de . Una "buena" aproximación se define generalmente con la ayuda de una función de pérdida , que caracteriza lo mal que es como una predicción de . Luego nos gustaría elegir una hipótesis que minimice el riesgo esperado :

En la mayoría de los casos, no conocemos la distribución conjunta de directamente. En estos casos, una estrategia común es elegir la hipótesis que minimice el riesgo empírico:

Bajo ciertos supuestos sobre la secuencia de variables aleatorias (por ejemplo, que son generadas por un proceso finito de Markov), si el conjunto de hipótesis que se está considerando es lo suficientemente pequeño, el minimizador del riesgo empírico se aproximará mucho al minimizador del riesgo esperado. a medida que crece. Este enfoque se denomina minimización de riesgos empíricos o ERM.

Regularización y estabilidad

Para que el problema de minimización tenga una solución bien definida, tenemos que imponer restricciones al conjunto de hipótesis que se están considerando. Si es un espacio normado (como es el caso de SVM), una técnica particularmente efectiva es considerar solo aquellas hipótesis para las cuales . Esto equivale a imponer una penalización por regularización y resolver el nuevo problema de optimización.

Este enfoque se llama regularización de Tikhonov .

De manera más general, puede ser alguna medida de la complejidad de la hipótesis , por lo que se prefieren hipótesis más simples.

SVM y la pérdida de bisagra

Recuerde que el clasificador SVM (margen suave) se elige para minimizar la siguiente expresión:

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

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 las tres mentiras en la elección de la función de pérdida: regularizado mínimos cuadrados asciende a la minimización del riesgo empírico con la pérdida de la plaza , ; La regresión logística emplea la pérdida logarítmica ,

Funciones de destino

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 .

En particular, denotemos condicional al evento que . En el ámbito de la clasificación, tenemos:

Por tanto, el clasificador óptimo es:

Para la pérdida al cuadrado, la función objetivo es la función de expectativa condicional ; Para la pérdida de logística, que es la función logit, . Si bien ambas funciones de destino producen el clasificador correcto , nos brindan más información de la que necesitamos. De hecho, nos dan suficiente información para describir completamente la distribución de .

Por otro lado, se puede verificar que la función objetivo para la pérdida de bisagra sea exactamente . Por lo tanto, en un espacio de hipótesis suficientemente rico, o de manera equivalente, para un núcleo elegido apropiadamente, el clasificador SVM convergerá a la función más simple (en términos de ) que clasifique correctamente los datos. Esto amplía la interpretación geométrica de SVM: para la clasificación lineal, el riesgo empírico se minimiza mediante cualquier función cuyos márgenes se encuentren entre los vectores de soporte, y el más simple de ellos es el clasificador de margen máximo.

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 minimizan simultáneamente el error de clasificación empírica y maximizan el margen geométrico ; de ahí que también se les 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 efectividad 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 solo parámetro . La mejor combinación de y a menudo se selecciona mediante una búsqueda de cuadrícula con secuencias de crecimiento exponencial de y , por ejemplo ,; . Por lo general, cada combinación de opciones de parámetros se verifica mediante validación cruzada y se seleccionan los parámetros con la mejor precisión de validación cruzada. Alternativamente, el trabajo reciente en optimización bayesiana se puede utilizar para seleccionar y , a menudo, requiere la evaluación de muchas menos combinaciones de parámetros que la búsqueda de 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.

Cuestiones

Los posibles inconvenientes de la SVM incluyen los siguientes aspectos:

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

Extensiones

Agrupación de vectores de soporte (SVC)

SVC es un método similar que también se basa en funciones del kernel, pero es apropiado para el aprendizaje no supervisado. Se considera un método fundamental en la ciencia de datos .

SVM multiclase

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

  • 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 de uno frente a todos se realiza mediante una estrategia en el que 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 se calibren para producir puntuaciones comparables ). Para el enfoque uno contra uno, la clasificación se realiza mediante una estrategia de votación de victorias máximas, 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 el la clase con más votos determina la clasificación de la instancia.
  • Gráfico acíclico dirigido SVM (DAGSVM)
  • Códigos de salida de corrección de errores

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 de vectores de soporte transductivos

Las máquinas de vectores de soporte transductivos amplían las SVM en el sentido de que también podrían tratar datos parcialmente etiquetados en aprendizaje semi-supervisado siguiendo los principios de transducción . Aquí, además del conjunto de formación , el alumno también recibe un conjunto

de ejemplos de prueba a clasificar. Formalmente, una máquina de vectores de soporte transductiva se define por el siguiente problema de optimización principal:

Minimizar (en )

sujeto a (para cualquiera y cualquiera )

y

Vladimir N. Vapnik introdujo las máquinas de vectores de soporte transductivos en 1998.

SVM estructurado

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

Regresión

Regresión de vectores de soporte (predicción) con diferentes umbrales ε . A medida que ε aumenta, la predicción se vuelve menos sensible a los errores.

Vladimir N. Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman y Alexander J. Smola propusieron una versión de SVM para regresión en 1996 . Este método se denomina regresión de vectores de soporte (RVS). El modelo producido por la clasificación de vectores de soporte (como se describe 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. De manera análoga, 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 al SVR original significa resolver

minimizar
sujeto a

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 generalmente se agregan a lo anterior para permitir errores y permitir una aproximación en el caso de que el problema anterior no sea factible.

SVM bayesiano

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 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 SVM bayesiano , que permite la aplicación de SVM bayesianas a big data . Florian Wenzel desarrolló dos versiones diferentes, un esquema de inferencia variacional (VI) para la máquina de vectores de soporte de kernel bayesiano (SVM) 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 programación cuadrática (QP) que surge de las SVM, que se basan principalmente en la heurística para dividir el problema en fragmentos más pequeños 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 primarios y duales. En lugar de resolver una secuencia de problemas desglosados, este enfoque resuelve directamente el problema por completo. Para evitar resolver un sistema lineal que involucra la matriz del núcleo grande, a menudo se usa una aproximación de rango bajo a la matriz en el truco del núcleo.

Otro método común es el algoritmo de optimización secuencial mínima (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 almacenamiento de matrices. Este algoritmo es conceptualmente simple, fácil de implementar, generalmente más rápido y tiene mejores propiedades de escala para problemas difíciles de SVM.

El caso especial de las máquinas de vectores de soporte lineal puede resolverse de manera más eficiente mediante el mismo tipo de algoritmos que se utilizan para optimizar su pariente cercano, la regresión logística ; esta clase de algoritmos incluye descenso de sub-gradiente (por ejemplo, PEGASOS) y descenso de coordenadas (por ejemplo, LIBLINEAR). LIBLINEAR tiene algunas propiedades atractivas para el tiempo de formación. Cada iteración de convergencia lleva 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 utilizando el descenso de sub-gradiente (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 datos (estandarización) para mejorar la precisión de la clasificación. Hay algunos métodos de estandarización, como mínimo-máximo, normalización por escala decimal, Z-score. La resta de la media y la división por varianza de cada característica se usa generalmente para SVM.

Ver también

Referencias

Otras lecturas

enlaces externos

  • libsvm , LIBSVM es una biblioteca popular de estudiantes de SVM
  • liblinear es una biblioteca para grandes clasificaciones lineales que incluyen algunas SVM
  • SVM light es una colección de herramientas de software para el aprendizaje y la clasificación usando SVM
  • La demostración en vivo de SVMJS es una demostración de GUI para la implementación de JavaScript de SVM