El modelo interno de las SVMs lineales

Publicado por @titokimbo el Aug. 26, 2019, 2:34 p.m.
Las SVMs son un conjunto de algoritmos de machine learning que se utilizan principalmente para problemas de clasificación y regresión. En este post, haremos una breve introducción al modelo matemático que rige las SVMs lineales y explicaremos cuál es la idea e fondo. Nos centraremos en el problema de clasificación y además, para simplificar, lo reduciremos a dos clases (clasificación binaria). La idea general para entrenar una SVM lineal es hallar, a partir de los datos de entrenamiento (ya clasificados en ambas clases), un hiperplano del espacio de características (*feature space*) que separe ambas clases y que sea óptimo respecto a una cierta métrica. Esto es, que deje a cada lado las muestras de una sóla clase. Está claro que esto puede suponer un problema, pues no siempre los datos serán *linealmente separables*. Esto quiere decir que no siempre existirá un hiperplano que separe las dos clases de puntos. ![Clases linealmente separables][1] ![Clases no linealmente separables][2] Recordemos que un hiperplano en un espacio n-dimensional se expresa mediante la siguiente ecuación ![Fórmula del hiperplano][3] donde ***w*** es el vector de pesos del hiperplano y *b* el término independiente. Hemos hablado anteriormente de la optimalidad del hiperplano. En el caso de las SVMs, queremos que, además de separar las clases, maximice lo que llamaremos *margen geométrico*, que no es más que la mínima distancia (euclídea) entre los puntos de un conjunto y el hiperplano. Para un sólo punto ***x***, este valor viene dado por ![Fórmula del margen geométrico][4] siendo *y* la etiqueta que indica la clase a la que pertenece el punto (1 para una de las clases y -1 para la otra). El resto se reduce a resolver un problema de optimización, que no es más que maximizar el margen geométrico del que hemos hablado a medida que modificamos los parámetros del hiperplano (***w*** y *b*). Obviando una serie de transformaciones matemáticas para simplificar el problema, la formulación general resulta en ![Problema de optimización de la SVM][5] donde *m* es el número de muestras o puntos de los que disponemos. A pesar de la formulación sencilla de este problema, su resolución directa es complicada y, por tanto, se busca transformarlo en otro problema equivalente que sea más fácil de tratar. Para ello se utiliza la técnica de los *multiplicadores de Lagrange*, que utiliza un vector ***alfa*** (denominado vector de multiplicadores de Lagrange). Además, también es necesario introducir la función Lagrangiano, que para este problema es ![Lagrangiano para las SVMs][6] Ahora, pasa a considerarse el llamado *problema lagrangiano primal*, en el que se realiza una minimización respecto a los mismos parámetros que en el caso del problema original pero además se maximiza anteriormente respecto al vector ***alfa***. No sólo eso, sino que la función a optimizar deja de ser la que teníamos anteriormente y pasa a ser el Lagrangiano. Además, las restricciones ahora pasan a ser que todas las componentes del vector de multiplicadores sean no negativas. ![Problema lagrangiano primal para las SVMs][7] Fijémonos en que, como las soluciones al problema anterior son extremos del Lagrangiano, las derivadas respecto a las componentes de ***w*** y respecto de ***b*** serán 0. Con estas restricciones, podemos obtener una expresión de ***w*** en función de ***alfa*** ![w como función de alfa][8] El último paso es aplicar el principio de dualidad para transformar el problema anterior en el denominado problema dual de Woflfe y que, a pesar de su apariencia, es mucho más tratable que el original. ![Problema dual de Wolfe para las SVMs][9] El último paso para tener una SVM completamente funcional consiste en resolver el problema anterior y hallar los multiplicadores pues, como hemos visto antes, esto nos permite reconstruir el vector ***w*** y esto, a su vez, nos permite calcular ***b*** ![Cálculo de b ][10] Obsérvese que, aunque se podría calcular ***b*** tan solo con una de las muestras, tomar la media proporciona una solución que es más estable numéricamente y reduce así errores en el cálculo. A partir de este punto, la solución del problema anterior se puede hacer de diversas maneras, por ejemplo tratando el problema como un problema de optimización cuadrático convexo o resolviendo analíticamente el problema para dos multiplicadores y aplicando el Teorema de Osuna (esto es lo que conduce al algoritmo de SMO u Optimización Mínima Secuencial, que es probablemente la forma más eficiente y rápida de entrenar una SVM). Para más detalles, podéis dirigiros a [mi publicación][11] en LinkedIn sobre SVMs, en la que trato todo lo anterior con algo más de detalle y también una posible implementación y algunas notas sobre la eficiencia de las SVMs y las técnicas que se utilizan para mejorarla. También os podéis dirigir al libro SVMs Succintly de Alexandre Kowalczyk , que está disponible online de forma gratuita y es una excelente referencia para aprender sobre estos algoritmos. [1]: https://upload.wikimedia.org/wikipedia/commons/d/d9/VC1.svg [2]: https://upload.wikimedia.org/wikipedia/commons/3/37/VC4.svg [3]: https://i.imgur.com/sN8C1qh.png [4]: https://i.imgur.com/xCVvlk2.png [5]: https://i.imgur.com/DsWACXb.png [6]: https://i.imgur.com/aF7I5cs.png [7]: https://i.imgur.com/qIWX58M.png [8]: https://i.imgur.com/h9IdMEp.png [9]: https://i.imgur.com/UpN8vDE.png [10]:https://i.imgur.com/S0zsjwJ.png [11]: https://www.linkedin.com/posts/eduardo-rivero-rodr%C3%ADguez-34950b177_introducci%C3%B3n-a-las-svms-activity-6527453181960605696-jUIa