Inferenza causale - modelli causali strutturali e scala della causalità

Argomento del corso da 9 CFU (il corso da 6 CFU esclude Causal Inference). Si usano gli strumenti delle reti bayesiane: 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 → e 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 →. Prosegue con 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 → e Controfattuali e scoperta causaleUn controfattuale chiede «cosa sarebbe successo a questo individuo se X fosse stato x?»: $Y_x(u)$ è il valore di Y nel modello $M_x$ (equazione di X sostituita da X=x) con le esogene fissate al valore $u$ dell'individuo. Si calcola in tre passi: abduzione (aggiornare $P(U)$ con l'evidenza, nel caso deterministico ricavare $u$ dai dati), azione (sostituire l'equazione di X con la costante), predizione (calcolare Y in $M_x$). Differenza con gli interventi: $P(Y\mid do(x))\equiv P(Y_x)$ è a livello di popolazione, ma in generale $P(Y\mid do(x),z)\ne P(Y_x\mid z)$ perché nel secondo il condizionamento è prima dell'intervento. Nei modelli lineari gaussiani i coefficienti di regressione di ogni variabile sui suoi genitori sono i coefficienti strutturali, e l'effetto causale totale è la somma dei prodotti dei coefficienti lungo i cammini non backdoor. Scoperta causale (algoritmo PC): si parte dal grafo completo non orientato, si toglie ogni arco X−Y con $X\perp!!!\perp Y\mid Z$ a $|Z|$ crescente (test di Fisher), si orientano i collider (Z mai nell'insieme separatore), poi si propaga l'orientamento; catena e fork non sono distinguibili (stessa classe di equivalenza di Markov). Assunzioni: aciclicità, sufficienza, Markov, fedeltà. Argomento del corso da 9 CFU.Controfattuali e scoperta causale →.

1. Perché serve la causalità

I metodi basati sui dati (deep learning, big data) sanno dire come sono distribuite le variabili, non perché valgono certi valori. Il perché serve per validare un farmaco, prevedere l'effetto di una politica economica, capire un comportamento.

Correlazione non implica causazione. Il gallo canta quando sorge il sole (correlazione fortissima), ma il sole non sorge perché il gallo canta. Gli annegamenti aumentano con il consumo di gelati, ma c'è una causa comune (la stagione): vietare i gelati non salverebbe nessuno. Lo stesso vale per lo studio osservazionale che lega il consumo nazionale di cioccolato al numero di premi Nobel, e per i sistemi di raccomandazione, che vedono solo ciò che gli utenti hanno già scelto.

Una causa comune di due variabili (un confondente, confounder) produce una correlazione che non è un effetto di una variabile sull'altra. Distinguere i due casi con i soli dati è impossibile, come mostrano i due paragrafi seguenti.

Il paradosso di Simpson

A 700 pazienti (357 uomini e 343 donne) viene offerta una medicina: 350 scelgono di prenderla, 350 no. Guariscono:

La medicina funziona in entrambi i sottogruppi (93% > 87% e 73% > 69%) ma sembra peggiorare la popolazione (78% < 83%). Non è un errore di calcolo: la proporzione di uomini è molto diversa nei due gruppi. Tra chi prende la medicina gli uomini sono 87 su 350 (25%), tra chi non la prende sono 270 su 350 (77%). Gli uomini guariscono di più in ogni caso, quindi il gruppo «senza medicina», pieno di uomini, parte avvantaggiato: il sesso è un confondente (influenza sia la scelta della medicina sia la guarigione). I numeri aggregati mescolano l'effetto della medicina con l'effetto del sesso.

Quale tabella usare, quella aggregata o quelle separate, non si decide con la matematica ma con il modello causale del processo che ha generato i dati: se il sesso è causa della scelta (grafo $Z\to X$, $Z\to Y$, $X\to Y$) si guarda per sottogruppi e si pesa con la frequenza del sesso (aggiustamento: 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 →); se invece la variabile che divide in gruppi fosse una conseguenza della medicina (un mediatore), si userebbe la tabella aggregata. L'esercizio svolto è Esercizio - Paradosso di Simpson ed effetto causale della medicina (slide del corso).

