Apprendimento Automatico: Apprendimento Bayesiano Roberto Navigli Apprendimento Automatico: Apprendimento Probabilistico Roberto Navigli 1 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 AB 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 cY cY arg max P(c) P( x j | c) cY 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 2M • 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