Reti bayesiane - semantica, indipendenze e inferenza esatta

La congiunta completa (Incertezza - probabilità, regola di Bayes e indipendenza condizionataUn agente con osservazioni parziali non può usare regole logiche rigide ("mal di denti implica carie" è falso): usa la probabilità come grado di credenza e, con la teoria dell'utilità, sceglie l'azione con utilità attesa massima. Strumenti: distribuzione congiunta completa (tabella di $2^n$ valori), marginalizzazione $P(Y\mid e)=\alpha\sum_h P(Y,e,h)$ con costante di normalizzazione $\alpha=1/P(e)$, regola del prodotto $P(a,b)=P(a\mid b)P(b)$, regola di Bayes $P(\text{causa}\mid\text{effetto})=\frac{P(\text{effetto}\mid\text{causa})P(\text{causa})}{P(\text{effetto})}$ e indipendenza condizionata $P(a,b\mid c)=P(a\mid c)P(b\mid c)$, che permette di scomporre la congiunta in tabelle più piccole. Un test con sensibilità 73% e falsi positivi 12% su una malattia con prior 1/700 dà una probabilità a posteriori di appena 0,9%.Incertezza - probabilità, regola di Bayes e indipendenza condizionata →) risponde a qualsiasi domanda, ma ha $a^n$ numeri ($a$ = valori per variabile, $n$ = variabili): per tre booleane $2^3=8$ valori (in realtà $7$: l'ultimo si ricava dalla somma $=1$), per trenta più di un miliardo. Non si sa dove trovare i numeri e dove metterli. Le reti bayesiane (Bayesian networks, dette anche belief networks, modelli grafici probabilistici) la scompongono sfruttando le indipendenze condizionate.

Scomposizione della congiunta

Regola della catena. Per qualsiasi ordine delle variabili, per la regola del prodotto: $$P(x_1,\dots,x_n)=P(x_n\mid x_{n-1},\dots,x_1)\,P(x_{n-1}\mid x_{n-2},\dots,x_1)\cdots P(x_2\mid x_1)\,P(x_1)=\prod_{i}P(x_i\mid x_{i-1},\dots,x_1).$$

Se ogni $X_i$ è indipendente da tutti i predecessori tranne un sottoinsieme $\text{Parents}(X_i)\subseteq\{X_1,\dots,X_{i-1}\}$ (i suoi genitori), nella catena rimangono solo i genitori:

Definizione (scomposizione in prodotto). $$P(x_1,\dots,x_n)=\prod_{i=1}^n P\big(x_i\mid \text{parents}(X_i)\big).$$

Esempio. $P(X_1,X_2,X_3)=P(X_3\mid X_1,X_2)P(X_2\mid X_1)P(X_1)$. Se $X_3$ è condizionalmente indipendente da $X_1$ dato $X_2$, diventa $P(X_3\mid X_2)P(X_2\mid X_1)P(X_1)$: $X_2$ è genitore di $X_3$, $X_1$ di $X_2$, $X_1$ non ha genitori.

Definizione (rete bayesiana). Un DAG (grafo diretto senza cicli) in cui:

• ogni nodo è una variabile aleatoria;
• un arco $X\to Y$ dice che $X$ è genitore di $Y$ (di solito: $X$ è una causa di $Y$);
• ogni nodo ha una tabella delle probabilità condizionate (conditional probability table, CPT) $\mathbf P(X_i\mid\text{Parents}(X_i))$; un nodo senza genitori ha una distribuzione a priori.

La rete rappresenta la congiunta come prodotto delle CPT. Topologia + CPT = rappresentazione compatta, di solito semplice da costruire anche per non esperti.

Esempio. Nella rete con archi $X\to Z$, $Y\to Z$, $Z\to W$ la congiunta è $\mathbf P(W,Z,X,Y)=\mathbf P(W\mid Z)\,\mathbf P(Z\mid X,Y)\,\mathbf P(X)\,\mathbf P(Y)$: ogni fattore è la CPT di un nodo condizionata ai suoi genitori.

Quanti numeri servono

Una CPT booleana con $k$ genitori ha $2^k$ righe e basta la colonna "vero" (quella "falso" è $1-p$). Per la distribuzione $P(D)$, $P(A\mid D)$, $P(B\mid D)$ di tre booleane: $1+2+2=5$ numeri invece di $7$. Il vantaggio è anche statistico: stimando da $25$ campioni la congiunta $P(A,B,D)$ ci sono $8$ combinazioni, circa $3$ campioni ciascuna; stimando $P(A\mid D)$, $P(B\mid D)$, $P(D)$ ce ne sono circa $6$, $6$ e $12$ per ogni numero, quindi stime più affidabili.

Esempio: l'allarme antifurto

Un allarme suona per un furto (Burglary, $B$) o per un terremoto (Earthquake, $E$); i vicini Giovanni (JohnCalls, $J$) e Maria (MaryCalls, $M$) telefonano se lo sentono. Archi $B\to A$, $E\to A$, $A\to J$, $A\to M$.

Cinque CPT, $1+1+4+2+2=10$ numeri invece di $2^5-1=31$.

Probabilità di un evento completo. $P(j,m,a,\neg b,\neg e)$ è uno dei $32$ termini della congiunta: si moltiplicano le CPT, scegliendo per ogni nodo la riga dei valori dei genitori. $$P(j,m,a,\neg b,\neg e)=P(j\mid a)P(m\mid a)P(a\mid\neg b,\neg e)P(\neg b)P(\neg e)=0{,}90\cdot0{,}70\cdot0{,}001\cdot0{,}999\cdot0{,}998=0{,}000628.$$ $$P(j,\neg m,a,b,\neg e)=P(j\mid a)P(\neg m\mid a)P(a\mid b,\neg e)P(b)P(\neg e)=0{,}90\cdot0{,}30\cdot0{,}94\cdot0{,}001\cdot0{,}998=0{,}00025329.$$ (Il primo è il numero verificato nel Esercizio - Prior sampling sulla rete burglary (laboratorio 6).)

Ordinamento e costruzione

Qualunque ordine delle variabili dà una rete corretta (la regola della catena vale sempre), ma gli archi cambiano. Un modello causale (i genitori sono le cause) è molto più compatto. Con l'ordine inverso $M,J,E,B,A$ i genitori diventano: $J$ ha $M$; $E$ ha $M,J$; $B$ ha $M,J,E$; $A$ ha tutti e quattro. I numeri sono $1+2+4+8+16=31$, tanti quanti la congiunta, e le probabilità non hanno più un significato causale facile da stimare.

Le tre strutture elementari

Le indipendenze di una rete si leggono dal grafo guardando tre configurazioni di tre nodi $X,Y,Z$:

Sono le tre configurazioni con cui si compongono tutti i cammini del grafo; l'indipendenza condizionata usata è quella di 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 →.

• Catena. $B\to A\to J$: il furto influenza la telefonata di Giovanni solo attraverso l'allarme. $P(b\mid j)=0{,}0163$ ma $P(b\mid j,a)=0{,}3736=P(b\mid a)$: noto $A$, $J$ non dà altra informazione su $B$.
• Fork. $J\leftarrow A\rightarrow M$: $A$ è causa comune. Senza osservare $A$, $J$ e $M$ sono dipendenti: $P(j\mid m)=0{,}1776\ne P(j)=0{,}0521$ (se Maria chiama, probabilmente l'allarme suona, quindi probabilmente chiama anche Giovanni). Noto $A$: $P(j\mid a,m)=P(j\mid a)=0{,}90$.
• Collider. $B\to A\leftarrow E$: furto e terremoto sono indipendenti, $P(b,e)=0{,}000002=P(b)P(e)$. Ma se si osserva l'allarme diventano dipendenti: $P(b\mid a)=0{,}3736$; se si sa anche che c'è stato un terremoto, $P(b\mid a,e)=0{,}0033$: il terremoto spiega l'allarme e il furto diventa improbabile (explaining away). Se invece non c'è stato terremoto, $P(b\mid a,\neg e)=0{,}4848$.

Esempio dei dadi. $X$ = primo dado, $Y$ = secondo dado, $Z=X+Y$: $X\to Z\leftarrow Y$. $X$ e $Y$ sono indipendenti, ma se $Z=7$ e $X=1$ allora $Y=6$: $Z$ crea la dipendenza. Lo stesso avviene osservando un discendente del collider (se si sapesse solo che Giovanni ha chiamato, $B$ e $E$ diventerebbero dipendenti: $P(b\mid j)=0{,}0163$ ma $P(b\mid j,e)=0{,}0029$).

Un nodo è inoltre indipendente dai suoi non discendenti dati i genitori: per l'allarme, $J$ è indipendente da $B$, $E$ e $M$ dato $A$. Il ragionamento sui cammini del grafo (quali sono bloccati dall'evidenza) è il punto di partenza dell'inferenza causale: Interventi e operatore do - criterio backdoor e aggiustamentoOsservare $X=x$ e forzare $X=x$ sono cose diverse: $P(y\mid x)\ne P(y\mid do(x))$ quando c'è un confondente. L'intervento $do(X=x)$ si calcola con la «chirurgia» del grafo (si tolgono le frecce entranti in X) e si traduce in probabilità osservazionali con la formula di aggiustamento $P(y\mid do(x))=\sum_z P(y\mid x,z)P(z)$, dove $Z$ sono i genitori di X, o più in generale un insieme S che soddisfa il criterio backdoor: blocca ogni cammino backdoor (cammino da X a Y che inizia con una freccia entrante in X) e non contiene discendenti di X. Effetto causale medio $ACE=P(y\mid do(x))-P(y\mid do(\neg x))$. Se il confondente non è osservabile ma c'è un mediatore Z con X→Z→Y, vale il front-door $P(y\mid do(x))=\sum_z P(z\mid x)\sum_{x'}P(y\mid x',z)P(x')$. Mediazione: effetto diretto controllato CDE con $do(x),do(z)$. Se due insiemi backdoor danno risultati diversi sui dati, il modello è sbagliato. Argomento del corso da 9 CFU.Interventi e operatore do - criterio backdoor e aggiustamento →.

Inferenza per enumerazione

Problema. Data l'evidenza $\mathbf e$ (variabili osservate $\mathbf E$), calcolare $\mathbf P(X\mid\mathbf e)$ per una variabile di interrogazione $X$. Le variabili $\mathbf Y$ né osservate né interrogate sono nascoste. Si usa la marginalizzazione: $$\mathbf P(X\mid\mathbf e)=\alpha\,\mathbf P(X,\mathbf e)=\alpha\sum_{\mathbf y}\mathbf P(X,\mathbf e,\mathbf y),$$ dove $\alpha=1/P(\mathbf e)=1/\sum_x P(x,\mathbf e)$ normalizza. Ogni termine $P(X,\mathbf e,\mathbf y)$ è una congiunta completa, quindi un prodotto di CPT.

Algoritmo (enumeration-ask). Per ogni valore $x$ di $X$: sommare, sui valori delle variabili nascoste, il prodotto delle CPT nell'ordine topologico (genitori prima dei figli); poi normalizzare. Si calcola in profondità e da sinistra a destra, portando fuori dalle somme i fattori che non dipendono dalla variabile sommata.

Esempio completo: $\mathbf P(B\mid j,m)$

Con evidenza $j,m$ le nascoste sono $E$ e $A$: $\mathbf P(B\mid j,m)=\alpha\langle P(b,j,m),\,P(\neg b,j,m)\rangle$. $$P(b,j,m)=\sum_e\sum_a P(b)P(e)P(a\mid b,e)P(j\mid a)P(m\mid a)=P(b)\sum_e P(e)\sum_a P(a\mid b,e)P(j\mid a)P(m\mid a).$$ $P(b)$ esce da entrambe le somme; $P(e)$ esce dalla somma su $a$. Numeri (per $e$, poi per $\neg e$): $$P(b,j,m)=0{,}001\,[\,0{,}002\,(0{,}95\cdot0{,}9\cdot0{,}7+0{,}05\cdot0{,}05\cdot0{,}01)+0{,}998\,(0{,}94\cdot0{,}9\cdot0{,}7+0{,}06\cdot0{,}05\cdot0{,}01)\,]$$

• somma su $a$ con $e$: $0{,}95\cdot0{,}63+0{,}05\cdot0{,}0005=0{,}598525$ (dove $P(j\mid a)P(m\mid a)=0{,}9\cdot0{,}7=0{,}63$ e $P(j\mid\neg a)P(m\mid\neg a)=0{,}05\cdot0{,}01=0{,}0005$);
• somma su $a$ con $\neg e$: $0{,}94\cdot0{,}63+0{,}06\cdot0{,}0005=0{,}59223$;
• $0{,}002\cdot0{,}598525+0{,}998\cdot0{,}59223=0{,}5922426$; per $0{,}001$: $P(b,j,m)=0{,}0005922$.

Per $\neg b$: $$P(\neg b,j,m)=0{,}999\,[\,0{,}002\,(0{,}29\cdot0{,}63+0{,}71\cdot0{,}0005)+0{,}998\,(0{,}001\cdot0{,}63+0{,}999\cdot0{,}0005)\,]=0{,}999\cdot(0{,}000366+0{,}001127)=0{,}0014919.$$ Normalizzazione: $\alpha=\dfrac1{0{,}0005922+0{,}0014919}=479{,}82$ e $$\mathbf P(B\mid j,m)=\langle0{,}284;\ 0{,}716\rangle.$$ Anche se entrambi i vicini chiamano, la probabilità di furto è solo $28\%$: l'allarme scatta spesso per altre cause e il prior $0{,}001$ è bassissimo.

# rete burglary: per ogni variabile (genitori, CPT) con CPT = P(X=vero | genitori)
bn = {
    'B': ([], {(): 0.001}),
    'E': ([], {(): 0.002}),
    'A': (['B', 'E'], {(True, True): 0.95, (True, False): 0.94,
                       (False, True): 0.29, (False, False): 0.001}),
    'J': (['A'], {(True,): 0.90, (False,): 0.05}),
    'M': (['A'], {(True,): 0.70, (False,): 0.01}),
}
ordine = ['B', 'E', 'A', 'J', 'M']          # ordine topologico

def prob(var, val, ev):
    """P(var=val | genitori), con i valori dei genitori presi da ev."""
    genitori, cpt = bn[var]
    p = cpt[tuple(ev[g] for g in genitori)]
    return p if val else 1 - p

def enumera_tutto(variabili, ev):
    """Somma sulle variabili non osservate, nell'ordine topologico."""
    if not variabili:
        return 1.0
    v, resto = variabili[0], variabili[1:]
    if v in ev:                              # osservata: un solo termine
        return prob(v, ev[v], ev) * enumera_tutto(resto, ev)
    return sum(prob(v, x, {**ev, v: x}) * enumera_tutto(resto, {**ev, v: x})
               for x in (True, False))       # nascosta: si somma sui due valori

def enumeration_ask(X, ev):
    q = [enumera_tutto(ordine, {**ev, X: x}) for x in (True, False)]
    alfa = 1 / sum(q)                        # normalizzazione
    return [alfa * p for p in q]

print(enumeration_ask('B', {'J': True, 'M': True}))

Output atteso: [0.2841718353643929, 0.7158281646356071].

Costo. La ricorsione visita un albero con una foglia per ogni assegnazione delle nascoste: costo esponenziale nel loro numero. Inoltre molti sottoprodotti si ripetono: nell'albero del calcolo precedente $P(j\mid a)P(m\mid a)=0{,}9\cdot0{,}7$ e $P(j\mid\neg a)P(m\mid\neg a)=0{,}05\cdot0{,}01$ compaiono sia sotto $e$ sia sotto $\neg e$, e vengono ricalcolati.

Eliminazione di variabili

L'idea è salvare i risultati intermedi in tabelle, i fattori (factors), e riusarli. Un fattore $f(X_1,\dots,X_k)$ è una tabella di numeri indicizzata dai valori delle variabili (non è per forza una distribuzione).

Due operazioni:

• prodotto puntuale (pointwise product): $f\cdot g$ ha come variabili l'unione delle variabili e come valore il prodotto dei valori compatibili;
• somma (sum out) di una variabile: si sommano le righe che differiscono solo per quella variabile, che sparisce.

Algoritmo (variable elimination). Si scrive ogni CPT come fattore (fissando le variabili d'evidenza ai valori osservati, che le toglie dai fattori). Per ogni variabile nascosta, in un ordine scelto: si moltiplicano tutti i fattori che la contengono e si somma la variabile. Alla fine si moltiplicano i fattori rimasti e si normalizza.

Esempio: $\mathbf P(B\mid j,m)$. Fattori (con $j,m$ fissati): $f_J(A)=P(j\mid A)=\langle0{,}9;\ 0{,}05\rangle$, $f_M(A)=P(m\mid A)=\langle0{,}7;\ 0{,}01\rangle$, $f_A(A,B,E)=P(A\mid B,E)$, $f_E(E)$, $f_B(B)$.

1. Eliminare $A$. Prodotto $f_J f_M(A)=\langle0{,}63;\ 0{,}0005\rangle$; poi $g(B,E)=\sum_a f_A(a,B,E)\,f_Jf_M(a)$:

   	$e$	$\neg e$
   $b$	$0{,}598525$	$0{,}59223$
   $\neg b$	$0{,}183055$	$0{,}0011295$

   Per esempio $g(\neg b,e)=0{,}29\cdot0{,}63+0{,}71\cdot0{,}0005=0{,}183055$. Sono esattamente le somme interne dell'enumerazione, ma calcolate una volta sola.

2. Eliminare $E$. $h(B)=\sum_e f_E(e)\,g(B,e)$: $h(b)=0{,}002\cdot0{,}598525+0{,}998\cdot0{,}59223=0{,}5922426$ e $h(\neg b)=0{,}002\cdot0{,}183055+0{,}998\cdot0{,}0011295=0{,}0014934$.

3. Moltiplicare per $f_B$ e normalizzare. $\langle0{,}001\cdot0{,}5922426;\ 0{,}999\cdot0{,}0014934\rangle=\langle0{,}0005922;\ 0{,}0014919\rangle\to\langle0{,}284;\ 0{,}716\rangle$ ✓.

È lo stesso metodo del laboratorio sullo sprinkler (Esercizio - Rete sprinkler per enumerazione e variable elimination (laboratorio 5)), dove i fattori sono chiamati $\Phi_S(W,R)$ e $\Phi_R(W)$. L'ordine di eliminazione conta per il costo (il fattore più grande che si crea determina la complessità), ma il risultato è sempre lo stesso. Esempio svolto: Esercizio - Eliminazione di variabili nella rete burglary (slide del corso).

Domande d'esame

1. Quale congiunta rappresenta la rete $X\to Z\leftarrow Y$, $Z\to W$? $P(W\mid Z)P(Z\mid X,Y)P(X)P(Y)$.
2. Quanti numeri servono per la rete dell'allarme e per la congiunta? $10$ contro $2^5-1=31$.
3. Calcolare $P(j,\neg m,a,b,\neg e)$. $0{,}90\cdot0{,}30\cdot0{,}94\cdot0{,}001\cdot0{,}998=0{,}00025329$.
4. In $X\to Z\leftarrow Y$, $X$ e $Y$ sono indipendenti? E dato $Z$? Sì senza osservare $Z$; no se si osserva $Z$ (o un suo discendente).
5. Perché i modelli causali sono preferibili? Con genitori = cause la rete ha meno archi e meno numeri (allarme: $10$ contro $31$ con l'ordine invertito) e le CPT hanno un significato stimabile.