aula5

Prévia do material em texto

Aprendizagem por 
gerenciamento de modelos 
múltiplos
Aprendizagem por 
gerenciamento de modelos 
múltiplos
Marco Henrique TerraMarco Henrique Terra
Introdução à Inteligência Artificial
IntroduçãoIntrodução
nn Neste capNeste capíítulo descrevetulo descreve--se uma maneira de se usar se uma maneira de se usar 
exemplos positivos e negativos para criar um espaexemplos positivos e negativos para criar um espaçço de o de 
versões, que auxilia na escolha do que se deve considerar versões, que auxilia na escolha do que se deve considerar 
para ser um membro de uma classe.para ser um membro de uma classe.
nn O procedimento de espaO procedimento de espaçço de versões pode aprender o de versões pode aprender 
rapidamente que, se existe um fluxo de exemplos positivos rapidamente que, se existe um fluxo de exemplos positivos 
e negativos livres de rue negativos livres de ruíídos, existe um ndos, existe um núúmero fixo de mero fixo de 
atributos, e um modelo de caracterizaatributos, e um modelo de caracterizaçção de classes pode ão de classes pode 
ser expresso como uma combinaser expresso como uma combinaçção de valores para os ão de valores para os 
atributos.atributos.
nn Para efeito de ilustraPara efeito de ilustraçção, descreveão, descreve--se como extrair se como extrair 
conhecimento de um banco de dados que descreve os conhecimento de um banco de dados que descreve os 
hháábitos recentes de um estudante que em determinados bitos recentes de um estudante que em determinados 
momentos exibe uma reamomentos exibe uma reaçção alão aléérgica com comportamento rgica com comportamento 
depressivo.depressivo.
O método de espaço de versõesO método de espaço de versões
nn Um espaUm espaçço de versões o de versões éé uma representauma representaçção que permite ão que permite 
inspecionar todas as informainspecionar todas as informaçções ões úúteis fornecidas teis fornecidas por por uma uma 
sequência sequência de exemplos de aprendizagem, sem relembrar de exemplos de aprendizagem, sem relembrar 
qualquer dos exemplos.qualquer dos exemplos.
nn Uma descriUma descriçção ão porpor espaespaçço de versões consiste de duas o de versões consiste de duas 
áárvores complementares, uma contendo nrvores complementares, uma contendo nóós conectados aos s conectados aos 
modelos mais gerais e o outro contendo nmodelos mais gerais e o outro contendo nóós conectados aos s conectados aos 
modelos mais especmodelos mais especííficos.ficos.
nn Cada ligamento entre os nCada ligamento entre os nóós em um espas em um espaçço de versões o de versões 
representa uma operarepresenta uma operaçção de especializaão de especializaçção ou ão ou 
generalizageneralizaçção entre os modelos conectados aos não entre os modelos conectados aos nóós: s: 
nn Um espaUm espaçço de versões o de versões éé uma representauma representaçção na qual:ão na qual:
-- Existe uma Existe uma áárvore de especializarvore de especializaçção e uma ão e uma áárvore de rvore de 
generalizageneralizaçção.ão.
-- Cada nCada nóó éé conectado a um modelo.conectado a um modelo.
-- Um nUm nóó na na áárvore de generalizarvore de generalizaçção ão éé conectado a um conectado a um 
modelo que combina com todos os itens.modelo que combina com todos os itens.
-- Um nUm nóó na na áárvore de especializarvore de especializaçção ão éé conectado a um conectado a um 
modelo que combina somente um item.modelo que combina somente um item.
-- Ligamentos entre nLigamentos entre nóós denotam relas denotam relaçção de generalizaão de generalizaçção e ão e 
especializaespecializaçção entre os modelos deles.ão entre os modelos deles.
Com escritores que conectam um nCom escritores que conectam um nóó com um modelo.com um modelo.
Com leitores que produzem um modelo de um nCom leitores que produzem um modelo de um nóó. . 
nn Figura 1.Figura 1.
Aprendizagem em umAprendizagem em um
espaespaçço de versões.o de versões.
Exemplos positivosExemplos positivos
generalizam modelosgeneralizam modelos
especespecííficos e eliminam ficos e eliminam 
modelos gerais; modelos gerais; 
exemplos negativos exemplos negativos 
especializam modelos especializam modelos 
gerais e eliminam gerais e eliminam 
modelos especmodelos especííficos. ficos. 
nn Na Figura 1a existem somente dois nNa Figura 1a existem somente dois nóós. Um representa o s. Um representa o 
modelo mais geral possmodelo mais geral possíível, representa todos os objetos vel, representa todos os objetos 
posspossííveis.veis.
nn O outro representa um modelo muito especO outro representa um modelo muito especíífico que fico que 
representa somente a descrirepresenta somente a descriçção do primeiro exemplo ão do primeiro exemplo 
positivo visto.positivo visto.
nn Na Figura 1b, observaNa Figura 1b, observa--se que modelos mais gerais ficam se que modelos mais gerais ficam 
mais especmais especííficos para prevenir combinaficos para prevenir combinaçções e modelos ões e modelos 
especespecííficos ficam mais gerais para assegurar combinaficos ficam mais gerais para assegurar combinaçções.ões.
nn A Figura 1c indica que as A Figura 1c indica que as áárvores emergem do modelo rvores emergem do modelo 
mais geral e do modelo mais especmais geral e do modelo mais especíífico e não se expandem fico e não se expandem 
sempre, alguns ligamentos são cortados. Amostras sempre, alguns ligamentos são cortados. Amostras 
positivas cortam as descripositivas cortam as descriçções mais gerais e amostras ões mais gerais e amostras 
negativas cortam descrinegativas cortam descriçções mais especões mais especííficas. ficas. 
nn Eventualmente exemplos positivos e negativos podem ser Eventualmente exemplos positivos e negativos podem ser 
tais que somente um modelo geral e um modelo espectais que somente um modelo geral e um modelo especíífico fico 
idêntico sobrevivam. Quando isto ocorre, como na Figura idêntico sobrevivam. Quando isto ocorre, como na Figura 
1d, não h1d, não háá mais a necessidade de mais exemplos porque mais a necessidade de mais exemplos porque éé
certo que o certo que o úúnico sobrevivente seja o modelo correto, nico sobrevivente seja o modelo correto, 
assumindo que um modelo correto exista.assumindo que um modelo correto exista.
nn Figura 2. Cada Figura 2. Cada 
especializaespecializaçção de um ão de um 
modelo geral deve ser modelo geral deve ser 
tal que ela seja uma tal que ela seja uma 
generalizageneralizaçção de algum ão de algum 
modelo especmodelo especíífico. fico. 
TambTambéém, cada m, cada 
especializaespecializaçção não deve ão não deve 
ser uma especializaser uma especializaçção ão 
de uma determinada de uma determinada 
generalizageneralizaçção mais ão mais 
geral.geral.
nn GeneralizaGeneralizaçção e especializaão e especializaçção resultam em uma ão resultam em uma 
convergência no espaconvergência no espaçço de versões.o de versões.
nn Vamos considerar o seguinte exemplo: suponha que um Vamos considerar o seguinte exemplo: suponha que um 
mméédico trata de um paciente que ocasionalmente sofre de dico trata de um paciente que ocasionalmente sofre de 
uma reauma reaçção alão aléérgica. rgica. Por Por intuiintuiçção, o mão, o méédico considera que a dico considera que a 
alergia alergia éé um resultado direto de uma certa combinaum resultado direto de uma certa combinaçção do ão do 
lugar onde o paciente come, a hora do dia, o dia da semana e lugar onde o paciente come, a hora do dia, o dia da semana e 
o preo preçço da refeio da refeiçção que o paciente paga. Pode ser, ão que o paciente paga. Pode ser, por por 
exemplo, que o cafexemplo, que o caféé da manhã que ele come nas sextasda manhã que ele come nas sextas--feiras feiras 
seja a fonte da alergia do paciente, ou alguma comida cara seja a fonte da alergia do paciente, ou alguma comida cara 
em um determinado restaurante (o nome do restaurante caro, em um determinado restaurante (o nome do restaurante caro, 
no exemplo do livro texto, no exemplo do livro texto, éé SamSam´´s). s). 
nn Um modelo especUmmodelo especíífico para este problema fico para este problema éé uma lista de uma lista de 
valores para atributos que caracterizam a situavalores para atributos que caracterizam a situaçção tais ão tais 
como lugar, refeicomo lugar, refeiçção, dia e custo. Um exemplo de tal ão, dia e custo. Um exemplo de tal 
modelo modelo éé
[[SamSam´´s, jantar, quintas, jantar, quinta--feira, caro].feira, caro].
Tal modelo com todos os valores dos atributos Tal modelo com todos os valores dos atributos 
especificados, podem representar somente uma especificados, podem representar somente uma 
combinacombinaçção de restauranteão de restaurante--refeirefeiççãoão--diadia--custo. Em custo. Em 
contrapartida, o modelo descritivo mais geral não contrapartida, o modelo descritivo mais geral não 
especifica qualquer valor de especifica qualquer valor de atriburtoatriburto. Uma nota. Uma notaçção para ão para 
este modelo geral este modelo geral éé uma lista de questõesuma lista de questões
[? ? ? ?][? ? ? ?]
com cada questão sinalizando que qualquer valor de com cada questão sinalizando que qualquer valor de 
atributo atributo éé permitido. permitido. 
nn O modeloO modelo
[[SamSam´´s, ?, ?, caro]s, ?, ?, caro]
representa qualquer situarepresenta qualquer situaçção na qual o paciente come um ão na qual o paciente come um 
alimento caro no alimento caro no SamSam´´s em qualquer dia e em qualquer s em qualquer dia e em qualquer 
tipo de refeitipo de refeiçção.ão.
Uma generalizaUma generalizaçção deste modelo seria: ão deste modelo seria: 
[[SamSam´´s, ?, ?, ?]s, ?, ?, ?]
Uma especializaUma especializaçção deste modelo seria:ão deste modelo seria:
[[SamSam´´s, jantar, ?, caro]s, jantar, ?, caro]
nn Vamos supor que exista uma combinaVamos supor que exista uma combinaçção particular de ão particular de 
caractercaracteríísticas que produza alergia no paciente e que os sticas que produza alergia no paciente e que os 
exemplos analisados são os seguintes:exemplos analisados são os seguintes:
nn nnúúmm. restaurante refei. restaurante refeiçção ão dia custo readia custo reaççãoão
nn 1 1 SamSam´´s cafs caféé(manhã) (manhã) sex sex barato simbarato sim
nn 2 2 Lobdel Lobdel almoalmoçço o sex sex caro nãocaro não
nn 3 3 SamSam´´s almos almoçço o sabsab. barato sim. barato sim
nn 4 4 SarahSarah´´s cafs caféé(manhã) dom. barato não(manhã) dom. barato não
nn 5 5 SamSam´´s cafs caféé(manhã) dom. caro não(manhã) dom. caro não
nn Figura 3. Nasce um espaFigura 3. Nasce um espaçço de versões. Ele consiste de um o de versões. Ele consiste de um 
exemplo positivo exemplo positivo -- junto com o modelo mais geral possjunto com o modelo mais geral possíível vel 
-- que representa qualquer caso.que representa qualquer caso.
nn Figura 4. Um exemplo negativo forFigura 4. Um exemplo negativo forçça a especializaa a especializaçção do ão do 
modelo mais geral possmodelo mais geral possíível. Cada especializavel. Cada especializaçção deve ser ão deve ser 
uma generalizauma generalizaçção de um ão de um úúnico modelo especnico modelo especíífico.fico.
nn Note que cada especializaNote que cada especializaçção envolve uma mudanão envolve uma mudançça a 
mmíínima para o modelo mais geral, [?, ?, ?, ?]. Constrnima para o modelo mais geral, [?, ?, ?, ?]. Constróóii--se se 
cada uma trocando a interrogacada uma trocando a interrogaçção no modelo mais geral ão no modelo mais geral 
pela parte correspondente do modelo mais especpela parte correspondente do modelo mais especíífico. Este fico. Este 
mméétodo assegura que cada nova especializatodo assegura que cada nova especializaçção ão éé uma uma 
generalizageneralizaçção do modelo mais especão do modelo mais especíífico. Isto assegura que fico. Isto assegura que 
especializaespecializaçções dos modelos mais gerais podem ões dos modelos mais gerais podem 
eventualmente convergir com generalizaeventualmente convergir com generalizaçções do modelo ões do modelo 
especespecíífico existente.fico existente.
nn A especializaA especializaçção [?, ?, sexta, ?] não aparece no espaão [?, ?, sexta, ?] não aparece no espaçço de o de 
versões porque ela combina com com o exemplo negativo versões porque ela combina com com o exemplo negativo 
[[Lobdel Lobdel almoalmoçço sexta caro]. O ponto de especializao sexta caro]. O ponto de especializaçção da ão da 
descridescriçção mais geral ão mais geral éé prevenir uma combinaprevenir uma combinaçção com o ão com o 
exemplo negativo. exemplo negativo. 
nn O terceiro exemplo, um exemplo positivo, forO terceiro exemplo, um exemplo positivo, forçça a a a 
generalizageneralizaçção do modelo mais especão do modelo mais especíífico, Figura 5. fico, Figura 5. 
ConstrConstróóii--se o novo modelo comparando o modelo mais se o novo modelo comparando o modelo mais 
especespecíífico existente com o exemplo positivo. Em cada fico existente com o exemplo positivo. Em cada 
lugar onde o modelo mais especlugar onde o modelo mais especíífico difere do exemplo fico difere do exemplo 
positivo, o item existente no modelo mais especpositivo, o item existente no modelo mais especíífico fico éé
trocado trocado por por uma interrogauma interrogaçção. Assim, ão. Assim, 
nn [[SamSam´´s cafs caféé--dada--manhã sexta barato] manhã sexta barato] éé comparado comcomparado com
nn [[SamSam´´s almos almoçço so sáábado barato] produzindobado barato] produzindo
nn [[SamSam´´s ? ? barato] s ? ? barato] 
Assim, o modelo mais especAssim, o modelo mais especíífico prfico préévio vio éé trocado trocado por por uma uma 
nova generalizanova generalizaçção que ão que éé a mesma, exceto onde o novo a mesma, exceto onde o novo 
exemplo positivamente forexemplo positivamente forçça uma mudana uma mudançça. a. 
nn Figura 5. Um exemplo positivo forFigura 5. Um exemplo positivo forçça a generalizaa a generalizaçção de ão de 
um modelo especum modelo especíífico. O novo modelo especfico. O novo modelo especíífico mais fico mais 
geral geral éé geral o bastante para representar ambos exemplos geral o bastante para representar ambos exemplos 
positivos analisados. Tambpositivos analisados. Tambéém, um modelo mais geral m, um modelo mais geral éé
eliminado. eliminado. 
nn Note tambNote tambéém, ainda na Figura 5, que m, ainda na Figura 5, que 
[[SamSam´´s almos almoçço so sáábado barato] bado barato] 
não pode possivelmente representar os modelos mais geraisnão pode possivelmente representar os modelos mais gerais
[? caf[? caféé--dada--manhã ? ?] manhã ? ?] 
ou qualquer outro modelo que seja uma especializaou qualquer outro modelo que seja uma especializaçção deão de
[? caf[? caféé--dada--manhã ? ?]. manhã ? ?]. 
Então, [? cafEntão, [? caféé--dada--manhã ? ?] não pode ser considerado no manhã ? ?] não pode ser considerado no 
processo de soluprocesso de soluçção, então ele ão, então ele éé eliminado.eliminado.
nn Figura 6. Outro exemplo negativo forFigura 6. Outro exemplo negativo forçça a especializaa a especializaçção ão 
de um dos modelos mais gerais. Este novo modelo de um dos modelos mais gerais. Este novo modelo éé
rapidamente eliminado, rapidamente eliminado, por por ele ser uma especializaele ser uma especializaçção de ão de 
outro modelo mais geral outro modelo mais geral 
nn O quarto exemplo (negativo) da Figura 6, forO quarto exemplo (negativo) da Figura 6, forçça a a a 
especializaespecializaçção de qualquer modelo geral que o representa. ão de qualquer modelo geral que o representa. 
nn Porque [Porque [SamSam’’s s ? ? ?] não representa ? ? ?] não representa 
[[SarahSarah’’s s cafcaféé--dada--manhã domingo barato]manhã domingo barato]
ele não precisa ser especializado.ele nãoprecisa ser especializado.
nn Porque [? ? ? barato] representa Porque [? ? ? barato] representa 
[[SarahSarah’’ss cafcaféé--dada--manhã domingo barato]manhã domingo barato]
ele requer especializaele requer especializaçção.ão.
nn A especializaA especializaçção de [? ? ? barato] deve tomar a direão de [? ? ? barato] deve tomar a direçção de ão de 
uma generalizauma generalizaçção de um modelo especão de um modelo especíífico, na qual existe fico, na qual existe 
somente um, somente um, 
[[SamSam’’s s ? ? barato].? ? barato].
O O úúnico caminho nico caminho éé especializar [? ? ? barato] para especializar [? ? ? barato] para 
[[SamSam’’s s ? ? barato], o que o faz um novo modelo geral e ? ? barato], o que o faz um novo modelo geral e 
idêntico ao modelo especidêntico ao modelo especíífico. fico. 
nn Note que a nova especializaNote que a nova especializaçção ão 
[[SamSam’’s s ? ? barato]? ? barato]
éé tambtambéém uma especializam uma especializaçção de um novo modelo geral ão de um novo modelo geral 
sobrevivente,sobrevivente,
[? ? ? barato].[? ? ? barato].
Em virtude disto ela Em virtude disto ela éé eliminada.eliminada.
nn Quando os modelos gerais e os especQuando os modelos gerais e os especííficos convergem ficos convergem 
significa que os exemplos negativos e positivos não significa que os exemplos negativos e positivos não 
permitem nenhum outro modelo.permitem nenhum outro modelo.
nn Neste ponto, somente um modelo geral e um modelo Neste ponto, somente um modelo geral e um modelo 
especespecíífico permanecem fico permanecem 
( [( [SamSam’’s s ? ? ?] e [? ? ?] e [SamSam’’s s ? ? Barato] ).? ? Barato] ).
Considere Considere agora agora o pro próóximo exemplo da Figura 7: ximo exemplo da Figura 7: 
nn Figura 7. Finalmente um Figura 7. Finalmente um 
outro exemplo negativo outro exemplo negativo 
forforçça a especializaa a especializaçção ão 
somente do modelo geral somente do modelo geral 
restante. Este novo restante. Este novo 
modelo geral modelo geral éé o mesmo o mesmo 
que o modelo especque o modelo especíífico. fico. 
Isto significa que o Isto significa que o 
conjunto geral e o conjunto geral e o 
conjunto especconjunto especíífico fico 
convergiram, produzindo convergiram, produzindo 
um modelo possum modelo possíível para vel para 
a resposta desejada. a resposta desejada. 
nn Na Figura 7 um exemplo negativo para Na Figura 7 um exemplo negativo para 
[ [ SamSam’’s s cafcaféé--dada--manhã domingo caro]manhã domingo caro]
forforçça uma especializaa uma especializaçção deão de
[ [ SamSam’’s s ? ? ?]? ? ?]
gerando um novo modelo geral gerando um novo modelo geral 
[ [ SamSam’’s s ? ? barato]? ? barato]
que que éé idêntico ao modelo especidêntico ao modelo especíífico. Assim, concluifico. Assim, conclui--se a se a 
aprendizagem.aprendizagem.
nn Comida barata no Comida barata no SamSam’’s s produz a alergia. produz a alergia. 
nn CaracterCaracteríísticas do espasticas do espaçço de versõeso de versões
nn Em resumo, os exemplos positivos e negativos são Em resumo, os exemplos positivos e negativos são 
considerados simetricamente no espaconsiderados simetricamente no espaçço de versões.o de versões.
nn Para responder aos exemplos positivos e negativos usando Para responder aos exemplos positivos e negativos usando 
um espaum espaçço de versões:o de versões:
nn Se o exemplo Se o exemplo éé positivo,positivo,
-- generalize todos os modelos especgeneralize todos os modelos especííficos para representar ficos para representar 
o exemplo positivo, mas assegure o seguinte,o exemplo positivo, mas assegure o seguinte,
-- os novos modelos especos novos modelos especííficos envolvem mudanficos envolvem mudançças as 
mmíínimas,nimas,
-- cada novo modelo especcada novo modelo especíífico fico éé uma especializauma especializaçção ão 
de um modelo geral,de um modelo geral,
-- nenhum novo modelo especnenhum novo modelo especíífico fico éé uma generalizauma generaliza--
ççãoão de um outro modelo especde um outro modelo especíífico. fico. 
-- Corte todos os modelos gerais que falhem na Corte todos os modelos gerais que falhem na represenrepresen--
tataççãoão de um exemplo positivo.de um exemplo positivo.
nn Se o exemplo Se o exemplo éé negativo,negativo,
-- especialize todos os modelos gerais para prevenir uma especialize todos os modelos gerais para prevenir uma 
combinacombinaçção com o exemplo negativo, devendo valer o ão com o exemplo negativo, devendo valer o 
seguinte:seguinte:
-- os novos modelos gerais envolvem mudanos novos modelos gerais envolvem mudançças as mmíí--
nimasnimas,,
-- cada novo modelo geral cada novo modelo geral éé uma generalizauma generalizaçção de ão de 
um determinado modelo especum determinado modelo especíífico,fico,
-- nenhum novo modelo geral nenhum novo modelo geral éé uma especializauma especializaçção ão 
de um outro modelo geral.de um outro modelo geral.
-- Elimine todos os modelos especElimine todos os modelos especííficos que representem ficos que representem 
o exemplo negativo. o exemplo negativo.