Post on 10-Jul-2020
Modelli Probabilistici per la Computazione Affettiva:
Reti Bayesiane
Corso di Modelli di Computazione Affettiva
Prof. Giuseppe Boccignone
Dipartimento di InformaticaUniversità di Milano
boccignone@di.unimi.itGiuseppe.Boccignone@unimi.it
http://boccignone.di.unimi.it/CompAff2015.html
Grafo diretto (Rete Bayesiana)
Grafo indiretto
Modelli grafici probabilistici //rappresentazione: PGM diretti (DAG)
• Costruzione del modello:
• Step 1. Identifico gli oggetti semanticamente rilevanti e li rappresento in termini di variabili aleatorie
• (Step 2). Definisco la “probabilità di tutto”, o probabilità congiunta
Modelli grafici probabilistici //rappresentazione a BN
• Step 3. Introduco i “vincoli” del problema: mi consentono di strutturare /semplificare la congiunta. La rappresentazione è un grafo probabilistico
Grafo diretto (Rete Bayesiana)
Modelli grafici probabilistici //rappresentazione: struttura
• Step 3. Introduco i “vincoli” del problema: mi consentono di strutturare /semplificare la congiunta. La rappresentazione è un grafo probabilistico
Chain Rule per Reti Bayesiane
Modelli grafici probabilistici //rappresentazione: struttura
• Questo mi consente di fattorizzare il “tabellone” della congiunta
Modelli grafici probabilistici //rappresentazione: struttura
0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional
Probability Distribution
CPT : Conditional Probability
Tables
• Questo mi consente di fattorizzare il “tabellone” della congiunta
Modelli grafici probabilistici //rappresentazione: struttura
0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional
Probability Distribution
CPT : Conditional Probability
Tables
• Questo mi consente di fattorizzare il “tabellone” della congiunta
Modelli grafici probabilistici //rappresentazione: struttura
0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional
Probability Distribution
CPT : Conditional Probability
Tables
Modelli grafici probabilistici //rappresentazione: PGM diretti (DAG)
• Definizione di rete Bayesiana: è una coppia
• è grafo diretto aciclico (DAG) sulle variabili
• Le variabili aleatorie sono i nodi del grafo a cui sono associate le CPD
• P è una distribuzione che fattorizza sul grafo secondo la chain rule:
• Si noti che la distribuzione congiunta P così ottenuta è effettivamente una distribuzione di probabilità ammissibile:
• P ≥ 0 (Dim. E’ il prodotto di CPD tutte non negative)
• ∑ P = 1 (Dim. Si somma su tutte le variabili sfruttando la fattorizzazione)
Modelli grafici probabilistici //rappresentazione: PGM diretti (DAG)
Modelli grafici probabilistici //BN: Pattern di ragionamento / inferenza
• Valutiamo il pattern downstream o causale o predittivo
• Bob avrà una lettera di raccomandazione?
• Bob non è tanto intelligente. Avrà una lettera di raccomandazione?
• Bob non è tanto intelligente ma l’esame di Matematica è semplice. Avrà una lettera di raccomandazione?
Cause
Effetti
1.49 +1.51= 3
1.51 / 3 = 0.503
Modelli grafici probabilistici //BN: Pattern di ragionamento / inferenza
• Valutiamo il pattern upstream o evidenziale :
• Bob è intelligente? mmm... 30% a priori
• Bob prende C. Bob è intelligente?
Cause
Effetti
evidenza
evidenza
Modelli grafici probabilistici //BN: Pattern di ragionamento / inferenza
• Valutiamo il pattern intercausale: lo studente prende C
• Bob è intelligente? mmm... 30% a priori
• Bob prende C. Bob è intelligente?
• Bob prende C, ma l’esame di Matematica è difficile. Bob è intelligente?
Cause
Effetti
Cause
Modelli grafici probabilistici //BN: Pattern di ragionamento / inferenza
• Valutiamo il pattern intercausale: lo studente prende C
• Bob è intelligente? mmm... 30% a priori
• Bob prende C. Pero’ Bob aveva superato il SAT brillantemente
• “Explaining away”
Cause
Effetti
Cause
Modelli grafici probabilistici //Flussi in BN: quando X influenza Y?
causale evidenziale causa comune
effetto comune
V structure
• Condizionando su X, influenzo la credenza di Y
Modelli grafici probabilistici //Flussi in BN: quando X influenza Y?
attivo se Z non osservato
V structure attivo se
Z osservato
• L’influenza è come un flusso che si propaga su trail (cammini) attivi
attivo se Z non osservato
attivo se Z non osservato
Modelli grafici probabilistici //Flussi in BN: quando X influenza Y?
attivo se Z non osservato
V structure attivo se
Z o un figlio di Z osservato
• L’influenza è come un flusso che si propaga su trail (cammini) attivi
attivo se Z non osservato
attivo se Z non osservato
Modelli grafici probabilistici //Flussi in BN: quando X influenza Y?
• Ho un trail (cammino) attivo S - I- G - D se:
• Ho un trail (cammino) bloccato S - I- G - D se:
• Sia un trail sul grafo G.
• Sia Z un sottoinsieme di variabili osservate sul grafo G.
• Il cammino è attivo se e solo se
• Data una struttura V del tipo
• è in Z
• un discendente di è in Z
• Nessun altro nodo del trail è in Z
Modelli grafici probabilistici //Flussi in BN: trail attivi
Esempio //Il problema dell’irrigatore
• Alice vive a Napoli (dove piove poco):
• Caso 1: si sveglia e osserva il prato del giardino bagnato: ha lasciato l’irrigatore in funzione?
• Caso 2: poi osserva il prato del vicino, Bob…..: anche quello è bagnato
• QUERY: qual è la probabilità che l'irrigatore fosse in funzione nei due casi?
Esempio //Il problema dell’irrigatore
• Supponiamo che tutte le tabelle di probabilità siano note (nessun learning)
B=0 B=1
P=0 0.8 0.2
P=1 0 1
A=0 A=1
P=0 I=0 1 0
P=1 I=0 0 1
P=0 I=1 0.1 0.9
P=1 I=1 0 1
P=0 P=10.8 0.2
I=0 I=10.9 0.1
Esempio //Il problema dell’irrigatore: soluzione con BNT
• QUERY: qual è la probabilità che l'irrigatore fosse in funzione nei due casi?
• Caso 1: si sveglia e osserva il prato del giardino bagnato: ha lasciato l’irrigatore in funzione?
• Caso 2: poi osserva il prato del vicino, Bob…..: anche quello è bagnato
P(I=true | A=true) = ?
Esempio //Il problema dell’irrigatore: soluzione con BNT
• QUERY: qual è la probabilità che l'irrigatore fosse in funzione nei due casi?
• Caso 1: si sveglia e osserva il prato del giardino bagnato: ha lasciato l’irrigatore in funzione?
• Caso 2: poi osserva il prato del vicino, Bob…..: anche quello è bagnato
P(I=true | A=true,B=true) = ?
trail attivo
Esempio //Il problema dell’irrigatore: soluzione con BNT
• QUERY: qual è la probabilità che l'irrigatore fosse in funzione nei due casi?
• Caso 1: si sveglia e osserva il prato del giardino bagnato: ha lasciato l’irrigatore in funzione?
• Caso 2: poi osserva il prato del vicino, Bob…..: anche quello è bagnato
falso
falso
vero
vero
P(I=true | A=true) = 0.3382
P(I=true | A=true,B=true) = 0.1604
Esempio: Alice e Bob in BNT (kevin murphy)
• Il concetto di trail attivo / non attivo su grafo è in relazione con il concetto di indipendenza condizionale
• Ricordiamo il concetto di indipendenza (marginale): due eventi sono indipendenti in P
• se
• vale inoltre
• Analogamente per le VA
Modelli grafici probabilistici //Flussi in BN e indipendenza condizionale
,
indipendenza marginale
• Esempio: G non è osservata e marginalizzo su G per ottenere P(I,D), ...
Modelli grafici probabilistici //Flussi in BN e indipendenza condizionale
∑ G ∑ D
∑ I
P(I,D,G)
P(I,D)P(I)
P(D)
P(I,D) = P(I) * P(D)
G non è osservato: il trail è bloccato
• Per eventi:
• Per variabili aleatorie vale
• qualunque
• Caveat: l’indipendenza marginale è il sotto caso
• Vale la proprietà:
• Sia P una distribuzione su Denotiamo l’insieme delle asserzioni di indipendenza che valgono in P come:
Modelli grafici probabilistici //Flussi in BN e indipendenza condizionale
indipendenza condizionale
• Definizione
• Si tratta di comprendere la relazione fra proprietà di indipendenza e fattorizzazione
• Idea generale:P fattorizza nella forma:
insieme delle
asserzioni di indipendenza
valide per P
INDIPENDENZA FATTORIZZAZIONE
Modelli grafici probabilistici //Flussi in BN e indipendenza condizionale
P(I,S,G)
P(S,G | I = i0)P(S | I = i0)
P(G | I = i0)
Modelli grafici probabilistici //Flussi in BN e indipendenza condizionale
I è osservato: il trail è bloccato
X
• Concetto fondamentale: due modi equivalenti di vedere la struttura grafica
• Fattorizzazione: G permette di rappresentare P
• I-map: le indipendenze codificate da G valgono in P
Modelli grafici probabilistici //Fattorizzazione e indipendenza
P fattorizza su G
ecc...
Insieme delle asserzioni di indipendenza che valgono in P
A B
• Generalizziamo il flusso di influenza nel concetto di d-separazione
• Si supponga di avere tre insiemi di nodi in G,
• Se non esiste nessun trail attivo tra qualsiasi nodo e qualsiasi dato Z, allora
Modelli grafici probabilistici //Fattorizzazione e indipendenza
• Fattorizzazione Indipendenza
• Teorema (proprietà di validità o soundness):
• P fattorizza su G
•
• Esempio: dimostrare che vale l’indipendenza Questa vale se
Modelli grafici probabilistici //Fattorizzazione e indipendenza
• Denotiamo l’insieme delle indipendenze che corrispondono alla d-separazione come:
• Definizione: I-map
• Se P soddisfa I(G), allora G è una I-map (indipendency map) di P
Modelli grafici probabilistici //Fattorizzazione e indipendenza
I(G) Insieme delle indipendenze che
corrispondono alla d-separazione
• Proprietà di validità (soundness):
• Se la distribuzione P fattorizza come G, allora ovvero G è una I-map per P
• Oss. 1: ci dice che se due nodi sono d-separati dato Z, allora sono condizionalmente indipendenti dato Z
• Oss. 2: Posso leggere direttamente sul grafo G le indipendenze per P
Modelli grafici probabilistici //Fattorizzazione e indipendenza
I(P) Insieme delle asserzioni di
indipendenza che valgono in P
I(G) Insieme delle indipendenze che
corrispondono alla d-separazione
• La proprietà fondamentale delle RB deriva da questo teorema:
• Ogni nodo della rete, dati i suoi genitori, è d-separato dai suoi non-discendenti
• P fattorizza su G
• Formalmente: Una rete Bayesiana è un DAG che codifica un insieme di ipotesi di indipendenza (indipendenze locali):
• Per qualunque variabile
• Ogni VA è indipendente dalle altre VA non figlie, dati i suoi genitori
Modelli grafici probabilistici //Fattorizzazione e indipendenza
Semantica delle RB
• Fattorizzazione Indipendenza
• Teorema:
• G è una I-map per P
Modelli grafici probabilistici //Fattorizzazione e indipendenza
• P fattorizza su G:
P soddisfa I(G) Insieme delle indipendenze che
corrispondono alla d-separazione
• Esempio
Modelli grafici probabilistici //Fattorizzazione e indipendenza
• G è una I-map per P:
chain rule (regola del prodotto)
IPOTESI:
TESI: • P fattorizza su G:
• In sintesi: due modi equivalenti di vedere la struttura grafica
• Fattorizzazione: G permette di rappresentare P
• I-map: le indipendenze codificate da G valgono in P
• Se P fattorizza su un grafo G, possiamo leggere dal grafo le indipendenze che devono valere per P (ovvero la mappa delle indipendenze, I-map)
Modelli grafici probabilistici //Fattorizzazione e indipendenza
Esempio //Naive Bayes
• Indicando con
• Valgono le seguenti ipotesi di indipendenza
• P fattorizza come
C
X1 X2
X3
Esempio //Naive Bayes
• Decidiamo se Obama è allegro (C=c1) o triste (C= c2)
• Se non ci sono vincoli particolari, P(C)= 0.5
C
X1 X2
X3
Esempio //Naive Bayes: Sebe et al. (2002)
Esempio //Naive Bayes: Sebe et al. (2002)
Esempio //Naive Bayes: Sebe et al. (2002)