Page 1

Metodologias de Inteligência Artificial2005/2006

Introdução à Aprendizagem Simbólica Automática

2MIA - 2005/06

Aprendizagem Simbólica Automática• Aprendizagem Simbólica Automática

– "aprender implica mudanças adaptativas do sistema no sentido de lhe permitir realizar a(s) mesma(s) tarefa(s) nas mesmas circunstâncias de um modo mais eficiente e efectivo da próxima vez“ (Herbert A. Simon)

• Aprendizagem humana:

– aquisição de conhecimento (Knowledge acquisition)consiste na aquisição estruturada de nova informação simbólica assim como da capacidade de a aplicar a situações novas.

– ex: aprender Matemática.

– refinamento de habilidade (skill refinement)processo, eminentemente não simbólico, caracterizado por refinar um procedimento através de tentativas sucessivas até atingir uma proximidade desejada com o objectivo.

– ex: aprender a andar de bicicleta ou tocar violino.

Page 2

3MIA - 2005/06

Aprendizagem Simbólica Automática• Taxonomia dos métodos de Aprendizagem Simbólica

– classificação quanto à estratégia, à representação e ao domínio.

1. Classificação quanto à estratégia usada– rote learning

Consiste na implantação directa de novo conhecimento• aprender por ser programado (by being programmed)• aprender por memorização de novos factos ou dados. Caso das bases de dados primitivas.

Aliás o nome “rote learning” deriva precisamente daí.

– aprendizagem por conselho ou por instrução (by being told or by instruction)O conselho é fornecido pelo agente exterior numa forma ou linguagem não directamente utilizável pelo sistema. Uma transformação de representação e/ou alguma inferência deve ser feita pelo sistema de aprendizagem por forma a operacionalizar o novo conhecimento e compatibilizá-lo com o pré-existente.

4MIA - 2005/06

Aprendizagem Simbólica Automática– aprendizagem por analogia

Consiste na aquisição de novos conceitos ou factos ou planos por transformação ou ampliação de conceitos já adquiridos pelo sistema.

– Ex: CBR (“Case Base Reasoning”), Generalização de Planos em robótica

– aprendizagem por exemplosDado um conjunto de exemplos e contra-exemplos, o sistema de aprendizagem deve induzir um conceito geral que verifique todos os exemplos (ou exemplos positivos) e não contemple nenhum dos contra-exemplos (ou exemplos negativos).

– aprendizagem por observação ou descoberta (não supervisionada)É um método bastante geral de aprendizagem indutiva que inclui os chamados sistemas de descoberta, tarefas de formação de teorias, criação de critérios de classificação para formação de hierarquias taxonómicas (conceptual clustering) sem a intervenção ou auxílio de um agente exterior.

Page 3

5MIA - 2005/06

Aprendizagem Simbólica Automática2. Classificação quanto à representação do conhecimento adquirido

– Parâmetros em expressões algébricasElementos lógicos de limiar (threshold logic elements). Funções que modelam o desempenho do sistema e cujos coeficientes são ajustados.

– Árvores de decisão

– Gramáticas formaisSão tipicamente representadas por expressões regulares, autómatos finitos, regras de uma gramática independente do contexto ou regras de tranformação.

– Regras de produção

– Expressões baseadas em lógica formal e formalismos semelhantes• Lógica de Predicados de Primeira Ordem.• Cálculo de predicados anotado desenvolvido por Michalski.

– Grafos e redes

6MIA - 2005/06

Métodos Baseados em ExplicaçõesAprendizagem Dedutiva/Indutiva por Métodos Baseados em Explicações

Estratégia de "aprendizagem por exemplos": Como identificar uma definição correcta de um conceito a partir de exemplos positivos, tais que o conceito seja uma especialização de um conceito-genérico (target) definido pela "Teoria do Domínio".

3 métodos (para a Especialização de Conceitos baseados na Teoria): • Generalização Baseada nas Explicações (EBG)• EBG de exemplos múltiplos (mEBG)• um novo método: Indução Sobre as Explicações (IOE)

Os dois primeiros têm desvantagens: • raramente identificam a definição correcta• o sucesso depende grandemente da codificação das regras da teoria do domínio.

Page 4

7MIA - 2005/06

Generalização Baseada nas Explicações (EBG)EBG (Explanation Based Generalization)

O Resolvedor de Problemas começa com uma teoria correcta do domínio que define o conceito-genérico (target-concept). A teoria, embora correcta pode ser ineficiente.

