1Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Roberto Navigli
Apprendimento Automatico:Apprendimento Bayesiano
Cap. 6.1-6.2, 6.9-6.11 [Mitchell] Cap. 14 [Russel & Norvig]Cap. 5.3 [Tan, Steinbech, Kumar]
2Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
3Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
• 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:
6,4,25,3,1)(.
)(),(0)()(
)()()()()(
1)(
1)(0
BAdadolancies
esclusivemutuamenteBPAPseBAPBAPdove
BAPBAPBPAPBAP
trueP
AP
A B
Richiamo di concetti di calcolo delle probabilità
4Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)
5Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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:
)()|()()|()(
0)( )(
)()|(
0)( )(
)()|(
APABPBPBAPBAP
APAP
BAPABP
BPBP
BAPBAP
A BAB
6Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Teorema di Bayes
• Sfruttando la definizione di probabilità condizionata si ottiene:
)(
)()|()|(
BP
APABPBAP
7Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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:
)|()(maxarg
),...,,(
)()|,...,,(maxarg),...,,|(maxarg
21
2121
jj
Yc
m
m
Ycmj
YcNB
cxPcP
xxxP
cPcxxxPxxxcPc
8Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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:
i
ijij n
ncxP )|(
9Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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 in salute
raffred-dore
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
Dall’insieme D stimole prob. a priorie condizionatees:
10Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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,027Analogamente avrò, ad es.: - P(x1=1|raffreddore)=2/2=1- P(x1=1|allergia)=2/2=1- ecc.
11Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
• Devo calcolare il massimo al variare di c di:
• Quindi ad esempio per c=raffreddore
• Analogamente, troverò:
)|()( j
j cxPcP
0125,05,05,0105,0
)|()|()|()( 321
raffrnoxPraffrsìxPraffrsìxPeraffreddorP
0125,05,05,0105,0
)|()|()|()(
000017,0027,0027,0027.09,0
)|()|()|()(
321
321
allnoxPallsìxPallsìxPallergiaP
salnoxPsalsìxPsalsìxPsaluteinP
Esempio (continua)
12Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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.
13Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
• Nell’esempio precedente, ad es.
• 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
Mn
MpncxP
i
ijij
)|(
M
MraffxP
2
5,00)|0( 1
14Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)
15Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
16Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Variabili aleatorie
• Una variabile aleatoria X è una funzione dell’esito di un esperimento:
che associa un valore a ogni esito. Ad esempio, dato l’evento “lancio di dado”, la funzione può essere definita come:
:X
6" faccia la esce"6
1" faccia la esce"1
X
17Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Reti Bayesiane: esempio (da Tan, Steinbech, Kumar)
• La topologia della rete codifica le asserzioni di dipendenza/indipendenza
• Nell’esempio, l’esercizio è indipendente dalle altre variabili, la cardiopatia dipende dall’esercizio e dalla dieta.
Esercizio Dieta
Cardiopatia Bruciore di stomaco
Doloreal petto
Pressionesanguigna
18Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
19Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Reti Bayesiane: esempio (da Russel & Norvig)
20Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Semantica delle Reti Bayesiane
• La distribuzione congiunta di tutte le variabili è data dal prodotto delle probabilità condizionate “locali”:
• Perché? “Chain rule”
m
iiim XParentsXPXXXP
121 ))(|(),...,,(
21Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
22Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Naive Bayes visto come Rete Bayesiana
C
X1 X2 X3 Xm…
23Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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?
24Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)
25Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Costruzione di una Rete Bayesiana: Esempio
• Supponiamo l’ordinamento: M, J, A, B, E
• P(J | M) = P(J)?
26Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)?
27Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)?
28Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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)?
29Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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ì
30Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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!
31Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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:
))((
))(,())(|(
i
iiii XParentscount
XParentsXcountXParentsXP
32Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
Esempio: il Buon Ricercatore Sperimentale
Abilità Ricercatore
QualitàScrittura
QualitàRisultati
Articoloaccettato
33Apprendimento Automatico: Apprendimento ProbabilisticoRoberto Navigli
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
Top Related