Programação em Lógica Indutiva
Jacques Robin
CIn-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
Dimensões de aprendizagem

Metáfora cognitiva (ou paradigma):
• Simbólica, Nebulosa, Estatística, Conexionista, Evolucionista,
Híbrida

Propriedades matemáticas da função a aproximar:
• domínio e contra-domínio {0,1}, R
• dependência: linear, linear por parte, não linear, etc.

Representação da função a aproximar:
• lógica, probabilística, numérica

Propriedades matemáticas do espaço das representações:
• dimensão
• densidade
Dimensões de aprendizagem (cont.)

Conhecimento:
• a priori: aproveitável, necessário
• aprendido: novidade, interpretabilidade

Algoritmo de aprendizagem:
• iterativo ou não
• local ou global

Feedback disponível:
• supervisionado, não supervisionado, por reforço
• nível de ruído (grau de aproximação)
Aprendizagem: feedback disponível

Aprendizagem supervisionada: certo ou errado
• Dado um conjunto de exemplos pré-classificados, aprender uma
descrição geral que encapsula a informação contida nesses
exemplos e que pode ser usada para prever casos futuros
• ex. concessão de crédito

Aprendizagem não supervisionada: se vira!
• Dada uma coleção de dados não classificados, agrupá-los por
regularidades
• ex. caixa de supermercado empacotando

Aprendizagem por reforço: recompensa/punição
• ex. jogo de xadrez, RoboCup: é por aí!
Dedução x Indução

Dedução: D(A,R) = T
• a partir de


uma base de axiomas A conhecida a priori
uma base de regras de inferência R conhecida a priori
• deduzir: a base de teoremas T, tal que: A  R |= T

Indução: I(A,T,R) = H
• a partir de:



base de axiomas A conhecida a priori
base de teoremas T+ e não teoremas T- observada empiricamente
uma base de regras de inferência R conhecida a priori
• induzir:



base de regras de inferência hipotéticas H,
tal que: A  R  H |= T+ e A  R  H | T-
ILP : indução com A, R, H e T representadas em Lógica
de Horn da 1a ordem.
ILP ao longo das dimensões de aprendizagem




Metáfora cognitiva: simbólica
Função a aproximar: booleana
Representação da função a
aproximar: fórmula da lógica de
Horn da 1a ordem
Algoritmo de aprendizagem:
• iterativo ou não
• local ou global

Feedback:
• supervisionado
• ruído: com ou sem

Conhecimento a priori:
• aproveitável
• necessário quando poucos
exemplos

Conhecimento aprendido:
• altamente interpretável
• alguns métodos de ILP criam
novos predicados
ILP x outras abordagem de aprendizagem

Vantagens x outros métodos de aprendizagem (ID3,
version-space, redes neurais, redes bayesianas, etc.):
•
•
•
•

indução de relações abstratas e definições recursivas
na forma de um programa diretamente executável
aproveitamento do conhecimento a priori do domínio
poucos exemplos necessários (i.e., A e T podem ser pequenas)
Desvantagens x outros métodos de aprendizagem:
• alto custo computacional do treinamento
• dificuldade em formar hipóteses interessantes na ausência de
conhecimento a priori
Aprender relação abstrata com ILP:
daughter(D,P) = f(father,female,male,mother).
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:
 daughter(sue,eve).
 daughter(ann,pat).
 Negativos:
 not daughter(tom,ann).
 not daughter(eve,ann).
Objetivo:
 Induzir:
 daughter(D,P) :female(D), parent(P,D).
Aprender definição recursiva com ILP:
ancestor = f(parent, ancestor).
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:
ancestor(tom,sue).
ancestor(eve,sue).
...
 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).
Dimensões de ILP

Tarefa:
•
•
•
•
•
•

