Perceptron - Perceptron

No aprendizado de máquina , o perceptron é um algoritmo de 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 alguma 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

Máquina Mark I Perceptron, a primeira implementação do algoritmo perceptron. Ele foi conectado a uma câmera com fotocélulas de sulfeto de cádmio 20 × 20 para fazer uma imagem de 400 pixels. O principal recurso visível é um painel de patch que define diferentes combinações de recursos de entrada. À direita, arranjos de potenciômetros que implementaram os pesos adaptativos.

O algoritmo perceptron foi inventado em 1958 no Laboratório Aeronáutico Cornell por Frank Rosenblatt , financiado pelo Escritório de Pesquisa Naval dos Estados Unidos .

O perceptron foi planejado para ser uma máquina, ao invés de um programa, e embora sua primeira implementação tenha sido em software para o IBM 704 , ele foi subsequentemente implementado em hardware customizado como o "Mark 1 perceptron". Essa máquina foi projetada para o reconhecimento de imagens : tinha um conjunto de 400 fotocélulas , conectadas aleatoriamente aos "neurônios". Os pesos foram codificados em potenciômetros e as atualizações de peso durante o aprendizado foram realizadas por motores elétricos.

Em uma entrevista coletiva em 1958 organizada pela Marinha dos Estados Unidos, Rosenblatt fez declarações sobre o perceptron que causou uma controvérsia acalorada entre a comunidade de IA incipiente ; com base nas declarações de Rosenblatt, o New York Times relatou que o perceptron é "o embrião de um computador eletrônico que [a Marinha] espera ser capaz de andar, falar, ver, escrever, se reproduzir e ter consciência de sua existência".

Embora o perceptron inicialmente parecesse promissor, foi rapidamente provado que os 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 de ser reconhecido que uma rede neural feedforward com duas ou mais camadas (também chamada de perceptron multicamadas ) tinha maior poder de processamento do que perceptrons com uma camada (também chamada de single- camada perceptron ).

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 de etapa, 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 de alguma forma ser combinadas para formar classificações mais complexas. Uma segunda camada de perceptrons, ou mesmo nós lineares, são suficientes para resolver muitos problemas não separáveis ​​de outra forma.

Em 1969, um famoso livro intitulado Perceptrons, de Marvin Minsky e Seymour Papert, mostrou que era impossível para essas classes de rede aprenderem uma função XOR . Muitas vezes, acredita-se (incorretamente) que eles também conjeturaram que um resultado semelhante seria válido 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. (Consulte a página sobre Perceptrons (livro) para obter mais informações.) No entanto, o texto frequentemente miscitado de Minsky / Papert causou um declínio significativo no interesse e no financiamento da pesquisa de redes neurais. Demorou mais dez anos até que a pesquisa de redes neurais ressurgisse na década de 1980. Este texto foi reimpresso em 1987 como "Perceptrons - Edição Expandida", onde alguns erros no texto original são mostrados e corrigidos.

O algoritmo perceptron do 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 os resultados anteriores e fornecem novos limites L1.

O perceptron é um modelo simplificado de um neurônio biológico . Embora a complexidade dos modelos de neurônios biológicos seja freqüentemente necessária para compreender completamente o comportamento neural, a pesquisa sugere que um modelo linear do tipo perceptron pode produzir algum comportamento visto em neurônios reais.

Definição

No sentido moderno, o perceptron é um algoritmo para aprender um classificador binário chamado função de limiar : uma função que mapeia sua entrada (um vetor de valor real ) para um valor de saída (um único valor binário ):

onde é um vetor de pesos com valor real, é o produto escalar , onde m é o número de entradas para o perceptron e b é o viés . A tendência desloca o limite de decisão da origem e não depende de nenhum valor de entrada.

O valor de (0 ou 1) é usado para classificar como uma instância positiva ou negativa, no caso de um problema de classificação binária. Se b for negativo, então a combinação ponderada de entradas deve produzir um valor positivo maior do que para empurrar o neurônio classificador acima do limite 0. Espacialmente, a tendência altera a posição (embora não a orientação) do limite de decisão . O algoritmo de aprendizagem perceptron não termina se o conjunto de aprendizagem não for linearmente separável . Se os vetores não forem linearmente separáveis, o aprendizado nunca chegará a um ponto em que todos os vetores sejam classificados corretamente. O exemplo mais famoso da incapacidade do perceptron de resolver problemas com vetores linearmente não separáveis ​​é o problema booleano ou exclusivo . Os espaços de solução de limites de decisão para todas as funções binárias e comportamentos de aprendizagem são estudados na referência.

No contexto das redes neurais, um perceptron é um neurônio artificial que usa a função de etapa de Heaviside como função de ativação. O algoritmo 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 .

Algoritmo de aprendizagem

Abaixo está um exemplo de um algoritmo de aprendizado para um perceptron de camada única. 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 que está sendo modelado pelo perceptron for não linear , algoritmos de aprendizagem alternativos, como a regra delta, podem ser usados, desde que a função de ativação seja diferenciável . No entanto, o algoritmo de aprendizagem descrito nas etapas abaixo frequentemente funcionará, 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 aprendizagem do perceptron. A taxa de aprendizagem está entre 0 e 1, valores maiores tornam as alterações de peso mais voláteis.
  • denota a saída do perceptron para um vetor de entrada .
  • é o conjunto de amostras de treinamento , onde:
    • é o vetor de entrada dimensional.
    • é o valor de saída desejado do perceptron para essa entrada.

Mostramos os valores dos recursos da seguinte forma:

  • é o valor da ésima característica do ésimo vetor de entrada de treinamento .
  • .

Para representar os pesos:

  • é o enésimo valor no vetor de peso , a ser multiplicado pelo valor do enésimo recurso de entrada.
  • Porque , o é efetivamente um viés que usamos em vez da constante de viés .

Para mostrar a dependência do tempo de , usamos:

  • é o peso no momento .


Passos

  1. Inicialize os pesos. Os pesos podem ser inicializados com 0 ou com um pequeno valor aleatório. No exemplo abaixo, usamos 0.
  2. Para cada exemplo j em nosso conjunto de treinamento D , execute as seguintes etapas sobre a entrada e a saída desejada :
    1. Calcule a produção real:
    2. Atualize os pesos:
      , para todos os recursos , é a taxa de aprendizado .
  3. Para aprendizagem offline , a segunda etapa pode ser repetida até que o erro de iteração seja menor que um limite de erro especificado pelo usuário ou um número predeterminado de iterações tenha sido concluído, onde s é novamente o tamanho do conjunto de amostra.

O algoritmo atualiza os pesos após as etapas 2a e 2b. Esses pesos são aplicados imediatamente a um par no conjunto de treinamento e, posteriormente, atualizados, em vez de esperar até que todos os pares no conjunto de treinamento tenham passado por essas etapas.

Um diagrama que mostra um perceptron atualizando seu limite linear conforme mais exemplos de treinamento são adicionados
Os pesos apropriados são aplicados às entradas e a soma ponderada resultante é passada para uma função que produz a saída o.

Convergência

O perceptron é um classificador linear , portanto nunca chegará ao estado com todos os vetores de entrada classificados corretamente se o conjunto de treinamento D não for linearmente separável , ou seja, se os exemplos positivos não puderem ser separados dos exemplos negativos por um hiperplano. Nesse caso, nenhuma solução "aproximada" será gradualmente abordada no algoritmo de aprendizado padrão, mas, em vez disso, o aprendizado falhará completamente. Portanto, se a separabilidade linear do conjunto de treinamento não for conhecida a priori, uma das variantes de treinamento abaixo deve ser usada.

Se o conjunto de treinamento for linearmente separável, o perceptron certamente convergirá. Além disso, há um limite superior no número de vezes que o perceptron ajustará seus pesos durante o treinamento.

Suponha que os vetores de entrada das duas classes possam ser separados por um hiperplano com uma margem , ou seja, existe um vetor de peso e um termo de polarização b tal que para todos com e para todos com , onde é o valor de saída desejado do perceptron para entrada . Além disso, deixe R denotar a norma máxima de um vetor de entrada. Novikoff (1962) provou que, neste caso, o algoritmo perceptron converge após fazer atualizações. A ideia da prova é que o vetor de peso é sempre ajustado por um valor limitado 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 mudanças para o vetor de peso. No entanto, ele também pode ser limitado abaixo por O ( t ) porque se houver um vetor de peso satisfatório (desconhecido), então cada mudança progride nesta direção (desconhecida) por uma quantidade positiva que depende apenas do vetor de entrada.

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

Embora o algoritmo perceptron tenha a garantia de 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 este problema (Krauth e Mezard, 1987).

Variantes

O algoritmo de bolso 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 de bolso então retorna a solução no bolso, ao invés da última solução. Pode ser usado também 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 de bolso não as aborda gradualmente no curso do aprendizado, nem é garantido que apareçam dentro de um determinado número de etapas de aprendizado.

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

O Perceptron Votado (Freund e 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á outro peso correspondente a quantos exemplos eles classificam corretamente antes de classificar incorretamente um, e no final a saída será uma votação ponderada em todos os perceptrons.

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

O -perceptron usou ainda uma camada de pré-processamento de pesos aleatórios fixos, com unidades de saída limitadas. Isso permitiu ao perceptron classificar padrões analógicos , projetando-os em um espaço binário . Na verdade, 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 camadas múltiplas é usar redes de ordem superior (unidade sigma-pi). Nesse tipo de rede, cada elemento do vetor de entrada é estendido com cada combinação de pares de entradas multiplicadas (segunda ordem). Isso pode ser estendido a uma rede de n ordem .

Deve-se ter em mente, entretanto, que o melhor classificador não é necessariamente aquele que classifica perfeitamente todos os dados de treinamento. De fato, se tivéssemos a restrição anterior de que os dados vêm de distribuições gaussianas equivariáveis, a separação linear no espaço de entrada é ótima e a solução não linear é ajustada demais .

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

Perceptron multiclasse

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

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

Esta formulação de feedback multiclasse se reduz ao perceptron original quando é um vetor de valor real, é escolhido de , e .

Para certos problemas, representações de entrada / saída e recursos podem ser escolhidos de forma que possam ser encontrados de forma eficiente, mesmo que seja escolhido a partir 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 marcação de parte da fala e análise sintática (Collins, 2002). Ele também foi aplicado a problemas de aprendizado de máquina em grande escala em um ambiente de computação distribuída .

Referências

Leitura adicional

links externos