Apprendimento Automatico:
Apprendimento Bayesiano
Roberto Navigli
Cap. 6.1-6.2, 6.9-6.11 [Mitchell]
Cap. 14 [Russel & Norvig] 1
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
Cap. 5.3 [Tan, Steinbech, Kumar]
Caratteristiche dell’Apprendimento Bayesiano
• Ogni esempio di addestramento progressivamente
decrementa o incrementa la probabilità stimata che
un’ipotesi sia corretta
• La conoscenza pregressa può essere combinata con i
dati osservati per determinare la probabilità finale di
un’ipotesi
• I metodi Bayesiani possono fornire predizioni
probabilistiche (es. questo paziente ha il 93% di possibilità
di guarire)
• Nuove istanze possono essere classificate combinando le
predizioni di ipotesi multiple, pesate con le loro probabilità
• Anche quando i metodi Bayesiani sono intrattabili
computazionalmente, possono fornire uno standard di
decisione ottimale rispetto al quale misurare metodi più
pratici
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
2
Richiamo di concetti di calcolo delle probabilità
•
•
•
•
Spazio di campionamento Ω è l’insieme degli esiti di una prova
 è l’esito di una prova (es. il lancio del dado ha esito 2)
A è un evento (sottoinsieme di Ω)
Indichiamo con P(A) la probabilità (massa di probabilità) di un evento A
(es: x=1, o x “pari”)
• Per ogni coppia di eventi A e B:
A
B
0  P( A)  1
P(true)  1
P( A  B)  P( A)  P( B)  P( A  B)  P( A  B)
dove P( A  B)  P( A  B)  0 se P( A), P( B) mutuamente esclusive
es. (lanci dado) A  {1,3,5} B  {2,4,6}
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
3
Probabilità congiunta
• Dati due eventi A e B, P(A) è la probabilità marginale
dell’evento A e P(B) quella dell’evento B
• La probabilità congiunta che si verifichino entrambi gli
eventi è P(A, B)
• Se i due eventi sono indipendenti, allora si ha:
– P(A, B) = P(A) P(B)
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
4
Probabilità condizionata
• La probabilità condizionata dell’evento B dato l’evento A
(probabilità di un evento A supponendo che sia
verificato un evento B) è data da:
P( A  B)
P( A | B) 
P( B)  0
P( B)
P( B | A) 
P( A  B)
P( A)
P( A)  0
 P( A  B)  P( A | B) P( B)  P( B | A) P( A)
A
AB
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
B
5
Teorema di Bayes
• Sfruttando la definizione di probabilità condizionata si
ottiene:
P( B | A) P( A)
P( A | B) 
P( B)
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
6
Classificatore Naïve Bayes
• Si applica al caso in cui le ipotesi in H sono rappresentabili
mediante una congiunzione di valori di attributi e la
classificazione è scelta da un insieme finito Y. Le istanze x
in X sono descritte mediante m-uple di valori (x1,x2, ..., xm)
associati agli m attributi di x
• Il classificatore “naif” si basa sull’assunzione semplificativa
che i valori degli attributi siano condizionalmente
indipendenti, assegnato un valore della funzione
obiettivo, cioè, dato un nuovo esempio x da classificare,
calcoliamo:
cNB  arg max P(c j | x1 , x2 ,..., xm )  arg max
cY
cY
arg max P(c) P( x j | c)
cY
P( x1 , x2 ,..., xm | c) P(c)

