Modelos de Preferências em Inteligência Artificial

TCP-Nets

AULA 6

SISTEMAS DE BANCO DE DADOS

TCP-Net TCP-Net = Tradeoffs-enhanced CP-Net Modelo de preferência mais expressivoExemplo: Vestuário (Paletó, Calça, Camisa)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.4. Para mim, a cor do paletó é muito mais importante que a

cor da calça.

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

Modelo: TCP-Net

P C

Cam

Preto > brancoPreto > branco

P=p, C=p: cam = v > cam=bP=b, C=p: cam = b > cam=vP=p, C=b: cam = b > cam=vP=b, C=b: cam = v > cam=b

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

P C

Cam

Preto > branco

C=p: cam = v > cam=b C=b: cam = b > cam=v

C=p: P > Cam C=b: Cam > P

t1= (paletó = b, calça = b, cam=b)

t2 = (paletó = p, calça = b, cam=v)

t1 > t2

Preto > branco

C

Arco de importância relativa

Arco de importância absoluta

Exercicio: voo para os USA(D) Dia = {d1, d2}

(C) Companhia = {b (British Airways), k (KLM)}

(H) Hora da Partida = {m (de dia), n (a noite)}

(Co) Conexões = {co, c1}

(Cl) Classe = {e (economica), b (business) }

Dada a lista de regras de preferência descritas a seguir, especifique a TCP-Net correspondente.

O objetivo no final será determinar qual a combinação que melhor atende às minhas preferências.

Preferências expressas pelo usuário1. Como sou muito ocupado, prefiro partir um dia antes da conferência.2. Prefiro a British Airways pois minha bagagem já foi extraviada com a KML !3. Entre os voos partindo dois dias antes da conferência, prefiro um voo noturno, pois isto vai me permitir

trabalhar durante o dia do voo. Entre os voos partindo um dia antes, prefiro viajar de dia para poder passar a noite descansando no hotel

4. Em voos diurnos, estou acordado o tempo todo, e como sou fumante, prefiro fazer conexões. Em voos noturnos, entretanto, prefiro voos diretos.

5. Em voos noturnos, prefiro a classe economica, ja que não me incomodo onde vou dormir, e o preço compensa. Entretanto, num voo diurno já prefiro a business class pois, assim, posso apreciar melhor a boa comida, vinho, etc.

6. Para mim, a hora da partida é mais importante do que a companhia aérea.7. Num voo diurno da KLM, uma parada intermediária em Amsterdam é mais importante do que viajar de

classe executiva (acho que a classe executiva da KLM não tem uma boa taxa custo-beneficio, vale mais a pena poder visitar um cassino no aeroporto de Amsterdam.

8. Num voo noturno da BA, o fato do voo ser direto é mais importante para mim do que viajar na classe econômica. Estou disposto a pagar pela business class para não passar um minuto no aeroporto de Heathrow à noite !!

9. Num voo diurno da BA, a classe executiva é mais importante para mim do que poder fazer uma parada (já que é super dificil encontrar uma área de fumantes no aeroporto de Heathrow!)

Como uma TCP-Net ordena tuplas Constrói-se o grafo cujos vértices são todos as

tuplas possiveis, com os arcos produzidos pela CP-Net subjacente à TCP-Net.

Em seguida, atenta-se para os pares de tuplas que podem ser comparados levando-se em conta os arcos de importância absoluta.

Em seguida, atenta-se para os pares de tuplas que podem ser comparados levando-se em conta os arcos de importância relativa.

Exemplo Exemplo 4 pagina 57 do Capitulo

“Preferences”

ExercicioA TCP-net do exemplo da viagem para os USA

permite ordenar os seguintes pares de tuplas?

t1= (d1,k,m,co,e)t2 = (d1,k,m,c1,b)

t3 = (d2,k,n,co,e)t4 = (d2,b,m,co,e)

Ordem compatível com uma TCP-net

Uma ordem satisfaz uma TCP-Net N se:

1. É compatível com a CP-Net subjacente.

2. Satisfaz X > Y para cada arco de importância absoluta entre atributos X e Y.

3. Satisfaz todas as tabelas labels de arcos de importância relativa.

TCP-Net satisfatível Uma TCP-Net é satisfatível se existe uma

ordem (pode ser parcial) que lhe seja compatível.

Uma ordenação entre duas tuplas t1 > t2 é derivada da TCP-Net se é verificada em qualquer ordem compatível com a TCP-Net.

Exemplo Rever exemplo 4, pagina 57 do artigo

Preferences.

Grafo de Dependência de uma TCPNet G= (V,E)

Vértices do grafo = vértices da TCP-Net (A,B) é um arco de E se existe arco dirigido de A

para B na TCP-Net Para cada arco não-dirigido (A,B) da TCP-Net,

com label C, consideramos dois arcos dirigidos em G : (C,A) e (C,B)

Conjunto de grafos associados a uma TCP-NetSeja G o grafo de dependência associado a TCP-NetPara cada instanciação i dos atributos labels de arcos de

importância relativa, constrói-se um grafo Gi = (V, Ei) obtido da seguinte maneira:

1. Os vértices de Gi são os mesmos de G2. Toda aresta de G é aresta de Gi3. Insere-se arestas adicionais a Gi impostas pelas

tabelas de importância relativa, compatíveis com a instanciação i dos atributos label.

Exemplo

B,E

e > e’a: b > b’a’: b’>b

A

B

C D

E

b: d > d’b’: d’>d

a > a’

b: c > c’b’: c’ > c

b,e : C > Db’,e: D > Cb,e’: D > C

E

A

B

C D

Grafo de Dependência

Grafo (b,e)

E

A

B

C D

Grafo (b’,e’)

E

A

B

C D

Grafo (b’,e) = Grafo(b,e’)

Conjunto de grafos da TCP-Net

Condição suficiente para TCP-Net ser satisfatível TCP-Net deve ser condicionalmente acíclica

Todos os grafos de dependência são aciclicos Problema: testar a condição de

condicionalmente acíclica é difícil !

Dada uma TCP-Net binária N, o problema: existe um ciclo num dos grafos de N é NP-completo.

Exemplo

B,E

e > e’a: b > b’a’: b’>b

A

B

C D

E

b: d > d’b’: d’>d

a > a’

b: c > c’b’: c’ > c

b,e : C > Db’,e: D > Cb,e’: D > C

E

A

B

C D

Grafo (b,e)

E

A

B

C D

Grafo (b’,e’)

E

A

B

C D

Grafo (b’,e) = Grafo(b,e’)

Conjunto de grafos da TCP-NetTCP-Net é satisfatível

Algoritmo de construção das tuplas preferidas Considera-se a CP-Net subjacente a TCP-Net,

ignorando os arcos de importância absoluta e relativa.

Aplica-se o método de obtenção dos melhores objetos da CP-Net.

Tal método pode ser aplicado para todas as TCP-Nets para as quais a CP-Net subjacente é aciclica.

Exemplo

B,E

e > e’a: b > b’a’: b’>b

A

B

C D

E

b: d > d’b’: d’>d

a > a’

b,e : C > Db’,e: D > Cb,e’: D > C

e > e’a: b > b’a’: b’>b

A

B

C D

E

b: d > d’b’: d’>d

a > a’

b: c > c’b’: c’ > c

b: c > c’b’: c’ > c

TCP-Net

CP-Net correspondente

Tupla preferida: (a,b,c,d,e)

Exercicio Determinar a alternativa de voo que melhor

agrade ao usuário do exemplo da viagem aos USA.