Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Comprender la regresión de la máquina vectorial de soporte

Formulación matemática de la regresión de SVM

Visión general

El análisis de la máquina vectorial de soporte (SVM) es una herramienta popular de aprendizaje automático para la clasificación y la regresión, identificada por primera vez por Vladimir Vapnik y sus colegas en 1992.[5] La regresión de SVM se considera una técnica no paramétrica porque se basa en las funciones del kernel.

implementa la regresión lineal de SVM insensible a los épsilones, que también se conoce como 1 pérdida.Statistics and Machine Learning Toolbox™L En la regresión -SVM, el conjunto de datos de entrenamiento incluye variables predictoras y valores de respuesta observados.ε El objetivo es encontrar una función f(x) que se desvía de y yn por un valor no mayor que para cada punto de entrenamiento, y al mismo tiempo es lo más plano posible.x

Regresión SVM lineal: Fórmula primigenia

Supongamos que tenemos un conjunto de datos de entrenamiento donde Xn es un conjunto multivariado de observaciones con valores de respuesta observadosN y yn.

Para encontrar la función lineal

f(x)=xβ+b,

y asegurarse de que sea lo más plano posible, encontrar f(x) con el valor mínimo de la norma (ββ). Esto se formula como un problema de optimización convexa para minimizar

J(β)=12ββ

sujeto a todos los residuos que tengan un valor menor que el valor; o, en forma de ecuación:

n:|yn(xnβ+b)|ε.

Es posible que no se f(x) existe para satisfacer estas restricciones para todos los puntos. Para hacer frente a restricciones inviables, introduzca variables holgantes ξn Y ξ*n para cada punto. Este enfoque es similar al concepto de "margen blando" en la clasificación SVM, porque las variables de holgura permiten que existan errores de regresión hasta el valor de ξn Y ξ*n, sin embargo, aún cumplen las condiciones requeridas.

La inclusión de variables holgadoras conduce a la función objetiva, también conocida como fórmula primaria:[5]

J(β)=12ββ+Cn=1N(ξn+ξn*),

sujeto a:

n:yn(xnβ+b)ε+ξnn:(xnβ+b)ynε+ξn*n:ξn*0n:ξn0.

La constante es la restricción de cuadro, un valor numérico positivo que controla la penalización impuesta a las observaciones que se encuentran fuera del margen de épsilon ( ) y ayuda a evitar el sobreajuste (regularización).Cε Este valor determina el equilibrio entre la planitud de f(x) y la cantidad hasta la cual se toleran desviaciones mayores de las que se toleran.ε

La función de pérdida sin distinción lineal de la línea de cambio s ignora los errores que están dentro de la distancia del valor observado al tratarlos como iguales a cero.ε La pérdida se mide en función de la distancia entre el valor observado y el límite.yε Esto se describe formalmente por

Lε={0if |yf(x)|ε|yf(x)|εotherwise

Regresión Lineal de SVM: Fórmula Dual

El problema de optimización descrito anteriormente es computacionalmente más simple de resolver en su formulación dual Lagrange. La solución al problema dual proporciona un límite inferior a la solución del problema primario (minimización). Los valores óptimos de los problemas primarios y duales no tienen por qué ser iguales, y la diferencia se llama la "brecha de dualidad". Pero cuando el problema es convexo y satisface una condición de calificación de restricción, el valor de la solución óptima al problema primario es dado por la solución del problema dual.

Para obtener la fórmula dual, construir una función lagrangiana a partir de la función primaria mediante la introducción de multiplicadores no negativos αn Y α*n para cada observación Xn. Esto conduce a la fórmula dual, donde minimizamos

L(α)=12i=1Nj=1N(αiαi*)(αjαj*)xixj+εi=1N(αi+αi*)+i=1Nyi(αi*αi)

sujeto a las limitaciones

n=1N(αnαn*)=0n:0αnCn:0αn*C.

El parámetro se puede describir completamente como una combinación lineal de las observaciones de entrenamiento utilizando la ecuaciónβ

β=n=1N(αnαn*)xn.

La función utilizada para predecir nuevos valores depende únicamente de los vectores de soporte:

f(x)=n=1N(αnαn*)(xnx)+b.(1)

Las condiciones de complementariedad de Karush-Kuhn-Tucker (KKT) son restricciones de optimización necesarias para obtener soluciones óptimas. Para la regresión sórgica lineal, estas condiciones son

n:αn(ε+ξnyn+xnβ+b)=0n:αn*(ε+ξn*+ynxnβb)=0n:ξn(Cαn)=0n:ξn*(Cαn*)=0.

Estas condiciones indican que todas las observaciones estrictamente dentro del tubo de épsilon tienen multiplicadores Lagrange αn = 0 Y αn* = 0. Si cualquiera de los dos Αn O Αn* no es cero, entonces la observación correspondiente se llama un .vector de apoyo

La propiedad de un modelo SVM entrenado almacena la diferencia entre dos multiplicadores Lagrange de vectores de soporte,Alpha αnαn*. Las propiedades y la tiendaSupportVectorsBias Xn y , respectivamente.b

Regresión SVM no lineal: Fórmula primigenia

Algunos problemas de regresión no se pueden describir adecuadamente mediante un modelo lineal. En tal caso, la formulación dual Lagrange permite que la técnica descrita anteriormente se extienda a funciones no lineales.

Obtenga un modelo de regresión SVM no lineal reemplazando el producto de puntos x1x2 con una función de kernel no lineal G(x1,x2) = <φ(x1),φ(x2)>, donde ( ) es una transformación que se asigna a un espacio de alta dimensión. proporciona las siguientes funciones de kernel semidefinidas integradas.φxxStatistics and Machine Learning Toolbox

Nombre del núcleoFunción del núcleo
Lineal (producto de puntos)G(xj,xk)=xjxk
GaussianoG(xj,xk)=exp(xjxk2)
PolinomioG(xj,xk)=(1+xjxk)q, donde se encuentra en el conjunto de 2,3,....q

Es una matriz -por- que contiene elementosMatriz de Gramnn gi,j = G(xi,xj). Cada elemento gi,j es igual al producto interno de los predictores transformados por .φ Sin embargo, no necesitamos saber, porque podemos utilizar la función kernel para generar la matriz Gram directamente.φ Con este método, SVM no lineal encuentra la función óptima f(x) en el espacio predictor transformado.

Regresión SVM no lineal: Fórmula dual

La fórmula dual para la regresión SVM no lineal reemplaza el producto interno de los predictores (xixj) con el elemento correspondiente de la matriz Gram (gi,j).

La regresión SVM no lineal encuentra los coeficientes que minimizan

L(α)=12i=1Nj=1N(αiαi*)(αjαj*)G(xi,xj)+εi=1N(αi+αi*)i=1Nyi(αiαi*)

sujeto a

n=1N(αnαn*)=0n:0αnCn:0αn*C.

La función utilizada para predecir nuevos valores es igual a

f(x)=n=1N(αnαn*)G(xn,x)+b.(2)

Las condiciones de complementariedad de KKT son

n:αn(ε+ξnyn+f(xn))=0n:αn*(ε+ξn*+ynf(xn))=0n:ξn(Cαn)=0n:ξn*(Cαn*)=0.

Resolver el problema de optimización de regresión de SVM

Algoritmos del solucionador

El problema de minimización puede expresarse en forma de programación cuadrática estándar y resolverse utilizando técnicas de programación cuadráticas comunes. Sin embargo, puede ser costoso computacionalmente utilizar algoritmos de programación cuadrática, especialmente porque la matriz Gram puede ser demasiado grande para ser almacenada en la memoria. El uso de un método de descomposición en su lugar puede acelerar el cálculo y evitar quedarse sin memoria.

(también llamado ) separar todas las observaciones en dos conjuntos separados: el conjunto de trabajo y el conjunto restante.Métodos de descomposiciónmétodos de fragmentación y conjunto de trabajo Un método de descomposición modifica solo los elementos del conjunto de trabajo en cada iteración. Por lo tanto, solo se necesitan algunas columnas de la matriz Gram en cada iteración, lo que reduce la cantidad de almacenamiento necesario para cada iteración.

(SMO) es el enfoque más popular para resolver problemas de SVM.Optimización mínima secuencial[4] SMO realiza una serie de optimizaciones de dos puntos. En cada iteración, se elige un conjunto de trabajo de dos puntos en función de una regla de selección que utiliza información de segundo orden. A continuación, los multiplicadores Lagrange para este conjunto de trabajo se resuelven analíticamente utilizando el enfoque descrito en y .[2][1]

En la regresión SVM, el vector de degradado L para el conjunto activo se actualiza después de cada iteración. La ecuación descompuesta para el vector de degradado es

(L)n={i=1N(αiαi*)G(xi,xn)+εyn,nNi=1N(αiαi*)G(xi,xn)+ε+yn,n>N.

(ISDA) actualiza un multiplicador Lagrange con cada iteración.Algoritmo iterativo de datos únicos[3] ISDA se lleva a cabo a menudo sin el término de sesgo mediante la adición de una pequeña constante positiva a la función del núcleo.ba Al soltar se cae la restricción de sumab

n=1N(αiα*)=0

en la ecuación dual. Esto nos permite actualizar un multiplicador Lagrange en cada iteración, lo que hace que sea más fácil que SMO eliminar valores atípicos. ISDA selecciona al peor violador de KKT entre todos los αn Y αn* valores como el conjunto de trabajo que se va a actualizar.

Criterios de convergencia

Cada uno de estos algoritmos del solucionador calcula de forma iterativa hasta que se cumple el criterio de convergencia especificado. Hay varias opciones para los criterios de convergencia:

  • — La brecha de viabilidad se expresa comoBrecha de viabilidad

    Δ=J(β)+L(α)J(β)+1,

    Dónde J(β) es el objetivo primordial y L(α) es el doble objetivo. Después de cada iteración, el software evalúa la brecha de viabilidad. Si la brecha de viabilidad es menor que el valor especificado por , entonces el algoritmo cumplió el criterio de convergencia y el software devuelve una solución.GapTolerance

  • — Después de cada iteración, el software evalúa el vector de gradiente,Diferencia de gradiente L. Si la diferencia en los valores vectoriales de degradado para la iteración actual y la iteración anterior es menor que el valor especificado por , entonces el algoritmo cumplió el criterio de convergencia y el software devuelve una solución.DeltaGradientTolerance

  • — Después de cada iteración, el software evalúa la infracción de KKT para todos losMayor violación de KKT αn Y αn* Valores. Si la infracción más grande es menor que el valor especificado por , entonces el algoritmo cumplió con el criterio de convergencia y el software devuelve una solución.KKTTolerance

Referencias

[1] Fan, R.E. , P.H. Chen, and C.J. Lin. A Study on SMO-Type Decomposition Methods for Support Vector Machines. IEEE Transactions on Neural Networks, 17:893–908, 2006.

[2] Fan, R.E. , P.H. Chen, and C.J. Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. The Journal of machine Learning Research, 6:1871–1918, 2005.

[3] Huang, T.M., V. Kecman, and I. Kopriva. Kernel Based Algorithms for Mining Huge Data Sets: Supervised, Semi-Supervised, and Unsupervised Learning. Springer, New York, 2006.

[4] Platt, J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98–14, 1999.

[5] Vapnik, V. The Nature of Statistical Learning Theory. Springer, New York, 1995.

Consulte también

| | |

Temas relacionados