Aprendizagem Automática Usando Algoritmos Genéticos

Aprendizagem Automática usando

Algoritmos Genéticos "Learning with Genetic Algorithms - An Overview" por Kenneth de Jong, 1988

Por Gustavo Maçães, nº 13890 Waldir Pimenta, nº 12650

Aprendizagem Automática (AA)? • Analogia à aprendizagem natural • Tópico incontornável para a Inteligência Artificial • Definição » sistema de resolução de problemas capaz de se alterar a si próprio com o objectivo de: – Melhorar a performance – Descobrir novas soluções – Generalizar o conhecimento que dispõe

• Tanto melhores quanto maior for a sua capacidade de adaptação

Algoritmos Genéticos (AG)? • Vocês supostamente já sabem sobre isso :) • Tal como os AA, também usam a aplicação de um sistema natural à computação: a Evolução • Pesquisa de soluções em espaços muito grandes (NP-hard problems) • Independentes do contexto (domínio) • Não requerem conhecimento prévio do domínio • Portanto, eficazes para AA, especialmente quando não há conhecimento prévio

AA + AG? •

Como aplicar AGs a sistemas de AA? –

Um SAA baseado em AG é composto por dois blocos: um módulo que executa uma tarefa e um módulo (o AG) que faz as alterações internas de acordo com a performance do módulo anterior.

Formas de aplicação de AGs: • Alterar parâmetros do algoritmo de avaliação • Alterar a própria estrutura do mód. de tarefas • Alterar código do algoritmo interno do m.t.

1. Alterar parâmetros •

O módulo de execução de tarefas possui um algoritmo parametrizável –

•

Problema: se população < valores possiveis: – – –

•

Por exemplo, os pesos das sinapses de uma rede neuronal Novos genes por mutação Baixa taxa mut. = picos locais Alta taxa mut. = perda de genes bons

Solução: binarização dos valores –

permite geração de novos valores via cruzamento

2. Alterar a estrutura •

O módulo de execução de tarefas é um conjunto organizado de pontos de dados –

• •

Problema: GA irá produzir estruturas ilegais Solução: – –

•

Por exemplo, uma árvore de decisão, ou uma sequência (o problema do caixeiro viajante)

Redefinir a representação da estrutura nos genes Redefinir os operadores genéticos (com restrições)

Nota: strings não são “sagradas”; a representação genética apenas deve permitir a recombinação válida dos genes

3. Alterar o algoritmo •

Programa == string de símbolos –

•

main(){printf(“hello world”);} / 000101010110101…

Mas tem regras complexas de sintaxe –

•

main)({world” “hello );}

…e semântica: –

•

main(){printf(“asdfgXPTO???”);}

Redefinir operadores genéticos para assegurar a validade do código? –

•

Não: Sintaxe e semântica demasiado complexas

Usar linguagens com sintaxe mais simples (lisp, etc)? –

Não: Mantêm a característica de serem procedurais: a ordem das instruções é importante

3. Alterar o algoritmo •

Solução: broadcast languages (ex: OPS5) –

•

Usadas em Production Systems, nas quais as regras que compõem um programa são independentes da ordem em que são definidas

Production Systems – – –

Regras no formato IF – THEN. Basicamente um conjunto de event listeners (Think triggers, stored procedures…) Geralmente usam sintaxe booleana; porém, a OPS5 (Forgy, 1981) usa uma linguagem de padrões que têm que ser detectados no ambiente

3. Alterar o algoritmo •

Production Systems (cont.) – –

–

–

Ambas as sintaxes podem se tornar complexas Abordagem por padrões mais flexível por se poder detectar matches parciais em vez de exactos (tal como na aprendizagem real, que se baseia em experiências semelhantes – não iguais) Há ainda quem afirme que a linguagem de padrões do OPS5 (que para obter matches parciais usa wildcards como em {0,1,#}) seja mesmo assim restritiva Propõem a atribuição de scores em vez do match/não match que é (quase) booleano...

3. Alterar o algoritmo •

Pitts approach – – – –

–

Todo o programa é uma única string, e a população contém vários programas Cruzamento produz conjuntos diferentes das mesmas regras Mutação produz novas regras Geralmente usa-se um nº fixo de regras, cada uma destas também com um tamanho fixo; ou seja, cada string da população tem o mesmo tamanho total; parece restritivo, mas funciona (em binário) Se se usar um nº flexível de regras, é preciso implementar regras de recompensa dos programas menores com igual performance

3. Alterar o algoritmo •

Michigan approach – –

Cada indivíduo é uma regra, e a população representa o programa Exemplo de implementação: sistema multi-agentes baseado em quadro negro (message board) • • •

•

Cada agente possui detectores (IF) e actuadores (THEN) O ambiente pune ou recompensa os agentes em relação à sua performance O AG usa os “pontos” acumulados por cada agente como medida de fitness durante o ciclo de cruzamento/selecção

Hybrid approach –

Há quem sugira o uso de medições de performance tanto individuais (das regras) como colectivas (do programa)

Conclusão! • • •

•

•

Está alguém acordado ainda? (just kidding) É claro que o conhecimento prévio sobre o domínio do problema pode e deve ser usado, se existir. Porém, é nos casos em que não o há que os Algoritmos Genéticos são mais úteis para sistemas de Aprendizagem Automática. Apesar disso, eles tem limitações, como já vimos, pelo que devem ser vistos como mais uma “arma” no arsenal do designer de sistemas de aprendizagem, para casos específicos, e não o santo graal deste campo. Perguntas?