Perceptrón del núcleo

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

Preliminares

El algoritmo del perceptrón

El algoritmo 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 actualiza 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 de 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í por simplicidad) 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 en un vector todo cero de longitud p , el número de predictores (características).

Para un número fijo de iteraciones, o hasta que se cumpla algún criterio de parada:

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

En contraste con 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 xi , asocia con cada uno un peso α _i y toma decisiones para nuevas muestras x' mediante la evaluación _.

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

Aquí, K es alguna función del núcleo. Formalmente, una función kernel es un kernel semidefinido no negativo (ver la 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 mediante una función Φ : K ( x , x' ) = Φ( x ) · Φ( x' ) . Intuitivamente, se puede considerar como una función de similitud entre muestras, por lo que la máquina del núcleo establece la clase de una nueva muestra mediante comparación ponderada con el conjunto de entrenamiento. Cada función x' ↦ K ( x _i , x' ) sirve como 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 , a partir de la observación de que el vector de peso w se puede expresar 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 fue clasificado erróneamente, lo que obligó a 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 circuito 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 central arbitraria, para obtener el efecto de un mapa de características Φ sin calcular Φ( x ) explícitamente para ninguna muestra. Hacer esto produce el algoritmo del perceptrón del núcleo: ^[4]

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

Para un número fijo de iteraciones, o hasta que se cumpla algún criterio de parada:

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 ampliaciones

Un problema con el perceptrón del núcleo, como se presentó anteriormente, es que no aprende máquinas con núcleo disperso . Inicialmente, todos los α _i son cero, por lo que evaluar la función de decisión para obtener ŷ no requiere ninguna evaluación del 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 del núcleo se utiliza en un entorno en línea , el número de α _i distintos de cero y, por tanto, el coste de la evaluación crecen linealmente en el número de ejemplos presentados al algoritmo.

Se sugirió la variante olvidada del perceptrón del núcleo para solucionar este problema. 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) ejemplos antiguos a medida que se promueven otros nuevos. a distinto de cero α _i . ^[5]

Otro problema con el perceptrón del núcleo es que no se regulariza , haciéndolo vulnerable al sobreajuste . El algoritmo de aprendizaje del kernel en línea NORMA puede considerarse como una generalización del algoritmo del perceptrón del 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 del núcleo. ^[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 del kernel. ^[2]

Referencias

1. Aizerman, MA; Braverman, Emmanuel M.; Rozoner, LI (1964). "Fundamentos teóricos del método de la función potencial en el aprendizaje por reconocimiento de patrones". Automatización y Control Remoto . 25 : 821–837.Citado en Guyon, Isabelle; Bóser, B.; Vápnik, Vladimir (1993). "Sintonización automática de capacidad de clasificadores de dimensiones VC de gran tamaño" . Avances en los sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 . 
2. Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, León (2005). "Clasificadores de kernel rápidos con aprendizaje activo y en línea". JMLR . 6 : 1579-1619.
3. Schölkopf, Bernhard; y Smola, Alexander J.; Aprendiendo con Kernels , MIT Press, Cambridge, MA, 2002. ISBN 0-262-19475-9 
4. Shawe-Taylor, John; Cristianini, Nello (2004). Métodos del kernel para análisis de patrones . Prensa de la Universidad de Cambridge. págs. 241-242.
5. Dekel, oferta; Shalev-Shwartz, Shai; Cantante, Yoram (2008). "El olvido: un perceptrón basado en kernel con un presupuesto limitado" (PDF) . Revista SIAM de Computación . 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 online con kernels". Transacciones IEEE sobre procesamiento de señales . 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 grandes márgenes mediante el algoritmo perceptrón" (PDF) . Aprendizaje automático . 37 (3): 277–296. doi : 10.1023/A:1007662407062 .