Perceptrón

Algoritmo para el aprendizaje supervisado de clasificadores binarios

En el aprendizaje automático , el perceptrón (o neurona McCulloch–Pitts ) es un algoritmo de aprendizaje supervisado de clasificadores binarios . Un clasificador binario es una función que puede decidir si una entrada, representada por un vector de números, pertenece o no a alguna clase específica. ^[1] Es un tipo de clasificador lineal , es decir, un algoritmo de clasificación que realiza sus predicciones basándose en una función predictora lineal que combina un conjunto de pesos con el vector de características .

Historia

Máquina perceptrón Mark I, la primera implementación del algoritmo perceptrón. Se conectó a una cámara con fotocélulas de sulfuro de cadmio de 20x20 para generar una imagen de 400 píxeles. La característica visible principal es el tablero de conexiones de asociación sensorial, que establece diferentes combinaciones de características de entrada. A la derecha hay matrices de potenciómetros que implementaron los pesos adaptativos. ^{[2] : 213}

El perceptrón Mark 1, ajustado por Charles Wightman (ingeniero del proyecto del perceptrón Mark I). ^[3] Unidades sensoriales a la izquierda, unidades de asociación en el centro y panel de control y unidades de respuesta en el extremo derecho. El tablero de conexiones de sensores a asociaciones está detrás del panel cerrado a la derecha del operador. La letra "C" en el panel frontal es una pantalla del estado actual de la entrada sensorial. ^[4]

El perceptrón fue inventado en 1943 por Warren McCulloch y Walter Pitts . ^[5] La primera implementación de hardware fue la máquina Mark I Perceptron construida en 1957 en el Laboratorio Aeronáutico de Cornell por Frank Rosenblatt , ^{[6] financiada por la División de Sistemas de Información de la} Oficina de Investigación Naval de los Estados Unidos y el Centro de Desarrollo Aéreo de Roma . Se demostró públicamente por primera vez el 23 de junio de 1960. ^[7] La ​​máquina fue "parte de un esfuerzo de cuatro años previamente secreto del NPIC [el Centro Nacional de Interpretación Fotográfica de los Estados Unidos ] desde 1963 hasta 1966 para desarrollar este algoritmo en una herramienta útil para los intérpretes de fotografías". ^[8]

Rosenblatt describió los detalles del perceptrón en un artículo de 1958. ^[9] Su organización de un perceptrón está construida con tres tipos de células ("unidades"): AI, AII, R, que significan " proyección ", "asociación" y "respuesta".

El proyecto de Rosenblatt fue financiado bajo el Contrato Nonr-401(40) "Programa de Investigación de Sistemas Cognitivos", que duró desde 1959 hasta 1970, ^[10] y el Contrato Nonr-2381(00) "Proyecto PARA" ("PARA" significa "Autómatas de Percepción y Reconocimiento"), que duró desde 1957 ^[6] hasta 1963. ^[11]

Máquina perceptrón Mark I

Organización de un cerebro biológico y un perceptrón.

El perceptrón fue concebido como una máquina, en lugar de un programa, y ​​aunque su primera implementación fue en software para el IBM 704 , posteriormente se implementó en hardware personalizado como el "perceptrón Mark I" con el nombre de proyecto "Proyecto PARA", ^[12] diseñado para el reconocimiento de imágenes . La máquina se encuentra actualmente en el Museo Nacional Smithsoniano de Historia Estadounidense . ^[13]

El perceptrón Mark I tenía tres capas. Una versión se implementó de la siguiente manera:

• Conjunto de 400 fotocélulas dispuestas en una cuadrícula de 20x20, denominadas "unidades sensoriales" (unidades S) o "retina de entrada". Cada unidad S puede conectarse a un máximo de 40 unidades A.
• Una capa oculta de 512 perceptrones, denominadas "unidades de asociación" (unidades A).
• Una capa de salida de 8 perceptrones, denominadas "unidades de respuesta" (unidades R).

Rosenblatt llamó a esta red perceptrón de tres capas el perceptrón alfa , para distinguirlo de otros modelos de perceptrón con los que experimentó. ^[7]

Las unidades S están conectadas a las unidades A de forma aleatoria (según una tabla de números aleatorios) a través de un tablero de conexiones (ver foto), para "eliminar cualquier sesgo intencional particular en el perceptrón". Los pesos de conexión son fijos, no aprendidos. Rosenblatt era inflexible en cuanto a las conexiones aleatorias, ya que creía que la retina estaba conectada aleatoriamente a la corteza visual y quería que su máquina perceptrón se asemejara a la percepción visual humana. ^[14]

Las unidades A están conectadas a las unidades R, con pesos ajustables codificados en potenciómetros , y las actualizaciones de peso durante el aprendizaje se realizaron mediante motores eléctricos. ^{[2] : 193} Los detalles del hardware se encuentran en un manual del operador. ^[12]

Componentes del perceptrón Mark I. Del manual del operador. ^[12]

En una conferencia de prensa organizada por la Marina de los EE. UU. en 1958, Rosenblatt hizo declaraciones sobre el perceptrón que causaron una acalorada controversia entre la incipiente comunidad de IA ; basándose en las declaraciones de Rosenblatt, The New York Times informó que el perceptrón era "el embrión de una computadora electrónica que [la Marina] espera que pueda caminar, hablar, ver, escribir, reproducirse y ser consciente de su existencia". ^[15]

Principios de la neurodinámica(1962)

Rosenblatt describió sus experimentos con muchas variantes de la máquina Perceptrón en un libro titulado Principles of Neurodynamics (1962). El libro es una versión publicada del informe de 1961. ^[16]