La congiunta non basta

La distribuzione congiunta $\mathbf P(X_1,\dots,X_n)$ si può scrivere con più reti bayesiane, tutte corrette: $$\mathbf P(A,B)=\mathbf P(A\mid B)\mathbf P(B)=\mathbf P(B\mid A)\mathbf P(A),$$ quindi i grafi $A\leftarrow B$ e $A\to B$ rappresentano la stessa distribuzione e, dai soli dati, sono indistinguibili. Anche con tre variabili la fattorizzazione cambia con l'ordine delle variabili. Una rete bayesiana codifica indipendenze, non il verso delle cause (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 rispondere a «perché il gallo canta?», «da cosa dipende l'aumento di annegamenti?», «la medicina funziona davvero?» serve un modello causale, ricavato da conoscenza di dominio o da esperimenti, che spieghi come sono stati generati i dati.

2. Modelli causali strutturali (SCM)

Definizione (SCM, structural causal model). Un SCM è formato da

• un insieme di variabili esogene $U$: non dipendono da nessun'altra variabile del modello (sono i fattori esterni, il «rumore»);
• un insieme di variabili endogene $V$: ciascuna è determinata dalle altre;
• un insieme di funzioni $F=\{f_v\}_{v\in V}$, una per ogni variabile endogena, $v=f_v(\text{pa}(v),u_v)$;

e (implicitamente) da un grafo con una freccia da ogni variabile che compare in $f_v$ verso $v$.

Esempio. Stipendio $C$ in funzione di istruzione $A$ ed esperienza $B$: $U=\{A,B\}$, $V=\{C\}$, $F=\{f_C\}$ con $f_C:\ C=2A+3B$. Il grafo è $A\to C\leftarrow B$.

Definizione (causa). $X$ è causa diretta di $Y$ se compare nella funzione $f_Y$. $X$ è causa di $Y$ se è causa diretta di $Y$ o di un'altra causa di $Y$ (definizione ricorsiva).

Nell'esempio $A$ e $B$ sono entrambe cause di $C$. Il verso conta: la funzione $C=2A+3B$ non si può leggere come $A=(C-3B)/2$ nel senso causale, perché cambiare lo stipendio non cambia l'istruzione.

Reti causali

Le equazioni esatte spesso non sono note e a volte nemmeno le variabili. Esempio: prestazione a basket $P$ in funzione di altezza $H$ e sesso $G$, con termini di errore $U_1,U_2,U_3$. Le $U$ rappresentano fattori non osservati, indipendenti tra loro, e in tal caso si omettono dal grafo. Anche senza le equazioni, il solo grafo (la rete causale) contiene l'informazione qualitativa che basta per molte inferenze causali.

I tre modelli sono nidificati: gli SCM (grafo più funzioni) contengono le reti causali (grafo con frecce che sono cause), che sono particolari reti bayesiane (una rete bayesiana ha frecce qualsiasi purché la fattorizzazione sia corretta; una rete causale ha frecce che indicano cause).

L'esempio sprinkler come SCM

Variabili: nuvoloso $C$, pioggia $R$, irrigatore acceso $S$, erba bagnata $W$ (nei laboratori $G$, GrassWet). Con quattro esogene $U_1,\dots,U_4$ uniformi in $[0,1]$ e le tabelle di probabilità del laboratorio, le funzioni sono soglie:

$$C=\mathbf 1[U_1<0.5],\quad R=\mathbf 1[U_2<p_R(C)],\quad S=\mathbf 1[U_3<p_S(C)],\quad W=\mathbf 1[U_4<p_W(S,R)]$$ con $p_R(\text{true})=0.8$, $p_R(\text{false})=0.1$; $p_S(\text{true})=0.1$, $p_S(\text{false})=0.5$; $p_W(S,R)=0.95;\ 0.90;\ 0.90;\ 0.10$ per $(S,R)=(\text{T},\text{T}),(\text{T},\text{F}),(\text{F},\text{T}),(\text{F},\text{F})$. Il grafo è

