Intelligenza Artificiale
Apprendimento automatico (generalizzare
l’esperienza)
Prof. M.T. PAZIENZA
a.a. 2004-2005
Ipotesi di base associate all’aa
Problema della generalizzazione
e di come un sistema possa identificare in
modo sicuro pattern invarianti nei dati tali
da supportare con essi la soluzione
intelligente di future istanze di problemi
dello stesso tipo
Ipotesi di base associate all’aa
Polarizzazione induttiva dell’apprendimento
e di come un progettista di sistema usi la propria intuizione
e le proprie euristiche nella definizione delle
rappresentazioni, dei modelli e degli algoritmi che
supportano il processo di apprendimento (es. definizione
di concetti “importanti” all’interno di un dominio, la
scelta di un particolare algoritmo di ricerca, …)
Ipotesi di base associate all’aa
Problema dell’induzione
e di come un progettista di sistema usi le proprie euristiche
per generalizzare (spesso i dati utilizzabili non sono
sufficienti a garantire una ottima generalizzazione,
indipendentemente dall’algoritmo usato): seleziona gli
aspetti che la sua esperienza considera siano efficaci
anche nel futuro.
Apprendimento
L’elettricità è come l’acqua.
Inferenza (riconoscere l’analogia)
Così come l’acqua scorre attraverso una tubatura, l’elettricità scorre in un
cavo
Come per l’acqua, è possibile misurare la quantità di energia (corrente) e la
pressione del flusso (tensione).
Diversamente dall’acqua, l’elettricità non rende le cose umide e non ci è di
alcuna utilità per lavare oggetti.
L’interpretazione delle analogie implica il riconoscimento delle similarità e
differenze per evitare inferenze false o prive di significato.
Apprendimento
Apprendimento: estrazione di informazione
profonda (non superficiale) da un tipo di
situazione ripetutasi più volte.
L’esperienza può modificare lo stato di un
organismo in modo tale che il nuovo stato rende
il sistema capace di funzionare meglio in una
situazione successiva.
Apprendimento
L’esperienza accumulata attraverso le percezioni
dell’agente serve per migliorare la capacità del
sistema di agire in futuro.
Esperienza -> nuovo stato -> prestazioni
L’apprendimento ha luogo:
• come risultato dell’interazione tra l’agente ed il
mondo
• dall’osservazione da parte dell’agente del modo
in cui egli stesso prende decisioni
Apprendimento
Psicologia comportamentale: gli uomini nascono
senza sapere nulla ed “assorbono” ogni
conoscenza dall’osservazione di situazioni
ripetitive.
Scienze cognitive: affinché un organismo possa
imparare qualunque cosa, è necessario che egli
già conosca qualcosa. Si applica anche alla
linguistica.
Apprendimento concettuale
Apprendimento induttivo od induzione
L’output dell’apprendimento induttivo si presenta come
un insieme di regole di produzione del tipo:
If <circumstances>
then <do action, or conclude something>
La parte destra della regola si chiama concetto, la parte
sinistra definizione del concetto o pattern
(Una regola è un pezzo di conoscenza, qualcosa che il
programma deve sapere)
Apprendimento concettuale
Apprendimento induttivo od induzione
Da una o più istanze in cui una azione specifica (iesima)
risulta essere l’azione appropriata in risposta ad una
particolare situazione (iesima),
si inferisce che la versione generale della stessa azione è
l’azione (gener) più appropriata alla situazione (gener)
Il problema è verificare
se ed in che senso
una conclusione generale può scaturire da osservazioni
specifiche
Apprendimento concettuale
Fare il debug di una regola if-then significa rendere
l’antecedente più generale (weakening) o più
specifico (strengthening) a seguito della verifica
di quanto bene la versione corrente funziona
Si dice che l’antecedente è più forte se dice di più
ovvero se è vero in un numero minore di
situazioni.
Altrimenti si dice che è più debole.
Apprendimento concettuale
Quando una regola non viene confermata, allora
si cerca di specializzarla, ovvero la si può
applicare in un numero minore di situazioni
Nella situazione inversa la regola può essere
generalizzata.
Si possono avere casi di overgeneralizzazione.
Apprendimento concettuale
Il problema è trovare un pattern, o una definizione
concettuale che si applichi ad un set di situazioni (istanze
positive di un concetto), e non si applichi ad altre (istanze
negative)
Ovvero: generalizzare dagli esempi positivi fino ad un
pattern generale che non comprenda alcuna delle istanze
negative.
L’algoritmo di apprendimento per generalizzazione –
specializzazione è un algoritmo empirico
Un arco e la sua rappresentazione grafica
arch
part
brick
supports
part
brick
supports
part
brick
Un altro arco e la sua rappresentazione grafica
arch
part
brick
supports
part
brick
supports
part
pyramid
Conoscenza di base
(mattoni/rettangoli e piramidi sono esempi di poligoni
polygon
isa
brick
isa
pyramid
Generalizzazione che comprende entrambi gli esempi
arch
part
brick
supports
part
brick
supports
part
polygon
Rappresentazione generale di un arco
Esempio limite di arco e sua rappresentazione
part
brick
touch
arch
supports
touch
part
brick
part
polygon
supports
Descrizione specifica di un arco che escluda gli esempi al limite
part
brick
must-not-touch
arch
supports
must-not-touch
part
brick
part
polygon
supports
Generalizzazione /Specializzazione
La generalizzazione e la specializzazione sono operazioni
inverse.
Ciascun metodo di general./special., quindi, può essere
descritto come una progressione che funziona in ciascuna
delle due direzioni.
Le variabili sono più generali delle costanti, quindi nel
processo di generalizzazione delle regole di produzione
verranno usate variabili al posto delle costanti
Generalizzazione /Specializzazione
La generalizzaz. e la specializzaz. forniscono un
insieme di metodi per modificare le regole. Ciò
non basta in quanto oltre a conoscere la direzione
della modifica, bisogna sapere come modificare.
Si tratta di un problema di ricerca complesso in
quanto la correttezza di un’azione nella direzione
della generalizzaz. o della specializzaz. non può
essere valutata finché non si raggiunge il risultato
finale. Sono così possibili passi falsi.
Generalizzazione /Specializzazione
Esistono più direzioni di generalizzazione (problema):
i predicati e le classi tendono a raggrupparsi in
“famiglie” con più o meno membri
(generalizzazione in gerarchie is-a)
Due modalità per rendere più debole o più forte un
pattern sono rispettivamente:
Disjunct manipulation
+ generale
Conjunct manipulation
+ specifica
Generalizzazione /Specializzazione
Un ulteriore metodo di generalizzazione è data
dall’universalizzazione che, da liste di formule
specifiche, ricava combinazioni quantificate.
Es.
Il libro 1 è sul tavolo
Il libro 2 è sul tavolo
……
Il libro i è sul tavolo
Qualunque cosa sia sul tavolo deve essere un libro
Generalizzazione /Specializzazione
Necessità di definire cosa si intende con situazione corrente
Non è:
insieme delle conoscenze del sistema (che comprende
passato, presente e aspettative)
Definire le caratteristiche della situazione che devono essere
ignorate nella modifica delle regole costituisce l’attività
di “identificazione della situazione”. In casi reali
esistono migliaia di fatti veri ma irrilevanti per la
situazione.
Generalizzazione /Specializzazione
Problema della descrizione dei fatti
La notazione usata per esprimere le definizioni dei
concetti deve avere la proprietà che:
Situazioni simili devono avere descrizioni simili
nella notazione
In tal modo possiamo sperare che una
generalizzazione possa catturare tutte le istanze
positive
Generalizzazione /Specializzazione
Problema dell’ assegnazione di credito
Conoscere possibili errori compiuti in precedenti
situazioni simili permette al sistema di
generalizzare meglio
Effettuare ripetuti esperimenti
Chiedere ad un esperto
Queste informazioni costituiscono le basi per
definire metodologie di apprendimento.
Apprendimento: fattori principali
Il progetto di un task di apprendimento automatico è
caratterizzato da:
1. Le componenti atte a selezionare le azioni rilevanti
(che hanno un impatto sull’ambiente)
2. La modalità di rappresentazione delle componenti (es.
descrizioni deterministiche, formule proposizionali,
descrizioni probabilistiche,…)
3. La descrizione del feedback ammesso (apprendimento
supervisionato versus apprendimento non
supervisionato, apprendimento per rinforzo)
4. La descrizione delle informazione precedenti
disponibili (se c’è, la conoscenza a priori, aiuta..)
Apprendimento induttivo
Chiamiamo esempio una coppia (x,f(x)) in cui
x è l’ingresso ed f(x) è il risultato della
funzione applicata ad x.
L’inferenza induttiva, o induzione, è tale per
cui, data una collezione di esempi di f,
restituisce una funzione h che approssima f
La funzione h è chiamata ipotesi
Apprendimento induttivo
Per ogni f esiste un numero elevato di ipotesi h consistenti
con gli esempi.
Ciascuna preferenza per un’ipotesi piuttosto che per
un’altra (al di là della consistenza degli esempio in ogni
caso acclarata) rappresenta una inclinazione del
sistema.
Tutti gli algoritmi di apprendimento automatico
presentano una propria inclinazione.
Apprendimento induttivo
La scelta della rappresentazione per la funzione
desiderata è cruciale.
Esiste una ovvia contrapposizione tra:
espressività (la funzione desiderata è
rappresentabile con il linguaggio stesso)
efficienza (il problema dell’apprendimento è
trattabile se si sceglie un certo linguaggio di
rappresentazione)
Alberi di decisione/decision tree
Gli alberi di decisioni permettono di determinare la classificazione
di un oggetto andando a controllare i suoi valori rispetto a certe
proprietà.
In un albero di decisione ciascun nodo interno rappresenta un test
su qualche proprietà; ciascun possibile valore di quella proprietà
corrisponde ad (seleziona) un ramo dell’albero.
I nodi foglie rappresentano la classificazione.
Un elemento sconosciuto può essere classificato attraversando
l’albero: ad ogni nodo interno, test del valore individuale per la
proprietà ed individuazione del ramo specifico, fino alla foglia
(=classificazione); non tutte le proprietà vengono testate per
arrivare alla classificazione.
Alberi di decisione
Un albero di decisione ha in ingresso una situazione
od un oggetto descritto da un insieme di proprietà
ed in uscita una “decisione” del tipo si/no
(rappresentano funzioni booleane).
Ogni nodo rappresenta un test sul valore delle di una
proprietà e gli archi uscenti da un nodo esprimono
con la loro etichetta i possibili valori del test
Ciascuna foglia dell’albero specifica il valore
booleano in output
Alberi di decisione
Gli alberi di decisione possono rappresentare molte
funzioni con alberi di dimensioni più piccole
Un’istanza (un esempio) è descritta dai valori degli
attributi e dal valore del predicato obiettivo.
Il valore del predicato obiettivo si chiama
classificazione dell’esempio. Predicato con valore
vero: esempio positivo, con valore falso: esempio
negativo
L’insieme completo degli esempi si chiama insieme
di addestramento
Alberi di decisione
Si può costruire un albero di decisione che sia consistente
con l’insieme di addestramento e che sia anche conciso
(schema = + piccolo albero di decisione).
Rasoio di Ockham (William di Occam, 1324):
L’ipotesi più probabile è la più semplice che sia consistente
con tutte le osservazioni
<=> a parità di altre circostanze, un’ipotesi semplice che sia
consistente con tutte le osservazioni ha una probabilità di
essere corretta maggiore di una complessa
Alberi di decisione
Si può costruire un albero di decisione in un
approccio top-down
Si aggiungono test all’albero: si individua un
sottoalbero ad ogni test e si continua la ricerca;
non c’è backtracking
L’algoritmo è molto efficiente, e dipendente dal
criterio usato per selezionare le proprietà da
testare.
Alberi di decisione
Dopo che il test sul primo attributo ha suddiviso gli esempi, ciascuno
dei risultati è in se stesso un nuovo problema di apprendimento di
un albero di decisione con meno esempi e un attributo in meno.
(ricorsione)
• Con esempi + e – si sceglie l’attributo migliore per suddividerli
• Se rimangono solo esempi + (o -) , allora fine
• Se non ci sono più esempi, vuol dire che nessun esempio con quei
valori per gli attributi è stato osservato
• Se non ci sono più attributi, e ci sono esempi + e -, significa che
questi esempi hanno la stessa descrizione ma classificazioni diverse
(dati errati, costituiscono il rumore), oppure che gli attributi scelti
non descrivono completamente la situazione
Alberi di decisione
costruire un albero di decisione in un approccio top-down (ID3)
Function induce_tree(example_set, Properties)
begin
if all entries in example_set are in the same class
then return a leaf node labeled with that class
else if Properties is empty
then return leaf node labeled with disjunction of all classes
in example_set
else begin
select a property, P, and make it the root of the current tree;
delete P from Properties;
for each value, V, of P,
begin
create a branch of the tree labeled with V;
let partition-v be elements of example_set with values V for
property P;
call induce_tree (partition-v, Preoperties), attach results to
branch V
end
end
end
Alberi di decisioni
• Insiemi di apprendimento
• Insiemi di test
Caratteristiche degli algoritmi di aa
Dati ed obiettivi dell’algoritmo di
apprendimento
Rappresentazione della conoscenza appresa
Set di operazioni utilizzate
Spazio di definizione dei concetti potenziali
Ricerca euristica utilizzata