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.

Comprensión de la regresión de máquina de vectores de soporte

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

Visión general

El análisis de la máquina de vectores de soporte (SVM) es una herramienta popular de aprendizaje automático para clasificación y 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 de SVM (ε-SVM), que también se conoce como 1 pérdida.Statistics and Machine Learning Toolbox™L En la regresión de 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 yn por un valor no superior a ε para cada punto de entrenamiento, y al mismo tiempo es lo más plano posible.x

Regresión de 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 yn.

Para encontrar la función lineal

f(x)=xβ+b,

y asegúrese de que sea lo más plano posible, encuentre f(x) con el valor normal mínimo (ββ). Esto se formula como un problema de optimización convexa para minimizar

J(β)=12ββ

sujetos a todos los residuos que tengan un valor inferior a ε; o, en forma de ecuación:

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

Es posible que ninguna de esas funciones f(x) existe para satisfacer estas restricciones para todos los puntos. Para lidiar con restricciones infactibles, introduzca variables de Slack ξn Y ξ*n para cada punto. Este enfoque es similar al concepto de "margen flexible" en la clasificación de SVM, ya que las variables de Slack permiten que existan errores de regresión hasta el valor de ξn Y ξ*n, pero aún así satisfacen las condiciones requeridas.

Incluir variables de Slack conduce a la función objetiva, también conocida como la fórmula primigenia:[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 caja, 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 intercambio entre la planitud de f(x) y la cantidad hasta la cual las desviaciones más grandes que se toleran.ε

La función de pérdida lineal ε-insensible ignora los errores que están dentro de la distancia del valor observado tratándolos como igual 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 de SVM lineal: fórmula dual

El problema de optimización descrito anteriormente es computacionalmente más fácil de resolver en su formulación dual de Lagrange. La solución al doble problema 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 para el problema primigenio viene dado por la solución del doble problema.

Para obtener la fórmula dual, construya una función Lagrangia a partir de la función primordial introduciendo 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)

sujeta a las restricciones

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

El parámetro puede describirse 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 las restricciones de optimización requeridas para obtener soluciones óptimas. Para la regresión de SVM lineal, estas condiciones se

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 de Lagrange αn = 0 Y αn* = 0. Si cualquiera Αn O Αn* no es cero, entonces la observación correspondiente se llama a.support vector

La propiedad de un modelo de SVM entrenado almacena la diferencia entre dos multiplicadores de 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 de 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 punto x1x2 con una función de kernel no lineal G(x1,x2) = <φ(x1),φ(x2)>, where () es una transformación que se asigna a un espacio de alta dimensión. proporciona las siguientes funciones de kernel semidefinidas incorporadas.φxxStatistics and Machine Learning Toolbox

Nombre del kernelFunción kernel
Lineal (producto de punto)G(xj,xk)=xjxk
GaussianoG(xj,xk)=exp(xjxk2)
PolinomioG(xj,xk)=(1+xjxk)q, donde está en el set {2, 3,...}.q

El es un-por-matriz que contiene elementosGram matrixnn gi,j = G(xi,xj). Cada elemento gi,j es igual al producto interno de los predictores como transformado por.φ Sin embargo, no necesitamos saberlo, porque podemos utilizar la función kernel para generar directamente la matriz Gram.φ 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*)

sujetas 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 de Solver

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

(también llamado) separar todas las observaciones en dos conjuntos disjuntas: el conjunto de trabajo y el conjunto restante.Decomposition methodschunking and working set methods 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.Sequential minimal optimization[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 de Lagrange para este conjunto de trabajo se resuelven analíticamente utilizando el enfoque descrito en y.[2][1]

En la regresión de 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 de Lagrange con cada iteración.Iterative single data algorithm[3] ISDA se realiza a menudo sin el término de sesgo añadiendo una pequeña constante positiva a la función del kernel.ba Al soltar cae la restricción de sumab

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

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

Criterios de convergencia

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

  • — La brecha de viabilidad se expresa comoFeasibility gap

    Δ=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ó con 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 degradado,Gradient difference 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, el algoritmo cumple 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 losLargest KKT violation αn Y αn* Valores. Si la infracción más grande es menor que el valor especificado por, a continuación, el algoritmo cumple 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