Perceptrón del núcleo

En el aprendizaje automático , el perceptrón de núcleo es una variante del popular algoritmo de aprendizaje del perceptrón que puede aprender máquinas de núcleo , es decir, clasificadores no lineales que emplean una función de núcleo para calcular la similitud de muestras no vistas con muestras de entrenamiento. El algoritmo se inventó en 1964, ^[1] lo que lo convierte en el primer aprendiz de clasificación de núcleo. ^[2]

Preliminares

El algoritmo del perceptrón

El algoritmo del perceptrón es un algoritmo de aprendizaje en línea que funciona según un principio llamado "aprendizaje basado en errores". Mejora iterativamente un modelo ejecutándolo en muestras de entrenamiento y luego actualizando el modelo cada vez que descubre que ha realizado una clasificación incorrecta con respecto a una señal supervisada . El modelo aprendido por el algoritmo del perceptrón estándar es un clasificador binario lineal : un vector de pesos w (y opcionalmente un término de intersección b , omitido aquí para simplificar) que se utiliza para clasificar un vector de muestra x como clase "uno" o clase "menos uno" según

${\displaystyle {\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )}$

donde un cero se asigna arbitrariamente a uno o menos uno. (El " sombrero " en ŷ denota un valor estimado).

En pseudocódigo , el algoritmo del perceptrón viene dado por:

Inicialice w a un vector todo cero de longitud p , el número de predictores (características).

Durante un número fijo de iteraciones, o hasta que se cumpla algún criterio de detención:

Para cada ejemplo de entrenamiento x _i con etiqueta de verdad fundamental y _i ∈ {-1, 1 }:

Sea ŷ = sgn( w ^T x _i ) .

Si ŷ ≠ y _i , actualice w ← w + y _i x _i .

Métodos del núcleo

A diferencia de los modelos lineales aprendidos por el perceptrón, un método kernel ^[3] es un clasificador que almacena un subconjunto de sus ejemplos de entrenamiento x _i , asocia a cada uno un peso α _i y toma decisiones para nuevas muestras x' evaluando

${\displaystyle \operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )}$.

Aquí, K es una función kernel. Formalmente, una función kernel es un kernel semidefinido no negativo (ver condición de Mercer ), que representa un producto interno entre muestras en un espacio de alta dimensión, como si las muestras se hubieran expandido para incluir características adicionales por una función Φ : K ( x , x' ) = Φ( x ) · Φ( x' ) . Intuitivamente, se puede pensar como una función de similitud entre muestras, por lo que la máquina kernel establece la clase de una nueva muestra por comparación ponderada con el conjunto de entrenamiento. Cada función x' ↦ K ( x _i , x' ) sirve como una función base en la clasificación.

Algoritmo

Para derivar una versión kernelizada del algoritmo del perceptrón, primero debemos formularlo en forma dual , partiendo de la observación de que el vector de peso w puede expresarse como una combinación lineal de las n muestras de entrenamiento. La ecuación para el vector de peso es

${\displaystyle \mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}}$

donde α _i es el número de veces que x _i se clasificó incorrectamente, forzando una actualización w ← w + y _i x _i . Usando este resultado, podemos formular el algoritmo de perceptrón dual, que recorre las muestras como antes, haciendo predicciones, pero en lugar de almacenar y actualizar un vector de peso w , actualiza un vector de "contador de errores" α . También debemos reescribir la fórmula de predicción para deshacernos de w :

${\displaystyle {\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}}$

Al conectar estas dos ecuaciones al ciclo de entrenamiento, se convierte en el algoritmo de perceptrón dual .

Finalmente, podemos reemplazar el producto escalar en el perceptrón dual por una función kernel arbitraria, para obtener el efecto de un mapa de características Φ sin calcular Φ( x ) explícitamente para ninguna muestra. Al hacer esto, obtenemos el algoritmo del perceptrón kernel: ^[4]

Inicialice α en un vector de todos ceros de longitud n , el número de muestras de entrenamiento.

Durante un número fijo de iteraciones, o hasta que se cumpla algún criterio de detención:

Para cada ejemplo de entrenamiento x _j , y _j :

Dejar ${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})}$

Si ŷ ≠ y _j , realice una actualización incrementando el contador de errores:

αj ← αj ₊ 1_​

Variantes y extensiones

Un problema con el perceptrón de núcleo, como se presentó anteriormente, es que no aprende máquinas de núcleo dispersas . Inicialmente, todos los α _i son cero, de modo que evaluar la función de decisión para obtener ŷ no requiere ninguna evaluación de núcleo, pero cada actualización incrementa un solo α _i , lo que hace que la evaluación sea cada vez más costosa. Además, cuando el perceptrón de núcleo se utiliza en un entorno en línea , la cantidad de α _i no cero y, por lo tanto, el costo de evaluación crecen linealmente en la cantidad de ejemplos presentados al algoritmo.

Para solucionar este problema se sugirió la variante forgetron del perceptrón de núcleo. Mantiene un conjunto activo de ejemplos con α _i distinto de cero , eliminando ("olvidando") ejemplos del conjunto activo cuando excede un presupuesto predeterminado y "reduciendo" (reduciendo el peso de) los ejemplos antiguos a medida que los nuevos son promovidos a α _i distinto de cero . ^[5]

Otro problema con el perceptrón kernel es que no se regulariza , lo que lo hace vulnerable al sobreajuste . El algoritmo de aprendizaje kernel en línea NORMA puede considerarse como una generalización del algoritmo del perceptrón kernel con regularización. ^[6] El algoritmo de optimización mínima secuencial (SMO) utilizado para aprender máquinas de vectores de soporte también puede considerarse como una generalización del perceptrón kernel. ^[6]

El algoritmo de perceptrón votado de Freund y Schapire también se extiende al caso kernelizado, ^[7] dando límites de generalización comparables a los del SVM kernel. ^[2]

Referencias

1. Aizerman, MA; Braverman, Emmanuel M.; Rozoner, LI (1964). "Fundamentos teóricos del método de función potencial en el aprendizaje de reconocimiento de patrones". Automatización y control remoto . 25 : 821–837.Citado en Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Ajuste automático de la capacidad de clasificadores de dimensión VC muy grande . Avances en sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 . 
2. Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, Léon (2005). "Clasificadores de núcleo rápidos con aprendizaje en línea y activo". JMLR . 6 : 1579–1619.
3. Schölkopf, Bernhard; y Smola, Alexander J.; Aprendizaje con núcleos , MIT Press, Cambridge, MA, 2002. ISBN 0-262-19475-9 
4. Shawe-Taylor, John; Cristianini, Nello (2004). Métodos de núcleo para análisis de patrones . Cambridge University Press. págs. 241–242.
5. Dekel, Ofer; Shalev-Shwartz, Shai; Singer, Yoram (2008). "El forgetron: un perceptrón basado en kernel de bajo presupuesto" (PDF) . SIAM Journal on Computing . 37 (5): 1342–1372. CiteSeerX 10.1.1.115.568 . doi :10.1137/060666998. 
6. Kivinen, Jyrki; Smola, Alexander J.; Williamson, Robert C. (2004). "Aprendizaje en línea con núcleos". IEEE Transactions on Signal Processing . 52 (8): 2165–2176. CiteSeerX 10.1.1.578.5680 . doi :10.1109/TSP.2004.830991. 
7. Freund, Y. ; Schapire, RE (1999). "Clasificación de márgenes amplios utilizando el algoritmo perceptrón" (PDF) . Aprendizaje automático . 37 (3): 277–296. doi : 10.1023/A:1007662407062 .