Sistemas
Especialistas
Probabilísticos
CIn- UFPE
Sistemas Especialistas Probabilísticos

Glauber Tomaz ([email protected])

Hendrik Teixeira Macedo ([email protected])

Mariana Lara Neves ([email protected])
CIn- UFPE
Conteúdo da apresentação

Combinando conhecimento e objetivos num ambiente de incerteza

A Teoria da Utilidade

Funções de utilidade

Funções de utilidade multivariada

Redes de decisão

Teoria do Valor da Informação
CIn- UFPE
Combinando a teoria da utilidade com a teoria da probabilidade
Criação de um “decision-theoric agent”

este agente toma decisões em contextos onde a
incerteza e os objetivos conflitantes deixariam
um agente lógico sem poder de decisão

usa uma função utilidade no processo de tomada
de decisão
CIn- UFPE
Função utilidade

fornece um número que expressa quão desejável
o estado é para o agente

indica as preferências do agente entre as várias
situações do mundo

é combinada com a probabilidade de ocorrência
dos estados resultantes, fornecendo a utilidade
esperada de cada ação
CIn- UFPE
Função utilidade



U(S)  utilidade do estado S
cada ação A poderá gerar diferentes estados Resulti(A)
antes da execução da ação A, o agente calcula a
probabilidade para cada estado resultante:
P(Resulti(A) | Do(A),E)
E  evidência do agente sobre o mundo
Do(A)  proposição de que A será executada no estado em
que o agente se encontra
CIn- UFPE
Função utilidade

a utilidade esperada de uma ação, dadas as
evidências do estado:
EU(A|E) = P(Resulti(A)|E,Do(A)).U(Resulti(A))

Princípio da máxima utilidade esperada (MEU): um
agente racional deverá escolher a ação que
maximize sua utilidade esperada
CIn- UFPE
Teoria da Utilidade


Loteria: cenários complexos onde os diferentes resultados obtidos são
“prêmios”, e que estes são determinados por acaso.
L= [p,A ; 1-p,B]
Notação para expressar preferências entre loterias:

A>B, AB e AB
CIn- UFPE
Axiomas da teoria da utilidade:

Ordenamento:
(A>B) V (B>A) V (AB)

Transitividade:
(A>B)  (B>C)  (A>C)

Continuidade:
A>B>C  p [p,A ; 1-p,C]  B
CIn- UFPE
Axiomas da teoria da utilidade:

Substituição:
AB  [p,A ; 1-p,C]  [p,B ; 1-p,C]

