Apprendimento Automatico

Apprendimento Automatico

Tecniche ‘classiche’ di apprendimento

Stefano Cagnoni

In sostanza …..

 La capacità di apprendimento è fondamentale in un sistema intelligente per:

 Risolvere nuovi problemi (e includere la scoperta nella propria base di conoscenza)

 Non ripetere gli errori fatti in passato.

 Risolvere problemi in modo migliore o più efficiente.

 Avere autonomia nell’affrontare e risolvere problemi.

 Adattarsi ai cambiamenti dell’ambiente circostante.

 Un sistema senza queste caratteristiche difficilmente

Dinamica dell’apprendimento

Ambiente Conoscenza

Prestazioni

Apprendimento

“Apprendere significa migliorare le prestazioni in un determinato ambiente acquisendo conoscenza derivante dall’esperienza in tale ambiente”.

Definizione e Obiettivi

 Estrarre conoscenza dal ripetersi di situazioni

 esperienza stato comportamento

 Partendo da un minimo livello di conoscenza, utilizzare un metodo di apprendimento generale per acquisire, via via, nuova conoscenza.

 Partendo da un sistema che include già conoscenza

strutturata si cerca di incrementarla o strutturarla

Apprendimento Induttivo

 Viene utilizzato per apprendere dei concetti espressi in genere con delle regole la cui forma è: «nella situazione X esegui l’azione Y».

situazione₁  azione₁

...

situazione_n  azione_n

situazione_gen  azione_gen

oggetto1 è un corvo  oggetto1 è nero ...

oggetton è un corvo  oggetton è nero

?x è un corvo  ?xè nero

 Più in generale un algoritmo di apprendimento induttivo esegue il seguente compito: «dato un insieme di esempi (campioni) di f, definisci una funzione h (ipotesi) che approssima f».



Apprendimento Induttivo

• Gli esempi devono costituire un campione rappresentativo del problema

• Numero di esempi (ho abbastanza campioni ?)

• Distribuzione degli esempi (ho campioni distribuiti in modo tale da rappresentare ogni regione distinta dello spazio che descrivono ?)

In generale, problema non rimediabile e, soprattutto, non verificabile prima dell’apprendimento

• Gli esempi devono essere ‘corretti’

• Bisogna evitare contraddizioni o esempi palesemente errati

Non sempre possibile (es. segnale con rumore) ma rimediabile

Apprendimento da Esempi: problemi

• Per ovviare a tali problemi, gli esempi devono essere suddivisi in modo opportuno in insiemi ‘diversi’

• Training set, su cui avviene l’apprendimento

• Test set, contenente esempi non inclusi nel training set, su cui si verifica ciò che si è appreso

Se l’(algoritmo di) apprendimento dipende da parametri empirici

• Validation set, con funzioni simili al test set, ma finalizzato alla ricerca dei migliori parametri per l’algoritmo di apprendimento

Apprendimento da Esempi: suddivisione degli esempi

• Il confronto fra le prestazioni sul training set e sul test set serve a valutare il livello di generalizzazione dell’apprendimento.

• Una significativa differenza di prestazioni fra training set e test set può significare:

• Overfitting (l’algoritmo di apprendimento ha ‘imparato a memoria’ il training set e non le regole generali del processo di cui è un campionamento)

• La distribuzione statistica degli esempi nei due insiemi non è omogenea

• La percentuale di esempi errati è troppo elevata

• I valori dei parametri dell’algoritmo di apprendimento non sono corrretti

Apprendimento da Esempi: analisi

Apprendimento da Esempi: suddivisione degli esempi

Training Set Apprendimento Validation Set

Test Set

Alberi di Decisione

 Strutture ad albero in cui:

 I nodi rappresentano gli attributi su cui deve basarsi la decisione

 I rami rappresentano i valori dell’attributo da cui originano

 Le foglie rappresentano le decisioni Es. giocare o no a golf ? ^Tempo

Nuvoloso

Sole Pioggia

Vento Umidità

Gioca

Gioca Non Giocare

>75%

<=75%

sì no