Grau de automação: interativo x autónomo
Incremental (na apresentação dos dados): sim/não
Semântica: monótona normal, monótona definita, não-monótona
Descoberta de predicados: com/se
Entrada: T+, T+  T-, T+  A  R, T+  T-  A  R
Saída: um x vários predicados, LP x CLP
Abordagem:
• Operadores: -subsumption, rlgg, resolução ou implicação inversa
• Restrições da linguagem de hipótese L(H) (language bias):
 sintáticas x semânticas
 parametrizadas x declarativas
• Estratégia de busca:
 Global: especialização (top-down) x generalização (bottom-up)
 Local (preference bias):
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
Generalizacão x Especialização
Generalização (busca bottom-up)
 parte da hipótese a mais
específica: qualquer exemplo
positivo
 iterativamente generaliza-lá
 aplicando regras de indução
 até a 1a que cobre:
• quase todos os exemplos
positivos
• quase nenhum exemplo
negativo
Especialização (busca top-down)
 parte da hipótese a mais geral:
c(…,X,…) :-.
 iterativamente especializa-lá
 aplicando regras de dedução
 até a 1a que cobre:
• quase todos os exemplos
positivos
• quase nenhum exemplo
negativo
Para os 2:
• “quase” definido quantitativamente via uma taxa de erro
• necessária para:
• evitar overfitting da amostra de treinamento
• garantir o poder de generalização da hipótese
Semântica monótona

Propriedades:
•
•
•
•

Consistência a priori: A  R  T- |= {f}
Necessidade a priori: A  R | {f}
Consistência a posteriori: A  R  T-  H |= {f}
Completude a posteriori: A  R  H |= T+
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 T+ e T- 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:
•
•
•
•

T+  A  R
T- = L(H) - A  R via hipótese do mundo fechado
A  R limitado a cláusulas definidas
M+(A  R) = modelo de Herbrand mínimo de A  R
Propriedades:
• Validade: H  M+(A  R )
• Completude: H |= M+(A  R)
• Minimal: G  H  G inválido ou incompleto

Mais conservadora do que semântica monótona:
•
•
•
•
A  R = {bird(tweety). bird(oliver).}
T+ = {flies(tweety).}
Com semântica monótona, flies(X) :- bird(X).  H
Com semântica não-monótona, flies(X) :- bird(X).  H
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
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.
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  A  R |= T+ (e Hms  A  R |T-)
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  A  R |= T+
número de D- tal que: Hn  A  R |= Ttamanho 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).
Derivação inversa

Como:
•
A  R  H |= T
 A  R   T |=  H
 A  R   T |= M(A  R   T) |=  H
 H |= M(A  R   T)
• G -generaliza S  G |= S

Então, H pode ser computado em 2 passos:
• 1: Deduz M(A  R   T) a partir de A  R e de T
• 2: Calcula H = {h  L(H) | h -generaliza M(A  R   T)}
Restrições de 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 A  R  T+

Então:

• espaço de busca (seja bottom-up ou top-down)
• grande demais para ser explorado eficientemente
• as vezes até infinito
Restrição de L(H):
• meta-conhecimento heurístico a priori
• permitindo limitar espaço de busca
Restrições sintáticas parametrizadas
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
Restrições semânticas de 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))?
Restrições semânticas de 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

PROGOL: nas dimensões de ILP

Tarefa:
•
•
•
•
•
•

Grau de automação: interativo ou autônomo
Incremental (na apresentação dos dados): sim ou não
Semântica: não-monótona
Descoberta de predicados: ?
Entrada: D+ ou D+^D- ou D+^B ou D+^D-^B
Saída: um ou vários predicados, LP
Abordagem:
• Operadores: derivação inversa, -generalização
• Restrições da linguagem de hipótese L(H) (language bias):
 sintáticas e semânticas
 parametrizadas e declarativas
• Estratégia de busca:
 Global: top-down, mais bottom-up bounded
 Local: poda espaço usando função heurística f(H) estimando
