Soporte Vector Machine, 30 líneas

En este artículo, le mostraré cómo escribir su máquina de vectores de soporte muy simple sin scikit-learn u otras bibliotecas con una implementación lista para usar en solo 30 líneas en Python. Si desea comprender el algoritmo SMO, pero le parece demasiado complicado, este artículo puede resultarle útil.



Es imposible explicar qué es la máquina de vectores de soporte de Matrix ... Tienes que verla tú mismo.





Habiendo aprendido que Habré tiene la capacidad de insertar elementos multimedia, creé una pequeña demostración (si de repente no funciona, aún puedes probar suerte con la versión en github [1] ). Colocar en un plano (espacio de dos entidades $$$X$ y $$$Y$ ) varios puntos rojos y azules (este es nuestro conjunto de datos) y la máquina realizará la clasificación (se pinta cada punto del fondo según donde se clasifique la solicitud correspondiente). Mueve los puntos, cambia el kernel (te aconsejo que pruebes Radial Basis Functions) y la dureza del borde (constante $$$C$ ). Mis disculpas por el terrible código en JS: escribí en él solo unas pocas veces en mi vida, para comprender el algoritmo, use el código Python más adelante en el artículo.

Contenido

• , , , . , — . , — [2] [3], , , .
• « SMO» SMO , , . , , SMO, .
• , «» Python .
• « sklearn.svc.svm» — 2D confusion matrix MNIST.
• «» - .

Support Vector Machine es un método de aprendizaje automático (aprendizaje supervisado) para la resolución de problemas de clasificación, regresión, detección de anomalías, etc. Lo consideraremos usando el ejemplo de un problema de clasificación binaria. Nuestro ejemplo de formación es un conjunto de vectores de características $$$\boldsymbol{x}_i$ clasificado en una de dos clases $$$y_i = \pm 1$ ... Solicitud de clasificación - Vector $$$\boldsymbol{x}$ al cual debemos asignar la clase $$$+1$ o $$$-1$ ...



En el caso más simple, las clases de la muestra de entrenamiento se pueden dividir dibujando solo una línea recta como en la figura (para un mayor número de características, esto sería un hiperplano). Ahora, cuando llega una solicitud para clasificar algún punto $$$\boldsymbol{x}$ , es razonable colocarlo en la clase de qué lado estará.



¿Cómo elegir la mejor línea recta? Intuitivamente, quiero que la línea recta pase por el medio entre las clases. Para hacer esto, escribe la ecuación de la línea recta como $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ y escalar los parámetros para que el punto del conjunto de datos más cercano a la línea recta satisfaga $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (más o menos, según la clase): estos puntos se denominan vectores de soporte .



En este caso, la distancia entre los puntos límite de las clases es $$$2/|\boldsymbol{w}|$ ... Obviamente, queremos maximizar este valor para separar las clases lo mejor posible. Esto último equivale a minimizar $$$\frac{1}{2} |\boldsymbol{w}|^2$ , todo el problema de optimización está escrito

$$

$$\begin{aligned} &\min \frac{1}{2} |\boldsymbol{w}|^2 \\ \text{subject to: } &y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0. \end{aligned}$$

Si lo resuelve, entonces la clasificación a pedido. $$$\boldsymbol{x}$ producido así

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}\left(\boldsymbol{x} \cdot \boldsymbol{w} + b\right).$$

Esta es la máquina de vectores de soporte más simple.



¿Y qué hacer en el caso de que puntos de diferentes clases se penetren mutuamente como en la figura?



Ya no podemos resolver el problema de optimización anterior, no hay parámetros que satisfagan esas condiciones. Entonces es posible permitir que los puntos violen el límite por la cantidad $$$\xi_i \geq 0$ , pero también es deseable que tales infractores sean el menor número posible. Esto se puede lograr modificando la función objetivo con un término adicional (regularización $$$L_1$ ):

$$

$$\begin{aligned} &\min\left( \frac{1}{2} |\boldsymbol{w}|^2 + C \sum_i \xi_i \right)\\ \text{subject to: }&\xi_i + y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0,\\ &\xi_i \geq 0, \end{aligned}$$

y el procedimiento de clasificación continuará como antes. Aquí el hiperparámetro $$$C$ es responsable de la fuerza de la regularización, es decir, determina cuán estrictamente requerimos puntos para respetar el límite: cuanto más $$$C$ - cuanto más $$$\xi_i$ desaparecerá y menos puntos violarán el límite. Los vectores de soporte en este caso son los puntos para los cuales $$$\xi_i > 0$ ...



