Aprendizagem por gerenciamento de ... - sel.eesc.usp.br · SEL 0362 - Inteligência Artificial 2 Introdução Neste capítulo descreve-se uma maneira de se usar exemplos positivos

SEL 0362 - Inteligência Artificial 1

Aprendizagem por gerenciamento de modelos múltiplos

Marco H. TerraDepartamento de Eng. Elétrica - EESC - USP


Introdução

● Neste capítulo descreve-se uma maneira de se usar exemplos positivos e negativos para criar um espaço de versões, que auxilia na escolha do que se deve considerar para ser um membro de uma classe.

● O procedimento de espaço de versões pode aprender rapidamente que, se existe um fluxo de exemplos positivos e negativos livres de ruídos, existe um número fixo de atributos, e um modelo de caracterização de classes pode ser expresso como uma combinação de valores para os atributos.

● Para efeito de ilustração, descreve-se como extrair conhecimento de um banco de dados que descreve os hábitos recentes de um estudante que em determinados momentos exibe uma reação alérgica com comportamento depressivo.


O método de espaço de versões● Um espaço de versões é uma representação que permite

inspecionar todas as informações úteis fornecidas por uma sequência de exemplos de aprendizagem, sem relembrar qualquer dos exemplos.

● Uma descrição por espaço de versões consiste de duas árvores complementares, uma contendo nós conectados aos modelos mais gerais e o outro contendo nós conectados aos modelos mais específicos.

● Cada ligamento entre os nós em um espaço de versões representa uma operação de especialização ou generalização entre os modelos conectados aos nós:


O método de espaço de versões● Um espaço de versões é uma representação na qual:

– Existe uma árvore de especialização e uma árvore de generalização.– Cada nó é conectado a um modelo.– Um nó na árvore de generalização é conectado a um modelo que

combina com todos os itens.– Um nó na árvore de especialização é conectado a um modelo que

combina somente um item.– Ligamentos entre nós denotam relação de generalização e

especialização entre os modelos deles.● Com escritores que conectam um nó com um modelo.● Com leitores que produzem um modelo de um nó.


O método de espaço de versões

● Figura 1. Aprendizagem em um espaço de versões. Exemplos positivos generalizam modelos específicos e eliminam modelos gerais; exemplos negativos especializam modelos gerais e eliminam modelos específicos.


Aprendizagem em um espaço de versões● Na Figura 1a existem somente dois nós. Um representa o modelo

mais geral possível, representa todos os objetos possíveis.● O outro representa um modelo muito específico que representa

somente a descrição do primeiro exemplo positivo visto.● Na Figura 1b, observa-se que modelos mais gerais ficam mais

específicos para prevenir combinações e modelos específicos ficam mais gerais para assegurar combinações.

● A Figura 1c indica que as árvores emergem do modelo mais geral e do modelo mais específico e não se expandem sempre, alguns ligamentos são cortados. Amostras positivas cortam as descrições mais gerais e amostras negativas cortam descrições mais específicas.


Aprendizagem em um espaço de versões● Eventualmente exemplos positivos e

negativos podem ser tais que somente um modelo geral e um modelo específico idêntico sobrevivam. Quando isto ocorre, como na Figura 1d, não há mais a necessidade de mais exemplos porque é certo que o único sobrevivente seja o modelo correto, assumindo que um modelo correto exista.


Aprendizagem em um espaço de versões

● Figura 2. Cada especialização de um modelo geral deve ser tal que ela seja uma generalização de algum modelo específico. Também, cada especialização não deve ser uma especialização de uma determinada generalização mais geral.


Exemplo

● Generalização e especialização resultam em uma convergência no espaço de versões.

● Vamos considerar o seguinte exemplo: suponha que um médico trata de um paciente que ocasionalmente sofre de uma reação alérgica. Por intuição, o médico considera que a alergia é um resultado direto de uma certa combinação do lugar onde o paciente come, a hora do dia, o dia da semana e o preço da refeição que o paciente paga. Pode ser, por exemplo, que o café da manhã que ele come nas sextas-feiras seja a fonte da alergia do paciente, ou alguma comida cara em um determinado restaurante (o nome do restaurante caro, no exemplo do livro texto, é Sam´s).


Exemplo

● Um modelo específico para este problema é uma lista de valores para atributos que caracterizam a situação tais como lugar, refeição, dia e custo. Um exemplo de tal modelo é

[Sam´s, jantar, quinta-feira, caro].● Tal modelo com todos os valores dos atributos especificados, podem

representar somente uma combinação de restaurante-refeição-dia-custo. Em contrapartida, o modelo descritivo mais geral não especifica qualquer valor de atributo. Uma notação para este modelo geral é uma lista de questões

[? ? ? ?] ,

com cada questão sinalizando que qualquer valor de atributo é permitido.


Exemplo

● O modelo

[Sam´s, ?, ?, caro]

representa qualquer situação na qual o paciente come um alimento caro no Sam´s em qualquer dia e em qualquer tipo de refeição.

● Uma generalização deste modelo seria:

[Sam´s, ?, ?, ?]● Uma especialização deste modelo seria:

[Sam´s, jantar, ?, caro]


Exemplo

● Vamos supor que exista uma combinação particular de características que produza alergia no paciente e que os exemplos analisados são os seguintes:Número Restaurante Refeição Dia Custo Reação

1 Sam’s Café da manhã Sexta-feira Barato Sim

2 Lobdel Almoço Sexta-feira Caro Não

3 Sam’s Almoço Sábado Barato Sim

4 Sarah’s Café da manhã Domingo Barato Não

