perceptrón

Algoritmo de aprendizaje supervisado de clasificadores binarios.

En el aprendizaje automático , el perceptrón (o neurona de McCulloch-Pitts ) es un algoritmo para el 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 Mark I Perceptron, la primera implementación del algoritmo perceptrón. Estaba conectado a una cámara con fotocélulas de sulfuro de cadmio de 20×20 para generar una imagen de 400 píxeles. La principal característica visible es el panel de conexión sensorial a asociación, que establece diferentes combinaciones de características de entrada. A la derecha hay conjuntos de potenciómetros que implementaron los pesos adaptativos. ^{[2] : 213}

El perceptrón Mark 1, siendo 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 panel de conexión de asociación sensorial se encuentra detrás del panel cerrado a la derecha del operador. La letra "C" en el panel frontal es una visualización 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 era "parte de un esfuerzo previamente secreto de cuatro años del NPIC [ Centro Nacional de Interpretación Fotográfica de EE. UU .], desde 1963 hasta 1966, para desarrollar este algoritmo y convertirlo en una herramienta útil para la fotografía. -intérpretes". ^[8]

Rosenblatt describió los detalles del perceptrón en un artículo de 1958. ^[9] Su organización de un perceptrón se compone de 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ó de 1959 a 1970, ^[10] y el Contrato Nonr-2381(00) "Proyecto PARA" ("PARA" significa "Percepción y Reconocimiento Automata"), 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 estaba destinado a ser 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 Smithsonian de Historia Estadounidense . ^[13]

El perceptrón Mark I tiene 3 capas.

• Un conjunto de 400 fotocélulas dispuestas en una cuadrícula de 20x20, denominadas "unidades sensoriales" (unidades S) o "retina de entrada". Cada unidad S se puede conectar hasta 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 de perceptrones de tres capas perceptrón alfa , para distinguirla de otros modelos de perceptrones con los que experimentó. ^[7]

Las unidades S están conectadas a las unidades A aleatoriamente (según una tabla de números aleatorios) a través de un enchufe (ver foto), para "eliminar cualquier sesgo intencional particular en el perceptrón". Los pesos de conexión son fijos, no aprendidos. Rosenblatt se mantuvo firme 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 pareciera 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 el manual del operador. ^[12]

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

En una conferencia de prensa de 1958 organizada por la Marina estadounidense, Rosenblatt hizo declaraciones sobre el perceptrón que provocaron una acalorada controversia entre la incipiente comunidad de IA ; Basado en las declaraciones de Rosenblatt, The New York Times informó que el perceptrón es "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 neurodinámica (1962)

Rosenblatt describió sus experimentos con muchas variantes de la máquina Perceptrón en un libro Principios de neurodinámica (1962). El libro es una versión publicada del informe de 1961. ^[dieciséis]

Entre las variantes se encuentran:

• "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),
• Incorporar retardos de tiempo a las unidades de perceptrón, para permitir el procesamiento de datos secuenciales.
• Analizar 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 inicialmente el perceptrón parecía prometedor, rápidamente se demostró que no se podían entrenar para reconocer muchas clases de patrones. Esto provocó que el campo de la investigación de redes neuronales se estancara durante muchos años, antes de que se reconociera que una red neuronal feedforward con dos o más capas (también llamada perceptrón multicapa ) tenía mayor poder de procesamiento que los perceptrones con una capa (también llamado perceptrón de una sola capa). perceptrón de capa ).

Los perceptrones de una sola capa sólo son capaces de aprender patrones linealmente separables . ^[17] Para una tarea de clasificación con alguna función de activación de pasos, un solo nodo tendrá una sola línea que dividirá 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 serían inseparables.

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 sería válido 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. (Consulte la página sobre Perceptrones (libro) para obtener más información). Sin embargo, el texto de Minsky/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] Este texto fue reimpreso en 1987 como "Perceptrones - Edición ampliada" donde se muestran y corrigen algunos errores en el texto original.

Trabajo posterior

Rosenblatt continuó trabajando en perceptrones a pesar de la disminución de la financiación. El último intento fue Tobermory, construido entre 1961 y 1967, pensado 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 perceptrones especialmente diseñadas. ^[20] Murió en un accidente de navegación en 1971.

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

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

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

Los espacios de solución de los límites de decisión para todas las funciones binarias y los comportamientos de aprendizaje se estudian en ^{[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 de 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} )=\theta (\mathbf {w} \cdot \mathbf {x} +b)}$

donde es la función escalonada 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 lejos del origen y no depende de ningún valor de entrada. ${\displaystyle \theta }$ ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} \cdot \mathbf {x} }$ ${\displaystyle \sum _{i=1}^{m}w_{i}x_{i}}$

