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 análisis de clasificación y regresión . En esta versión se 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 kernels .

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

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

lo cual es equivalente a

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

dónde${\displaystyle \phi (x)}$es la aplicación no lineal del espacio original al espacio de alta dimensión o de dimensión infinita.

Datos inseparables

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

${\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}}}$

Según 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{Sujeto a }}{\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},}$

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

Al sustituir${\displaystyle w}$Al expresarlo en el lagrangiano formado a partir del objetivo y las restricciones apropiadas, obtendremos el siguiente problema de programación cuadrática:

${\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},}$

dónde${\displaystyle K(x_{i},x_{j})=\left\langle \phi (x_{i}),\phi (x_{j})\right\rangle }$se denomina función kernel . Resolviendo 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.

Formulación de SVM por 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${\displaystyle y_{i}^{2}=1}$, tenemos

${\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},}$

con${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b).}$Nótese que este error también tendría sentido para el ajuste de datos por mínimos cuadrados, de modo que el mismo resultado final se mantiene para el caso de regresión.

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${\displaystyle E_{W}={\frac {1}{2}}w^{T}w}$y${\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}.}$

Ambos${\displaystyle \mu }$y${\displaystyle \zeta }$Deben considerarse como hiperparámetros para ajustar la cantidad de regularización en función de la suma de los errores cuadráticos. La solución solo depende de la relación.${\displaystyle \gamma =\zeta /\mu }$, por lo tanto, la formulación original utiliza solo${\displaystyle \gamma }$como parámetro de ajuste. Usamos ambos${\displaystyle \mu }$y${\displaystyle \zeta }$como parámetros para proporcionar una interpretación bayesiana a LS-SVM.

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${\displaystyle \alpha _{i}\in \mathbb {R} }$son los multiplicadores de Lagrange. Las condiciones de optimalidad son

${\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}}}$

Eliminación de${\displaystyle w}$y${\displaystyle e}$dará como resultado un sistema lineal en lugar de un problema de programación cuadrática :

${\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${\displaystyle Y=[y_{1},\ldots ,y_{N}]^{T}}$,${\displaystyle 1_{N}=[1,\ldots ,1]^{T}}$y${\displaystyle \alpha =[\alpha _{1},\ldots ,\alpha _{N}]^{T}}$. Aquí,${\displaystyle I_{N}}$es un${\displaystyle N\times N}$matriz identidad y${\displaystyle \Omega \in \mathbb {R} ^{N\times N}}$es la matriz del núcleo definida por${\displaystyle \Omega _{ij}=\phi (x_{i})^{T}\phi (x_{j})=K(x_{i},x_{j})}$.

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

MacKay desarrolló un marco general de evidencia bayesiana, ^{[ 3 ] [ 4 ] [ 5 ]} y lo ha utilizado para el problema de la regresión, las redes neuronales directas y las redes de clasificación. Conjunto de datos proporcionado${\displaystyle D}$, un modelo${\displaystyle \mathbb {M} }$con vector de parámetros${\displaystyle w}$y un denominado hiperparámetro o parámetro de regularización.${\displaystyle \lambda }$La inferencia bayesiana se construye con 3 niveles de inferencia:

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

${\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${\displaystyle \lambda }$, maximizando

${\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 observar que el marco de evidencia bayesiana constituye una teoría unificada para el aprendizaje y la selección de modelos. Kwok utilizó este marco para interpretar la formulación de las máquinas de vectores de soporte (SVM) y la selección de modelos. Asimismo, lo aplicó a la regresión de vectores de soporte.

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

${\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} )}},}$

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

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

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

${\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í${\displaystyle n_{f}}$es la dimensionalidad del espacio de características, igual que la dimensionalidad de${\displaystyle w}$.

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

${\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 coste 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.${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b)}$como:

${\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 el${\displaystyle w}$y${\displaystyle b}$se determinan de tal manera que los centros de clase${\displaystyle {\hat {m}}_{-}}$y${\displaystyle {\hat {m}}_{+}}$se mapean sobre el objetivo -1 y +1, respectivamente. Las proyecciones${\displaystyle w^{T}\phi (x)+b}$de los elementos de la clase${\displaystyle \phi (x)}$siguen una distribución gaussiana multivariada, que tiene varianza${\displaystyle 1/\zeta }$.

Combinando las expresiones anteriores y despreciando 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${\displaystyle w_{MP}}$y${\displaystyle b_{MP}}$se obtienen luego minimizando el logaritmo negativo de (26), por lo que llegamos a (10).

• 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.º 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, pp.  469–505.

• www.esat.kuleuven.be/sista/lssvmlab/ "La caja de herramientas Least squares support vector machine Lab (LS-SVMlab) contiene implementaciones en Matlab/C para varios algoritmos LS-SVM".
• www.kernel-machines.org "Máquinas de vectores de soporte y métodos basados ​​en kernels (Smola y Schölkopf)".
• www.gaussianprocess.org "Procesos gaussianos: modelado de datos utilizando priors de procesos gaussianos 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.