5 Sam’s Café da manhã Domingo Caro Não


Exemplo

● Figura 3. Nasce um espaço de versões. Ele consiste de um exemplo positivo - junto com o modelo mais geral possível - que representa qualquer caso.


Exemplo

● Figura 4. Um exemplo negativo força a especialização do modelo mais geral possível. Cada especialização deve ser uma generalização de um único modelo específico.


Exemplo

● Note que cada especialização envolve uma mudança mínima para o modelo mais geral, [?, ?, ?, ?]. Constrói-se cada uma trocando a interrogação no modelo mais geral pela parte correspondente do modelo mais específico. Este método assegura que cada nova especialização é uma generalização do modelo mais específico. Isto assegura que especializações dos modelos mais gerais podem eventualmente convergir com generalizações do modelo específico existente.

● A especialização [?, ?, sexta, ?] não aparece no espaço de versões porque ela combina com com o exemplo negativo [Lobdel almoço sexta caro]. O ponto de especialização da descrição mais geral é prevenir uma combinação com o exemplo negativo.


Exemplo

● O terceiro exemplo, um exemplo positivo, força a generalização do modelo mais específico, Figura 5.

● Constrói-se o novo modelo comparando o modelo mais específico existente com o exemplo positivo. Em cada lugar onde o modelo mais específico difere do exemplo positivo, o item existente no modelo mais específico é trocado por uma interrogação. Assim,

● [Sam´s café-da-manhã sexta barato] é comparado com● [Sam´s almoço sábado barato] produzindo● [Sam´s ? ? barato]● Assim, o modelo mais específico prévio é trocado por uma nova

generalização que é a mesma, exceto onde o novo exemplo positivamente força uma mudança.


Exemplo

● Figura 5. Um exemplo positivo força a generalização de um modelo específico. O novo modelo específico mais geral é geral o bastante para representar ambos exemplos positivos analisados. Também, um modelo mais geral é eliminado.


Exemplo

● Note também, ainda na Figura 5, que

[Sam´s almoço sábado barato]

não pode possivelmente representar os modelos mais gerais

[? café-da-manhã ? ?]

ou qualquer outro modelo que seja uma especialização de

[? café-da-manhã ? ?].● Então, [? café-da-manhã ? ?] não pode ser considerado no

processo de solução, então ele é eliminado.


Exemplo

● Figura 6. Outro exemplo negativo força a especialização de um dos modelos mais gerais. Este novo modelo é rapidamente eliminado, por ele ser uma especialização de outro modelo mais geral


Exemplo

● O quarto exemplo (negativo) da Figura 6, força a especialização de qualquer modelo geral que o representa.

● Porque [Sam’s ? ? ?] não representa

[Sarah’s café-da-manhã domingo barato]

ele não precisa ser especializado.● Porque [? ? ? barato] representa

[Sarah’s café-da-manhã domingo barato]

ele requer especialização.● A especialização de [? ? ? barato] deve tomar a direção de uma generalização de um

modelo específico, na qual existe somente um,

[Sam’s ? ? barato].● O único caminho é especializar [? ? ? barato] para [Sam’s ? ? barato], o que o faz

um novo modelo geral e idêntico ao modelo específico.


Exemplo

● Note que a nova especialização

[Sam’s ? ? barato]

é também uma especialização de um novo modelo geral sobrevivente,

[? ? ? barato].

Em virtude disto ela é eliminada.● Quando os modelos gerais e os específicos convergem, significa que os

exemplos negativos e positivos não permitem nenhum outro modelo.● Neste ponto, somente um modelo geral e um modelo específico

permanecem

( [Sam’s ? ? ?] e [Sam’s ? ? Barato] ).● Considere agora o próximo exemplo da Figura 7:


Exemplo

● Figura 7. Finalmente um outro exemplo negativo força a especialização somente do modelo geral restante. Este novo modelo geral é o mesmo que o modelo específico. Isto significa que o conjunto geral e o conjunto específico convergiram, produzindo um modelo possível para a resposta desejada.


Exemplo

● Na Figura 7 um exemplo negativo para

[ Sam’s café-da-manhã domingo caro]

força uma especialização de

[ Sam’s ? ? ?]

gerando um novo modelo geral

[ Sam’s ? ? barato]

que é idêntico ao modelo específico. Assim, conclui-se a aprendizagem.

● Comida barata no Sam’s produz a alergia.


Resumo

● Características do espaço de versões● Em resumo, os exemplos positivos e negativos são considerados

simetricamente no espaço de versões.● Para responder aos exemplos positivos e negativos usando um

espaço de versões:● Se o exemplo é positivo,

– generalize todos os modelos específicos para representar o exemplo positivo, mas assegure o seguinte,

– os novos modelos específicos envolvem mudanças mínimas,– cada novo modelo específico é uma especialização de um modelo geral,– nenhum novo modelo específico é uma generalização de um outro modelo

específico.


Resumo

– Corte todos os modelos gerais que falhem na representação de um exemplo positivo.

● Se o exemplo é negativo,– especialize todos os modelos gerais para prevenir uma combinação

com o exemplo negativo, devendo valer o seguinte:– os novos modelos gerais envolvem mudanças mínimas,– cada novo modelo geral é uma generalização de um determinado

modelo específico,– nenhum novo modelo geral é uma especialização de um outro modelo

geral.– Elimine todos os modelos específicos que representem o exemplo

negativo.

Documents

Aprendizagem por gerenciamento de ... - sel.eesc.usp.br · SEL 0362 - Inteligência Artificial 2 Introdução Neste capítulo descreve-se uma maneira de se usar exemplos positivos