Soporta el programa Matlab básico de máquina vectorial y su aplicación.

1 Introducción

Support Vector Machine (SVM) es básicamente el mejor algoritmo de aprendizaje supervisado disponible actualmente. La primera vez que entré en contacto con SVM fue durante las vacaciones de verano del año pasado. El profesor me pidió que diera un informe sobre "Teoría del aprendizaje estadístico". En ese momento, descargué un tutorial introductorio. Solo entendí aproximadamente algunos conceptos. Esta vez, los materiales de aprendizaje proporcionados por Stanford me permitieron volver a aprender algunos conocimientos de SVM. He visto que muchos métodos ortodoxos parten de la teoría de la dimensión VC y el principio de minimización del riesgo estructural, y luego conducen a SVM, etc. Algunos materiales hablan sobre hiperplanos de clasificación, etc. Este material comienza con la regresión logística en las secciones anteriores y luego conduce a SVM, que revela la conexión entre los modelos y hace que la transición se sienta más natural.

2 Revisando la regresión logística

El propósito de la regresión logística es aprender un modelo de clasificación 0/1 a partir de características. Este modelo es una combinación lineal de características como variables independientes. variables El rango de valores de es desde infinito negativo hasta infinito positivo. Por lo tanto, utilice la función logística (también conocida como función sigmoidea) para asignar las variables independientes a (0,1) y trate el valor asignado como la probabilidad de pertenecer a y=1.

La representación formal es

Función de hipótesis

donde x es un vector propio n-dimensional y la función g es una función logarítmica.

La imagen de

es

que asigna infinito a (0,1) como se muestra.

La función de hipótesis es la probabilidad de que la característica pertenezca a y=1.

Cuando queremos determinar a qué categoría pertenece una nueva característica, solo necesitamos Si es mayor que 0,5, pertenece a la categoría y=1; de lo contrario, pertenece a la categoría y=0.

Vuelva a estudiar y descubrí que solo está relacionado con >0, entonces g (z) solo se usa para mapeo y la decisión real de la categoría sigue siendo. Otro hecho es que cuando , =1, viceversa =0. Si solo comenzamos desde , el objetivo que queremos que logre el modelo no es más que hacer que las características en los datos de entrenamiento sean y=1 en lugar de las características y=0. La regresión logística se obtiene mediante el aprendizaje, de modo que las características de las instancias positivas sean mucho mayores que 0, mientras que las características de las instancias negativas sean mucho menores que 0. Se enfatiza que esto se logra dentro de toda la gama de instancias de entrenamiento.

El diagrama es el siguiente:

La línea media es y la recuperación lógica enfatiza que todos los puntos están lo más lejos posible de la línea media. El resultado del aprendizaje es también la línea media. Considere los 3 puntos anteriores A, B y C. Del gráfico podemos estar seguros de que A pertenece a la categoría x, pero no estamos seguros de C y estamos bastante seguros de B. De esto podemos concluir que deberíamos prestar más atención a los puntos cerca de la línea divisoria media y mantenerlos lo más lejos posible de la línea media en lugar de optimizar todos los puntos. Porque al hacerlo, algunos puntos se acercarán a la mediana y otros puntos se alejarán de la mediana. Creo que esta es la diferencia entre las máquinas de vectores de soporte y la regresión logística, una considera lo local (no le importan los puntos que se han determinado que están más lejos), la otra considera lo global (ajustando la mediana, los puntos que ya están más lejos se pueden mover más lejos) más lejos). Esta es mi comprensión intuitiva personal.

3 Representación formal

Esta vez usamos las etiquetas de resultados y=-1,y=1 en lugar de y=0 e y=1 utilizadas en la regresión logística. Ahora reemplazamos b con b seguido de (es decir). De esta manera, dejamos además , . Es decir, no hay diferencia con la representación formal de la regresión logística excepto que cuando se cambia y de y = 0 a y = -1, sólo se marcan las diferencias. Asuma la función

Como se mencionó en la sección anterior, solo necesitamos considerar los aspectos positivos y negativos y no necesitamos preocuparnos por g (z), por lo que simplificaremos g (z) y simplemente mapearemos a y=-1 y y=1. La relación de mapeo es la siguiente:

4 Margen funcional y margen geométrico

Dada una muestra de entrenamiento, x es la característica, y es la etiqueta del resultado e i representa el i-ésimo muestra. Nuestra definición del intervalo de función es la siguiente:

Como puedes imaginar, en nuestra definición de g(z), cuando , el valor de es en realidad . viceversa.

Para maximizar el intervalo de función (para determinar con mayor confianza si un ejemplo es positivo o negativo), cuando , debe ser un número positivo grande y viceversa, debe ser un número negativo grande. Por lo tanto, el intervalo de función representa nuestra confianza en que la característica es un ejemplo positivo o negativo.

Continúe usando w y b. Si aumentamos w y b al mismo tiempo, por ejemplo, los multiplicamos por 2 veces, entonces el intervalo de función de todos los puntos aumentará 2 veces, lo que no debería. será útil para resolver el problema Cualquier efecto, ya que la solución que estamos pidiendo es que expandir w y b simultáneamente no tendrá ningún efecto en el resultado. En este caso, es posible que necesitemos agregar una condición de normalización para restringir w y b. Discutiremos esta condición de normalización más adelante.

Acabamos de definir el intervalo de función de una muestra específica, ahora definamos el intervalo de función de la muestra global

Para decirlo sin rodeos, es minimizar la certeza de resultados positivos y clasificación de casos negativos en el intervalo de función de muestra de entrenamiento.

A continuación, comenzamos a definir el intervalo geométrico de la figura.

Supongamos que tenemos un plano divisorio donde se encuentra el punto B. La distancia de cualquier otro punto (como A) a este plano se denota por , y se supone que B es la proyección de A en el plano divisorio. Sabemos que la dirección del vector BA es (el gradiente del plano divisorio) y el vector unitario es . El punto A es , por lo que el punto B es x= (usando el conocimiento de geometría de la escuela secundaria), de lo cual obtenemos,

Además, obtenemos

en realidad la distancia desde el punto hasta el avión.

Otra forma más elegante de escribir es:

¿No es este el intervalo de tiempo de la función? Sí, el resultado normalizado del intervalo de función mencionado anteriormente es el intervalo geométrico. ¿Por qué son iguales? Porque los intervalos de función los definimos nosotros y están coloreados por los intervalos geométricos cuando se definen. Del mismo modo, expandir tanto w como b en un factor de w es un factor de b, y el resultado no se ve afectado. De manera similar, defina el margen geométrico global

5 Clasificador de margen óptimo

Recuerde que mencionamos anteriormente que nuestro objetivo es encontrar un hiperplano tal que los puntos del plano cercanos al hiperplano puedan tener un mayor espaciado. Es decir, no creemos que todos los puntos deban estar lejos del hiperplano. Lo que nos importa es encontrar un hiperplano para que los puntos más cercanos entre todos los puntos puedan tener la distancia máxima. En sentido figurado, podemos pensar en la imagen de arriba como una hoja de papel. Lo que estamos buscando es una polilínea después de plegarla de acuerdo con esta polilínea, la distancia entre los puntos más cercanos es mayor que la de todas las demás polilíneas. La representación formal es:

Aquí usamos =1 estatuto w, que es el espaciado geométrico.

Llegados a este punto tenemos definido el modelo. Si resolvemos para w y b, entonces podemos obtener la característica x y clasificarla, que es el llamado clasificador de intervalo óptimo. La siguiente pregunta es cómo resolver para w y b.

Dado que no es una función convexa, primero queremos ocuparnos de la conversión de la relación entre intervalos geométricos e intervalos funcionales, por lo que reescribimos la ecuación anterior:

De hecho, Esta vez lo que buscamos es el valor máximo del intervalo geométrico, pero esta vez w no está restringido. Sin embargo, la función objetivo en este momento todavía no es una función convexa y no se puede colocar directamente en el software de optimización para su cálculo. Tenemos que reescribirlo. Como se mencionó anteriormente, ampliar w y b simultáneamente no tiene ningún efecto en los resultados, pero todavía estamos buscando valores definidos de w y b, no un conjunto de múltiplos de ellos, por lo que debemos imponer algunas restricciones para asegurar que nuestro La solución es única. Para simplificar, aquí tomamos . Esto significa que el intervalo de función global se define como 1, es decir, la distancia al punto más cercano al hiperplano se define como. Dado que el valor máximo es igual al valor mínimo, el resultado reescrito es:

Muy bien, solo hay restricciones lineales y este es un problema típico de programación cuadrática (la función objetivo es la función cuadrática de la variable independiente ). Sustitúyalo en el software de optimización para solucionarlo.

En este punto, descubrí que este folleto no comienza con gráficos, dibuja hiperplanos de clasificación y marca intervalos en el gráfico como otros folletos, sino que la derivación de cada paso está bien fundamentada y se basa en. ideas.La función objetivo y las restricciones se derivan para el flujo.

A continuación se presenta el método de solución manual, que es un método de solución más ideal.

6 Método de dualidad lagrangiana

Dejando de lado el problema de programación cuadrática anterior, veamos primero cómo resolver el problema de valores extremos con restricciones de igualdad, como la siguiente pregunta de optimización:

La función objetivo es f(w), y las siguientes son las restricciones de igualdad. La solución habitual es introducir un operador lagrangiano, que se utiliza aquí para representar el operador. La fórmula lagrangiana es

L es el número de restricciones de igualdad.