Monotonicidade:
A>B  (pq  [p,A; 1-p,B]  [q,A; 1-q,B]

Decomposição:
[p,A; 1-p,[q,B; 1-q,C]]  [p,A;(1-p)q,B; (1-p)(1-q),C]
CIn- UFPE
Axiomas da Utilidade:

Princípio da Utilidade:
U(A)>U(B)  A>B
U(A)=U(B)  A  B

Princípio da Máxima Utilidade Esperada (MEU):
U([p1,S1 ; ... ; pn,Sn]) =  piU(Si)
CIn- UFPE
Funções Utilidade

mapeia estados em valores reais

os agentes podem ter quaisquer preferências, contanto que elas
atendam aos axiomas da teoria

Utilidade do dinheiro:

preferência monotônica: o agente prefere possuir mais dinheiro quando
se lida com valores definidos
CIn- UFPE
Exemplo de um programa de TV
(solução 1)

opção 1: US$ 1,000,000

opção 2: tentar US$ 3,000,000 na moeda (cara ou coroa)

Cálculo do EMV (Valor monetário esperado)
EMV(rejeitar) = US$ 1,000,000
EMV(aceitar) = ½($0) + ½($3,000,000)
= US$ 1,500,000
Solução: aceitar!
CIn- UFPE
Exemplo de um programa de TV
(solução 2)

situação atual  U(Sk) = 5

opção 1  U(Sk+1,000,000) = 8

opção 2  U(Sk+3,000,000) = 10
EU(rejeitar) = U(Sk+1,000,000) = 8
EU(aceitar) = ½ U(Sk) + ½ U(Sk+3,000,000)
= 7.5
Solução: rejeitar!
CIn- UFPE
Paradoxo de St. Petersburg (Bernoulli - 1738)

Moeda : cara na n-ésima vez  $ 2n
Probabilidade = (½)n
EMV =  P(carai).MV(carai)
= (½)i.2i = 1 + 1 + ... = 

Bernoulli: a utilidade do dinheiro é medida em escala logarítmica
U(Sk+n) = log2n
EU =  P(carai).U(carai)
= (½)i.log22i = 1/2 + 2/4 + ... = 2
U(Sk+4) = log24 = 2
(US$4,00)
CIn- UFPE
Grayson (1960)
As preferências de Mr. Beard são consistentes com a função utilidade:
U(Sk+n) = -263.31 + 22.09.log(n + 150,000)
para (-$150,000 < n < $800,000)
CIn- UFPE
Grayson (1960)

Boa parte das pessoas tem uma função com forma côncava no lado
positivo de riqueza

risk-averse: U(SL) < U(SEMV(L))
(parte positiva do gráfico)

risk-seeking: (parte negativa do gráfico)

certainty equivalent: valor que o agente aceita no lugar de uma aposta

insurance premium: diferença entre EMV(L) e o certainty equivalent

risk-neutral: agente que possui uma curva linear para a função utilidade
CIn- UFPE
Julgamento humano

Teoria de decisão é normativa:

descreve como o agente deveria atuar.

As pessoas geralmente violam os axiomas da teoria da utilidade.
Tversky e Kahneman (1982) , Allais (1953)

A: 80% de chance de $4,000

B: 100% de chance de $3,000

C: 20% de chance de $4,000

D: 25% de chance de $3,000
CIn- UFPE
Julgamento humano

Resultados: B e C
U($0) = 0

0.8.U($4,000) < U($3,000)

0.2.U($4,000) > 0.25.U($3,000)

risk-averse em eventos com alta probabilidade de ganhos

risk-seeking em eventos de baixa probabilidade de ganho
CIn- UFPE
Escalas e valores da utilidade

“melhor prêmio possível”  U(S) = uT

“pior catástrofe possível”  U(S) = u
Utilidades normalizadas:

u = 0 e uT=1
resultados intermediário: [p, uT; (1-p), u]
Exemplos:

problemas médicos, de transporte e de meio-ambiente
CIn- UFPE
Escalas e valores da utilidade
Nos casos médicos e de segurança, temos:

u = morte imediata

exemplos: revisões em aviões, material dos carros, etc..
Valor de cada vida humana (análises médicas e de segurança):

micromort = chance de uma em um milhão de morte (US $20)

QUALY = equivalente a um ano em boa saúde, sem enfermidades
CIn- UFPE
Sistemas Especialistas sob Incertezas
Sistemas Especialistas
“...um programa de computador inteligente, que
usa uma base de conhecimento e inferências
para resolver
problemas
complexos,
que
requerem grande esforço intelectual humano.”
(Feigenbaum 82). Todos os organismos vivos são
especialistas em lidar com incertezas, do contrário
não sobreviveriam.
Problema: Instalar um reator nuclear.
Considerações: custo do terreno, distância às áreas
habitadas, risco de acidentes, etc.
Características do problema: vários atributos.
CIn- UFPE
Funções Utilidade Multivariadas
• Um agente com um conjunto de preferências tem uma
função utilidade do tipo
U(x1,..., xn) = f[f1(x1),..., fn(xn)]
onde f1(x1) é uma função “simples”.
• Quanto maior o valor do atributo, maior o valor da função
utilidade. Exemplo: quanto maior a AusênciaDeAcidentes,
melhor a solução.
CIn- UFPE
Dominância entre Atributos
• Um terreno B, para a construção do reator, custa menos e é
mais distante das áreas habitadas do que um terreno A.
X1
C
A
Região de
B domínio sobre
A
D
X2
Mas se os atributos forem incerteza ? ?
CIn- UFPE
Neste caso, precisamos introduzir o
conceito de dominância estocástica.
• Suponha que o custo do terreno A seja normalmente
distribuído em torno de R$ 3,7 milhões, com desvio
padrão de R$ 0,4 milhões; e o custo do terreno B seja
normalmente distribuído em torno de R$ 4,0 milhões,
com desvio padrão de R$ 0,35 milhões.
Professor, o que é
dominância estocástica ?
CIn- UFPE
Distribuição Acumulada e Dominância
• Matematicamente se duas ações A e B têm distribuição
de probabilidade p1(x) e p2(x) com relação ao atributo X,
então A domina estocasticamente B em X se
x
x  IR,
x
 p ( x' )dx'   p ( x' )dx'
1
-
2
-
CIn- UFPE
Estruturas de Preferências e Utilidade Multivariada
Preferências sem Incerteza
• Um conjunto de atributos {risco, custo do terreno, funcionários}
exibe independência preferencial mútua (IPM) se estes não são
correlacionados.
Teorema: Se os atributos X1,...,Xn são mutuamente
independentes, então a preferência do agente pode ser
descrita como a que vai maximizar a função
V (S )  Vi [ X i (S )]
i
onde cada Vi é a função valor do atributo Xi.
CIn- UFPE
Preferências com Incerteza
• Atributos {X1,..., Xn} têm independência de utilidade
sobre atributos {Y1,..., Yn}, se as preferências pelas
loterias em {X1,..., Xn} são independentes dos valores de
{Y1,..., Yn}.
• Atributos {X1,..., Xn} são mutuamente independentes
de utilidade (MIU), se cada subconjunto de {X1,..., Xn}
é independente de utilidade dos demais atributos do
conjunto.
• Para atributos MIU, a utilidade é multiplicativa.
U = k1U1 + k2U2 + k1 k2U1 U2.
CIn- UFPE
Rede de Decisão
Rede de Decisão = Rede Bayesiana + ações/utilidades
Local do reator
Risco de
Acidentes
Proximidade
à População
U
Funcionários
Custos
CIn- UFPE
Descrição da Rede de Decisão
• Nós de Chance (ovais): representam as variáveis aleatórias
como nas redes Bayesianas;
• Nós de Decisão (retângulos): representam os pontos onde o
agente que vai tomar a decisão pode escolher uma ação;
• Nós de Utilidade (losângulos): representam a função utilidade
do agente.
CIn- UFPE
Tabela de Ação-Utilidade
Local do reator
Risco de
Acidentes
U
Funcionários
• A tabela de ação-utilidade é uma versão compilada
da formulação original.
CIn- UFPE
Algoritmo de Avaliação de Redes de Decisão
1. Ajuste as variáveis de evidência para o estado atual.
2. Para cada possível valor do nó de decisão:
(a) Ajuste o nó para o valor de decisão dado;
(b) Calcule as probabilidades posteriores para os nós pais
do nó utilidade, usando um algoritmo inferência
probabilística padrão;
(c) Calcule a utilidade resultante da ação;
3. Retorne a ação com a maior função utilidade.
CIn- UFPE
Teoria do Valor da Informação
Quais as perguntas que devemos fazer sobre o problema?
• Precisamos saber como novas informações vão afetar a
função utilidade do agente.
Privatização ?
CIn- UFPE
Problema do Petróleo
• Uma multinacional está vai comprar os direitos de
explorar petróleo no Brasil. Existem 10 bacias onde a
exploração é permitida. Estudos revelaram que apenas
uma das bacia tem uma boa reserva de petróleo que vale
aproximadamente R$ 1 bilhão. O preço de cada bacia é
R$ 100 milhões.
Quanto a empresa deve pagar para obter a
informação da consultoria ?
CIn- UFPE
•Considere n = 10, C = R$ 1 bilhão e C/n = R$ 100 milhões.
• Com uma probabilidade 1/n, a consultoria mostra que a
bacia 3 tem petróleo. Neste caso, a companhia vai comprar o
bacia por C/n e terá um lucro de C - C/n = (n - 1)C/n .
• Com uma probabilidade (n - 1)/n, a consultoria mostra que
um bloco não tem petróleo. A probabilidade de encontrar
petróleo nas outras bacias é de 1/(n - 1). Assim, o lucro da
empresa é C/(n - 1) - C/n = C/[(n - 1)/n] .
• O lucro que a empresa terá devido a informação é
1 (n  1)C n  1
C
C




n
n
n
n(n  1) n
CIn- UFPE
Valor da Informação Perfeita (VIP)
• O conhecimento atual do agente é E. A função utilidade
esperada para a melhor ação a é dada por
(a | E )  max P[ Ri ( A) | E, F ( A)]U [ Ri ( A)]
A
i
onde A é uma ação do agente, Ri(A) é um estado de saída
possível, F(A) representa a execução da ação A e P(Ri | E, F ) é
a probabilidade condicional de Ri acontecer quando E e F
acontecem.
CIn- UFPE
• O novo valor de  após a nova evidência Ej é
(a E j | E, E j )  max P[ Ri ( A) | E, F ( A), E j ]U [ Ri ( A)]
A
i
• A evidência Ej é uma variável aleatória, portanto, devemos
tomar a média sobre todos os possíveis valores ejk de Ej.
• O valor da informação Ej é definido por
E ( E j )   P( E j  e jk | E)(a e jk | E, E j  e jk )  (a | E)
k
CIn- UFPE
Propriedades do Valor da Informação
• O valor da informação é não negativo
j  IN,E  IR E ( E j )  0.
• O valor da informação, em geral, é não aditivo
E ( E j , Ek )  E ( E j )  E ( Ek )
• O valor da informação independe da ordem
E ( E j , Ek )  E ( Ek , E j )
CIn- UFPE
Algoritmo de um Agente-Detetive Miope
função Agente-Detetive (percepção) retorna uma ação
estático: D - uma rede de decisão
integre a percepção em D
j
o valor que maximiza E(Ej) - C(Ej)
Se E(Ej) > C(Ej)
então retorne uma Requisição de Ej
do contrário retorne a melhor ação de D
• O agente miope calcula o valor da informação
assumindo que apenas uma evidência é adquirida.
CIn- UFPE
Construindo um Sistema Especialista sob Incerteza
• Determine o escopo do problema
• Desenhe a rede de conexões (topologia)
• Associe as probabilidades
• Associe as utilidades
• Forneça as evidências disponíveis
• Avalie o diagrama
• Obtenha outras evidências
• Realize uma análise sobre as repostas a pequenas variações
do sistema
CIn- UFPE
Biobliografia
• Russel, S. and Norvig, P., “Artificial Intelligence: A
Modern Approach”, Prentice-Hall (1995). Capítulo 16.
• Giarratano, J. and Riley, G., “Expert Systems:
Principles and Programming ”, International Thomson
Publishing, 2nd edition (1994). Capítulo 4.
• Waterman, D. A., “A Guide to Expert Systems ”,
Addison-Wesley (1986). Capítulos 12 e 25.
• Rich, E. e Knight, K., “ Inteligência Artificial ”,
Makron Books (1993). Capítulo 8.
CIn- UFPE