Entre las variantes están:

• "acoplamiento cruzado" (conexiones entre unidades dentro de la misma capa) con bucles posiblemente cerrados,
• "acoplamiento posterior" (conexiones de unidades en una capa posterior a unidades en una capa anterior),
• perceptrones de cuatro capas donde las dos últimas capas tienen pesos ajustables (y por lo tanto un perceptrón multicapa adecuado),
• Incorporando retardos de tiempo a las unidades de perceptrón, para permitir el procesamiento de datos secuenciales,
• analizando audio (en lugar de imágenes).

La máquina fue enviada desde Cornell al Smithsonian en 1967, bajo una transferencia gubernamental administrada por la Oficina de Investigación Naval. ^[8]

Perceptrones(1969)

Aunque el perceptrón parecía prometedor en un principio, se demostró rápidamente que no se podía entrenar a los perceptrones para que reconocieran muchas clases de patrones. Esto provocó que el campo de la investigación sobre redes neuronales se estancara durante muchos años, antes de que se reconociera que una red neuronal de propagación hacia delante con dos o más capas (también llamada perceptrón multicapa ) tenía mayor capacidad de procesamiento que los perceptrones con una capa (también llamados perceptrones de una sola capa ).

Los perceptrones de una sola capa solo son capaces de aprender patrones linealmente separables . ^[17] Para una tarea de clasificación con alguna función de activación por pasos, un solo nodo tendrá una sola línea que divide los puntos de datos que forman los patrones. Más nodos pueden crear más líneas divisorias, pero esas líneas deben combinarse de alguna manera para formar clasificaciones más complejas. Una segunda capa de perceptrones, o incluso nodos lineales, son suficientes para resolver muchos problemas que de otro modo no serían separables.

En 1969, un famoso libro titulado Perceptrones de Marvin Minsky y Seymour Papert demostró que era imposible para estas clases de redes aprender una función XOR . A menudo se cree incorrectamente que también conjeturaron que un resultado similar se daría para una red de perceptrones multicapa. Sin embargo, esto no es cierto, ya que tanto Minsky como Papert ya sabían que los perceptrones multicapa eran capaces de producir una función XOR. (Véase la página sobre Perceptrones (libro) para más información.) Sin embargo, el texto de Minsky y Papert, a menudo mal citado, provocó una disminución significativa en el interés y la financiación de la investigación de redes neuronales. Pasaron diez años más hasta que la investigación de redes neuronales experimentó un resurgimiento en la década de 1980. ^{[17] [ verificación necesaria ]} Este texto fue reimpreso en 1987 como "Perceptrones - Edición ampliada" donde se muestran y corrigen algunos errores en el texto original.

Trabajos posteriores

Rosenblatt siguió trabajando en perceptrones a pesar de la disminución de la financiación. El último intento fue Tobermory, construido entre 1961 y 1967, diseñado para el reconocimiento de voz. ^[18] Ocupaba una habitación entera. ^[19] Tenía 4 capas con 12.000 pesos implementados por núcleos magnéticos toroidales . En el momento de su finalización, la simulación en computadoras digitales se había vuelto más rápida que las máquinas perceptrón construidas específicamente para ese fin. ^[20] Murió en un accidente de navegación en 1971.

Vista isométrica de Tobermory Fase I. ^[19]

El algoritmo del perceptrón kernel fue introducido ya en 1964 por Aizerman et al. ^[21] Las garantías de límites de margen fueron dadas para el algoritmo del perceptrón en el caso general no separable por primera vez por Freund y Schapire (1998), ^[1] y más recientemente por Mohri y Rostamizadeh (2013) quienes extienden resultados previos y dan límites L1 nuevos y más favorables. ^{[22] [23]}

El perceptrón es un modelo simplificado de una neurona biológica . Si bien la complejidad de los modelos de neuronas biológicas suele ser necesaria para comprender por completo el comportamiento neuronal, las investigaciones sugieren que un modelo lineal similar al perceptrón puede producir algunos comportamientos observados en neuronas reales. ^[24]

En este trabajo se estudian los espacios de soluciones de los límites de decisión para todas las funciones binarias y los comportamientos de aprendizaje. ^[25]

Definición

Se aplican los pesos apropiados a las entradas y la suma ponderada resultante se pasa a una función que produce la salida o.

En el sentido moderno, el perceptrón es un algoritmo para aprender un clasificador binario llamado función umbral : una función que asigna su entrada (un vector de valor real ) a un valor de salida (un único valor binario ): ${\displaystyle \mathbf {x} }$ ${\displaystyle f(\mathbf {x} )}$

${\displaystyle f(\mathbf {x} )=h(\mathbf {w} \cdot \mathbf {x} +b)}$

donde es la función escalonada de Heaviside , es un vector de pesos de valor real, es el producto escalar , donde m es el número de entradas al perceptrón y b es el sesgo . El sesgo desplaza el límite de decisión alejándolo del origen y no depende de ningún valor de entrada. ${\displaystyle h}$ ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} \cdot \mathbf {x} }$ ${\displaystyle \sum _{i=1}^{m}w_{i}x_{i}}$

De manera equivalente, dado que , podemos agregar el término de sesgo como otro peso y agregar una coordenada a cada entrada , y luego escribirlo como un clasificador lineal que pasa el origen: ${\displaystyle \mathbf {w} \cdot \mathbf {x} +b=(\mathbf {w} ,b)\cdot (\mathbf {x} ,1)}$ ${\displaystyle b}$ ${\displaystyle \mathbf {w} _{m+1}}$ ${\displaystyle 1}$ ${\displaystyle \mathbf {x} }$ $${\displaystyle f(\mathbf {x} )=h(\mathbf {w} \cdot \mathbf {x} )}$$