P( x1 , x2 ,..., xm )
j
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
7
Stima delle probabilità
• Le probabilità P(xi|c) vengono stimate osservando le
frequenze nei dati di addestramento D
• Se D include ni esempi classificati ci, e nij di questi ni
esempi contengono il valore xj per l’attributo j, allora:
P( x j | ci ) 
nij
ni
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
8
Naïve Bayes: Esempio
•
•
•
Y = {allergia, raffreddore, in_salute} (possibili classi)
x1 = starnuti (sì, no) ; x2 = tosse (sì, no) ; x3 = febbre (sì, no) (attributi booleani)
x = (1, 1, 0) come lo classifico?
Prob
Dall’insieme D stimo
le prob. a priori
e condizionate
es:
{
in
salute
raffreddore
allergia
P(c)
0.9
0.05
0.05
P(x1 |c)
0.027
1.0
1.0
P(x2 |c)
0.027
0.5
0.5
P(x3 |c)
0.027
0.5
0.5
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
9
Esempio (continua)
• 40 esempi, 36 classificati “in salute”, 2 raffreddore, 2
allergia
• Per stimare, ad esempio, P(x1=1|in-salute), contare sui 36
esempi nei quali c(x)= “in-salute” quanti hanno x1=1
se 1 su 36, P(x1=1|in-salute)=1/36=0,027
Analogamente avrò, ad es.:
- P(x1=1|raffreddore)=2/2=1
- P(x1=1|allergia)=2/2=1
- ecc.
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
10
Esempio (continua)
•
•
 P( x
Devo calcolare il massimo al variare di c di: P(c)
Quindi ad esempio per c=raffreddore
j
| c)
j
P(raffreddore)P( x1  sì | raffr) P( x2  sì | raffr) P( x3  no | raffr) 
0,05  1 0,5  0,5  0,0125
•
Analogamente, troverò:
P(in  salute)P( x1  sì | sal ) P( x2  sì | sal ) P( x3  no | sal ) 
0,9  0.027  0,027  0,027  0,000017
P(allergia )P( x1  sì | all ) P( x2  sì | all ) P( x3  no | all ) 
0,05  1 0,5  0,5  0,0125
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
11
Problemi con Naive Bayes
• Se D è piccolo, le stime sono inaffidabili (nell’esempio
precedente alcune stime sono = 1!)
• Un valore raro xk può non capitare mai in D e dunque:
– c:
P(xk | c) = 0.
• Analogamente, se ho un solo esempio di una classe c,
–  xk: P(xk | c) = 1 o P(xk | c) = 0.
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
12
Smoothing
• Per tener conto di eventi rari, si operano degli aggiustamenti sulle
probabilità detti smoothing
• Laplace smoothing con una M-stima assume che ogni evento xj abbia
una probabilità a priori p, che si assume essere stata osservata in un
campione virtuale di dimensione M > del campione reale
nij  Mp
P( x j | ci ) 
ni  M
• Nell’esempio precedente, ad es.
P( x1  0 | raff ) 
0  M  0,5
2M
• M è una costante che determina il peso dello smoothing
• In assenza di altre informazioni, si assume p = 1/k dove k è il numero
di valori dell’attributo j in esame
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
13
Un esempio
• Classificazione automatica di documenti
– Un documento rappresentato come un elenco di termini
tj (j=1,…,|V|), dove V è il vocabolario
– Rappresentiamo un documento x con il vettore x =
(x1,x2…,x|V|) dove xj=1 se il termine tj è presente (0
altrimenti)
– D = { (xi, yi) } insieme di addestramento di documenti
già classificati
– Y = { sport, politica, ..., scienze }
– Stimare, sulla base di D, le P(tj|c)
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
14
Reti Bayesiane
• Una semplice notazione grafica per:
– l’asserzione di indipendenza condizionata
– la specifica compatta di distribuzioni congiunte
• Un grafo diretto G = (V, E) dove:
– I vertici sono le variabili aleatorie del problema
– Gli archi diretti (x, y) descrivono le dipendenze tra
variabili aleatorie
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
15
Variabili aleatorie
• Una variabile aleatoria X è una funzione dell’esito di un
esperimento:
X : 
che associa un valore a ogni esito. Ad esempio, dato
l’evento “lancio di dado”, la funzione può essere definita
come:
1 " esce la faccia 1"

X  


6 " esce la faccia 6"
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
16
Reti Bayesiane: esempio (da Tan, Steinbech, Kumar)
• La topologia della rete codifica le asserzioni di
dipendenza/indipendenza
Esercizio
Cardiopatia
Pressione
sanguigna
Dieta
Bruciore
di stomaco
Dolore
al petto
• Nell’esempio, l’esercizio è indipendente dalle altre variabili,
la cardiopatia dipende dall’esercizio e dalla dieta.
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
17
Reti Bayesiane: esempio (da Russel & Norvig)
• Sono al lavoro e il vicino John mi chiama per dire che
suona l’allarme, but la vicina Mary non chiama. A volte
viene attivato da piccole scosse di terremoto. C’e’ un
furto in corso?
• Variabili (booleane): Burglary (furto), Earthquake
(terremoto), Alarm (allarme), JohnCalls, MaryCalls
• La topologia della rete riflette la conoscenza “causale”
• Un furto o un terremoto possono causare l’attivazione
dell’allarme
• L’allarme può causare una chiamata di John o Mary
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
18
Reti Bayesiane: esempio (da Russel & Norvig)
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
19
Semantica delle Reti Bayesiane
• La distribuzione congiunta di tutte le variabili è data dal
prodotto delle probabilità condizionate “locali”:
m
P( X 1 , X 2 ,..., X m )   P( X i | Parents( X i ))
i 1
• Perché? “Chain rule”
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
20
Esempio
Qual è la probabilità che date le chiamate di John e Mary
per via dell’allarme non si sia verificato né un terremoto né
un furto?
P(J=true, M=true, A=true, B=false, E=false)
= P(j, m, a, ¬b, ¬e) = P(j|a)P(m|a)P(a| ¬b, ¬e)P(¬b)P(¬e)
= 0.9 * 0.7 * 0.001 * 0.999 * 0.998
= 0.000628
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
21
Naive Bayes visto come Rete Bayesiana
C
X1
X2
X3
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
…
Xm
22
Compattezza delle Reti Bayesiane
• Una tabella di probabilità condizionate per la variabile
booleana Xi con k genitori booleani ha 2k righe
(combinazioni dei valori dei genitori)
• Ogni riga richiede un valore di probabilità per Xi = true (il
numero per Xi = false è 1-p)
• Se ogni variabile non ha più di k genitori, la rete
completa richiede O(m2k) numeri dove m è il numero di
variabili (nodi) della rete
• Ovvero lo spazio richiesto cresce linearmente con m
• Di quanti numeri avrei bisogno invece se codificassi
l’intera distribuzione congiunta delle m variabili?
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
23
Costruzione di una Rete Bayesiana
• Scegli un ordinamento delle variabili aleatorie X1, … ,Xm
• For i = 1 to m
– aggiungi Xi alla rete
– seleziona i genitori da X1, … ,Xi-1 tali che
P (Xi | Parents(Xi)) = P (Xi | X1, ... Xi-1)
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
24
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
• P(J | M) = P(J)?
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
25
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
• P(J | M) = P(J)? No
• P(A | J, M) = P(A | J)? P(A | J, M) = P(A)?
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
26
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
•
•
•
•
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)?
P(B | A, J, M) = P(B)?
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
27
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
•
•
•
•
•
•
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)? Sì
P(B | A, J, M) = P(B)? No
P(E | B, A ,J, M) = P(E | A)?
P(E | B, A, J, M) = P(E | A, B)?
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
28
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
•
•
•
•
•
•
P(J | M) = P(J)? No
P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No
P(B | A, J, M) = P(B | A)? Sì
P(B | A, J, M) = P(B)? No
P(E | B, A ,J, M) = P(E | A)? No
P(E | B, A, J, M) = P(E | A, B)? Sì
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
29
Costruzione di una Rete Bayesiana: Esempio
• Decidere l’indipendenza condizionata è difficile se si
procede in direzione “non causale”
• Decidere sulle causalità è molto più semplice per gli
umani che non per le macchine!
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
30
Apprendimento automatico delle tabelle delle
probabilità condizionate
• Dato un insieme di addestramento, si procede in modo
simile a quanto fatto con Naive Bayes
• Si calcola la probabilità condizionata:
count ( X i , Parents( X i ))
P( X i | Parents( X i )) 
count ( Parents( X i ))
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
31
Esempio: il Buon Ricercatore Sperimentale
Abilità Ricercatore
Qualità
Scrittura
Qualità
Risultati
Articolo
accettato
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
32
Apprendimento Bayesiano “in a nutshell”
• Le reti bayesiane forniscono una rappresentazione
naturale per l’indipendenza condizionata indotta in
modo causale
• Naïve Bayes è una caratterizzazione estrema del
dominio, ma funziona generalmente bene
• Data la topologia e le tabelle di probabilità condizionate,
si ottiene una distribuzione congiunta compatta
• Semplice per gli esperti di dominio costruire una rete
Apprendimento Automatico: Apprendimento Probabilistico
Roberto Navigli
33