Incertezza - probabilità, regola di Bayes e indipendenza condizionata

Un agente reale vede solo una parte del mondo (Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →): osservabilità parziale, azioni non deterministiche, avversari. La logica (Agenti logici e logica proposizionale - inferenza e risoluzioneAgenti basati sulla conoscenza (KB, Tell e Ask), mondo del Wumpus come banco di prova, sintassi e semantica della logica proposizionale, conseguenza logica, equivalenze, inferenza per model checking (7 simboli, 128 modelli, 3 modelli della KB) e per risoluzione (CNF, regola di risoluzione, dimostrazione per assurdo). Limite: poca espressività, da cui la logica del primo ordine.Agenti logici e logica proposizionale - inferenza e risoluzione →) obbliga a regole sempre vere: "$\text{MalDiDenti}\Rightarrow\text{Carie}$" è falsa, e per salvarla servirebbe una lista infinita di cause ($\text{Carie}\lor\text{Gengivite}\lor\text{Ascesso}\lor\dots$). Le slide indicano tre motivi per cui questo fallisce in domini grandi come la diagnosi medica:

• pigrizia: elencare tutte le cause e i sintomi costa troppo;
• ignoranza teorica: la medicina non ha una teoria completa;
• ignoranza pratica: anche conoscendo le regole, non tutti gli esami sono stati fatti.

La probabilità riassume questa incertezza in un grado di credenza su ogni proposizione. Non dice che il mondo è casuale: dice quanto l'agente è sicuro, date le informazioni che ha.

Teoria delle decisioni

Definizione. Teoria delle decisioni (decision theory) = teoria della probabilità + teoria dell'utilità. Ogni stato ha un'utilità (quanto è desiderabile). Un agente è razionale se sceglie l'azione con utilità attesa massima, cioè la media delle utilità dei possibili esiti pesata con le loro probabilità: $EU(a)=\sum_s P(s\mid a)\,U(s)$.

Esempio (numeri inventati). Scorciatoia buia: con probabilità $0{,}9$ si arriva presto (utilità $8$), con probabilità $0{,}1$ si viene aggrediti (utilità $-50$). Strada illuminata e più lunga: utilità $4$ sicura. $EU(\text{scorciatoia})=0{,}9\cdot 8+0{,}1\cdot(-50)=2{,}2<4=EU(\text{strada})$: si sceglie la strada illuminata, anche se la scorciatoia è quasi sempre meglio. La scelta sequenziale con utilità e probabilità è sviluppata in Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iterationUn MDP (processo decisionale di Markov) modella un problema decisionale sequenziale in ambiente stocastico e completamente osservabile con stati S, azioni A(s), modello di transizione P(s'|s,a) e ricompensa R(s,a,s'). La soluzione è una politica pi(s). L'utilità U(s) è il ritorno scontato atteso e soddisfa l'equazione di Bellman U(s)=max_a sum_s' P(s'|s,a)[R(s,a,s')+gamma U(s')]; la quantità tra parentesi quadre sommata su s' è la funzione azione-utilità Q(s,a). Value iteration parte da U=0, applica Bellman a tutti gli stati insieme e si ferma quando delta <= eps(1-gamma)/gamma; la politica è argmax_a Q(s,a). Policy iteration alterna valutazione (sistema lineare, senza max) e miglioramento greedy, e termina quando la politica non cambia. Nei POMDP lo stato è nascosto: si lavora sullo stato di credenza b aggiornato come nel filtraggio, b'(s')=alpha P(e|s') sum_s P(s'|s,a)b(s).Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iteration →; il valor medio è quello di Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →.

Notazione

• Una variabile aleatoria (random variable) rappresenta una proprietà del mondo (esito di un dado, $\text{Weather}$). Qui sono quasi sempre discrete. I valori si scrivono minuscoli: $\text{Weather}=\text{sun}$ o, per le booleane, $a$ per $A=\text{true}$ e $\neg a$ per $A=\text{false}$.
• Un modello probabilistico assegna $P(\omega)$ a ogni mondo possibile $\omega$ con $0\le P(\omega)\le 1$ e $\sum_\omega P(\omega)=1$. Un evento è un insieme di mondi: $P(\phi)=\sum_{\omega\models\phi}P(\omega)$.
• La distribuzione $\mathbf P(X)$ (P maiuscola in grassetto) è il vettore delle probabilità di tutti i valori di $X$: $\mathbf P(\text{Weather})=\langle 0{,}6;\ 0{,}1;\ 0{,}29;\ 0{,}01\rangle$ per sole, pioggia, nuvole, neve. $P(x)$ è invece un singolo numero.
• Probabilità a priori (prior, non condizionata) $P(a)$: credenza senza altre informazioni. A posteriori (posterior, condizionata) $P(a\mid b)=\dfrac{P(a,b)}{P(b)}$ per $P(b)>0$. Il calcolo rigoroso è in Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →.
• Per variabili continue la distribuzione diventa una densità; nel corso si usano variabili discrete.

Esempio (due dadi). $P(D_1+D_2=7\mid D_1=3)$: i risultati sono $36$, ma solo $(3,4)$ soddisfa insieme $D_1=3$ e somma $7$, quindi $\dfrac{1/36}{1/6}=\dfrac16$. Altro caso: $P(D_1+D_2<7\mid D_1=D_2)$. Le coppie con dadi uguali sono $6$ su $36$; quelle con somma minore di $7$ sono $(1,1),(2,2),(3,3)$, cioè $3$ su $36$; il risultato è $\dfrac{3/36}{6/36}=\dfrac12$.

Legge delle probabilità totali

Teorema. Se $b_1,\dots,b_N$ sono eventi mutuamente esclusivi ed esaustivi, $P(a)=\sum_k P(a,b_k)=\sum_k P(a\mid b_k)P(b_k)$.

Serve a sommare via ciò che non interessa (marginalizzare): $P(D_1=1)=\sum_{d=1}^{6}P(D_1=1,D_2=d)=6\cdot\frac1{36}=\frac16$. La formulazione completa, con la partizione dello spazio, è in Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →.

Inferenza dalla distribuzione congiunta completa

La congiunta completa $\mathbf P(X_1,\dots,X_n)$ elenca la probabilità di ogni assegnazione. Con tre booleane (carie, mal di denti, uncino che si impiglia) sono $2^3=8$ numeri:

(Le otto probabilità sommano a $1$.) Da questa tabella si ricava qualsiasi probabilità sommando le celle in cui la proposizione è vera:

• $P(\text{toothache})=0{,}108+0{,}012+0{,}016+0{,}064=0{,}2$ (le quattro celle con $\text{toothache}$: due nella riga $\text{cavity}$ e due nella riga $\neg\text{cavity}$);
• $P(\text{cavity}\lor\text{toothache})=0{,}108+0{,}012+0{,}072+0{,}008+0{,}016+0{,}064=0{,}28$ (tutte le celle tranne le due con $\neg\text{cavity},\neg\text{toothache}$; equivale a $1-0{,}144-0{,}576$);
• $P(\neg\text{cavity}\mid\text{toothache})=\dfrac{0{,}016+0{,}064}{0{,}2}=0{,}4$.

Normalizzazione

Calcolare il denominatore $P(\text{toothache})$ ogni volta è inutile: i due valori di $\mathbf P(\text{Cavity}\mid\text{toothache})$ hanno lo stesso denominatore e devono sommare a $1$. Si scrive $$\mathbf P(\text{Cavity}\mid\text{toothache})=\alpha\,\mathbf P(\text{Cavity},\text{toothache}),\qquad \alpha=\frac1{P(\text{toothache})}$$ e si calcola il vettore non normalizzato, poi lo si divide per la somma delle sue componenti. Qui la variabile nascosta $\text{Catch}$ si somma via: $$\alpha\,[\langle0{,}108;\,0{,}016\rangle+\langle0{,}012;\,0{,}064\rangle]=\alpha\,\langle0{,}12;\,0{,}08\rangle,\quad\alpha=\frac1{0{,}12+0{,}08}=5\ \Rightarrow\ \langle0{,}6;\ 0{,}4\rangle.$$

Formula (inferenza per marginalizzazione). Sia $\mathbf X$ l'insieme di tutte le variabili, $\mathbf Y$ le variabili di interrogazione (query), $\mathbf E$ le variabili di evidenza con valori osservati $\mathbf e$ e $\mathbf H=\mathbf X-\mathbf Y-\mathbf E$ le variabili nascoste. Allora $$\mathbf P(\mathbf Y\mid\mathbf e)=\alpha\,\mathbf P(\mathbf Y,\mathbf e)=\alpha\sum_{\mathbf h}\mathbf P(\mathbf Y,\mathbf e,\mathbf h).$$

Aggiungendo anche l'evidenza $\text{catch}$ si ottiene $\alpha\langle0{,}108;\,0{,}016\rangle=\langle0{,}871;\ 0{,}129\rangle$: una seconda evidenza sposta la credenza da $0{,}6$ a $0{,}871$.

Limite. La tabella ha $a^n$ celle ($a$ = numero di valori, $n$ = numero di variabili): crescita esponenziale, troppi numeri da stimare e da memorizzare. La soluzione è l'indipendenza, vista sotto, e le Reti bayesiane - semantica, indipendenze e inferenza esattaUna rete bayesiana è un grafo diretto aciclico (DAG) con una variabile per nodo e una tabella delle probabilità condizionate (CPT) $P(X_i\mid\text{Parents}(X_i))$ per nodo; rappresenta la congiunta come prodotto $P(x_1,\dots,x_n)=\prod_i P(x_i\mid\text{parents}(X_i))$, con molti meno numeri della tabella completa (rete dell'allarme: 10 contro 31). Tre strutture elementari: catena $X\to Y\to Z$ e fork $Y\leftarrow X\to Z$ (estremi indipendenti dato il centro), collider $X\to Z\leftarrow Y$ (indipendenti, ma dipendenti se si osserva $Z$ o un suo discendente). Modelli causali (genitori = cause) danno reti più piccole. Inferenza esatta per enumerazione: $\mathbf P(X\mid\mathbf e)=\alpha\sum_{\mathbf y}\mathbf P(X,\mathbf e,\mathbf y)$ calcolata come somma di prodotti, in profondità e da sinistra a destra; per l'allarme $\mathbf P(B\mid j,m)=\langle0{,}284;\ 0{,}716\rangle$. Molti prodotti si ripetono: l'eliminazione di variabili li salva come fattori e li riusa.Reti bayesiane - semantica, indipendenze e inferenza esatta →.

Regola del prodotto e regola di Bayes

Dalla definizione di condizionata: $P(a,b)=P(a\mid b)P(b)=P(b\mid a)P(a)$. Uguagliando:

Teorema (regola di Bayes). $$P(b\mid a)=\frac{P(a\mid b)\,P(b)}{P(a)}\qquad\Longleftrightarrow\qquad \mathbf P(\text{causa}\mid\text{effetto})=\frac{\mathbf P(\text{effetto}\mid\text{causa})\,\mathbf P(\text{causa})}{P(\text{effetto})}.$$

$P(\text{effetto}\mid\text{causa})$ è la direzione causale: di solito è stabile e facile da stimare (la frequenza dei sintomi in chi ha la malattia). $P(\text{causa}\mid\text{effetto})$ è la direzione diagnostica, quella che serve al medico. Bayes converte la prima nella seconda. Dimostrazione e uso in Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →.

Esempio (meningite). $P(\text{rigidità}\mid\text{meningite})=0{,}7$, $P(\text{meningite})=1/50000$, $P(\text{rigidità})=0{,}01$. $$P(\text{meningite}\mid\text{rigidità})=\frac{0{,}7\cdot\frac1{50000}}{0{,}01}=0{,}0014.$$ Solo lo $0{,}14\%$ di chi ha il collo rigido ha la meningite: il sintomo è tipico della malattia, ma la rigidità ha un prior $0{,}01$ enormemente più grande di quello della malattia.

Esempio (mammografia). $P(c)=1/700\approx0{,}14\%$ (cancro in un anno a 40 anni), sensibilità $P(m\mid c)=0{,}73$, falsi positivi $P(m\mid\neg c)=0{,}12$. Il denominatore si ottiene con le probabilità totali: $$P(m)=0{,}73\cdot\tfrac1{700}+0{,}12\cdot\tfrac{699}{700}=0{,}001043+0{,}119829=0{,}120871\approx12{,}1\%,$$ $$P(c\mid m)=\frac{0{,}73}{0{,}120871}\cdot\frac1{700}=0{,}00863\approx0{,}9\%.$$ Il test positivo porta la credenza da $0{,}14\%$ a $0{,}9\%$: è sei volte più alta, ma resta bassa perché i sani sono $699$ volte più numerosi e il $12\%$ di essi dà un falso positivo.

L'effetto del prior si vede facendo variare $P(c)=x$: $P(c\mid m)=\dfrac{0{,}73x}{0{,}73x+0{,}12(1-x)}$.

Indipendenza e indipendenza condizionata

Definizione (indipendenza). $a$ e $b$ sono indipendenti se $P(a\mid b)=P(a)$, o equivalentemente $P(b\mid a)=P(b)$, o $P(a,b)=P(a)P(b)$. Vedi Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →.

Un'indipendenza permette di scomporre la congiunta: il meteo non dipende dai denti, quindi $$\mathbf P(\text{Toothache},\text{Catch},\text{Cavity},\text{Weather})=\mathbf P(\text{Weather})\,\mathbf P(\text{Toothache},\text{Catch},\text{Cavity}),$$ cioè, con $\text{Weather}$ a due valori, $16$ numeri diventano $2+8=10$. Le indipendenze totali però sono rare; quelle condizionate sono molto più comuni.

