Máquinas de vectores soporte

La máquina de vectores de soporte ( SVM, support vector machine ) es un conjunto de algoritmos de aprendizaje supervisado similares que se utilizan para problemas de clasificación y análisis de regresión . Pertenece a la familia de clasificadores lineales y también puede considerarse como un caso especial de regularización de Tikhonov . Una propiedad especial de la máquina de vectores de soporte es que el error de clasificación empírico disminuye continuamente y la brecha aumenta, razón por la cual el método también se conoce como método clasificador de brecha máxima .

La idea principal del método es traducir los vectores originales a un espacio de mayor dimensión y buscar un hiperplano de separación con la brecha más grande en este espacio. Se construyen dos hiperplanos paralelos a ambos lados del hiperplano que separa las clases. El hiperplano de separación será el hiperplano que crea la mayor distancia a dos hiperplanos paralelos. El algoritmo se basa en la suposición de que cuanto mayor sea la diferencia o la distancia entre estos hiperplanos paralelos, menor será el error promedio del clasificador.

Planteamiento del problema

A menudo, en los algoritmos de aprendizaje automático, se hace necesario clasificar los datos. Cada objeto de datos se representa como un vector (punto) en un espacio dimensional (un conjunto ordenado de números). Cada uno de estos puntos pertenece a una sola de las dos clases. La pregunta es si los puntos pueden estar separados por un hiperplano de dimensión ( -1). Este es un caso típico de separabilidad lineal . Puede haber muchos hiperplanos deseados, por lo que se cree que maximizar la brecha entre clases contribuye a una clasificación más segura. Es decir, ¿es posible encontrar un hiperplano tal que la distancia desde él hasta el punto más cercano sea máxima? Esto es equivalente [1] al hecho de que la suma de las distancias al hiperplano desde dos puntos más cercanos a él, que se encuentran en lados opuestos de él, es máxima. Si tal hiperplano existe, se denomina hiperplano de separación óptimo , y su clasificador lineal correspondiente se denomina clasificador de separación óptimo . $pags$ $pags$ $pags$

Descripción formal del problema

Creemos que los puntos se ven así:

\{({\mathbf {x}}_{1},c_{1}),({\mathbf {x}}_{2},c_{2}),\ldots,({\mathbf {x} }_{n},c_{n})\}

donde toma el valor 1 o −1, según la clase a la que pertenezca el punto . Cada uno es un vector real -dimensional , normalmente normalizado por o . Si los puntos no están normalizados, entonces un punto con grandes desviaciones de las coordenadas del punto promedio afectará demasiado al clasificador. Podemos pensar en esto como una muestra de entrenamiento en la que a cada elemento ya se le asigna una clase a la que pertenece. Queremos que el algoritmo de la máquina de vectores de soporte los clasifique de la misma manera. Para hacer esto, construimos un hiperplano de separación, que se parece a: $c_{yo}$ ${\mathbf {x}}_{i}$ ${\mathbf {x}}_{i}$ $pags$ $[0, 1]$ $[-1,1]$

{\mathbf {w}}\cdot {\mathbf {x}}-b=0.

El vector es perpendicular al hiperplano de separación. El parámetro es igual en valor absoluto a la distancia del hiperplano al origen. Si el parámetro b es cero, el hiperplano pasa por el origen, lo que limita la solución. $\mathbf {w}$ ${\frac{b}{\|{\mathbf {w}}\|}}$

Como estamos interesados en la separación óptima, estamos interesados en los vectores de soporte y los hiperplanos que son paralelos al óptimo y más cercanos a los vectores de soporte de las dos clases. Se puede demostrar que estos hiperplanos paralelos se pueden describir mediante las siguientes ecuaciones (hasta la normalización).

{\mathbf {w}}\cdot {\mathbf {x}}-b=1,

{\mathbf {w}}\cdot {\mathbf {x}}-b=-1.

Si la muestra de entrenamiento es linealmente separable , entonces podemos elegir los hiperplanos para que ningún punto de la muestra de entrenamiento se encuentre entre ellos y luego maximizar la distancia entre los hiperplanos. El ancho de la franja entre ellos es fácil de encontrar a partir de consideraciones geométricas, es igual a [2] , por lo que nuestra tarea es minimizar . Para excluir todos los puntos de la tira, debemos asegurarnos por todo lo que ${\frac{2}{\|{\mathbf {w}}\|}}$ $\|{\mathbf{w}}\|$ $i$

