Perceptrón

Diagrama dun perceptrón con catro sinais de entrada.

O perceptrón é un dos algoritmos de aprendizaxe supervisada máis coñecidos dentro da disciplina do deep learning e da intelixencia artificial en xeral. Introducido por Frank Rosenblatt en 1957, serve como piar para a maior parte de arquitecturas de redes neuronais modernas. Considérase un clasificador lineal, é dicir, asigna un input (vector de números) a unha clase específica de saída. Entre as súas aplicacións no campo da aprendizaxe automática está o recoñecemento de patróns.

A arquitectura de perceptrón aséntase sobre a neurona M-P (Neurona de McCulloch e Pitts), considerada a primeira neurona artificial da historia.

Historia

Mark I Perceptron, a primeira implementación do algoritmo perceptrón.

Warren McCulloch e Walter Pitts inventaron a neurona M-P en 1943. O Mark I Perceptron foi a primeira implementación hardware do perceptrón, construído en 1957 por Frank Rosenblatt no Laboratorio Aeronáutico Cornell. A intención era aplicar o algoritmo de perceptrón para que fose posible usalo como ferramenta para interpretar fotografías. A creación da máquina foi levada a cabo con moito segredismo; de feito, non se revelou ao público ata 1960 nunha demostración. A NPIC (National Photographic Interpretation Center) estadounidense desenvolveu o Mark I Perceptron como un proxecto secreto desde 1963 ata 1966.

O propio Rosenblatt publicou en 1958 "O perceptrón: Un modelo probabilístico de almacenamento de información e organización cerebral", paper no que describe a organización do perceptrón en tres tipos de células, unidades ou neuronas:

• Al (proxección)
• All (asociación)
• R (resposta)

O paper trata de establecer unha relación entre a biofísica e a psicoloxía, especulando na forma en que a información se retén en memoria e como influencia o recoñecemento de patróns (aplicación directa do perceptrón) e o comportamento. O obxectivo final de Rosenblatt era a comprensión de sistemas cognitivos a través de técnicas estatísticas.

Mark I Perceptron

O mainframe IBM 704 (unha das primeiras computadoras con soporte hardware para operacións de punto flotante) recibiu unha implementación software co algoritmo perceptrón, pero o proxecto hardware Mark I Perceptron "Project PARA" para recoñecemento de imaxes foi probablemente a aplicación máis exitosa do perceptrón no momento.

Perceptrón elemental de Rosenblatt.

O Mark I Perceptron contaba tres tipos de unidades ou capas, seguindo o modelo proposto por Rosenblatt en 1958:

• Unidades-S (sensores ou input)
• Unidades-A (asociación)
• Unidades-R (resposta)

Respecto ás limitacións técnicas, as Unidades-S estaban limitadas a unha malla $20x20$, onde cada unha delas podía conectarse a 40 Unidades-A (análogo á conexión axón-dendrita nas neuronas biolóxicas). As 512 Unidades-A funcionaban como capa oculta (hidden layer), que conducían á capa final de saída con 8 perceptróns funcionando como Unidades-R.

Construción

Mark I Perceptron coa función de indentificar as letras do abecedario. Neste caso as Unidades-S encárganse de mostrar o input (letra "C").

A imaxe de 400 píxeles fórmase a través da malla $20x20$ do Mark I. A cámara conta con fotosensores de sulfuro de cadmio que se conectan cun taboleiro de enchufes que establece as diferentes configuracións das Unidades-S (input) no proceso de asociación. Os potenciómetros implementan os diferentes pesos de asociación entre as Unidades-A e Unidades-R. Este pesos varían no proceso de aprendizaxe coa axuda de motores eléctricos.

Funcionamento

As Unidades-S comenzan conectadas ás Unidades-A mediante valores ou "pesos" aleatorios. Rosenblatt insistíu no carácter aleatorio destas conexións, pois intentaba replicar o funcionamento da visión humana e creía que así se conectaba a retina coa corteza visual.Despois, un sistema eléctrico actualiza os pesos de asociación ata que conclúe o algoritmo.

Controversia

Rosenblatt deu a coñecer o perceptrón nunha conferencia de 1958 organizada pola Armada dos Estados Unidos. A comunidade da intelixencia artificial daquel momento recibíu a existencia da máquina como unha noticia sorprendente que abría novas posibilidades no campo das computadoras intelixentes.