Luego toma las derivadas parciales de w y respectivamente, de modo que las derivadas parciales sean iguales a 0, y luego resuelve para w y . En cuanto a por qué se puede encontrar el valor extremo introduciendo el operador lagrangiano, la razón es que la dirección cambiante de dw de f (w) está limitada por otras desigualdades. El valor extremo solo se puede encontrar cuando la dirección cambiante de dw es perpendicular a la. gradiente de f(w), y en los valores extremos, el gradiente de f(w) es paralelo a la combinación lineal de los gradientes de las otras ecuaciones, por lo que existe una relación lineal entre ellos. (Ver Optimización y condiciones KKT)

Luego exploramos la solución al problema de valores extremos con restricciones de desigualdad de la siguiente manera:

Definimos la fórmula lagrangiana generalizada

Aquí y están ambos operadores lagrangianos. Si resolvemos esta fórmula, encontraremos un problema, porque estamos resolviendo el valor mínimo, y el valor mínimo aquí ya no es 0, podemos ajustarlo a un valor positivo muy grande, de modo que el resultado de la función final es infinito negativo. Por lo tanto, debemos descartar este caso y definir la función de la siguiente manera:

Aquí P representa la función original. Suponiendo o , entonces siempre podemos ajustar y para que el valor máximo sea infinito positivo. Cuando sólo g y h satisfacen las restricciones, es f(w). La belleza de esta función es que lo es y toma valores extremadamente grandes.

Por lo tanto, podemos escribir

de modo que nuestra solicitud inicial de min f(w) pueda convertirse en una solicitud para ello.

Usamos . Si lo resolvemos directamente, primero debemos enfrentar dos parámetros, que también son restricciones de desigualdad, y luego minimizarlos en w. Este proceso no es fácil de realizar, entonces, ¿qué debemos hacer? Este proceso no es fácil, entonces ¿qué hacer?

Consideremos otro problema

D representa la dualidad, que transforma el problema en encontrar primero el mínimo del Lagrangiano en w, tratando y como valores fijos. Después de eso, si encontramos el valor máximo:

Este problema es el problema dual del problema original, donde el orden de mínimo y máximo se cambia en relación con el problema original y, en general, el resultado de el cambio de orden es Max Min (X) <= MinMax(X). Sin embargo, aquí son iguales. La expresión del problema binario es la siguiente:

A continuación se explicarán las condiciones bajo las cuales los dos son equivalentes. Supongamos que f y g son funciones convexas y h es una función afín (afín,). Y existe w tal que para todo i, . Bajo este supuesto, debe haber una situación donde: es la solución al problema original y también es la solución al problema dual. Además, también se cumple la condición de Karush-Kuhn-Tucker (condición KKT), de la siguiente manera:

Por lo tanto, si se cumple la condición de Kuhn-Tucker, entonces son solución de problemas primarios y duales. Revisemos la ecuación (5), esta condición se conoce como condición de complementariedad dual KKT. Esta condición significa que si, entonces. Es decir, cuando w está en el límite de la región factible, es cuando las restricciones entran en juego. Todos los demás puntos ubicados dentro (de) la región factible son restricciones ineficaces, siendo la restricción . Esta condición de doble complementación KKT se utilizará para interpretar pruebas de convergencia de vectores de soporte y SMO.

Las ideas de esta parte son un poco confusas. Primero debes estudiar el problema de valores extremos restringidos en "Programación no lineal" y luego mirar hacia atrás. La idea general de KKT es que los valores extremos se obtendrán en los límites de la región factible (es decir, desigualdad 0 o restricciones de igualdad), y la mejor dirección de descenso suele ser una combinación lineal de estas ecuaciones, donde cada elemento es ya sea una restricción de desigualdad 0 o son elementos de la restricción de igualdad. Restricciones de ecuaciones. Para puntos dentro del límite de la región factible, no tiene ningún efecto sobre la solución óptima, por lo que los coeficientes anteriores son todos 0.

Los 7 mejores clasificadores marginales

Volviendo al problema de optimización de SVM:

Reescribimos las restricciones de la siguiente manera:

De KKT It Se puede ver a partir de la condición de que solo los coeficientes delante de las restricciones lineales con un intervalo de función de 1 (el punto más cercano al hiperplano), es decir, estas restricciones, para otros puntos () que no están en la línea recta, por lo tanto, no obtendrá el valor extremo en su rango. Tenga en cuenta que cada ecuación de restricción es en realidad una muestra de entrenamiento.

Mire la siguiente figura:

La línea continua es el hiperplano de intervalo máximo, suponiendo que x es un ejemplo positivo y el círculo es un ejemplo negativo. Los puntos en la línea de puntos son puntos donde el intervalo de función es 1, los coeficientes delante de ellos son y los coeficientes de todos los demás puntos son. Estos tres puntos se llaman vectores de soporte. La construcción de la función lagrangiana es la siguiente:

Tenga en cuenta que aquí solo no hay, porque no hay restricciones de igualdad en el problema original, solo restricciones de desigualdad.

A continuación resolvemos el problema binario paso a paso según los pasos:

Primero, encontramos el valor mínimo de a fijo, y solo encontramos los valores mínimos de w y b , respectivamente. Encuentre las derivadas parciales de w y b.

Luego obtenemos

Llevamos la ecuación anterior a la función lagrangiana y luego obtenemos el valor mínimo de la función (la función objetivo es una función convexa)

Sustituir, el proceso de simplificación es el siguiente:

Finalmente obtenemos

Como el último término es 0, se simplifica a

Aquí expresamos el producto interno del vector como

En este momento, la función lagrangiana solo contiene variables.

Como se mencionó anteriormente, tanto el problema dual como el problema primitivo deben cumplir varias condiciones. Primero, dado que la función objetivo y las restricciones lineales son convexas y no existe una restricción de igualdad h, existe tal w. : Para todos yo, . Por lo tanto, debe haber tales soluciones, es decir, soluciones al problema original y soluciones al problema dual. En este caso preguntar significa preguntar.

Si encontramos , entonces hemos encontrado w (que también es la solución al problema original).

Entonces es posible encontrar b. En otras palabras, el intervalo de funciones positivas más cercano al hiperplano es igual al intervalo de funciones negativas más cercano al hiperplano.

Cómo resolver el problema binario anterior, lo aclararemos mediante el algoritmo SMO en el próximo artículo.

Aquí hay otro problema a considerar debido a la solución anterior,

El punto de partida que consideramos en todo el problema es, según la solución, sustituimos la fórmula anterior para obtener.

En otras palabras, en el pasado, las nuevas muestras tenían que realizar operaciones lineales basadas en los w y b clasificados, y luego ver si el resultado era mayor que 0 o menor que 0 para determinar si era un ejemplo positivo o negativo. Ahora, no necesitamos encontrar w, solo necesitamos sumar los productos internos de la nueva muestra y todas las muestras en los datos de entrenamiento. Entonces algunas personas pueden decir: ¿consume demasiado tiempo utilizar todas las muestras anteriores para realizar cálculos? De hecho, no es así. Podemos obtener de la condición KKT que solo el vector de soporte es y otras situaciones lo son. Por lo tanto, solo necesitamos pedir el producto interno de la nueva muestra y el vector de soporte para completar la operación. Esta forma de escribir allana el camino para que la función del núcleo se mencione a continuación. Este es el artículo anterior, así que me detendré aquí por ahora.

7 Funciones Kernel

Considere el problema que planteamos originalmente en regresión lineal, donde las características son el tamaño de la casa x, donde x es un número real y el resultado y es el precio de la casa. Supongamos que vemos en la distribución de puntos muestrales que xey se ajustan a una curva cúbica, entonces queremos aproximar estos puntos muestrales con un polinomio cúbico de x. Luego, primero debemos extender la característica x al espacio tridimensional y luego encontrar un modelo entre la característica y el resultado. A esta transformación de características la llamamos mapa de características. La función de mapeo se llama y en este ejemplo

queremos aplicar el mapa de características resultante a la clasificación SVM en lugar de las características originales. Por lo tanto, necesitamos mapear el producto interno en la ecuación anterior de , a .

En cuanto a por qué necesitamos características mapeadas en lugar de características iniciales para participar en el cálculo, una de las razones es la mencionada anteriormente (para un mejor ajuste), otra razón importante es que las muestras pueden ser linealmente indistinguibles. y Una vez que las características se asignan a un espacio dimensional superior, a menudo son distinguibles.

(

Para definir formalmente la función del núcleo, si el producto interno de la característica original es y el mapeo es, entonces defina la función del núcleo (Kernel) como

En este punto, podemos concluir que para lograr el efecto al comienzo de esta sección, solo necesitamos calcularlo primero y luego calcularlo. Por ejemplo, si la característica inicial es n-dimensional, llevará tiempo asignarla a la dimensión. y luego calcularlo. ¿Encuentra una manera de reducir el tiempo de cálculo?

Veamos un ejemplo. Supongamos que x y z son n dimensiones.

Esta vez solo necesitamos calcular el cuadrado del producto interno de las características originales x y z (la complejidad del tiempo es O (n)), lo que equivale a calcular el producto interno de la característica mapeada. lo que significa que no necesitamos gastar dinero.

Ahora mira la función de mapeo (cuando n=3), de acuerdo con la fórmula anterior, podemos obtener

Eso. es decir, solo seleccionando una función como la función de mapeo, la función del núcleo puede ser equivalente al producto interno de la función de mapeo

Mire nuevamente la función del núcleo