Progol:
uma extensão indutiva de Prolog
Jacques Robin
CIn-UFPE
O que é Progol?
Sistema de programação em lógica indutiva (ILP)
 Embute um interpretador Prolog
 Estende a programação em lógica dedutiva de Prolog com
a programação em lógica indutiva e também abdutiva
 Permite aprendizagem parcial ou total de um programa
Prolog a partir de exemplos positivos e/ou negativos de
predicados do programa a aprender
 Aplicado com êxito para uma grande variedade de
aplicações práticas
 Já fez descoberta científica publicada em revista
especializada
 Implementação em C para Unix disponível de graça

Representação do conhecimento

Exemplos:
• positivos: fatos Prolog instanciados, ex. aunt_of(jane,henry).
• negativos: fatos Prolog instanciados, ex :- aunt_of(henry,sally)
• porque :- antes dos fatos negados?




h :- b.  (b  h)  (b  h)  (F  b  h  F)
 ((F  b))  (h  F))  ((T  b))  (h  F)
 (T  b)  (h  F)  F, h :- b, T
quando b = Ø, h :- Ø  h.  (T  h)  (T  h)  (F  h)  h
quando h = Ø, Ø :- b.  :- b  (b  F)  (b  F)  b
Conhecimento prévio:
• fatos Prolog, ex, father(sam,henry)
• regras Prolog, ex, parent(P,C) :- father(P,C).

Conhecimento aprendido (hipótese):
• regras Prolog, ex, aunt(A,N) :- parent(P,N), sister(A,P).
Representação de viés de aprendizagem

Declarações de modo:
• predefine o vocabulário de
predicados
• que podem aparecer nas
conclusões das regras a
aprender (i.e., predicados cuja
definições Progol está
tentando induzir)
• que podem aparecer nas
premissas das regras a
aprender (i.e., predicados cuja
definições foram fornecidas
para Progol como conhecimento
prévio ou estão sendo
aprendidas)
• impõem restrições de tipo, de
instanciação e de numero de
soluções possíveis para os
argumentos desses predicados
• por default Progol funciona
sem invenção de predicados

Parâmetros definindo:
• número máximo de premissas
nas regras a aprender
• fator de compressão da
aprendizagem: comprimento
relativo dos exemplos
fornecidos e das regras
induzidas a partir deles

Progol permite também:
• Declarar restrições de
integridade entre predicados
• Excluir explicitamente de
padrões sintáticos de regras
Declarações de modo

modeh(Recall,Pred(I1T1 ... InTn))
• inclui Pred no vocabulário das conclusões das regras a aprender

modeb(Recall,Pred(I1T1 ... InTn)).
• inclui Pred no vocabulário das premissas das regras a aprender

Com a restrições seguintes:
numero máximo de soluções para Pred = Recall
i, instanciação de Argi restrita a Ii e tipo de Argi restrito a Ti
tipo = predicado unário tipando constantes dos exemplos
ex, person(jane). na base de conhecimento prévio define tipo de
jane, aparecendo no exemplo aunt_of(jane,henry), como person
• instanciação:
•
•
•
•




+ para argumento de entrada (variável instanciada)
- para argumento de saída (variável não instanciada)
# para argumento constante
ex, modeh(1,aunt(+person,+person)).
Exemplo de entrada
% Base de exemplos dos predicados
% aprender
% 1/ Exemplos positivos
aunt(jane,henry). aunt(sally,jim).
...
% 2/ Exemplos negativos
:- aunt(henry,sally).
:- aunt(judy,sarah).
...
% Base de conhecimento prévio
% 1/ conhecimento em extensão
% 1a: Tipos das constantes
% aparecendo nos exemplos
person(jane). person(henry). ...
% 1b: Fatos relacionais
father(sam,henry). ...
mother(sarah,jim). ...
sister(jane,sam). ...
% 2/ conhecimento em intenção
parent(P,C) :- father(P,C).
parent(P,C) :- mother(P,C).
% Viés de aprendizagem
% 1/ Declarações de modos
:- modeh(1,aunt(+person,+person))?
:- modeb(*,parent(-person,+person))?
:- modeb(*,parent(+person,-person))?
:- modeb(*, sister(+person,-person))?
% 2/ Instanciação dos parâmetros de viés
% Excluir do espaço das hipóteses regras
% com mais de 3 premissas
c(3).
Características de Progol como sistema de
programação em lógica indutiva
Aprendizagem:
 autônomo e não incremental
 com semântica monótona
 de regras definindo um ou
vários predicados
 tanto a partir de exemplos
positivos e negativos quanto
apenas a partir de exemplos
positivos
 tanto a partir de exemplos e
conhecimento prévio quanto
apenas a partir de exemplos
 por default sem invenção de
predicados, porém permite
programar tal invenção
Busca:
 heurística incorporando ambos
concisão e estimativa da
generalidade das hipóteses
 em parte bottom-up usando rlgg
a partir de um exemplo
 em parte top-down usando
-especialização
 de complexidade polinomial
devido às declarações de viés
podando o espaço de hipótese
Fundamentos lógicos para entender Progol:
modelo de Herbrand de um programa lógico
CH(B  e1)
B = programa family
e1 = :- aunt(jane,henry).
BH(B  e1) =
person(jane) ... person(judy).
parent(jane,jane) ... parent(judy,judy).
father(jane,jane) ... father(judy,judy).
mother(jane,jane) ... mother(judy,judy).
sister(jane,jane) ... sister(judy,judy).
aunt(jane,jane) ... aunt(judy,judy)
CH(B  e1) =
person(jane) ... person(judy) 
parent(sam,henry)  parent(sarah,jim) 
father(sam,henry)  mother(sarah,jim) 
sister(jane,sam)  sister(sally,sarah) 
sister(judy,sarah)  aunt(jane,henry)
CH(B  e1) =
aunt(jane,henry) 
person(jane) ...  person(judy) 
parent(sam,henry)  parent(sarah,jim) 
father(sam,henry)  mother(sarah,jim) 
sister(jane,sam)   sister(sally,sarah) 
sister(judy,sarah)
Princípio lógico da aprendizagem com Progol:
derivação inversa dirigida por modos

A partir de:
• Uma base de exemplos E e uma base de conhecimento prévio B

Progol busca:
• as hipóteses mais concisas H tal que B  H  E
•  (B  H)  E  (B  H)  E  (B  E)  H
•  (B  E)  H  (B  E)  H  (B  E  H)

Considerando:
•
•
•
•
MH(P) o modelo de Herbrand mínimo de um programa lógico P.
B  E  MH(B  E)  H, e então H   MH(B  E)
já que G,S ((G -generaliza S)  (G  S)) (mas não vice-versa)
um subconjunto H’ de H pode ser calculado por
-generalização de  MH (B  E)
Etapas da busca por hipóteses com Progol
1. Busca 1o exemplo e1 em E
2. Busca bottom-up da hipótese mais específica (e1)
explicando e1 dado B e o viés V sobre as hipóteses
• busca 1a declaração modeh do predicado p1 tal que e1 = p1(...) em V
• constrói o sub-conjunto SH(e1,B,V) de MH(B   e1) que satisfaz as
restrições de viés (modeb e outras)
• (e1) = SH(e1,B,V) = h1 :- b1, ..., bn.
3. Busca heurística top-down da melhor generalização T(e1)
da hipótese mais específica (e1)
• Gera todas as cláusulas Ci com conclusão h1 e tendo com premissas
combinações de b1, ..., bn módulo substituições variável/variável
compatíveis com as declarações de modo
• T(e1) = cláusula gerada que maximiza uma heurística f(Ci) função da
concisão de Ci e do seu poder de generalização sobre E
4. acrescenta T(e1) nas regras aprendidas
5. tira de E os exemplos E’ explicados por T(e1) (i.e., tal que BT(e1)E’)
6. Repetir 1-5 até E = 
Princípio da construção
da hipótese mais específica 
B  E  MH(B  E)  H, e então H   MH(B  E)
 como em geral MH(P) pode ser infinito
 Progol não tenta construir MH (B  E)
 mas apenas o sub-conjunto SH(e1,B,V) de MH(B  e1)

• para um exemplo particular e1 no lugar de todos os exemplos E
• e sobre restrições de viés:


tanto explicitamente declaradas (modeb e outras)
quanto implícitas no algoritmo de construção de (e1)
ex, que todas as variáveis de (e1) sejam ligadas
Lembrete: variável V é ligada em C :- P1, …, Pn se
V  C ou V co-ocorre em mesma premissa com W ligada
que é garantido ser finito
 (e1) = SH(e1,B,V) = h1 :- b1, ..., bn.

