Máquina de vectores de soporte de mínimos cuadrados

Las máquinas de vectores de soporte de mínimos cuadrados (LS-SVM) para estadística y en modelado estadístico , son versiones de mínimos cuadrados de las máquinas de vectores de soporte (SVM), que son un conjunto de métodos de aprendizaje supervisado relacionados que analizan datos y reconocen patrones, y que se utilizan para la clasificación y el análisis de regresión . En esta versión, uno encuentra la solución resolviendo un conjunto de ecuaciones lineales en lugar de un problema de programación cuadrática convexa (QP) para las SVM clásicas. Los clasificadores SVM de mínimos cuadrados fueron propuestos por Johan Suykens y Joos Vandewalle. ^[1] Las LS-SVM son una clase de métodos de aprendizaje basados ​​en kernel .

De la máquina de vectores de soporte a la máquina de vectores de soporte de mínimos cuadrados

Dado un conjunto de entrenamiento con datos de entrada y etiquetas de clase binarias correspondientes , el clasificador SVM ^[2] , según la formulación original de Vapnik , satisface las siguientes condiciones: ${\displaystyle \{x_{i},y_{i}\}_{i=1}^{N}}$ ${\displaystyle x_{i}\in \mathbb {R} ^{n}}$ ${\displaystyle y_{i}\in \{-1,+1\}}$

Los datos en espiral: para el punto de datos azul, para el punto de datos rojo ${\displaystyle y_{i}=1}$ ${\displaystyle y_{i}=-1}$

${\displaystyle {\begin{cases}w^{T}\phi (x_{i})+b\geq 1,&{\text{if }}\quad y_{i}=+1,\\w^{T}\phi (x_{i})+b\leq -1,&{\text{if }}\quad y_{i}=-1,\end{cases}}}$

que es equivalente a

${\displaystyle y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1,\quad i=1,\ldots ,N,}$

¿Dónde está el mapa no lineal del espacio original al espacio de alta o infinita dimensión? ${\displaystyle \phi (x)}$

Datos inseparables

En caso de que no exista dicho hiperplano separador, introducimos las llamadas variables de holgura tales que ${\displaystyle \xi _{i}}$

${\displaystyle {\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N.\end{cases}}}$

El resultado del clasificador SVM

De acuerdo con el principio de minimización del riesgo estructural , el límite de riesgo se minimiza mediante el siguiente problema de minimización:

${\displaystyle \min J_{1}(w,\xi )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}\xi _{i},}$

${\displaystyle {\text{Subject to }}{\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N,\end{cases}}}$

Para resolver este problema, podríamos construir la función lagrangiana :

${\displaystyle L_{1}(w,b,\xi ,\alpha ,\beta )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}{\xi _{i}}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{y_{i}\left[{w^{T}\phi (x_{i})+b}\right]-1+\xi _{i}\right\}-\sum \limits _{i=1}^{N}\beta _{i}\xi _{i},}$

donde están los multiplicadores lagrangianos . El punto óptimo estará en el punto de silla de la función lagrangiana, y entonces obtenemos ${\displaystyle \alpha _{i}\geq 0,\ \beta _{i}\geq 0\ (i=1,\ldots ,N)}$

Sustituyendo por su expresión en el Lagrangiano formado a partir del objetivo y restricciones adecuados, obtendremos el siguiente problema de programación cuadrática: ${\displaystyle w}$

${\displaystyle \max Q_{1}(\alpha )=-{\frac {1}{2}}\sum \limits _{i,j=1}^{N}{\alpha _{i}\alpha _{j}y_{i}y_{j}K(x_{i},x_{j})}+\sum \limits _{i=1}^{N}\alpha _{i},}$

donde se denomina función kernel . Al resolver este problema QP sujeto a las restricciones en ( 1 ), obtendremos el hiperplano en el espacio de alta dimensión y, por lo tanto, el clasificador en el espacio original. ${\displaystyle K(x_{i},x_{j})=\left\langle \phi (x_{i}),\phi (x_{j})\right\rangle }$

Formulación de SVM de mínimos cuadrados

La versión de mínimos cuadrados del clasificador SVM se obtiene reformulando el problema de minimización como

${\displaystyle \min J_{2}(w,b,e)={\frac {\mu }{2}}w^{T}w+{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}e_{i}^{2},}$

sujeto a las restricciones de igualdad

${\displaystyle y_{i}\left[{w^{T}\phi (x_{i})+b}\right]=1-e_{i},\quad i=1,\ldots ,N.}$

La formulación del clasificador SVM de mínimos cuadrados (LS-SVM) anterior corresponde implícitamente a una interpretación de regresión con objetivos binarios . ${\displaystyle y_{i}=\pm 1}$

