Apprendimento automatico (machine learning)

X

R(d) = r(h)p(h)

h∈H T

dove p(h) = N (h)/N è la proporzione di osservazioni presenti nel nodo-foglia

h dell’albero caratterizzato da H .

t

A seconda della natura dell’albero, r(h) viene definito:

10

ˆ Alberi di classificazione: tasso di errata classificazione.

‚ ƒ

E’ il rapporto tra il numero di osservazioni etichettate correttamente e il

totale delle osservazioni N

h

1 X I[d(x )]

R(h) = i

N

h i=1

·

dove I[ ] = 1 se l’espressione contenuta è vera (se l’osservazione x è stata

i

classificata correttamente), 0 altrimenti.

ˆ alberi di regressione: errore di previsione.

1 X 2

−

(y ŷ )

R(h) = i i

N

h h∈H T

Il calcolo del tasso di errata classificazione o l’errore di previsione si basa su

osservazioni che non siano state utilizzate per la costruzione dell’albero. I

dati a disposizione vengono dunque suddivisi:

- Campione di apprendimento (training set): osservazioni utilizzate per co-

struire l’albero.

- Campione test (test set): osservazioni utilizzate per valutare la regola di

decisione dell’albero.

Come scelgo gli attributi?

La selezione si basa sulla minimizzazione della profondità dell’albero risul-

tante. Un attributo perfetto suddivide gli esempi in insiemi tutti positivi o

tutti negativi. Dato che risulta difficile trovare un attributo completamente

positivo o negativo, sceglieremo quello ”abbastanza buono” e quello ”davvero

inutile”.

Una misura adeguata è la quantità di informazione fornita dall’attributo. Si

misura il contenuto informativo in BIT che è sufficiente a rispondere ”si” o

”no” ad una domanda su cui non si sa nulla.

4.2 parametri per guidare la costruzione dell’albero

p p n n

p

→ − −

Entropia I( )= log ( ) log ( )

2 2

p + n p + n p + n p + n p + n

Il test di un singolo attributo A non ci darà molta informazione. Posso

misurare tale quantità dopo aver eseguito il test. Ogni attributo A divide

11

l’insieme di addestramento E nei sottoinsiemi E , ..., E presumendo che A

1 v

possa avere v valori distinti.

Ogni insieme E ha p esempi positivi e n esempi negativi.

i i i

v p n

p + n

X i i

i i

→

Resto(A) I( , )

p + n p + n p + n

i i i i

i=1 n

p −

− → , ) Resto(A)

InformationGain(A) Guadagno I( p + n p + n

Se un attributo ha molti valori, la misura del guadagno di informazione for-

nisce un’indicazione inappropriata della sua utilità.

Potremmo identificare un attributo irrilevante o del tutto inutile. Una solu-

zione è L’indice di guadagno.

ID3 è costruito sul guadagno di informazione e non il gain ratio.

Un algoritmo di apprendimento è buono se produce ipotesi che riescono a

produrre con accuratezza la classificazione di esempi mai incontrati prece-

dentemente:

- raccogliere un grande insieme di esempi.

- divido in insieme di addestramento e insieme di test.

- applico algoritmo di apprendimento all’insieme di addestramento, generan-

do h ipotesi.

- misuro la percentuale di esempi classificati correttamente in h.

- ripeto 2 e 4 con insiemi di dimensioni diverse.

Grazie a questa procedura ottengo la qualità media della predizione in fun-

zione delle dimensioni dell’insieme di addestramento.

4.3 Vantaggi e svantaggi

Gli alberi di decisione sono caratterizzati da vantaggi e svantaggi:

ˆ Vantaggi:

- Possono gestire data set di grandi dimensioni.

- Possono gestire predittori di diversa natura (quantitativi e qualitativi).

- Consentono di trattare variabili ridondanti e valori mancanti.

- facilità di interpretazione di alberi di dimensioni contenute

ˆ Svantaggi:

- Difficoltà di interpretazione di alberi di grandi dimensioni.

- Rispetto ad altri metodi, le performance di previsione sono talora peggiori.

12

Alberi di grandi dimensioni ottenuti dal processo di splitting troppo ampio

con un numero elevato di foglie, sono responsabili dell’ iper-adattamento de-

gli alberi ai dati. L’albero ottimale, che minimizzi il misclassification rate

generale , ha meno foglie ed è quindi meno articolato. L’individuazio-

ne dell’albero ottimale avviene attraverso il processo di pruning (potatura),

mediante il quale si tagliano i rami dell’albero ottenuto dallo splitting,

riducendolo in modo opportuno.

Con quale criterio si effettua il pruning? Ogni splitting produce due effetti:

1) Rende più omogenee le foglie.

2) Aumenta la complessità dell’albero, rendendolo meno interpretabile e me-

no robusto quando applicato sui dati nuovi.

L’idea è di ridurre l’albero cercando un compromesso tra omogeneità del-

le foglie e complessità.

Quindi, il criterio di eliminazione di un ramo consiste nel valutare se la

maggiore eterogeneità delle foglie dell’albero ottenuto potando quel ramo è

compensata dalla sua minore complessità.

La scelta dell’albero migliore dipende sia dall’accuratezza che dalla taglia

di quest’ultimo: |

R (T ) = R(T ) + α|

T

α e | |

dove R(T) è il tasso di errata classificazione o previsione, T è il numero di

e