Aprender gramática do inglês com Progol:
arquivo de entrada
% Parâmetros limitando a busca
:- set(i,5)? % limite no nível das variáveis em 
:- set(c,5)? % limite do numero de premissas em 
% aprendizagem sem exemplos negativos
:- set(posonly)?
% Declarações de modos
:- modeh(1,s(+wlist,-wlist1))?
:- modeb(1,det(+wlist,-wlist))?
:- modeb(1,prep(+wlist,-wlist))?
:- modeb(1,noun(+wlist,-wlist))?
:- modeb(1,tverb(+wlist,-wlist))?
:- modeb(1,iverb(+wlist,-wlist))?
:- modeb(*,np(+wlist,-wlist))?
:- modeb(*,vp(+wlist,-wlist))?
% Declarações de tipos
wlist([]).
wlist([W|Ws]) :- word(W), wlist(Ws).
word(a). ... word(walks).
% Conhecimento prévio: regras de formação dos
% sub-constituintes da frase inglesa
np(S1,S2) :- det(S1,S3), noun(S3,S2).
np(S1,S2) :- det(S1,S3), adj(S3,S4), noun(S4,S2).
det([a|S],S). det([the|S],S). det([every|S],S).
vp(S1,S2) :- tverb(S1,S2).
vp(S1,S2) :- tverb(S1,S3), prep(S3,S2).
noun([man|S],S). ... noun([ball|S],S).
tverb([hits|S],S). ... tverb([walks|S],S).
iverb([barks|S],S). ... iverb([walks|S],S).
prep([at|S],S). ... prep([from|S],S).
adj([big|S],S). ... adj([happy|S],S).
% Exemplos de frases
s([the,man,walks,the,dog],[]).
s([the,dog,walks,to,the,man],[]).
s([a,dog,hits,a,ball],[]). ...
s([a,ball,hits,the,dog],[]).
s([the,man,walks],[]).
s([a,ball,hits],[]). ...
s([a,man,walks],[]). ...
s([every,nice,dog,barks],[]).
Algoritmo de construção de 
1. busca 1o exemplo ainda não coberto e1 = p1(...). em E
inicializa (e1) =  e domínio da variáveis a ligar D = 
2. busca 1a declaração modeh(R1, p1(...)) em V
• unifica R1 vezes p1(...) com B
• insere instanciações resultantes dos argumentos +tipo de p1(...) em D
• insere p1(...) instanciado em (e1)
3. para cada declaração modeb(Ri pi(...)) em V:
•
•
•
•
unifica pi(...) com B e D para instanciar argumentos +tipo
unifica resultado Ri vezes com B para instanciar argumentos -tipo
insere instanciações resultantes dos argumentos -tipo em D
insere pi(...) instanciado em (e1)
4. complementa (e1) com lei de Morgan
•
•

considerando os argumentos instanciados de (e1)
como constantes de Skolem a substituir por variáveis
E = exemplos, V = declarações de viés, B = conhecimento prévio
Aprender gramática do inglês com Progol:
construção de (e1)




...

1o exemplo: e1 = s([the,man,walks,the,dog],[]).
1o modeh sobre s: :- modeh(1,s(+wlist,-wlist))?
1 = {+wlist1/[the,man,walks,the,dog], -wlist1/[]},
D1 = {[the,man,walks,the,dog]},
s([the,man,walks,the,dog],[])  (e1)
1o modeb: :-modeb(1,det(+wlist,-wlist)).
2 = {+wlist2/[the,man,walks,the,dog], por unificação de D1 com sub-gramática de det em B
-wlist2/[man,walks,the,dog]},
por unificação com S em det([the|S],S)
D2 = {[the,man,walks,the,dog],[man,walks,the,dog]}
det([the,man,walks,the,dog],[man,walks,the,dog])  (e1)
2o modeb: :-modeb(1,noun(+wlist,-wlist)).
3 = {+wlist3/[man,walks,the,dog], por unificação de D2 com sub-gramática de noun em B
-wlist3/[walks,the,dog]},
por unificação com S em noun([man|S],S)
D2 = {[the,man,walks,the,dog],[man,walks,the,dog],[walks,the,dog]}
noun([man,walks,the,dog],[walks,the,dog])  (e1)
No modeb: :- modeb(*,np(+wlist,-wlist)).
N = {+wlistN/ [the,dog], por unificação de DN-1 com sub-gramática de np em B
-wlistN/[]},
por unificação com S2 em np(S1,S2) :- det(S1,S3), noun(S3,S2)
DN = {[the,man,walks,the,dog],[man,walks,the,dog],[walks,the,dog],[the dog],[]}
np([the,dog],[])  (e1)
Aprender gramática do inglês com Progol:
construção de (e1) (cont.)



