Principios básicos de las máquinas de vectores de soporte (SVM)
Una introducción popular a las máquinas de vectores de soporte (comprensión de los tres niveles de SVM)
Regresión lineal
Dado un conjunto de datos, lineal intentos de regresión Aprenda un modelo lineal para generar etiquetas correctas tanto como sea posible.
Si queremos usar un algoritmo de regresión lineal para resolver un problema de clasificación (para clasificación, el valor de y es 0 o 1), pero si usamos regresión lineal, entonces el valor de salida del hipotético La función puede ser mucho mayor que 1 o mucho mayor que 0, incluso si todas las muestras de entrenamiento están marcadas como 0 o 1, si el valor obtenido por el algoritmo es mucho mayor que 1 o mucho mayor que 0, por lo tanto, el algoritmo que estudiaremos El siguiente se llama algoritmo de regresión logística. La esencia de este algoritmo es que su valor de salida siempre está entre 0 y 1.
Entonces, la regresión logística es un algoritmo de clasificación y el valor de salida de este algoritmo siempre está entre 0 y 1.
Veamos primero el LR de dos categorías. Específicamente, usamos la función sigmoidea para asignar el valor de regresión de cada punto entre 0 y 1. Las características de la función sigmoidea son las siguientes:
Como se muestra en la figura, cuando z > 0, cuanto mayor es z, más cerca está el valor de retorno sigmoideo de 1 (pero nunca excederá 1). Por el contrario, cuando z
Support Vector Machine (SVM), debido a su nombre en inglés, a menudo se llama SVM. En términos generales, es un modelo de clasificación de dos niveles. Su modelo básico se define como un clasificador lineal con el intervalo más grande en el espacio de características, y su estrategia de aprendizaje es la maximización del intervalo, que en última instancia puede transformarse en la solución de un problema de programación cuadrática convexa.
Clasificador lineal
Dados algunos puntos de datos, que pertenecen a dos clases diferentes, es necesario encontrar un clasificador lineal para clasificar estos datos en dos clases. Si los puntos de datos están representados por La ecuación de se puede expresar como (T en wT representa transposición):
El propósito de la regresión logística es aprender un modelo de clasificación 0/1 a partir de características. combinación lineal de características como variables independientes Porque la variable independiente varía desde el infinito negativo hasta el infinito positivo. Por lo tanto, la función logística (o función sigmoidea) se utiliza para asignar la variable independiente a (0, 1), y el valor asignado se considera la probabilidad de y = 1.
Función hipotética:
Donde x es un vector de características n-dimensional y la función g es una función logística.
La imagen es:
Cuando se determina el hiperplano w x+b=0, |w x+b| puede representar la distancia desde el punto X al hiperplano. x+ Si el signo de b es consistente con el signo de la etiqueta de clase y puede determinar si la clasificación es correcta. Por lo tanto, la exactitud de la clasificación puede juzgarse o expresarse por lo positivo o negativo de (y (w*x+b). )). Aquí presentamos el concepto de margen funcional.
Defina el intervalo de función (expresado por) como
El hiperplano (w, b) es relativo a T (donde ) es el intervalo de función mínimo de todos los puntos de muestra (xi, yi ) en el hiperplano (w, b) en relación con el conjunto de datos de entrenamiento T:
Pero hay un problema con el intervalo de función definido de esta manera, es decir, si W y If B cambian proporcionalmente ( por ejemplo, a 2w y 2b), el valor f(x) del intervalo de función se duplicará (aunque el hiperplano no cambia en este momento), por lo que solo el intervalo de función no es suficiente.
De hecho, podemos agregar algunas restricciones al vector normal W, lo que lleva al concepto de margen geométrico. El margen geométrico realmente define la distancia desde el punto al hiperplano.
Supongamos que para un punto X, el punto correspondiente perpendicular a la proyección del hiperplano es x0, w es un vector perpendicular al hiperplano, que es la distancia desde la muestra p>
Según el conocimiento de En geometría plana, hay
donde ||w|| w|| es la norma de segundo orden de w (la norma es un concepto similar a un módulo para expresar longitud), es un vector unitario (el vector dividido por él se llama vector unitario).
Y debido a que x0 es un punto en el hiperplano, satisface f(x0)=0, por lo que se puede obtener sustituyéndolo en la ecuación del hiperplano, es decir,
Entonces multiplique ambos lados de esta fórmula al mismo tiempo y luego, en función de la suma, podrá calcular:
Para obtener el valor absoluto, multiplíquelo por la categoría correspondiente y para obtener la definición de el intervalo geométrico (expresado en términos):
De las definiciones anteriores de intervalos funcionales e intervalos geométricos, podemos ver que el intervalo geométrico es el intervalo de función dividido por ||w|||, y la función intervalo y (wx+b) = y f(x) es en realidad |f(x)| , esto es solo una medida de intervalo definida artificialmente, y el intervalo geométrico |f(x)|/||w|| apuntando al hiperplano.
Cuando se clasifica un punto de datos, cuanto mayor sea la "brecha" entre el hiperplano y el punto de datos, mayor será la confianza en la clasificación. Por lo tanto, para que la confianza de la clasificación sea lo más alta posible, es necesario maximizar este valor de "intervalo" del hiperplano seleccionado. Esta brecha es la mitad de la brecha en la imagen de abajo.
Se puede ver en el análisis anterior que la función intervalo no es adecuada para tomar el valor máximo del valor del intervalo, porque una vez que se fija el hiperplano, la longitud de W y el valor de B pueden ser escalado proporcionalmente, y el valor puede hacerse arbitrariamente grande, es decir, el intervalo de función puede ser arbitrariamente grande sin cambiar el hiperplano. Pero debido a que el intervalo geométrico se divide por, al escalar W y B, el valor del intervalo geométrico no cambiará, pero cambiará con el cambio del hiperplano, por lo que este es un intervalo más apropiado. En otras palabras, el "intervalo" en el hiperplano de la clasificación de intervalo máximo que se encuentra aquí se refiere al intervalo geométrico.
Por lo tanto, la función objetivo del clasificador de margen máximo se puede definir como
Al mismo tiempo, se deben cumplir algunas condiciones. Según la definición de intervalo,
Recordando la definición de intervalo geométrico, podemos ver que si el intervalo de la función es igual a 1 (la razón por la que es igual a 1 es para facilitar la derivación y optimización, y no tiene impacto en la optimización de la función objetivo), entonces hay = 1/||w|| suma, por lo que la función objetivo anterior se transforma en:
Es equivalente a tomar el valor máximo de 1/||w|| bajo las restricciones correspondientes, 1/| w |||
Se puede entender que,
Debido a la estructura especial de este problema, también se puede transformar en un problema de optimización de variables duales mediante la dualidad lagrangiana, es decir, resolviendo el mismo problema que el problema original El problema dual equivalente obtiene la solución óptima al problema original, que es el algoritmo dual de la máquina de vectores de soporte en condiciones linealmente separables. Las ventajas de este método son: los problemas duales suelen ser más fáciles de resolver; ambos pueden introducir funciones del núcleo de forma natural y luego generalizarse a problemas de clasificación no lineales.
¿Qué es entonces la dualidad lagrangiana? En pocas palabras, agregamos un multiplicador de Lagrange a cada restricción y definimos la función lagrangiana (las restricciones se integran en la función objetivo a través de la función lagrangiana, de modo que nuestro problema solo usa una expresión de función para expresarla claramente).
Luego haz:
Fácil de verificar, por ejemplo, cuando una restricción no se cumple, es obvio (siempre que se cumpla). Cuando se satisfacen todas las restricciones, el valor óptimo es, es decir, la cantidad que se minimizará primero.
Entonces, la minimización bajo las restricciones que cumplen con los requisitos es en realidad equivalente a la minimización directa (por supuesto, aquí también hay restricciones, es decir, ≥0, i=1,...,n), porque Si no se cumplen las restricciones, será igual a infinito, que naturalmente no es el valor mínimo que requerimos.
Específicamente, la función objetivo se convierte en:
Esta se utiliza para representar el valor óptimo de este problema, que es equivalente al problema original. Si lo resuelve directamente, debe enfrentar los dos parámetros W y B, los cuales son restricciones de desigualdad. Este proceso de solución no es fácil de realizar. También puedes intercambiar las posiciones mínima y máxima para convertirte en:
El nuevo problema después del intercambio es el problema dual del problema original, y el valor óptimo de este nuevo problema se expresa como. Y con ≤, bajo ciertas condiciones, los dos son iguales. En este momento, al resolver el problema dual, el problema original se puede resolver indirectamente.
En otras palabras, la razón por la cual el problema original de minmax se convierte en el problema dual de maxmin es porque uno de ellos es una solución aproximada, y es más fácil de resolver después de que ambos se convierten en problemas duales. .
Primero encuentre el valor mínimo de l a w y b, y luego encuentre el valor máximo de l a b.
Condiciones KKT
≤Si se cumplen determinadas condiciones, son equivalentes. El llamado "cumplir ciertas condiciones" significa cumplir las condiciones del KKT.
Para igualarlos, es necesario satisfacer una dualidad fuerte, y luego algunos académicos propusieron la condición KKT bajo dualidad fuerte. La condición KKT debe satisfacer restricciones, una de las cuales es la condición de Slater. La condición de Slater se refiere a un problema de optimización convexa. Si hay un punto Para esto, se cumple la condición de Slater, por lo que ≤ puede ser el signo igual.
Por lo general, el modelo matemático optimizado se puede expresar en la siguiente forma estándar:
donde f(x) es la función a minimizar, h(x) es la restricción de igualdad, g(x) es la restricción de desigualdad, p y q son el número de restricciones de igualdad y restricciones de desigualdad respectivamente.
La importancia de las condiciones KKT: los problemas de programación no lineal tienen condiciones necesarias y suficientes para soluciones óptimas.
La condición KKT significa que el punto mínimo, F y gi también son diferenciables, es decir, L es diferenciable a W y B), entonces ahora pasamos a resolver el segundo problema.
Es decir, al satisfacer la condición KKT, el problema original se transforma en un problema dual. La solución de este problema de aprendizaje dual se divide en tres pasos: primero minimizar L (w, b, a) en relación con w y b, luego encontrar el valor máximo del par y finalmente usar el algoritmo SMO para resolver el multiplicador de Lagrange en el dual. problema.
Tres pasos para resolver el problema dual
Coloque los resultados anteriores en el l anterior:
Obtener:
El proceso de derivación específico es más complicado, como se muestra en la siguiente figura:
Finalmente, obtenemos:
La derivación del "cuarto paso desde abajo" al "tercer paso desde abajo" Utiliza la operación de transposición del álgebra lineal. Debido a que ai y yi son números reales, serán iguales a ellos mismos después de la transposición. El "penúltimo paso" se deriva del "penúltimo paso" utilizando el algoritmo de multiplicación de (A+B+C+…) = AA+AB+AC+BA+BB+BC+…). El último paso es el ajuste de secuencia del paso anterior.
Como se puede ver en la última fórmula anterior, la función lagrangiana en este momento solo contiene una variable, es decir, (si se resuelve, W y B se pueden resolver. De esta manera, el problema central: la función de clasificación se puede resolver fácilmente).
La fórmula anterior es para resolver el problema de encontrar el valor máximo w entre los parámetros. En cuanto a la suma, todos son números conocidos. Para comprender cómo se deriva este algoritmo SMO, pase a la Sección 3.5, Algoritmo SMO a continuación.
Resumen
Echemos un vistazo a algunas formas interesantes derivadas anteriormente. El primero es sobre nuestro hiperplano. De hecho, nuestra clasificación de un punto de datos X es incluirlo en el resultado del cálculo y luego clasificarlo según su signo. En la derivación anterior, obtenemos:
Entonces la función de clasificación es:
Lo interesante de la forma aquí es que para la predicción de un nuevo punto (que representa el producto interno de vectores) Simplemente calcule su producto interno. Esto es muy importante y es la premisa básica para el uso posterior de núcleos para la generalización no lineal. Además, aquí también se muestran los llamados vectores de soporte; de hecho, los coeficientes correspondientes a todos los vectores que no son de soporte son iguales a cero, por lo que el cálculo del producto interno del nuevo punto es en realidad solo para unos pocos "vectores de soporte". en lugar de todos los datos de entrenamiento.
¿Por qué los vectores no soporte corresponden a cero? Intuitivamente, son estos puntos "atrás" los que, como analizamos antes, no tienen ningún efecto en el hiperplano. Debido a que la clasificación está completamente determinada por el hiperplano, estos puntos irrelevantes no participarán en el cálculo del problema de clasificación, por lo que no tendrán ningún impacto.
Recuerde la función objetivo que obtuvimos a través del multiplicador de Lagrange:
Tenga en cuenta que si xi es un vector de soporte, la parte roja en la fórmula anterior es igual a 0 (debido al vector de soporte vector El margen funcional es igual a 1), y para los vectores que no son de soporte, el margen funcional será mayor que 1, por lo que la parte roja es mayor que cero y no negativa, y debe ser igual a 0 para satisfacer la maximización. Esta también es una limitación de estos puntos vectoriales sin soporte.
En este punto hemos obtenido un clasificador de hiperplano de margen máximo, que es la llamada máquina de vectores de soporte. Por supuesto, nuestro SVM hasta ahora todavía es débil y solo puede manejar el caso lineal.
Pero después de obtener la forma dual, resulta muy fácil generalizarla a situaciones no lineales a través del núcleo (la solución óptima se puede obtener resolviendo el problema dual. Este es el algoritmo dual de la máquina de vectores de soporte en condiciones linealmente separables. La ventaja es que los problemas duales suelen ser más fáciles de resolver; ambos pueden introducir naturalmente funciones del núcleo y luego generalizarse a problemas de clasificación no lineales").
De hecho, la mayoría de las veces, los datos no son separables linealmente. esta vez, no existe un hiperplano que satisfaga tal condición. Arriba, ya sabemos que SVM maneja la separabilidad lineal. ¿Qué pasa con SVM para datos no lineales? Para casos no lineales, el método de procesamiento de SVM es elegir la función del núcleo κ ( ? ,?), resuelve el problema de inseparabilidad lineal en el espacio original mapeando los datos en un espacio de alta dimensión.
Específicamente, en el caso de inseparabilidad lineal, la máquina de vectores de soporte se completa primero en el. Calcule el espacio de baja dimensión, luego asigne el espacio de entrada a un espacio de características de alta dimensión a través de la función del núcleo y finalmente construya un hiperplano de separación óptimo en el espacio de características de alta dimensión para separar los datos no lineales en el plano. En la figura, un montón de datos no se pueden dividir en un espacio bidimensional, por lo que se asigna a un espacio tridimensional para la segmentación:
Antes de encontrar la función del núcleo, si usamos la original. método y usar un alumno lineal para aprender relaciones no lineales, debemos elegir un conjunto de características no lineales Escribir una nueva expresión en los datos es equivalente a aplicar un mapeo no lineal fijo para asignar los datos al espacio de características, usando un alumno lineal en el espacio de características Por lo tanto, el conjunto de hipótesis consideradas es este tipo de función:
¿Aquí?: Los datos se transforman en el espacio de características f,
Entonces un aprendiz lineal. utilizado para clasificar en el espacio de características
Debido a que la forma dual es una propiedad importante del alumno lineal, esto significa que la hipótesis se puede expresar como una combinación lineal de puntos de entrenamiento, por lo que la regla de decisión se puede expresar como el producto interno del punto de prueba y el punto de entrenamiento:
Si hay una manera de calcular directamente el producto interno en el espacio de características, al igual que en el punto de entrada original Como en la función, es Es posible fusionar estos dos pasos para construir un alumno no lineal, por lo que el método de cálculo directo se llama método de función del núcleo:
El núcleo es la función k, para todo x, z Todos están satisfechos, donde φ es el mapeo de x al espacio de características del producto interno f.
Veamos un ejemplo de la función del núcleo. Como se muestra en la figura siguiente, los dos tipos de datos se distribuyen en dos círculos. los datos son linealmente inseparables. ¿Cómo podemos separar estos dos tipos de datos en este momento (habrá un diagrama espacial tridimensional correspondiente a continuación)? en dos círculos con radios diferentes se genera agregando un poco de ruido, por lo que el límite ideal debería ser un "círculo" en lugar de una línea (hiperplano). Si se usa la suma para representar las dos coordenadas de este plano bidimensional, sabemos que la curva cuadrática (un círculo es una cuadrática). La ecuación del caso especial de la curva se puede escribir de la siguiente forma:
Observa la forma anterior si construimos otra de cinco dimensiones. espacio en el que están los valores de las cinco coordenadas respectivamente, entonces, obviamente, la ecuación anterior se puede escribir como Nuevo sistema de coordenadas:
Acerca del nuevo sistema de coordenadas, ¡esta es completamente una ecuación de hiperplano! En otras palabras, si hacemos un mapeo, se mapeará de acuerdo con las reglas anteriores, luego los datos originales se volverán separables linealmente en el nuevo espacio y luego podremos usar el algoritmo de clasificación lineal que dedujimos antes de Procesado. Esta es la idea básica del método kernel para abordar problemas no lineales.
Antes de describir más detalladamente los detalles de Kernel, primero echemos un vistazo a la forma intuitiva de mapeo en el ejemplo anterior. Por supuesto, es posible que usted y yo no podamos dibujar un espacio de cinco dimensiones, pero debido a que utilicé un caso especial al generar datos aquí, la ecuación real del hiperplano aquí es así (un círculo perfecto con el centro en el eje )
Así que sólo necesito asignarlo a un espacio tridimensional como este. La siguiente imagen es el resultado después del mapeo. Después de girar los ejes adecuadamente, queda claro que los datos se pueden separar mediante un plano.
La función del núcleo es equivalente a la función de clasificación original:
Asignada a:
Una de ellas se puede obtener resolviendo el siguiente problema dual:
¿Entonces el problema está resuelto? Se ve así: obtenga datos no lineales y encuentre el mapeo.