El valor binario (0 o 1) se utiliza para realizar una clasificación binaria como instancia positiva o negativa. Espacialmente, el sesgo cambia la posición (aunque no la orientación) del límite de decisión planar . ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$

En el contexto de las redes neuronales, un perceptrón es una neurona artificial que utiliza la función de paso de Heaviside como función de activación. El algoritmo del perceptrón también se denomina perceptrón de una sola capa , para distinguirlo de un perceptrón multicapa , que es un nombre inapropiado para una red neuronal más complicada. Como clasificador lineal, el perceptrón de una sola capa es la red neuronal de propagación hacia adelante más simple .

Poder de representación

Teoría de la información

Desde el punto de vista de la teoría de la información , un solo perceptrón con K entradas tiene una capacidad de 2K bits de información. ^[26] Este resultado se debe a Thomas Cover . ^[27]

Sea específicamente el número de formas de separar linealmente N puntos en K dimensiones, entonces, cuando K es grande, es muy cercano a uno cuando , pero muy cercano a cero cuando . En palabras, una unidad de perceptrón puede memorizar casi con certeza una asignación aleatoria de etiquetas binarias en N puntos cuando , pero casi con certeza no cuando . ${\displaystyle T(N,K)}$ $${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}}\right)&K<N\end{array}}\right.}$$ ${\displaystyle T(N,K)/2^{N}}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$

Función booleana

Cuando opera solo con entradas binarias, un perceptrón se denomina función booleana linealmente separable o función booleana de umbral. La secuencia de números de funciones booleanas de umbral en n entradas es OEIS A000609. El valor solo se conoce con exactitud hasta el caso, pero el orden de magnitud se conoce con bastante exactitud: tiene un límite superior y un límite inferior . ^[28] ${\displaystyle n=9}$ ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$ ${\displaystyle 2^{n^{2}-n\log _{2}n-O(n)}}$

Cualquier función de umbral lineal booleana se puede implementar con pesos enteros únicamente. Además, la cantidad de bits necesaria y suficiente para representar un único parámetro de peso entero es . ^[28] ${\displaystyle \Theta (n\ln n)}$

Teorema de aproximación universal

Un único perceptrón puede aprender a clasificar cualquier semiespacio, pero no puede resolver ningún vector linealmente no separable, como el problema booleano de " o exclusivo" (el famoso "problema XOR").

Una red de perceptrones con una capa oculta puede aprender a clasificar cualquier subconjunto compacto con una precisión arbitraria. De manera similar, también puede aproximarse a cualquier función continua con soporte compacto con una precisión arbitraria. Este es, en esencia, un caso especial de los teoremas de George Cybenko y Kurt Hornik .

Perceptrón local conjuntivamente

Los perceptrones (Minsky y Papert, 1969) estudiaron el tipo de redes de perceptrones necesarias para aprender varias funciones booleanas.

Consideremos una red de perceptrones con unidades de entrada, una capa oculta y una salida, similar a la máquina de perceptrones Mark I. Calcula una función booleana de tipo . Llaman a una función conjuntivamente local de orden , si y solo si existe una red de perceptrones tal que cada unidad en la capa oculta se conecta a, como máximo, unidades de entrada. ${\displaystyle n}$ ${\displaystyle f:2^{n}\to 2}$ ${\displaystyle k}$ ${\displaystyle k}$

Teorema. (Teorema 3.1.1): La función de paridad es conjuntivamente local de orden . ${\displaystyle n}$

Teorema. (Sección 5.5): La función de conexidad es conjuntivamente local de orden . ${\displaystyle \Omega (n^{1/2})}$

Algoritmo de aprendizaje para un perceptrón de una sola capa

Un diagrama que muestra un perceptrón que actualiza su límite lineal a medida que se agregan más ejemplos de entrenamiento

A continuación se muestra un ejemplo de un algoritmo de aprendizaje para un perceptrón de una sola capa con una sola unidad de salida. En el caso de un perceptrón de una sola capa con varias unidades de salida, dado que los pesos de una unidad de salida están completamente separados de los de las demás, se puede ejecutar el mismo algoritmo para cada unidad de salida.

En el caso de los perceptrones multicapa , donde existe una capa oculta, se deben utilizar algoritmos más sofisticados, como la retropropagación . Si la función de activación o el proceso subyacente que modela el perceptrón no es lineal , se pueden utilizar algoritmos de aprendizaje alternativos, como la regla delta , siempre que la función de activación sea diferenciable . No obstante, el algoritmo de aprendizaje descrito en los pasos siguientes suele funcionar, incluso en el caso de perceptrones multicapa con funciones de activación no lineales.

Cuando se combinan múltiples perceptrones en una red neuronal artificial, cada neurona de salida opera independientemente de todas las demás; por lo tanto, el aprendizaje de cada salida puede considerarse de forma aislada.

Definiciones

Primero definimos algunas variables:

• ${\displaystyle r}$es la tasa de aprendizaje del perceptrón. La tasa de aprendizaje es un número positivo que generalmente se elige como menor que 1. Cuanto mayor sea el valor, mayor será la probabilidad de volatilidad en los cambios de peso.
• ${\displaystyle y=f(\mathbf {z} )}$denota la salida del perceptrón para un vector de entrada . ${\displaystyle \mathbf {z} }$
• ${\displaystyle D=\{(\mathbf {x} _{1},d_{1}),\dots ,(\mathbf {x} _{s},d_{s})\}}$es el conjunto de entrenamiento de muestras, donde: ${\displaystyle s}$
  • ${\displaystyle \mathbf {x} _{j}}$es el vector de entrada dimensional. ${\displaystyle n}$
  • ${\displaystyle d_{j}}$es el valor de salida deseado del perceptrón para esa entrada.