Pero, ¿qué pasa si el conjunto de entrenamiento se parece al logotipo de The Who y los puntos nunca pueden separarse con una línea recta?



Aquí nos ayudará una técnica ingeniosa: el truco del kernel [4] . Sin embargo, para aplicarlo hay que pasar al llamado problema de Lagrange dual (o dual ). Se puede encontrar una descripción detallada del mismo en Wikipedia [5] o en la sexta conferencia del curso [3] . Las variables en las que se resuelve el nuevo problema se denominan multiplicadores duales o de Lagrange.... El problema dual es a menudo más simple que el original y tiene buenas propiedades adicionales, por ejemplo, es cóncavo incluso si el problema original no es convexo. Si bien su solución no siempre coincide con la solución del problema original (ruptura de dualidad), existen una serie de teoremas que, en determinadas condiciones, garantizan dicha coincidencia (dualidad fuerte). Y este es solo nuestro caso, por lo que puede pasar con seguridad al problema dual

$$

$$\begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j (\boldsymbol{x}_i \cdot \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

Dónde $$$\lambda_i$ - variables duales. Después de resolver el problema de maximización, también es necesario calcular el parámetro $$$b$ , que no está incluido en el problema dual, pero es necesario para el clasificador

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}\left[y_k - \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}_k)\right].$$

El clasificador puede (y debe) reescribirse en términos de variables duales

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}) + b.$$

¿Cuál es la ventaja de esta grabación? Tenga en cuenta que todos los vectores del conjunto de formación se incluyen aquí exclusivamente en forma de productos punto $$$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... Primero puede mapear puntos a una superficie en un espacio de mayor dimensión y solo luego calcular el producto escalar de las imágenes en el nuevo espacio. Por qué hacer esto se puede ver en la figura.



Si el mapeo es exitoso, las imágenes de los puntos están separadas por un hiperplano. De hecho, todo es aún mejor: no hay necesidad de mostrar, porque solo nos interesa el producto escalar y no las coordenadas específicas de los puntos. Entonces, todo el procedimiento se puede emular reemplazando el producto escalar con la función $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , que se llama núcleo . Por supuesto, no todas las funciones pueden ser un kernel; debe existir al menos hipotéticamente un mapeo $$$\varphi$ tal que $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... Las condiciones necesarias están determinadas por el teorema de Mercer [6] . La implementación de Python representará lineal ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), polinomio ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) el núcleo y el núcleo de las funciones de base radial ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ). Como puede ver en los ejemplos, los núcleos pueden introducir sus hiperparámetros específicos en el algoritmo, lo que también afectará su funcionamiento.



Es posible que hayas visto un video donde se explica la acción de la gravedad usando el ejemplo de una película de goma estirada en forma de embudo [7] . Esto funciona, ya que el movimiento de un punto a lo largo de una superficie curva en un espacio de alta dimensión es equivalente al movimiento de su imagen en un espacio de menor dimensión, si se proporciona una métrica no trivial. De hecho, el núcleo dobla el espacio.

Algoritmo SMO

Entonces, estamos en la meta, queda por resolver el problema dual planteado en el apartado anterior

$$

$$\def\M{{\color{red}M}} \def\L{{\color{blue}L}} \begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(\boldsymbol{x}_i; \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

luego encuentra el parámetro

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}[y_k - \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}_k)], \tag{1}$$

y el clasificador tomará la siguiente forma

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}) + b. \tag{2}$$

El algoritmo SMO (Optimización mínima secuencial, [8] ) para resolver el problema dual es el siguiente. En el ciclo, utilizando una heurística compleja ( [9] ), se selecciona un par de variables duales $$$\lambda_\M$ y $$$\lambda_\L$ , y luego la función objetivo se minimiza sobre ellos, con la condición de la constancia de la suma $$$y_\M\lambda_\M + y_\L\lambda_\L$ y restricciones $$$0 \leq \lambda_\M \leq C$ , $$$0 \leq \lambda_\L \leq C$ (ajuste de la dureza del borde). La condición de suma almacena la suma de todos $$$y_i\lambda_i$ sin cambios (después de todo, no tocamos el resto de las lambdas). El algoritmo se detiene cuando detecta una observancia suficientemente buena de las llamadas condiciones KKT (Karush-Kuna-Tucker [10] ).