De manera equivalente, desde , 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 por 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} )=\theta (\mathbf {w} \cdot \mathbf {x} )}$$

El valor binario de (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 plano . ${\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 escalonada 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 feedforward 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]

Específicamente, sea el número de formas de separar linealmente N puntos en K dimensiones, entonces ${\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.}$$

K ${\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 únicamente 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 sólo se conoce exactamente hasta el caso, pero el orden de magnitud se conoce con bastante exactitud: tiene límite superior y 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 booleano se puede implementar solo con pesos enteros. Además, el número de bits necesarios y suficientes para representar un único parámetro de peso entero es . ^[28] ${\displaystyle \Theta (n\ln n)}$

Teorema de aproximación universal

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

Una red de perceptrones con una capa oculta puede aprender a clasificar cualquier subconjunto compacto de manera arbitrariamente cercana. De manera similar, también puede aproximarse arbitrariamente a cualquier función continua con soporte compacto . Éste es esencialmente un caso especial de los teoremas de George Cybenko y Kurt Hornik .

Perceptrón conjuntivamente local

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

Considere una red de perceptrones con unidades de entrada, una capa oculta y una salida, similar a la máquina Perceptrón Mark I. Calcula una función booleana de tipo . Llaman a una función conjuntivamente local de orden , si existe una red de perceptrones tal que cada unidad en la capa oculta se conecte como máximo a 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 conectividad 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 actualizando 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. Para un perceptrón de una sola capa con múltiples unidades de salida, dado que los pesos de una unidad de salida están completamente separados de los demás, se puede ejecutar el mismo algoritmo para cada unidad de salida.

Para 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 modelado por 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 que se describe en los pasos siguientes suele funcionar, incluso para 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 resultado se puede considerar 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 para que sea menor que 1. Cuanto mayor sea el valor, mayor será la posibilidad 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 enésima característica del enésimo vector de entrada de entrenamiento . ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle x_{j,0}=1}$.

Para representar los pesos:

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

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

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

Pasos

1. Inicialice los pesos. Los pesos se pueden inicializar a 0 o a un pequeño valor aleatorio. En el siguiente ejemplo, 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. Calcule la producción 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. Actualiza los pesos:
      ${\displaystyle w_{i}(t+1)=w_{i}(t)\;{\boldsymbol {+}}\;r\cdot (d_{j}-y_{j}(t))x_{j,i}}$, para todas las funciones , 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 separable

Ilustración de la convergencia del perceptrón. En la imagen, . Todos los puntos de datos tienen , ya que las muestras negativas equivalen a después de la reflexión a través del origen. A medida que avanza el aprendizaje, el vector de pesos realiza un recorrido algo aleatorio en el espacio de pesos. Cada paso está al menos a 90 grados de su dirección actual, aumentando así su cuadrado norma como máximo . Cada paso suma un punto en las muestras y, dado que todas las muestras tienen , el vector de peso debe moverse al menos . Dado que 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ía 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 solo perceptrón es un clasificador lineal . Sólo 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 pueden separarse de los ejemplos negativos mediante un hiperplano, entonces el algoritmo no convergería ya que no hay solución. Por lo tanto, si no se conoce a priori la separabilidad lineal del conjunto de entrenamiento, 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 probar 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 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 sencilla 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 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 debajo de 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 únicamente del vector de entrada.

Prueba

Supongamos que en el paso , el perceptrón con peso comete un error en el punto de datos y 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 , , luego , , 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:

$${\displaystyle w^{*}\cdot x\geq \gamma }$$

De este modo,

$${\displaystyle w^{*}\cdot w_{t+1}-w^{*}\cdot w_{t}=w^{*}\cdot (rx)\geq r\gamma }$$

También

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

y dado que el perceptrón cometió un error, y así ${\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, ${\textstyle w_{0}=0}$ ${\textstyle N}$

$${\displaystyle \|w\|_{2}\leq {\sqrt {Nr^{2}R^{2}}}}$$

pero también

$${\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 están casi en ángulo recto 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 más conocido como 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 solo perceptrón converja. Sin embargo, todavía tenemos ^[33]

Teorema del ciclo del perceptrón  :  si el conjunto de datos tiene solo un número finito de puntos, entonces existe un número de límite superior , tal que para cualquier vector de peso inicial, todo vector de peso tiene un límite normativo 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]

Aprender una función booleana

Considere un conjunto de datos de donde provienen , es decir, los vértices de un hipercubo de n dimensiones centrado en el origen, y . Es decir, todos los puntos de datos 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, eventualmente eliminamos todas las coordenadas menos una, momento en el que se aprende el conjunto de datos. ^[35]

Este límite es asintóticamente estrecho 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á mínimamente de los ejemplos anteriores y proporciona 1 bit cada uno. Después de los ejemplos, hay fragmentos de información que son suficientes para el perceptrón (con fragmentos de información). ^[26] ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 2n}$ ${\displaystyle 2n}$

Sin embargo, no es estricto en términos de expectativas si los ejemplos se presentan uniformemente al azar, 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 manteniendo "en su bolsillo" la mejor solución vista hasta ahora. Luego, el algoritmo de bolsillo devuelve la solución del 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 de forma puramente estocástica y, por lo tanto, el algoritmo de bolsillo no las aborda 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 linealmente separable, resolverá el problema de entrenamiento, si se desea, incluso con una estabilidad óptima ( margen máximo entre las clases). Para conjuntos de datos no separables, devolverá una solución con una pequeña cantidad de clasificaciones erróneas. En todos los casos, el algoritmo se acerca gradualmente a la solución en el transcurso del aprendizaje, sin memorizar estados anteriores y sin saltos estocásticos. La convergencia es hacia la optimización global para conjuntos de datos separables y hacia la optimización 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 erróneamente, inicializando el vector de pesos con los pesos finales del último perceptrón. A cada perceptrón también se le dará otro peso correspondiente a cuántos ejemplos clasifican correctamente antes de clasificar uno incorrectamente, y al final el resultado será un voto ponderado sobre 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 denominado perceptrón de estabilidad óptima puede determinarse 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ática correspondiente es convexo. El perceptrón de estabilidad óptima, junto con el truco del núcleo , 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 umbralizadas. Esto permitió al perceptrón clasificar patrones analógicos proyectándolos en un espacio binario . De hecho, para un espacio de proyección de dimensiones suficientemente altas, los patrones pueden llegar a ser 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 por 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 aquel que clasifica perfectamente todos los datos de entrenamiento. 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

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

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

El aprendizaje vuelve a iterar sobre los ejemplos, prediciendo un resultado para cada uno, dejando los pesos sin cambios cuando el resultado previsto coincide con el objetivo y cambiándolos cuando no lo hace. La actualización pasa a ser:

${\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 manera 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 de perceptrones 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 informático distribuido . ^[38]

Referencias

1. 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 . S2CID  5885617.
2. Obispo, Christopher M. (2006). Reconocimiento de patrones y aprendizaje automático . Saltador. ISBN 0-387-31073-8.
3. Hecht-Nielsen, Robert (1991). Neurocomputación (Reimpresión con correcciones ed.). Reading (Massachusetts) Menlo Park (California) Nueva York [etc.]: Addison-Wesley. pag. 6, pie de foto de la Figura 1.3. ISBN 978-0-201-09355-1.
4. Bloquear, HD (1 de enero de 1962). "El perceptrón: un modelo para el funcionamiento del cerebro. I" . Reseñas de Física Moderna . 34 (1): 123-135. doi :10.1103/RevModPhys.34.123. ISSN  0034-6861.
5. McCulloch, W; Pitts, W (1943). "Un cálculo lógico de ideas inmanentes a 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: Prensa de la Universidad de Cambridge. 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 de 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 organización de la información en el cerebro" . Revisión psicológica . 65 (6): 386–408. doi :10.1037/h0042519. ISSN  1939-1471.
10. Rosenblatt, Frank y CORNELL UNIV ITHACA NY. Programa de Investigación de Sistemas Cognitivos. Informe técnico, Universidad de Cornell, 72, 1971.
11. Muerle, John Ludwig y CORNELL AERONAUTICAL LAB INC BUFFALO NY. Proyecto Para, Autómatas de Percepción y Reconocimiento . Laboratorio Aeronáutico de Cornell, incorporado, 1963.
12. Hay, John Cameron (1960). Manual del operador del perceptrón Mark I (Proyecto PARA) / (PDF) . Búfalo: Laboratorio Aeronáutico de Cornell.
13. "Perceptrón, Mark I". Museo Nacional de Historia Americana . Consultado el 30 de octubre de 2023 .
14. Anderson, James A.; Rosenfeld, Edward, eds. (2000). Redes parlantes: una historia oral de las redes neuronales. La prensa del MIT. doi : 10.7551/mitpress/6626.003.0004. ISBN 978-0-262-26715-1.
15. Olazarán, 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 informado en este volumen se llevó a cabo bajo contrato. Nonr-2381 (00) (Proyecto PARA) en CAL y Contrato Nonr-401(40), en Cornell University.
17. Sejnowski, Terrence J. (2018). La revolución del aprendizaje profundo. Prensa del MIT. pag. 47.ISBN _ 978-0-262-03803-4.
18. Rosenblatt, Frank (1962). " Una descripción del perceptrón Tobermory ". Programa de Investigación Cognitiva. Informe No. 4. Artículos técnicos recopilados, vol. 2. Editado por Frank Rosenblatt. Ithaca, Nueva York: Universidad de Cornell.
19. Nagy, George. 1963. Diseños de sistemas y circuitos para el perceptrón 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: entonces y ahora". Transacciones IEEE en redes neuronales 2.2 (1991): 316-318.
21. Aizerman, MA; Braverman, EM; Rozonoer, 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.
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. Efectivo, Sídney; Yuste, Rafael (1999). "Suma lineal de entradas excitadoras de neuronas piramidales CA1". Neurona . 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. Prensa de la Universidad de Cambridge . pag. 483.ISBN _ 9780521642989.
27. Portada, Thomas M. (junio de 1965). "Propiedades geométricas y estadísticas de sistemas de desigualdades lineales con aplicaciones en reconocimiento de patrones" . Transacciones IEEE en computadoras electrónicas . CE-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.
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 de perceptrones". Oficina de Investigaciones Navales .
31. Obispo, Christopher M (17 de agosto de 2006). "Capítulo 4. Modelos lineales de clasificación". Reconocimiento de patrones y aprendizaje automático . Springer Ciencia+Business Media, LLC. pag. 194.ISBN _ 978-0387-31073-2.
32. Krauth, W.; Mezard, M. (1987). "Algoritmos de aprendizaje con estabilidad óptima en redes neuronales". Revista de Física A: Matemática y General . 20 (11): L745-L752. Código Bib : 1987JPhA...20L.745K. doi :10.1088/0305-4470/20/11/013.
33. Bloquear, HD; Levin, SA (1970). "Sobre la acotación de un procedimiento iterativo para resolver un sistema de desigualdades lineales". Actas de la Sociedad Matemática Estadounidense . 26 (2): 229–235. doi : 10.1090/S0002-9939-1970-0265383-5 . ISSN  0002-9939.
34. Efrón, Bradley. "El procedimiento de corrección del perceptrón en situaciones inseparables". Desarrollo aéreo de Roma. Centro Tecnológico. Doc. Reptar (1964).
35. Simón, Herbert A.; Laird, John E. (13 de agosto de 2019). "Límites a la velocidad de consecución del concepto". The Sciences of the Artificial, reedición de la tercera edición con una nueva introducción de John Laird (Reedición ed.). Cambridge, Massachusetts Londres, Inglaterra: The MIT Press. ISBN 978-0-262-53753-7.
36. Wendemuth, A. (1995). "Aprender lo inaprendible". Revista de Física A: Matemática y General . 28 (18): 5423–5436. Código Bib : 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". Cartas de Eurofísica . 10 (7): 687–692. Código bibliográfico : 1989EL.....10..687A. doi :10.1209/0295-5075/10/7/014. S2CID  250773895.
38. McDonald, R.; Salón, K.; Mann, G. (2010). "Estrategias de entrenamiento distribuido para el perceptrón estructurado" (PDF) . Tecnologías del lenguaje humano: la conferencia anual de 2010 del capítulo norteamericano de la ACL . Asociación de Lingüística Computacional. págs. 456–464.

Otras lecturas

• Aizerman, MA y Braverman, EM y Lev I. Rozonoer. 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, 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, Laboratorio Aeronáutico de Cornell, Psychoological Review, v65, No. 6, págs. doi :10.1037/h0042519.
• Rosenblatt, Frank (1962), Principios de neurodinámica. Washington, DC: Libros espartanos.
• Minsky, ML y Papert, SA 1969. Perceptrones . Cambridge, MA: MIT Press.
• Galán, SI (1990). Algoritmos de aprendizaje basados ​​en perceptrones. Transacciones IEEE en redes neuronales, vol. 1, núm. 2, págs. 179-191.
• Olazarán Rodríguez, José Miguel. Una sociología histórica de la investigación de redes neuronales . Tesis Doctoral. Universidad de Edimburgo, 1991.
• Mohri, Mehryar y Rostamizadeh, Afshin (2013). Límites de error de 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, Madaline y retropropagación", Proc. IEEE , vol 78, no 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 del perceptrón en Actas de la Conferencia sobre métodos empíricos en el procesamiento del lenguaje natural (EMNLP '02).
• Yin, Hongfeng (1996), Análisis y algoritmos basados ​​en perceptrones, Biblioteca de espectro, Universidad de Concordia, Canadá

enlaces externos

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