Mostramos los valores de las características de la siguiente manera:

• ${\displaystyle x_{j,i}}$es el valor de la característica n del vector de entrada de entrenamiento n . ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle x_{j,0}=1}$.

Para representar los pesos:

• ${\displaystyle w_{i}}$es el valor n en el vector de peso , que se multiplicará por el valor de la característica de entrada n. ${\displaystyle i}$ ${\displaystyle i}$
• Porque , es efectivamente un sesgo que usamos en lugar de la constante de sesgo . ${\displaystyle x_{j,0}=1}$ ${\displaystyle w_{0}}$ ${\displaystyle b}$

Para mostrar la dependencia del tiempo de , usamos: ${\displaystyle \mathbf {w} }$

• ${\displaystyle w_{i}(t)}$es el peso en el momento ${\displaystyle i}$ ${\displaystyle t}$

Pasos

1. Inicializar los pesos. Los pesos se pueden inicializar en 0 o en un valor aleatorio pequeño. En el ejemplo siguiente, usamos 0.
2. Para cada ejemplo j en nuestro conjunto de entrenamiento D , realice los siguientes pasos sobre la entrada y la salida deseada : ${\displaystyle \mathbf {x} _{j}}$ ${\displaystyle d_{j}}$
   1. Calcular la salida real:

      ${\displaystyle {\begin{aligned}y_{j}(t)&=f[\mathbf {w} (t)\cdot \mathbf {x} _{j}]\\&=f[w_{0}(t)x_{j,0}+w_{1}(t)x_{j,1}+w_{2}(t)x_{j,2}+\dotsb +w_{n}(t)x_{j,n}]\end{aligned}}}$

   2. Actualizar los pesos:
      ${\displaystyle w_{i}(t+1)=w_{i}(t)\;{\boldsymbol {+}}\;r\cdot (d_{j}-y_{j}(t))x_{j,i}}$, para todas las características , es la tasa de aprendizaje . ${\displaystyle 0\leq i\leq n}$ ${\displaystyle r}$