Alberi di Decisione

 Come si opera per imparare dagli esempi la funzione di decisione basata sul valore degli attributi disponibili ?

 Usare l’attributo che meglio separa esempi positivi e negativi.

 Se l’attributo divide tutti gli esempi negativi da quelli positivi, allora abbiamo trovato la funzione.

 Altrimenti bisogna applicare il primo punto ricorsivamente sui sottoinsiemi generati fino a quel punto dall’algoritmo.

 L’iterazione termina anche nel caso in cui non sia stata trovata la funzione, ma non abbiamo più attributi da utilizzare per suddividere gli esempi. Questo può accadere se abbiamo:

 Dati scorretti / conoscenza incerta

 Informazioni insufficienti.

Alberi di Decisione

 Se troviamo una funzione che non usa tutti gli attributi ci possono essere problemi?

 Possibile sottoutilizzo delle informazioni disponibili

 L’albero creato è l’unico possibile? Se non lo è, è il migliore possibile?

 Se troviamo una funzione che usa tutti gli attributi ci possono essere problemi?

 Tutti gli attributi sono utilizzati per il loro effettivo contenuto informativo o

‘per far tornare le cose’ (overfitting) ?

 Come si scelgono gli attributi?

Alberi di Decisione

Approccio basato sulla teoria dell’informazione

 Bisogna scegliere prima quelli che hanno un valore informativo maggiore, ossia il migliore guadagno informativo:

Gain(A) = I(p/(p+n),n/(p+n)) - _ip_i+n_i)/(p+n) I(p_i/(p_i+n_i),n_i/(p_i+n_i)) i=1..N possibili valori di A

[ p/(p+n)  P(p), n/(p+n)  P(n) ] dove

I(P(p),P(n)) = -P(n)log2P(n) - P(p)log2P(p)

Alberi di Decisione

Esempio del ristorante: vale la pena attendere la disponibilità di un tavolo ?

Alberi di Decisione

Costruzione albero per il problema del ristorante Passo 1 (scelta della radice dell’albero):

I(p/(n+p),n/(n+p))=1 ho 6 esempi positivi e 6 negativi => max. incertezza R(Pat) = 0.45915 G(Patr) = 0.54085

R(Bar) = R(Alt) = R(Rain) = 1 G(Bar) = G(Alt) = G(Rain) = 0 R(Fri/Sat) = 0.97928 G(Fri/Sat) = 0.02072

R(WTime) = 0.79248 G(WTime) = 0.20752

R(Hun) = 0.80429 G(Hun) = 0.19571

Patrons è l’attributo che offre il maggior guadagno

Il “rasoio di Occam”

“Entia non sunt moltiplicanda praeter necessitatem”

(principio di parsimonia)

Adattando il principio,

“la descrizione più semplice è anche la più efficace”

Per gli alberi di decisione

“L’albero di decisione più piccolo che sia consistente con gli esempi ha la massima probabilità di identificare correttamente istanze del problema non incluse negli esempi”

Non sempre vero (spesso per colpa del training set), ma principio importante quando si deve ottenere una buona generalizzazione.

Alberi di Decisione

Yes

No WaitTime

Patrons

No Alternate Hungry Reservation Fri/Sat

Bar

Yes

Yes No Yes

Yes Alternate Yes Raining

none

yes

some full

>60 30-60 10-30 0-10

no no

no no

no no

no

yes yes

yes yes yes

yes

Albero ‘ragionevole’ ma non derivabile dagli esempi col criterio

di parsimonia

Alberi di Decisione

Yes

No WaitTime

Patrons

No Fri/Sat Hungry Yes

Yes

No

Yes Bar

none some full

>60 30-60 10-30 0-10

no no no

no yes yes

No

yes

Albero minimale derivabile dagli esempi ma meno ragionevole

Yes

Alberi di Decisione per Informazione Incerta

 I valori di un training set possono essere soggetti a rumore:

 Un insieme di attributi può essere erroneamente considerato insufficiente.

 Si genera un albero inutilmente complesso.

 Se si sa che il training set può contenere degli errori, possiamo limitarne la complessità usando due strategie:

 Potatura in avanti.

