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
potrebbe essere considerato intelligente.
2
Dinamica dell’apprendimento
“Apprendere significa migliorare le prestazioni in un determinato
ambiente acquisendo conoscenza derivante dall’esperienza in tale
ambiente”.
Prestazioni
Ambiente
Conoscenza
Apprendimento
3
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
ulteriormente.
4
Apprendimento Induttivo
 Viene utilizzato per apprendere dei concetti espressi in
genere con delle regole la cui forma è: «nella situazione
X esegui l’azione Y».
situazione1

azione1

azionen
...
situazionen
situazionegen

azionegen
5
Apprendimento Induttivo
oggetto1 è un corvo 
...
oggetton è un corvo 
oggetto1 è nero
?x è un corvo

oggetton è nero
?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».
 Problema: trovare il giusto livello di approssimazione (le
osservazioni possono essere contraddittorie)
6
Apprendimento da Esempi: problemi
• 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
7
Apprendimento da Esempi: suddivisione degli esempi
• 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
8
Apprendimento da Esempi: analisi
• 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
9
Apprendimento da Esempi: suddivisione degli esempi
Training Set
Apprendimento
Validation
Set
Test Set
10
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
Pioggia
Nuvoloso
Sole
Gioca
>75%
Non Giocare
Umidità
Vento
sì
no
Non Giocare
Gioca
<=75%
Gioca
11
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.
(vedi anche http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html)
12
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?
13
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pi+ni)/(p+n) I(pi/(pi+ni),ni/(pi+ni))
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)
è il contenuto informativo (risoluzione di incertezza) di una corretta risposta
yes/no con probabilità P(p) e P(n) rispettivamente.
14
Alberi di Decisione
Esempio del ristorante: vale la pena attendere
la disponibilità di un tavolo ?
Alt
Bar
Fri/ Sa
Hu n
Patr
Rain
Re s
Wtim e Go al
yes
yes
no
yes
yes
no
no
no
no
yes
no
no
yes
yes
no
no
no
yes
yes
no
no
yes
yes
no
yes
no
yes
no
so m e
fu ll
so m e
fu ll
fu ll
so m e
n on e
no
no
no
no
no
yes
yes
yes
no
no
no
yes
yes
no
0 -1 0
3 0 -6 0
0 -1 0
1 0 -3 0
>6 0
0 -1 0
0 -1 0
YES
NO
YES
YES
NO
YES
NO
no
no
no
yes
so m e
yes
yes
0 -1 0
YES
no
yes
yes
no
fu ll
yes
no
>6 0
NO
yes
yes
yes
yes
fu ll
no
yes
1 0 -3 0 NO
no
no
no
no
n on e
no
no
0 -1 0
yes
yes
yes
yes
fu ll
no
no
3 0 -6 0 YES
NO
15
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
R(Bar) = R(Alt) = R(Rain) = 1
R(Fri/Sat) = 0.97928
R(WTime) = 0.79248
R(Hun) = 0.80429
G(Patr) = 0.54085
G(Bar) = G(Alt) = G(Rain) = 0
G(Fri/Sat) = 0.02072
G(WTime) = 0.20752
G(Hun) = 0.19571
Patrons è l’attributo che offre il maggior guadagno
….. e così via ricorsivamente per i livelli successivi
16
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.
17
Alberi di Decisione
Albero ‘ragionevole’ ma non
derivabile dagli esempi col criterio
di parsimonia
Patrons
none
full
some
No
Yes
>60
WaitTime
30-60
No
Alternate
no
No
yes
no
Bar
Yes
No
yes
Yes
Yes
yes
Yes
Yes
yes
no
Fri/Sat
no
0-10
Hungry
yes
Reservation
no
10-30
Alternate
no
Yes
yes
Raining
no
No
yes
Yes
18
Alberi di Decisione
Albero minimale derivabile dagli
esempi ma meno ragionevole
Patrons
none
No
full
some
Yes
>60
WaitTime
30-60
No
10-30
Fri/Sat
no
no
yes
No
Yes
0-10
Hungry
Yes
yes
no
Yes
Bar
no
Yes
yes
No
19
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.
 Potatura all’indietro.
20
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.
21
C4.5
 Programma freeware per la costruzione di alberi di
decisione
 Composto da 4 eseguibili




C4.5
C4.5rules
Consult
Consultr
genera un albero binario
genera regole derivate dall’albero
classifica usando l’albero
classifica usando le regole
 Scaricabile dal sito http://www.rulequest.com/Personal/
22
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
 si applica ID3 ricorsivamente ai successori.
23
C4.5
 Utilizza vari file




xxxxx.names
xxxxx.data
xxxxx.test
xxxxx.rules
definizione degli attributi
dati per la costruzione dell’albero (training set)
dati per la verifica delle prestazioni (test set)
regole derivate dall’albero corrispondente
 xxxxx.tree
 xxxxx.unpruned
miglior albero in forma binaria
albero generato dall’algoritmo prima della
potatura
24
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!!!)
25
C4.5
 xxxxx.data training set
 xxxxx.test test set
| attr1, attr2, attr3, ……., attrm
valattr1, valattr2, valattr3, …. valattrm, decisione
valattr1, valattr2, valattr3, …. valattrm, decisione
valattr1, valattr2, valattr3, …. valattrm, decisione
…..
valattr1, valattr2, valattr3, …. valattrm, decisione
| esempio1
| esempio2
| esempio3
| esempioN
26
C4.5
 Esempio (golf.names)
Play, Don't Play.
outlook: sunny, overcast, rain.
temperature: continuous.
humidity: continuous.
windy: true, false.
27
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
overcast, 81, 75, false, Play
rain, 71, 80, true, Don't Play
28
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
---------------Size
Errors
8
0( 0.0%)
After Pruning
--------------------------Size
Errors
Estimate
8
0( 0.0%)
(38.5%) <<
29