Le funzioni dicono qualcosa in più della rete: dicono cosa succederebbe se si cambiasse una variabile. Questo è il punto di partenza degli interventi (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 →).

3. La scala della causalità

Pearl (The Book of Why, indicato nelle risorse del corso) distingue tre livelli di domande, ciascuno non risolvibile con gli strumenti del precedente:

1. Associazione (vedere): $P(y\mid x)$, «cosa vedo di $Y$ se osservo $X=x$?». Bastano i dati e la congiunta (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 →).
2. Intervento (fare): $P(y\mid do(x))$, «cosa accade a $Y$ se forzo $X=x$?». Serve la rete 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 →).
3. Controfattuali (immaginare): «cosa sarebbe successo a questo individuo se $X$ fosse stato $x$?». Serve l'SCM completo con le funzioni (Controfattuali e scoperta causaleUn controfattuale chiede «cosa sarebbe successo a questo individuo se X fosse stato x?»: $Y_x(u)$ è il valore di Y nel modello $M_x$ (equazione di X sostituita da X=x) con le esogene fissate al valore $u$ dell'individuo. Si calcola in tre passi: abduzione (aggiornare $P(U)$ con l'evidenza, nel caso deterministico ricavare $u$ dai dati), azione (sostituire l'equazione di X con la costante), predizione (calcolare Y in $M_x$). Differenza con gli interventi: $P(Y\mid do(x))\equiv P(Y_x)$ è a livello di popolazione, ma in generale $P(Y\mid do(x),z)\ne P(Y_x\mid z)$ perché nel secondo il condizionamento è prima dell'intervento. Nei modelli lineari gaussiani i coefficienti di regressione di ogni variabile sui suoi genitori sono i coefficienti strutturali, e l'effetto causale totale è la somma dei prodotti dei coefficienti lungo i cammini non backdoor. Scoperta causale (algoritmo PC): si parte dal grafo completo non orientato, si toglie ogni arco X−Y con $X\perp!!!\perp Y\mid Z$ a $|Z|$ crescente (test di Fisher), si orientano i collider (Z mai nell'insieme separatore), poi si propaga l'orientamento; catena e fork non sono distinguibili (stessa classe di equivalenza di Markov). Assunzioni: aciclicità, sufficienza, Markov, fedeltà. Argomento del corso da 9 CFU.Controfattuali e scoperta causale →).

Il corso arriva fino al terzo livello e poi tratta la scoperta causale (ricavare il grafo dai dati).

4. Strutture elementari e d-separazione

Il grafo di una rete causale decide quali variabili sono indipendenti. Tre configurazioni di tre nodi bastano per costruire tutto. Si ricorda che $X\perp\!\!\!\perp Y\mid Z$ significa $P(x\mid y,z)=P(x\mid z)$ (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 →).

Nello sprinkler: catena $C\to R\to W$ (osservata $R$, $W$ non dipende più da $C$ attraverso questo cammino), fork $R\leftarrow C\to S$ (dato $C$, $R$ e $S$ sono indipendenti), collider $R\to W\leftarrow S$ (se osservo $W$, $R$ e $S$ diventano dipendenti).

Verifica numerica del collider (explaining away). Con le tabelle sopra:

• non dato $W$: $P(r\mid s,c)=P(r\mid c)=0.8$, cioè $R\perp\!\!\!\perp S\mid C$ (fork);
• osservata $W=$ vero e $C=$ vero: $P(r\mid w,c)=0.953$, ma se si sa anche che l'irrigatore era acceso $P(r\mid w,s,c)=0.809$ e se era spento $P(r\mid w,\neg s,c)=0.973$.

L'erba bagnata ha due spiegazioni; sapere che una c'è (irrigatore acceso) rende meno necessaria l'altra (pioggia): l'informazione su $S$ cambia la probabilità di $R$, quindi sono dipendenti dato $W$. Senza condizionare su $C$ si ha lo stesso effetto in forma più marcata: $P(r\mid w)=0.627$, $P(r\mid w,s)=0.226$, $P(r\mid w,\neg s)=0.917$.

d-separazione

Definizione (d-separazione). Sia $Z$ l'insieme delle variabili condizionanti. $X$ e $Y$ sono d-separate da $Z$ se ogni cammino $p$ tra loro (di qualunque verso delle frecce) soddisfa almeno una condizione:

• $p$ contiene una catena $A\to B\to C$ o un fork $A\leftarrow B\to C$ con $B\in Z$;
• $p$ contiene un collider $A\to B\leftarrow C$ e né $B$ né i suoi discendenti sono in $Z$.

In tal caso $X\perp\!\!\!\perp Y\mid Z$.

Un cammino che soddisfa una condizione è bloccato; se almeno un cammino non è bloccato, X e Y sono d-connesse e in generale dipendenti.

Esempio (allarme antifurto). Grafo: $B\to A\leftarrow E$ (furto $B$ e terremoto $E$ attivano l'allarme $A$), $A\to J$ e $A\to M$ (chiamate dei vicini John e Mary).

• $B\perp\!\!\!\perp E$? L'unico cammino $B\to A\leftarrow E$ ha un collider $A$ non osservato: bloccato, quindi sì.
• $B\perp\!\!\!\perp E\mid A$? Il collider è osservato: cammino aperto, quindi no (explaining away).
• $B\perp\!\!\!\perp J\mid A$? Il cammino $B\to A\to J$ è una catena con $A\in Z$: bloccato, quindi sì.
• $J\perp\!\!\!\perp M\mid A$? $J\leftarrow A\to M$ è un fork con $A\in Z$: sì. Senza condizionare, $J$ e $M$ sono invece dipendenti (hanno la causa comune $A$).
• $B\perp\!\!\!\perp E\mid J$? $J$ è un discendente del collider $A$ e sta in $Z$: il cammino si apre, quindi no.

def d_separati(archi, x, y, Z):
    nodi = {n for e in archi for n in e}
    pa = lambda v: {a for a, b in archi if b == v}
    ch = lambda v: {b for a, b in archi if a == v}
    def disc(v):                                   # discendenti di v
        out, pila = set(), [v]
        while pila:
            for c in ch(pila.pop()):
                if c not in out: out.add(c); pila.append(c)
        return out
    def cammini(p):                                # cammini semplici x..y, frecce in ogni verso
        if p[-1] == y: yield p; return
        for n in (pa(p[-1]) | ch(p[-1])) - set(p): yield from cammini(p + [n])
    def bloccato(p):
        for a, b, c in zip(p, p[1:], p[2:]):
            if (a, b) in archi and (c, b) in archi:          # collider
                if not ({b} | disc(b)) & Z: return True
            elif b in Z: return True                         # catena o fork
        return False
    return all(bloccato(p) for p in cammini([x]))

allarme = {("B", "A"), ("E", "A"), ("A", "J"), ("A", "M")}
print(d_separati(allarme, "B", "E", set()), d_separati(allarme, "B", "E", {"A"}),
      d_separati(allarme, "B", "J", {"A"}), d_separati(allarme, "J", "M", {"A"}),
      d_separati(allarme, "B", "E", {"J"}))

Output: True False True True False, in accordo con le cinque risposte. Per grafi grandi i cammini si enumerano in modo più efficiente (BFS e DFS: Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →), ma il criterio è lo stesso.

5. Dalla rete bayesiana alla rete causale

Una rete bayesiana qualsiasi è consistente con la congiunta ma i suoi archi possono andare in qualunque verso compatibile; una rete causale impone che le frecce siano le cause reali. La conseguenza decisiva (sviluppata nella nota sugli interventi): se intervengo su una variabile, le frecce entranti in quella variabile scompaiono, mentre quelle uscenti restano. Con la sola rete bayesiana questa operazione non ha senso perché le frecce non sono cause; con una rete causale sì. Per apprendere la struttura dai dati si veda anche Apprendimento delle reti bayesiane - parametri e strutturaImparare una rete bayesiana significa stimare i parametri (le CPT) con la struttura nota, oppure trovare la struttura stessa dai dati. Con dati completi la stima di massima verosimiglianza (ML) è una frequenza: $P(B_i\mid A_j,C_k)\approx N_{ijk}/N_{jk}$. Per evitare probabilità zero si usa lo smoothing di Laplace: $P(x_i)=(1+m)/(k+N)$ ($k$ valori, $N$ campioni, $m$ occorrenze). Con valori mancanti si inferisce il valore più probabile dagli altri della riga e si ristimano i parametri; con variabili nascoste si usa l'algoritmo EM (passo E: stima dei dati mancanti con i parametri correnti; passo M: aggiornamento dei parametri), da inizializzazione casuale fino a convergenza. L'apprendimento della struttura è difficile (numero di DAG superesponenziale): metodi globali (ricerca con punteggio, ad esempio BIC $=\log P(D\mid m)-|m|\log|D|/2$ con hill climbing) e metodi locali (test di indipendenza, algoritmo PC).Apprendimento delle reti bayesiane - parametri e struttura →, ricordando che i dati osservazionali determinano il grafo solo fino all'equivalenza di Markov (Controfattuali e scoperta causaleUn controfattuale chiede «cosa sarebbe successo a questo individuo se X fosse stato x?»: $Y_x(u)$ è il valore di Y nel modello $M_x$ (equazione di X sostituita da X=x) con le esogene fissate al valore $u$ dell'individuo. Si calcola in tre passi: abduzione (aggiornare $P(U)$ con l'evidenza, nel caso deterministico ricavare $u$ dai dati), azione (sostituire l'equazione di X con la costante), predizione (calcolare Y in $M_x$). Differenza con gli interventi: $P(Y\mid do(x))\equiv P(Y_x)$ è a livello di popolazione, ma in generale $P(Y\mid do(x),z)\ne P(Y_x\mid z)$ perché nel secondo il condizionamento è prima dell'intervento. Nei modelli lineari gaussiani i coefficienti di regressione di ogni variabile sui suoi genitori sono i coefficienti strutturali, e l'effetto causale totale è la somma dei prodotti dei coefficienti lungo i cammini non backdoor. Scoperta causale (algoritmo PC): si parte dal grafo completo non orientato, si toglie ogni arco X−Y con $X\perp!!!\perp Y\mid Z$ a $|Z|$ crescente (test di Fisher), si orientano i collider (Z mai nell'insieme separatore), poi si propaga l'orientamento; catena e fork non sono distinguibili (stessa classe di equivalenza di Markov). Assunzioni: aciclicità, sufficienza, Markov, fedeltà. Argomento del corso da 9 CFU.Controfattuali e scoperta causale →).

Domande d'esame

1. Nel paradosso di Simpson con $X$ medicina, $Y$ guarigione, $Z$ sesso e grafo $Z\to X$, $Z\to Y$, $X\to Y$, quale tabella si usa per l'effetto causale? Quelle per sottogruppi, pesate con $P(z)$: $Z$ è un confondente. La tabella aggregata mescola effetto della medicina ed effetto del sesso.
2. Nel grafo $A\to B\leftarrow C$ con $D$ figlio di $B$, $A$ e $C$ sono indipendenti dato $D$? No: $D$ è discendente del collider $B$ e osservarlo apre il cammino.
3. Nello sprinkler, $R$ e $S$ sono indipendenti dato $C$? Sì, il cammino $R\leftarrow C\to S$ è un fork con $C$ osservato. Dato $W$ (e non $C$) non lo sono.
4. Differenza tra rete bayesiana e rete causale? Nella rete causale le frecce sono cause: permette di rispondere a domande di intervento, perché tagliando le frecce entranti si ottiene il modello dopo l'intervento.