Esercizio - Rete sprinkler per enumerazione e variable elimination (laboratorio 5)

Soluzione: variable elimination

Passo 1: scomporre la query con le regole delle reti bayesiane (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 →): $$\mathbf P(W\mid c)=\alpha\,\mathbf P(W,c)=\alpha\sum_{r,s}\mathbf P(W,c,r,s)=\alpha\sum_{r,s}\mathbf P(W\mid r,s)P(r\mid c)P(s\mid c)P(c)=\alpha\,P(c)\sum_rP(r\mid c)\sum_s\mathbf P(W\mid r,s)P(s\mid c).$$ Le variabili nascoste sono $R$ e $S$, e $P(c)$ esce dalle somme.

Passo 2: sommare $S$ (la somma più interna). Si ottiene la tabella $\Phi_S(W,R)=\sum_s\mathbf P(W\mid R,s)P(s\mid c)$:

(Le colonne sommano a $1$: $0{,}905+0{,}095=1$ e $0{,}18+0{,}82=1$.)

Passo 3: sommare $R$. $\Phi_R(W)=P(r\mid c)\,\Phi_S(W,r)+P(\neg r\mid c)\,\Phi_S(W,\neg r)$: $$\Phi_R(w)=0{,}8\cdot0{,}905+0{,}2\cdot0{,}18=0{,}724+0{,}036=0{,}76,\qquad\Phi_R(\neg w)=0{,}8\cdot0{,}095+0{,}2\cdot0{,}82=0{,}076+0{,}164=0{,}24.$$

Passo 4: moltiplicare per $P(c)$ e normalizzare. $0{,}5\cdot\langle0{,}76;\ 0{,}24\rangle=\langle0{,}38;\ 0{,}12\rangle\to\langle0{,}76;\ 0{,}24\rangle$. L'ultimo passo non cambia il risultato perché la somma precedente era già normalizzata e $P(c)$ è solo una costante che si poteva includere in $\alpha$.

$$\mathbf P(W\mid c)=\langle0{,}76;\ 0{,}24\rangle.$$

Codice

import numpy as np

t, f = 0, 1                                   # indici di 'vero' e 'falso'

P_c   = np.array([0.5, 0.5])                  # P(C)
P_R_c = np.array([0.8, 0.2])                  # P(R | c)    = <P(r|c), P(non r|c)>
P_S_c = np.array([0.1, 0.9])                  # P(S | c)
# P_W_RS[w, r, s] = P(W=w | R=r, S=s)   (primo indice: w vero/falso)
P_W_RS = np.array([[[0.95, 0.90], [0.90, 0.10]],     # w vero:  r=t: (s=t, s=f); r=f: (s=t, s=f)
                   [[0.05, 0.10], [0.10, 0.90]]])    # w falso

Phi_S = P_W_RS[:, :, t] * P_S_c[t] + P_W_RS[:, :, f] * P_S_c[f]   # somma su S: tabella (W, R)
print(Phi_S)
Phi_R = P_R_c[t] * Phi_S[:, t] + P_R_c[f] * Phi_S[:, f]           # somma su R: vettore (W)
print(Phi_R)
risultato = P_c[t] * Phi_R
print(risultato / risultato.sum())

Output: [[0.905 0.18 ] [0.095 0.82 ]], [0.76 0.24], [0.76 0.24]. Verificato con l'enumerazione sulle $8$ combinazioni di $R,S,W$: $\langle0{,}76;\ 0{,}24\rangle$.

Quiz: valori modificati e un errore nel materiale del corso

Con l'array del quiz il codice del corso stampa Phi_S = [[0.905 0.795] [0.095 0.195]] e Phi_R = [0.883 0.115]. Il risultato è giusto nella forma del calcolo, ma non è una distribuzione: $0{,}883+0{,}115=0{,}998\ne1$. Il motivo è nell'array: per $\neg r,s$ si ha $P(w\mid\neg r,s)=0{,}75$ e $P(\neg w\mid\neg r,s)=0{,}15$, che sommano a $0{,}9$ (le altre tre colonne sommano a $1$). Una delle due cifre è un refuso:

• se $P(\neg w\mid\neg r,s)=0{,}25$: $\Phi_R=\langle0{,}883;\ 0{,}117\rangle$;
• se $P(w\mid\neg r,s)=0{,}85$ (il $0{,}15$ è giusto): $\Phi_S(w,\neg r)=0{,}85\cdot0{,}1+0{,}80\cdot0{,}9=0{,}805$ e $\Phi_R=\langle0{,}8\cdot0{,}905+0{,}2\cdot0{,}805;\ 0{,}115\rangle=\langle0{,}885;\ 0{,}115\rangle$.

Senza la figura originale non si può dire quale delle due sia quella voluta. Se si usa l'array così com'è, si normalizza: $\langle0{,}883;\ 0{,}115\rangle/0{,}998=\langle0{,}8848;\ 0{,}1152\rangle$. In ogni caso il risultato è molto vicino a $0{,}88$: il prato bagnato è più probabile rispetto al caso originale ($0{,}76$) perché $P(w\mid\neg r,\neg s)$ passa da $0{,}10$ a $0{,}80$.