Usando , tenemos ${\displaystyle y_{i}^{2}=1}$

${\displaystyle \sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}(y_{i}e_{i})^{2}=\sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2},}$

Tenga en cuenta que este error también tendría sentido para el ajuste de datos de mínimos cuadrados, de modo que los mismos resultados finales se aplican al caso de regresión. ${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b).}$

Por lo tanto, la formulación del clasificador LS-SVM es equivalente a

${\displaystyle J_{2}(w,b,e)=\mu E_{W}+\zeta E_{D}}$

con y ${\displaystyle E_{W}={\frac {1}{2}}w^{T}w}$ ${\displaystyle E_{D}={\frac {1}{2}}\sum \limits _{i=1}^{N}e_{i}^{2}={\frac {1}{2}}\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2}.}$

El resultado del clasificador LS-SVM

Tanto y deben considerarse como hiperparámetros para ajustar la cantidad de regularización en función del error cuadrático medio. La solución solo depende de la relación , por lo que la formulación original utiliza solo como parámetro de ajuste. Usamos y como parámetros para proporcionar una interpretación bayesiana a LS-SVM. ${\displaystyle \mu }$ ${\displaystyle \zeta }$ ${\displaystyle \gamma =\zeta /\mu }$ ${\displaystyle \gamma }$ ${\displaystyle \mu }$ ${\displaystyle \zeta }$

La solución del regresor LS-SVM se obtendrá después de construir la función lagrangiana :

${\displaystyle {\begin{cases}L_{2}(w,b,e,\alpha )\;=J_{2}(w,e)-\sum \limits _{i=1}^{N}\alpha _{i}\left\{{\left[{w^{T}\phi (x_{i})+b}\right]+e_{i}-y_{i}}\right\},\\\quad \quad \quad \quad \quad \;={\frac {1}{2}}w^{T}w+{\frac {\gamma }{2}}\sum \limits _{i=1}^{N}e_{i}^{2}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{\left[w^{T}\phi (x_{i})+b\right]+e_{i}-y_{i}\right\},\end{cases}}}$

¿Dónde están los multiplicadores de Lagrange? Las condiciones de optimalidad son ${\displaystyle \alpha _{i}\in \mathbb {R} }$

${\displaystyle {\begin{cases}{\frac {\partial L_{2}}{\partial w}}=0\quad \to \quad w=\sum \limits _{i=1}^{N}\alpha _{i}\phi (x_{i}),\\{\frac {\partial L_{2}}{\partial b}}=0\quad \to \quad \sum \limits _{i=1}^{N}\alpha _{i}=0,\\{\frac {\partial L_{2}}{\partial e_{i}}}=0\quad \to \quad \alpha _{i}=\gamma e_{i},\;i=1,\ldots ,N,\\{\frac {\partial L_{2}}{\partial \alpha _{i}}}=0\quad \to \quad y_{i}=w^{T}\phi (x_{i})+b+e_{i},\,i=1,\ldots ,N.\end{cases}}}$

La eliminación de y producirá un sistema lineal en lugar de un problema de programación cuadrática : ${\displaystyle w}$ ${\displaystyle e}$

${\displaystyle \left[{\begin{matrix}0&1_{N}^{T}\\1_{N}&\Omega +\gamma ^{-1}I_{N}\end{matrix}}\right]\left[{\begin{matrix}b\\\alpha \end{matrix}}\right]=\left[{\begin{matrix}0\\Y\end{matrix}}\right],}$

con , y . Aquí, es una matriz identidad , y es la matriz kernel definida por . ${\displaystyle Y=[y_{1},\ldots ,y_{N}]^{T}}$ ${\displaystyle 1_{N}=[1,\ldots ,1]^{T}}$ ${\displaystyle \alpha =[\alpha _{1},\ldots ,\alpha _{N}]^{T}}$ ${\displaystyle I_{N}}$ ${\displaystyle N\times N}$ ${\displaystyle \Omega \in \mathbb {R} ^{N\times N}}$ ${\displaystyle \Omega _{ij}=\phi (x_{i})^{T}\phi (x_{j})=K(x_{i},x_{j})}$

Función del núcleoK

Para la función kernel K (•, •) normalmente se tienen las siguientes opciones:

• Núcleo lineal : ${\displaystyle K(x,x_{i})=x_{i}^{T}x,}$
• Núcleo polinomial de grado : ${\displaystyle d}$ ${\displaystyle K(x,x_{i})=\left({1+x_{i}^{T}x/c}\right)^{d},}$
• Función de base radial RBF kernel: ${\displaystyle K(x,x_{i})=\exp \left({-\left\|{x-x_{i}}\right\|^{2}/\sigma ^{2}}\right),}$
• Núcleo MLP: ${\displaystyle K(x,x_{i})=\tanh \left({k\,x_{i}^{T}x+\theta }\right),}$