Voy a hacer algunas simplificaciones.

• Abandonaré las complejas heurísticas de la selección de índices (esto se hace en el curso de la Universidad de Stanford [11] ), iteraré sobre un índice y seleccionaré el segundo al azar.
• Me negaré a verificar el PCC y realizaré un número predeterminado de iteraciones por adelantado.
• En el procedimiento de optimización en sí, en contraste con el trabajo clásico [9] o el enfoque de Stanford [11] , usaré la ecuación vectorial en línea recta. Esto simplificará enormemente los cálculos (compare el volumen de [12] y [13] ).

Ahora para los detalles. La información de la muestra de formación se puede escribir en forma de matriz

$$

$$\boldsymbol{K} = \begin{pmatrix} y_1 y_1 K(\boldsymbol{x}_1; \boldsymbol{x}_1) & y_1 y_2 K(\boldsymbol{x}_1; \boldsymbol{x}_2) & \dots & y_1 y_N K(\boldsymbol{x}_1; \boldsymbol{x}_N) \\ y_2 y_1 K(\boldsymbol{x}_2; \boldsymbol{x}_1) & y_2 y_2 K(\boldsymbol{x}_2; \boldsymbol{x}_2) & \dots & y_2 y_N K(\boldsymbol{x}_2; \boldsymbol{x}_N) \\ \cdots & \cdots & \cdots & \cdots \\ y_N y_1 K(\boldsymbol{x}_N; \boldsymbol{x}_1) & y_N y_2 K(\boldsymbol{x}_N; \boldsymbol{x}_2) & \dots & y_N y_N K(\boldsymbol{x}_N; \boldsymbol{x}_N) \\ \end{pmatrix}. \tag{3}$$

En lo que sigue, usaré la notación con dos índices ( $$$\boldsymbol{K}_{i,j}$ ) para hacer referencia a un elemento de la matriz y con un índice ( $$$\boldsymbol{K}_{k}$ ) para denotar el vector columna de la matriz. Recopile las variables duales en un vector de columna $$$\boldsymbol{\lambda}$ ... Estamos interesados ​​en

$$

$$\max_{\boldsymbol{\lambda}} \underbrace{ \sum_{i=1}^n \lambda_i - \frac12 \boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda} }_{\mathscr{L}}.$$

Supongamos que, en la iteración actual, queremos maximizar la función objetivo mediante índices $$$\L$ y $$$\M$ ... Tomaremos derivados, por lo que conviene seleccionar los términos que contienen los índices $$$\L$ y $$$\M$ ... Es fácil de hacer en la parte con la cantidad. $$$\lambda_i$ , pero la forma cuadrática requerirá varias transformaciones.



Al calcular $$$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ la suma se realiza sobre dos índices, sea $$$i$ y $$$j$ ... Resalte los pares de índices que contienen $$$\L$ o $$$\M$ ...





Reescribamos el problema combinando todo lo que no contiene $$$\lambda_\L$ o $$$\lambda_\M$ ... Para facilitar el seguimiento de los índices, preste atención a $$$\boldsymbol{K}$ en la imagen.

$$

$$\begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{}\atop\text{ }} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned}$$

Dónde $$$\text{const}$ denota términos independientes de $$$\lambda_\L$ o $$$\lambda_\M$ ... En la última línea, usé la notación

$$

$$\begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align}$$

tenga en cuenta que $$$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ no depende de $$$\lambda_\L$ ni de $$$\lambda_\M$

$$

$$\boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0.$$

El kernel es simétrico, por lo tanto $$$\boldsymbol{Q}^T = \boldsymbol{Q}$ y tu puedes escribir

$$

$$\mathscr{L} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0 - \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 - \frac{1}{2} \boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}$$

Queremos realizar la maximización para que $$$y_\L\lambda_\L + y_\M\lambda_\M$ permaneció constante. Para ello, los nuevos valores deben estar en línea recta.

$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}.$$

Es fácil asegurarse de que para cualquier $$$t$

$$

$$y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L.$$

En este caso, debemos maximizar

$$

$$\mathscr{L}(t) = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}(t) - \frac12 \boldsymbol{v}^{\,T}(t) \, \boldsymbol{Q} \, \boldsymbol{v}(t) + \text{const},$$

que es fácil de hacer tomando la derivada

$$