poderDePredição(H) x concisão(H)
PROGOL: algoritmo
Instância do algoritmo genérico de ILP com:
 inicialize: H = {obj(…,X,…) :- }.
 delete: dE, B  H |= E
 escolha: H que maximiza f(H), função heurística de
busca aproximando (poderDePredição(H),concisão(H))
 pode:

• hipóteses mais específicas que M(B   D)
• hipóteses que não pode mais melhorar f(H)

critérioDeParada:
• |falsos+| + |falsos-| < limiar de ruído, ou
• E=
PROGOL: função heurística de busca

f(H) = (P(p-n-c-h+1))/p, com:
•
•
•
•
•
P
p
n
c
h
=
=
=
=
=
|E+|
|E+ deduzidos de H| (verdadeiros +)
|E- deduzidos de H| (falsos -)
|H| (em número de literais)
|variáveis de saída não restritas|
PROGOL: construir hipótese + específica
% Restrições semânticas de L(H)
:- set(r, 10000) % max Prolog unif
:- set(h, 100)
% max Prolog search depth
:- modeh(1,implies5(+bool5, +bool5, -bool5).
:- modeb(1,or5(+bool5, +bool5, -bool5).
:- modeb(1,not5(+bool5, -bool5).
bool5(X) :- integer(X), X => 0, X <= 4.
% B: conhecimento a priori
not5(I,Out) :- Out is 4 - I.
or5(X,X,X).
or5(I,J,Out) :- I > J, Out is I.
or5(I,J,Out) :- I < J, Out is J.
% E+: exemplos positivos
implies5(4,4,4).
implies5(4,0,0).
implies5(0,4,4).
implies5(1,2,3)
% E-: exemplos negativos
:- implies5(2,0,0).
:- implies5(4,2,4).
1/ d= implies5(4,4,4)  mode declar
 or5(4,4,4)  M(B   d)  not5(4,0)  M(B   d)
 or5(4,0,4)  M(B   d)  or5(0,4,4)  M(B   d)
 or5(0,0,0)  M(B   d)  not5(4,0)  M(B   d)
 M(B   d) = or5(4,4,4)  not5(4,0)  or5(4,0,4) 
or5(0,4,4)  or5(0,0,0)  not5(4,0) 
 implies5(4,4,4).
 maxspec{h | h  H |= e} = or5(A,A,A)  not5(A,B)
 or5(A,B,A)  or5(B,A,A)  or5(B,B, B)
 not5(B,A)  implies5(A,A,A).
CProgol Version 4.4
|- consult(implies5a)?
[No contradictions found]
yes
|- generalise(implies5/3)?
[Generalising implies5(4,4,4).]
[Most specific clause is]
implies5(A,A,A) :- or5(A,A,A), not5(A,B),
or5(A,B,A), or5(B,A,A), or5(B,B,B), not5(B,A).
PROGOL: Generalizar hipótese + especifica 1
% Restrições semânticas de L(H)
:- set(r, 10000) % max Prolog unif
:- set(h, 100)
% max Prolog search depth
:- modeh(1,implies5(+bool5, +bool5, -bool5).
:- modeh(1,or5(+bool5, +bool5, -bool5).
:- modeh(1,not5(+bool5, -bool5).
bool5(X) :- integer(X), X => 0, X <= 4.
% B: conhecimento a priori
not5(I,Out) :- Out is 4 - I.
or5(X,X,X).
or5(I,J,Out) :- I > J, Out is I.
or5(I,J,Out) :- I < J, Out is J.
% E+: exemplos positivos
implies5(4,4,4).
implies5(4,0,0).
implies5(0,4,4).
implies5(1,2,3)
% E-: exemplos negativos
:- implies5(2,0,0).
:- implies5(4,2,4).
% Generalising implies5(A,A,A).
[C:0,1,0,0 implies5(A,A,A).]
[C:-5,1,1,0 implies5(A,B,A).]
% pruned
[C:2,3,1,0 implies5(A,B,B).] % 1st tried
[C:0,2,0,1 implies5(A,A,B).]
% pruned
[C:1,5,2,1 implies5(A,B,C).]
% 2nd
% Specialising implies5(A,B,B)
[C:0,3,1,0 implies5(A,B,B) :- or5(B,B,B).]
[C:0,3,1,0 implies5(A,B,B) :- or5(B,B,C).]
[C:0,2,0,0 implies5(A,B,B) :- or5(A,B,B).]
[C:-2,2,1,0 implies5(A,B,B) :- or5(A,B,A).]
[C:0,3,1,0 implies5(A,B,B) :- or5(A,B,C).]
[C:0,2,0,0 implies5(A,B,B) :- or5(B,A,B).]
[C:-2,2,1,0 implies5(A,B,B) :- or5(B,A,A).]
[C:0,3,1,0 implies5(A,B,B) :- or5(B,A,C).]
[C:0,3,1,0 implies5(A,B,B) :- or5(A,A,A).]
[C:0,3,1,0 implies5(A,B,B) :- or5(A,A,C).]
[C:0,3,1,0 implies5(A,B,B) :- not5(B,C).]
[C:0,3,1,0 implies5(A,B,B) :- not5(A,C).]
[C:-2,3,1,0 implies5(A,B,B) :- not5(B,C), or5(B,C,D).]
...
[C:-2,3,1,0 implies5(A,B,B) :- or5(A,A,C), not5(C,D).]
PROGOL: Generalizar hipótese + especifica 2
% Restrições semânticas de L(H)
:- set(r, 10000) % max Prolog unif
:- set(h, 100)
% max Prolog search depth
:- modeh(1,implies5(+bool5, +bool5, -bool5).
:- modeh(1,or5(+bool5, +bool5, -bool5).
:- modeh(1,not5(+bool5, -bool5).
bool5(X) :- integer(X), X => 0, X <= 4.
% B: conhecimento a priori
not5(I,Out) :- Out is 4 - I.
or5(X,X,X).
or5(I,J,Out) :- I > J, Out is I.
or5(I,J,Out) :- I < J, Out is J.
% E+: exemplos positivos
implies5(4,4,4).
implies5(4,0,0).
implies5(0,4,4).
implies5(1,2,3)
% E-: exemplos negativos
:- implies5(2,0,0).
:- implies5(4,2,4).
% Specialising implies5(A,B,C)
[C:0,5,2,1 implies5(A,B,C) :- or5(A,A,A).]
...
[C:0,5,2,1 implies5(A,B,C) :- or5(B,B,D).]
[C:-2,3,1,0 implies5(A,B,C) :- or5(B,B,C), not5(C,D).]
...
[C:0,4,0,1 implies5(A,B,C) :- or5(A,B,B), not5(B,D).]
[C:0,5,2,1 implies5(A,B,C) :- not5(A,D).]
[C:0,5,2,1 implies5(A,B,C) :- not5(B,D).]
[C:0,4,0,0 implies5(A,B,C) :or5(B,A,B), not5(A,D), or5(A,D,C).]
...
[C:-1,4,0,1 implies5(A,B,C) :or5(A,B,B), not5(B,D), not5(D,E).]
[C:0,4,1,0 implies5(A,B,C) :- not5(A,D), or5(A,D,C).]
[C:-1,5,2,1 implies5(A,B,C) :- not5(A,D), or5(A,D,E).]
[C:2,5,0,0 implies5(A,B,C) :not5(A,D), or5(B,D,C).] % BINGO!
[C:-3,3,1,1 implies5(A,B,C) :- not5(A,D), or5(B,D,B).]
[C:-1,5,2,1 implies5(A,B,C) :- not5(A,D), or5(B,D,E).]
[122 explored search nodes, f=2,p=5,n=0,h=0]
[5 redundant clauses retracted]
PROGOL: exemplo com ruído