Machine Learning

Machine
Learning
Come migliorarsi
attraverso l’esperienza
2004-05-12
Rossi Fabio
Indice

Apprendimento Automatico



Alberi di decisione



Definizioni
Applicazioni
Definizione, obbiettivi
Esempi
Inductive logic Programming


Definizioni, tassonomie
Alcune regole e tecniche
Definizioni di
Apprendimento Automatico

Definizione1:


Learning is constructing or modifying
representations of what is being experienced
[Michalski 1986]
Definizione2:

Learning denotes changes in the system that are
adaptive in the sense that they enable the system
to do the same task or tasks drawn from the same
population more efficiently and more effectively
the next time [Simon 1984]
Definizioni di
Apprendimento Automatico

Apprendere = migliorare la capacità di esecuzione di
un certo compito, attraverso l’esperienza





Migliorare nel task T
Rispetto ad una misura di prestazione P
Basandosi sull’esperienza E
E = esempi di comportamenti “positivi” o “negativi”
forniti da un istruttore, oppure un sistema di
“ricompense”.
In A.I. : Tecniche che consentono ad agenti (o
sistemi automatici ) di migliorare il proprio
comportamento attraverso l’analisi delle proprie
esperienze.
Impieghi
dell’Apprendimento Automatico
1.
2.
3.
Data Mining (estrazione di conoscenza):
scoprire regolarità e patterns in dati multidimensionali e complessi (es. cartelle
cliniche).
Miglioramento delle performance:
macchine che migliorano le loro capacità
(es. movimenti di un robot).
Software adattabili: programmi che si
adattano alle esigenze dell’utente (es.
Letizia).
Scelte nella definizione
di un sistema di apprendimento
1.
2.
3.
4.
Componenti Migliorabili: decidere quali
sono le componenti sulle quali “lavorare”
Scelta e Rappresentazione di una
“funzione obiettivo” che rappresenti il
compito
Scelta di un algoritmo di apprendimento
Modalità di training: supervisionato,
guidato da obiettivi
2. funzione obiettivo
Funzione obiettivo: espressione formale
della conoscenza appresa. Viene usata per
determinare le prestazioni del programma di
apprendimento.

Esempi di funzioni obiettivo: polinomi, alberi di
decisione, reti neurali, insiemi di regole….
altezza

-
+
+
peso
+
+
A=bP
2. funzione obiettivo e
funzione appresa



Nota: Difficilmente un sistema riesce ad
apprendere perfettamente una funzione obbiettivo
f (l’esempio della funzione altezza-peso è un
caso).
In genere viene appresa un funzione, avente la
forma prescelta (polinomio, regole,..), che
rappresenta una stima , o IPOTESI (indicata con
h), per la funzione obiettivo.
L’obiettivo è di apprendere una h che approssimi f
“il meglio possibile”.
3. algoritmo di apprendimento
Scelta dell’algoritmo e della funzione obiettivo
ovviamente correlate
Metodi statistici




Bayesian learning
Markov models
Metodi algebrici



Gradient descent
Support Vector Machines
Metodi knowledge-based



Alberi di decisione
Regole di associazione
4. Modalità di training
Basato sull’informazione a disposizione:




Supervisionato (esempi disponibili)
Con rinforzo (premi a fronte di comportamenti
corretti)
Non supervisionato (senza esempi)
Basato sul ruolo dell’apprendista (learner)



Apprendimento passivo (apprende da esempi apriori)
Apprendimento attivo (apprende anche durante il
funzionamento)
4. Modalità di training
Definiamo:
KB
Conoscenza base
KA
Conoscenza aggiuntiva
E
Input Esterno
Mi
Motore Inferenziale

Apprendimento Dichiarativo
KB + E
KB*
Apprendimento
4.3.a Apprendimento Deduttivo
Nel caso DICHIARATIVO si può avere:

Apprendimento Deduttivo:
KB* = KB + KA con
KB
KA
se KB Mi E
KA = E
KA Mi E

In genere aumento l’efficienza del sistema
4.3.b Apprendimento Induttivo
Apprendimento Induttivo:
KB* = KB + KA con
KBKA



