Red de conocimiento informático - Aprendizaje de código fuente - Máquina de vectores de soporte: desde la derivación hasta la escritura a mano en Python

Máquina de vectores de soporte: desde la derivación hasta la escritura a mano en Python

Tomé capturas de pantalla de todos los lugares donde me daba pereza tomar capturas de pantalla.

Las máquinas de vectores de soporte se dividen en tres categorías:

(1) Máquinas de vectores de soporte linealmente separables, las muestras son linealmente separables y se puede entrenar un clasificador maximizando el intervalo estricto.

(2) Máquina de vectores de soporte lineal, las muestras son básicamente separables linealmente y se puede entrenar un clasificador maximizando el intervalo suave.

(3) Máquina de vectores de soporte no lineal, las muestras son linealmente inseparables y se puede entrenar un clasificador maximizando la función del núcleo y el margen suave.

Lo más difícil de entender arriba es probablemente el intervalo duro y el intervalo suave.

Para decirlo sin rodeos, el intervalo duro significa que existe un plano que puede separar las muestras. Por supuesto, esta es una situación extremadamente ideal que no existe en la realidad, por lo que hay un intervalo suave.

Lo que significa el margen suave es que no hay ningún plano que pueda separar las muestras de manera completa y precisa. Por lo tanto, se permite que algunas muestras se clasifiquen erróneamente. La forma de hacerlo es agregar variables de holgura, porque así es. Se espera que las muestras mal clasificadas sean más pequeñas. Cuanto más pequeñas, mejor, por lo que las variables de holgura también tienen restricciones. Después de agregar la variable de holgura, el problema se vuelve linealmente separable, porque cada muestra es linealmente separable, por lo que la variable de holgura es específica de la muestra y cada muestra corresponde a una variable de holgura diferente.

De hecho, el perceptrón debe encontrar una línea recta para separar los puntos de muestra, es decir, la parte superior es de un tipo y la inferior es de otro tipo. Por supuesto, la separación completa es algo bueno, pero a menudo no se puede separar por completo. Por lo tanto, existe una función de pérdida, que es la distancia más corta desde el punto de clasificación errónea hasta este plano:

Aquí hay una larga. oración, el punto de clasificación errónea y*(wx b )lt;0, así que agregue un signo negativo al frente.

En circunstancias normales ||w|| se puede escalar, luego lo escalamos a 1 y la función objetivo final se convierte en

El intervalo es la distancia, asumimos la separación El hiperplano es, entonces la distancia desde el punto de muestra a este plano se puede registrar como. Todos sabemos que los puntos divididos por el perceptrón son los puntos por encima del hiperplano y los puntos por debajo, y luego juzgamos si la clasificación es correcta juzgando si el valor de es consistente con el signo de y. Según esta idea, la función intervalo se define como:

La definición de vector de soporte proviene del intervalo geométrico. La explicación más directa del intervalo geométrico es la distancia desde el punto más cercano al hiperplano de separación. La distancia de cualquier otro punto al plano es mayor que este valor, por lo que el intervalo geométrico es el vector soporte. Luego, de la misma manera, w y b se pueden escalar, por lo que el vector de soporte se define para cumplir las siguientes condiciones:

Para decirlo de manera más simple, los vectores de soporte son puntos más cercanos al plano de separación. Por conveniencia significa que deben escalarse y calcularse para que satisfagan wx b= -1

La función del núcleo es uno de los conceptos centrales de la máquina de vectores de soporte. Simplifique el cálculo después de la conversión de dimensiones, para lograr el propósito de reducir la cantidad de cálculo.

Todos sabemos que la máquina de vectores de soporte busca maximizar la distancia. Normalmente el alfa que obtenemos es igual a 0, por lo que el vector de soporte determina el grado de maximización de la distancia.

La forma de la función kernel es así

Entre ellos, x (i) y x (j) son ambos vectores. La multiplicación de los dos es el vector interno. producto y la multiplicación da como resultado un número. Como se mencionó hace un momento, la función objetivo generalmente solo está relacionada con el vector de soporte, por lo que antes de realizar el cálculo de la función central, se selecciona el vector de soporte para el cálculo.

Agregaré más después de escribir esto

Conocemos el concepto de vector de soporte, entonces la función objetivo de la máquina de vectores de soporte es hacer que la distancia entre los dos vectores de soporte sea lo más cercana posible. lo más lejos posible, porque esto puede separar mejor los puntos de muestra. Por supuesto, el vector de soporte también debe cumplir con las restricciones más básicas, es decir, la clasificación es correcta y la distancia desde otros puntos al plano de separación debe ser mayor que. o igual a la distancia entre el vector de soporte y la distancia de separación.