• exemplos treino E• aplicar a teoria do domínio para provar que E é uma instância do conceito-genérico. • Extrair as pré-condições mais fracas (WP) da prova para formar uma regra eficiente• O conceito-genérico é convertido numa "forma operacional".

É claro que se pode aprender neste caso mais conhecimento se as WP forem condição necessária e suficiente para a definição de um conceito C mais específico.

WP(E) = C (E)

8MIA - 2005/06

Generalização Baseada nas Explicações (EBG)Exemplo:– Sistema de Pazzani (OCCAM) onde a teoria do domínio define o conceito genérico

"coerção" (fazer executar um objectivo pela ameaça). Ao aplicar "um país ameaça não vender petróleo" e ao achar a pré-condição mais fraca deriva o conceito de sanção económica que é aprendido.

Como explorar o domínio do conhecimento para guiar uma aprendizagem indutiva?Dados:– Uma teoria do Domínio que define um conceito genérico (CG) .– Um conjunto de exemplos positivos de treino envolvendo um conceito C que é uma

especialização de CGEncontrar:– Uma definição correcta de C

Page 5

9MIA - 2005/06

Generalização Baseada nas Explicações (EBG)Método EBG

1. Construir a árvore de explicação que prova que um (único) exemplo é uma instância do conceito genérico.

2. Constriur as Pré-condições mais fracas (WP) tais que uma explicação é ainda verdadeira. Para árvores simples, WP é a conjunção dos literais das folhas .

Mas os Termos argumento devem ser o mais gerais possíveis, i.e., independentes do exemplo (eis a generalização).

10MIA - 2005/06

Generalização Baseada nas Explicações (EBG)Vamos considerar os três métodos referidos para o problema da especialização de conceitos baseados na teoria do domínio (TD), o conceito genérico (CG) e o(s) exemplo(s) de treino E.

• Teoria do Domínio que define o objecto genérico chávena

regra Cchavena(Obj) :- conter_liquido(Obj), estavel(Obj), eleva(Obj), acessivel(Obj).

regra CLconter_liquido(Obj) :- superficie(Obj,S), feito_de(S,Ms), nao_poroso(MS),

fundo(Obj,F), feito_de(F,Mf), nao_poroso(Mf).nao_poroso(plastico). nao_poroso(porcelana). nao_poroso (aluminio).

regra Esestavel(Obj) :- fundo(Obj, F), plano(F).

regra Eleleva(Obj): - leve(Obj), apanhavel(Obj).

Page 6

11MIA - 2005/06

Generalização Baseada nas Explicações (EBG)

regra Acacessivel(Obj):- tem(Obj,Parte), concavidade(Parte), para_cima(Parte).

regra Lvleve(Obj) :- pequeno(Obj), superficie(Obj,S), feito_de(S,Ms), material_leve(Ms),

fundo(Obj,F), feito_de(F,Mf), material_leve(Mf).material_leve(plastico). material_leve(porcelana). material_leve(aluminio).

regra Ap1apanhavel(Obj) :- pequeno(Obj), superficie(Obj,S), cilindrico(S), feita_de(S,M),

isolante_termico(M).

regra Ap2apanhavel(Obj) :- pequeno(Obj), tem(Obj, P), asa(P).isolante_termico(plastico). isolante_termico(porcelana).

12MIA - 2005/06

c1 c2 c3

Generalização Baseada nas Explicações (EBG)

asa(p31)

tem(c3,p31)

pequeno(c3)

para_cima(p3)

concavidade(p3)

tem(c3,p3)

plano(f3)

feito_de(f3,porcelana)

fundo(s3,f3)

feito_de(s3,porcelana)

superficie(c3,s3)

asa(p21)

tem(c2,p21)cilindrico(c1)

pequeno(c2)pequeno(c1)

para_cima(p2)para_cima(p1)

concavidade(p2)concavidade(p1)

tem(c2,p2)tem(c1,p1)

plano(f2)plano(f1)

feito_de(f2,aluminio)feito_de(f1,plastico)

fundo(c2,f2)fundo(c1,f1)

feito_de(s2,plastico)feito_de(s1,plastico)

superficie(c2,s2)superficie(c1,s1)

Page 7

13MIA - 2005/06

Generalização Baseada nas Explicações (EBG)As árvores de explicação construídas para provar cada exemplo a partir da teoriado Domínio são:

C

CL Es El Ac

Factos FactosLv Ap

Ap1

C

CL Es El Ac

Lv Ap

Ap2

C

CL Es El Ac

Lv Ap

Ap2

Factos

14MIA - 2005/06

Generalização Baseada nas Explicações (EBG)Método EBG