3. Para el aprendizaje fuera de línea , el segundo paso puede repetirse hasta que el error de iteración sea menor que un umbral de error especificado por el usuario , o hasta que se haya completado un número predeterminado de iteraciones, donde s es nuevamente el tamaño del conjunto de muestra. ${\displaystyle {\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|}$ ${\displaystyle \gamma }$

El algoritmo actualiza los pesos después de cada muestra de entrenamiento en el paso 2b.

Convergencia de un perceptrón en un conjunto de datos linealmente separables

Ilustración de la convergencia del perceptrón. En la imagen, . Todos los puntos de datos tienen , ya que las muestras negativas son equivalentes a después de la reflexión a través del origen. A medida que avanza el aprendizaje, el vector de peso realiza un recorrido algo aleatorio en el espacio de pesos. Cada paso se aleja al menos 90 grados de su dirección actual, lo que aumenta su cuadrado de norma en como máximo . Cada paso suma en un punto en las muestras, y como todas las muestras tienen , el vector de peso debe moverse al menos en . Como la norma crece como pero el componente crece como , esto eventualmente obligaría al vector de peso a apuntar casi por completo en la dirección y, por lo tanto, lograr la convergencia. ${\displaystyle \gamma =0.01,R=1,r=1}$ ${\displaystyle y=+1}$ ${\displaystyle y=+1}$ ${\displaystyle R}$ ${\displaystyle w}$ ${\displaystyle x_{1}\geq 0.01}$ ${\displaystyle x_{1}}$ ${\displaystyle 0.01}$ ${\displaystyle {\sqrt {t}}}$ ${\displaystyle x_{1}}$ ${\displaystyle t}$ ${\displaystyle x_{1}}$

Un perceptrón único es un clasificador lineal . Solo puede alcanzar un estado estable si todos los vectores de entrada se clasifican correctamente. En caso de que el conjunto de entrenamiento D no sea linealmente separable , es decir, si los ejemplos positivos no se pueden separar de los ejemplos negativos mediante un hiperplano, entonces el algoritmo no convergería ya que no hay solución. Por lo tanto, si la separabilidad lineal del conjunto de entrenamiento no se conoce a priori, se debe utilizar una de las variantes de entrenamiento siguientes. El análisis detallado y las extensiones del teorema de convergencia se encuentran en el Capítulo 11 de Perceptrons (1969).

La separabilidad lineal se puede comprobar en el tiempo , donde es el número de puntos de datos y es la dimensión de cada punto. ^[29] ${\displaystyle \min(O(n^{d/2}),O(d^{2n}),O(n^{d-1}\ln n))}$ ${\displaystyle n}$ ${\displaystyle d}$

Si el conjunto de entrenamiento es linealmente separable, entonces se garantiza que el perceptrón convergerá después de cometer un número finito de errores. ^[30] El teorema está demostrado por Rosenblatt et al.

Teorema de convergencia del perceptrón  :  dado un conjunto de datos , tal que , y es linealmente separable por algún vector unitario , con margen : ${\textstyle D}$ ${\textstyle \max _{(x,y)\in D}\|x\|_{2}=R}$ ${\textstyle w^{*}}$ ${\textstyle \gamma }$ $${\displaystyle \gamma :=\min _{(x,y)\in D}y(w^{*}\cdot x)}$$

Luego, el algoritmo de aprendizaje del perceptrón 0-1 converge después de cometer como máximo errores, para cualquier tasa de aprendizaje y cualquier método de muestreo del conjunto de datos. ${\textstyle (R/\gamma )^{2}}$

La siguiente prueba simple se debe a Novikoff (1962). La idea de la prueba es que el vector de peso siempre se ajusta en una cantidad acotada en una dirección con la que tiene un producto escalar negativo y, por lo tanto, puede estar acotado por arriba por O ( √ t ) , donde t es el número de cambios en el vector de peso. Sin embargo, también puede estar acotado por abajo por O ( t ) porque si existe un vector de peso satisfactorio (desconocido), entonces cada cambio avanza en esta dirección (desconocida) en una cantidad positiva que depende solo del vector de entrada.

Prueba

Supongamos que en el paso , el perceptrón con peso comete un error en el punto de datos , luego se actualiza a . ${\textstyle t}$ ${\textstyle w_{t}}$ ${\textstyle (x,y)}$ ${\textstyle w_{t+1}=w_{t}+r(y-f_{w_{t}}(x))x}$

Si , el argumento es simétrico, entonces lo omitimos. ${\textstyle y=0}$

WLOG , , entonces , , y . ${\textstyle y=1}$ ${\textstyle f_{w_{t}}(x)=0}$ ${\textstyle f_{w^{*}}(x)=1}$ ${\textstyle w_{t+1}=w_{t}+rx}$

Por supuesto, tenemos separación con márgenes: Por lo tanto, $${\displaystyle w^{*}\cdot x\geq \gamma }$$
$${\displaystyle w^{*}\cdot w_{t+1}-w^{*}\cdot w_{t}=w^{*}\cdot (rx)\geq r\gamma }$$

Además, y dado que el perceptrón cometió un error, , y así $${\displaystyle \|w_{t+1}\|_{2}^{2}-\|w_{t}\|_{2}^{2}=\|w_{t}+rx\|_{2}^{2}-\|w_{t}\|_{2}^{2}=2r(w_{t}\cdot x)+r^{2}\|x\|_{2}^{2}}$$ ${\textstyle w_{t}\cdot x\leq 0}$
$${\displaystyle \|w_{t+1}\|_{2}^{2}-\|w_{t}\|_{2}^{2}\leq \|x\|_{2}^{2}\leq r^{2}R^{2}}$$

Desde que empezamos con , después de cometer errores, pero también ${\textstyle w_{0}=0}$ ${\textstyle N}$ $${\displaystyle \|w\|_{2}\leq {\sqrt {Nr^{2}R^{2}}}}$$
$${\displaystyle \|w\|_{2}\geq w\cdot w^{*}\geq Nr\gamma }$$

Combinando los dos, tenemos ${\textstyle N\leq (R/\gamma )^{2}}$

Dos clases de puntos y dos de los infinitos límites lineales que los separan. Aunque los límites forman ángulos casi rectos entre sí, el algoritmo del perceptrón no tiene forma de elegir entre ellos.

Si bien se garantiza que el algoritmo del perceptrón convergerá en alguna solución en el caso de un conjunto de entrenamiento linealmente separable, aún puede elegir cualquier solución y los problemas pueden admitir muchas soluciones de calidad variable. ^[31] El perceptrón de estabilidad óptima , hoy en día mejor conocido como la máquina de vectores de soporte lineal , fue diseñado para resolver este problema (Krauth y Mezard , 1987). ^[32]

Teorema del ciclo del perceptrón

Cuando el conjunto de datos no es linealmente separable, no hay forma de que un único perceptrón converja. Sin embargo, todavía tenemos ^[33]

Teorema de ciclado del perceptrón  :  si el conjunto de datos tiene solo un número finito de puntos, entonces existe un número límite superior , tal que para cualquier vector de peso inicial, todos los vectores de peso tienen una norma limitada por ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle w_{0}}$ ${\displaystyle w_{t}}$ ${\displaystyle \|w_{t}\|\leq \|w_{0}\|+M}$

Esto lo demuestra por primera vez Bradley Efron . ^[34]

Aprendiendo una función booleana

Considere un conjunto de datos donde son de , es decir, los vértices de un hipercubo n-dimensional centrado en el origen, y . Es decir, todos los puntos de datos con valores positivos tienen , y viceversa. Según el teorema de convergencia del perceptrón, un perceptrón convergería después de cometer, como máximo, errores. ${\displaystyle x}$ ${\displaystyle \{-1,+1\}^{n}}$ ${\displaystyle y=\theta (x_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle y=1}$ ${\displaystyle n}$

Si tuviéramos que escribir un programa lógico para realizar la misma tarea, cada ejemplo positivo muestra que una de las coordenadas es la correcta, y cada ejemplo negativo muestra que su complemento es un ejemplo positivo. Al recopilar todos los ejemplos positivos conocidos, finalmente eliminamos todas las coordenadas menos una, momento en el cual se aprende el conjunto de datos. ^[35]

Este límite es asintóticamente ajustado en términos del peor de los casos. En el peor de los casos, el primer ejemplo presentado es completamente nuevo y proporciona bits de información, pero cada ejemplo posterior diferiría mínimamente de los ejemplos anteriores y proporciona 1 bit cada uno. Después de los ejemplos, hay bits de información, lo que es suficiente para el perceptrón (con bits de información). ^[26] ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 2n}$ ${\displaystyle 2n}$

