Modelos de Preferências
em Inteligência Artificial
CP-Nets
AULA 8
PGC 107 - Sistemas de Banco de Dados
Profa. Sandra de Amo
Pós-graduação em Ciência da Computação – UFU
2012-2
Preferências
Inteligência Artificial: interesse se concentra


formalismos para especificação de preferências
métodos de dedução de preferências
Banco de Dados: interesse se concentra em


Estender Algebra Relacional com operadores de
preferência
Projetar e implementar linguagens permitindo consultas
do tipo: “Quais os restaurantes que melhor atendem
minhas preferências de localização, facilidades de
estacionamento, menu variado e preço ?”
Problema – Fase 1

Fase da Elicitação das Preferências

Quantitativa: usuário fornece um rank para cada
objeto do banco de dados.
 infactível quando o banco de dados é grande.
 Depende da disponibilidade do usuário

Qualitativa: usuário especifica um conjunto de
“regras” de preferência.
Problema – Fase 2

Fase do Raciocínio – em caso de elicitação
quantitativa



Sistema automático assume certas
premissas extras que devem ser satisfeitas
pelo conceito de “preferência”
Sistema automático deduz a ordem de
preferência entre dois objetos quaisquer
Sistema automático calcula os k-melhores
objetos de acordo com as preferências do
usuário.
Exemplo – Filme(G, D)
Regras de Preferência:
1.
Prefiro comédias a dramas e suspense a comédias.
2.
Prefiro mais os dramas de Bergman do que os de Woody
Allen e mais os dramas de W.A do que os de Hitchcock.
3.
Prefiro mais as comédias de W.A do que as B. E mais as de
B. do que as de Hitchcock.
4.
Quanto a thrillers eu prefiro muito mais os de Hitchcock do
que os de WA e os de B. Entretanto se for preciso escolher
entre um thriller de WA e um de B., prefiro aqueles de B.
5.
Quanto aos filmes de Woody Allen, prefiro mais as
comédias do que os dramas.
Modelo: CP-Net
G
c>d
t >c
Dom(G) = {c,d,t}
Dom(D) = {w, b, h}
D
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
O que é uma CP-Net ?

Grafo = (V,E)



V : vértices = atributos do banco de dados
E : arestas – existe aresta de A para B se a
preferência entre os valores de B depende de
valores do atributo A.
Tabelas de preferência condicionais
associadas a cada vértice.

A ordem sobre os valores dos atributos é total.
Como uma CP-Net ordena tuplas

Premissas assumidas:

Semântica Ceteris Paribus:



R(A,B,C)
Uma regra F (que só diz respeito aos atributos A e B)
pode comparar dois objetos t1(x1,x2,x3) e
t2(y1,y2,y3), somente se x3 = y3
Ceteris paribus: Todos os valores de atributos que
não aparecem na regra devem ser iguais nos dois
objetos.
Ordem de Preferência é transitiva.
Exemplo 1
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exemplo 2
Jantar(Sopa, Vinho)
Dom(Sopa) = {p,l} Dom(Vinho) = {b, t}
1. Prefiro sopa de peixe a sopa de legumes.
2. Caso for sopa de peixe, prefiro vinho branco
para acompanhar.
3. Caso for sopa de legumes, prefiro vinho
tinto.
Exemplo 2 – continuação
S
p>l
(p,b)
(p,t)
(l,t)
W
p: b > t
l: t > b
(l,b)
Neste caso, todas as tuplas são comparáveis.
A CP-Net induz uma única ordem total sobre o
conjunto de todas as tuplas
Exercício
Preferências no vestuário: (Paletó, Calça, Camisa)
Dom(Paletó) = {branco, preto}
Dom(Calça) = {branco, preto}
Dom(Camisa) = {branco,vermelho}
1.
Prefiro paletó e calça pretos do que brancos.
2.
Se o paletó e calça são da mesma cor, então prefiro uma camisa
vermelha mais do que branca.
3.
Se o paletó e calça são de cores diferentes, então neste caso prefiro uma
camisa branca do que uma vermelha.
Pede-se:


Dar a CP-Net correspondente
Determinar a ordem (parcial) induzida pela CP-Net sobre todas as
combinações possiveis de meu vestuário.
CP-Net satisfatível

Uma CP-Net N é satisfatível se e somente se
existe uma ordem TOTAL entre os objetos
que é compatível com a ordem dos valores de
cada domínio de atributo X induzida pelos
valores dos atributos dos pais de X na CP-Net
e supondo a semântica ceteris paribus.
Exemplo
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exemplo: CP-Net não satisfatível
A
B
a : b > b’
a’ : b’ > b
c : a > a’
c’ : a’ > a
C
Tuplas em ordem de preferência
(a, b, c)
(a, b’,c)
(a’,b’,c)
b : c > c’
(a’,b,c)
b’ : c’ > c
(a’,b,c’)
(a, b, c’)
(a, b’,c’)
(a, b’,c)
Condição suficiente para ser
satisfatível (consistente)


