Apprendimento Bayesiano

L’apprendimento bayesiano fornisce un approccio probabilistico al proble- ma dell’apprendimento. Solitamente, durante il processo di apprendimento, dobbiamo determinare la migliore ipotesi tra quelle contenute nello spazio delle ipotesi H, basandoci sui dati di allenamento a disposizione; seguendo l’approccio bayesiano la migliore ipotesi `e quella pi`u probabile dati gli esempi di allenamento e la conoscenza iniziale della probabilit`a delle ipotesi in H.

Teorema di Bayes

Un metodo diretto per calcolare queste probabilit`a `e il teorema di Bayes, che calcola la probabilit`a di una ipotesi data la sua probabilit`a a priori, la pro-

CAPITOLO 4. MACHINE LEARNING

babilit`a di osservare alcuni dati data la probabilit`a dell’ipotesi e la probabilit`a di osservare tali dati. Formalmente il teorema di Bayes `e il seguente:

P (hi|d) = P (d|hi)P (hi) P (d) = P (d|hi)P (hi) P jP (d|hj)P (hj)

dove per P (hi) si intende la probabilit`a a priori dell’ipotesi hi, cio`e la proba-

bilit`a iniziale dell’ipotesi, per P (d|hi) si intende la probabilit`a di osservare il

dato di allenamento d data l’ipotesi hi vera, per P (d) si intende la probabi-

lit`a a priori di osservare il dato di allenamento d e per P (hi|d) si intende la

probabilit`a a posteriori dell’ipotesi hi, cio`e la probabilit`a che hi sia vera data

l’osservazione del dato di allenamento d.

L’apprendimento bayesiano ha come obiettivo effetuare predizioni utiliz- zando tutte le ipotesi contenute nello spazio delle ipotesi:

P (X|D = d) =X i P (X|d, hi)P (hi|d) = X i P (X|hi)P (hi|d)

ci`o richiede una somma (potenzialmente infinita) su l’intero spazio delle ipo- tesi; computazionalmente questo approccio `e inapplicabile in numerosi casi, ma offre comunque uno standard al quale confrontare gli altri metodi di apprendimento.

Maximum a Priori

Per diminuire l’impatto computazionale possiamo comunque utilizzare il teorema di Bayes per calcolare l’ipotesi pi`u probabile basandoci su ogni singolo dato di esempio a disposizione; l’ipotesi pi`u probabile cos`ı calcolata `e chiamata MAP, da maximum a posteriori :

hM AP = argmax h∈H P (h|d) ≡ argmax h∈H P (d|h)P (h) P (d) ≡ argmaxh∈H P (d|h)P (h)

il termine P (d) `e stato semplificato dato che `e una costante indipenden- te dall’ipotesi. L’ipotesi selezionata viene utilizzata per effettuare la previ-

CAPITOLO 4. MACHINE LEARNING

sione ((P (X|hM AP); tali predizioni sono approssimativamente bayesiane se

P (X|d) ≈ P (X|hM AP); si pu`o notare come questo sia vero all’aumentare

dei dati di esempio disponibili. MAP `e utilizzato nell’algoritmo Brute-Force MAP, che prevede il calcolo della probabilit`a a posteriori di tutte le ipotesi e la scelta di quella con probabilit`a pi`u alta.

Maximum Likelihood

Nel caso in cui tutte le ipotesi possibili abbiano la stessa probabilit`a possiamo prendere in considerazione esclusivamente il termine P (d|h) per trovare l’ipotesi pi`u probabile (questa probabilit`a `e chiamata likelihood di d data l’ipotesi h); questa ipotesi `e chiamata ML (da maximum likelihood ):

hM L = argmax h∈H

P (d|h)

tale ipotesi `e poi utilizzata per la previsione (P (X|hM L)). Le previsioni

effettuate con ML sono una buona approssimazione delle MAP se ci sono molti esempi di allenamento e non c’`e una preferenza iniziale tra le ipotesi; si pu`o dire che l’approccio ML sia data driven. Se abbiamo un grande insieme di dati di esempio le probabilit`a a priori diventano pressoch`e ininfluenti, altrimenti questo approccio non offre una valida alternativa.

Classificatori Bayesiani

L’approccio bayesiano si presta anche ai problemi di classificazione; per trovare la classificazione pi`u probabile potremo pensare ad un approccio MAP, ma possiamo vedere che esso non `e l’idea migliore. Ad esempio, pen- siamo ad uno spazio delle ipotesi contenente le tre ipotesi h1, h2, h3 con

probabilit`a a posteriori 0.4, 0.3, 0.3 ; h1`e quindi l’ipotesi MAP. Supponiamo