Sin embargo, no es estricto en términos de expectativa si los ejemplos se presentan de manera uniforme y aleatoria, ya que el primero daría bits, el segundo bits, y así sucesivamente, tomando los ejemplos en total. ^[35] ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle O(\ln n)}$

Variantes

El algoritmo de bolsillo con trinquete (Gallant, 1990) resuelve el problema de estabilidad del aprendizaje del perceptrón al mantener la mejor solución vista hasta el momento "en su bolsillo". El algoritmo de bolsillo luego devuelve la solución en el bolsillo, en lugar de la última solución. También se puede utilizar para conjuntos de datos no separables, donde el objetivo es encontrar un perceptrón con un pequeño número de clasificaciones erróneas. Sin embargo, estas soluciones aparecen puramente estocásticamente y, por lo tanto, el algoritmo de bolsillo no se acerca a ellas gradualmente en el curso del aprendizaje, ni se garantiza que aparezcan dentro de un número determinado de pasos de aprendizaje.

El algoritmo Maxover (Wendemuth, 1995) es "robusto" en el sentido de que convergerá independientemente del conocimiento (previo) de la separabilidad lineal del conjunto de datos. ^[36] En el caso de separabilidad lineal, resolverá el problema de entrenamiento, si se desea, incluso con una estabilidad óptima ( máximo margen entre las clases). Para conjuntos de datos no separables, devolverá una solución con un pequeño número de clasificaciones erróneas. En todos los casos, el algoritmo se acerca gradualmente a la solución en el curso del aprendizaje, sin memorizar estados previos y sin saltos estocásticos. La convergencia es hacia la optimalidad global para conjuntos de datos separables y hacia la optimalidad local para conjuntos de datos no separables.

El perceptrón votado (Freund y Schapire, 1999) es una variante que utiliza múltiples perceptrones ponderados. El algoritmo inicia un nuevo perceptrón cada vez que un ejemplo se clasifica incorrectamente, inicializando el vector de pesos con los pesos finales del último perceptrón. A cada perceptrón también se le asignará otro peso correspondiente a cuántos ejemplos clasifique correctamente antes de clasificar incorrectamente uno, y al final el resultado será una votación ponderada de todos los perceptrones.

En problemas separables, el entrenamiento del perceptrón también puede apuntar a encontrar el mayor margen de separación entre las clases. El llamado perceptrón de estabilidad óptima se puede determinar mediante esquemas iterativos de entrenamiento y optimización, como el algoritmo Min-Over (Krauth y Mezard, 1987) ^[32] o el AdaTron (Anlauf y Biehl, 1989)). ^[37] AdaTron utiliza el hecho de que el problema de optimización cuadrático correspondiente es convexo. El perceptrón de estabilidad óptima, junto con el truco del kernel , son los fundamentos conceptuales de la máquina de vectores de soporte .

El perceptrón utilizó además una capa de preprocesamiento de pesos aleatorios fijos, con unidades de salida con umbrales. Esto le permitió al perceptrón clasificar patrones analógicos, proyectándolos en un espacio binario . De hecho, para un espacio de proyección de dimensión suficientemente alta, los patrones pueden volverse linealmente separables. ${\displaystyle \alpha }$

Otra forma de resolver problemas no lineales sin utilizar múltiples capas es utilizar redes de orden superior (unidad sigma-pi). En este tipo de red, cada elemento del vector de entrada se extiende con cada combinación de pares de entradas multiplicadas (segundo orden). Esto se puede extender a una red de orden n .

Sin embargo, hay que tener en cuenta que el mejor clasificador no es necesariamente el que clasifica todos los datos de entrenamiento a la perfección. De hecho, si tuviéramos la restricción previa de que los datos provienen de distribuciones gaussianas equivariantes, la separación lineal en el espacio de entrada es óptima y la solución no lineal está sobreajustada .

Otros algoritmos de clasificación lineal incluyen Winnow , máquina de vectores de soporte y regresión logística .

Perceptrón multiclase

Al igual que la mayoría de las demás técnicas para entrenar clasificadores lineales, el perceptrón se generaliza de forma natural a la clasificación multiclase . En este caso, la entrada y la salida se extraen de conjuntos arbitrarios. Una función de representación de características asigna cada par de entrada/salida posible a un vector de características de valor real y dimensión finita. Como antes, el vector de características se multiplica por un vector de peso , pero ahora se utiliza la puntuación resultante para elegir entre muchas salidas posibles: ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x,y)}$ ${\displaystyle w}$

${\displaystyle {\hat {y}}=\operatorname {argmax} _{y}f(x,y)\cdot w.}$

El aprendizaje itera nuevamente sobre los ejemplos, predice un resultado para cada uno, deja los pesos sin cambios cuando el resultado previsto coincide con el objetivo y los cambia cuando no lo hace. La actualización se convierte en:

${\displaystyle w_{t+1}=w_{t}+f(x,y)-f(x,{\hat {y}}).}$

Esta formulación de retroalimentación multiclase se reduce al perceptrón original cuando es un vector de valor real, se elige entre , y . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \{0,1\}}$ ${\displaystyle f(x,y)=yx}$

Para ciertos problemas, las representaciones y características de entrada/salida se pueden elegir de modo que se puedan encontrar de manera eficiente incluso si se eligen de un conjunto muy grande o incluso infinito. ${\displaystyle \mathrm {argmax} _{y}f(x,y)\cdot w}$ ${\displaystyle y}$

Desde 2002, el entrenamiento del perceptrón se ha vuelto popular en el campo del procesamiento del lenguaje natural para tareas como el etiquetado de partes del discurso y el análisis sintáctico (Collins, 2002). También se ha aplicado a problemas de aprendizaje automático a gran escala en un entorno de computación distribuida . ^[38]

