Programação em Lógica IndutivaProgramação em Lógica Indutiva

Jacques RobinDI-UFPE

Aprendizagem Indutivo

Programação em Lógica

Programação em Lógica Indutiva (IPL)

O que é ILP (Inductive Logic O que é ILP (Inductive Logic Programming)?Programming)?

ILP x resto da aprendizagem • Descobre conhecimento novo expressado em lógica da 1a

ordem ILP x resto da programação em lógica

• Inverte mecanismos de dedução para implementar indução

Programação em Lógica Indutiva x Programação em Lógica Indutiva x DedutivaDedutiva

PL Dedutiva (Prolog, BD dedutivas):• Fatos positivos declarados Regras |= Fatos positivos deduzidos • Conhecimento prévio em extensão Conhecimento prévio em intenção |= Novo conhecimento comprovado em extensão

PL Indutiva (Progol, BD indutivas):• Fatos positivos declarados Fatos negativos declarados Regras declaradas ?|= Regras induzidas• Conhecimento prévio em extensão Conhecimento prévio em intenção

|= Novo conhecimento hipotético em intenção PL com Restrições (CLP, BD de restrições):

• Restrições instanciadas Restrições abstrata |= Restrições instanciadas (mais numerosas) Restrições abstratas (menos numerosas e menos abstratas)• Conhecimento prévio em extensão Conhecimento prévio em intenção |= Novo conhecimento comprovado em extensão Novo conhecimento comprovado em intenção

Programação em Lógica Indutiva: Programação em Lógica Indutiva: tarefa genéricatarefa genérica

Dados:• exemplos positivos (Xi,f(Xi))• exemplos negativos (Xj, f(Xj))• conhecimento prévio B (regras)• viés de aprendizagem (restrições sobre forma das regras)

Aprende hipótese H (regras) tal que: • ~ Xi,f(Xi), Xi B H |= f(Xi)• ~ Xj,f(Xj), Xj B H |= f(Xj)• H verifica restrições do viés de aprendizagem• ~ definido por limiar de tolerância ao ruído

Linguagem de ILP x Prolog:• com negações no BD e nas conclusões • sem símbolo de função, e.g.:

pessoa(nome(joão),idade(20)).

Viés de aprendizagem em ILPViés de aprendizagem em ILP

Objetivo: reduzir busca no espaço de hipótese Sintática paramétrica sobre cláusulas: limitar

•número de premissas por cláusula,•número de variáveis por cláusula,•profundidade dos termos das cláusulas,•nível dos termos das cláusulas.

Semântica sobre predicados: •tipos dos seus argumentos•instanciação dos seus argumentos

constante #, variável de entrada + ou variável de saída -

•número de vezes que um predicado pode ser satisfeito

Programação em Lógica Indutiva (ILP):Programação em Lógica Indutiva (ILP):característicascaracterísticas

Tarefas: classificação, previsão e controle Ambiente pode ser:

• inacessível, não episódico • contínuo, ruidoso• dinâmico?, grande?• relacional, diverso

Supervisionado: E+E- ou E+

Treino antes da ação

Incremental ou não Não iterativo Top-down ou bottom-up ou

bidirecional Guloso Global Aproveita conhecimento

prévio para podar busca da hipótese

Aproxima qualquer funçãoRepresentação do conhecimento: •exemplos, conhecimento prévio e conhecimento aprendido •uniformemente representados por conjunto de conjunto de cláusulas de Horn, •i.e., regras da lógica 1a ordem da forma c(...,X,Y,Z, ...) :- p1(...,X,Y,...),...,pn(...,Y,Z,...).

com semântica ...X,Y,Z,... c(...,X,Y,Z, ...) p1(...,X,Y,...) ... pn(...,Y,Z,...)

ILP x métodos baseados em atributosILP x métodos baseados em atributos(ID3, Redes Neurais, Redes Bayesianas) (ID3, Redes Neurais, Redes Bayesianas)

Vantagens: Aprende conhecimento relacional em lógica da 1a ordem Aprende conhecimento diretamente executável

(programa Prolog) Re-aproveita conhecimento prévio no mesmo formalismo Capaz de inventar novos predicados (i.e., conceitos)Limitações: Dificilmente aprende conhecimento interessante a partir

apenas de exemplos Métodos suficientemente eficientes para grandes BD:

• requer viés muito restringidor sobre regras a aprender• não tem capacidade a inventar novos predicados

Aprender relação abstrata com atributos Aprender relação abstrata com atributos ou lógica proposicionalou lógica proposicional

Conhecimento a priori

name1 = ann…name5 = tomfather11 = F…father31 = T…father54 = Tmother11 = F…mother55 = Ffemale1 = T…female5 = Fmale1 = F

Exemplos positivos:daughter42 = Tdaughter13 = T

Exemplo negativos:daughter11 = F…daughter44 = F

Aprende:daughter(D,P) :- female(D),

parent(P,D), D = {1,2,3,4,5}, P = {1,2,3,4,5}.

Limitação: name6 = mariafemale6 = Tparent56 = T| daughter65

Aprender relação abstrata com ILPAprender relação abstrata com ILP

Conhecimento a prioriIntencional:parent(F,C) :- father(F,C). parent(M,C) :- mother(P,C).Extensional:father(pat,ann).father(tom,sue).female(ann).female(eve).female(sue).male(pat).male(tom).mother(eve,sue).mother(ann,tom).

ExemplosPositivos:daughter(sue,eve).daughter(ann,pat).Negativos:not daughter(tom,ann).not daughter(eve,ann).

Aprende:daughter(D,P) :- female(D), parent(P,D).

Aprender definição recursiva com ILPAprender definição recursiva com ILP

Conhecimento a prioriIntencional:parent(F,C) :- father(F,C). parent(M,C) :- mother(M,C).Extensional:father(pat,ann).father(tom,sue).female(ann).female(eve).female(sue).male(pat).male(tom).mother(eve,sue).mother(ann,tom).

Exemplos positivos:ancestor(tom,sue).ancestor(eve,sue)....Exemplo negativos:not ancestor(ann,eve).not ancestor(sue,eve)....Definição induzida:ancestor(A,D) :- parent(A,D).ancestor(A,D) :- parent(A,P), ancestor(P,D).

Semântica monótona e não-monótonaSemântica monótona e não-monótona Com:

• B = Base de conhecimento prévio• H = base de conhecimento Hipotético aprendido• D+ = base de Dados (exemplos) positivos• D- = base de Dados (exemplos) negativos

ILP monótona: • B H D+ completude (B H D-) consistência

ILP não monótona:• B H D+ completude (B H D-) consistência

Generalizacão x EspecializaçãoGeneralizacão x Especialização

Generalização (busca bottom-up)

parte da hipótese a mais específica: um exemplo +

iterativamente a generaliza aplicando regras de indução até a 1a que cobre:

• todos os exemplos positivos - taxa de erro

• nenhum exemplo negativos - taxa de erro

Especialização (busca top-down)

parte da hipótese a mais geral:

c(…,X,…) :-. iterativamente a especializa aplicando regras de dedução até a 1a que cobre:

• todos os exemplos positivos - taxa de erro

• nenhum exemplo negativos - taxa de erro

Regras e operadores para ILPRegras e operadores para ILP

Especialização (refinamento) baseado em -Generalização

Generalização Mínima Relativa (RLGG Relative Least General Generalization)

Resolução inversa em V Resolução inversa em W (invenção de predicados) Implicação inversa Derivação inversa (inverse entailment)

-Generalização -Generalização ((-Subsumption)-Subsumption)

G -generaliza S sse substituição , (G) S ie, G se unifica com uma parte de S ex, com = {D/ann}, daughter(D,P) :- female(D). -generaliza daughter(ann,P) :- female(ann),

parent(P,ann). Sugere 2 operadores de especializações:

• aplicar substituição e acrescentar premissa (G -generaliza S) (G |= S) -- “G entails S” mas (G |= S) (G -generaliza S) contrex,

• G: humano(paiDe(H)) :- humano(H).• S: humano(paide(paiDe(H))) :- humano(H).• G |= S, porém G não -generaliza S

Busca top-down Busca top-down em reticulado de refinamentoem reticulado de refinamento

Adaptação de ID3 para representação da 1a ordem Espaço de hipótese:

• reticulado no qual cada no -generaliza seus filhos• em cima: conclusão a aprender sem premissa• em baixo: contradição ou hipótese mais específica Hms tal que:

Hms B |= D+ (e Hms B | D-)

Percorre reticulado de cima para baixo em largura 1a Cada passo implementa uma abordagem gerar & testar

• gerar: todas as hipóteses Hn em L(H) refinando a hipótese atual

• testar: função heurística de: número de D+ tal que: Hn B |= D+ número de D- tal que: Hn B |= D- tamanho de Hn

Busca top-down em reticulado de Busca top-down em reticulado de refinamento: exemplorefinamento: exemplo

daughter(D,P).

daughter(D,D). daughter(D,P) :- parent(P,D).

daughter(D,P) :- parent(D,X).

daughter(D,P):- female(D).

daughter(D,P):- female(D), female(D).

daughter(D,P):- female(D),

parent(P,D).

... ... ...

daughter(D,P):- parent(P,D),

female(D).

... ...

Generalização mínima relativaGeneralização mínima relativa

Generalização mínima de 2 termos T e L (literais):• substituição dos sub-termos que não se casam com variáveis• ex, lgg(daughter(mary,ann),daughter(eve,tom)) =

daughther(D,P)• unificação inversa

Generalização mínima de 2 cláusulas:• lgg(C1 :- P1, …, Q1. , C2 :- P2, …, Q2) = lgg(C1,C2) :- lgg(P1,P2), …, lgg(Q1,Q2).• ex, lgg(daughter(mary,ann) :-

female(mary),parent(ann,mary). , daughter(eve,tom) :- female(eve),parent(tom,eve).) = = daughter(D,P) :- female(D), parent(P,D).

Generalização mínima de 2 termos C1 e C2 relativa a base de conhecimento prévio BCP = {D1, …, Dn}:

• rlgg(C1,C2) = lgg(C1 :- D1, …, Dn. , C2 :- D1, …, Dn)

Busca bottom-up com Busca bottom-up com generalização mínima relativa: exemplogeneralização mínima relativa: exemplo

Com BCP = {parent(ann,mary). parent(ann,tom). parent(tom,eve). parent(tom,ian). female(ann). female(mary). female(eve).}

e BDE+ = {daughter(mary,ann). , daughter(eve,tom)}.

rlgg(daughter(mary,ann). , daughter(eve,tom).)

= lgg(daughter(mary,ann) :- BCP. , daughter(eve,tom) :- BCP. ).

= lgg(daughter(mary,ann), daughter(eve,tom)) :- lgg(parent(ann,mary), parent(ann,mary)), lgg(parent(ann,mary), parent(ann,tom), lgg(parent(ann,mary), parent(tom,eve), ... lgg(female(mary), female(eve)), lgg(female(eve), female(eve)).= daughter(D,P) :- BDE, parent(ann,D0), parent(P,D), parent(P1,D1), parent(P2,D2), parent(P3,D3), parent(P4,D4), female(D1), female(D2), female(D).= daughther(D,P) :- parent(P,D),female(D).

Resolução inversa em VResolução inversa em V

Absorção:

Identificacão:

Limitação: vocabulário fixo de predicados

.b,...,b -q,:p

.b,...,b ,a,...,a -: p .a,...,a :q

n1

n1n1n1

.b,...,b -:q

.b,...,b ,a,...,a -: p q.,a,...,a :p

n1

n1n1n1

Exemplo de resolução inversa em V:Exemplo de resolução inversa em V:encadeamento de 2 absorções encadeamento de 2 absorções

E1: daughter(mary,ann).

B1: parent(ann,mary).

B2: female(mary).

H1: daughter(mary,P) :- parent(P,mary).

H2: daughter(D,P) :- parent(P,D), female(D).

:{ann/P}

:{mary/D}

q1 = b21 = parentq2 = femalep1 = p2 = daughtera11 = b11 = a21 = T

11

12

Resolução inversa em W:Resolução inversa em W:invenção de predicadosinvenção de predicados

Intra-construção:

Inter-construção:

Limitações: • incapacidade em inverter derivação envolvendo várias

vezes a mesma cláusula hipotética• complexidade da busca aumenta com conhecimento a

priori• ex, intra-construção: 2 cláusulas 3 cláusulas

.c,...,c -:q q. ,a,...,a :p .b,...,b -:q

.c,...,c ,a,...,a :p .b,...,b ,a,...,a -: p

n1n1n1

n1n1n1n1

.c,...,cr, -:p .a,...,a :r .b,...,br, -:p

.c,...,c ,a,...,a :p .b,...,b ,a,...,a -: p

n1n1n1

n1n1n1n1

Exemplo de invenção de predicado Exemplo de invenção de predicado com intra-construçãocom intra-construção

ancestor(A,D) :- ancestor(A,F), father(F,D).

ancestor(A,D) :- ancestor(A,M), mother(M,D).

ancestor(A,D) :- ancestor(A,P), q(P,D).

q(P,D) :- father(P,D).

q(P,D) :- mother(P,D).

:{F/P} :{M/P}

q = parent b1 = fatherp = a1 = ancestor c1 = mother

11 1

2

Viés sobre L(H): motivaçãoViés sobre L(H): motivação

Se L(H) contem qualquer cláusula de Horn gerável:• por refinamento da cláusula sem premissa• por resolução inversa de 2 elementos de B U D+

Então:• espaço de busca (seja bottom-up ou top-down) • grande demais para ser explorado eficientemente• as vezes até infinito

Viés sobre L(H): • meta-conhecimento heurístico a priori • permitindo limitar espaço de busca

Viés sintático sobre L(H)Viés sintático sobre L(H)

Conhecimento estrutural a priori sobre as hipóteses:• preciso e específico do domínio• ou heurístico e geral

Dimensões:• explícito/implícito• parametrizado/declarativo

Formalismos de declaração explícito de bias sintático:• gramática de cláusulas definidas (DCG -- Definite Clause

Grammar) formalismo built-in da programação em lógica para parsing and

geração de linguagens)

• cláusulas da 2a ordem

Exemplo de viés sintático Exemplo de viés sintático declarado com DCGdeclarado com DCG

head(father(P,C)).head(mother(P,C)).body(father(P,C)) --> m(P),f(P),[parent(P,C)].body(mother(P,C)) --> m(P),f(P),[parent(P,C)].m(M) --> [ ].m(M) --> [male(M)].f(M) --> [ ].f(M) --> [female(M)].

Exemplo de restrições sintáticas Exemplo de restrições sintáticas declaradas com cláusulas da 2a ordemdeclaradas com cláusulas da 2a ordem

Q(P,F) :- R(P,F).Q(P,F) :- S(P).Q(P,F) :- S(P), R(P,F).Q(P,F) :- S1(P), S2(P), R(P,F).

Substituição da 2a ordem = {Q/father,S/male,R/parent} seleciona cláusula: father(P,F) :- male(P),

parent(P,F).

Viés sintático parametrizadoViés sintático parametrizado

lista dos nomes de predicado permitidos em hipóteses

número máximo de premissas por cláusula número máximo de variáveis por cláusula profundidade máxima dos termos das cláusulas nível máximo dos termos das cláusulas:

• variável V é ligada em cláusula C :- P1, …, Pn sse: V C, ou i {1, …, n}, W V: V Pi W Pi W ligada em C :- P1, …,

Pn.

• cláusula ligada sse todas suas variáveis são ligadas ex, p(X) :- q(Z) não ligada, p(X) :- q(X,Y),r(Y,Z),u(Z,W) ligada.

• nível n(t) de um termo t em cláusula ligada C :- P1, …, Pn: 0 se t C, ou 1 + min(n(s)) se t Pi s Pi ex, n(C, grandfather(G) :- male(G), parent(G,F), parent(F,C)) = 2

Viés semântico sobre L(H): tipos e modosViés semântico sobre L(H): tipos e modos

Tipos:const(a). const(b). …clist([]).clist([H|T]) :- const(H), clist(T).

Modos: restrições sobre predicados • na conclusão (modeh) ou premissa (modeb) das regras• número de vezes que um predicado pode ser satisfeito• tipos dos seus argumentos• instanciação dos seus argumentos (constante #, variável de

entrada + ou variável de saída -)• ex: modos para append

:- modeh(1,append(+clist,+clist,-clist))?:- modeh(1,append([+const|+clist],+clist,[-const|-clist]))?:- modeh(1,append(#clist,+clist,-clist))?:- modeb(1,append(+clist,+clist,-clist))?

Viés semântico sobre L(H): determinaçãoViés semântico sobre L(H): determinação

h(…,X0i,...) :- p1(...,X1j,…), …, pn(…,Xnk,…). determinada dados um conhecimento a priori B e exemplos D sse:• as instanciações dos X0j, …, Xij restringem os X(i+1)j a um

único valor, ie, i {1,…,n}, Xij pi, Xkl, k < I, ! v tal que:

Xij/v compatível com Xkl/vkl

Exemplo:• D: parent(jef,paul). parent(jef,ann). male(paul). female(ann).• hasFather(C) :- parent(P,C). determinada: P/jef• isFather(F) :- parent(F,C). não determinada: C/{paul;ann}

Torna aprendizagem eficiente (porém incompleto)

Preferências sintáticas e probabilísticas Preferências sintáticas e probabilísticas

(H) = número de bits na codificação mínima de H Thm:

• H que minimiza (H) em L(H) também maximiza P(H|B E)• ie, a hipótese mais concisa sempre corresponde a mais

verossímil Prova: Thm de Bayes + Thm de Shannon Justificação téorica do navalha de Occam

Aplicações práticas de KDD por ILPAplicações práticas de KDD por ILP

Medicina e saúde: • previsão dos efeitos de uma

nova droga composta a partir dos efeitos dos seus componentes em drogas testadas

• previsão da forma 3D de uma proteína a partir da sua seqüência de ácidos-amidos

• descoberta de regras diagnosticas em reumatologia

CAD/CAM: • descoberta de regras

escolhendo resolução de elementos finitos em modelos numéricos de estresses em estruturas

• derivar regras de diagnostico de falha em satélites a partir de regras causais modelando o funcionamento dos mesmos

Jogos: • descoberta de regras para jogar

xadrez Engenharia de software:

• programação (em lógica) automática

• otimização de código (de programas lógicos)

• teste e depuração de código (de programas lógicos)

• descobertas de restrições de integridade implícitas em BD

Processamento de linguagem natural:• aprendizagem de regras de

gramáticas de uma língua natural a partir de grande corpus de textos