Programação em Lógica Indutiva
Jacques Robin
DI-UFPE
O que é ILP (Inductive Logic Programming)?
Aprendizagem
Indutivo

Programação
em Lógica
Indutiva
(IPL)
Programação
em Lógica
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 Dedutiva

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:
tarefa genérica

Dados:
•
•
•
•

Aprende hipótese H (regras) tal que:
•
•
•
•

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)
~ 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 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):
caracterí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ção
Representaçã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 atributos
(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 ou
lógica proposicional
Conhecimento a priori
Exemplos positivos:
name1 = ann
…
name5 = tom
father11 = F
…
father31 = T
…
father54 = T
mother11 = F
…
mother55 = F
female1 = T
…
female5 = F
male1 = F
daughter42 = T
daughter13 = 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 = maria
female6 = T
parent56 = T
| daughter65
Aprender relação abstrata com ILP
Conhecimento a priori
Intencional:
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).
Exemplos
Positivos:
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 ILP
Conhecimento a priori
Intencional:
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).
Algoritmo genérico de ILP
inicialize fila de hipótese Fh
 repetir

•
•
•
•
•
delete H de Fh
escolha regras de inferências R1, …, Rk em R
induz H1, …, Hn aplicando R1, …, Rk a H
coloca H1, …, Hn em Fh
pode Fh

até satisfazer critérioDeParada para Fh

Qualquer algoritmo de ILP:
• é uma instância desse algoritmo
• com definições e implementações particulares para:

inicialize, delete, escolha, pode e critérioDeParada
Semântica monótona

Propriedades:
•
•
•
•

Consistência a priori: B  D- |= F
Necessidade a priori: B | F
Consistência a posteriori: B  D-  H |= F
Completude a posteriori: B  H |= D+
Casos particulares:
• Monótona definida:


Monótona normal com B e H limitado a cláusulas definidas,
ie, c(X,Y) :- p(X), q(Y) mas não T :- p(X), q(Y).
• Monótona baseada em exemplos:


Monótona definida com todos D fatos instanciados
(unit ground clauses)
ie, c(a,b) ou not c(a,b) mas nem c(X,b), nem c(a,b) :- p(a),q(b).
Modelos de Herbrand

M(L) modelo de Herbrand de um programa lógico L sse:
• M(L) = {p(…, c, …) | p  pred(L)  c  const(L)  L |= p(…,c,…)}
= todos os fatos instanciados formados a partir de
predicados e constantes de L e deriváveis a partir de L

Exemplo: L: male(paulo). female(ana). male(joao).
parent(paulo,joao). parent(ana,joao).
father(F,C) :- parent(F,C), male(F).
mother(M,C) :- parent(F,C), female(M).
M(L): male(paulo). female(ana). male(joao).
parent(paulo,joao). parent(ana,joao).
father(paulo,joao). mother(ana,joao).

Thm: L sem not  M(L) mínimo
Semântica não-monótona

Pressupostos:
•
•
•
•

D+  B
D- = L(H) - B via hipótese do mundo fechado
B limitado a cláusulas definidas
M+(B) = modelo de Herbrand mínimo de B
Propriedades:
• Validade: H  M+(B)
• Completude: H |= M+(B)
• Mínima: G  H  G inválido ou incompleto

Mais conservadora do que semântica monótona:
•
•
•
•
B = {ave(piupiu). ave(oliver).}
D+ = {voa(piupiu).}
Com semântica monótona, voa(X) :- ave(X).  H
Com semântica não-monótona, voa(X) :- ave(X).  H
Generalizacã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 ILP
Especialização (refinamento) baseado em -Subsumption
 Relative Least General Generalization (RLGG)
 Resolução inversa em V
 Resolução inversa em W (invenção de predicados)
 Implicação inversa
 Derivação inversa (inverse entailment)

-Generalização (-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
em 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 |= Dtamanho de Hn
Busca top-down em reticulado de
refinamento: exemplo
daughter(D,P).
...
daughter(D,D).
...
daughter(D,P)
:- female(D).
...
daughter(D,P)
:- parent(P,D).
...
daughter(D,P)
:- female(D),
female(D).
daughter(D,P)
:- female(D),
parent(P,D).
daughter(D,P)
:- parent(D,X).
...
daughter(D,P)
:- parent(P,D),
female(D).
Generalizaçã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
BDE = {D1, …, Dn} a priori:
• rlgg(C1,C2) = lgg(C1 :- D1, …, Dn. , C2 :- D1, …, Dn)
Generalização mínima relativa: exemplo
Com BDE = {parent(ann,mary). parent(ann,tom). parent(tom,eve). parent(tom,ian).
female(ann). female(mary). female(eve).}
rlgg(daughter(mary,ann). , daughter(eve,tom).)
= lgg(daughter(mary,ann) :- BDE. , daughter(eve,tom) :- BDE. ).
= 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).
Em GOLEM:
 premissas redundantes podadas usando bias semântico limitando busca a
cláusulas determinadas.
Resolução inversa em V
q :  a1 ,...,a n . p : - a1 ,...,a n , b1 ,...,b n .
 Absorção:
p : -q, b1 ,...,b n .
p :  a1 ,...,a n , q. p : - a1 ,...,a n , b1 ,...,b n .
 Identificacão:
q : - b1 ,...,b n .

Para L1: necessidade de inverter unificação:
• achatar cláusulas introduzindo um novo predicado de aridade n+1
para cada função de aridade n
• ex, member(a,[a,b]) ou member(a,.(a,.(b,nil))) chateado em
• member(U,V) :- a(U), dot(V,U,X), dot(X,Y,Z), b(Y), nil(Z).
• unificação de 2 cláusulas achatadas reduz-se a casamento de
padrão das suas premissas.

Limitação: vocabulário fixo de predicados
Exemplo de resolução inversa em V:
encadeamento de 2 absorções
H2: daughter(D,P) :- parent(P,D), female(D).
 11:{mary/D}
B2: female(mary).
H1: daughter(mary,P) :- parent(P,mary).
B1: parent(ann,mary).
 21:{ann/P}
E1: daughter(mary,ann).
q1 = b21 = parent
q2 = female
p1 = p2 = daughter
a11 = b11 = a21 = T
Resolução inversa em W:
invenção de predicados
p : - a1 ,...,a n , b1 ,...,b n . p :  a1 ,...,a n , c1 ,...,c n .
 Intra-construção:
q : - b1 ,...,b n .
p :  a1 ,...,a n , q.
q : - c1 ,...,c n .

Inter-construção:

Limitações:
p : - a 1 ,..., a n , b 1 ,..., b n . p :  a 1 ,..., a n , c1 ,..., c n .
p : - r, b 1 ,..., b n .
r :  a 1 ,..., a n .
p : - r, c1 ,..., c n .
• 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
Exemplo de invenção de predicado
com intra-construção
q(P,D) :father(P,D).
ancestor(A,D) :ancestor(A,P), q(P,D).
 11 :{F/P}
ancestor(A,D) :ancestor(A,F), father(F,D).
q = parent
p = a1 = ancestor
q(P,D) :mother(P,D).
 21 :{M/P}
ancestor(A,D) :ancestor(A,M), mother(M,D).
b1 = father
c1 = mother
Vié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)

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
declarado 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 declaradas
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 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 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çã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
(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 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

•

•
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
•
•
•

descoberta de regras para jogar
xadrez
Engenharia de software:
•
CAD/CAM:
•
Jogos:
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