Referencias

1. 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 . S2CID  5885617.
2. Bishop, Christopher M. (2006). Reconocimiento de patrones y aprendizaje automático . Springer. ISBN 0-387-31073-8.
3. Hecht-Nielsen, Robert (1991). Neurocomputing (Reimpresión con correcciones de la edición). Reading (Massachusetts) Menlo Park (California) Nueva York [etc.]: Addison-Wesley. pág. 6, título de la figura 1.3. ISBN 978-0-201-09355-1.
4. Block, HD (1962-01-01). "El perceptrón: un modelo para el funcionamiento del cerebro. I" . Reseñas de física moderna . 34 (1): 123–135. Bibcode :1962RvMP...34..123B. doi :10.1103/RevModPhys.34.123. ISSN  0034-6861.
5. McCulloch, W; Pitts, W (1943). "Un cálculo lógico de ideas inmanentes en la actividad nerviosa". Boletín de biofísica matemática . 5 (4): 115–133. doi :10.1007/BF02478259.
6. Rosenblatt, Frank (1957). "El perceptrón: un autómata que percibe y reconoce" (PDF) . Informe 85-460-1 . Laboratorio Aeronáutico de Cornell.
7. Nilsson, Nils J. (2009). "4.2.1. Perceptrones". La búsqueda de la inteligencia artificial. Cambridge: Cambridge University Press. ISBN 978-0-521-11639-8.
8. O'Connor, Jack (21 de junio de 2022). "Algoritmo encubierto: un capítulo secreto en la historia temprana de la inteligencia artificial y las imágenes por satélite" . Revista internacional de inteligencia y contrainteligencia : 1–15. doi :10.1080/08850607.2022.2073542. ISSN  0885-0607. S2CID  249946000.
9. Rosenblatt, F. (1958). "El perceptrón: un modelo probabilístico para el almacenamiento y la organización de la información en el cerebro" . Psychological Review . 65 (6): 386–408. doi :10.1037/h0042519. ISSN  1939-1471. PMID  13602029.
10. Rosenblatt, Frank y CORNELL UNIV ITHACA NY. Programa de investigación de sistemas cognitivos. Informe técnico, Cornell University, 72, 1971.
11. Muerle, John Ludwig y CORNELL AERONAUTICAL LAB INC BUFFALO NY. Proyecto Para, Autómatas de percepción y reconocimiento . Cornell Aeronautical Laboratory, Incorporated, 1963.
12. Hay, John Cameron (1960). Manual del operador del perceptrón Mark I (Proyecto PARA) / (PDF) . Buffalo: Cornell Aeronautical Laboratory. Archivado desde el original (PDF) el 2023-10-27.
13. "Perceptrón, Mark I". Museo Nacional de Historia Estadounidense . Consultado el 30 de octubre de 2023 .
14. Anderson, James A.; Rosenfeld, Edward, eds. (2000). Talking Nets: Una historia oral de las redes neuronales. The MIT Press. doi :10.7551/mitpress/6626.003.0004. ISBN 978-0-262-26715-1.
15. Olazaran, Mikel (1996). "Un estudio sociológico de la historia oficial de la controversia de los perceptrones". Estudios sociales de la ciencia . 26 (3): 611–659. doi :10.1177/030631296026003005. JSTOR  285702. S2CID  16786738.
16. Principios de neurodinámica: Perceptrones y la teoría de los mecanismos cerebrales , por Frank Rosenblatt, Informe Número VG-1196-G-8, Cornell Aeronautical Laboratory, publicado el 15 de marzo de 1961. El trabajo reportado en este volumen ha sido llevado a cabo bajo el Contrato Nonr-2381 (00) (Proyecto PARA) en CAL y el Contrato Nonr-401(40), en la Universidad de Cornell.
17. Sejnowski, Terrence J. (2018). La revolución del aprendizaje profundo. MIT Press. pág. 47. ISBN 978-0-262-03803-4.
18. Rosenblatt, Frank (1962). “ Una descripción del perceptrón de Tobermory ”. Programa de investigación cognitiva. Informe n.º 4. Documentos técnicos recopilados, vol. 2. Editado por Frank Rosenblatt. Ithaca, NY: Universidad de Cornell.
19. Nagy, George. 1963. Diseños de sistemas y circuitos para el perceptrón de Tobermory . Informe técnico número 5, Programa de investigación de sistemas cognitivos, Universidad de Cornell, Ithaca, Nueva York.
20. Nagy, George. "Redes neuronales: ayer y hoy". IEEE Transactions on Neural Networks 2.2 (1991): 316-318.
21. Aizerman, MA; Braverman, EM; Rozonoer, 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.
22. Mohri, Mehryar; Rostamizadeh, Afshin (2013). "Límites de error del perceptrón". arXiv : 1305.0208 [cs.LG].
23. [1] Fundamentos del aprendizaje automático, MIT Press (Capítulo 8).
24. Cash, Sydney; Yuste, Rafael (1999). "Suma lineal de entradas excitatorias por neuronas piramidales CA1". Neuron . 22 (2): 383–394. doi : 10.1016/S0896-6273(00)81098-3 . PMID  10069343.
25. Liou, DR; Liou, J.-W.; Liou, C.-Y. (2013). Comportamientos de aprendizaje del perceptrón . Prensa iConcept. ISBN 978-1-477554-73-9.
26. MacKay, David (25 de septiembre de 2003). Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge University Press . pág. 483. ISBN 9780521642989.
27. Portada, Thomas M. (junio de 1965). "Propiedades geométricas y estadísticas de sistemas de desigualdades lineales con aplicaciones en el reconocimiento de patrones" . IEEE Transactions on Electronic Computers . EC-14 (3): 326–334. doi :10.1109/PGEC.1965.264137. ISSN  0367-7508.
28. Šíma, Jiří; Orponen, Pekka (1 de diciembre de 2003). "Computación de propósito general con redes neuronales: un estudio de los resultados teóricos de la complejidad". Computación neuronal . 15 (12): 2727–2778. doi :10.1162/089976603322518731. ISSN  0899-7667. PMID  14629867.
29. "Introducción al aprendizaje automático, capítulo 3: perceptrón". openlearninglibrary.mit.edu . Consultado el 27 de octubre de 2023 .
30. Novikoff, Albert J. (1963). "Sobre pruebas de convergencia para perceptrones". Oficina de Investigación Naval .
31. Bishop, Christopher M (17 de agosto de 2006). "Capítulo 4. Modelos lineales para la clasificación". Reconocimiento de patrones y aprendizaje automático . Springer Science+Business Media, LLC. pág. 194. ISBN 978-0387-31073-2.
32. Krauth, W.; Mezard, M. (1987). "Algoritmos de aprendizaje con estabilidad óptima en redes neuronales". Journal of Physics A: Mathematical and General . 20 (11): L745–L752. Bibcode :1987JPhA...20L.745K. doi :10.1088/0305-4470/20/11/013.
33. Block, HD; Levin, SA (1970). "Sobre la acotación de un procedimiento iterativo para resolver un sistema de desigualdades lineales". Actas de la American Mathematical Society . 26 (2): 229–235. doi : 10.1090/S0002-9939-1970-0265383-5 . ISSN  0002-9939.
34. Efron, Bradley. "El procedimiento de corrección del perceptrón en situaciones no separables". Rome Air Dev. Center Tech. Doc. Report (1964).
35. Simon, Herbert A.; Laird, John E. (13 de agosto de 2019). "Límites en la velocidad de consecución de conceptos". The Sciences of the Artificial, reedición de la tercera edición con una nueva introducción de John Laird (edición reeditada). Cambridge, Massachusetts Londres, Inglaterra: The MIT Press. ISBN 978-0-262-53753-7.
36. Wendemuth, A. (1995). "Aprender lo inaprendible". Journal of Physics A: Mathematical and General . 28 (18): 5423–5436. Bibcode :1995JPhA...28.5423W. doi :10.1088/0305-4470/28/18/030.
37. Anlauf, JK; Biehl, M. (1989). "El AdaTron: un algoritmo de perceptrón adaptativo". Europhysics Letters . 10 (7): 687–692. Bibcode :1989EL.....10..687A. doi :10.1209/0295-5075/10/7/014. S2CID  250773895.
38. McDonald, R.; Hall, K.; Mann, G. (2010). "Estrategias de entrenamiento distribuido para el perceptrón estructurado" (PDF) . Tecnologías del lenguaje humano: Conferencia anual de 2010 del Capítulo norteamericano de la ACL . Asociación de lingüística computacional. págs. 456–464.

