Dipartimento di Ingegneria dell’Informazione
Università degli Studi di Parma
Intelligenza Artificiale
Apprendimento
Parte 2
Agostino Poggi
Stefano Cagnoni
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
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
Apprendimento
2
Alberi di Decisione
Costruzione albero per il problema del ristorante
Passo 2 (scelta dell’attributo per il primo livello):
I(p/(n+p),n/(n+p)) = 0.45915
R(Bar) = 0.45915
G(Bar) = 0
R(Alt) = R(Fr/S) = R(Rain)0.40456 G(Alt) = G(Fr/S) = G(Rain) = 0.05459
R(WTime) = R(Hun) =0.33333
G(WTime) = G(Hun) = 0.12382
WTime e Hungry sono gli attributi che offrono il maggior guadagno
Apprendimento
3
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.
Apprendimento
4
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.
Apprendimento
5
Alberi di Decisione
per Informazione Incerta
 La potatura 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) = P( j | xiS, i≠j) la probabilità di classificare erroneamente gli elementi
dell’insieme S.
 Per un nodo terminale
Errore(nodo) = Err(S)
 Per i nodi non terminali:
ErroreCumulato(nodo) = ipiErrore(nodoi), dove nodoi è figlio di nodo.
 Valutazione :
Si opera in modo tale da avere Errore(nodo) = min(Err(nodo),ErroreCumulato(nodo))
Cioè si decide se mantenere la ramificazione se la presenza di nodi figli riduce l’errore
Apprendimento
6
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)
[generalizzazione NON valida]
(and (is ?x felino) (piccolo ?x))  possibile(accarezzare ?x) [specializzazione valida]
(and (is ?x carnivoro) (piccolo ?x))  possibile(accarezzare ?x) [generalizzazione valida]
 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
7
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
8
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
9
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
10
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, cioè sostituire le parti che
differiscono con un versione che le accomuni:
(or (is a1 mattone) (is a1 cuneo))
Generalizzando: (is a1 prisma)
Apprendimento
11
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 in futuro.
 Tuttavia è un metodo che non 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
12
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 se
non enumerando tutte le possibili situazioni:
 Ad esempio per un animale il concetto «buon posto per cercare di
mangiare».
Apprendimento
13