E
Con KB* non inconsistente e
relazione
debole di conseguenza logica
In genere aumento la conoscenza del sistema
Apprendimento Induttivo
Il sistema parte dai fatti e dalle osservazioni
derivanti da un insegnante o dall’ambiente
circostante e le generalizza, ottenendo
conoscenza che, auspicabilmente, sia valida
anche per casi non ancora osservati (induzione).
Due tipi di apprendimento induttivo:



Apprendimento da esempi: la conoscenza è acquisita a
partire da un insieme di esempi positivi che sono istanze
del concetto da imparare e di esempi negativi che sono
non-istanze del concetto.
Apprendimento di regolarità: non c’e’ un concetto da
imparare, l’obiettivo e’ quello di trovare regolarità (ovvero
caratteristiche comuni) nelle istanze date.
Apprendimento Induttivo
Problema:
In generale possono esserci molte ipotesi per la
funzione obiettivo, alle quali è possibile assegnare,
al di là del semplice criterio di consistenza con gli
esempi, un grado di preferenza detto inclinazione
Approccio Incrementale: Si cerca di modificare
l’ipotesi corrente ad ogni nuovo esempio fornito
Apprendimento Induttivo
Definizione formale del problema
Dato:

Un insieme di osservazioni (esempi, istanze) xX
(es: x feature vector): x: (a1,a2..an), ai assume valori su 0,1)

Una funzione obiettivo o concetto da apprendere (indicata
con f) (es. valutazione dell’interesse di una pagina web per un
utente): Interessante: X0,1 dove X è l’insieme delle
rappresentazioni feature-vector di pagine web

Uno spazio di ipotesi H (che dipende dalla modalità di
rappresentazione di f)

Un insieme di apprendimento D:
D: <(x1,f(x1))…(x, f(xm))>
Dove f(xi)=1 se xi è un esempio positivo di f, 0 altrimenti
Determinare: un’ipotesi h in H tale che h(x) = f(x) x in D
Apprendimento Induttivo
Completezza e Consistenza
Alberi di
Decisione
Metodo di apprendimento
di conoscenza simbolica
Alberi di Decisione


Un albero di decisione prende in ingresso
un elemento xX descritto mediante un
insieme di proprietà (coppie attributo-valore)
ed emette in uscita una "decisione” binaria
( si o no)
Nodi ed Archi: corrispondono al test della
proprietà che può avere come risultato uno
dei Vi
PROPRIETA’
V1
V2
…
Vk
Alberi di Decisione
Aspettare o meno?
Clienti?
Pieno
Alcuni
0
No
Attesa
stimata?
Si
>60
30-60
Alternative?
No
No
Si
Prenotazione?
No
Si
Bar?
Si
No
No
0-10
10-30
E' Venerdì o
sabato?
Si
Si
fame?
Si
Si
No
Si
Alternative?
No
Si
Si
Pioggia?
No
No
Si
Si
No
No
Si
Si
Alberi di Decisione
Obiettivo


Lo scopo è, come in tutti i modelli di apprendimento
induttivo da esempi, imparare la definizione di una
funzione obiettivo espressa in termini di albero di
decisioni.
Un albero di decisione può essere espressa come una
disgiunzione (OR) di implicazioni, aventi il valore della
decisione come conclusione. Nell'esempio, la funzione
obiettivo (decisione) è "Attendo" ed è implicata, fra
l'altro, dalla implicazione:
r Clienti(r,Pieno)  AttesaStimata(r,10-30) 
Fame(r,N)  Attendo(r)
Dove r rappresenta l’istanza (di ristorante) da valutare
Alberi di Decisione

La decisione deve basarsi sull'esame di esempi D: xX,
così descritti:
ogni esempio è rappresentato da un vettore che rappresenta i
valori degli attributi prescelti per descrivere le istanze del
dominio x: <v1=vali,v2=valj,..vn=valm>
(utilizzando attributi booleani : <a1,a2,………..aN> ai={0,1} )

