ine 5376/79

Programa

Links

Bibliografia

Plano de Ensino

ine 5376/79 - Reconhecimento de Padrões 

3. Técnicas Subsimbólicas: Redes Neurais

Parte I - Backpropagation

Parte I:

3.1. Filosofia Geral da Aplicação do Raciocínio Subsimbólico a Padrões: Redes Neurais Aprendendo Dados, Classificadores e Agrupadores
3.2. O Simulador SNNS - Stutgarter Neural Network Simulator
3.3. Classificadores: Usando Aprendizado Supervisionado para Reconhecer Padrões

3.3.1. Princípios  Matemáticos de Redes-BP
3.3.2. Aspectos Práticos de Métodos de Descida em Gradiente
Parte II:

3.4. Desenvolvimento de Aplicações: Usando Aprendizado Supervisionado

Parte III:

3.5. Agrupadores: Usando Aprendizado Não Supervisionado para Organizar Padrões
      3.5.1. O Modelo de Kohonen e Quantização de Vetores
      3.5.2. O Modelo ART: Teoria da Ressonância Adaptativa

Parte IV:

3.6. Explorando Dados Agrupados em Redes
 
 

3.1. Filosofia Geral da Aplicação do Raciocínio Subsimbólico a Padrões: Redes Neurais Aprendendo Dados, Classificadores e Agrupadores

Chamamos de Raciocínio Subsimbólico ao procesamento de informação em um nível onde os padrões representam conjuntos de dados mas onde não podemos associar um significado imediato a cada dado processado. Isto significa que trabalhamos com dados, que em seu conjunto podem ser chamados de informação e assumir um significado, mas onde não sabemos ou não podemos determinar o significado de cada parte do conjunto de informação em separado. O mesmo vale para as representações internas, intermediárias desses dados: usamos sistemas que representam essa informação, mas eles são sistemas black box - caixa preta - produzindo classificações dos padrões e resultados numéricos, sem no entanto fazer isto de forma explícita. As redes neurais são o melhor exemplo de um sistema subsimbólico: mesmo que cada parte de um padrão apresentado a uma rede tenha um significado explícito, associável a um símbolo de nosso modelo do mundo real, a representação interna dos dados no procesador (a rede) não é explícita e não possui significado. Um método subsimbólico tipicamente é incapaz de explicar porque chegou a uma determinada conclusão, uma vez que um mapeamento explícito de causa-e-efeito não existe.

Fica mais fácil ilustrar este conceito através de um exemplo. Imagine um sistema militar para classificar tipos de navios ("inimigos") a partir do padrão de ruído emitido por estes, da forma como é captado por um submarino ("nosso"). Hipotetize que nós sabemos que um determinado padrão de ruídos corresponde a um porta-aviões de determinada classe de uma determinada nacionalidade. Este padrão inclue um conjunto de freqüências e as variações de amplitude dessas freqüências, além de algumas outras informações. Nós podemos associar um conjunto de símbolos a esse padrão: "Porta-Aviões modelo Banheirão de Corto Maltese", mas classificamos o padrão como um todo. Nós não sabemos dizer que papel tem uma freqüência X qualquer do ruído neste padrão ou que parte mecânica do navio em questão ela representa. Talvez não saibamos nem mesmo, se vamos continuar cnseguindo classificar o padrão, caso retiremos os valores correspondentes a esta freqüência do padrão.

Este é um exemplo típico. Mesmo em situações onde os dados possuem um significado conhecido, como no caso de dados de um paciente cardíaco potencial, onde eu sei o significado da freqüência cardíaca,  mas onde eu não sei o relacionamento entre a freqüência cardíaca e a chance deste paciente ter um infarte numa determinada situação futura. É esse relacionamento, que eu não posso mapear de forma explícita que eu quero que um sistema subsimbólico mapeie implicitamente para mim. E os sistemas subsimbólicos fazem isto, mas o fazem de forma fechada, sem gerar mapas, tabelas estatísticas ou conjuntos de regras de como criam este mapeamento.

As Redes Neurais Artificiais são o mais difundido e popular conjunto de métodos subsimbólicos, sendo em geral caixas-pretas por excelência. Existem outros métodos que não vamos abordar aqui. O fato das redes neurais serem caixas pretas muitas vezes é citado como uma de suas desvantagens. Neste capítulo nós vamos ver que isto é relativo. Este capítulo pressupõe que você já viu Teoria das Redes Neurais na cadeira de Inteligência Artificial e que você tem o conhecimento teórico básco sobre os métodos: aqui nós vamo ver aplicações de redes neurais e técnicas de integração das mesmas em sistemas mais complexos. 
 

3.2. O Simulador SNNS - Stutgarter Neural Network Simulator

O SNNS é um dos melhores simuladores de Redes Neurais existentes. Porisso nós vamos vê-lo aqui. O objetivo de alocarmos um capítulo a ele é o de prover ao aluno com uma ferramenta poderosa para a execução dos exercícios propostos, livrando-o da necessidade de ter de programar ele mesmo as redes. 

O SNNS possui outra vantagem: após treinada um rede, você pode gerar com o SNNS um arquivo em linguagem "C" contendo a rede treinada. Este arquivo compilado pode ser utilizado como prorama standalone ou então como biblioteca (.dll ou .so) linkada ao programa aplicativo que você for usar. Isto é uma vantagem para as aplicações em Smalltalk que você vai desenvolver, pois permite que você utilize o pacote "DLL & C connect" para usar estas redes em Smalltalk.

  • Versão do SNNS em Java para Windows
  • Java Runtime Environment completo que você precisa para o software acima
  • Versão compilada do SNNS 4.2 para Linux (se você possue RedHat ou Conectiva instalado pode ter problemas para rodar pois a versão do Athena suprida com RedHat e seus clones é meio estranha. Teste estas opções: a) Mude a profundidade de seu vídeo para 8 bits ou b) Não carregue os arquivos de configuração dos exemplos, apenas as redes e os arquivos de treinamento.
  • Versão do SNNS para SunOS ou Solaris: Os fontes do SNNS compilam sem problemas nas plataformas Sun. Acesse a homepage do SNNS e baixe os fontes. As bibliotecas do Athena podem ser baixadas para Sun em vários lugares.

3.3. Classificadores: Usando Aprendizado Supervisionado para Reconhecer Padrões

Há dois modelos de redes neurais utilizados na prática como classificadores passíveis de serem gerados através de aprendizado supervisionado. Ambos os modelos baseiam-se nos Perceptrons feed-forward 1 , variando o número de camadas e a função de ativação e, por conseguinte, a regra de aprendizado: a) As Redes Backpropagation 2 e b) as Redes de Base Radial. 

Por serem as mais utilizadas e, do ponto de vista prático, mas mais importantes, vamos nos ocupar aqui das Redes Backpropagation, também chamadas redes-BP. As redes de Base Radial, conhecidas também por redes-RBF podem ser usadas, em teoria, para representar os mesmos tipos de problemas que uma rede Backpropagation equivalente. Alguns autores argumentam que são mais eficientes durante o treinamento. Por outro lado, a compreensão de seu algoritmo de aprendizado envolve uma matemática bastante mais complexa. Como são utilizadas para resolver o mesmo tipo de problemas que os onde Backpropagation encontra aplicação, sem vantagens consideráveis na qualidade do resultado final, vamos ignorá-las aqui. No final desta seção há uma comparação entre redes-RBF e redes-BP, extraída de [Haykin] e um comentário nosso sobre redes-RBF e sua relação com Nearest Neighbour e métodos que utilizam NN, como IBL*.

Como esta disciplina pressupõe que você já viu o assunto Redes Neurais, vamos aqui apenas recordar alguns conceitos matemáticos importantes para que você entenda a nossa discussão mais adiante de como se deve aplicar corretamente Backpropagation. 
 

3.3.1. Princípios  Matemáticos de Redes-BP
Existem várias convenções amtemáticas para a nomenclatura dos elementos de uma rede neural. Durante todo o capítulo de Redes Neurais vamos utilizar a simbologia matemática descrita em [Hertz et.ali.]. 
Um conjunto de treinamento é um conjunto p de padrões, todos de mesmo tamanho, cada qual dividido em duas partes: vetor de entrada  e vetor de saída  . O vetor de saída representa a atividades esperada nos neurônios de saída quando é apresentado o vetor de entrada nos neurônios de entrada da rede. 




 

Princípios Básicos das Redes Backpropagation
A idéia básica de toda rede neural feedforward com aprendizado supervisionado é que, durante o seu treinamento, aplicamos à sua camada de entrada o padrão que desejamos que seja aprendido e propagamos a ativação  gerada por este padrão na camada de neurônios de entrada, camada a camada, até gerarmos uma ativação nos neurônios da camada de saída.
Cada neurônio i de uma camada está tipicamente ligado a todos os neurônios j da camada anterior e recebe o sinal h de todos estes, cada qual ponderado pelo peso wij da conexão correspondente. 
Cada neurônio possui uma função de ativação g() cuja variável independente é a entrada h do neurônio. 
Todo neurônio i possui um sinal de saída, que será denominado Vi se o sinal for dirigido para outra camada da rede (neurônios de entrada e internos) ou Oi se o neurônio for de saída. A relação entre o sinal de saída e a ativação g(h) do neurônio tipicamente é a identidade. A separação da ativação e do sinal de saída em duas variáveis permite realizar-se de forma elegante o sincronismo de toda a rede (inerentemente paralela) quando se simula a mesma em uma máquina de von Neumann (seqüencial): Atualizamos os valores de saída dos neurônios de uma camada somente depois de termos calculado todas as ativações desta camada. Isto é especialmente importante em redes BP recorrentes e outros modelos de rede onde neurônios possuem ligações com neurônios da própria camada.
O objetivo do treinamento supervisionado é modificar os pesos das conexões da rede de tal forma que a saída  gerada para o vetor de entrada  do padrão m pela rede seja o mais próximo possível do vetor de saída  deste padrão, de forma que no futuro, quando apresentarmos um outro vetor similar a  , a rede produza uma resposta o mais próxima possível de  . 
Para realizarmos esta modificação dos pesos, representamos o erro de saída da rede como uma função do conjunto dos pesos, E(w), e utilizamos a técnica denominada descida em gradiente (gradient descent ou Gradientenabstieg) para realizar alterações iterativas dos pesos de forma a reduzir o erro. Para isto, representamos inicialmente E(w) como uma função-custo baseada na soma dos quadrados dos erros:
A função acima representa o erro do resultado apresentado pela rede como uma função da diferença entre o resultado esperado e os pesos das ligações entre a camada de saída e a anterior e a entrada desta camada. Como os valores de entrada e de saída são dados, o conjunto de variáveis independentes é formado pelos pesos e o erro está representado como função dos pesos.
A variação do erro em função dos pesos pode então ser representada pelo vetor das derivadas parciais do erro em função dos pesos, também denominado gradiente do erro: . 
Este vetor possui a propriedade de apontar no sentido do maior acréscimo de erro. Portanto para reduzir E(w) da forma mais rápida possível movemo-nos no sentido contrário e definimos a modificação dos pesos como:
Chamamos a esta fórmula de regra-delta.
Como esta modificação dos pesos deve ser gradativa, para evitar que uma modificação brusca de pesos faça a rede desaprender outro padrão já aprendido, utilizamos os seguintes princípios:
  • introduzimos uma taxa de aprendizado h, tipicamente de valor < 0,2
  • apresentamos os padrões de treinamento em ordem aleatória, garantindo que tenhamos apresentado todos antes de reapresentarmos algum. 
Podemos também representar a alteração dos pesos individualmente para cada padrão m : 
No treinamento de redes neurais, ao invés de falarmos de iterações, chamamos a cada ciclo de apresentação de todos os padrões de época. Antes de iniciar uma nova época, reorganizamos os padrões em uma nova ordem aleatória. A cada época todos os padrões são apreseentados.
A regra-delta, tal qual está representada acima, ainda não nos permite treinar a rede, apenas expressa um vetor de modificação dos pesos para a camada de saída. Vamos agora recapitular brevemente a regra de aprendizado das redes-BP.
Aprendizado das Redes-BP
O fato que fez com que a pesquisa em redes neurais ficasse quase 20 anos (1968 - 1984) parada no cenário internacional foi o seguinte conjunto de fatos:
  • para que uma rede neural feedforward possa representar uma função qualquer (universalidade representacional) ela necessita de pelo menos uma camada intermediária, além da camada de entrada e da de saída e a função de ativação de pelo menos parte dos neurônios deve ter caráter não-linear.
  • para que a rede possa aprender, é necesário que possamos calcular a derivada do erro em relação aos pesos em cada camada, de tràs para frente, de forma a minimizar a função custo definida na camada de saída. Para isto ser possível, a função de ativação deve ser derivável.
Já o modelo de rede de McCulloch & Pitts possuía um caráter representacional quase universal, mas não apresentava a possibilidade de treinar-se redes com camadas intermediárias, pois a função de limiar por eles desenvolvida não era derivável.
A regra de aprendizado do modelo do Perceptron podia treinar redes com quantas camadas se quisesse, mas estas camadas intermediárias eram inúteis pois a função de ativação linear do neurônio do Perceptron fazia com que camadas adicionais representasssem transformações lineares sobre transformações lineares, o que é equivalente a uma única transformação linear e incapaz de representar problemas linearmente inseparáveis.
Como resolver este problema? Através de uma idéia muito simples: introduzir uma não linearidade "bem comportada" através de funções quaselineares contínuas e deriváveis. Com isto conseguimos:
  • introduzir uma não linearidade sem no entanto alterar de forma radical a resposta da rede (ela se comporta de forma similar a uma rede linear para casos "normais") e
  • possibilitar o cálculo da derivada parcial do erro em relação aos pesos (o que nós queríamos desde o começo) de uma forma elegante e generalizável para todas as camadas.
As funções de ativação quaselineares que se costuma utilizar têm a forma geral do desenho abaixo.
Esta família de funções possue comportamento assintótico, significando que para valores valores muito grandes ou muito pequenos de y elas tendem a um valor constante. Além disso é derivável e, próxima de sua parte "mais normal", possue um comportamento muito semelhante ao de uma reta inclinada, como em uma função linear.
As duas funções mais utilizadas são a tangente hiperbólica e a função logística, mostradas abaixo, juntamente com suas derivadas:
O parâmetro b é um parâmetro livre com b > 0 que permite parametrizar o comportamento da função. Na prática utilizamos geralmente b =1.
Estas duas funções possuem a propriedade adicional de se poder definir suas derivadas em função delas mesmas, significando que se pode reutilizar o valor já calculado para a ativação ao se realizar a retropropagação do erro, sem necessidade de novos cálculos complexos.
A função tangente hiperbólica possui domínio no intervalo aberto ]-1, +1[ e a função logística no domínio ]0, 1[ . Podemos escolhê-las de acordo com nosso domínio de aplicação ou fazer, como o fazem a maioria dos simuladores de redes-BP, tomar a função logística como função padrão e suprir valores negativos de saída através da adição de uma constante. Essa constante é muitas vezes provida através de um neurônio virtual a mais em cada camada, denominado bias neuron, que possui saída constante e negativa. 
E a regra para modificação dos pesos imediatamente após a apresentação de cada padrão:
Aprendizado para Redes de Várias Camadas
As fórmulas deduzidas acima nos permitem implementar uma descida em gradiente, realizando o aprendizado, em redes de duas camadas. Como já discutimos, porém, necessitamos de redes com pelo menos uma camada interna. Para extender o aprendizado a redes de uma camada interna, temos de primeiramente extender a nossa função-custo de forma que ela diferencie entre pesos de neurônios internos e pesos de neurônios de saída. 
Para isto observemos a figura 3.3 abaixo, que representa uma rede de 9 neurônios divididos em três camadas. Você pode observar na figura que os pesos k -> j são representados por wjk e os pesos j -> i são representados por Wij . 
Lembrando que a nossa função-custo tem a forma geral: 
...e que desejamos minimizar E(w) modificando gradualmente o vetor dos pesos w = (w11 ,....,W11 ,....).
Para isso, vamos inicialmente definir como surge o vetor de saída da rede O i :

Esta função E(w) é contínua e diferenciável para todos os wjk ,, Wij . Isto permite que se utilize o método de descida em gradiente para construir o algoritmo de aprendizado. 
Faremos a descida em gradiente em etapas, uma para cada conjunto de pesos entre camadas. Para uma rede BP com uma camada interna, isto é feito de trás para frente (por isso retropropagação do erro) em duas etapas, uma para Wij e outra para wjk .
Observe que esta é praticamente a mesma regra que havíamos escrito antes, somente substituímos os valores do vetor de entrada pelos valores da ativação dos neurônios internos.
Para o caso dos pesos entrada -> interno nós vamos ter de aplicar a regra da cadeia também para as derivadas internas:


Observe que esta fórmula possui caráter genérico extensível a qualquer camada interna, pois se criarmos um buffer para os deltas da adaptação da camada anterior, podemos utilizá-los para a atual, de trás para frente.
Dessa forma, a regra-delta generalizada para a m-ésima camada de uma rede backpropagation fica assim (considerando-se a camada de entrada como camada 0 e a camada de saída como camada M):


Algoritmo Backpropagation
Dados:
  • uma rede feedforward de M camadas
  • um conjunto de conexões ponderadas por pesos e dirigidas da camada m-1 para a camada m: 

  • uma função de ativação não-linear contínua e diferenciável no domínio dos valores a serem treinados na rede
  • uma taxa de aprendizado h
  • um conjunto de treinamento contendo xm entradas e zm saídas.
Execução:




 


3.3.2. O que Aprende uma Rede-BP ?

Como citamos em outras partes deste texto, uma rede backpropagation, ao contrário de redes-RBF ou classificadores baseados em Nearest Neighbour, como IBL, aprende uma função capaz de mapear a entrada à saída, caso esta exista. Se o conjunto de treinamento for inconsistente a rede não aprenderá nada ou aprenderá cada exemplo individual do conjunto de treinamento, caso a criemos grande o suficiente.

Em princípio, o mapeamento entrada-saída em uma rede-BP está distribuído sobre o total dos pesos e conexões da rede, sendo bastante difícil associarmos um determinado neurônio e suas conexões a uma determinada classe. 

Do ponto de vista matemático, existem várias interpretações do significado dos pesos aprendidos por uma rede neural. Uma discussão detalhada deste assunto foge do escopo de uma disciplina de graduação e nós remetemos à literatura, principalmente [Hertz et.ali.].

Existem, porém, algumas situações interessantes, onde o aprendizado da rede neural pode ser visualizado e podemos realmente associar um ou um conjunto de neurônios a uma determinada classe. Isto tende a acontecer quando o conjunto de treinamento contém classes realmente muito bem comportadas. 

O exemplo clássico para este comportamento é o encoder (codificador). Este exemplo está incluído na coleção de exemplo sprontos do SNNS e sugerimos ao leitor que faça alguns experimentos com ele. O encoder é um exemplo onde podemos fazer os padrões de ativação dos neurônios da camada interna representarem uma compressão dos dados de treinamento e ainda utilizar esta compressão de dados como um código representando os mesmos. 

O encoder toma um valor de entrada de 0 a 7 e aprende a asociá-lo a mesma saída, possuíndo 8 neurônios de entrada, um para cada valor e 8 neurônios de saída, com a mesma representação. Na camada intermediária possui apenas 3 neurônios. O objetivo é que, ao aprender a associação entrada-saída, ele codifique os dados. A figura abaixo mostra o encoder recebendo o número 1 como padrão de entrada (01000000) e representando internamente este número como 101. 

O conjunto de treinamento do encoder não é só linearmente separável, mas é também linearmente independente e, portanto, um conjunto extremamente fácil de aprender, que não necessitaria de uma camada interna, podendo ser representado por um perceptron simples. Mesmo assim é interessante de se observar o fenômeno da representação interna. Este fenômeno porém não ocorre sempre dessa forma, com a rede “inventando” seu próprio código binário. Às vezes os pesos se distribuem de uma forma tal na rede que não é possível uma interpretação visual da “representação interna”.

Exercício: Observando o Encoder

Vamos ver com que freqüência o encoder realmente aprende uma representação interna que para nós, humanos, faz “sentido”. Carregue o exemplo do encoder no SNNS.  Reinicialize a rede e treine-o. Bastam 100 épocas pois o conjunto é aprendido extremamente rápido. Feito isto, vá para o modo “updating” e repasse todo o conjunto de treinamento pela rede. Foi possível criar-se um arepresnetação interna similar a algum código binário conhecido ? Repita este processo várias vezes, reincializando, treinando e testando a rede para ver como ela se comporta. 

3.3.3. Aspectos Práticos de Métodos de Descida em Gradiente

Como citamos brevemente antes, o processo de redução do erro E(w) pertence a uma categoria de métodos matemáticos denominado Métodos de Descida em Gradiente (Gradient Descent Methods). Nocaso específico das redes-BP, que nos interessa, podemos imaginar a idéia de que o erro é uma (hiper) superfície em um espaço definido pelos pesos [w] da rede neural. O estado atual da rede (conjunto de valores específico dos pesos das conexões entre os neurônios) é um ponto sobre esta superfície. O nosso objetivo é mover este ponto através da alteração dos valores do spesos de forma a encontrar uma posição onde o erro seja o menor possível. O movimento é realizado sempre no sentido de reduzir-se o erro, ou seja sempre descendo a superfície de erro de forma que o próximo ponto seja uma posição mais funda nesta superfície, até encontrar uma posição de onde não sejja possível descer-se mais. Se imaginarmos uma situação 3D, onde há apenas dois pesos definindo os espaços x e Y e a coordenada z sendo definida pelo erro, podemos imaginar o processo como o mostra a figura abaixo. 
 

O material abaixo é um resumo do tutorial de redes neurais disponibilizado pela Neuro-Fuzzy AG (Grupo de Trabalho Neuro-Fuzzy) do Departamento de Matemática da Universidade de Muenster, Alemanha.
 

Mínimo Local: Partindo-se da configuração de pesos inicial w1, o método de descida em gradiente não encontrará a solução (mínimo global).
Platô encontrado em E(w) durante treinamento da rede neural. Durante um longo período não haverá mudanças significativas em E(w). Após um tempo, porém, o mínimo absoluto (global) é encontrado.
Oscilações ocorrem quando o processo de descida de gradiente cai em uma ravina de onde não sai mais. Também é uma espécie de mínimo local. O passo de modificação dos pesos (taxa de aprendizado) é grande demais para que a rede caia na ravina, mas pequena demais para sair do mínimo. Ao conrário do mínimo local comum, aqui a rede não encontra um estado estável.
A Oscilação Indireta é uma situação de oscilação mais complexa, onde a rede também fica "presa" em um mínimo local e não encontra um estado estável. Neste caso porém, existem estados intermediários entre os estados extremos da oscilação, onde o erro por momentos se permite reduzir.
Saída do mínimo ótimo para um subótimo. Se a mudança dos pesos se inicia numa área de gradiente muito grande, os primeiros ajustes podem ser excessivamente grandes e levar a rede a passar do vale onde está o mínimo global, para uma região com um mínimo local.

Existem várias técnicas para "turbinar"a descida em gradiente de forma e evitar alguns dos problemas descritos acima. Estas técnicas são implementadas em parte no SNNS. Na aula vamos discutir suas vantagens e limitações.
 

1.Conceito referido por alguns autores em Língua Portuguesa como "Alimentação Adiante". Como na literatura internacional de computação em muitas línguas, não somente a inglesa, este termo já se estabeleceu como termo técnico, vamos nos abster aqui de traduções de eufonia questionável.
2.Retropropagação. A rede em si na verdade é um perceptron de três ou mais camadas utilizando uma função quaselinear como função de ativação. Chamamos de redes backpropagation porque o algoritmo de aprendizado utilizado é assim chamado.
3.Com exceção da camada de entrada, que em ambos os modelos serve apenas para distribuir o sinal de entrada à camada interna e onde a função de ativação é sempre a função identidade.

3.4. Desenvolvimento de Aplicações Usando Aprendizado Supervisionado

  
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR