CLP(BN): Constraint Logic
Programming with Bayes Net
Constraints
Rodrigo Cunha
Cin-UFPE
Roteiro
Introdução
 Contexto
 BN (Bayesian Networks)
 PRM (Probabilistic Relational Models)
 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 diferente de 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,
simulação estocástica, ..)
11/08/2003
Rodrigo Cunha – Cin / UFPE
3
Contexto
Lógica 1ª
Ordem
CLP(BN)
Ontológico
Prolog
Negação
Explícita e
Disjunção
Símbolo de
Funções
BD
Dedutivo
Recursão
PRM
BD Relacional
{0,1}
Lógica
Proposicional
Redes
Bayesianas
{0 ,1/2 ,1}
[0..1]
Variáveis
Universalmente
Quantificadas
Epistemológico
11/08/2003
Rodrigo Cunha – Cin / UFPE
4
CLP(BN)

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)
C/B
Estrutura
Ontológica Lógica
reg_grade (K, Grade) :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
Grade
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
Grade
Rodrigo Cunha – Cin / UFPE
11
Exemplo: CLP(BN) x PRM
M
Professor
Teaching-Ability
Popularity
Student
M
1
Course
Intelligence
1
Rating
M
Registration
Ranking
M
Difficulty
AVG
Satisfaction
AVG
Grade
11/08/2003
Rodrigo Cunha – Cin / UFPE
12
Expressar BD de PRM como fatos
CLP(BN)
Course
Professor
Key
Sue
David
Popularity Ability
h
l
h
l
Sam
Terry
11/08/2003
Professo
r
cs1
cs2
Sue
David
Rating Difficult
y
h
h
h
l
Registration
Student
Key
Key
Intelligenc
e
Rank
m
h
m
h
Key
Course
Studen
t
Satisfaction
Grade
r1
r2
r3
cs1
cs2
cs1
Sam
Sam
Terry
h
l
h
a
c
b
Rodrigo Cunha – Cin / UFPE
13
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
14
Expressar BD de PRM como fatos
CLP(BN)
Professor
Key
Sue
Davi
d
Key
Popularit
y
h
l
Key
Sue
Davi
d
Student
Intelligenc
e
Sam
Terry
Ability
Key
m
h
h
l
Key
Professo
r
cs1
cs2
Sue
David
Ran
k
Key
Cours
e
Ke
y
Studen
t
Ke
y
Satisfaction
Key
Grad
e
r1
r2
r3
cs1
cs2
cs1
r1
r2
r3
Sam
Sam
Terry
r1
r2
r3
h
l
h
r1
r2
r3
a
c
b
11/08/2003
Rodrigo Cunha – Cin / UFPE
Ratin
g
Course cs1
cs2
Key Difficult
y
cs1
cs2
Sam
m
Terr
h
yRegistration
Key
h
h
h
l
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 uma 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: CLP(BN) x PRM
M
Professor
Teaching-Ability
Popularity
Student
M
Course
1
Rating
Intelligence
1
M
Difficulty
AVG
reg(Key, Student)
reg(Key,Course)
course(Key,Professor)
11/08/2003
Registration
Ranking
M
Satisfaction
AVG
Grade
Rodrigo Cunha – Cin / UFPE
19
Exemplo:
Professor
Key
Course
Popularity
Ability
h
l
h
l
Sue
David
Key
Sam
Terry
Student
Intelligence
Rank
l
h
m
h
reg(Key, Student)
reg(Key,Course)
course(Key,Professor)
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
20
Estágio de Agregação



Este estágio é para variáveis que tem
múltiplas ligações.
Podemos ter todas as ligações de Rating
através do predicado built-in findall.
Por exemplo:
course_rating (K, Rating) :findall (Sats, (reg_course(R,K) , (reg_sat(R,Stats))),
avg(Sats, AvS).
11/08/2003
Rodrigo Cunha – Cin / UFPE
21
Estágio CPT
11/08/2003
Rodrigo Cunha – Cin / UFPE
22
Estágio CPT
reg_grade(K, Grade) :
reg_course(K,C), reg_student(K,S),
course_diff (C,D), student_intell
(S,I).
{Grade = grade(K) 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
23
Neste caso D e I só podem assumir dois valores.
Professor Clauses
prof_abil (K, A) :{A = abil(K) with p( [h,l],[ 0.7,0.3]
}.
A
prof_pop (K, P):prof_abil (K,A),
P = { pop(K) with
A
p([h,m,l] , ( [0.9, 0.2,
0.1, 0.6,
0.0, 0.2, [A])
P
11/08/2003
Rodrigo Cunha – Cin / UFPE
24
Exemplo: CLP(BN) x PRM
M
Professor
Teaching-Ability
Popularity
Student
M
1
Course
Intelligence
1
Rating
M
Registration
Ranking
M
Difficulty
AVG
Satisfaction
AVG
Grade
11/08/2003
Rodrigo Cunha – Cin / UFPE
25
Registration Clauses
reg_grade(K, Grade) :
reg_course(K,C), reg_student(K,S),
course_diff (C,D), student_intell
(S,I),
{Grade = grade(K) with p(
[a,b,c],[ 0.5, 0.1, 0.8, 0.3
D
I
0.4, 0.5, 0.1,
0.6,
0.1, 0.4, 0.1, 0.1] ,
Grade
[D,I])}.
11/08/2003
Rodrigo Cunha – Cin / UFPE
26
Course Clauses
course_rating (K, Rating) :findall (Sats, (reg_course(R,K) , (reg_sat(R,S))),
Rating = { rating(K) with p([h,l] , ( [0.9, 0.2,
0.1, 0.8] ,
avg(Sats,
AvS
AvS))
Rating
11/08/2003
Rodrigo Cunha – Cin / UFPE
27
Avaliação (Evaluation)

Uma consulta em CLP(BN)


Uma ou mais provas construídas através de
resolução


uma consulta Prolog, conjunção de literais
positivos.
cada passo de resolução termos de diferentes
cláusulas devem ser unificados.
Construir uma grande rede bayesiana

todos as pequenas redes de bayes que foram
unificadas durante a fase de resolução.
11/08/2003
Rodrigo Cunha – Cin / UFPE
28
reg_grade (K, Grade):reg_course (K,C),
reg_student (K,S),
course_diff (C,D),
student_intell (S,I).
D
Grade
reg_sat (K, S):reg_course (K,C),
course_prof (C,P),
prof_abil (P,A),
reg_grade (K,Grade’).
reg_sat (K, S):reg_course (K,C),
course_prof (C,P),
prof_abil (P,A),
reg_course (K,C),
reg_student (K,S),
course_diff (C,D),
student_intell (S,I).
I
Grade’
A
S
D
I
Grade
A
S
Avaliação(Evaluation):
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
30
Consultas
?- professor_ability(X,A).
X = sue,
A = [ 0.7 , 0.3 ] => [ h , l ] ? ;
X = david,
A = [ 0.8 , 0.2 ] => [ h , l ] ? ;
?- professor_popularity (X , P ) , professor_ability ( X , h ).
X = sue,
P = [ 0.9 , 0.1 , 0.0] => [ h , m , l ] ?
?- professor_popularity (david , P ) , professor_ability ( david ,
h ).
P = [ 0.9 , 0.1 , 0.0] => [ h , m , l ] ?
11/08/2003
Rodrigo Cunha – Cin / UFPE
31
Consultas
?- course_rating ( cs1 , R ).
R = [ 0.6 , 0.4 ] => [ h , l ] ?
?- course_rating ( cs1 , R ), course_professor ( cs1 , P ),
professor_ability (P , h ).
P = sue,
R = [ 0.7 , 0.3] => [ h , l ] ? ;
11/08/2003
Rodrigo Cunha – Cin / UFPE
32
Restrições
Probabilísticas
Apenas restrições de variáveis discretas,



CLP(BN) através de restrições
contínuas.(Trabalho Atual).
Distribuições de Probabilidade Contínuas:
 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)?





Incorporar probabilidade na lógica de
primeira ordem.
Ajudar a entender melhor o
relacionamento entre PRMs e probabilistic
logic.
CLP(BN) pode aprender usando ILP
Recursão
Símbolo de Funções.
11/08/2003
Rodrigo Cunha – Cin / UFPE
34
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
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