Alberi di Decisione per Informazione Incerta

 La potatura in avanti può decidere di non espandere un nodo in più nodi in base:

 al numero di istanze contenute nell’insieme corrispondente al nodo.

 alla loro ripartizione tra le classi corrispondenti ai possibili nodi figli, in funzione dei diversi attributi su cui basare la partizione.

 Esempio:

 Se abbiamo 100 istanze e l’unico attributo disponibile le divide in due classi di 99 e 1 elementi, possiamo decidere di non espandere il nodo ritenendo generata da un errore l’unica istanza della seconda classe.

 La potatura all’indietro genera tutto l’albero e poi decide quali nodi eliminare in base ad una stima empirica dell’errore di

classificazione.

C4.5

 Programma freeware per la costruzione di alberi di decisione

 Composto da 4 eseguibili

 C4.5 genera un albero binario

 C4.5rules genera regole derivate dall’albero

 Consult classifica usando l’albero

 Consultr classifica usando le regole

C4.5

 Basato sull’algoritmo ID3 con alcune estensioni (gestione di attributi continui e pruning)

(http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/c4.5/tutorial.html)

 Basato sul guadagno di informazione

 Insieme finito di classi.

 A seconda che l’attributo sia simbolico o numerico i nodi generano

 un successore per ogni possibile valore

 una serie di successori divisi in base al confronto con una costante o all’appartenenza ad intervalli prefissati

 L’algoritmo inizia con tutti gli esempi, un insieme di possibili nodi test e la radice come nodo attuale. Finché gli esempi assegnati ad un certo nodo non appartengono alla stessa classe e ci sono attributi disponibili

 si sceglie il nodo col max guadagno informativo

 si genera l’insieme dei successori

 ogni esempio è assegnato al successore determinato dall’attributo scelto

C4.5

 Utilizza vari file

 xxxxx.names definizione degli attributi

 xxxxx.data dati per la costruzione dell’albero (training set)

 xxxxx.test dati per la verifica delle prestazioni (test set)

 xxxxx.rules regole derivate dall’albero corrispondente

 xxxxx.tree miglior albero in forma binaria

 xxxxx.unpruned albero generato dall’algoritmo prima della potatura

C4.5

 xxxxx.names definizione degli attributi class1, class2, ….. classn. | classi attr1: val1attr1,val2attr1,….valmattr1.

attr2: continuous.

….

attrk: val1attrk,val2attrk,….valmattrk.

(NB INSERIRE un <cr> dopo l’ultima riga!!!)

C4.5

 xxxxx.data training set

 xxxxx.test test set

| attr1, attr2, attr3, ……., attrm

valattr1, valattr2, valattr3, …. valattrm, decisione | esempio1 valattr1, valattr2, valattr3, …. valattrm, decisione | esempio2 valattr1, valattr2, valattr3, …. valattrm, decisione | esempio3

…..

valattr1, valattr2, valattr3, …. valattrm, decisione | esempioN

C4.5

 Esempio (golf.names) Play, Don't Play.

outlook: sunny, overcast, rain.

temperature: continuous.

humidity: continuous.

windy: true, false.

C4.5

 Esempio (golf.data)

sunny, 85, 85, false, Don't Play sunny, 80, 90, true, Don't Play overcast, 83, 78, false, Play rain, 70, 96, false, Play

rain, 68, 80, false, Play

rain, 65, 70, true, Don't Play overcast, 64, 65, true, Play

sunny, 72, 95, false, Don't Play sunny, 69, 70, false, Play

rain, 75, 80, false, Play sunny, 75, 70, true, Play overcast, 72, 90, true, Play

C4.5

 Output del programma

C4.5 [release 8] decision tree generator Tue May 11 15:37:34 2004 ---

Options:

File stem <golf>

Read 14 cases (4 attributes) from golf.data Decision Tree:

outlook = overcast: Play (4.0) outlook = sunny:

| humidity <= 75 : Play (2.0)

| humidity > 75 : Don't Play (3.0) outlook = rain:

| windy = true: Don't Play (2.0)

| windy = false: Play (3.0)

Evaluation on training data (14 items):

Before Pruning After Pruning

--- ---

Size Errors Size Errors Estimate

8 0( 0.0%) 8 0( 0.0%) (38.5%) <<