\left[{\begin{matriz}{lcr}{\mathbf {w}}\cdot {\mathbf {x_{i}}}-b\geq 1,\ c_{i}=1{\mathrm {}} \\{\mathbf {w}}\cdot {\mathbf {x_{i}}}-b\leq -1,\ c_{i}=-1{\mathrm {}}\\\end{matriz}} \Correcto.

Esto también se puede escribir como:

c_{i}({\mathbf {w}}\cdot {\mathbf {x_{i}}}-b)\geq 1,\quad 1\leq i\leq n.\qquad \qquad (1)

El caso de la separabilidad lineal

El problema de construir un hiperplano de separación óptimo se reduce a minimizar , bajo la condición (1). Este es un problema de optimización cuadrática que se parece a: $\|{\mathbf{w}}\|$

\left\{{\begin{matriz}{lcr}\|{\mathbf {w}}\|^{2}\to \min \\c_{i}({\mathbf {w}}\cdot {\ mathbf {x_{i}}}-b)\geq 1,\quad 1\leq i\leq n.\\\end{array}}\right.

Por el teorema de Kuhn-Tucker, este problema es equivalente al problema dual de encontrar el punto de silla de la función de Lagrange

\left\{{\begin{matriz}{lcr}{\mathbf {L}}({\mathbf {w}},{\mathbf {b}};{\mathbf {\lambda }})={\frac {1}{2}}\|{\mathbf {w}}\|^{2}-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}( c_{i}(({\mathbf {w}}\cdot {\mathbf {x_{i}}})-b)-1)\to \min_{{w,b}}\max_{{\ lambda ))\\{\mathbf {\lambda _{i))}\geq 0,\quad 1\leq i\leq n\\\end{matriz))\right.(2)

donde es el vector de variables duales. ${\mathbf {\lambda }}=({\mathbf {\lambda _{1}}},\ldots,{\mathbf {\lambda _{n}}})$

Reducimos este problema a un problema de programación cuadrática equivalente que contiene solo variables duales:

\left\{{\begin{matriz}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum_{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\sum_{{i=1}}^{n}\sum_{{j=1}}^{n}{\ mathbf {\lambda _{i))}{\mathbf {\lambda _{j))}c_{i}c_{j}({\mathbf {x_{i))}\cdot {\mathbf {x_{j )))))\to \min_{{\lambda}}\\{\mathbf {\lambda_{i}}}\geq 0,\quad 1\leq i\leq n\\\sum_{{ i =1))^{n}{\mathbf {\lambda _{i))}c_{i}=0\\\end{matriz))\right.(3)

Supongamos que hemos resuelto este problema, entonces se puede encontrar mediante las fórmulas: $\mathbf {w}$ ${\ matemáticas {b}}$

{\mathbf {w}}=\sum_{{i=1}}^{n}{\mathbf {\lambda_{i}}}c_{i}{\mathbf {x_{i}}}

{\mathbf {b}}={\mathbf {w}}\cdot {\mathbf {x_{i}}}-c_{i},\quad {\mathbf \lambda }_{i}>0

Como resultado, el algoritmo de clasificación se puede escribir como:

a(x)=signo\left(\sum_{{i=1}}^{n}{\mathbf {\lambda_{i}}}c_{i}{\mathbf {x_{i}}}\ cdot {\mathbf {x}}-b\right)(4)

En este caso, la suma no se realiza sobre toda la muestra, sino solo sobre los vectores de soporte para los que . ${\mathbf {\lambda _{i))}\neq 0$

El caso de la inseparabilidad lineal

Para que el algoritmo funcione si las clases son linealmente inseparables, permitamos que cometa errores en el conjunto de entrenamiento. Introduzcamos un conjunto de variables adicionales que caracterizan la magnitud del error en los objetos . Tomemos (2) como punto de partida, suavicemos las restricciones de desigualdad y también introduzcamos una penalización por el error total en el funcional minimizado: $\xi _{i}\geq 0$ ${\mathbf {x}}_{i},\quad 1\leq i\leq n$

\left\{{\begin{matriz}{lcr}{\frac {1}{2}}\|{\mathbf {w}}\|^{2}+C\sum _{{i=1}} ^{n}\xi _{i}\to \min _{{w,b,\xi _{i}}}\\c_{i}({\mathbf {w}}\cdot {\mathbf {x_ {i}}}-b)\geq 1-\xi _{i},\quad 1\leq i\leq n\\\xi _{i}\geq 0,\quad 1\leq i\leq n\ \\end{matriz}}\derecha.

El coeficiente es un parámetro de configuración del método que le permite ajustar la proporción entre maximizar el ancho de la tira de separación y minimizar el error total. $C$

De manera similar, según el teorema de Kuhn-Tucker , reducimos el problema a encontrar el punto de silla de la función de Lagrange :

\left\{{\begin{matriz}{lcr}\mathbf {L} (\mathbf {w} ,\mathbf {b} ,\mathbf {\xi } ;\mathbf {\lambda } ,\mathbf {\eta})={\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum_{i=1}^{n}\mathbf {\lambda_{i )) (c_{i}((\mathbf {w} \cdot \mathbf {x_{i)) )-b)-1)-\sum _{i=1}^{n}\mathbf {\xi _ {i)) (\mathbf {\lambda_{i)) +\mathbf {\eta_{i)) -C)\a \min_{w,b,\xi}\max_{\lambda,\ eta }\\\mathbf {\xi _{i)) \geq 0,\mathbf {\lambda _{i)) \geq 0,\mathbf {\eta _{i)) \geq 0,\quad 1\ leq i\leq n\\\left[{\begin{array}{lcr}\mathbf {\lambda _{i))=0\\c_{i}(\mathbf {w} \cdot \mathbf {x_{ i}} -b)=1-\xi _{i},\\\end{array}}\right.\quad 1\leq i\leq n\\\left[{\begin{array}{lcr} \mathbf {\eta _{i)) =0\\\mathbf {\xi _{i)) =0,\\\end{matriz))\right.\quad 1\leq i\leq n\end{ matriz}}\derecha.

Por analogía, reducimos este problema a uno equivalente:

\left\{{\begin{matriz}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum_{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\sum_{{i=1}}^{n}\sum_{{j=1}}^{n}{\ mathbf {\lambda _{i))}{\mathbf {\lambda _{j))}c_{i}c_{j}({\mathbf {x_{i))}\cdot {\mathbf {x_{j }}})\to \min_{{\lambda}}\\0\leq {\mathbf {\lambda_{i}}}\leq {\mathbf {C}},\quad 1\leq i\leq n\\\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}c_{i}=0\\\end{matriz}}\right.

En la práctica, para construir una máquina de vectores de soporte, es este problema el que se resuelve, y no (3), ya que generalmente no es posible garantizar la separabilidad lineal de los puntos en dos clases. Esta variante del algoritmo se denomina algoritmo SVM de margen suave, mientras que en el caso linealmente separable se habla de margen duro (SVM de margen duro).

Para el algoritmo de clasificación, se conserva la fórmula (4), con la única diferencia de que ahora no solo los objetos de referencia, sino también los objetos violatorios tienen valores distintos de cero. En cierto sentido, esto es un inconveniente, ya que los picos de ruido son a menudo los infractores, y la regla de decisión basada en ellos, de hecho, se basa en el ruido. ${\mathbf {\lambda _{i))}$

La constante C suele elegirse según el criterio de un control deslizante. Este es un método laborioso, ya que el problema debe resolverse nuevamente para cada valor de C.

Si hay motivos para creer que la muestra se puede separar casi linealmente y que solo los objetos atípicos se clasifican incorrectamente, se puede aplicar el filtrado de atípicos. Primero, el problema se resuelve para algo de C y se elimina de la muestra una pequeña fracción de objetos con el mayor valor de error . Después de eso, el problema se resuelve de nuevo en una muestra truncada. Puede ser necesario hacer varias de estas iteraciones hasta que los objetos restantes sean linealmente separables. ${\mathbf {\xi _{i))}$

Núcleos

El algoritmo para construir el hiperplano de separación óptimo, propuesto en 1963 por Vladimir Vapnik y Aleksey Chervonenkis , es un algoritmo de clasificación lineal. Sin embargo, en 1992, Bernhard Boser, Isabelle Guyon y Vapnik propusieron un método para crear un clasificador no lineal basado en la transición de productos escalares a núcleos arbitrarios, el llamado truco del núcleo (propuesto por primera vez por M. A. Aizerman , E. M. Braverman y L. I. Rozonoer por el método de las funciones potenciales), que permite construir separadores no lineales. El algoritmo resultante es muy similar al algoritmo de clasificación lineal, con la única diferencia de que cada producto escalar en las fórmulas anteriores se reemplaza por una función kernel no lineal (producto escalar en un espacio con una dimensión mayor). Es posible que ya exista un hiperplano de separación óptimo en este espacio. Dado que la dimensión del espacio resultante puede ser mayor que la dimensión del original, la transformación que iguala los productos escalares será no lineal, lo que significa que la función correspondiente al hiperplano de separación óptimo en el espacio original también será no lineal.

Si el espacio original tiene una dimensión suficientemente alta, entonces la muestra puede ser linealmente separable.

Los núcleos más comunes:

Polinomio (homogéneo): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}})^{d}$
Polinomio (heterogéneo): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}}+1)^{d}$
Función de base radial : , para $k({\mathbf {x)),{\mathbf {x}}')=\exp(-\gamma \|{\mathbf {x}}-{\mathbf {x'}}\|^{2} )$ $\gamma > 0$
Función de base gaussiana radial: $k({\mathbf {x)),{\mathbf {x}}')=\exp \left(-{\frac {\|{\mathbf {x}}-{\mathbf {x'}}\| ^{2}}{2\sigma ^{2}}}\derecha)$
Sigmoide : , para casi todos y $k({\mathbf {x)),{\mathbf {x}}')=\tanh(\kappa {\mathbf {x}}\cdot {\mathbf {x'}}+c)$ $\kappa >0$ $c<0$

