Perceptron

Máquina Mark I 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.^:193 Os detalhes do hardware estão em um 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)

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.^[verificar] 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.

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.

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 ${\displaystyle T(N,K)}$ o número de maneiras de separar linearmente N pontos em K dimensões, então$${\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.}$$Quando K é grande, ${\displaystyle T(N,K)/2^{N}}$ está muito próximo de um quando ${\displaystyle N\leq 2K}$, mas muito próximo de zero quando ${\displaystyle 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 ${\displaystyle N\leq 2K}$, mas quase certamente não quando ${\displaystyle 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 ${\displaystyle n=9}$, mas a ordem de magnitude é conhecida com bastante precisão: tem limite superior ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$ e limite inferior ${\displaystyle 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 é ${\displaystyle \Theta (n\ln n)}$.

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

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 ${\displaystyle 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 ${\displaystyle f:2^{n}\to 2}$. Eles chamam uma função de conjuntivamente local de ordem ${\displaystyle k}$, se existe uma rede perceptron tal que cada unidade na camada oculta se conecta a no máximo ${\displaystyle k}$ unidades de entrada.

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

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

Definições

Primeiro, definimos algumas variáveis:

• ${\displaystyle 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.
• ${\displaystyle D=\{(\mathbf {x} _{1},d_{1}),\dots ,(\mathbf {x} _{s},d_{s})\}}$ é o conjunto de treinamento de ${\displaystyle s}$ amostras, onde:
  • ${\displaystyle \mathbf {x} _{j}}$ é o ${\displaystyle j}$-ésimo vetor de entrada do espaço euclidiano ${\displaystyle n}$-dimensional ${\displaystyle \mathbb {R} ^{n}}$.
  • ${\displaystyle 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:

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

Para representar os pesos:

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

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

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

Passos

Para aprendizado offline, a segunda etapa pode ser repetida até que o erro de iteração ${\displaystyle {\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|}$ seja menor que um limite de erro ${\displaystyle \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 ${\displaystyle d_{j}=y_{j}(t)}$.

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

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 ${\displaystyle \min(O(n^{d/2}),O(d^{2n}),O(n^{d-1}\ln n))}$, where ${\displaystyle n}$ is the number of data points, and ${\displaystyle 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.

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.

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

Isso foi provado primeiro por Bradley Efron.

Aprendendo uma função booleana

Considere um conjunto de dados onde os ${\displaystyle x}$ são de ${\displaystyle \{-1,+1\}^{n}}$, ou seja, os vértices de um hipercubo n-dimensional centrado na origem, e ${\displaystyle y=\theta (x_{i})}$. Ou seja, todos os pontos de dados com ${\displaystyle x_{i}}$ positivo têm ${\displaystyle y=1}$ e vice-versa. Pelo teorema da convergência do perceptron, um perceptron convergiria após cometer no máximo ${\displaystyle 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 ${\displaystyle n}$ bits de informação, mas cada exemplo subsequente diferiria minimamente dos exemplos anteriores e forneceria 1 bit cada. Após ${\displaystyle n+1}$ exemplos, há ${\displaystyle 2n}$ bits de informação, o que é suficiente para o perceptron (com ${\displaystyle 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 ${\displaystyle n}$ bits, o segundo ${\displaystyle n/2}$ bits e assim por diante, totalizando ${\displaystyle O(\ln n)}$ exemplos.

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 ${\displaystyle x}$ e a saída ${\displaystyle y}$ são extraídas de conjuntos arbitrários. Uma função de representação de características ${\displaystyle 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 ${\displaystyle w}$, mas agora a pontuação resultante é usada para escolher entre muitas saídas possíveis:

${\displaystyle {\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:

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

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

Para certos problemas, as representações de entrada/saída e as características podem ser escolhidas de modo que ${\displaystyle \mathrm {argmax} _{y}f(x,y)\cdot w}$ possa ser encontrado de forma eficiente, mesmo que ${\displaystyle 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.