Sistema Progol
TÉCNICAS E HEURÍSTICAS
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;
Definição do Sistema

O Progol é um interpretador Prolog com
provador limitado por profundidade. (depth
bound);

O Progol possui um mecanismo de inversão
da conseqüência lógica, que o torna capaz
de aprender e/ou refinar teorias de forma
indutiva (através de exemplos);
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;
Declarações de Modo

São uma forma de definir (restringir) as relações
entre diversos literais nas cláusulas geradas, como :
– Os literais que podem aparecer no corpo e na cabeça;
– O tipo de cada termo em um predicado;
– A definição de termos de entrada e saída em um
predicado;
– O número máximo de literais com os quais um
predicado pode se relacionar;
Declarações de Modo
Restringindo literais do corpo e cabeça

Modeb
– As declarações modeb definem quais os literais
que podem aparecer no corpo de uma regra;
Ex.: modeb(*, long(+car))

Modeh
– As declarações modeh definem quais os literais
que podem aparecer na cabeça de uma regra;
Ex.: modeh(*, eastbound(+train))
Declarações de Modo
Restringindo utilização de variáveis

Definição de Tipos :
– As declarações modeb e modeh necessitam da
definição de um tipo para cada termo do literal
sendo definido.
modeh(*,eastbound(+train)), modeb(*,long(+car))
Não é permitido : eastbound(A)<- long(A)
Declarações de Modo
Restringindo utilização de variáveis

Definição de Tipos :
– Para cada tipo definido, nós devemos definir
também o seu domínio.
Ex. modeb(shape(+car, #shape))
Domínio car :

car(car_11), car(car_12), car(car_22).
Domínio shape :

shape(elipse), shape(hexagon), shape(u_shaped).
Declarações de Modo
Restringindo utilização de variáveis

Termos de Entrada e Saída :
– Definição do predicado como uma função com
parâmetros de entrada (termos de entrada) e
parâmetros de saída (termos de saída);
Existem três tipos de marcadores: +tipo(entrada), –tipo
(saída) e #tipo (constante);
modeb(*, open(+car)), modeb(*, has_car(+train, -car))
modeb(*, shape(+car, #shape))
Declarações de Modo
Restringindo utilização de variáveis

Cadeia de variáveis :
– Uma cláusula C é um encadeamento de variáveis (variable-
chaining) se e somente se ela contém uma cadeia de variáveis
v1, ..., vn, tal que v1, vn são, respectivamente, termos de entrada
e saída na cabeça de C e cada par vi,vi+1, 1 i < n, são
respectivamente termos de entrada e saída em um literal do
corpo de C.

Uma cláusula C é E/S completa (I/O complete) se e
somente se para cada termo de saída u da cabeça de C,
existe uma cadeia de variáveis v1,..,vn, onde vn = u.
Declarações de Modo
Restringindo utilização de variáveis
Considere o seguinte exemplo:
modeh(*, mult(+real, +real,-real)), modeb(*, dec(+real,-real))
modeb(*, plus(+real, +real,-real))
C = mult(E,F,G)  dec(E, H), mult(F, H, I), plus(F,I,G).
C é um encadeamento de variáveis pois contém a cadeia
de variáveis E,H,I,G.
C é E/S completa pois existe uma cadeia de variáveis
para G em C.
.
Declarações de Modo
Restringindo utilização de variáveis

Restrição do Progol :
– Uma variável só pode ser utilizada como termo de
entrada em um literal se ela for uma variável global
(da cabeça, quantificada universalmente) ou uma
variável de trabalho retornada anteriormente na
regra como resposta (quantificada existencialmente).
eastbound(A)<-has_car(A,B), not open(B), not long(B)
eastbound(A)<-not open(B), has_car(A,B), not long(B)
Declarações de Modo
Restringindo utilização de variáveis

Literais determinados :
– São literais que “fornecem somente uma resposta”
para uma determinada configuração de parâmetros
de entrada.
dec(5,4), inc(5, 6), infront_of(car_11, car_12).
has_car(train1, car_11), has_car(train1, car_12)
Declarações de Modo
Restringindo utilização de variáveis

Profundidade de uma variável :
– Seja A L1,..Ln uma cláusula ordenada
– A profundidade de uma variável v é definida como :
 prof(v) = 0, se v ocorre em A
 prof(v)=prof(x)+1, onde v, x ocorre em Li e x é a variável
de maior profundidade em Li. Se nenhuma das outras
variáveis de Li tem a profundidade já definida então
prof(v) = 
Declarações de Modo
Restringindo utilização de variáveis

No Progol, nós podemos afirmar que a profundidade
exprime o menor caminho entre uma variável de
trabalho (quantificada existencialmente) e uma
variável global (quantificada universalmente, da
cabeça).

eastbound(A)<-has_car(A,B), has_car(A,C), long(B),
short(C), infront_of(B,C).
Prof(A) = 0
Prof(B) = 1
Prof(C) = 1
Declarações de Modo
Restringindo o número o de relações entre
predicados

Parâmetro de Recall :
– A declaração modeb (e/ou modeh) para um literal p
permitem definir o número máximo de possíveis
instanciações para os termos de saída de p.
modeb(2, squareroot(+real, -real)),
modeb(1, dec(+int,-int))
modeb(*, has_car(+train,-car))
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;
Algoritmo da Bottom Clause
• Entrada : h, i naturais, B conhecimento preliminar, e uma
instância e M um conjunto de declarações de modo.
Seja m uma declaração de modo. a(m) representa o átomo
formado pela troca de cada marcador por uma variável
distinta.
Ex.: a(modeb(*, open(+car))) = open(B)
Seja hash : Termos  + uma função que mapeia termos
em números naturais.
• Seja k = 0, i = <>, TermosInt =
Algoritmo da Bottom Clause
1. Se não existe nenhum modeh em M tal que a(m)  e
então retorne .
2. Caso contrário, seja m a primeira declaração de modo
tal que a(m)  e com substituição h. Seja ah uma cópia
de a(m). Para cada v/t em h, se v corresponde a um
marcador #tipo em m troque v em ah por t, caso contrário
troque v por vj onde j = hash(t). Adicione ah em i. Se v
for um termo de entrada (+tipo), adicione t a TermosInt.
3. Se k = i então retorne i caso contrário k = k + 1.
Algoritmo da Bottom Clause
4.Para cada modeb mb seja {v1,..,vn} variáveis de entrada
em a(mb). Seja T(mb) = T1 x .. x Tn o conjunto de tuplas
de termos tal que cada Tj corresponde ao conjunto de
todos os termos do mesmo tipo de vj em TermosInt. Para
cada <t1,..,tn> seja ab uma cópia de a(mb) e  =
{v1/t1,...,vn/tn}. Se Prolog com limite de profundidade h for
bem-sucedido na consulta ab?, retornando o conjunto de
respostas b então para cada b em b e v/t em b se v
for constante (#tipo) então troque v em ab por t caso
contrário troque v em ab por vj onde j = hash(t) e adicione
ab em i. Se v for um termo de saída(-tipo), adicione t a
TermosInt.
5.Vá para o passo 3.
.
Algoritmo da Bottom Clause
eastbound(east2). (i = 2, h = 100)
B = {has_car(east2,car_21), has_car(east2, car_22),
has_car(east2, car_23), open(car_21), open(car_22),
shape(car_21, u_shaped), shape(car_22, u_shaped),
shape(car_23, rectangle)}
i = {eastbound(A)  has_car(A,B), has_car(A,C), has_car(A,D),
open(B), open(C), not open(D), not long(B), not long(C),
not long(D), shape(B, u_shaped), shape(C, u_shaped),
shape(D, rectangle) }
TermosInt = {east2,
{east2 car_21, car_22, car_23}
.
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;
Algoritmo de Covering do
Progol
1.Se E =  então retorne B.
2.Seja e o primeiro exemplo de E.
3.Construa a cláusula i de e.
4.Construa a cláusula cl para i.
5.Seja B = B  cl
6.Seja E’= {e | e  E , B╞ e}
7.E = E – E’ e retorna para 1.
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;
Algoritmo A* de construção de
cláusula

O algoritmo de construção de cláusula do
Progol para um exemplo e busca encontrar a
melhor cláusula cl tal que • cl  i,

O algoritmo inicia com uma cláusula vazia e
através de um operador de refinamento
(especialização) e uma heurística, pesquisa
no espaço de cláusulas tais que • cl  i.
Algoritmo A* de construção de
cláusula

Definição da -subsumption :
• Seja C e D duas cláusulas. C -subsume D
ou C  D se e somente se CD.
C = eastbound(A)has_car(A,B), long(B), has_car(A,C), open(C).
D = eastbound(A)has_car(A,B), long(B), open(B), shape(B, triangle).
= {A/A, B/B, C/B}
C = eastbound(A)has_car(A,B), long(B), open(B)  D.
Algoritmo A* de construção de
cláusula

Um operador de refinamento retorna para uma
determinada cláusula C, um conjunto de
especializações de C.

Ex.:
C = eastbound(A) 
(C) = {(eastbound(A)  has_car(A,B)),
(eastbound(A)  has_car(A,B), not open(B)), ...}
Algoritmo A* de construção de
cláusula

O operador de refinamento (C) é construído
para manter • cl  i :
– Ele trabalha com estados do tipo <C,,k>,
onde C é uma cláusula,  um conjunto de
substituições tal que Ci e k (1  k  n,
onde n = |i|) um índice indicando que os
literais l1,..,lk foram considerados para estar
em C.
Algoritmo A* de construção de
cláusula

Seja C uma cláusula e  uma substituição tal que
C  i.
<C´, ´, k´> está em (<C, , k>) se e somente se
C´ = C  {l}, k´ = k, <l,´>  (, k) e C´Li(M), ou
C´ = C, k´ = k+1, ´ =  e k < n.
Algoritmo A* de construção de
cláusula

Uma variável v é dita splittable em um literal p
se ela corresponde a um marcador +tipo ou –
tipo em uma declaração modeh de p ou se
corresponde a um marcador –tipo em uma
definição modeb de p.
Ex.:
eastbound(A)  has_car(A,B), not open(B), not
long(B), has_car(A,C), long(C), open(C).
Algoritmo A* de construção de
cláusula

Sejam l = p(v1,...,vm), lk = p(u1,...,um), o k-ésimo
literal de i duas cláusulas,  e ’, ’, dois
conjuntos de substituições

< l, ’>  (,k) se e somente se
• l’=lk,
• ’- = {(vj / uj) | uj é splittable em lk e vj não pertence a
dom()},
• Para cada variável uj splittable em lk, vj / uj  ’
Algoritmo A* de construção de
cláusula
1. Seja Abertos = {<,,1>} e Fechados = 
2. Seja s = melhor(Abertos) e Abertos = Abertos-{s}
3. Seja Fechados = Fechados  {s}.
4. Se poda(s) vá até 6.
5. Seja Abertos = (Abertos  (s)) - Fechados.
6. Se terminado(Fechados, Abertos) então retorne
melhor(Fechado).
7. Se Abertos =  então imprima ´sem compressão´ e
retorne <e, , 1>
8. Vá até 2.
Algoritmo A* de construção de
cláusula
Verdadeiro
se ns = 0 e fs > 0
Falso
caso contrário
poda(s) =
terminado(S,S´) =
Verdadeiro se s = melhor(S), ns = 0,
fs > 0 e para cada s´  S´ fs  fs´
Falso
caso contrário
.
Algoritmo A* de construção de
cláusula
ps = |{e : e  E | B  C  e╞h •
}|
ns = |{e : e  E | B  C  e╞h •
}|
(# ex. corretos)
(# ex. incorretos)
cs = |C|-1
(# tamanho da cláusula-1)
Vs = {v : u / v   e u está no corpo de C}
hs = min vVsd´(v)
fs = ps – (ns + cs + hs)
(# de átomos para completar a cláusula)
(medida de performance da cláusula)
melhor(S) é o estado s  S que tem o maior valor de f e cs  c.
.
Algoritmo A* de construção de
cláusula

se não existe variável –tipo
na cabeça de i.
se v é uma variável –tipo na
cabeça de i.
se v não está em i.
(minuUvd´(u)+1)
caso contrário.
0
0
d´(v)=
onde Uv são variáveis –tipo nos literais do corpo de C
onde v é um termo de entrada.
.
Algoritmo A* de construção de
cláusula
Considere o seguinte exemplo:
modeh(*, mult(+real, +real,-real)), modeb(*, dec(+real,-real))
modeb(*, plus(+real, +real,-real))
i = mult(A,B,C)  dec(A, D), dec(B, E), mult(B, D, F),
mult(A, E, G), plus(A, G, C), plus(B, F, C).
C = mult(A,B,C)  dec(A, D), mult(B, D, F).
d’(A)=3, d’(B)=2, d’(D) = 2, d’(F) = 1 e d’(C) = 0 (h = 1)
C = mult(A,B,C)  dec(A, D),
d’(A)=3, d’(B)=3, d’(D) = 2 e d’(C) = 0 (h = 2)
.
Algoritmo A* de construção de
cláusula
• Este algoritmo é garantido de terminar e retorna a cláusula,
se existir, que tem o melhor poder explanatório com o menor
tamanho possível. No pior caso, o algoritmo irá considerar
todas as cláusulas da ordenação subsumption.
• Refinamentos de estados s são desconsiderados se fs > 0 e
ns = 0, porque os refinamentos aumentam cs e tendem a
diminuir ps, piorando o valor de fs. O algoritmo termina
quando existe um estado já fechado com maior fs já
encontrado até então e que não pode ser melhorado por
refinamentos. Considera-se que nenhum outro estado s´
ainda aberto com fs  fs´ pode ter refinamento melhor.
.
Progol – Tópicos

Definição do sistema;
 Declarações de Modo;
 Construção da cláusula mais específica;
 Algoritmo de Covering do Progol;
 Algoritmo A* de construção de cláusula;
 Exemplo de construção de cláusula;