Perceptron

Em aprendizado de máquina, o perceptron é um algoritmo para aprendizado supervisionado de classificadores binários. Um classificador binário é uma função que pode decidir se uma entrada, representada por um vetor de números, pertence ou não a uma classe específica. É um tipo de classificador linear, ou seja, um algoritmo de classificação que faz suas previsões com base em uma função preditora linear combinando um conjunto de pesos com o vetor de características.

História

Ver também: História da inteligência artificial § Perceptrons e primeiras redes neurais

Ficheiro:Mark I perceptron.jpeg

Máquina Mark I Perceptron, a primeira implementação do algoritmo do perceptron. Era conectada a uma câmera com 20×20 células fotossensíveis de sulfeto de cádmio para formar uma imagem de 400 pixels. A característica principal visível é o painel de conexões sensorial-associação, que define diferentes combinações de características de entrada. À direita estão conjuntos de potenciômetros que implementavam os pesos adaptativos.

O Mark 1 Perceptron, sendo ajustado por Charles Wightman (engenheiro de projeto do Mark I Perceptron). Unidades sensoriais à esquerda, unidades de associação no centro e painel de controle e unidades de resposta à extrema direita. O painel de conexões sensorial-associação está atrás do painel fechado à direita do operador. A letra "C" no painel frontal é uma exibição do estado atual da entrada sensorial.

O neurônio artificial e a rede neural artificial foram inventados em 1943 por Warren McCulloch e Walter Pitts em seu artigo seminal "A Logical Calculus of the Ideas Immanent in Nervous Activity".

Em 1957, Frank Rosenblatt estava no Cornell Aeronautical Laboratory. Ele simulou o perceptron em um IBM 704. Mais tarde, ele obteve financiamento do Information Systems Branch do Office of Naval Research dos Estados Unidos e do Rome Air Development Center para construir um computador personalizado, o Mark I Perceptron. Foi demonstrado publicamente pela primeira vez em 23 de junho de 1960. A máquina fazia "parte de um esforço secreto de quatro anos do NPIC [o National Photographic Interpretation Center dos EUA] de 1963 a 1966 para desenvolver este algoritmo em uma ferramenta útil para foto-intérpretes".

Rosenblatt descreveu os detalhes do perceptron em um artigo de 1958. Sua organização de um perceptron é construída com três tipos de células ("unidades"): S, A, R, que significam "sensorial", "associação" e "resposta". Ele apresentou no primeiro simpósio internacional sobre IA, Mechanisation of Thought Processes, que ocorreu em novembro de 1958.

O projeto de Rosenblatt foi financiado sob o Contrato Nonr-401(40) "Cognitive Systems Research Program", que durou de 1959 a 1970, e o Contrato Nonr-2381(00) "Project PARA" ("PARA" significa "Perceiving and Recognition Automata"), que durou de 1957 a 1963.

Em 1959, o Institute for Defense Analysis concedeu ao seu grupo um contrato de $10.000. Em setembro de 1961, o ONR concedeu mais $153.000 em contratos, com $108.000 comprometidos para 1962.

O gerente de pesquisa do ONR, Marvin Denicoff, afirmou que o ONR, em vez da ARPA, financiou o projeto Perceptron, porque era improvável que o projeto produzisse resultados tecnológicos no curto ou médio prazo. O financiamento da ARPA chega à ordem de milhões de dólares, enquanto o do ONR é da ordem de 10.000 dólares. Enquanto isso, o chefe do IPTO da ARPA, J.C.R. Licklider, estava interessado em métodos 'auto-organizáveis', 'adaptativos' e outros métodos de inspiração biológica na década de 1950; mas em meados da década de 1960, ele era abertamente crítico a estes, incluindo o perceptron. Em vez disso, ele favoreceu fortemente a abordagem de IA lógica de Simon e Newell.

Máquina Mark I Perceptron

Ver artigo principal: Mark I Perceptron

Organização de um cérebro biológico e de um perceptron

O perceptron foi concebido para ser uma máquina, e não um programa, e, embora sua primeira implementação tenha sido em software para o IBM 704, foi posteriormente implementado em hardware personalizado como o Mark I Perceptron com o nome de projeto "Project PARA", projetado para reconhecimento de imagens. A máquina está atualmente no Smithsonian National Museum of American History.

O Mark I Perceptron tinha três camadas. Uma versão foi implementada da seguinte forma:

• Uma matriz de 400 fotocélulas dispostas em uma grade 20x20, chamadas de "unidades sensoriais" (unidades S), ou "retina de entrada". Cada unidade S pode se conectar a até 40 unidades A.
• Uma camada oculta de 512 perceptrons, chamados de "unidades de associação" (unidades A).
• Uma camada de saída de oito perceptrons, chamados de "unidades de resposta" (unidades R).

Rosenblatt chamou essa rede perceptron de três camadas de alpha-perceptron, para distingui-la de outros modelos de perceptron com os quais ele experimentou.

As unidades S estão conectadas às unidades A aleatoriamente (de acordo com uma tabela de números aleatórios) através de um painel de conexões (ver foto), para "eliminar qualquer viés intencional particular no perceptron". Os pesos das conexões são fixos, não aprendidos. Rosenblatt era inflexível sobre as conexões aleatórias, pois acreditava que a retina estava conectada aleatoriamente ao córtex visual e queria que sua máquina perceptron se assemelhasse à percepção visual humana.

As unidades A estão conectadas às unidades R, com pesos ajustáveis codificados em potenciômetros, e as atualizações de peso durante o aprendizado eram realizadas por motores elétricos. Os detalhes do hardware estão em um manual do operador.

Componentes do Mark I Perceptron. Do manual do operador.

Em uma conferência de imprensa de 1958 organizada pela Marinha dos EUA, Rosenblatt fez declarações sobre o perceptron que causaram uma controvérsia acalorada entre a comunidade de IA incipiente; com base nas declarações de Rosenblatt, o The New York Times relatou que o perceptron era "o embrião de um computador eletrônico que [a Marinha] espera que será capaz de andar, falar, ver, escrever, se reproduzir e estar consciente de sua existência."

A Divisão de Fotografia da Agência Central de Inteligência, de 1960 a 1964, estudou o uso da máquina Mark I Perceptron para reconhecer alvos silhuetados de interesse militar (como aviões e navios) em fotos aéreas.

Principles of Neurodynamics (1962)

Rosenblatt descreveu seus experimentos com muitas variantes da máquina Perceptron em um livro Principles of Neurodynamics (1962). O livro é uma versão publicada do relatório de 1961.

Entre as variantes estão:

• "acoplamento cruzado" (conexões entre unidades dentro da mesma camada) possivelmente com loops fechados,
• "retroacoplamento" (conexões de unidades em uma camada posterior para unidades em uma camada anterior),
• perceptrons de quatro camadas onde as duas últimas camadas têm pesos ajustáveis (e, portanto, um perceptron multicamadas adequado),
• incorporação de atrasos de tempo às unidades do perceptron, para permitir o processamento de dados sequenciais,
• análise de áudio (em vez de imagens).

A máquina foi enviada da Cornell para o Smithsonian em 1967, sob uma transferência do governo administrada pelo Office of Naval Research.

Perceptrons (1969)

Ver artigo principal: Perceptrons (livro)

Embora o perceptron inicialmente parecesse promissor, rapidamente se provou que perceptrons não podiam ser treinados para reconhecer muitas classes de padrões. Isso fez com que o campo de pesquisa de redes neurais estagnasse por muitos anos, antes que se reconhecesse que uma rede neural feedforward com duas ou mais camadas (também chamada de perceptron multicamadas) tinha um poder de processamento maior do que perceptrons com uma camada (também chamada de perceptron de camada única).

Perceptrons de camada única são capazes apenas de aprender padrões linearmente separáveis. Para uma tarefa de classificação com alguma função de ativação degrau, um único nó terá uma única linha dividindo os pontos de dados que formam os padrões. Mais nós podem criar mais linhas divisórias, mas essas linhas devem ser combinadas de alguma forma para formar classificações mais complexas. Uma segunda camada de perceptrons, ou mesmo nós lineares, é suficiente para resolver muitos problemas de outra forma não separáveis.

Em 1969, um famoso livro intitulado Perceptrons de Marvin Minsky e Seymour Papert mostrou que era impossível para essas classes de rede aprender uma função XOR. Muitas vezes, acredita-se erroneamente que eles também conjecturaram que um resultado semelhante valeria para uma rede perceptron multicamadas. No entanto, isso não é verdade, pois tanto Minsky quanto Papert já sabiam que perceptrons multicamadas eram capazes de produzir uma função XOR. (Veja a página sobre Perceptrons (livro) para mais informações.) No entanto, o texto de Minsky e Papert, frequentemente mal citado, causou um declínio significativo no interesse e financiamento da pesquisa em redes neurais. Levou mais dez anos até que a pesquisa em redes neurais experimentasse um ressurgimento na década de 1980. Este texto foi reimpresso em 1987 como "Perceptrons - Expanded Edition", onde alguns erros no texto original são mostrados e corrigidos.

Trabalho subsequente

Rosenblatt continuou trabalhando em perceptrons apesar da diminuição do financiamento. A última tentativa foi Tobermory, construído entre 1961 e 1967, para reconhecimento de fala. Ocupava uma sala inteira. Tinha 4 camadas com 12.000 pesos implementados por núcleos magnéticos toroidais. Na época de sua conclusão, a simulação em computadores digitais tornou-se mais rápida do que as máquinas perceptron construídas para esse fim. Ele morreu em um acidente de barco em 1971.

Um programa de simulação para redes neurais foi escrito para IBM 7090/7094 e foi usado para estudar várias aplicações de reconhecimento de padrões, como reconhecimento de caracteres, rastros de partículas em fotografias de câmara de bolhas; fonemas, palavras isoladas e reconhecimento de fala contínuo; verificação de locutor; e mecanismos de atenção central para processamento de imagens.

Vista isométrica de Tobermory, Fase I

O algoritmo do perceptron kernel já foi introduzido em 1964 por Aizerman et al. Garantias de limites de margem foram dadas para o algoritmo Perceptron no caso geral não separável primeiro por Freund e Schapire (1998), e mais recentemente por Mohri e Rostamizadeh (2013) que estendem resultados anteriores e fornecem novos limites L1 mais favoráveis.

O perceptron é um modelo simplificado de um neurônio biológico. Embora a complexidade dos modelos de neurônio biológico seja frequentemente necessária para entender completamente o comportamento neural, a pesquisa sugere que um modelo linear semelhante ao perceptron pode produzir alguns comportamentos observados em neurônios reais.

Os espaços de solução das fronteiras de decisão para todas as funções binárias e comportamentos de aprendizado são estudados em.

Definição

Os pesos apropriados são aplicados às entradas, e a soma ponderada resultante é passada para uma função que produz a saída o.

No sentido moderno, o perceptron é um algoritmo para aprender um classificador binário chamado função limiar: uma função que mapeia sua entrada $\mathbf {x}$ (um vetor de valores reais) para um valor de saída $f(\mathbf {x} )$ (um único valor binário):

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

onde $h$ é a função degrau de Heaviside (onde uma entrada de ${\textstyle >0}$ produz saída 1; caso contrário, a saída é 0), $\mathbf {w}$ é um vetor de pesos de valores reais, $\mathbf {w} \cdot \mathbf {x}$ é o produto escalar ${\textstyle \sum _{i=1}^{m}w_{i}x_{i}}$, onde m é o número de entradas para o perceptron, e b é o viés. O viés desloca a fronteira de decisão para longe da origem e não depende de nenhum valor de entrada.

Equivalentemente, como $\mathbf {w} \cdot \mathbf {x} +b=(\mathbf {w} ,b)\cdot (\mathbf {x} ,1)$, podemos adicionar o termo de viés $b$ como outro peso $\mathbf {w} _{m+1}$ e adicionar uma coordenada $1$ a cada entrada $\mathbf {x}$, e então escrevê-lo como um classificador linear que passa pela origem:$$f(\mathbf {x} )=h(\mathbf {w} \cdot \mathbf {x} )$$

O valor binário de $f(\mathbf {x} )$ (0 ou 1) é usado para realizar a classificação binária em $\mathbf {x}$ como uma instância positiva ou negativa. Espacialmente, o viés desloca a posição (embora não a orientação) da fronteira de decisão planar.

No contexto das redes neurais, um perceptron é um neurônio artificial que usa a função degrau de Heaviside como função de ativação. O algoritmo do perceptron também é denominado perceptron de camada única, para distingui-lo de um perceptron multicamadas, que é um nome impróprio para uma rede neural mais complicada. Como um classificador linear, o perceptron de camada única é a rede neural feedforward mais simples.

Poder de representação

Teoria da informação

Do ponto de vista da teoria da informação, um único perceptron com K entradas tem uma capacidade de 2K bits de informação. Este resultado é devido a Thomas M. Cover.

Especificamente, seja $T(N,K)$ o número de maneiras de separar linearmente N pontos em K dimensões, então$$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.$$Quando K é grande, $T(N,K)/2^{N}$ está muito próximo de um quando $N\leq 2K$, mas muito próximo de zero quando $N>2K$. Em palavras, uma unidade perceptron pode quase certamente memorizar uma atribuição aleatória de rótulos binários em N pontos quando $N\leq 2K$, mas quase certamente não quando $N>2K$.

Função booleana

Quando opera apenas em entradas binárias, um perceptron é chamado de função booleana linearmente separável, ou função booleana limiar. A sequência de números de funções booleanas limiares em n entradas é OEIS A000609. O valor é conhecido exatamente apenas até o caso $n=9$, mas a ordem de magnitude é conhecida com bastante precisão: tem limite superior $2^{n^{2}-n\log _{2}n+O(n)}$ e limite inferior $2^{n^{2}-n\log _{2}n-O(n)}$.

Qualquer função limiar linear booleana pode ser implementada apenas com pesos inteiros. Além disso, o número de bits necessários e suficientes para representar um único parâmetro de peso inteiro é $\Theta (n\ln n)$.

Teorema da aproximação universal

Ver artigo principal: Teorema da aproximação universal

Um único perceptron pode aprender a classificar qualquer semi-espaço. Ele não pode resolver nenhum vetor linearmente não separável, como o problema exclusive-or booleano (o famoso "problema XOR").

Uma rede perceptron com uma camada oculta pode aprender a classificar qualquer subconjunto compacto arbitrariamente próximo. Da mesma forma, também pode aproximar qualquer função contínua de suporte compacto arbitrariamente próxima. Este é essencialmente um caso especial do teorema de George Cybenko e Kurt Hornik.

Perceptron conjuntivamente local

Ver artigo principal: Perceptrons (livro)

Perceptrons (Minsky e Papert, 1969) estudou o tipo de redes perceptron necessárias para aprender várias funções booleanas.

Considere uma rede perceptron com $n$ unidades de entrada, uma camada oculta e uma saída, semelhante à máquina Mark I Perceptron. Ela calcula uma função booleana do tipo $f:2^{n}\to 2$. Eles chamam uma função de conjuntivamente local de ordem $k$, se existe uma rede perceptron tal que cada unidade na camada oculta se conecta a no máximo $k$ unidades de entrada.

Teorema. (Teorema 3.1.1): A função paridade é conjuntivamente local de ordem $n$.

Teorema. (Seção 5.5): A função conectividade é conjuntivamente local de ordem $\Omega (n^{1/2})$.

Algoritmo de aprendizado para um perceptron de camada única

Um diagrama mostrando um perceptron atualizando sua fronteira linear à medida que mais exemplos de treinamento são adicionados

Abaixo está um exemplo de um algoritmo de aprendizado para um perceptron de camada única com uma única unidade de saída. Para um perceptron de camada única com múltiplas unidades de saída, como os pesos de uma unidade de saída são completamente separados dos das outras, o mesmo algoritmo pode ser executado para cada unidade de saída.

Para perceptrons multicamadas, onde existe uma camada oculta, algoritmos mais sofisticados, como retropropagação, devem ser usados. Se a função de ativação ou o processo subjacente sendo modelado pelo perceptron for não linear, algoritmos de aprendizado alternativos, como a regra delta, podem ser usados, desde que a função de ativação seja diferenciável. No entanto, o algoritmo de aprendizado descrito nas etapas abaixo geralmente funciona, mesmo para perceptrons multicamadas com funções de ativação não lineares.

Quando múltiplos perceptrons são combinados em uma rede neural artificial, cada neurônio de saída opera independentemente de todos os outros; assim, aprender cada saída pode ser considerado isoladamente.

Definições

Primeiro, definimos algumas variáveis:

• $r$ é a taxa de aprendizado do perceptron. A taxa de aprendizado é um número positivo geralmente escolhido como menor que 1. Quanto maior o valor, maior a chance de volatilidade nas mudanças de peso.
• $D=\{(\mathbf {x} _{1},d_{1}),\dots ,(\mathbf {x} _{s},d_{s})\}$ é o conjunto de treinamento de $s$ amostras, onde:
  • $\mathbf {x} _{j}$ é o $j$-ésimo vetor de entrada do espaço euclidiano $n$-dimensional $\mathbb {R} ^{n}$.
  • $d_{j}\in \{0,1\}$ é o valor de saída desejado do perceptron para essa entrada.

Mostramos os valores das características da seguinte forma:

• $x_{j,i}$ é o valor da $i$-ésima característica do $j$-ésimo vetor de entrada de treinamento.
• $x_{j,0}=1$.

Para representar os pesos:

• $w_{i}$ é o $i$-ésimo valor no vetor de pesos, a ser multiplicado pelo valor da $i$-ésima característica de entrada.
• Como $x_{j,0}=1$, o $w_{0}$ é efetivamente um viés que usamos em vez da constante de viés $b$.

Para mostrar a dependência temporal de $\mathbf {w}$, usamos:

• $w_{i}(t)$ é o peso $i$ no tempo $t$.

Passos

1. Inicialize os pesos. Os pesos podem ser inicializados com 0 ou com um pequeno valor aleatório. No exemplo abaixo, usamos 0. Defina o contador de tempo $t$ como 0.
2. Para cada exemplo j em nosso conjunto de treinamento D, execute as seguintes etapas sobre a entrada $\mathbf {x} _{j}$ e a saída desejada $d_{j}$:
   1. Calcule a saída com o vetor de pesos atual $\mathbf {w} (t)=(w_{0}(t),w_{1}(t),\dots ,w_{n}(t))$:

      ${\begin{aligned}y_{j}(t)&=h[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. Atualize os pesos:

      $w_{i}(t+1)=w_{i}(t)\;{\boldsymbol {+}}\;r\cdot (d_{j}-y_{j}(t))x_{j,i}$, para todas as características $0\leq i\leq n$, onde $r$ é a taxa de aprendizado.

   3. Incremente o contador de tempo: $t:=t+1$

Para aprendizado offline, a segunda etapa pode ser repetida até que o erro de iteração ${\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|$ seja menor que um limite de erro $\gamma$ especificado pelo usuário, ou até que um número predeterminado de iterações tenha sido concluído, onde s é novamente o tamanho do conjunto de amostras.

O algoritmo atualiza os pesos após cada amostra de treinamento na etapa 2b, embora se possa notar que os pesos permanecem inalterados sempre que $d_{j}=y_{j}(t)$.

Convergência de um perceptron em um conjunto de dados linearmente separável

Ilustração da convergência do perceptron. Na figura, $\gamma =0.01,R=1,r=1$. Todos os pontos de dados têm $y=+1$, uma vez que as amostras negativas são equivalentes a $y=+1$ após a reflexão através da origem. À medida que o aprendizado avança, o vetor de peso realiza uma caminhada um tanto aleatória no espaço dos pesos. Cada passo está a pelo menos 90 graus de distância de sua direção atual, aumentando assim sua norma ao quadrado em no máximo $R$. Cada passo adiciona a $w$ um ponto nas amostras e, como todas as amostras têm $x_{1}\geq 0.01$, o vetor de peso deve se mover ao longo de $x_{1}$ em pelo menos $0.01$. Como a norma cresce como ${\sqrt {t}}$ mas a componente $x_{1}$ cresce como $t$, isso acabaria forçando o vetor de peso a apontar quase inteiramente na direção $x_{1}$ e, assim, alcançar a convergência.

Um único perceptron é um classificador linear. Ele só pode atingir um estado estável se todos os vetores de entrada forem classificados corretamente. Caso o conjunto de treinamento D não seja linearmente separável, ou seja, se os exemplos positivos não podem ser separados dos exemplos negativos por um hiperplano, então o algoritmo não convergiria, pois não há solução. Portanto, se a separabilidade linear do conjunto de treinamento não for conhecida a priori, uma das variantes de treinamento abaixo deve ser usada. A análise detalhada e as extensões do teorema de convergência estão no Capítulo 11 de Perceptrons (1969).

Linear separability is testable in time $\min(O(n^{d/2}),O(d^{2n}),O(n^{d-1}\ln n))$, where $n$ is the number of data points, and $d$ is the dimension of each point.

Se o conjunto de treinamento for linearmente separável, então o perceptron é garantido para convergir após cometer um número finito de erros. O teorema é provado por Rosenblatt et al.

Teorema da convergência do perceptron
Dado um conjunto de dados $D$, tal que $\max _{(x,y)\in D}\|x\|_{2}=R$, e ele é linearmente separável por algum vetor unitário $w^{*}$, com margem $\gamma =\min _{(x,y)\in D}y(w^{*}\cdot x)$. Então, o algoritmo de aprendizado 0-1 do perceptron converge após cometer no máximo $(R/\gamma )^{2}$ erros, para qualquer taxa de aprendizado e qualquer método de amostragem do conjunto de dados.

A prova simples a seguir é devida a Novikoff (1962). A ideia da prova é que o vetor de peso é sempre ajustado por uma quantidade limitada em uma direção com a qual ele tem um produto escalar negativo e, portanto, pode ser limitado acima por O(√t), onde t é o número de alterações no vetor de peso. No entanto, também pode ser limitado abaixo por O(t) porque, se existe um vetor de peso satisfatório (desconhecido), então cada mudança faz progresso nessa direção (desconhecida) por uma quantidade positiva que depende apenas do vetor de entrada.

Prova
Suponha que na etapa $t$, o perceptron com peso $w_{t}$ cometa um erro no ponto de dados $(x,y)$, então ele atualiza para $w_{t+1}=w_{t}+r(y-f_{w_{t}}(x))x$.

Se $y=0$, o argumento é simétrico, então o omitimos.

Sem perda de generalidade, $y=1$, então $f_{w_{t}}(x)=0$, $f_{w^{*}}(x)=1$, e $w_{t+1}=w_{t}+rx$.

Por hipótese, temos separação com margens: $$w^{*}\cdot x\geq \gamma$$ Assim, $$w^{*}\cdot w_{t+1}-w^{*}\cdot w_{t}=w^{*}\cdot (rx)\geq r\gamma$$
Também $$\|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}$$ e como o perceptron cometeu um erro, $w_{t}\cdot x\leq 0$, e então $$\|w_{t+1}\|_{2}^{2}-\|w_{t}\|_{2}^{2}\leq r^{2}\|x\|_{2}^{2}\leq r^{2}R^{2}$$
Como começamos com $w_{0}=0$, após cometer $N$ erros, $$\|w\|_{2}\leq {\sqrt {Nr^{2}R^{2}}}$$ mas também $$\|w\|_{2}\geq w\cdot w^{*}\geq Nr\gamma$$
Combinando os dois, temos $N\leq (R/\gamma )^{2}$.

Duas classes de pontos e duas das infinitas fronteiras lineares que as separam. Mesmo que as fronteiras estejam em ângulos quase retos entre si, o algoritmo do perceptron não tem como escolher entre elas.

Embora o algoritmo do perceptron seja garantido para convergir para alguma solução no caso de um conjunto de treinamento linearmente separável, ele ainda pode escolher qualquer solução e os problemas podem admitir muitas soluções de qualidade variada. O perceptron de estabilidade ótima, hoje mais conhecido como máquina de vetores de suporte linear, foi projetado para resolver esse problema (Krauth and Mezard, 1987).

Teorema da ciclagem do perceptron

Quando o conjunto de dados não é linearmente separável, não há como um único perceptron convergir. No entanto, ainda temos

Teorema da ciclagem do perceptron
Se o conjunto de dados $D$ tem apenas um número finito de pontos, então existe um número limite superior $M$, tal que para qualquer vetor de peso inicial $w_{0}$ todo vetor de peso $w_{t}$ tem norma limitada por $\|w_{t}\|\leq \|w_{0}\|+M$

Isso foi provado primeiro por Bradley Efron.

Aprendendo uma função booleana

Considere um conjunto de dados onde os $x$ são de $\{-1,+1\}^{n}$, ou seja, os vértices de um hipercubo n-dimensional centrado na origem, e $y=\theta (x_{i})$. Ou seja, todos os pontos de dados com $x_{i}$ positivo têm $y=1$ e vice-versa. Pelo teorema da convergência do perceptron, um perceptron convergiria após cometer no máximo $n$ erros.

Se fôssemos escrever um programa lógico para executar a mesma tarefa, cada exemplo positivo mostra que uma das coordenadas é a correta, e cada exemplo negativo mostra que seu complemento é um exemplo positivo. Ao coletar todos os exemplos positivos conhecidos, acabamos eliminando todas as coordenadas, exceto uma, momento em que o conjunto de dados é aprendido.

Esse limite é assintoticamente restrito em termos do pior caso. No pior caso, o primeiro exemplo apresentado é totalmente novo e fornece $n$ bits de informação, mas cada exemplo subsequente diferiria minimamente dos exemplos anteriores e forneceria 1 bit cada. Após $n+1$ exemplos, há $2n$ bits de informação, o que é suficiente para o perceptron (com $2n$ bits de informação).

No entanto, não é restrito em termos de expectativa se os exemplos forem apresentados uniformemente ao acaso, uma vez que o primeiro forneceria $n$ bits, o segundo $n/2$ bits e assim por diante, totalizando $O(\ln n)$ exemplos.

Variantes

O algoritmo pocket com catraca (Gallant, 1990) resolve o problema de estabilidade do aprendizado do perceptron, mantendo a melhor solução vista até agora "em seu bolso". O algoritmo pocket retorna então a solução no bolso, em vez da última solução. Ele também pode ser usado para conjuntos de dados não separáveis, onde o objetivo é encontrar um perceptron com um pequeno número de classificações incorretas. No entanto, essas soluções aparecem puramente estocasticamente e, portanto, o algoritmo pocket não se aproxima delas gradualmente no decorrer do aprendizado, nem há garantia de que apareçam dentro de um determinado número de etapas de aprendizado.

O algoritmo Maxover (Wendemuth, 1995) é "robusto" no sentido de que convergirá independentemente do conhecimento (prévio) da separabilidade linear do conjunto de dados. No caso linearmente separável, ele resolverá o problema de treinamento – se desejado, até mesmo com estabilidade ótima (margem máxima entre as classes). Para conjuntos de dados não separáveis, ele retornará uma solução com um pequeno número computável de classificações incorretas. Em todos os casos, o algoritmo se aproxima gradualmente da solução no decorrer do aprendizado, sem memorizar estados anteriores e sem saltos estocásticos. A convergência é para a otimalidade global para conjuntos de dados separáveis e para a otimalidade local para conjuntos de dados não separáveis.

O Perceptron Votado (Freund and Schapire, 1999), é uma variante que usa vários perceptrons ponderados. O algoritmo inicia um novo perceptron toda vez que um exemplo é classificado incorretamente, inicializando o vetor de pesos com os pesos finais do último perceptron. Cada perceptron também receberá um peso adicional correspondente a quantos exemplos eles classificam corretamente antes de classificar incorretamente um, e no final a saída será um voto ponderado em todos os perceptrons.

Em problemas separáveis, o treinamento do perceptron também pode visar encontrar a maior margem de separação entre as classes. O chamado perceptron de estabilidade ótima pode ser determinado por meio de esquemas iterativos de treinamento e otimização, como o algoritmo Min-Over (Krauth and Mezard, 1987) ou o AdaTron (Anlauf and Biehl, 1989)). AdaTron usa o fato de que o problema de otimização quadrática correspondente é convexo. O perceptron de estabilidade ótima, juntamente com o kernel trick, são os fundamentos conceituais da máquina de vetores de suporte.

O $\alpha$-perceptron usava ainda uma camada de pré-processamento de pesos aleatórios fixos, com unidades de saída limitadas. Isso permitiu que o perceptron classificasse padrões analógicos, projetando-os em um espaço binário. De fato, para um espaço de projeção de dimensão suficientemente alta, os padrões podem se tornar linearmente separáveis.

Outra maneira de resolver problemas não lineares sem usar múltiplas camadas é usar redes de ordem superior (unidade sigma-pi). Nesse tipo de rede, cada elemento no vetor de entrada é estendido com cada combinação de pares de entradas multiplicadas (segunda ordem). Isso pode ser estendido para uma rede de ordem n.

Uma generalização do modelo perceptron é o Receptron que incorpora interações não lineares entre as entradas. Um único receptron é capaz de classificar funções booleanas não lineares.

No entanto, deve-se ter em mente que o melhor classificador não é necessariamente aquele que classifica perfeitamente todos os dados de treinamento. De fato, se tivéssemos a restrição prévia de que os dados vêm de distribuições gaussianas equi-variantes, a separação linear no espaço de entrada é ótima, e a solução não linear é superajustada.

Outros algoritmos de classificação linear incluem Winnow, máquina de vetores de suporte e regressão logística.

Perceptron multiclasse

Como a maioria das outras técnicas para treinar classificadores lineares, o perceptron se generaliza naturalmente para a classificação multiclasse. Aqui, a entrada $x$ e a saída $y$ são extraídas de conjuntos arbitrários. Uma função de representação de características $f(x,y)$ mapeia cada par possível de entrada/saída para um vetor de características real de dimensão finita. Como antes, o vetor de características é multiplicado por um vetor de peso $w$, mas agora a pontuação resultante é usada para escolher entre muitas saídas possíveis:

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

O aprendizado novamente itera sobre os exemplos, prevendo uma saída para cada um, deixando os pesos inalterados quando a saída prevista corresponde ao alvo e alterando-os quando não corresponde. A atualização se torna:

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

Essa formulação de feedback multiclasse se reduz ao perceptron original quando $x$ é um vetor de valor real, $y$ é escolhido de $\{0,1\}$ e $f(x,y)=yx$.

Para certos problemas, as representações de entrada/saída e as características podem ser escolhidas de modo que $\mathrm {argmax} _{y}f(x,y)\cdot w$ possa ser encontrado de forma eficiente, mesmo que $y$ seja escolhido de um conjunto muito grande ou mesmo infinito.

Desde 2002, o treinamento do perceptron se tornou popular no campo do processamento de linguagem natural para tarefas como etiquetagem de classes gramaticais e análise sintática (Collins, 2002). Também foi aplicado a problemas de aprendizado de máquina em larga escala em um ambiente de computação distribuída.

Implementação em Python

'''
	Este projeto esta disponivel no GiHub de Marcos castro de Sousa
	Implementação da rede neural Perceptron
	w = w + N * (d(k) - y) * x(k)
'''

import random, copy

class Perceptron:

	def __init__(self, amostras, saidas, taxa_aprendizado=0.1, epocas=1000, limiar=-1):

		self.amostras = amostras # todas as amostras
		self.saidas = saidas # saídas respectivas de cada amostra
		self.taxa_aprendizado = taxa_aprendizado # taxa de aprendizado (entre 0 e 1)
		self.epocas = epocas # número de épocas
		self.limiar = limiar # limiar
		self.num_amostras = len(amostras) # quantidade de amostras
		self.num_amostra = len(amostras[0]) # quantidade de elementos por amostra
		self.pesos = [] # vetor de pesos


	# função para treinar a rede
	def treinar(self):
		
		# adiciona -1 para cada uma das amostras
		for amostra in self.amostras:
			amostra.insert(0, -1)

		# inicia o vetor de pesos com valores aleatórios
		for i in range(self.num_amostra):
			self.pesos.append(random.random())

		# insere o limiar no vetor de pesos
		self.pesos.insert(0, self.limiar)

		# inicia o contador de epocas
		num_epocas = 0

		while True:

			erro = False # o erro inicialmente inexiste

			# para todas as amostras de treinamento
			for i in range(self.num_amostras):

				u = 0

				'''
					realiza o somatório, o limite (self.amostra + 1)
					é porque foi inserido o -1 para cada amostra
				'''
				for j in range(self.num_amostra + 1):
					u += self.pesos[j] * self.amostras[i][j]

				# obtém a saída da rede utilizando a função de ativação
				y = self.sinal(u)

				# verifica se a saída da rede é diferente da saída desejada
				if y != self.saidas[i]:

					# calcula o erro: subtração entre a saída desejada e a saída da rede
					erro_aux = self.saidas[i] - y

					# faz o ajuste dos pesos para cada elemento da amostra
					for j in range(self.num_amostra + 1):
						self.pesos[j] = self.pesos[j] + self.taxa_aprendizado * erro_aux * self.amostras[i][j]

					erro = True # ainda existe erro

			# incrementa o número de épocas
			num_epocas += 1

			# critério de parada é pelo número de épocas ou se não existir erro
			if num_epocas > self.epocas or not erro:
				break


	# função utilizada para testar a rede
	# recebe uma amostra a ser classificada e os nomes das classes
	# utiliza a função sinal, se é -1 então é classe1, senão é classe2
	def testar(self, amostra, classe1, classe2):

		# insere o -1
		amostra.insert(0, -1)

		# utiliza o vetor de pesos que foi ajustado na fase de treinamento
		u = 0
		for i in range(self.num_amostra + 1):
			u += self.pesos[i] * amostra[i]

		# calcula a saída da rede
		y = self.sinal(u)

		# verifica a qual classe pertence
		if y == -1:
			print('A amostra pertence a classe %s' % classe1)
		else:
			print('A amostra pertence a classe %s' % classe2)


	# função de ativação: degrau bipolar (sinal)
	def sinal(self, u):
		return 1 if u >= 0 else -1


print('\nA ou B?\n')

# amostras: um total de 4 amostras
amostras = [[0.1, 0.4, 0.7], [0.3, 0.7, 0.2], 
				[0.6, 0.9, 0.8], [0.5, 0.7, 0.1]]

# saídas desejadas de cada amostra
saidas = [1, -1, -1, 1]

# conjunto de amostras de testes
testes = copy.deepcopy(amostras)

# cria uma rede Perceptron
rede = Perceptron(amostras=amostras, saidas=saidas,	
						taxa_aprendizado=0.1, epocas=1000)

# treina a rede
rede.treinar()

# testando a rede
for teste in testes:
	rede.testar(teste, 'A', 'B')

Implementação em C#

 
using System;
using System.Linq;

namespace perceptron
{
    public class Perceptron
    {
        static readonly double[] w = new double[3];
        private readonly int[,] _matrizAprendizado = new int[4, 3];
        private double _net;

        Perceptron()
        {
             //tabela AND
            _matrizAprendizado[0, 0] = 0;
            _matrizAprendizado[0, 1] = 0;
            _matrizAprendizado[0, 2] = 0;

            _matrizAprendizado[1, 0] = 0;
            _matrizAprendizado[1, 1] = 1;
            _matrizAprendizado[1, 2] = 0;

            _matrizAprendizado[2, 0] = 1;
            _matrizAprendizado[2, 1] = 0;
            _matrizAprendizado[2, 2] = 0;

            _matrizAprendizado[3, 0] = 1;
            _matrizAprendizado[3, 1] = 1;
            _matrizAprendizado[3, 2] = 1;

            w[0] = 0;
            w[1] = 0;
            w[2] = 0;
        }

        public static void Main(string[] args)
        {
            //pesos antes do treinamento
            w.ToList().ForEach(x => Console.WriteLine(x + ","));

            Console.WriteLine("\n");

            //efetua-se o treinamento da rede
            new Perceptron().Treinar();

            Console.WriteLine("\n");

            //pesos ajustados após treinamento
            w.ToList().ForEach(x => Console.WriteLine(x + ","));

            //dados de entrada para rede treinada, 0 e 0 resulta em 0 (tabela and) -1 corresponde ao BIAS

            int[] amostra1 = { 0, 1, -1 }; // 0 e 1 -> 0 Classe B
            int[] amostra2 = { 1, 0, -1 }; // 1 e 0 -> 0 Classe B
            int[] amostra3 = { 0, 0, -1 }; // 0 e 0 -> 0 Classe B
            int[] amostra4 = { 1, 1, -1 }; // 1 e 1 -> 1 Classe A


            ClassificarAmostra(amostra1);
            ClassificarAmostra(amostra2);
            ClassificarAmostra(amostra3);
            ClassificarAmostra(amostra4);

            Console.ReadKey();
        }

        public static void ClassificarAmostra(int[] amostra)
        {
            //pesos encontrados após o treinamento
            int[] pesos = { 2, 1, 3 };

            //aplicação da separação dos dados linearmente após aprendizado
            var u = amostra.Select((t, k) => pesos[k] * t).Sum();

            var y = LimiarAtivacao(u);

            Console.WriteLine(y > 0 ? "Amostra da classe A >= 0" : "HelloWorld < 0");
        }

        private static int LimiarAtivacao(double u)
        {
            return (u >= 0) ? 1 : 0;
        }

        int Executar(int x1, int x2)
        {
            _net = (x1 * w[0]) + (x2 * w[1]) + ((-1) * w[2]);

            return (_net >= 0) ? 1 : 0;
        }

        public void Treinar()
        {
            var treinou = true;

            for (var i = 0; i < _matrizAprendizado.GetLength(0); i++)
            {
                var saida = Executar(_matrizAprendizado[i, 0], _matrizAprendizado[i, 1]);

                if (saida != _matrizAprendizado[i, 2])
                {
                    CorrigirPeso(i, saida);

                    treinou = false;
                }
            }

            if (!treinou)
                Treinar();
        }

        void CorrigirPeso(int i, int saida)
        {
            w[0] = w[0] + (1 * (_matrizAprendizado[i, 2] - saida) * _matrizAprendizado[i, 0]);
            w[1] = w[1] + (1 * (_matrizAprendizado[i, 2] - saida) * _matrizAprendizado[i, 1]);
            w[2] = w[2] + (1 * (_matrizAprendizado[i, 2] - saida) * (-1));
        }
    }
}

Implementação em Ruby

  #
 # Classe PERCEPTRON responsável para aprendizado e resolução da tabela AND
 #

class Perceptron 

  def initialize
    # pesos sinápticos [0] entrada 1, [1] entrada 2, [3]BIAS
    @w   = []

    # variável responsável pelo somatório(rede).
    @net = 0

    # variavél responsável pelo número máximo de épocas
    @epocasMax = 30

    # variável responsável pela contagem das épocas durante o treinamento
    @count      = 0

    # declara o vetor da matriz de aprendizado
    @matriz_aprendizado = []

    self.inicia_matriz
  end

  def inicia_matriz
    # Primeiro valor
    @matriz_aprendizado[0]    = []
    @matriz_aprendizado[0][0] = 0; # entrada 1
    @matriz_aprendizado[0][1] = 0; # entrada 2
    @matriz_aprendizado[0][2] = 0; # valor esperado

    # Segundo Valor
    @matriz_aprendizado[1]    = []
    @matriz_aprendizado[1][0] = 0; # entrada 1
    @matriz_aprendizado[1][1] = 1; # entrada 2
    @matriz_aprendizado[1][2] = 0; # valor esperado

    # terceiro valor
    @matriz_aprendizado[2]    = []
    @matriz_aprendizado[2][0] = 1; # entrada 1
    @matriz_aprendizado[2][1] = 0; # entrada 2
    @matriz_aprendizado[2][2] = 0; # valor esperado

    # quarto valor
    @matriz_aprendizado[3]    = []
    @matriz_aprendizado[3][0] = 1; # entrada 1
    @matriz_aprendizado[3][1] = 1; # entrada 2
    @matriz_aprendizado[3][2] = 1; # valor esperado
    
    # inicialização dos pesos sinápticos

    # Peso sináptico para primeira entrada.
    @w[0] = 0;
    # Peso sináptico para segunda entrada.
    @w[1] = 0;
    # Peso sináptico para o BIAS
    @w[2] = 0;
  end

  # Método responsávelpelo somatório e a função de ativação.
  def executar(x1, x2)
    # Somatório (NET)
    @net = (x1 * @w[0]) + (x2 * @w[1]) + ((-1) * @w[2]);

    # Função de Ativação
    return 1 if (@net >= 0) 

    return 0;
  end

  # Método para treinamento da rede
  def treinar() 
    # variavel utilizada responsável pelo controlede treinamento recebefalso
    treinou = true;
    
    # varável responsável para receber o valor da saída (y)
    saida   = nil;

    # laço usado para fazer todas as entradas
    @matriz_aprendizado.length.times do |i|
      
      # A saída recebe o resultado da rede que no caso é 1 ou 0
      saida = self.executar(@matriz_aprendizado[i][0], @matriz_aprendizado[i][1]);
     
      if (saida != @matriz_aprendizado[i][2]) 
        # Caso a saída seja diferente do valor esperado
        
        # os pesos sinápticos serão corrigidos
        self.corrigirPeso(i, saida);

        # a variavél responsável pelo controlede treinamento recebe falso
        treinou = false;
      end
    end

    # acrescenta uma época
    @count+=1;

    # teste se houve algum erro duranteo treinamento e o número de epocas
    #é menor qe o definido
    if(not treinou and (@count < @epocasMax))
      # chamada recursiva do método
      self.treinar();
    end
  end    # fim do método para treinamento

  # Método para a correção de pesos
  def corrigirPeso(i, saida) 
    @w[0] = @w[0] + (1 * (@matriz_aprendizado[i][2] - saida) * @matriz_aprendizado[i][0]);
    @w[1] = @w[1] + (1 * (@matriz_aprendizado[i][2] - saida) * @matriz_aprendizado[i][1]);
    @w[2] = @w[2] + (1 * (@matriz_aprendizado[i][2] - saida) * (-1));
  end
end

Implementação em Java

 
 /*
 * Classe PERCEPTRON responsável para aprendizado e resolução da tabela AND
 */

public class Perceptron {

    // pesos sinápticos [0] entrada 1, [1] entrada 2, [3]BIAS
    private double[] w = new double[3];

    // variável responsável pelo somatório(rede).
    private double NET = 0;

    // variavél responsável pelo número máximo de épocas
    private final int epocasMax = 30;

    // variável responsável pela contagem das épocas durante o treinamento
    private int count = 0;

    // declara o vetor da matriz de aprendizado
    private int[][] matrizAprendizado = new int[4][3];

    // MÉTODO DE RETORNO DO CONTADOR
    public int getCount(){

      return this.count;

    }
 // metodo de inicialização inicia o vetor da matriz de aprendizado
  Perceptron() {

    // Primeiro valor
    this.matrizAprendizado[0][0] = 0; // entrada 1
    this.matrizAprendizado[0][1] = 0; // entrada 2
    this.matrizAprendizado[0][2] = 0; // valor esperado

    // Segundo Valor
    this.matrizAprendizado[1][0] = 0; // entrada 1
    this.matrizAprendizado[1][1] = 1; // entrada 2
    this.matrizAprendizado[1][2] = 0; // valor esperado

    // terceiro valor
    this.matrizAprendizado[2][0] = 1; // entrada 1
    this.matrizAprendizado[2][1] = 0; // entrada 2
    this.matrizAprendizado[2][2] = 0; // valor esperado

    // quarto valor
    this.matrizAprendizado[3][0] = 1; // entrada 1
    this.matrizAprendizado[3][1] = 1; // entrada 2
    this.matrizAprendizado[3][2] = 1; // valor esperado
    
    // inicialização dos pesos sinápticos

    // Peso sináptico para primeira entrada.
    w[0] = 0;
    // Peso sináptico para segunda entrada.
    w[1] = 0;
    // Peso sináptico para o BIAS
    w[2]= 0;
       
}

  // Método responsávelpelo somatório e a função de ativação.
    int executar(int x1, int x2) {

        // Somatório (NET)
        NET = (x1 * w[0]) + (x2 * w[1]) + ((-1) * w[2]);

        // Função de Ativação
        if (NET >= 0) {
            return 1;
        }
        return 0;
    }

    // Método para treinamento da rede
    public void treinar() {

        // variavel utilizada responsável pelo controlede treinamento recebefalso
        boolean treinou= true;
        // varável responsável para receber o valor da saída (y)
        int saida;

        // laço usado para fazer todas as entradas
        for (int i = 0; i < matrizAprendizado.length; i++) {
            // A saída recebe o resultado da rede que no caso é 1 ou 0
            saida = executar(matrizAprendizado[i][0], matrizAprendizado[i][1]);
            
           
            if (saida != matrizAprendizado[i][2]) {
                // Caso a saída seja diferente do valor esperado
                
                // os pesos sinápticos serão corrigidos
                corrigirPeso(i, saida);
                // a variavél responsável pelo controlede treinamento recebe falso
                treinou = false;

            }
        }
        // acrescenta uma época
        this.count++;

        // teste se houve algum erro duranteo treinamento e o número de epocas
        //é menor qe o definido
        if((treinou == false) && (this.count < this.epocasMax)) {
            // chamada recursiva do método
            treinar();

        }

    }    // fim do método para treinamento

    // Método para a correção de pesos
    void corrigirPeso(int i, int saida) {

        w[0] = w[0] + (1 * (matrizAprendizado[i][2] - saida) * matrizAprendizado[i][0]);
        w[1] = w[1] + (1 * (matrizAprendizado[i][2] - saida) * matrizAprendizado[i][1]);
        w[2] = w[2] + (1 * (matrizAprendizado[i][2] - saida) * (-1));
}}

Ver também

• Redes neurais artificiais
• Retropropagação

Leitura adicional

• Aizerman, M. A. and Braverman, E. M. and Lev I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821–837, 1964.
• Rosenblatt, Frank (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386–408. doi:10.1037/h0042519.
• Rosenblatt, Frank (1962), Principles of Neurodynamics. Washington, DC: Spartan Books.
• Minsky, M. L. and Papert, S. A. 1969. Perceptrons. Cambridge, MA: MIT Press.
• Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
• Olazaran Rodriguez, Jose Miguel. A historical sociology of neural network research. PhD Dissertation. University of Edinburgh, 1991.
• Mohri, Mehryar and Rostamizadeh, Afshin (2013). Perceptron Mistake Bounds arXiv:1305.0208, 2013.
• Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615–622. Polytechnic Institute of Brooklyn.
• Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415–1442, (1990).
• Collins, M. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with the perceptron algorithm in Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02).
• Yin, Hongfeng (1996), Perceptron-Based Algorithms and Analysis, Spectrum Library, Concordia University, Canada

Ligações externas

• Um Perceptron implementado em MATLAB para aprender a função NAND binária Arquivado em 2012-11-06 no Wayback Machine
• Capítulo 3 Redes ponderadas - o perceptron e capítulo 4 Aprendizado do perceptron de Neural Networks - A Systematic Introduction de Raúl Rojas (ISBN 978-3-540-60505-8)
• História dos perceptrons
• Matemática dos perceptrons multicamadas
• Aplicando um modelo perceptron usando scikit-learn - https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html