1. Construir a árvore de explicação que prova que um (único) exemplo é uma instância do conceito genérico.

2. Construir as Pré-condições mais fracas (WP) tais que uma explicação é aindaverdadeira. Para árvores simples, WP é a conjunção dos literais das folhas. Mas os Termos argumento devem ser o mais gerais possíveis, i.e., independentes do exemplo (eis a generalização).

– Para a chávena 1 as WP são:superficie(O,S), feito_de(S, Ms), nao_poroso(Ms), fundo(O,F), feito_de(F,Mf), nao_poroso(Mf), plano(F), pequeno(O), material_leve(Ms), material_leve(F), cilindrico(S), isolante_termico(Ms), tem(O,P), concavidade(P), para_cima(P).

– Estas WP formam o novo conceito Ca que é uma especialização do conceito chávena. (Superfície cilindrica feita de material leve e isolante térmico).

Page 8

15MIA - 2005/06

Generalização Baseada nas Explicações (EBG)

Se em vez de chávena 1 construíssemos a árvore de explicação para chávena 2, um novo conceito Cb seria criado para chávenas com asa removendo a restrição do material isolante_termico.

Logo, o número de conceitos derivados é igual ao número de árvores de explicação completas diferentes que se podem derivar. (no caso visto, só 2).

16MIA - 2005/06

EBG por múltiplos exemplos (mEBG)Generalização Baseada nas Explicações por múltiplos exemplos: mEBG

O Algoritmo é o seguinte:

1. Para cada exemplo construir a árvore de explicação provando que o exemplo é uma instância do conceito geral (CG).

2. Comparar as árvores de explicação para encontrar a maior sub-árvore partilhada por todos os exemplos.

3. Aplicar as técnicas de generalização do EBG a esta sub-árvore e extrair a WP tal que a árvore permaneça uma prova válida.

Page 9

17MIA - 2005/06

EBG por múltiplos exemplos (mEBG)– Se tivessemos usado os exemplos da chávena 1 e 2, a máxima sub-árvore seria:

WP:superficie(O,S), feito_de(S,Ms), nao_poroso(Ms), fundo(O,F), feito_de(F,Mf), nao_poroso(Mf), plano(F), pequeno(O), material_leve(Ms), material_leve(Mf), tem(O,P), concavidade(P), para_cima(P), apanhavel(O).

– As condições específicas de "apanhavel" foram apagadas.

C

CL Es El Ac

Lv Ap

mEBG(C1, C2)

18MIA - 2005/06

Indução Sobre as Explicações (IOE)IOE : Indução Sobre as Explicações

Como em mEBG, também IOE aprende a partir de múltiplos exemplos.A diferença está na estratégia de derivar a máxima sub-árvore comum de explicações.

Consideremos 2 exemplos de treino :1. Aplicar mEBG aos dois exemplos, produzindo a definição de novos conceitos e

retendo as árvores originais.2. Fazer o "matching" do conceito com cada uma das árvores de prova dos exemplos de

treino para produzir uma substituição θi de pares cj=vj.• vj é cada variável em C• cj uma constante ou termo do exemplo ou Teoria do Domínio.

3. Derive θ, uma nova substituição para C da seguinte forma:

Page 10

19MIA - 2005/06

Indução Sobre as Explicações (IOE)

3.1. θ ← ∅

3.2. para cada vj em C faça vj =cj em θ, onde cj é computado como segue:

3.2.1. atente aos valores que substituiram vj em θ1 (c1j), e em θ2 (c2j).

3.2.2. cj ← gen(c1j, c2j), onde gen(c1, c2) é definido por:

SE c1=c2 ENTAO gen (c1, c2) = c1SENAOSE c1 = f(t1,1, t1,2 , ..., t1,k) e c2 = f(t2,1, t2,2 , ..., t2,k)

(i.e. termos com o mesmo functor)

ENTAO gen (c1, c2) = f(gen(t1,1, t1,2 , ..., t1,k), ..., gen(t2,1, t2,2 , ..., t2,k) ).

20MIA - 2005/06

Indução Sobre as Explicações (IOE)

SENAO gen(c1, c2)=V, onde V é selecionado como segue: SE gen(c1, c2) nunca chamadoENTAO

V é uma variável ainda não usada em θ1, θ2 ou θ.guardar gen(c1, c2) = V numa tabela

SENAO (i.e. já houve uma chamada a gen (c1, c2) )consulte a tabela e retire a variável considerada paragen(c1, c2) = V

4. Computar e retornar C com a substituição θ

IOE computa portanto a definição do conceito C tal como mEBG, mas depois especializa-a introduzindo restrições às variáveis usando a substituição θ.

Page 11

21MIA - 2005/06

Indução Sobre as Explicações (IOE)– Primeiro tipo de restrição : Uma constante é introduzida na definição do conceito

quando uma variável V aparecendo na definição C de mEBG fica ligada a uma constante em cada exemplo de treino.

Suponhamos que se aplicava mEBG às chávenas 1 e 2 :Na definição do conceito especializado aparece feito_de(S, Ms) onde Ms é o material da superficie lateral da chávena. c1 e c2 têm superficies laterais de plastico o que implicará que a definição final do conceito exija que a superficie lateral seja de plastico.

– Segundo tipo de restrição: É uma restrição de igualdade forçando 2 ou mais variáveis da definição de C a serem iguais.

Tal acontece quando IOE encontra 2 ou mais variáveis diferentes V1, V2 na definição do conceito mEBG ligadas ao mesmo termo em cada exemplo. Isto é, o termo Ci pode diferir de um exemplo para outro mas em cada um deles V1 e V2 estão ligados a um mesmo Ci.

22MIA - 2005/06

Indução Sobre as Explicações (IOE)Suponhamos que aplicamos IOE aos exemplos c1 e c3. Em c1, quer a superficie quer o fundo são de plastico e em c3 sao ambos de porcelana.

– A definição do conceito C por mEBG leva a :

feito_de(S, Ms) e feito_de(F, Mf).

No primeiro caso (c1), Ms = Mf = plastico

e no segundo caso (c2), Ms = Mf = porcelana.

– Então, IOE encontra uma nova variável M e a definição final do conceito inclui :

feito_de (S, M) e feito_de(F,M).

O novo conceito define chávenas homogéneas

Page 12

23MIA - 2005/06

Variável V

exemplos treino resultados da aprendizagemIOE(C1, C2) IOE(C1, C3)

Ms plástico plástico porcelana plástico M

Mf plástico alumínio porcelana Ma M

C1 C2 C3

Obj c1 c2 c3 O O

S s1 s2 s3 Sup Sup

F f1 f2 f3 Fundo Fundo

Parte p1 p2 p3 P P

Indução Sobre as Explicações (IOE)Consideremos a seguinte tabela onde a 1ª coluna mostra as 6 variáveis que aparecem na definição do conceito C de mEBG.As 2ª, 3ª e 4ª colunas apresentam as substituições θ, para c1, c2 e c3. As duas colunas finais mostram os resultados da aplicação de IOE aos exemplos (c1,c2) e (c1,c3), respectivamente.

24MIA - 2005/06

Indução Sobre as Explicações (IOE)Consideremos a última coluna da tabela mostrando os resultados do algoritmo IOE para c1 e c3. No passo 3 do algoritmo, o procedimento gen é aplicado a cada linha.

– A 1ª chamada computa gen (c1, c3), e como as constantes são diferentes cria uma nova variável, seja:

θ = {Obj = O}

– A 2ª chamada a gen leva a : gen(s1, s3) = Sup θ = {Obj = O, S=Sup}

– A 3ª chamada a gen (gen(plastico, porcelana)) cria uma restrição de igualdade gerando a variável M

θ = {Obj = O, S=Sup, Ms=M}A informação gen(plastico,porcelana)=M é guardada para posterior utilização.

– Quando se chega à 5ª linha, o algoritmo consulta a tabela e verifica que gen já foi chamado com aqueles argumentos, logo dá à variável Mf a mesma substitução, isto é, M.

θ = {Obj=O, S=Sup, Ms=M, F=Fundo, Mf=M}

Page 13

25MIA - 2005/06

Indução Sobre as Explicações (IOE)Este método (chamado das "não-coincidências" ) é simples mas poderoso.

– Ao contrário de outros métodos indutivos, não procura encontrar padrões nos exemplos de treino tal como eles são apresentados originalmente.

– Aplica a Teoria do Domínio e o conceito genérico para identificar características úteis para a generalização indutiva.O espaço das definições de conceitos possíveis de serem construídas por esta técnica ésuperior a mEBG, pois IOE pega em cada um dos conceitos mEBG e gera substituições restringindo a definição pelas igualdades.

No domínio considerado das chávenas, IOE gera 58 diferentes definições de chávenas (incluindo as de asa de plástico e as homogéneas).

– Baseado em :– "A study of Explanation-based methods for inductive learning" - Nicholas Flann;

Thomas Dietterich; Machine Learning, Nov-89