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 las 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 fue inventado en 1964, [1] convirtiéndolo en el primer aprendiz de clasificación del núcleo. [2]
Preliminares
El algoritmo del perceptrón
El algoritmo de perceptrón es un algoritmo de aprendizaje en línea que opera 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 encuentra 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 usa para clasificar un vector de muestra x como clase "uno" o clase "menos uno "según
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 .
- Para cada ejemplo de entrenamiento x i con etiqueta de verdad fundamental y i ∈ {-1, 1 }:
Métodos de kernel
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 x i , asocia con cada uno un peso α i , y toma decisiones para nuevas muestras x ' evaluando
- .
Aquí, K es alguna función del núcleo. Formalmente, una función de kernel es un kernel semidefinito 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 kernel establece la clase de una nueva muestra mediante una 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 , 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
donde α i es el número de veces que x i se clasificó erróneamente, lo que obliga a actualizar 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 :
Conectar estas dos ecuaciones en el ciclo de entrenamiento lo convierte en el algoritmo de perceptrón dual .
Finalmente, podemos reemplazar el producto escalar en el perceptrón dual por una función de núcleo arbitraria, para obtener el efecto de un mapa de características Φ sin calcular Φ ( x ) explícitamente para ninguna muestra. Al hacer esto, se obtiene 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
- Si ŷ ≠ y j , realice una actualización incrementando el contador de errores:
- α j ← α j + 1
- Para cada ejemplo de entrenamiento x j , y j :
Variantes y ampliaciones
Un problema con el perceptrón del kernel, como se presentó anteriormente, es que no aprende máquinas de kernel dispersas . Inicialmente, todos los α i son cero, por lo que evaluar la función de decisión para obtener ŷ no requiere evaluaciones 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 lo tanto, el costo de evaluación aumentan linealmente en el número de ejemplos presentados al algoritmo.
Se sugirió la variante forgetron del perceptrón del núcleo para tratar 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 nuevos. a diferente de cero α i . [5]
Otro problema con el perceptrón del núcleo es que no se regulariza , lo que lo hace vulnerable al sobreajuste . El algoritmo de aprendizaje del kernel en línea NORMA se puede considerar 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 kernel SVM. [2]
Referencias
- ^ 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 Telemando . 25 : 821–837. Citado en Guyon, Isabelle; Boser, B .; Vapnik, Vladimir (1993). Ajuste automático de la capacidad de clasificadores de dimensiones VC muy grandes . Avances en sistemas de procesamiento de información neuronal. CiteSeerX 10.1.1.17.7215 .
- ^ a b Bordes, Antoine; Ertekin, Seyda; Weston, Jason; Bottou, Léon (2005). "Clasificadores de kernel rápidos con aprendizaje activo y en línea". JMLR . 6 : 1579-1619.
- ^ Schölkopf, Bernhard; y Smola, Alexander J .; Aprendiendo con Kernels , MIT Press, Cambridge, MA, 2002. ISBN 0-262-19475-9
- ^ Shawe-Taylor, John; Cristianini, Nello (2004). Métodos de kernel para análisis de patrones . Prensa de la Universidad de Cambridge. págs. 241–242.
- ^ Dekel, Ofer; Shalev-Shwartz, Shai; Cantante, Yoram (2008). "El forgetron: un perceptrón basado en el núcleo con un presupuesto" (PDF) . Revista SIAM de Computación . 37 (5): 1342-1372. CiteSeerX 10.1.1.115.568 . doi : 10.1137 / 060666998 .
- ^ a b 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 .
- ^ Freund, Y .; Schapire, RE (1999). "Clasificación de grandes márgenes mediante el algoritmo de perceptrón" (PDF) . Aprendizaje automático . 37 (3): 277-296. doi : 10.1023 / A: 1007662407062 .