Intelligenza Artificiale
Preferenze
Slides Intelligenza Artificiale,
Vincenzo Cutello
1
Outline






Preferenze razionali
Utilità
Denaro
Utilità multi-attibuto
Reti di decisione
Valore dell’informazione
Slides Intelligenza Artificiale,
Vincenzo Cutello
2
Preferenze
Un agente sceglie tra premi (A, B, etc.) e
lotterie, cioè, situazioni con premi incerti
A
p
Lotteria L = [p, A; (1-p), B]
L
Notazione :
A B
A è preferito a B
A B
A e B sono indifferen ti
A  B
B non è preferito ad A
Slides Intelligenza Artificiale,
Vincenzo Cutello
1-p
B
3
Preferenze razionali
Idea: le preferenze di un agente razionale devono obbedire a vincoli.
Preferenze razionali  comportamento descrivibile come
massimizzazione dell’utilità attesa
Vincoli :
Ordinabilità
(A
B)  (B
Transitività
(A B)  (B
A)  (A  B)
C)  (A
C)
Continuità
A
B
C  p [ p, A;1 p,C]  B
Sostituibilità
A  B  [ p, A;1 p,C]  [ p,B;1 p,C]
Monotonicità
A  B  ( p  q  [ p, A;1 p,B]  [q, A;1 q,B])
Decomponibilità
[ p, A;1 p,[q,B;1 q,C]]  [ p, A;(1 p)q,B;(1 p)(1 q)C]
Slides Intelligenza Artificiale,
Vincenzo Cutello
4
Preferenze razionali (cont.)
La violazione dei vincoli conduce a evidenti contraddizioni
Per esempio: un agente con preferenze intransitive può
essere indotto a dare via tutto il suo denaro
Se B  C , allora un agente che possiede C pagherebbe
(diciamo) 1 centesimo per ottenere B
Se A  B, allora un agente che possiede B pagherebbe
(diciamo) 1 centesimo per ottenere A
Se C  B, allora un agente che possiede A pagherebbe
(diciamo) 1 centesimo per ottenere C
Slides Intelligenza Artificiale,
Vincenzo Cutello
5
Massimizzando l’utilità attesa
Teorema (Ramsey, 1931; von Neumann e Morgenstern, 1944):
Date le preferenze soddisfacenti i vincoli esiste una funzione a valori reali
U tale che
U ( A)  U ( B)  A  B
U ([ p1 , S1;...; pn , S n ])  i piU ( Si )
Principio MEU: Scegliere l’azione che massimizza l’utilità attesa
Nota: un agente può essere interamente razionale (consistente con MEU)
senza mai rappresentare o manipolare utilità e probabilità
Es., una tabella predefinita per un giocatore perfetto di tris
Slides Intelligenza Artificiale,
Vincenzo Cutello
6
Utilità
L’utilità associa gli stati a numeri reali. Quali numeri ?
Approccio standard per stabilire l’utilità umana:
Comparare un dato stato A con una lotteria standard Lp che ha:
“miglior premio possibile” u^ con probabilità p
“peggiore catastrofe possibile” u^ con probabilità (1-p)
Aggiustare la probabilità della lotteria p fino a quando A è indifferente
rispetto a Lp
Continua come prima
0.999999
Pagare 30 €
è indifferente a
L
0.000001
Slides Intelligenza Artificiale,
Vincenzo Cutello
Morte istantanea
7
Scale di utilità
Utilità normalizzate: u^ = 1.0, u^ = 0.0
 Micromorts: un milionesimo della possibilità di
morire
– utile per la roulette russa, pagamento per ridurre i rischi
prodotti, etc.,
 QALYs: quality-adjusted life years
– Utile per decisioni mediche comportanti un rischio
sostanziale
Note: il comportamento è invariante per
trasformazioni lineari
U’(x) = k1U(x) + k2 dove k1 > 0
Slides Intelligenza Artificiale,
Vincenzo Cutello
8
Denaro
 Il denaro non si comporta come una funzione di utilità
 Data una lotteria L con valore monetario atteso di EMV(L),