gli attributi sono proprietà che descrivono gli esempi del
dominio (es: fame=si,no Prezzo = $,$$,$$$ Attesa = 010,10-30..,>60


Gli alberi di decisione hanno il potere espressivo dei
linguaggi proposizionali, ovvero
-
qualsiasi funzione booleana può essere scritta
come un albero di decisione (e viceversa).
Alberi di Decisione
Quando è appropriato usarli?

Quando è appropriato usare alberi di decisione?

Gli esempi (istanze) sono rappresentabili in termini di
coppie attributo-valore.

La funzione obiettivo assume valori nel discreto. Un
albero di decisioni assegna classificazioni booleane ma
può essere esteso al caso di funzioni a più valori. Non è
comune, ma possibile, l'utilizzo di questa tecnica per
apprendere funzioni nel continuo (discretizzando i valori
di f(x)).

E’ appropriato rappresentare il concetto da apprendere
mediante una forma normale disgiuntiva.

I dati di apprendimento possono contenere errori, oppure
attributi di cui il valore è mancante.
Alberi di Decisione
Come utilizzare gli esempi D?
Es.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X 10
X 11
X 12
A lt.
SI
SI
NO
SI
SI
NO
NO
NO
NO
SI
NO
SI
Ba r
NO
NO
SI
NO
NO
SI
SI
NO
SI
SI
NO
SI
V /S
NO
NO
NO
SI
SI
NO
NO
NO
SI
SI
NO
SI
Fa.
SI
SI
NO
SI
NO
SI
NO
SI
NO
SI
NO
SI
Clien
.
A lc
Pien
A lc
Pie
Pie
A lc
A lc
N es
Pie
Pie
N es
Pie
Pz.
$$$
$
$..
Pio .
Pr e.
Tip.
Fr
Tail
F.F
Tail
.
.
A tt.
0-10
30 60
A tt?
Si
No
Si
Si
…
Alberi di Decisione
Come utilizzare gli esempi D?

L'insieme di addestramento D è l'insieme completo
degli esempi sottoposti al sistema di
apprendimento

Una soluzione semplice sarebbe creare una
espressione congiuntiva per ogni esempio e
costruire una disgiunzione: ma il sistema non
avrebbe alcun potere predittivo su esempi non
visti! Il problema è estrarre uno schema dagli
esempi, che sia in grado di estrapolare esempi
non visti
Alberi di Decisione
Algoritmo





L'obiettivo è di estrarre uno schema coinciso.
Rasoio di Ockham: l'ipotesi più probabile è la più semplice che
sia consistente con tutte le osservazioni.
Il problema di identificare l'albero più piccolo è intrattabile.
Tuttavia esistono euristiche che consentono di trovare alberi
"abbastanza" piccoli.
L'idea consiste nell’analizzare dapprima gli attributi più
importanti, ovvero quelli che discriminano di più.
Supponendo per ora di poter fare questa scelta ad ogni passo
i, l'algoritmo di creazione di un albero delle decisioni da un set
di esempi D è il seguente:
Alberi di Decisione
Algoritmo
Scelgo l’attributo più importante come radice e
suddivido gli esempi
Per ogni nodo successore:
1.
2.





Se ci sono sia es. positivi che negativi ricorsivamente
applico l’algoritmo con un attributo in meno
Se sono tutti es. positivi metto la foglia SI
Se sono tutti es. negativi metto la foglia NO
Se non ci sono esempi restituisco un valore di default
calcolato in base alla maggioranza del nodo progenitore
Se non ci sono più attributi ma ho ancora esempi misti ho
una situazione di errore (rumore) o di vero non
determinismo
Inductive
Logic Programming
Per la rappresentazione
degli esempi e dei concetti
Conoscenza e Apprendimento
Come utilizzare la conoscenza a priori
L’approccio induttivo “puro” cerca ipotesi:
Ipotesi  Descrizioni
Classificazioni.
Ovviamente cerca Ipotesi “semplici” e consistenti con le descrizioni
Conoscenza e Apprendimento
Come utilizzare la conoscenza a priori
Schema KBIL:
knowledge Based Inductive Learning
La conoscenza di fondo e le nuove ipotesi vengono combinate
per spiegare gli esempi.
Fondo  Ipotesi  Descrizioni
Classificazioni
Conoscenza
a priori
osservazioni
Approccio induttivo
basato sulla
Conoscenza
Ipotesi
predizioni
Inductive Logic Programming
Definizione

E’ il settore dell’Apprendimento Automatico
che impiega la programmazione logica come
linguaggio di rappresentazione degli esempi e
dei concetti
ML + LP = ILP
Inductive Logic Programming
Definizione del problema
Dati:





un insieme P di possibili programmi
un insieme E+ di esempi positivi
un insieme E- di esempi negativi
un programma logico consistente B, tale che
B
e+, per almeno un e+  E+
Trovare:
un programma logico P  P tale che



 e+  E+,
 e-  E-,
B,P
B,P
e+ (P è completo)
e- (P è consistente)
Inductive Logic Programming
Terminologia





B: background knowledge, conoscenza a
priori, predicati di cui conosciamo già la
definizione.
E+ E- costituiscono il training set
P programma target, B,P è il programma
ottenuto aggiungendo le clausole di P dopo
quelle di B.
P viene detto hypothesis space. Definisce lo
spazio di ricerca. La descrizione di tale spazio
delle ipotesi prende il nome di language bias.
B,P
e
si dice "P copre e"
Inductive Logic Programming
Esempio
Apprendimento del predicato father.
Dati




P : programmi logici contenenti clausole
father(X,Y) :- α
con α congiunzione di letterali scelti fra
parent(X,Y),parent(Y,X),male(X),male(Y),
female(X),female(Y)
B= { parent(john,mary),male(john),
parent(david,steve),male(david),
parent(kathy,ellen),female(kathy)}
Inductive Logic Programming
Esempio
E+={father(john,mary),father(david,steve)}
E-={father(kathy,ellen),father(john,steve)}
Trovare:




un programma per calcolare il predicato father
che sia consistente e completo rispetto ad E+, E-
Possibile soluzione:


father(X,Y):-parent(X,Y),male(X).
Altro Esempio
Inductive Logic Programming
Aree di Applicazione





acquisizione di conoscenza per sistemi esperti
knowledge discovery nei database: scoperta di
informazioni potenzialmente utili dai dati
memorizzati in un database
scientific knowledge discovery: generazione di
una teoria scientifica a partire da osservazioni +
generazione di esperimenti discriminanti + test
della teoria
software engineering: sintesi di programmi logici
inductive engineering: costruzione di un modello
di un dispositivo partendo da esempi del suo
comportamento.
Inductive Logic Programming
Applicazioni di successo





predizione della relazione struttura - attività
nella progettazione di medicine
predizione della struttura secondaria delle
proteine, importante per determinare l'attività di
una medicina.
classificazione dei documenti in base alla loro
struttura
diagnosi di guasti in apparati elettromeccanici
regole temporali per la diagnosi di guasti ai
componenti di satelliti
Inductive Logic Programming
Classificazione dei sistemi
Esistono diverse dimensioni di classificazione dei sistemi di ILP.

Possono richiedere che tutti gli esempi siano dati all'inizio
(batch learners) oppure possono accettarli uno ad uno
(incremental learners).

Possono apprendere un solo predicato alla volta (single
predicate learners) oppure più di uno (multiple predicate
learners).

Durante l'apprendimento possono fare domande all’utente
per chiedere la validità delle generalizzazioni e/o per
classificare esempi generati dal sistema (interactive learners)
oppure non avere interazione con l'esterno (non-interactive
learners).

