Esercizio - Inferenza per enumerazione nella rete burglary (slide del corso)

Soluzione

1. Un termine della congiunta

La congiunta si scompone nel prodotto delle CPT (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 →); per ogni nodo si prende la riga che corrisponde ai valori dei suoi genitori: $$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).$$ Valori: $P(j\mid a)=0{,}90$; $P(\neg m\mid a)=1-0{,}70=0{,}30$; $P(a\mid b,\neg e)=0{,}94$; $P(b)=0{,}001$; $P(\neg e)=1-0{,}002=0{,}998$. $$0{,}90\cdot0{,}30\cdot0{,}94\cdot0{,}001\cdot0{,}998=0{,}00025329.$$ La risposta è la quarta opzione. (Le altre sono errori tipici: per esempio dimenticare $P(\neg m\mid a)=0{,}3$ usando $0{,}7$, o prendere la riga $\neg b$.)

2. $\mathbf P(B\mid j,m)$

Impostazione. Le variabili nascoste sono $E$ e $A$; l'evidenza è $j,m$. Dalla marginalizzazione: $$\mathbf P(B\mid j,m)=\alpha\,\mathbf P(B,j,m)=\alpha\,\langle P(b,j,m),\ P(\neg b,j,m)\rangle.$$

Passo 1: scomporre e portare fuori i fattori costanti. $$P(b,j,m)=\sum_e\sum_aP(b)P(e)P(a\mid b,e)P(j\mid a)P(m\mid a)=P(b)\sum_eP(e)\sum_aP(a\mid b,e)P(j\mid a)P(m\mid a).$$ $P(b)$ non dipende né da $e$ né da $a$; $P(e)$ non dipende da $a$.

Passo 2: i prodotti $P(j\mid a)P(m\mid a)$ (indipendenti da $b,e$): per $a$ vale $0{,}9\cdot0{,}7=0{,}63$; per $\neg a$ vale $0{,}05\cdot0{,}01=0{,}0005$.

Passo 3: calcolo di $P(b,j,m)$. Somma su $a$ per ciascun $e$:

• $e$: $0{,}95\cdot0{,}63+0{,}05\cdot0{,}0005=0{,}5985+0{,}000025=0{,}598525$;
• $\neg e$: $0{,}94\cdot0{,}63+0{,}06\cdot0{,}0005=0{,}5922+0{,}00003=0{,}59223$.

Somma su $e$ pesata con $P(e)$: $0{,}002\cdot0{,}598525+0{,}998\cdot0{,}59223=0{,}001197+0{,}591046=0{,}592243$. Moltiplicato per $P(b)$: $$P(b,j,m)=0{,}001\cdot0{,}592243=0{,}0005922.$$

Passo 4: calcolo di $P(\neg b,j,m)$ (stesse operazioni con $P(a\mid\neg b,e)$):

• $e$: $0{,}29\cdot0{,}63+0{,}71\cdot0{,}0005=0{,}1827+0{,}000355=0{,}183055$;
• $\neg e$: $0{,}001\cdot0{,}63+0{,}999\cdot0{,}0005=0{,}00063+0{,}0004995=0{,}0011295$;
• pesata: $0{,}002\cdot0{,}183055+0{,}998\cdot0{,}0011295=0{,}000366+0{,}001127=0{,}001493$;
• per $P(\neg b)=0{,}999$: $P(\neg b,j,m)=0{,}0014919$.

Passo 5: normalizzazione. $\alpha=1/(0{,}0005922+0{,}0014919)=1/0{,}0020841=479{,}82$: $$\mathbf P(B\mid j,m)=479{,}82\cdot\langle0{,}0005922;\ 0{,}0014919\rangle=\langle0{,}284;\ 0{,}716\rangle.$$ Anche con entrambe le telefonate il furto ha probabilità solo $28{,}4\%$: il prior del furto è $0{,}001$ e l'allarme può suonare anche senza furto (terremoto, oppure falso allarme con $P(a\mid\neg b,\neg e)=0{,}001$ in una situazione, $\neg b,\neg e$, che quasi sempre si verifica).

3. Estensione: $\mathbf P(A\mid j,m)$ e $\mathbf P(E\mid j,m)$

Il denominatore comune è $P(j,m)=0{,}0020841$ (somma dei due termini sopra).

• $\mathbf P(A\mid j,m)$: $P(a,j,m)=P(a)P(j\mid a)P(m\mid a)$, con $P(a)=\sum_{b,e}P(b)P(e)P(a\mid b,e)=0{,}0025164$ (marginale dell'allarme): $0{,}0025164\cdot0{,}63=0{,}0015853$; $P(\neg a,j,m)=0{,}9974836\cdot0{,}0005=0{,}0004987$. Normalizzando: $\langle0{,}7607;\ 0{,}2393\rangle$.
• $\mathbf P(E\mid j,m)$: $P(e,j,m)=P(e)\sum_bP(b)\sum_aP(a\mid b,e)P(j\mid a)P(m\mid a)$; per $e$: $0{,}002\cdot(0{,}001\cdot0{,}598525+0{,}999\cdot0{,}183055)=0{,}002\cdot0{,}183471=0{,}000367$. Con il totale $0{,}0020841$ si ottiene $P(e\mid j,m)=0{,}176$, cioè $\langle0{,}176;\ 0{,}824\rangle$ (verificato anche per enumerazione completa).

Il valore di $P(a\mid j,m)=0{,}76$ ($>0{,}28$) mostra che se entrambi chiamano l'allarme è probabilmente suonato, ma la causa più probabile resta un falso allarme o un terremoto.

Codice

# 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}))
print(enumera_tutto(ordine, {'B': True, 'E': False, 'A': True, 'J': True, 'M': False}))

Output: [0.2841718353643929, 0.7158281646356071] e 0.00025329240000000004.