Este tipo de problema de optimización convexa se puede optimizar mediante el operador lagrangiano, lo que significa imponer restricciones a la función objetivo mediante coeficientes lagrangianos. Esta parte del conocimiento básico es que el algoritmo lagrangiano puede agregar restricciones de igualdad y de desigualdad a la función objetivo para completar la conversión y resolver el problema, pero debe satisfacer algunas restricciones, que son las condiciones kkt de las que hablaremos más adelante.

Un detalle aquí es el problema de los signos más y menos durante la conversión, que está relacionado con los signos positivos y negativos de la función objetivo y las restricciones. Generalmente entendido de esta manera, al resolver un problema de minimización, si la restricción es mayor que 0, entonces un operador Langiano se puede reducir a esta parte. De esta manera, la función objetivo solo puede volverse cada vez más pequeña, y la solución óptima es cuando. la restricción es 0. Cuando, este tiempo equivale a sin restricciones, y luego encontrar el mínimo es el problema original.

Este es un problema de minimización. Esta parte de la restricción se resta directamente y luego la segunda mitad siempre es mayor o igual a 0, por lo que el valor de esta fórmula es menor que el valor de la función objetivo original. . Sabemos que cuando x satisface las restricciones del problema original, maximizar L es igual a la función objetivo original. Entonces podemos transformar este problema en:

Vuelve a la función objetivo original y resuélvelo.

En este momento, solo se requiere el α óptimo y se pueden encontrar w y b. Hemos realizado muchas transformaciones arriba y este proceso debe satisfacer algo llamado condición kkt. De hecho, esto consiste en reunir un montón de restricciones.

(1) La viabilidad del problema original, es decir, h(x)=0, g(x)lt 0

Ponlo aquí:

<; p > La idea central del algoritmo SMO es encontrar el α óptimo y luego calcular w y b de acuerdo con la relación derivada previamente entre w, b y α. La fórmula de cálculo final es:

Actual El problema es cómo encontrar α.

El algoritmo SMO se divide en dos partes. Una parte es un algoritmo de programación cuadrática para resolver dos α y la otra parte es un algoritmo heurístico para seleccionar dos α.

Hablemos primero de la parte del algoritmo heurístico de seleccionar α: el maestro puede demostrar que al optimizar α que viola la condición kkt primero, la solución óptima se puede obtener más rápido. En cuanto a la prueba, yo gané. No lo mires por ahora.

Cuando se habla del algoritmo de solución de la máquina de vectores de soporte, la función del núcleo K se proporciona directamente, entonces, cómo entender la función del núcleo. La función de la función del núcleo es resolver el problema de operación del producto interno de los puntos de muestra en un espacio de alta dimensión. ¿Cómo entenderlo? Por lo general, los problemas de clasificación tienen muchas características y luego, para lograr la separabilidad lineal, se mapearán desde abajo. -dimensional a alta dimensión Si el tamaño de la muestra es más de una dimensión, la cantidad de cálculo será muy grande, por lo que primero se realiza una conversión a través de una función para reducir la cantidad de cálculo de la multiplicación.

Para comprender la función del núcleo, primero comprenda la operación del producto interno. La operación del producto interno es en realidad la multiplicación y suma de dos vectores en las posiciones correspondientes. Por ejemplo, tengo x1 = [v1, v2]. , x2 = [w1, w2], entonces el método de cálculo del producto interno de x1 y x2 es: v1w1 v2w2.

Si la situación anterior es linealmente inseparable, es necesario asignarla a una dimensión alta para que los datos sean linealmente separables, y luego los datos se vuelven de cinco dimensiones, es decir, v1 2 v2 2 v1 v2 v1v2 y luego continúe. Después de un cálculo del producto interno, los datos se convierten.

Con una ligera transformación, se puede cambiar a . La expansión formal es similar a la fórmula larga anterior. Luego, en realidad puede mapear la multiplicación del producto interno, por lo que se puede cambiar la función del núcleo.

El problema es que cuando necesita escribir explícitamente el formulario de mapeo, cuando las dimensiones son muy altas, la cantidad de cálculo requerida es demasiado grande. Por ejemplo, x1 tiene tres dimensiones, y luego el mapeo se realizará. Tiene 19 dimensiones. Sí, el cálculo es complicado. Si usa la función del núcleo, aún realiza operaciones en la dimensión baja original, lo que no solo tiene efectos similares (asignación a dimensiones altas), sino que también reduce la cantidad de cálculos. Esta es la función de la función del núcleo.

Tipos de funciones del kernel:

El núcleo de esta parte radica en la escritura del algoritmo SMO. Para agregar.