$$\begin{align} \frac{d \mathscr{L}(t)}{d t} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \frac{d \boldsymbol{v}}{dt} &- \frac12 \left(\frac{d(\boldsymbol{v}^{\,T} \, \boldsymbol{Q} \, \boldsymbol{v})}{d \boldsymbol{v}}\right)^T \frac{d\boldsymbol{v}}{d t} =\\ &= \boldsymbol{k}_0^T \boldsymbol{u} + \underbrace{\boldsymbol{v}_0^T \boldsymbol{Q}^T \boldsymbol{u} - \boldsymbol{v}^T \boldsymbol{Q}^T \boldsymbol{u}}_{(\boldsymbol{v}_0^T - \boldsymbol{v}^T)\boldsymbol{Q} \boldsymbol{u}} = \boldsymbol{k}_0^T \boldsymbol{u} - t \boldsymbol{u}^T \boldsymbol{Q} \boldsymbol{u}. \end{align}$$

Igualando la derivada a cero, obtenemos

$$

$$t_* = \frac{\boldsymbol{k}^T_0 \boldsymbol{u}}{\boldsymbol{u}^{\,T} \boldsymbol{Q} \boldsymbol{u}}. \tag{5}$$

Y una cosa más: quizás trepemos más de lo necesario y nos encontremos fuera de la plaza como en la imagen. Entonces necesitas dar un paso atrás y regresar a su borde.

$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}.$$

Esto completa la iteración y selecciona nuevos índices.

Implementación

El diagrama esquemático del entrenamiento de una máquina de vectores de soporte simplificada se puede escribir como







Echemos un vistazo al código en un lenguaje de programación real. Si no le gusta el código de los artículos, puede estudiarlo en github [14] .







Al crear un objeto de la clase SVM, puede especificar hiperparámetros. El entrenamiento se realiza llamando a la función de ajuste, las clases deben especificarse como $$$0$ y $$$1$ (convertido internamente a $$$-1$ y $$$+1$ , hecho para una mayor compatibilidad con sklearn), la dimensión del vector de características se permite arbitrariamente. La función de predicción se utiliza para la clasificación.

Comparación con sklearn.svm.SVC

No es que esta comparación tenga mucho sentido, porque estamos hablando de un algoritmo extremadamente simplificado, desarrollado únicamente con el propósito de enseñar a los estudiantes, pero aún así. Para probar (y ver cómo usarlo todo), puede hacer lo siguiente (este código también está disponible en github [14] ).





Después del lanzamiento, se generarán imágenes, pero como el algoritmo es aleatorio, serán ligeramente diferentes para cada lanzamiento. Aquí hay un ejemplo de cómo funciona el algoritmo simplificado (de izquierda a derecha: núcleos lineales, polinomiales y rbf)



Y este es el resultado de la versión industrial de la máquina de vectores de soporte.



Si la dimensión $$$2$ parece demasiado pequeño, aún puede probar en MNIST





Para MNIST, probé varios pares aleatorios de clases (el algoritmo simplificado solo admite clasificación binaria), pero no encontré ninguna diferencia en el trabajo del algoritmo simplificado y sklearn. La siguiente matriz de confusión da una idea de la calidad.

Conclusión

Gracias a todos los que leyeron hasta el final. En este artículo, analizamos una implementación tutorial simplificada de una máquina de vectores de soporte. Por supuesto, no puede competir con un diseño industrial, pero debido a la extrema simplicidad y el código compacto de Python, así como al hecho de que se han conservado todas las ideas básicas de SMO, esta versión de SVM bien puede ocupar su lugar en el salón de clases. Cabe señalar que el algoritmo es más simple no solo que un algoritmo muy complicado [9] , sino incluso su versión simplificada de la Universidad de Stanford [11] . Después de todo, una máquina de vectores de soporte en 30 líneas es hermosa.

Lista de referencias

1. https://fbeilstein.github.io/simplest_smo_ever/
2. página en http://www.machinelearning.ru
3. "Inicios del aprendizaje automático", KAU
4. https://en.wikipedia.org/wiki/Kernel_method
5. https://en.wikipedia.org/wiki/Duality_(optimization)
6. http://www.machinelearning.ru
7. https://www.youtube.com/watch?v=MTY1Kje0yLg
8. https://en.wikipedia.org/wiki/Sequential_minimal_optimization
9. Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
10. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
11. http://cs229.stanford.edu/materials/smo.pdf
12. https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
13. http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
14. https://github.com/fbeilstein/simplest_smo_ever