Infine, un sistema può imparare una teoria da zero oppure
partendo da una teoria preesistente incompleta e/o
inconsistente (theory revisors).
Inductive Logic Programming
Classificazione dei sistemi


Sebbene si tratti di dimensioni indipendenti,
i sistemi esistenti appartengono a due
gruppi opposti.
Da una parte ci sono i sistemi batch, non
interattivi che apprendono da zero un
concetto alla volta (empirical systems);
dall'altro ci sono i sistemi incrementali,
interattivi che fanno theory revision e
imparano più predicati alla volta (interactive
or incremental systems)
Inductive Logic Programming
Relazione di generalità
I sistemi apprendono una teoria compiendo una
ricerca nello spazio delle clausole ordinato secondo la
relazione di generalità.
Nel caso della programmazione logica induttiva la
relazione di generalità e’ basata su quella di θsussunzione:





La clausola C1 θ -sussume C2 se esiste una sostituzione θ
tale che C1θ  C2.
Si dice che una clausola C1 e’ almeno tanto generale
quanto una clausola C2 (e si scrive C1 ≥ C2)
se C1 θ-sussume C2
C1 e’ piu’ generale di C2 (C1>C2)
se C1 ≥ C2 ma non C2 ≥ C1
Inductive Logic Programming
Esempio di θ-sussunzione
C1=grandfather(X,Y)←father(X,Z).
C2=grandfather(X,Y)←father(X,Z),parent(Z,Y).
C3=grandfather(john,steve)←father(john,mary),
parent(mary,steve).