Lectura adicional

• Aizerman, MA y Braverman, EM y Lev I. Rozonoer. 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, 1964.
• Rosenblatt, Frank (1958), El perceptrón: un modelo probabilístico para el almacenamiento y la organización de la información en el cerebro, Cornell Aeronautical Laboratory, Psychological Review, v65, n.º 6, págs. 386–408. doi :10.1037/h0042519.
• Rosenblatt, Frank (1962), Principios de neurodinámica. Washington, DC: Spartan Books.
• Minsky, ML y Papert, SA 1969. Perceptrones . Cambridge, MA: MIT Press.
• Gallant, SI (1990). Algoritmos de aprendizaje basados ​​en perceptrones. IEEE Transactions on Neural Networks, vol. 1, núm. 2, págs. 179–191.
• Olazaran Rodriguez, Jose Miguel. Una sociología histórica de la investigación en redes neuronales . Tesis doctoral. Universidad de Edimburgo, 1991.
• Mohri, Mehryar y Rostamizadeh, Afshin (2013). Límites de error del perceptrón arXiv:1305.0208, 2013.
• Novikoff, AB (1962). Sobre pruebas de convergencia en perceptrones. Simposio sobre la teoría matemática de los autómatas, 12, 615–622. Instituto Politécnico de Brooklyn.
• Widrow, B. , Lehr, MA, "30 años de redes neuronales adaptativas: perceptrón, madalina y retropropagación", Proc. IEEE , vol. 78, n.º 9, págs. 1415-1442, (1990).
• Collins, M. 2002. Métodos de entrenamiento discriminativo para modelos ocultos de Markov: teoría y experimentos con el algoritmo perceptrón en Actas de la Conferencia sobre métodos empíricos en procesamiento del lenguaje natural (EMNLP '02).
• Yin, Hongfeng (1996), Algoritmos y análisis basados ​​en perceptrones, Biblioteca Spectrum, Universidad Concordia, Canadá

Enlaces externos

• Un perceptrón implementado en MATLAB para aprender la función NAND binaria
• Capítulo 3 Redes ponderadas - el perceptrón y Capítulo 4 Aprendizaje perceptrónico de redes neuronales - Una introducción sistemática por Raúl Rojas ( ISBN 978-3-540-60505-8 ) 
• Historia de los perceptrones
• Matemáticas de los perceptrones multicapa
• Aplicación de un modelo de perceptrón mediante scikit-learn : https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html