donde , , , y son constantes. Nótese que la condición de Mercer se cumple para todos los valores y en el caso polinomial y RBF, pero no para todas las opciones posibles de y en el caso MLP. Los parámetros de escala , y determinan el escalamiento de las entradas en la función kernel polinomial, RBF y MLP . Este escalamiento está relacionado con el ancho de banda del kernel en las estadísticas , donde se muestra que el ancho de banda es un parámetro importante del comportamiento de generalización de un método kernel. ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle \sigma }$ ${\displaystyle k}$ ${\displaystyle \theta }$ ${\displaystyle c,\sigma \in \mathbb {R} ^{+}}$ ${\displaystyle d\in N}$ ${\displaystyle k}$ ${\displaystyle \theta }$ ${\displaystyle c}$ ${\displaystyle \sigma }$ ${\displaystyle k}$

Interpretación bayesiana para LS-SVM

Smola et al. propusieron una interpretación bayesiana del SVM. Demostraron que el uso de diferentes núcleos en el SVM puede considerarse como la definición de diferentes distribuciones de probabilidad previa en el espacio funcional, como . Aquí es una constante y es el operador de regularización correspondiente al núcleo seleccionado. ${\displaystyle P[f]\propto \exp \left({-\beta \left\|{{\hat {P}}f}\right\|^{2}}\right)}$ ${\displaystyle \beta >0}$ ${\displaystyle {\hat {P}}}$

^{MacKay [3] [4] [5]} desarrolló un marco de evidencia bayesiano general y lo utilizó para resolver problemas de regresión, redes neuronales directas y redes de clasificación. A partir de un conjunto de datos , un modelo con un vector de parámetros y un denominado hiperparámetro o parámetro de regularización , se construye una inferencia bayesiana con tres niveles de inferencia: ${\displaystyle D}$ ${\displaystyle \mathbb {M} }$ ${\displaystyle w}$ ${\displaystyle \lambda }$

• En el nivel 1, para un valor dado de , el primer nivel de inferencia infiere la distribución posterior de mediante la regla bayesiana ${\displaystyle \lambda }$ ${\displaystyle w}$

${\displaystyle p(w|D,\lambda ,\mathbb {M} )\propto p(D|w,\mathbb {M} )p(w|\lambda ,\mathbb {M} ).}$

• El segundo nivel de inferencia determina el valor de , maximizando ${\displaystyle \lambda }$

${\displaystyle p(\lambda |D,\mathbb {M} )\propto p(D|\lambda ,\mathbb {M} )p(\lambda |\mathbb {M} ).}$

• El tercer nivel de inferencia en el marco de evidencia clasifica diferentes modelos examinando sus probabilidades posteriores.

${\displaystyle p(\mathbb {M} |D)\propto p(D|\mathbb {M} )p(\mathbb {M} ).}$

Podemos ver que el marco de evidencia bayesiano es una teoría unificada para el aprendizaje del modelo y la selección del modelo. Kwok utilizó el marco de evidencia bayesiano para interpretar la formulación de SVM y la selección del modelo. Y también aplicó el marco de evidencia bayesiano para respaldar la regresión vectorial.

Ahora, dados los puntos de datos y los hiperparámetros y del modelo , los parámetros del modelo y se estiman maximizando el posterior . Aplicando la regla de Bayes, obtenemos ${\displaystyle \{x_{i},y_{i}\}_{i=1}^{N}}$ ${\displaystyle \mu }$ ${\displaystyle \zeta }$ ${\displaystyle \mathbb {M} }$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )}$

${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )={\frac {p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )}{p(D|\log \mu ,\log \zeta ,\mathbb {M} )}},}$

donde es una constante normalizadora tal que la integral sobre todos los posibles y es igual a 1. Suponemos que y son independientes del hiperparámetro , y son condicionalmente independientes, es decir, suponemos ${\displaystyle p(D|\log \mu ,\log \zeta ,\mathbb {M} )}$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle \zeta }$

${\displaystyle p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )=p(w|\log \mu ,\mathbb {M} )p(b|\log \sigma _{b},\mathbb {M} ).}$

Cuando , la distribución de se aproximará a una distribución uniforme. Además, suponemos que y son una distribución gaussiana, por lo que obtenemos la distribución a priori de y con que es ${\displaystyle \sigma _{b}\to \infty }$ ${\displaystyle b}$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle \sigma _{b}\to \infty }$