Definizione (indipendenza condizionata). $a$ e $b$ sono condizionalmente indipendenti dato $c$ se $P(a\mid b,c)=P(a\mid c)$, o equivalentemente $P(b\mid a,c)=P(b\mid c)$, o $P(a,b\mid c)=P(a\mid c)P(b\mid c)$. Vedi Eventi indipendenti e indipendenza condizionataA e B sono indipendenti se P(AB) = P(A)P(B), cioè (se P(B) > 0) P(A | B) = P(A): sapere B non cambia la probabilità di A. Se A, B sono indipendenti lo sono anche A e Bᶜ. Tre eventi sono indipendenti se lo sono a coppie E P(ABC) = P(A)P(B)P(C): l'indipendenza a coppie non basta. Prove ripetute indipendenti: le probabilità si moltiplicano. Indipendenza condizionata a F: P(AB | F) = P(A | F)P(B | F); non implica l'indipendenza (due lanci della stessa moneta scelta a caso). Eventi disgiunti con probabilità positive non sono mai indipendenti.Eventi indipendenti e indipendenza condizionata →.

Esempio (allarme antincendio). $P(\text{allarme}\mid\text{fuoco},\text{fumo})=P(\text{allarme}\mid\text{fumo})$: se si sa che c'è fumo, sapere che c'è fuoco non aggiunge nulla, perché l'allarme reagisce al fumo.

Verifica sulla tabella del dentista. Dato $\text{cavity}$, $\text{toothache}$ e $\text{catch}$ sono indipendenti. Le probabilità condizionate si ottengono dividendo la riga per $P(\text{cavity})=0{,}2$: $P(t,ca\mid cav)=\frac{0{,}108}{0{,}2}=0{,}54$, $P(t\mid cav)=\frac{0{,}108+0{,}012}{0{,}2}=0{,}6$, $P(ca\mid cav)=\frac{0{,}108+0{,}072}{0{,}2}=0{,}9$ e $0{,}6\cdot0{,}9=0{,}54$ ✓. Per $\neg cav$ ($P=0{,}8$): $0{,}016/0{,}8=0{,}02=0{,}1\cdot0{,}2$ ✓. Quindi la congiunta si scrive $\mathbf P(\text{Cavity})\,\mathbf P(\text{Toothache}\mid\text{Cavity})\,\mathbf P(\text{Catch}\mid\text{Cavity})$: $1+2+2=5$ numeri invece di $7$.

Questa è la struttura del classificatore bayesiano ingenuo (naive Bayes): una causa e molti effetti indipendenti dato la causa. È quella dell'esercizio Esercizio - Diagnosi COVID con la regola di Bayes (laboratorio 5): con tre sintomi $P(d\mid f,c,l)=\dfrac{P(f\mid d)P(c\mid d)P(l\mid d)P(d)}{\sum_x P(f\mid x)P(c\mid x)P(l\mid x)P(x)}\approx0{,}968$. Le reti bayesiane generalizzano l'idea a qualsiasi grafo di dipendenze.

Domande d'esame

1. Con $P(\text{toothache})=0{,}2$ e $P(\neg\text{cavity},\text{toothache})=0{,}08$, quanto vale $P(\neg\text{cavity}\mid\text{toothache})$? $0{,}08/0{,}2=0{,}4$.
2. Una malattia ha prior $0{,}01$, un test ha sensibilità $0{,}9$ e falsi positivi $0{,}09$. Qual è la probabilità di malattia dato il test positivo? $P(m)=0{,}9\cdot0{,}01+0{,}09\cdot0{,}99=0{,}0981$; $P(d\mid m)=0{,}009/0{,}0981=0{,}0917\approx9\%$.
3. Cosa significa che $a$ e $b$ sono condizionalmente indipendenti dato $c$, e perché serve? $P(a,b\mid c)=P(a\mid c)P(b\mid c)$: noto $c$, $b$ non dà informazione su $a$. Permette di scomporre la congiunta in tabelle piccole, evitando la crescita esponenziale.
4. Cos'è la costante $\alpha$ nell'inferenza per marginalizzazione? $\alpha=1/P(\mathbf e)$: normalizza il vettore $\mathbf P(\mathbf Y,\mathbf e)$ affinché sommi a $1$. Si trova sommando le componenti, senza calcolare $P(\mathbf e)$ a parte.