Grafo é acíclico
Neste caso é possível construir ordem total
compatível com a CP-Net.
Aciclicidade não é necessária para
consistência da CP-Net
a : b > b’
a’: b’ > b
A
B
b : a > a’
b’: a’ > a
a’b
ab’
ab
a’b’
CP-Net é consistente,
embora o grafo seja
cíclico
a : b > b’
a’: b’ > b
A
B
b : a’ > a
b’: a > a’
ab
ab’
a’b
a’b’
CP-Net não é
consistente !
Como construir uma ordem total
quando o grafo é acíclico




Considera-se os atributos sem “pais”.
Ordena-se os valores destes atributos segundo
a ordem total ditada pelas tabelas destes
atributos.
Retira-se estes atributos.
Repete o processo para os atributos restantes,
para cada combinação de valores dos atributos
retirados.
Exemplo
G
D
c>d
t >c
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Ordem compatível com a CP-Net não é
única
(d,b)
(c,w)
(t,h)
(d,w)
(c,b)
(t,w)
(d,h)
(c,h)
(t,b)
É possível comparar (c,w) e (t,b) ?
É possivel comparar (c,h) e (d,b) ?
Exercicio
Construir duas ordens totais compatíveis com a CP-Net
A a > a’
B a: b > b’
a’: b’> b
C
b: c > c’
b’: c’> c
Discussão (1)
Ordem induzida por uma CP-Net =
Intersecção de todas as ordens totais compatíveis
= ordem parcial


Problemas de se encontrar uma ordem quando
o grafo é cíclico: CP-Net pode ser
inconsistente (não necessariamente, como já
vimos)
Tuplas Preferidas



Mesmo que existam diferentes ordens
compatíveis com a CP-Net, a tupla preferida
é única.
Tupla preferida pode ser construída
independentemente da particular ordem
compatível.
Esta tupla é preferida com relação a qualquer
ordem compatível com a CP-Net.
Algoritmo de construção da tupla
preferida
Seja X = (X1,X2, ..., Xn) os atributos da relação
 Considera-se os atributos sem pais na CP-Net.
 Para estes atributos considera-se seus
melhores valores.
 Retira-se estes atributos da CP-Net e repete-se
o processo para os demais atributos, levandose em conta os valores assumidos pelos
atributos retirados.
Exemplo
G
c>d
t >c
Gênero = thriller
Diretor = Hithcock
D
d: b > w
d: w > h
t: h > w
t: w > b
c: w > b
c: b > h
Tupla preferida = (t,h)
Exercício
Preferências no vestuário: (Paletó, Calça, Camisa)
Dom(Paletó) = {branco, preto}
Dom(Calça) = {branco, preto}
Dom(Camisa) = {branco,vermelho}
1.
Prefiro paletó e calça pretos do que brancos.
2.
Se o paletó e calça são da mesma cor, então prefiro uma camisa
vermelha mais do que branca.
3.
Se o paletó e calça são de cores diferentes, então neste caso prefiro uma
camisa branca do que uma vermelha.
Pede-se:

Qual o vestuário preferido ?
Discussão (2): ordem total versus
ordem parcial.


Pode-se definir CP-Net sem exigir ordem total
nos domínios dos atributos.
Neste caso, a tupla preferida não é única.
Discussão (3)
Tupla preferida pode existir mesmo se a CP-Net for inconsistente !
c: a > a’
c’: a’> a
abc
A
ab’c
B
ac: b > b’
a’c’:b> b’
a’c: b’> b
ac’:b’> b
ab’c’
C
b: c > c’
b’: c’> c
a’b’c
a’bc
a’b’c’
abc’
a’bc’
Tupla preferida = (a,b,c)
TCP-Net
TCP-Net = Tradeoffs-enhanced CP-Net
 Modelo de preferência mais expressivo
Exemplo: Vestuário (Paletó, Calça, Camisa)

1.
2.
3.
4.
Prefiro paletó e calça pretos do que brancos.
Se o paletó e calça são da mesma cor, então prefiro uma
camisa vermelha mais do que branca.
Se o paletó e calça são de cores diferentes, então neste caso
prefiro uma camisa branca do que uma vermelha.
Para mim, a cor do paletó é muito mais importante que a
cor da calça.
Modelo: TCP-Net
Preto > branco
P
C
Cam
Preto > branco
P=p, C=p: cam = v > cam=b
P=b, C=p: cam = b > cam=v
P=p, C=b: cam = b > cam=v
P=b, C=b: cam = v > cam=b
TCP-Net versus CP-Net
Segundo a CP-Net, a ordem entre
t1 = (P=preto, C=branca, Camisa= vermelha)
t2 = (P = branco, C=preta, Camisa = vermelha)
não pode ser deduzida diretamente da CP-Net.
 Na TCP-Net, esta ordem é clara: t1 > t2

O que é uma TCP-Net ?



É uma CP-Net (não se exige que as ordens de
cada atributo sejam totais)
Existem arcos de dominância absoluta entre
certos atributos
Existem arcos de dominância relativa entre
certos atributos. Tais arcos possuem como
labels


os atributos relativos
Tabelas que determinam a preferência relativa.
Exemplo
Preto > branco
P
Arco de importância absoluta
C
Preto > branco
C
C=p: P > Cam
C=b: Cam > P
Cam
C=p: cam = v > cam=b
C=b: cam = b > cam=v
t1= (paletó = b, calça = b, cam=b)
t2 = (paletó = p, calça = b, cam=v)
Arco de importância relativa
t1 > t2