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 più efficiente o migliore.
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 quasi nessuna conoscenza, attraverso un metodo di
apprendimento generale acquisire, via via, nuova conoscenza.
 Partendo da un sistema che include già conoscenza organizzata
si cerca di incrementarla o organizzarla 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
?x è un corvo


oggetto1 è nero

oggetton è nero
?x è nero
 Più in generale un algoritmo di apprendimento induttivo
esegue il seguente compito: «data un insieme di esempi
(campioni) di f, definisci una funzione h (ipotesi) che
approssima f».
Apprendimento
5
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
6
Alberi di Decisione
Alt
yes
yes
no
yes
Yes
no
no
Apprendimento
Bar
no
no
yes
no
no
yes
yes
Fri/Sa
no
no
no
yes
Yes
no
no
Hun
yes
yes
no
yes
no
yes
no
Pat
some
full
some
full
full
some
none
Rain
no
no
no
no
no
yes
yes
Res
yes
no
no
yes
yes
yes
no
Time
0-10
30-60
0-10
10-30
>60
0-10
0-10
Goal
yes
no
yes
yes
no
yes
no
7
Alberi di Decisione
 Come si fa a imparare dagli esempi la funzione booleana che
permette di decidere in funzione del 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:
 Dati scorretti.
 Informazioni insufficienti.
Apprendimento
8
Alberi di Decisione
 Se troviamo una funzione che non usa tutti gli attributi ci
possono essere problemi?
 Se troviamo una funzione che usa tutti gli attributi ci possono
essere problemi?
 Come si scelgono gli attributi?
Apprendimento
9
Alberi di Decisione
 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))
dove
I(P(n),P(p)) = -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
Alberi di Decisione
per Informazione Incerta
 I valori di un training set possono essere soggetti a rumore:
 Un insieme di attributi può essere 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.
Apprendimento
11
Alberi di Decisione
per Informazione Incerta
 La ricerca in avanti decide di 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.
 Ad esempio:
 Se abbiamo 100 istanze e l’unico attributo su cui possiamo lavorare li
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.
Apprendimento
12
Alberi di Decisione
per Informazione Incerta
 La ricerca all’indietro genera tutto l’albero e poi decide quali
nodi eliminare in base ad una stima euristica dell’errore di
classificazione.
 Sia:
Err(S) la probabilità di classificare erroneamente gli elementi
dell’insieme S.
Errore(nodo) = Err(S) se il nodo è una foglia.
ErroreCumulato(nodo) = ipiErrore(nodoi), dove nodoi è un figlio di
nodo.
 Allora si ha per i nodi non terminali:
Errore(nodo) = min(Err(nodo),ErroreCumulato(nodo))
Apprendimento
13
Generalizzazione e Specializzazione
 La generalizzazione e la specializzazione sono un ottimo
strumento per l’apprendimento:
(is ?x gatto)  possibile(accarezzare ?x)
(is ?x felino)  possibile(accarezzare ?x)
(and (is ?x felino) (piccolo ?x))  possibile(accarezzare ?x)
(and (is ?x carnivoro) (piccolo ?x))  possibile(accarezzare ?x)
 Tali strumenti vanno applicati finché non si trova una
definizione del concetto che descriva un insieme di situazioni
(istanze positive) e non si applichi ad altre (istanze negative).
Apprendimento
14
Generalizzazione e Specializzazione
 Se abbiamo la descrizione:
(su a1 a2) (su a1 a3) (not (a-contatto a2 a3) (parti a (a1 a2 a3))
(is a1 mattone) (is a2 mattone) (is a3 mattone)(is a arco)
 Problema di identificazione della situazione:
 Bisogna ignorare tutte le caratteristiche non interessanti.
 Problema della descrizione:
 Bisogna avere delle descrizioni adeguate.
 Bisogna utilizzare descrizioni simili.
Apprendimento
15
Generalizzazione e Specializzazione
 Le variabili sono più generali delle costanti:
(and (su ?x tavolo) (su ?y tavolo))
più specifica
(and (su ?x ?z) (su ?y tavolo))
(and (su ?x tavolo) (su ?y?z))
(and (su ?x ?z) (su ?y ?z))
(and (su ?x ?z) (su ?y ?v))
più generale
 Il problema di specializzazione diventa un problema di ricerca.
Apprendimento
16
Generalizzazione e Specializzazione
 Data la forma:
(su ?x tavolo)
 l’aggiunta di una clausola in ‘or’ generalizza:
(or (su ?x tavolo) (sospeso ?x soffitto))
 l’aggiunta di una clausola in ‘and’ specializza:
(and (su ?x tavolo) (a-contatto ?x parete1))
Apprendimento
17
Accoppiamento di Descrizioni
 Date le due descrizioni:
(su a1 a2) (su a1 a3) (not (a-contatto a2 a3)) (parti a (a1 a2 a3))
(is a1 mattone) (is a2 mattone) (is a3 mattone) (is a arco)
(su a1 a2) (su a1 a3) (not (a-contatto a2 a3)) (parti a (a1 a2 a3))
(is a1 cuneo) (is a2 mattone) (is a3 mattone) (is a arco)
 Il sistema deve accoppiare le due descrizioni:
(is a1 prisma) (or (is a1 mattone) (is a1 cuneo))
Apprendimento
18
Analogia
 Può essere che una situazione sia simile a situazioni passate e
che il modo in cui ci eravamo comportati possa aiutare a
decidere come comportarci adesso.
 Tuttavia non è un metodo che ci permette di generalizzare
facilmente.
 Problema 1: dato un segmento RY e due punti su di esso O e N
tali che valga RO = NY provare che RN = OY.
 Problema 2: dato un segmento AD e due punti su di esso C e B
tali che valga AB > CD provare che AC > BD.
Apprendimento
19
Valutazione
dell’Apprendimento Induttivo
 Non è in grado di gestire dati perturbati:
 Il maestro in certi casi imbroglia.
 In alcuni casi non si riesce ad individuare la regola responsabile del
fallimento.
 Non è capace di gestire concetti che cambiano nel tempo:
 Ad esempio per un animale il concetto «buon posto per cercare di
mangiare».
Apprendimento
20
Reinforcement Learning
 Si può imparare senza avere esempi di comportamento
corretto?
 Un caso in cui si può imparare senza esempi è quello in cui ad
ogni passo o al raggiungimento di uno stato finale viene
assegnato un premio (o una punizione).
 Esistono due classi di problemi in cui viene diviso il
reinforcement learning:
 Passive learning, muovendosi tra i diversi stati del mondo si impara
l’utilità di essere nei diversi stati.
 Active learning, in ogni stato bisogna eseguire un’azione imparando
l’utilità di eseguire una certa azione in un dato stato.
Apprendimento
21
Passive Learning
 Minimi quadrato medio:
Ui = average(Ui, reward-to-go(Ui)
 Programmazione dinamica adattiva:
U i= Ri + iMijUj
Se si conoscono le probabilità MiJ, non appena si conoscono i
premi dei vari stati è possibile calcolare l’utilità dei vari stati.
 Differenza temporale (TD Learning):
Ui = Ui + (Ri + Uj - Ui)
Se il valore di decresce al crescere del numero delle
iterazioni, allora Ui converge al valore corretto.
Apprendimento
22
Active Learning
 Il problema che deve risolvere è:
U i= Ri + maxaiMaijUj
 Il problema di calcolare Ui si può trasformare nel problema di
calcolare l’utilità di eseguire una certa azione in un dato stato.
 Infatti si ha:
U i= maxa Q(a,i) dove: Q(a,i) = Ri + iMaijmaxa’ Q(a’,j)
 Si può applicare il TD-Q Learning:
Q(a,i) = Q(a,i) + (Ri + maxa’ Q(a’,j) -Q(a,i))
Apprendimento
23
Apprendimento
Guidato da Insuccesso
 I concetti imparati vengono applicati ed in caso di errore gli
errori vengono utilizzati per la revisione dei concetti (Hacker).
(per-fare ?compito (ottieni (su ?x ?y))
(sposta ?x ?y)
(per-fare ?compito (ottieni (su ?x ?y))
(progn
(per-ogni ?z (su ?z ?x)
(liberati-di ?z))
(sposta ?x ?y)))
Apprendimento
24
Apprendimento
Guidato da Insuccesso
 In casi reali è poco plausibile che il sistema si possa rendere
conto in modo netto delle ragioni del fallimento.
 Con questo metodo è solo possibile imparare dei casi speciali
di concetti più generali, si può parlare di programmazione
automatica.
Apprendimento
25
Apprendimento
per Insegnamento Diretto
 L’insegnante comunica non solo se sta sbagliando o meno, ma
anche perché.
 Se l’insegnante non conosce la struttura interna del sistema:
 Deve essere il sistema che trasforma il suggerimento in una forma
utile.
 Il problema è come dare i suggerimenti:
 L’insegnante deve capire a che livello il sistema vuole i suggerimenti.
Apprendimento
26
Apprendimento
per Insegnamento Diretto
 Esempio di questo tipo di sistema è Teiresias.
 Teiresias opera all’indietro lungo la catena degli obiettivi fino a
che l’insegnante non riconosce un punto di malfunzionamento:
 Una regola ha determinato P, le premesse della regola sono vere, ma P
non segue da esse.
 P avrebbe dovuto essere determinata, ma ogni regola che poteva
determinare P non é stata applicata perché delle premesse non erano
vere.
 Nel primo caso il sistema deve specializzare la regola che ha
determinato P.
 Nel secondo, o viene introdotta una nuova regola o viene
generalizzata una regola.
Apprendimento
27
Apprendimento
mediante Esplorazione
 Metodo utilizzato da Eurisko e AM per la ricerca di
configurazioni e generalizzazioni nei domini dei circuiti VLSI,
dei giochi e della matematica elementare.
 Mantengono una base di dati contenente i concetti che
accrescono attraverso l’utilizzo di euristiche.
 Ad esempio, in AM ogni concetto è rappresentato da
una struttura a frame.
Apprendimento
28
Apprendimento
mediante Esplorazione
 Questi metodi esplorano (non ricercano) lo spazio del
problema sulla base di un’agenda di compiti da eseguire che
sono ordinati in ordine decrescente di interesse.
 Ad esempio, in AM il concetto insieme è definito:
Nome:
Specializzazioni:
Generalizzazioni:
Esempi:
Tipici:
Limite
Valore:
Apprendimento
insieme
insieme-vuoto, insieme-non-vuoto, ...
struttura-non-ordinata, ...
[[]], [A, B]
[]
600
29
Apprendimento
mediante Esplorazione
 Per creare nuovi concetti devono essere in grado di mutare i
concetti preesistenti.
 Ad esempio, AM utilizza un’euristica per la generalizzazione:
 Se il compito è generalizzare X allora considera la sua definizione D e
la sostituisco con una generalizzazione in base ai seguenti criteri:
 Se D è un concetto allora usa le sue generalizzazioni.
 Se D è una congiunzione allora elimina o generalizza una clausola-and.
 Se D è una disgiunzione allora aggiungi o generalizza una clausola-or.
 Se D è una negazione (not D’), specializza D’.
Apprendimento
30
Apprendimento
mediante Esplorazione
 Sono capaci di scoprire nuove congetture non di dimostrarle
(ad esempio, AM ipotizza che i numeri devono avere un’unica
fattorizzazione: scomposizione in fattori primi).
 Sono sistemi attivi e non passivi: generano essi stessi gli
oggetti su cui lavorare.
 Tuttavia hanno bisogno di una conoscenza iniziale.
 Ad esempio, AM ha scoperto il concetto di numero sulla base
delle definizioni di lista, di insieme e di sacco (insieme che
permette ripetizioni) e dell’uguaglianza in questi domini.
Apprendimento
31