(e1) = s([the,man,walks,the,dog],[]) 
det([the,man,walks,the,dog],[man,walks,the,dog]) 
noun([man,walks,the,dog],[walks,the,dog]) 
np([the,man,walks,the,dog],[walks,the,dog]) 
tverb([walks,the,dog],[the,dog])  iverb([walks,the,dog],[the,dog]) 
vp([walks,the,dog],[the,dog])  det([the,dog],[dog]) 
noun([dog],[])  np([the dog],[])
(e1) = s(A,B)  (det(A,C)  noun(A,D)  np(C,D)  tverb(D,E)  iverb(D,E) 
vp(D,E)  det(E,F)  noun(F,B)  np(E,B))
(e1) = s(A,B) :- det(A,C), np(A,D), noun(C,D), tverb(D,E), iverb(D,E),
vp(D,E), det(E,F), noun(F,B), np(E,B).
Princípio da generalização de  em T


Busca top-down em reticulado ordenado por -generalização
Podada pela:
• satisfação das restrições declaradas em V
• restrições dos literais das hipóteses nos literais de
(e1) = h1 :- b1, ..., bn

Abordagem gerar e testar
1. gerar todas as cláusulas Ci com conclusão h1 e
com premissas combinações de b1, ..., bn módulo substituições
variável/variável compatíveis com as declarações de modo e
as restrições de viés paramétricas em V
2. testar as Ci geradas pela função heurística:
f(Ci) = ps(Ci) - ns(Ci) - hs(Ci) - cs(Ci) + 1 onde:




ps(Ci) = número de verdadeiros positivos e+  E+ tal que B  Ci  e+
ns(Ci) = número de falso positivos e-  E- tal que B  Ci  e-
cs(Ci) = comprimento da Ci
hs(Ci) = número de premissas faltando para ligar todas as variáveis
ainda não ligadas em Ci
3. Escolher como T a hipótese ligada que maximiza f
Aprender gramática do inglês com Progol:
generalização de (e1) em T(e1)

Formato do rastreamento:
[C: f(Ci),ps(Ci),ns(Ci),hs(Ci), Ci]
Exemplo de rastreamento:
CProgol Version 4.4
|- consult(grammarTutorial)?
yes
|- generalise(s/2)?
[Generalising s([the,man,walks,the,dog],[]).]
[Most specific clause is]
s(A,B) :- det(A,C), np(A,D), noun(C,D),
tverb(D,E), iverb(D,E), vp(D,E),
det(E,F), np(E,B).
[Learning s/2 from positive examples]
[C:-3,56,55,3 s(A,B).]
[C:38,56,13,3 s(A,B) :- det(A,C).]
[C:47,56,4,2 s(A,B) :- det(A,C), np(A,D).]
...
[C:48,52,1,1 s(A,B) :- det(A,C), np(A,D),
tverb(D,E), iverb(D,E).]
...

[C:35,16,1,0 s(A,B) :- det(A,C), np(A,D),
iverb(D,E), np(E,B).]
...
[C:51,52,1,1 s(A,B) :- np(A,C), tverb(C,D).]
...
[C:42,24,1,0 s(A,B) :- np(A,C), tverb(C,D),
vp(C,E), np(E,B).]
...
[C:44,24,1,0 s(A,B) :- np(A,C), vp(C,D) np(D,B).]
[C:42,24,1,1 s(A,B) :- np(A,C), vp(C,D), np(D,E).]
[106 explored search nodes]
f=44,p=24,n=1,h=0
[Result of search is]
s(A,B) :- np(A,C), vp(C,D), np(D,B).
[6 redundant clauses retracted]
Aplicações práticas de Progol




Processamento de linguagem
natural: indução de gramática a
partir de corpus de texto
Mineração da Web:
aprendizagem de padrões de
navegação por interface
adaptativa
Mineração de dados do
Detran: previsão de
engarrafamento
Jogos: indução de estratégias
para jogar xadrez


Medicina: previsão de
carcinogenesa
Biologia molecular:
• descoberta de estrutura de
proteina
• descoberta de função de
enzima


Indústria farmacêutica:
invenção de novos remédios
Indústria metalúrgica:
invenção de novas compósitos