foglie (nodi terminali) dell’albero e α è il parametro di complessità.

Il parametro α misura la complessità dell’albero in base al numero di nodi

terminali. Sia T il sottoalbero dell’albero T che minimizza R (T )

α max α

R(T ) = min r (T )

α α

⊂T

T max

Più elevato è il valore di α, più piccola sarà la taglia dell’albero migliore.

Qualche osservazione finale sugli alberi di decisione:

ˆ Gli alberi di classificazione forniscono anche misure di importanza delle va-

riabili, cioè consentono di valutare quanto una variabile discrimina fra classi.

In questo senso possono aiutare ad interpretare il meccanismo che genera

l’outcome.

ˆ Tuttavia, essi rimangono strumenti black-box , più orientati alla previ-

sione che alla spiegazione.

ˆ Gli alberi sono piuttosto instabili, nel senso che ricostruendo alberi diffe-

renti su campioni estratti dalla medesima popolazione, si possono ottenere

13

strutture molto diverse, (ma con Misclassification Rate simile).

ˆ In realtà, oggi gli alberi sono superati da strumenti meno euristici, che ne

sfruttano il principio, ma che hanno performance più solide: le foreste casuali.

14

5 PAC

Capacità computazionale (teoria della computabilità), ragionamento/deduzione

(logica formale), apprendimento/deduzione.

Teoria dell’apprendibile:

Le macchine possono imparare intere categorie di concetti e queste possono

essere caratterizzate, le categorie di concetti sono appropriate e non banali

per una conoscenza a scopo generale, il processo computazionale con il quale

la macchina costruisce i programmi desiderati richiede un numero di passi

”fattibile”.

Si cercano leggi generali che vincolano l’apprendimento induttivo, relativo

alla probabilità di successo dell’apprendimento, numero di esempi forma-

tivi, complessità dello spazio d’ipotesi, accuratezza con la quale il concetto

obiettivo è approssimato, maniera in cui gli esempi formativi sono presentati.

Come si può essere certi che il proprio algoritmo di apprendimento abbia

predetto una teoria capace di predire correttamente il futuro?

Come facciamo a sapere quindi che l’ipotesi h è abbastanza vicina alla fun-

zione obiettivo f se non conosciamo f ? →

Teoria dell’apprendimento computazionale Ogni ipotesi gravemente

erronea sarà quasi certamente ”scovata” dopo un piccolo numero di esempi,

poichè sbaglierà una previsione. Di conseguenza, è improbabile che un’ipotesi

consistente con un insieme di esempi di addestramento sufficientemente gran-

de sia gravemente erronea: sarà probabilmente approssimativamente corretta

→

(PAC questione principale: collegamento tra esempi di training e test).

→ sull’insieme di

Vogliamo che l’ipotesi sia approssimativamente corretta

test.

I 2 insiemi sono estratti casualmente e indipendentemente dalla stessa popo-

lazione, con la stessa distribuzione di probabilità (ipotesi di stazionarietà).

Senza questa ipotesi, la teoria non potrebbe dire nulla sul futuro, dato che

non ci sarebbe alcuna connessione con il passato.

Notazioni:

→

- X Insieme di tutti i possibili esempi.

→

- D Distribuzione da cui sono presi gli esempi.

→

- H Insieme delle possibili ipotesi.

→

- N Numero di esempi nell’insieme di addestramento.

15

Presumiamo che la funzione vera f sia un membro di H.

Definiamo l’errore di un’ipotesi h rispetto alla funzione f data da una distri-

buzione D sugli esempi. 6

errore(h) = P r(h(x) = f (x)) con x preso da D ≤

Un’ipotesi h si dice approssimativamente corretta se errore(h) ε con ε

che corrisponde ad una costante piccola. Voglio dimostrare che dopo aver

considerato N esempi, ci sarà un’altra probabilità che tutte le ipotesi consi-

stenti siano approssimativamente corrette. ∈

Posso calcolare la probabilità che un’ipotesi ”gravemente errata” h H

b bad

≥

sia consistente con i primi N esempi. Sappiamo che errore(h) ε, di con-

seguenza la probabilità che si accordi con un altro esempio è pari almeno a

−

1 ε. N

≤ −

Quindi il limite per N esempi è P r(h con N esempi) (1 ε) .

b

Voglio ridurre questa probabilità sotto un certo numero piccolo δ:

1

1

−ε

N

|H|(1 − ≤ − ≤ → ≥ (ln + ln|H|)

ε) δ dato che 1 ε e N ε δ

Se un algoritmo di apprendimento restituisce un’ipotesi consistente con que-

sto numero di esempi, c’è una probabilità pari almeno a 1−δ che il suo errore

sia al massimo ε (ipotesi AC). →

Il numero di esempi in funzione di ε e δ complessità di campiona-

mento dello spazio delle ipotesi.

Il problema è la dimensione dello spazio delle ipotesi.

n

|H| = 2 , numero di tutti i possibili esempi.

Per ogni esempio mai incontrato prima, lo spazio conterrà tante ipotesi con-

sistenti che predicono il risultato positivo quante ipotesi che predicono uno

negativo.

La teoria si concentrava nei primi anni ’60 sul problema di identificazione al

limite.

Secondo questo approccio, un algoritmo di identificazione deve re-

stituire un’ipotesi che corrisponde esattamente alla funzione reale.

- ordino le ipotesi in H secondo una misura di semplicità.

- scelgo l’