C1 θ-sussume C2 con la sostituzione vuota θ=
C1 θ-sussume C3 con la sostituzione
θ={X/john,Y/steve,Z/mary}.
C2 θ-sussume C3 con la sostituzione
θ={X/john,Y/steve,Z/mary}.
Inductive Logic Programming
proprietà della θ-sussunzione



La θ-sussunzione ha l’importante proprietà che se C1 θsussume C2 allora C1 C2.
Non e’ pero’ vero viceversa.
Per questa ragione la θ-sussunzione viene utilizzata per
rappresentare la relazione di generalità: essa approssima la
relazione di generalità intuitiva che è basata sulla relazione di
conseguenza logica.
Inductive Logic Programming
Algoritmi
Gli algoritmi per ILP si dividono in bottom-up e
top-down a seconda che utilizzino operatori di
generalizzazione o specializzazione.
Gli algoritmi bottom-up partono dagli esempi
(specifici o bottom) e li generalizzano ottenendo
una teoria che li copre.



Vengono utilizzati degli operatori di generalizzazione
ottenuti invertendo le regole deduttive di unificazione,
risoluzione e implicazione
Inductive Logic Programming
Algoritmi Top-Down

Gli algoritmi top-down imparano programmi
generando le clausole in maniera
sequenziale (una dopo l’altra). La
generazione di una clausola avviene
partendo da una clausola generale (con il
body vuoto) e specializzandola (applicando
un operatore di specializzazione o
raffinamento) fino a che non copre più
nessun esempio negativo.
Inductive Logic Programming
Top-Down: criteri di terminazione



Gli algoritmo top-down differiscono tra di loro a
seconda del criterio di necessita’ e di sufficienza.
In genere, il criterio di Sufficienza richiede che tutti
gli esempi positivi siano coperti.
In genere, il criterio di Necessità richiede che
nessun esempio negativo sia coperto dalla
clausola. Nel caso di dati rumorosi, questo criterio
può essere rilassato e si può ammettere la
copertura di un certo numero di esempi negativi.
Inductive Logic Programming
Top-Down: Esempio




P : father(X,Y) :- α con α 
{parent(X,Y),parent(Y,X),
male(X),male(Y),female(X),female(Y)}
B= { parent(john,mary),male(john),
parent(david,steve),male(david),
parent(kathy,ellen),female(kathy)}
E+={father(john,mary),father(david,steve)}
E-={father(kathy,ellen),father(john,steve)}
Inductive Logic Programming
1° passo di specializzazione
father(X,Y) :- true.
copre tutti gli e+ ma anche gli e2° passo
father(X,Y) :- parent(X,Y).
copre tutti gli e+ ma anche l'e- father(kathy,ellen).
3° passo
father(X,Y) :- parent(X,Y), male(X).
copre tutti gli e+ e nessun eGli esempi positivi coperti vengono rimossi, E+
diventa vuoto e l'algoritmo termina generando la
teoria:





father(X,Y) :- parent(X,Y), male(X).
Bibliografia
Fonti del
seminario
Bibliografia
Machine Learning




T. M. Mitchell, Machine Learning, McGrawHill,1997
J. R. Quinlan, C4.5: Programs for machine
learning, Morgan Kaufmann Publishers, San
Mateo, California, 1993
J. R. Quinlan, Improved Use of Continuous
Attributes in C4.5, Journal of Artificial Intelligence
Research, 4, pag. 77--90, 1996.
ftp://ftp.cs.cmu.edu/project/jair/volume4/quinlan96a
.ps
I.H. Witten, E. Frank, Data Mining: Practical
Machine Learning Tools and Techniques with Java
Implementations, Morgan Kaufmann, 1999.
Bibliografia
Inductive Logic Programming



S. Muggleton e C. Feng, Efficient induction of logic
programs, Proceedings of the 1st Conference on
Algorithmic Learning Theory Ohmsma, Tokyo, pag.
368-381, 1990.
G.D. Plotkin. A note on inductive generalisation.In
B. Meltzer and D. Michie, editors, Machine
Intelligence 5, pages 153-163. Edinburgh
University Press, Edinburgh, 1969.
J. R. Quinlan, Determinate literals in inductive
logic programming, Proceedings of Twelfth
International Joint Conference on Artificial
Intelligence, Morgan Kaufmann, 1991.