É o embrión dunha futura computadora [o Mark I Perceptron] que os expertos da Armada consideran que será capaz de andar, falar, ver, escribir, reproducirse e ser consciente da súa propia existencia. The New York Times

A controversia concernente á existencia do perceptrón nunha etapa temperá do desenvolvemento dos computadores podería ser considerado como un dos primeiros grandes debates sociais e éticos dentro do campo de estudo da intelixencia artificial.

Precedente: neurona M-P

Nesta arquitectura neuronal recibíanse unha serie de entradas (inputs) de tipo binario $\{0,1\}$ coa intención de devolver unha resposta, tamén de tipo binario.

A neurona de McCulloch e Pitts estaba conformada polas seguintes partes:

1. Datos binarios de entrada. Características extraídas da pregunta a responder ou modelar. No caso da neurona M-P, é obrigatorio que se poidan responder con simple si/non.
2. Threshold. Valor limiar, determina a activación ou desactivación da neurona. A suma ponderada compárase con dito limiar, e o valor de threshold decide sobre a posible activación.
3. Función de adición. A neurona M-P comeza procesando os datos de entrada realizando unha adición. A función $z$ recibe os parámetros iniciais como un vector $x$ con $i$ compoñentes (cada un deles funciona como unha das entradas da neurona). A suma/adición de compoñentes do vector $x$ funciona como $z(x)\equiv \Sigma x_{i}$.
4. Función de activación. Computada a adición dos datos, a función de activación encárgase de devolver $1$ pasado certo limiar (o threshold) e $0$ noutros casos (heaviside step). O output (valor de salida) consiste no valor proporcionado pola función de activación. $f(x)={\begin{cases}1&{\text{se }}z(x)>=0\\0&{\text{se }}z(x)<0\end{cases}}$
5. Inhibidores e excitadores. Os excitadores activan a neurona e consisten en valores binarios $\{0,1\}$ que indican a presenza ou ausencia de entradas necesarias para xerar unha resposta. Os inhibidores desactivan ou, como o propio nome indica, inhiben a neurona. Tamén se representan con valores binarios.

Porta lóxica XOR.

As portas lóxicas sinxelas de tipo AND, OR e NOT resultan modelables pola neurona M-P xa que son linealmente separables. Con todo, portas lóxicas como a XOR non o son. É dicir, entre as limitacións da neurona M-P están:

• Valores binarios como entrada.
• Threshold definido manualmente.
• Entradas sen pesos asociados.
• Predicións só para problemas separables linealmente por un hiperplano (discriminación gráfica de elementos).

Definición

Sinapse neuronal.

O modelo biolóxico máis simple dun perceptrón é unha neurona e viceversa. O análogo biolóxico do perceptrón (a neurona) consiste en entradas coñecidas como dendritas acompañadas por saídas a modo de axóns. O sinal eléctrico coñecido como sinapse transmite información ao cerebro, pero o proceso completo carece de sentido se observamos unha neurona en particular. A especialización da labor dunha célula do sistema nervioso adquire valor cando se asocia con outras neuronas e forma unha rede.

O intercambio axón-dendrita establece esa asociación entre un par de neuronas, pero é a rede neural ao completo a que dá sentido e propósito á comunicación/predición transmitida na sinapse. Así, diríase que unha neurona singular é análoga en certa medida a un perceptrón de tipo simple (similar á neurona M-P). A conclusión de Frank Rosenblatt foi que eran necesarias neuronas de tipo complexo para modelar e responder a coñecemento de maior entidade, neuronas artificiais que requerían da incorporación dunha rede.

O perceptrón diferénciase notablemente da neurona M-P en que permite valores de entrada non binarios. Ademais, iso repercute en que as respostas non teñen que ser necesariamente binarias. O perceptrón como algoritmo componse de varias neuronas artificiais, cada unha delas funcionando como unidade lóxica.

Arquitectura

Capas de perceptrón.

Como rede composta por máis dunha neurona, a arquitectura de perceptrón exemplifica a construción dunha rede neural artificial. Cada neurona individual computa unha suma paramétrica das entradas recollidas no vector $x$. Estas unidades coñécense como TLU (Threshold Logic Unit) e son as encargadas de sumar as entradas contando cos pesos, a diferenza dunha neurona M-P.

A arquitectura tradicional dun perceptrón pódese dividir en tres compoñentes principais:

1. Capa de entrada (input layer). Nela recíbense os datos de entrada. Cada nodo desta capa representa unha característica dun conxunto de datos de entrada. Por exemplo, nunha clasificación de imaxes cada nodo da capa de entrada podería funcionar medindo a intensidade dun píxel.
2. Capa oculta (hidden layer). A maior parte do procesamento acontece na capa intermedia. Un perceptrón simple non ten capas ocultas, pero os perceptróns multicapa (MLP, Multilayer Perceptron) incluén unha ou máis. Cada nodo da capa oculta realiza unha suma ponderada das entradas, aplica unha función de activación e pasa o resulta á seguinte capa.
3. Capa de saída (output layer). Última capa da rede onde se produce a predición final. O número de nodos finais da capa corresponde ao número de posibles saídas do problema a modelar.

Formalización

O funcionamento de cada unidade lóxica ou neurona artificial (TLU) dentro da rede neural do perceptrón descríbese da seguinte maneira:

O vector $x$ almacena as entradas $x_{1},x_{2},\ldots ,x_{n}$, multiplicadas polo vector de pesos $w$.

Función de adición dun perceptrón. O resultado do sumatorio pasa a unha función de activación (neste caso denotada por $\varphi$) que determina o output $o$.

Deste modo, a función de adición $z$ será:

$z=\Sigma _{i=1}^{n}w_{i}*x_{i}+b$

• $w*x$ produto escalar.
• $b$ ou bias como sesgo, fixa un nivel mínimo de actividade (grado de "inhibición" da neurona).

En canto á función de activación $f(z)$, un exemplo sinxelo sería o heaviside step, é dicir, o "chanzo de Heaviside".

$f(z)={\begin{cases}1&{\text{se }}z\geq 0\\0&{\text{se }}z<0\end{cases}}$

Funcións como a ReLU (Rectified Linear Unit), sigmoide ou tanh utilízanse nas redes neuronais modernas, e son moito máis complexas que o "chanzo de Heaviside". Neste caso particular, discrimínase a saída a modo de problema de clasificación binario.

O termo de bias cumpre a función dun peso máis, de modo que pode denotarse como $w_{n+1}$. Deste modo:

$w*x+b=(w,b)*(x,1)$

Pode engadirse a coordenada $1$ ao vector de entrada $x$ para facilitar a notación.

Aprendizaxe

O adestramento dun perceptrón encárgase de actualizar sucesivamente os pesos $w_{i}$ e o bias $b$ para minimizar o erro entre a saída predita e a real. O algoritmo de descenso do gradiente optimiza tipicamente os parámetros. Entre as regras de aprendizaxe máis utilizadas está a regra delta.

Regra de actualización de pesos

O algoritmo de aprendizaxe característico dun perceptrón simple (ou perceptrón de 1 capa) funciona como se mostra a continuación:

• $N\leftarrow inputs\ de\ clase\ 0$
• $S\leftarrow inputs\ de\ clase\ 1$

Porta lóxica XOR resolta cun perceptrón.

$w$ inicialízase con valores aleatorios.

1. Mentres non converxencia, escoller $x\in N\cup Y$.
2. Se $x\in N$ AND $w*x\geq 0$, entón $w=w-x$. Volver a 1.
3. Se $x\in Y$ AND $w*x<0$, entón $w=w+x$. Volver a 1.
4. Final.

Desta forma actualízanse os pesos $w$ para que os produtos escalares $w*x$ manteñan a coherencia que esixe o perceptrón.

• Se unha entrada $x$ pertence á clase $N$ (inputs negativos), entón $w*x$ será menor que $0$.
• Se unha entrada $x$ pertence á clase $S$ (inputs positivos), entón $w*x$ será maior ou igual que $0$.

Taxa de aprendizaxe

O algoritmo de aprendizaxe pode empregar unha constante $\alpha$ para acelerar a actualización dos pesos. O proceso resulta idéntico para todas as neuronas, de modo que se pode estudar para unha célula illada como se ve a continuación:

• $x_{j}$ elemento $j$ do vector de entrada $x$.
• $w_{j}$ elemento $j$ do vector de pesos $w$.
• $\alpha$ constante de aprendizaxe $(0<\alpha <1)$.
• $y$ saída da neurona.
• $\delta$ saída esperada.

Aprendizaxe Tipo 1

Carece de $\alpha$:

$w(j)'=w(j)+(\delta -y)x(j)$

Aprendizaxe Tipo 2

Conta con $\alpha$:

$w(j)'=w(j)+\alpha (\delta -y)x(j)\,$

Iteracións

No algoritmo de perceptrón a aprendizaxe como tal consiste na actualización dos pesos $w$, de modo que, con ou sen $\alpha$, a diferenza entre o valor real de saída $y$ e o esperado $\delta$ será o factor máis importante $(\delta -y)$.

Para a actualización de $w$ de forma iterativa, cóntase con:

• $x^{i}$ vector de entrada na iteración $i$.
• $w^{i}$ vector de pesos na iteración $i$.
• $y^{i}$ saída da neurona na iteración $i$.

En cada iteración administrar $(x^{i},y^{i},w^{i})$ á regra de actualización e proceder con ou sen $\alpha$. A converxencia está asegurada nun número de iteracións finito sempre que os datos de partida sexan separables linealmente. De non ser así, é posible que o perceptrón atope unha solución, aínda que non estea asegurada a converxencia.

Converxencia

Supóñase un conxunto de datos de adestramento da forma $D_{n}=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}$ onde,

• Cada $x_{i}$ é un vector da mesma dimensión que $w$.
• $y_{i},i=1,\ldots ,n$ como output.

Para facilitar o desenvolvemento posterior, considérese a seguinte función de activación:

$f(z)={\begin{cases}1&{\text{se }}z>0\\-1&{\text{se }}z\leq 0\end{cases}}$.

Dise que un $D_{n}$ é linealmente separable se existen $w$, $w_{n+1}$ (é dicir, pesos e bias) que cumpran para todo $i$

$y_{i}(w^{T}*x_{i}+b)>0$,

o que faría que todas as predicións do conxunto de datos de adestramento foran correctas (o erro de adestramento sería 0).

Polo Teorema de Converxencia do Perceptrón, se $D_{n}$ é linealmente separable entón o algoritmo de perceptrón encontra un separador lineal.

Marxe de punto

A distancia dun punto $x$ respecto ao hiperplano formado por $w,w_{n+1}$ é

$w^{T}*x+w_{n+1} \over \lVert w\rVert$.

• A marxe dun punto $(x,y)$ respecto ao hiperplano $w,w_{n+1}$ é $y*{w^{T}*x+w_{n+1} \over \lVert w\rVert }$, cantidade só positiva cando o punto $x$ clasifícase como $y$ polo clasificador lineal do hiperplano.
• A marxe do conxunto de datos $D_{n}$ respecto ao hiperplano $w,w_{n+1}$ é $min_{i}{\Bigl (}y_{i}*{w^{T}*x_{i}+w_{n+1} \over \lVert w\rVert }{\Bigr )}$.

A marxe de $D_{n}$ será positiva se todos os puntos do conxunto están ben clasificados (de non estalo, a marxe dalgún punto sería negativa e tomaría o valor mínimo por baixo $0$). Nese caso (nunha correcta clasificación e só baixo ese suposto), a marxe de $D_{n}$ representa a distancia do hiperplano ao punto máis próximo.

Teorema de converxencia do perceptrón

Por simplicidade considérase que o hiperplano pasa pola orixe (óbviase $w_{n+1}$, o bias).

Se:

1. Existe $w^{*}$ tal que $y_{i}*{w^{*T}*x_{i} \over \lVert w^{*}\rVert }\geq \gamma$ para todo $i=1,\ldots ,n$ e algún $\gamma >0$.
2. Todos os exemplos teñen magnitude acotada: $\lVert x_{i}\rVert \leq R$ para todo $i=1,\ldots ,n$.

entón:

o algoritmo de perceptrón comete como moito $\left({\frac {R}{\gamma }}\right)^{2}$ erros e separa linealmente os datos.