IA369 - Gudwin & Von Zuben (1s/98)

Sistemas Classificadores (Classifier Systems)

¾ Sistemas classificadores são sistemas baseados em regras, trabalhando massivamente
em paralelo e com passagem de mensagens, capazes de aprender utilizando as
técnicas de credit assignment (algoritmo Bucket Brigade) e rule discovery (algoritmo
genético).
¾ Operam em ambientes que tipicamente exibem as seguintes características:
• Eventos novos e sucessivos, acompanhados de largas doses de ruído e dados
irrelevantes
• Necessidade de agir de maneira contínua e frequentemente em tempo real
• Metas implícitas ou inexatas
• Recompensas esparsas, obtidas somente depois de ações longas.
¾ Criados para absorver novas informações continuamente, avaliando conjuntos de
hipóteses competindo entre si, sem prejudicar as capacidades já adquiridas.

Aula 7 1

IA369 - Gudwin & Von Zuben (1s/98)

¾ De modo a solucionar esse problema, o sistema deve:

• Inventar categorias que representem regularidades presentes no ambiente, e que
sejam relevantes para as metas desejadas
• Utilizar o fluxo de informação encontrado no caminho até a meta para refinar seu
modelo do ambiente
• Associar ações de controle apropriadas às categorias encontradas na busca da meta.
¾ 3 níveis de atividade:

Saída para o Ambiente

Discovery Credit Assignment Performance

Genetic Algrorithm Bucket Brigade System

Entrada do Ambiente

Aula 7 2
 IA369 - Gudwin & Von Zuben (1s/98)

¾ Classificador: regra condição-ação

¾ 100110##11##100#11/11010###00100101##
Condição Ação
¾ Variações: - 100##1010## = nenhum string na população satisfazendo 100##1010##
010##1010, 0010####0 = 010##1010 e 0010####0 devem ocorrer
¾ Performance System:

Lista Classificadores

Interface de Entrada Lista de Mensagens Interface de Saída

AMBIENTE

Aula 7 3

IA369 - Gudwin & Von Zuben (1s/98)

Ciclo Básico de Execução de um Sistema de

Classificadores
PASSO 1: Adicionar todas as mensagens da interface de entrada na lista de mensagens
PASSO 2: Comparar todas as mensagens na lista de mensagens com todas as condições
de todos os classificadores, anotando todos os matches (condições satisfeitas)
PASSO 3: Para cada conjunto de matches, postar a mensagem especificada na parte de
ação do classificador em uma lista de novas mensagens
PASSO 4: Substituir TODAS as mensagens na lista de mensagens pela lista de novas
mensagens
PASSO 5: Traduzir as mensagens na lista de mensagens para a interface de saída,
produzindo a saída do sistema
PASSO 6: Retornar ao PASSO 1.

Aula 7 4
 IA369 - Gudwin & Von Zuben (1s/98)

Exemplo: Controle de um Veículo Autônomo

Detetores:
d1 – 1 – objeto movendo 0 – c.c.
(d2, d3) – (0,0) – objeto centrado
Vetor Visual
(1,0) – objeto à esquerda
(0,1) – objeto à direita
Vetor Motor
d4 – 1 – adjacente ao objeto, 0 – c.c.
d5 – 1 - objeto é grande, 0 – c.c.
d6 – 1 – visão parcial do objeto 0 – c.c.
Efetores Visão: V-LEFT, V-RIGHT
Objetos
Efetores Motores: M-LEFT, M-RIGHT,
ALIGN, OPPOSE
Velocidade: FAST,CRUISE, SLOW, STOP

Aula 7 5

IA369 - Gudwin & Von Zuben (1s/98)

Sistemas Classificadores × Outras Estratégias utilizando AI

¾ Processo Adaptativo
¾ Difere dos métodos simbólicos que são familiares na comunidade AI
¾ 2 aparentes sérias deficiências:
• Regras são representadas em uma linguagem com fraco poder descritivo
• Devido ao fato que várias regras podem disparar simultaneamente, existem
particularidades no controle (sincronismo), que não aparecem em sistemas
convencionais baseados em regras – computação distribuída
¾ Vantagens
• Tipo de problema que eles são projetados para resolver:
- Fluxo de dados continuamente sendo renovado, extremamente complexo e
incerto
• Abordagem Usual: Arquitetura Blackboard

Aula 7 6
 IA369 - Gudwin & Von Zuben (1s/98)

¾ Deficiência: sistema necessita construir e modificar dinamicamente a representação

do problema
¾ Requisito: Flexibilidade
¾ Sistemas de Classificadores permitem esta flexibilidade – Building Blocks
• Lista de Mensagens → blackboard
• Mensagens, tags e regras → building blocks
¾ Abordagem distribuída → similar a sistemas conexionistas (redes neurais NN)
• SC: regras condição/ação
• NN: neurônios
¾ Indução é obtida de diferentes maneiras:
• NN→ modificação nos pesos das conexões → regras são fixas
• SC→ largo espectro de mecanismos indutivos: ajuste de pesos, analogias, etc.
- Controlado por regras inferenciais → meta-controle

Aula 7 7

IA369 - Gudwin & Von Zuben (1s/98)

¾ SC → ocupa um meio termo entre os paradigmas simbólicos e conexionistas

¾ SC × SOAR → arquitetura motivada por considerações amplas envolvendo processos
cognitivos → arquitetura de propósito geral para problemas orientados a metas
envolvendo aprendizado.
¾ Comportamento: busca no espaço de soluções do problema por um estado que
satisfaça as metas.
• Seleção dos operadores apropriados para modificar o estado inicial
• Impasse → inexistência de critérios suficientes para selecionar um operador → sub-
metas → novo problema → resolvido recursivamente
• Conhecimento dos estados do problema, operadores e critérios de solução → regras
condição/ação
• Resolução de um impasse → oportunidade de aprender uma nova regra (or regras)
• Nova regra (chunk de conhecimento) → usada para evitar impasses no futuro

Aula 7 8
 IA369 - Gudwin & Von Zuben (1s/98)

• Mecanismo único de aprendizagem → chunking

¾ SC × SOAR
• Ambos enfatizam a flexibilidade utilizando regras
• Ambos enfatizam a importância de um acoplamento eficiente entre mecanismos
indutivos e a resolução do problema
• SC não força nenhum tipo particular de regime na solução do problema
¾ SOAR: Enfatiza uma única metodologia de resolução de problemas e um único
mecanismo de aprendizagem
• O único meio de resolver impasses → sub-metas
• O único meio de aprender e adicionar regras → chunking
¾ SC: Enfatiza a flexibilidade na modelagem como forma de resolver impasses.
• Gera hipoteticamente novas regras (por meio da recombinação dos building
blocks), ao invés da recompilação (chunking) de regras existentes.

Aula 7 9

IA369 - Gudwin & Von Zuben (1s/98)

Algoritmo Bucket Brigade

¾ Primeiro passo considerando-se a utilização de sistemas baseados em regras em
ambientes complexos é a tarefa de Credit Assignment, ou seja, a descoberta do valor
das regras diante de sua utilização no ambiente.
¾ Sistema de análise de desempenho deve indicar as regras responsáveis pelo
sucesso/fracasso do sistema e a representatividade das condições utilizadas para esta
análise.
¾ Algoritmo bucket brigade foi desenvolvido com o intuito de prover um método
eficiente de credit assignment em sistemas classificadores.
¾ Para implementar o algoritmo, a cada classificador é atribuída uma quantidade
chamada sua força (strength). O algoritmo BB ajusta o strength dos classificadores,
de modo a refletir a sua utilidade diante dos propósitos gerais do sistema. Esse
strength é então utilizado como base para uma competição. A cada instante de tempo,

Aula 7 10
 IA369 - Gudwin & Von Zuben (1s/98)

cada classificador com seu antecedente satisfeito por uma mensagem faz uma aposta
(bid), baseada em seu strength, e apenas o classificador com o maior bid consegue
utilizar a mensagem, retirando a mensagem da lista de mensagens.
¾ Não existe nenhuma verificação de consistência na lista de mensagens (é possível se
ter mensagens contraditórias na lista). O único ponto onde ocorre uma verificação de
consistência é na interface de saída. Neste caso, mensagens indicando respostas
conflituosas são resolvidas por meio de uma competição entre os classificadores
querendo postá-las.
¾ Processo de aposta: 2 fatores são utilizados:
• Relevância diante da situação corrente: dada pela especificidade da condição da
regra
• Utilidade no passado : dada pelo strength da regra
¾ Para implementar o processo de aposta, modifica-se o passo 3 do ciclo de execução:

Aula 7 11

IA369 - Gudwin & Von Zuben (1s/98)

¾ Passo 3: Para um conjunto de classificadores satisfazendo uma mensagem postada,

calcula-se a aposta de cada classificador C, de acordo com a seguinte fórmula:
B(C,t) = b.R(C).s(C,t)
onde:
¾ R(C) - especificidade da condição do classificador - dado pelo número de bits que não
# na parte de condição do classificador, dividido pelo seu comprimento
¾ b - constante menor que 1 (por exemplo, 1/8 ou 1/16)
¾ s(C,t) - strength do classificador C no instante t.
• valor do bid determina a probabilidade de que o classificador poste sua mensagem
(especificada na parte de ação do classificador) na nova lista de mensagens.
¾ Sendo sorteado (e postando sua mensagem), o strength do classificador C é reduzido
por: s(C,t+1) = s(C,t) - B(C,t)

Aula 7 12
 IA369 - Gudwin & Von Zuben (1s/98)

¾ Os classificadores {C’} que postaram a mensagem geradora têm seu strength

aumentado por: s(C’,t+1) = s(C’,t) + a.B(C,t)
onde a = 1/(número de membros em {C’})
¾ Uma regra só será profícua, se seus consumidores também forem profícuos. Uma
cadeia de consumidores profícuos leva a um consumidor final (interface de saída),
recebendo seu pagamento direto do ambiente.
¾ Se uma sequência se quebra, a regra final da sequência perde seu strength, e a
sequência tende a se deteriorar no tempo.
¾ Descoberta de Regras
• processo de descoberta de regras em sistemas classificadores utiliza um
algoritmo genético.
¾ Basicamente, o GA seleciona os classificadores com os maiores strengths como pais,
gerando novos indivíduos por meio da recombinação e mutação destes. Os novos

Aula 7 13

IA369 - Gudwin & Von Zuben (1s/98)

classificadores gerados tomam o lugar dos classificadores mais fracos, modificando o

conjunto de classificadores do sistema.

Aplicações
¾ Em 1978 uma implementação de Holland e Reitman chamada de CS-1 (Cognitive
System Level One) foi treinada para aprender a tarefa de resolver 2 casos de escape
de labirinto. Ela utilizava um sistema de análise de desempenho com lista de
mensagens e classificadores simples, um algoritmo de credit assignment que retinha
informações sobre todos os classificadores ativos, ajustando seu strength, e um GA
com reprodução, crossover, mutação e agrupamento, de modo a gerar novos
classificadores. O principal resultado demostrou que o sistema podia transferir sua
experiência em labirintos simples, de modo a resolver problemas em labirintos mais
complexos.

Aula 7 14
 IA369 - Gudwin & Von Zuben (1s/98)

¾ Smith (1980) estudou um sistema de classificadores utilizando um GA puro, pulando

as etapas de credit assignment. Ele representava toda uma base de regras por meio de
um único cromossomo. O sistema de Smith, chamado de LS-1 (Learning System 1)
foi aplicado aos labirintos de Holland e Reitman e ao problema do jogador de pôquer.
No caso do problema do jogador de pôquer, o sistema de Smith foi capaz de bater um
outro programa feito por Waterman (1970), que utilizava um grande número de
informações específicas ao domínio do problema.
¾ Booker estudou os sistemas classificadores dentro do contexto de criaturas artificiais
em um ambiente virtual bi-dimensional, contendo objetos associados a “comida” e
“veneno”. O sistema de classificadores utilizado por Booker continha uma série de
inovações, tais como o uso de compartilhamento para promover o aproveitamento de
“nichos”, e o uso de restrições na geração de pares, de modo a evitar gerações
proibidas (letais).

Aula 7 15

IA369 - Gudwin & Von Zuben (1s/98)

¾ Em 1983, Goldberg utilizou sistemas classificadores para controlar 2 sistemas de

engenharia: um problema de controle de pêndulo e um sistema de compressão de gás
natural em pipelines. As simulações ocorreram na forma de estímulo-resposta, com o
pagamento sendo realizado por um crítico a cada instante de tempo. Goldberg
observou a formação de sub-populações estáveis servindo como hierarquias default.
Nestas, um conjunto de regras com antecedentes mais genéricos cobriam os casos
mais frequentes, sendo que as exceções eram cobertas por regras contendo
antecedentes mais específicos (que tipicamente contradiziam as regras default).
¾ Wilson (1983,1985) estudou um grande número de aplicações de sistemas
classificadores. Dentre eles, enquanto trabalhava na Polaroid, criou um sistema que
aprendia a focalizar o centro e centralizar uma video-câmera em objetos colocados em
seu campo de visão. Estes experimentos fizeram com que ele iniciasse uma
investigação sistemática envolvendo ambientes mais simples e versões mais simples

Aula 7 16
 IA369 - Gudwin & Von Zuben (1s/98)

de sistemas classificadores, de modo a entender melhor seu funcionamento. Nestes

experimentos, realizados no Rowland Institute for Science, um sistema de
classificadores chamado ANIMAT operava em um ambiente bi-dimensional,
procurando por comida escondida atrás de obstáculos. O sistema ANIMAT não
utilizava lista de mensagens, e portanto não podia utilizar o algoritmo bucket-brigade,
mas uma adaptação do mesmo.
¾ Um grande número de aplicações envolvendo sistemas classificadores e GA’s foi
desenvolvido depois destes trabalhos iniciais, em uma lista que inclui a evolução de
cooperação e predição de eventos internacionais, até técnicas de compactação para
circuitos VLSI.

Aula 7 17

IA369 - Gudwin & Von Zuben (1s/98)

Futuro dos Sistemas Classificadores

¾ Vantagens: As maiores vantagens advém da utilização de um GA, onde destaca-se o
paralelismo implícito. Além disso, existem outras vantagens, tais como a
possibilidade de incluir-se novas regras sem a imposição da severa restrição
computacional que é a verificação de inconsistência com as outras regras dos sistema.
Os SC podem conter um grande número de regras contraditórias, parcialmente
confirmadas, que servem de alternativa quando as regras atuais deixam de ser efetivas
na obtenção dos propósitos especificados. Esta comunhão dos SC’s com os GA’s
provê uma metodologia robusta no tratamento de dados com ruído.
¾ Problemas: Os problemas mais sérios encontrados dizem respeito à estabilidade das
hieraquias defaults em processo de emergência. Estas hierarquias efetivamente
emergem, mas em simulações longas, podem haver colapsos catastróficos, onde

Aula 7 18
 IA369 - Gudwin & Von Zuben (1s/98)

conjuntos grandes de regras boas são perdidas. Estas regras são posteriormente re-
adquiridas, mas ao preço de uma instabilidade indesejável.
¾ Forrest (1985) demonstrou que redes semânticas podem ser implementadas de modo
simples e direto utilizando classificadores acoplados, mas a questão de como tais
estruturas podem emergir como uma resposta à experiência não foi efetivamente
estudada. Esta é mais uma lacuna do que uma falta. Hoje se têm apenas uma pequena
idéia do comportamento do algoritmo bucket-brigade quando sequências longas e
intercaladas são formadas. Existe uma grande demanda de pesquisa nestes temas.
¾ Técnicas: Algumas técnicas podem ser utilizadas de modo a aumentar o poder de
representação e robustez dos sistemas classificadores. Dentre elas, encontra-se o
triggering de operadores genéticos → bids baixos (indicando classificadores muito
gerais) levariam à combinação da mensagem com o classificador, de modo a gerar
novas regras. Outra técnica interessante seria o suporte → técnica que permite ao

Aula 7 19

IA369 - Gudwin & Von Zuben (1s/98)

classificador integrar diversas informações parciais relacionadas entre si. O suporte é

uma quantidade que é associada a mensagens, ao contrário dos bids. Quando um
classificador é satisfeito por várias mensagens, este soma os valores de suporte de
cada uma, e utiliza este valor para determinar os bids.
¾ Direções para o futuro: O ponto mais importante a ser investigado tem a ver com a
expansão da teoria. Neste ponto, prevê-se a contribuição da:
• Economia Matemática: organizações hierárquicas, fluxo de ganhos, competição
baseada em fluxo de ganhos, distribuição de ganhos de acordo com interação local
entre consumidores/fornecedores, taxação como controle de eficiência, divisão dos
esforços em produção e pesquisa (exploitation × exploration), etc.
• Ecologia Matemática: exploração de nichos, hierarquias filogenéticas,
polimorfismo e diversidade forçada (competição entre sub-sistemas), convergência
funcional, simbiose, parasitismo, cadeias de comidas, relações predador/presa, etc.

Aula 7 20
 IA369 - Gudwin & Von Zuben (1s/98)

• Estudo do mecanismo de paralismo implícito

• Estudo do fenômeno da emergência de tags nos SC’s.
• Geração de regras por meio de regras – níveis hierárquicos de sistemas
classificadores
• Combinação de SC’s com redes neurais e lógica fuzzy, de modo a utilizar outros
tipos de classificadores – Neural-Darwinismo

Aula 7 21

IA369 - Gudwin & Von Zuben (1s/98)

EC 7 – Veículo Auto Guiado por Sistema de Classificadores

Implemente um ambiente computacional simulando um veículo autônomo auto-guiado,
conforme as figuras a seguir, e desenvolva um sistema de classificadores para controlar
o veículo. O veículo se desloca a uma velocidade constante, e sua meta é não colidir
com as pilastras e com as paredes. O parâmetro a ser avaliado é o tempo até uma colisão.
A velocidade V = 15 unidades por iteração é
constante.
1
2
O veículo pode se deslocar a cada iteração de um

4
∆θ = -15°, 0° ou +15°, dependendo do controle
5 3

O sensor de visão descreve se, em cada uma das

7 8 6 200
9
100 áreas numeradas de 1 a 9, existe uma pilastra ou
50

não. O sensor de contato verifica se o veículo

50
entrou em contato com alguma pilastra.

Aula 7 22
 IA369 - Gudwin & Von Zuben (1s/98)

50 100 100 100 100 100 100 50

50

100

100

100

100

100

100

50

Aula 7 23