${\displaystyle {\begin{array}{l}p(w,b|\log \mu ,)=\left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right){\frac {1}{\sqrt {2\pi \sigma _{b}}}}\exp \left({-{\frac {b^{2}}{2\sigma _{b}}}}\right)\\\quad \quad \quad \quad \quad \quad \quad \propto \left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right)\end{array}}.}$

Aquí está la dimensionalidad del espacio de características, igual que la dimensionalidad de . ${\displaystyle n_{f}}$ ${\displaystyle w}$

Se supone que la probabilidad de depende únicamente de y . Suponemos que los puntos de datos están distribuidos de manera idéntica e independiente (iid), de modo que: ${\displaystyle p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )}$ ${\displaystyle w,b,\zeta }$ ${\displaystyle \mathbb {M} }$

${\displaystyle p(D|w,b,\log \zeta ,\mathbb {M} )=\prod \limits _{i=1}^{N}{p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )}.}$

Para obtener la función de costo de mínimos cuadrados, se supone que la probabilidad de un punto de datos es proporcional a:

${\displaystyle p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )\propto p(e_{i}|w,b,\log \zeta ,\mathbb {M} ).}$

Se toma una distribución gaussiana para los errores como: ${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b)}$

${\displaystyle p(e_{i}|w,b,\log \zeta ,\mathbb {M} )={\sqrt {\frac {\zeta }{2\pi }}}\exp \left({-{\frac {\zeta e_{i}^{2}}{2}}}\right).}$

Se supone que y se determinan de tal manera que los centros de clase y se asignan a los objetivos -1 y +1, respectivamente. Las proyecciones de los elementos de clase siguen una distribución gaussiana multivariante, que tienen una varianza . ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle {\hat {m}}_{-}}$ ${\displaystyle {\hat {m}}_{+}}$ ${\displaystyle w^{T}\phi (x)+b}$ ${\displaystyle \phi (x)}$ ${\displaystyle 1/\zeta }$

Combinando las expresiones anteriores y descuidando todas las constantes, la regla de Bayes se convierte en

${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )\propto \exp(-{\frac {\mu }{2}}w^{T}w-{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}{e_{i}^{2}})=\exp(-J_{2}(w,b)).}$

Las estimaciones de densidad posterior máxima y se obtienen luego minimizando el logaritmo negativo de (26), por lo que llegamos a (10). ${\displaystyle w_{MP}}$ ${\displaystyle b_{MP}}$

Referencias

1. Suykens, J. A. K.; Vandewalle, J. (1999) "Clasificadores de máquinas de vectores de soporte de mínimos cuadrados", Neural Processing Letters , 9 (3), 293–300.
2. Vapnik, V. La naturaleza de la teoría del aprendizaje estadístico. Springer-Verlag, Nueva York, 1995.
3. MacKay, D. J. C. Interpolación bayesiana. Neural Computation, 4(3): 415–447, mayo de 1992.
4. MacKay, D. J. C. Un marco bayesiano práctico para redes de retropropagación. Neural Computation, 4(3): 448–472, mayo de 1992.
5. MacKay, D. J. C. El marco de evidencia aplicado a las redes de clasificación. Neural Computation, 4(5): 720–736, septiembre de 1992.

Bibliografía

• JAK Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, J. Vandewalle, Máquinas de vectores de soporte de mínimos cuadrados, World Scientific Pub. Co., Singapur, 2002. ISBN  981-238-151-1
• Suykens J. A. K., Vandewalle J., Clasificadores de máquinas de vectores de soporte de mínimos cuadrados, Neural Processing Letters , vol. 9, núm. 3, junio de 1999, págs. 293–300.
• Vladimir Vapnik. La naturaleza de la teoría del aprendizaje estadístico . Springer-Verlag, 1995. ISBN 0-387-98780-0 
• MacKay, DJC, Redes probables y predicciones plausibles: una revisión de métodos bayesianos prácticos para redes neuronales supervisadas. Network: Computation in Neural Systems , vol. 6, 1995, págs. 469–505.

Enlaces externos

• "La caja de herramientas del Laboratorio de máquinas de vectores de soporte de mínimos cuadrados (LS-SVMlab) contiene implementaciones de Matlab/C para varios algoritmos LS-SVM".
• www.kernel-machines.org "Máquinas de vectores de soporte y métodos basados ​​en kernel (Smola y Schölkopf)".
• www.gaussianprocess.org "Procesos Gaussianos: Modelado de datos utilizando valores previos del Proceso Gaussiano sobre funciones para regresión y clasificación (MacKay, Williams)".
• www.support-vector.net "Máquinas de vectores de soporte y métodos basados ​​en kernel (Cristianini)".
• dlib: contiene una implementación de SVM de mínimos cuadrados para conjuntos de datos a gran escala.