Dipartimento di Ingegneria dell’Informazione
Università degli Studi di Parma
Intelligenza Artificiale
Apprendimento
Agostino Poggi
Stefano Cagnoni
Introduzione
 La capacità di apprendimento è fondamentale in un sistema
“intelligente” per:




Risolvere nuovi problemi.
Non ripetere gli errori fatti in passato.
Risolvere problemi in modo migliore o più efficiente.
Avere autonomia nell’affrontare e risolvere problemi (in modo
indipendente da un esperto che fornisce la conoscenza).
 Adattarsi ai cambiamenti dell’ambiente circostante.
 Un sistema senza queste caratteristiche difficilmente potrebbe
essere considerato intelligente.
Apprendimento
2
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.
Apprendimento
3
Apprendimento Induttivo
 Viene utilizzato per apprendere dei concetti espressi in genere
con delle regole la cui forma è: «nella situazione X esegui
l’azione Y».
azione1
situazionen

...

situazionegen

azionegen
situazione1
Apprendimento
azionen
4
Apprendimento Induttivo
oggetto1 è un corvo
...
oggetton è un corvo

oggetto1 è nero

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
5
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
Ye s
no
no
no
no
yes
no
no
yes
yes
no
no
no
yes
Ye s
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
yes
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
YES
YES
NO
Esempi positivi : decisione YES
Esempi negativi: decisione NO
Apprendimento
6
Alberi di Decisione
Patrons
none
full
some
No
Yes
>60
WaitTime
30-60
No
Alternate
no
No
Apprendimento
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
7
Alberi di Decisione
 Come si opera per imparare dagli esempi la funzione di
decisione booleana che basata sul valore degli attributi ?
 Scegliere l’attributo che meglio separa gli esempi positivi da quelli
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 dall’algoritmo.
 L’iterazione termina anche nel caso in cui non abbiamo trovato la
funzione, ma non abbiamo più attributi da utilizzare per suddividere
gli esempi. Questo può accadere se abbiamo:
 Dati scorretti / conoscenza incerta
 Informazioni insufficienti.
Apprendimento
8
Alberi di Decisione
 Se troviamo una funzione che non usa tutti gli attributi ci
possono essere problemi?
 Possibile sotto utilizzo 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?
Apprendimento
9
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))
[ 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 di una corretta risposta yes/no con probabilità P(p) e P(n)
rispettivamente.
Apprendimento
10