Véase también

Dimensión Vapnik-Chervonenkis

Notas

↑ Vyugin, 2013 , pág. 86-90.
↑ KV Vorontsov. Conferencias sobre máquinas de vectores de soporte Archivado el 27 de septiembre de 2007 en Wayback Machine .

Literatura

Vladímir Vyuguin. Fundamentos matemáticos de la teoría del aprendizaje automático y la previsión. — MTsMNO, 2013. — 390 p. - ISBN 978-5-4439-0111-4 .
Nello Cristianini, John Shawe-Taylor. Una introducción a las máquinas de vectores de soporte y otros métodos de aprendizaje basados en el kernel . - Prensa de la Universidad de Cambridge, 2000. - ISBN 978-1-139-64363-4 .
Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. Una introducción suave a las máquinas de vectores de soporte en biomedicina: teoría y métodos. - World Scientific, 2011. - ISBN 978-981-4324-38-0 .
Aleksey Nefedov. Máquinas de vectores de soporte: un tutorial simple . — 2016.

Enlaces

procesamiento de datos. 10. Clase magistral: Métodos de clasificación y previsión. Máquina de vectores de soporte // Intuit.ru
Yuri Lifshits. Máquina de vectores de soporte (diapositivas) - Lección 7 del curso Algorithms for the Web

Tipos de redes neuronales artificiales

Red feed-forward ( Red de funciones de base radial )
Perceptrón de una sola capa
Perceptrón multicapa ( Rosenblatt • Rumelhart )
Red Hopfield
cadena de Markov
máquina de Boltzmann
Máquina Boltzmann limitada
Codificador automático ( Codificador automático de eliminación de ruido • Codificador automático disperso [en • Codificador automático variacional )
Red profunda de confianza
Red neuronal convolucional
Red neuronal convolucional profunda
Red neuronal de despliegue
Red gráfica inversa convolucional profunda
Red adversaria generativa
Red neuronal recurrente
Redes Neuronales Recursivas
memoria a corto plazo
Bloque recurrente controlado
Máquinas neurales de Turing
Red bidireccional (Red neuronal recurrente bidireccional • Red bidireccional con memoria a corto plazo larga • Neuronas recurrentes controladas bidireccionales )
Red residual profunda
Red de eco neuronal
Método de aprendizaje extremo
Método de estados inestables
Máquinas de vectores soporte
Red Kohonen
Mapa autoorganizado de Kohonen
Red neuronal de la cápsula
Memoria asociativa en redes neuronales

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG