Sistemas Classificadores

if <condição> then <ação>

O significado de uma regra de produção é que a ação deve ser executada quando a condição é satisfeita. À primeira vista, uma unidade simples como esta pode parecer trazer restrições à representação do conhecimento. Entretanto, Misky (67) e Post (43) demonstraram que sistemas de produção são computacionalmente completos. Seu poder para representar conhecimento envolve mais do que isso. Eles também são computacionalmente convenientes.

Apesar do crescimento de aplicações usando sistemas especialistas, sistemas baseados em regras têm sido menos freqüentemente sugeridos em situações onde há necessidade de aprendizagem. Um dos obstáculos principais para aprender tem sido a complexidade da sintaxe das regras. Muitos sistemas de produção permitem a construção de condições e ações com gramática envolvida como partes de uma regra.

Sistemas classificadores partem de cara restringindo uma regra a uma representação de tamanho fixo. Essa restrição tem 2 benefícios: Primeiro, todos os strings representados com o alfabeto permitido são sintaticamente importantes. Segundo, um string de tamanho fixo permite a utilização de operadores do tipo genético. Isto deixa a porta aberta para que GA pesquisem todo o espaço de regras permissíveis.

Para fazer isto, as múltiplas atividades dos sistemas classificadores precisam ser coordenadas simultaneamente. Quando escolhas precisam ser feitas entre ações ambientais mutuamente exclusivas ou quando o tamanho do conjunto de regras deve ser aparado para acomodar a lista de mensagens de tamanho fixo, tais decisões são postergadas até o último momento possível, e a decisão é executada competitivamente. Embora vejamos mais detalhes à frente, é hora de reconhecer que o paralelismo encorajado pela arquitetura dos sistemas classificadores pode permitir implementações rápidas ao mesmo tempo que promove decisões racionais sem estratégias arbitrais arbitrárias.

Em sistemas especialistas o valor ou peso ou classificação de uma regra relativamente às demais é fixada pelo programador em conjunto com o especialista. Em sistemas classificadores não se tem esse luxo. O valor relativo das diferentes regras é um dos pontos chave que devem ser aprendidos pelo sistema. Para facilitar esse tipo de aprendizado sistemas classificadores forçam os classificadores a coexistir em uma economia de mercado. A competição é obtida entre classificadores, onde o direito de responder a mensagens relevantes vai para o maior ofertante, com o subseqüente pagamento das ofertas servindo como fonte do rendimento para os enviadores de mensagens prévias que tiveram sucesso. Desta maneira uma cadeia de meios-de-campo é formada entre os manufaturadores (os detectores) e os consumidores (ações ambientais e pagamentos). A natureza competitiva do mercado assegura que boas regras (proveitosas) sobrevivem enquanto más regras morrem.

Ver-se-á mais tarde em mais detalhes, o algoritmo de distribuição de crédito, mas por enquanto um ponto é crucial: a introdução de um dinheiro interno. O câmbio e a acumulação do dinheiro provê um mecanismo natural para a aplicação de algoritmos genéticos. Usando um balanço bancário classificador como função objetivo, classificadores podem ser reproduzidos, sofrer crossover, e sofrer mutação que são a base dos algoritmos genéticos.

Juntos, a distribuição de crédito via competição e a descoberta de regras usando GA formam uma base razoável para a construção de sistemas de aprendizado de máquina. Além de conveniência computacional e um completo esquema de trabalho de classificadores. Agora, olharemos cada um dos componentes em detalhe.

Sistema de regras e mensagens

O sistema de regras e mensagens forma a espinha dorsal do sistema. A informação chega do ambiente através dos detectores, os olhos e ouvidos dos sistemas   classificadores, onde são decodificados em uma ou mais mensagens de   comprimento finito. Essas mensagens são colocadas em uma lista (também de   comprimento finito). Aqui, as mensagens ativam regras chamadas classificadores.  
Quando ativado, um classificador coloca uma mensagem na lista de mensagens.   Essas mensagens podem então invocar outros classificadores ou podem causar ações gatilho a serem tomadas pelo sistema, através dos chamados efetores. Dessa maneira, os classificadores combinam insinuações ambientais com raciocínios internos para determinar o que o sistema deve fazer e pensar no futuro. Nesse sentido, ele coordena o fluxo de informação de onde ele é sentido (detectores) até onde ele é processado   (lista de mensagens e armazém do classificador) para aonde ele chama ações (efetores). Para melhor entender a operação de um sistema de regras e mensagens, veja-se as duas unidades de informação: mensagens e classificadores -- e como eles são processados.

Uma mensagem dentro de um sistema classificador é simplesmente um string de comprimento fixo finito sobre algum alfabeto finito. Se nos limitarmos ao alfabeto binário, teremos a seguinte definição:

<mensagem> ::=    {0,1}k

Onde o símbolo ::= significa "é definido como" e elevando o conjunto {0, 1} à potência k dizemos que concatenamos elementos de {0, 1} k vezes. Mensagens são o componente básico das trocas de informação em um sistemas classificador. As mensagens na lista de mensagens devem casar com um ou mais classificadores ou regras. Um classificador é uma regra de produção com uma sintaxe extremamente simples:

<classificador> ::=   <condição> :  <mensagem>.

A condição é um simples reconhecedor de padrões onde um caractere coringa é adicionado ao alfabeto.

<condição> ::= {O, 1, #}k.

Então uma condição casa com uma mensagem se 0 casa com 0, 1 casa com 1, e # casa com qualquer coisa. Por exemplo, a condição #01# casa com mensagem 0010, mas não casa com 0000.

Uma vez que a condição de um classificador é atingida então o classificador torna-se candidato a postar uma mensagem na lista de mensagens no próximo step time. Se ele vai postar ou não a mensagem é determinado pelo resultado de um leilão de ativação o que, por seu turno, depende da avaliação do valor ou peso do classificador.

Para consolidar o nosso entendimento do trabalho de um sistema de regras e mensagens, simularemos a atividade de match a mão. Suponhamos ter os seguintes classificadores:

1) 01##:0000
2) 00#0:1100
3) 11##:1000
4) ##00:0001

Quando uma mensagem ambiental 0111 chega a lista de mensagens, ela casa com o classificador 1, que por sua vez posta a mensagem 0000. Esta aciona os classificadores 2 e 4, que colocam suas mensagens (1100 e 0001). A primeira dispara os classificadores 3 e 4. A mensagem enviada pelo 3, (1000) bate com o classificador 4 e o processo termina.

Um sistema de regras e mensagens simples é sempre mecanicamente "para frente". Diversos estudos estenderam a sintaxe dos classificadores para permitir condições múltiplas (goldberg,83) e caracteres pass-through (Forrest, 85b Riolo, 86a). Seguindo o velho acrônimo dos militares KISS (kept it simple, stupid), deixaremos as dificuldades para depois. Mesmo um sistema simples permite que interessantes comportamentos sejam aprendidos. Ele também traz algumas questões importantes. Uma delas vem à mente imediatamente: Quando a lista de mensagens tem tamanho insuficiente para aceitar todos os classificadores que foram casados com mensagens, como determinar quais classificadores ativar? A resposta é o subsistema de distribuição de crédito.

Algoritmo de distribuição de crédito: a brigada de incêndio

Este algoritmo foi batizado por Holland. A brigada de incêndio pode muito facilmente ser vista (com algum uso de metáforas), como um mercado de informações, no qual o direito de comerciar informações é comprado e vendido pelos classificadores. Classificadores formam uma cadeia de homens intermediários dos produtores de informação (o ambiente) aos consumidores de informação (os efetores).

Este mercado contém dois outros componentes: um leilão e uma câmara de compensação. Quando os classificadores (matched) casam com as mensagens, eles não postam diretamente suas mensagens. Ao invés disso, ao casarem, eles ganham qualificação para participarem de um leilão de ativação. Para participar deste leilão, cada classificador mantém um registro de seu preço líquido, chamado vigor (strength). Cada classificador casado (matched) faz um lance B proporcional ao seu vigor. Dessa maneira, regras que são altamente aptas (tendo acumulado no passado bastante dinheiro) têm preferência sobre outras regras. Outras estruturas de oferecer lances têm sido sugeridas e olharemos algumas delas, entretanto nossa busca por simplicidade governará nossa escolha.

O leilão permite que os classificadores sejam selecionados para postar suas mensagens. Mas isto ainda não é o fim da nossa história da brigada de incêndio. Uma vez que um classificador foi selecionado para ativação, ele deve liquidar seu pagamento através da câmara de compensação pagando seu lance a outros classificadores, para retribuição do casamento de mensagens. O classificador casado e ativado, manda sua oferta B para aqueles classificadores responsáveis por enviar a mensagem que causou a condição de casamento para o classificador ofertante. O pagamento da oferta B é dividido de alguma maneira entre os classificadores casando.

Esta divisão do pagamento entre os classificadores contribuindo, ajuda a assegurar a formação de subpopulação de tamanho apropriado de regras (Booker, 1982). Então, diferentes tipos de regras podem cobrir diferentes tipos de requerimentos de comportamento sem competição interespécies indevida. Em um sistema de aprendizado por regras de qualquer importância, nós não podemos pesquisar por uma regra mestre. Nós devemos, ao invés, pesquisar um conjunto de regras coadaptadas que juntas cubram um intervalo de comportamento que preveja um largo payoff para o sistema de aprendizado.

Exemplificando com os quatro classificadores

Classificador         Vigor
1)    01##:0000       200
2)    00#0:1100       200
3)    11##:1000       200
4)    ##00:0001       200

e assumindo um vigor inicial de 200 para todos os quatro. Colocando-se a mensagem 0111, teremos a seguinte tabela, imaginado um coeficiente de lance de 0,1 (10%), e imaginemos o lance sendo dado como uma multiplicação entre o vigor e o coeficiente.

TEMPO = 0
Ind    Classif.             Vig         Mensagem     Quem disparou      Oferta
----    ----------------     ------      -------------------------------------------------------------------------
1)     01##:0000       200                                  ambiente                 20
2)     00#0:1100       200
3)     11##:1000       200
4)     ##00:0001       200
---------------------------------------------------------------------------------------------------------------
ambiente                        0     0111

No tempo zero (T = 0), o classificador 1 é casado (matched), oferta 20 unidades e envia sua mensagem em T = 1. O classificador 1 paga sua oferta para o parceiro responsável por sua ativação. Neste caso o vigor do ambiente é incrementado em 20 unidades, já que foi uma mensagem ambiental que ativou o classificador 1.

TEMPO = 1
Ind    Classif.             Vig         Mensagem     Quem disparou      Oferta
----    ----------------     ------      -------------------------------------------------------------------------
1)     01##:0000       180        0000                                                    
2)     00#0:1100       200                                   1                                  20
3)     11##:1000       200
4)     ##00:0001       200                                   1                                  20
---------------------------------------------------------------------------------------------------------------
ambiente                     20

TEMPO = 2
Ind    Classif.             Vig         Mensagem     Quem disparou      Oferta
----    ----------------     ------      -------------------------------------------------------------------------
1)     01##:0000       220                                 
2)     00#0:1100       180          1100
3)     11##:1000       200                                   2                                 20
4)     ##00:0001       200          0001                2                                 18
---------------------------------------------------------------------------------------------------------------
ambiente                    20

TEMPO = 3
Ind    Classif.             Vig         Mensagem     Quem disparou      Oferta
----    ----------------     ------      -------------------------------------------------------------------------
1)     01##:0000       220                                 
2)     00#0:1100       218
3)     11##:1000       180          1000
4)     ##00:0001       162          0001                 3                                 16
---------------------------------------------------------------------------------------------------------------
ambiente                      20

TEMPO = 4
Ind    Classif.             Vig         Mensagem     Quem disparou      Oferta
----    ----------------     ------      -------------------------------------------------------------------------
1)     01##:0000       220                            
2)     00#0:1100       208
3)     11##:1000       196
4)     ##00:0001       156           0001
---------------------------------------------------------------------------------------------------------------
ambiente                     20

TEMPO FINAL
Vig     Oferta
----       --------------------------------------------------------
220
208
196
206      50
-----------------------------------------------------------------
ambiente                        20

Para implementar um procedimento bem definido, devemos ser mais rigorosos na definição dos detalhes do leilão e do esquema de pagamentos. Como já indicado, os classificadores fazem lances Bk durante o leilão. Classificadores vencedores voltam seus lances para a câmara de compensação como um pagamento (Pk). Um classificador pode também ter receitas Rk de seus enviadores de mensagens prévios ou como recompensa do ambiente. Em adição a ofertas e receitas, um classificador pode estar sujeito a uma ou mais taxas Tk. Tomados todos juntos, podemos escrever uma equação que governe a perda ou ganho de receita do vigor Sk de um classificador, como segue:

Sk(t+1)=Sk(t)-Pk(t)-Tk(t)+Rk(t)

Para entender a acumulação de riqueza do classificador em detalhe, também devemos quantificar sua oferta, pagamento e taxas. A oferta B é proporcional ao vigor.

Bk = Cbid . Sk

Onde Cbid é o coeficiente de ofertas, S é o vigor do classificador e k é um índice.

Nós podemos simplesmente parar aqui e selecionar os ganhadores do leilão deterministicamente pela seleção dos j melhores classificadores (onde j é o tamanho da lista de mensagens), entretanto isto poderia causar prejuízos para com o status quo (De Groot, 1970).

Entretanto, queremos segurar nosso leilão em presença de ruído randômico. Calcularemos o lance efetivo (EB) para cada classificador casado como a soma de seu lance determinístico com um termo ruído.

EBk = Bk + N (ðbid)

Onde o ruído N é uma função do desvio padrão específico do ruído da oferta.

Depois que o leilão (com algum ruído) e a seleção de quais classificadores reenviaram suas mensagens, o pagamento deve ser feito para aqueles classificadores responsáveis pelo envio das mensagens que ativaram os vencedores. Os vencedores pagam seus lances (o valor B, e não os valores EB) à câmara de compensação, onde o pagamento é dividido entre os classificadores responsáveis pelo envio da mensagem matched e vencedora.

Cada classificador é taxado, para prevenir a carga gratuita, o que acarretaria prejuízo à população através das regras. Muitos esquemas estão disponíveis: aqui, simplesmente se recolherá uma taxa proporcional ao vigor S do classificador.

Tk = Ctax - Sk

Juntos, estes relacionamentos definem o algoritmo de distribuição de crédito usados em diversos sistemas classificadores. Para examinar a estabilidade e o efeito deste mecanismo, relembremos a equação de pagamento, substituindo todo o mundo em função do vigor S.

Sk(t+1)  =  Sk(t)   -   Pk(t)   -  Tk(t)    +  Rk(t)    ===        equação original

S (t+1)  =    S(t)    -  Cbid.S (t)     -    Ctax.S (t)  +   R(t)     ===     nova equação

Reagrupando

S(t+1)  =  (1 - K)    .   S(t)   +    R(t),    onde K  =  Cbid + Ctax

Prova-se, através de transformadas Z que esta equação e estável.

Algoritmo genético

O algoritmo da brigada de incêndio provê um bom procedimento para avaliar regras e decidir entre alternativas competidoras. Mas ainda precisamos achar uma maneira de injetar regras, possivelmente melhores, no sistema. As regras de um algoritmo genético convencional serão introduzidas e processadas pelos mecanismos de leilão, pagamento e reforço para avaliar apropriadamente seu papel no sistema. Devemos esquecer de trocar a população toda e olhar mais atentamente para quem substitui quem. Nas aplicações de machine learning não é conveniente a substituição de toda a população. Aqui precisamos de bom desempenho em performance on-line, enquanto na pesquisa e otimização precisamos convergência (ou performance off-line).

De Jong implementou o fator C (de troca generacional). Aqui definiremos uma quantidade chamada proporção de seleção proporção, que indicará quantos elementos substituir. Também definiremos uma quantidade chamada período de AG (TGA) que indicará a quantidade de ciclos de tempo (ciclos de regras e mensagens) que deverão ser invocados entre as chamadas ao AG. Este valor pode ser tratado deterministicamente (AG será chamado a cada TGA ciclos) ou estocasticamente (AG é chamado probabilisticamente com período médio TGA). Além disso a invocação do AG pode ser disparada por determinados eventos (perda de match; baixa performance, etc.).

A seleção por roda da roleta usará como parâmetro o vigor S de cada classificador. É preciso estudar quem sai, e o procedimento de crowdind de DeJong (75) pode ser usado.

A mutação deve ser modificada, porque os classificadores usam um alfabeto ternário. A probabilidade de mutação é usada como anteriormente definida. Mas uma vez atingida um caractere será substituído por qualquer um dos outros dois com igual probabilidade. Com essas trocas, o algoritmo genético segue igual ao tradicional.

kantek@celepar.gov.br