CLP(BN): Constraint Logic
Programming with Bayes Net
Constraints
Rodrigo Cunha
Cin-UFPE
Roteiro
Contexto
 Introdução
 BN (Bayesian Networks)
 PRM (Probabilistic Relational Modelo)
 CLP(BN)
 Exemplo de CLP(BN)
 Avaliação (Evaluation)
 Aula Prática
 Referências Bibliográficas

11/08/2003
Rodrigo Cunha – Cin / UFPE
2
O que é CLP(BN)?


Extensão de Prolog que considera probabilidades
bayesianas sobre termos lógicos como restrições na
maneira de CLP.
Restrições de natureza diferentes do que CLP(FD),
CLP(R):



epistemológica no lugar de ontológica
não sobre domínio modelado mas sobre crenças do
agente sobre domínio
Segue esquema geral CLP:
máquina de inferência inter-laça unificação de termos
lógicos com resolução de restrições
 resolvedor de restrições implementa algoritmos
herdados de redes bayesianas (marginalização,
11/08/2003
Rodrigo Cunha – Cin / UFPE
simulação estocástica,
..)

3
Contexto

Fig Jr.
11/08/2003
Rodrigo Cunha – Cin / UFPE
4
CLP(BN) e Redes Bayesianas

CLP(BN):



Estritamente mais expressivo que Probabilistic
Relational Model (PRM)
Autoriza recursão
PRM:



redes bayesianas da 1a ordem
arcos com CPT não ligam mais proposições, mas
tabelas relacionais cujos elementos são descritos em
jargão orientado a objetos
resultado da instanciação de PRM via unificação de
variáveis: rede Bayesiana
11/08/2003
Rodrigo Cunha – Cin / UFPE
5
Revisão de PRM




Constantes, nomeando objetos de classes
 Ex: ProfSmith pertence a classe Professor, Jones
pertence a classe Estudante, Bloggs pertence a classe
Estudante
Funções Simples: classes -> imagem finita
 Ex: Inteligencia(Jones) = {alta, baixa}, Famoso(ProfSmith)
= {true, false}
Funções Complexas: de classes em classes
 Ex: Orientador(Jones) = ProfSmith
Informação probabilística: especificar pais para as funções
simples
 x, x Estudante  Parents(Sucesso(x)) =
{Inteligencia(x), Famoso(Orientador(x))}
 x, x Estudante  P(Sucesso(x) = true| Inteligencia(x) =
alta, Famoso(Orientador(x)) = true) = 0.95
11/08/2003
Rodrigo Cunha – Cin / UFPE
6
Revisão de PRM
Professor
Fame(ProfSmith)
Fame
Funding
Student
Funding(ProfSmith)
Intelligence(Bloggs)
Intelligence(Jones)
Success(Bloggs)
Success(Jones)
Inteligence
Success
Advisor
11/08/2003
Rodrigo Cunha – Cin / UFPE
7
Jargões relacionais e OO

Tradução (E-R para UML):
Databases
11/08/2003
Relational Logic
Table
Class
Tuple
Object
Standard Field
Descriptive Attribute
Foreign Key Field
Reference Slot
Rodrigo Cunha – Cin / UFPE
8
Programa CLP(BN)
Cláusula:
H
A
B
Restrição (parte probabilística)
Cabeça da cláusula.
11/08/2003
Conjunção de literais
Rodrigo Cunha – Cin / UFPE
9
Programa CLP(BN)
notação GradeC / B
Estrutura
Ontológica Lógica
reg_grade (K, skG (K,D,I)) :reg_course (K,C),
reg_student (K,S),
course_diff (C,D),
student_intell (S,I).
11/08/2003
Restrição
Epistemológica
Probabilística
D
Rodrigo Cunha – Cin / UFPE
I
skG (K,D,I)
10
Programa CLP(BN)
CPT de uma cláusula: equivalente a uma redes
bayesianas, onde cada nó é uma variável aleatória
D
Influência
causal direta
11/08/2003
I
Variável
skG (K,D,I)
Rodrigo Cunha – Cin / UFPE
11
Exemplo: CLP(BN) x PRM
Dar uma de Gisele nos fontes
M
Professor
Teaching-Ability
Popularity
M
1
Course
Intelligence
1
Rating
M
Difficulty
Student
AVG
Course rating depende da
média da satisfação dos
estudantes no curso, ou
11/08/2003
seja,
todas satisfações..
Registration
Satisfaction
Grade
Rodrigo Cunha – Cin / UFPE
M
Ranking
AVGStudent ranking
depende da avg de
grades, ou seja,
todas grades12
Representar PRM com CLP(BN)
Como converter BD relacional em programa
lógico?
 2 opções:


Um predicado para cada tabela relacional


Um predicado binário para cada campo não
chave


usual, BD dedutivas
CLP(BN)
Para cada campo do BD:


regra lógica que representa os seus pais,
e a distribuição de probabilidade condicional.
11/08/2003
Rodrigo Cunha – Cin / UFPE
13
Expressar BD de PRM como
fatos CLP(BN)
Course
Professor
Key
Popularity
Sue
David
Ability
h
l
h
l
Sam
Terry
11/08/2003
Professor
cs1
cs2
Sue
David
Rating
Difficulty
h
h
h
l
Registration
Student
Key
Key
Intelligence
Rank
m
h
m
h
Key
Course
Student
r1
r2
r3
cs1
cs2
cs1
Sam
Sam
Terry
Rodrigo Cunha – Cin / UFPE
Satisfaction
Grade
h
l
h
a
c
b
14
tabelas binárias
11/08/2003
Rodrigo Cunha – Cin / UFPE
15
Expressar BD de PRM como
fatos CLP(BN)
prof_pop(sue,h).
prof_pop(david,l).
prof_abil(sue,h).
prof_abil(david,l).
course_prof(cs1,sue).
course_prof(cs2,david).
course_rate(cs1,h).
course_rate(cs2,h).
student_intell(sam,m).
student_intell(terry,h).
student_rank(sam,m).
student_rank(terry,h).
reg_course(r1,cs1).
reg_course(r2,cs2).
reg_course(r3,cs1).
reg_student(r1,sam).
reg_student(r2,sam).
reg_student(r3,terry).
course_diff(cs1,h).
course_diff(cs2,l).
reg_sat(r1,h).
reg_sat(r2,l).
reg_sat(r3,h).
reg_grade(r1,a).
reg_grade(r2,c).
reg_grade(r3,b).
11/08/2003
Rodrigo Cunha – Cin / UFPE
16
Expressar CPT de PRM como
regras CLP(BN)
O Corpo de cada regra CLP(BN) é
construído em três estágios:


Estágio Relacional

Estágio de Agregação

Estágio CPT
11/08/2003
Rodrigo Cunha – Cin / UFPE
17
Estágio Relacional
Regras com variáveis compartilhadas
representam de seqüência de chave
estrangeira
 Cada passo gera um termo do tipo: ri(X,Y),
onde:



X representa a chave primária de R
Y representa o i-ésimo campo da relação R.
11/08/2003
Rodrigo Cunha – Cin / UFPE
18
Exemplo:
Professor
Key
Course
Popularity
Ability
h
l
h
l
Sue
David
Key
Sam
Terry
Student
Intelligence
Rank
m
h
m
h
reg(Key, Student)
reg(Key,Course)
course(Key,Professor)
professor(Key,Ability)
11/08/2003
Key
Professor
cs1
cs2
Sue
David
Rating
Difficulty
h
h
h
l
Registration
Key
Course
Student
r1
r2
r3
cs1
cs2
cs1
Sam
Sam
Terry
Rodrigo Cunha – Cin / UFPE
Satisfaction
Grade
h
l
h
a
c
b
19
Estágio de Agregação



Este estágio é para variáveis que tem
múltiplas ligações.
Podemos ter todas as ligações de Ability
através do predicado built-in findall.
Por exemplo:
course_rating (K, Rating) :findall (S, (reg_course(R,K) , (reg_sat(R,S)), Sats),
avg(Sats,AvS).
11/08/2003
Rodrigo Cunha – Cin / UFPE
20
Convertendo PRM em CLP(BN)
Estágio CPT
11/08/2003
Rodrigo Cunha – Cin / UFPE
21
Resultado dos 3 estágios
reg_grade(K, Grade) :
reg_course(K,C), reg_student(K,S),
course_diff (C,D), student_intell
(S,I).
{Grade = grade(Reg) with p(
[a,b,c],[ 0.5,0.1,0.8,0.3
0.4,0.5,0.1,0.6,
0.1,0.4,0.1,0.1] ,
[D,I])}.
11/08/2003
Rodrigo Cunha – Cin / UFPE
22
Neste caso D e I só podem assumir dois valores.
Professor Clauses Botar
probabilidade
skA (K)
prof_abil (K, sk (K)).
Fonte menos, juntar pedaços
em menos transparencias
A
prof_pop (K,
skP(K,A)):prof_abil (K,A).
11/08/2003
A
skP (K,A)
Rodrigo Cunha – Cin / UFPE
23
Registration Clauses
reg_grade (K, skG (K,D,I)):reg_course (K,C),
reg_student (K,S),
course_diff (C,D),
student_intell (S,I).
D
I
skG (K,D,I)
11/08/2003
Rodrigo Cunha – Cin / UFPE
24
Registration Clauses
reg_sat (K, sks(K,A,G)):reg_course (K,C),
course_prof (C,P),
prof_abil (P,A),
reg_grade (K,G).
11/08/2003
Rodrigo Cunha – Cin / UFPE
A
G
Sks (K,A,G)
25
Course Clauses
course_rating (K, skR (K,AvS)):findall (S,
(reg_course(R,K),
(reg_sat (R,S)),
Sats),
avg(Sats,AvS).
course_diff(K, skD(K)).
11/08/2003
AvS
skR (K,AvS)
skD (K)
Rodrigo Cunha – Cin / UFPE
26
Student Clauses
student_intell (K, skI (K)).
skI (K)
student_rank(K,skSR(K,AvG)):findall(G,
(reg_student(R,K),
reg_grade (R,G)),
Grades),
avg (Grades, AvG).
11/08/2003
Rodrigo Cunha – Cin / UFPE
AvG
skSR (K,AvG)
27
Consulta
reg_grade(r2, Grade), ,,,,,
 Qual é distribuição de probabilidade dos
valores da nota de sam em cs2?
 Resulta numa rede de restrições. CLP(BN) cria
uma rede de restrições com grade(r2)
dependendo de dif(course) e int(student).
CLP(BN) responderá com a distribuição de
probabilidade marginal de grade(r2).

11/08/2003
Rodrigo Cunha – Cin / UFPE
28
Avaliação (Evaluation)
A maior aplicação de sistemas Bayesianos é
condicionar evidências, por exemplo: se um
estudante está numa classe avançada
podemos querer saber sua inteligência.
 ?- grade(r2, a), intelligence(bob, I).
 O usuário introduz evidências através da
classe r2. Na prática o sistema executa
construindo um Rede de Bayes com duas
variáveis. A rede é avaliada através da técnica
de eliminação de variável (Seminário de
Hugo).

11/08/2003
Rodrigo Cunha – Cin / UFPE
29
Avaliação (Evaluation)
Uma consulta em CLP(BN) é uma consulta
Prolog, conjunção de literais positivos.
 Uma ou mais provas construídas através de
resolução, em cada passo de resolução
termos de diferentes cláusulas devem ser
unificados.
 Sendo unificados os termos participam das
restrições bayesianas.
 Construir uma grande rede bayesiana
consistindo de todos as pequenas redes de
bayes que foramRodrigo
unificadas
durante a fase de30
11/08/2003
Cunha – Cin / UFPE
resolução.

Em ppt com cores diferentes
entre variáveis lógicas e
aleatórias
11/08/2003
Rodrigo Cunha – Cin / UFPE
31
Variable Elimination em
Prolog
AuthorInstitution
AuthorRating
JournalRating
PaperRating
PaperCited
 P(PC, PR, JR, AI , AR)
P(PC) 
PR, JR, AI , AR
 P(PC | PR) P(PR | AI , JR) P(AR | AI ) P(AI ) P(JR)

PR, JR, AI , AR
  P(PC | PR) P(JR) P(PR | AI , JR) P(AI ) P(AR | AI )
PR
11/08/2003
JR
AI
Rodrigo Cunha – Cin / UFPE
AR
32
Restrições
Probabilísticas
Nesta apresentação apresentaremos apenas restrições de variáveis
discretas, mas é possível representar CLP(BN) através de
restrições contínuas. (Trabalho Atual).
• Distribuição Normal
• Distribuição Qui-Quadrado
• Distribuição T-Student
• Distribuição F
11/08/2003
Rodrigo Cunha – Cin / UFPE
33
Pergunta?

Dado que temos um PRM, qual a utilidade
de usar a representação CLP(BN)?
Incorporação de probabilidade na lógica de
primeira ordem.

CLP é uma extensão da programação
lógica.

Ajudar a entender melhor o
relacionamento entre PRMs e probabilistic
logic.

CLP(BN) podeRodrigo
aprender
usando ILP
11/08/2003
Cunha – Cin / UFPE
34

recursao

CLP(BN)
em
Yap Prolog
Aula de Laboratório
Yap
Yap é um sistema desenvolvimento cuja
linguagem é Prolog
 É multi-plataforma
 Código-fonte aberto e em desenvolvimento
 Contém diversas extensões prolog como por
exemplo: DEC-10 Prolog, Quintus Prolog e CProlog.
 Autores: Vítor Santos Costa,Luís
Damas,Rogério Reis e Ruben Azevedo
(Universidade do Porto).
11/08/2003
Rodrigo Cunha – Cin / UFPE
36

Site: http://www.ncc.up.pt/~vsc/Yap/

Yap
Possui alguns pacotes:
CHR package
 CLP(Q,R) package
 Logtalk Object-Oriented system
 Pillow WEB library
 CLP(BN)

Quando compilar o Yap digitar
configure --enable-coroutining --enable-depth-limit
11/08/2003
Rodrigo Cunha – Cin / UFPE
37
Yap

Executar



Conectar-se via ssh a buique.cin.ufpe.br
Mudar para o diretório onde estão os arquivos .yap
Executar Yap no prompt Unix.
yap

Carregar Arquivo

File_name.
Digitar [FILE_NAME_1, ...,FILE_NAME_N]. para
carregar N arquivos no ambiente Yap; ou
consult(FILE_NAME).

ou
reconsult(FILE_NAME).


11/08/2003
Rodrigo Cunha – Cin / UFPE
38
CLP(BN) no Yap
CLP(BN) é um pacote da mais nova versão do
YAP.
 Código-fonte aberto e em desenvolvimento
 Autores: Vítor Santos Costa, David Page e
James Cussens.
 Site: www.cos.ufrj.br/~vitor/Yap/clpbn/

11/08/2003
Rodrigo Cunha – Cin / UFPE
39
CLP(BN) no Yap
Se tudo estiver certo ... 
 Baixar e descompactar clpbn.tar.gz no
diretório $PATH/x/CLPBN
 Baixar e descompactar o exemplo
school.tar.gz e vai ficar com
$PATH/x/school_example
 faça cd para $PATH/x/school_example
 agora chame o yap
 > yap
 use_module('../CLPBN/clpbn').
11/08/2003
Rodrigo Cunha – Cin / UFPE
 ['school.yap'].

40
CLP(BN) no YAP
Se tudo der certo: 
professor_key(X).
X = p0 ?
yes
?- professor_ability(X,A).
X = p0,
A=[0.5,0.4,0.1]=>[h,m,l] ? ;
X = p1,
A=[0.8,0.15,0.05]=>[h,m,l] ? ;
X = p2,
A=[0.2,0.6,0.2]=>[h,m,l] ? ;
X = p3,
A=[0.6,0.3,0.1]=>[h,m,l] ? ;
11/08/2003
Rodrigo Cunha – Cin / UFPE
41
CLP(BN) no YAP
?- professor_popularity(X,A).
X = p0,
A=[0.53,0.3,0.17]=>[h,m,l] ? ;
X = p1,
A=[0.75,0.175,0.075]=>[h,m,l] ? ;
X = p2,
A=[0.3,0.4,0.3]=>[h,m,l] ? ;
X = p3,
A=[0.6,0.25,0.15]=>[h,m,l] ? ;
no
11/08/2003
Rodrigo Cunha – Cin / UFPE
42
CLP(BN) no YAP
?- professor_popularity(X,A), professor_ability(X,h).
X = p0,
A=[0.9,0.1,0.0]=>[h,m,l] ? ;
X = p1,
A=[0.9,0.1,0.0]=>[h,m,l] ? ;
X = p2,
A=[0.9,0.1,0.0]=>[h,m,l] ? ;
X = p3,
A=[0.9,0.1,0.0]=>[h,m,l] ? ;
11/08/2003
Rodrigo Cunha – Cin / UFPE
43
CLP(BN) no YAP
?- professor_ability(X,A), professor_popularity(X,h).
X = p0,
A=[0.849056603773585,0.150943396226415,0.0]=>[h,m,l]
?;
X = p1,
A=[0.96,0.04,0.0]=>[h,m,l] ? ;
X = p2,
A=[0.6,0.4,0.0]=>[h,m,l] ? ;
X = p3,
A=[0.9,0.1,0.0]=>[h,m,l] ? ;
no
11/08/2003
Rodrigo Cunha – Cin / UFPE
44
CLP(BN) no YAP
?- course_rating(c0,X).
X=[0.595526873437529,0.352055580547983,0.052417546
0144877]=>[h,m,l] ?
yes
?- course_rating(c0,X),course_professor(c0,P),
professor_ability(P,h).
P = p0,
X=[0.873,0.125,0.002]=>[h,m,l] ?
yes
11/08/2003
Rodrigo Cunha – Cin / UFPE
45
Referência Bibliográfica
Friedman, N., Getoor, L., Koller, D., and
Pfeffer, A. (1999) Learning Probabilistic
Relational Models. In Relational Data Mining,
Dzeroski and Lavrac, Editors, Springer-Verlag,
2001.
 Costa, V., Page, D., Cussens, J. (2001)
LCLP(BN): Constraint Logic Programming for
Probabilistic Knowledgr.
 http://dags.stanford.edu/PRMs/
 http://www.cs.berkeley.edu/~pasula/fopl/

Muitos e-mails para
Costa
[email protected] 46
11/08/2003
Rodrigo Cunha
– Cin / UFPE