solitamente U(L) < U(EMV(L)), cioè, le persone sono avverse
al rischio
 Curva di utilità: per quale probabilità p sono indifferente tra un
premio fisso x e una lotteria [p, € M; (1-p), € 0] per un grande
M?
 I dati si possono (o debbono estrapolare sperimentalmente)
Slides Intelligenza Artificiale,
Vincenzo Cutello
9
Paradosso di S. Pietroburgo



Vi viene chiesto di partecipare ad un gioco in cui una moneta viene
lanciata in aria sino a quando il risultato non è “testa”.
Se “testa” compare al lancio “n” , il giocatore vince € 2n .
Quanto paghereste per giocare ?

EMV(S.P.)=  P(Ti ) MV (Ti )  
i
i
1 i
2 
2i

Disposto a pagare qualunque cifra ? Assurdo. Bernoulli (1738) propose
di misurare l’utilità del denaro su scala logaritmica:
1
2 3 4
i
P
(
T
)
MV
(
T
)

log
2

1

   ...  2
i i
i 2i 2
i
4 8 16

Quindi per giocare un agente razionale paga sino a € 4 !
Slides Intelligenza Artificiale,
Vincenzo Cutello
10
Reti di decisione
 Aggiungere nodi di azioni e nodi di utilità alle
reti di credenza per prendere decisioni
razionali
 Algoritmo:
– for ogni valore del nodo di azione
 calcolare il valore atteso dell’utilità del nodo data
l’azione e la prova
– return l’azione MEU
Slides Intelligenza Artificiale,
Vincenzo Cutello
11
Utilità multiattributo
 Come possiamo gestire l’utilità di funzioni a più variabili
X1,…,Xn ?
 Esempio, per la costruzione di un aeroporto, parametri:
pericoli, rumori, costo di costruzione
– qual è U(Pericoli, Rumore, Costo) ?
 Come possono essere determinate le funzioni di utilità
complesse dal comportamento delle preferenze ?
 Idea 1: identificare le condizioni sotto le cui decisioni
possono essere fatte senza la completa identificazione di
U(x1,…,xn)
 Tipicamente definire attributi tale che U è monotona in
ogni parametro.
Slides Intelligenza Artificiale,
Vincenzo Cutello
12
Dominanza stretta
 La scelta B domina strettamente la scelta A se e solo se
– per ogni parametro i, Xi(B) ≥ Xi(A) (e quindi U(B) ≥ U (A) )
 La dominanza stretta si riscontra raramente nella pratica
Slides Intelligenza Artificiale,
Vincenzo Cutello
13
Dominanza stocastica
La distribuzi one p1 domina stocastica mente la distribuzi one p2 se e solo se
t
t
-

t  p1 ( x)dx   p2 ( x)dx
Se U è monotona in x, allora l' azione A1 , che produce una distribuzi one p1 ,
domina stocastica mente A 2 con distribuzi one p2 :




p1 ( x)U ( x)dx   p2 ( x)U ( x)dx

Caso multiattri buto : dominanza stocastica su tutti gli attributi  ottimale
Slides Intelligenza Artificiale,
Vincenzo Cutello
14
Dominanza stocastica
 La dominanza stocastica può essere spesso
determinata senza le distribuzioni esatte usando
ragionamenti qualitativi
 Es., i costi di costruzione aumentano con la
distanza dalla città. Quindi
– se S2, è più lontano dalla città rispetto a S1 ne deriva
che
– S1 domina stocasticamente S2 sui costi
Slides Intelligenza Artificiale,
Vincenzo Cutello
15
Struttura di preferenza: deterministico
X1 and X2 sono preferenziabilmente indipendenti (P.I.) da X3 se e solo se
la preferenza tra <x1,x2,x3> and <x’1,x’2,x’3> non dipende da x3
Es., <Rumore, Costi, Sicurezza>:
<20,000 soffrono, $4.6 miliardi, 0.06 morti/mpm> contro
<70,000 soffrono, $4.2 miliardi, 0.06 morti/mpm>
Teorema (Leontief, 1947): se ogni coppia di attributi è P.I. dal suo
complemento, allora ogni sottoinsieme di attributi è P.I. dal suo
complemento: P.I. mutuale
Teorema (Debreu, 1960): P.I. mutuale ⇒ esiste una funzione di
valutazione additiva :
V(S)=∑iVi(Xi(S))
Quindi bisogna determinare n funzioni con singolo attributo; spesso una buona
approssimazione
Slides Intelligenza Artificiale,
Vincenzo Cutello
16
Struttura di preferenza: Stocastica
 Abbiamo bisogno di considerare le preferenze sulle
lotterie:
– X è indipendente dall’utilità di Y se e solo se
– le preferenze sulle lotterie X non dipendono da y
 U.I. mutuale: ogni sottoinsieme è U.I. dal suo complemento
 Sotto tale ipotesi: esiste una funzione di utilità
moltiplicativa:
– U=k1U1+k2U2+k3U3+k1k2U1U2+k2k3U2U3+k3k1U3U1+k1k2k3U1U2U3
 Procedure di routine e pacchetti software per generare test
di preferenza per identificare varie famiglie canoniche di
funzioni di utilità
Slides Intelligenza Artificiale,
Vincenzo Cutello
17
Valore dell’informazione



Problema calcolare il valore di acquisire nuovi elementi decisionali.
Può essere fatto direttamente dalla rete di decisione
Esempio: comperare dei diritti petroliferi
–
–
–
–

Soluzione: calcolare il valore atteso dell’informazione =
–
–

n blocchi A1, …, An, solo in uno è presente il petrolio, valore stimato k
Probabilità a priori 1/n ognuno, mutuamente esclusivi
Il prezzo corrente di ogni blocco è allora k/n
Il consulente offre una perizia sul blocco A1. Costo della consulenza ?
valore atteso della miglior azione data l’informazione meno il
valore atteso della miglior azione senza l’informazione
Potremmo dire “petrolio in A1” o “niente petrolio in A1”, con probabilità rispettivamente
1/n e (n-1)/n,
–
–
–
[1/n * valore di “comprare A1” dato “petrolio in A1” +
(n-1)/n * valore di “comprare un altro lotto” dato “niente petrolio in A1” ] – 0
=
1 (n  1)
n 1 k
k
 k/n
n n
n n(n  1)
Slides Intelligenza Artificiale,
Vincenzo Cutello
18
Formula generale
Prova corrente E , miglior azione corrente 
Possibili esiti delle azioni Si , nuove prove potenziali E j
EU ( | E )  max i U ( Si ) P( Si | E ,  )
a
Supponiamo di conoscere E j  e jk , allora dovremmo scegliere  e jk
EU ( e jk | E , E j  e jk )  max i U ( Si ) P( Si | E ,  , E j  e jk )
a
E j è una variabile random il cui valore è attualmente sconosciut o
 dobbiamo calcolare il guadagno atteso su tutti i possibili valori :
VPI E ( E j )  (k P( E j  e jk | E ) EU ( ejk | E , E j  e jk ))  EU ( | E )
(VPI  valore della perfetta informazio ne)
Slides Intelligenza Artificiale,
Vincenzo Cutello
19
Proprietà del VPI
Non negatività in expectation, not post hoc
j , E VPI E ( E j )  0
Non additività considera, per esempio, di ottenere E j due volte
VPI E ( E j , Ek )  VPI E ( E j )  VPI E ( EK )
Indipenden za dall' ordine
VPI E ( E j , Ek )  VPI E ( E j )  VPI E , E j ( Ek )  VPI E ( Ek )  VPI E , Ek ( E j )
Nota : quando più di un elemento di prova può essere " gathered" ,
massimizza re VPI per ogni selezione non è sempre ottimale
" evidence - gathering" diventa un problema di decisione sequenzial e
Slides Intelligenza Artificiale,
Vincenzo Cutello
20