di avere una nuova istanza x, che `e classificata positiva da h1 ma negativa da

CAPITOLO 4. MACHINE LEARNING

vera `e 0.4 e che sia falsa `e 0.6 quindi la classificazione MAP `e diversa da quella pi`u probabile.

La pi`u probabile classificazione bayesiana `e data da:

C_{OP T}∗ = argmax cj∈C P (cj|d) = argmax cj∈C X i P (cj|hi)P (hi|d)

e tutti i sistemi che usano tale approccio sono chiamati classificatori baye- siani ottimi ; questo metodo massimizza la probabilit`a che la classificazione effettuata sia corretta, e nessun altro metodo di classificazione pu`o avere risultati migliori in media.

I classificatori bayesiani ottimi possono essere computazionalmente pesan- ti, dato che `e necessario calcolare la probabilit`a a posteriori di ogni ipotesi e poi combinare le predizioni di ogni ipotesi per classificare una istanza; una alternativa approssimata `e offerta dall’algoritmo di Gibbs, che prevede di sce- gliere casualmente una ipotesi tra quelle contenute nello spazio delle ipotesi, secondo la distribuzione di probabilit`a della probabilit`a a posteriori corrente, ed usarla per effettuare la classificazione dell’istanza. Sorprendentemente, sotto alcune condizioni il numero di errori di classificazione `e al massimo il doppio rispetto a quello di un classificatore bayesiano ottimo.

Una alternativa molto popolare ai classificatori bayesiani precedenti `e da- ta dal classificatore bayesiano naive; esso `e applicabile a problemi di classifi- cazione dove le istanze di input siano definite da un insieme di attributi con il relativo valore (x =< a1, · · · , aI, · · · , aL>). Una istanza viene classificata

assegnandogli la classe pi`u probabile: CN B = argmax

cj∈C

P (cj|a1, · · · , aL)

che tramite il teorema di Bayes `e possibile riscrivere come: CN B = argmax

cj∈C

CAPITOLO 4. MACHINE LEARNING

Per stimare il primo termine della precedente formula `e necessario un insie- me di dati di esempio molto grande; la stima risulta computazionalmente pesante ma `e possibile semplificare il problema assumendo che gli attribu- ti siano condizionalmente indipendenti data la classificazione cj (condizione

naive bayes). La formula pertanto pu`o essere riscritta come:

CN B = argmax cj∈C P (cj) L Y I=1 P (aI|cj)

In sintesi, il metodo prevede una fase di allenamento nella quale vengono stimati i valori di P (cj) e P (aI|cj) tramite le frequenze calcolate sui dati di

esempio; l’insieme di queste stime corrisponde alle ipotesi apprese. Le ipotesi cos`ı apprese vengono quindi utilizzate per effettuare la classificazione delle nuove istanze. Se la condizione naive bayes viene rispettata la classificazione `e equivalente al metodo MAP.

Reti Bayesiane

Le reti bayesiane esprimono la distribuzione di probabilit`a che guida un insieme di variabili specificando un insieme di assunzioni di indipendenza condizionale tra alcune di esse assieme ad un insieme di probabilit`a condizio- nate tra le altre; offre un approccio meno restrittivo rispetto al classificatore naive bayes e meno computazionalmente pesante rispetto al classificatore bayesiano ottimo.

Formalmente una rete bayesiana rappresenta la distribuzione di proba- bilit`a congiunta per un insieme di variabili. Consideriamo un insieme di variabili Y1· · · Yn che assumono un valore nell’insieme dei valori V (Yi); defi-

niamo come joint space per le variabili Yi il prodotto V (Y1)xV (Y2)x · · · x(Yn)

e come distribuzione di probabilit`a congiunta la distribuzione di probabilit`a sul dato spazio.

Un tipico approccio all’apprendimento tramite una rete bayesiana di strut- tura conosciuta `e dato dal parameter learning, che ha come obiettivo quello

CAPITOLO 4. MACHINE LEARNING

di trovare la migliore ipotesi regolata da uno o pi`u parametri; ad esem- pio hθ : la percentuale di lanci della moneta che danno testa `e θ. Una volta

definita l’ipotesi si calcolano le usuali probabilit`a bayesiane:

• a priori P (hθ) = P (θ),

• likelihood P (d|hθ) = P (d|θ),

• a posteriori P (hθ|d) = P (θ|d).

Se le ipotesi sono equiprobabili la scelta della miglior ipotesi pu`o essere effet- tuata tramite una stima ML (θM L = argmaxθ∈ΘP (d|θ)); l’ipotesi ottenuta

pu`o essere utilizzata anche per risolvere problemi di classificazione tramite l’approccio naive bayes. Nel caso in cui i dati a disposizione siano incompleti (ad esempio ci siano varibili non osservate) e non permettano di calcolare correttamente le probabilit`a precedenti si utilizza l’algoritmo EM, che preve- de di completare i dati disponibili effettuando delle stime basate su ipotesi fatte sui dati mancanti (expectation) che verranno utilizzate per aggiornare i parametri θ del modello.

Se invece la struttura della rete bayesiana non `e conosciuta `e possibile costruirla (structure learning) determinando le dipendenze tra le variabili e calcolando le varie probabilit`a condizionate.