Modelli Probabilistici per la Computazione Affettiva: Reti...

Modelli Probabilistici per la Computazione Affettiva:

Reti Bayesiane

Corso di Modelli di Computazione Affettiva

Prof. Giuseppe Boccignone

Dipartimento di InformaticaUniversità di Milano

[email protected]@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


• Questo mi consente di fattorizzare il “tabellone” della congiunta


0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional

Probability Distribution

CPT : Conditional Probability

Tables



0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional



Tables



0.6 * 0.3 * 0.02 * 0.8 * 0.01CPD : Conditional



Tables


• 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 //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


• Valutiamo il pattern upstream o evidenziale :

• Bob è intelligente? mmm... 30% a priori

• Bob prende C. Bob è intelligente?

Cause

Effetti

evidenza

evidenza


• Valutiamo il pattern intercausale: lo studente prende C


• Bob prende C. Bob è intelligente?

• Bob prende C, ma l’esame di Matematica è difficile. Bob è intelligente?

Cause

Effetti

Cause


• Valutiamo il pattern intercausale: lo studente prende C


• 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


attivo se Z non osservato

V structure attivo se

Z osservato

• L’influenza è come un flusso che si propaga su trail (cammini) attivi





V structure attivo se

Z o un figlio di Z osservato

• L’influenza è come un flusso che si propaga su trail (cammini) attivi




• 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




P(I=true | A=true) = ?





P(I=true | A=true,B=true) = ?

trail attivo





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), ...


∑ 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:


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


P(I,S,G)

P(S,G | I = i0)P(S | I = i0)

P(G | I = i0)


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


• Fattorizzazione Indipendenza

• Teorema (proprietà di validità o soundness):

• P fattorizza su G

•

• Esempio: dimostrare che vale l’indipendenza Questa vale se


• 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


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


I(P) Insieme delle asserzioni di

indipendenza che valgono in P

I(G) Insieme delle indipendenze che


• 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


Semantica delle RB

• Fattorizzazione Indipendenza

• Teorema:

• G è una I-map per P


• P fattorizza su G:

P soddisfa I(G) Insieme delle indipendenze che


• Esempio


• 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)


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)

Modelli Probabilistici per la Computazione Affettiva: Reti...

Documents

Transcript of Modelli Probabilistici per la Computazione Affettiva: Reti...