Lezione 1-Introduzione File - e

APPRENDIMENTO AUTOMATICO
Prof. Giancarlo Mauri
Lezione 1 Introduzione
Programma

Introduzione all’apprendimento automatico

Apprendimento di concetti

Apprendimento di alberi di decisione

Classificatori

Teoria computazionale dell’apprendimento

Apprendimento statistico con dati completi

Apprendimento statistico con variabili nascoste

Reti neurali

Metodi kernel - Support Vector Machines

Apprendimento non supervisionato

Apprendimento per rinforzo
2
Materiale

Libro di testo


S. Russel, P. Norvig
Intelligenza Artificiale, vol.2. Capp.18-21
Pearson - Prentice Hall, 2005
Testi ulteriori



Tom M. Mitchell, Machine Learning, McGraw Hill, 1997
Stephen Marsland, Machine Learning, An algorithmic
Perspective, CRC Press, 2009
Richard Sutton, Reinforcement Learning – An
Introduction, MIT Press, 1998
3
Informazioni utili

Pagina web del corso:
http://informatica.elearning.unimib.it

Orario ricevimento:
Lunedì 16-18
4
Machine Learning in the Sciences
Astronomy
- Brown dwarfs and fossil galaxies discovery via
machine learning, data mining, data federation
- Very large multi-dimensional datasets analysis
using KD-trees
Medicine
- Anti-inflammatory drugs
- Chronic hepatitis
- Mammograms
- Renal and respiratory failure
Meteorology
- Tornado formation
Neurosciences
- fMRI data analysis to understand language
via machine learning
5
Machine Learning Everywhere
Supermarkets
Credit Cards
Wall Street
Entertainment:
Shopping, Music, Travel
Sports
Jeannette M. Wing 6
Machine Learning - Definitions




Simon, 1983: Learning denotes changes in the system
that are adaptive in the sense that they enable the
system to do the same task or tasks draw from the
same population more efficiently and more effectively
the next time
Minsky, 1985: Learning is making useful changes in our
minds
Michalski, 1985: Learning is constructing or modifying
representations of what is being experienced
Carbonell, 1987: Learning is the study of computational
methods for acquiring new knowledge, new skills, and
new way to organize existing knowledge
7
Machine Learning - Definitions


Process of knowledge acquisition in the absence of
explicit programming
Process of building a program to perform a task on
the basis of information that do not provide an
explicit description of the program
8
Gli elementi di base
Apprendere

=
Migliorare rispetto a una data
misura la capacità di esecuzione
di un certo compito, attraverso
l’esperienza
Schematicamente, iniziamo con 3 “attributi” per
descrivere il problema in generale :



T come Task: il compito da apprendere
P come Performance: una misura di bontà su come
apprendiamo (abbiamo appreso)
E come Experience: facciamo esperienza
9
Nota sulla terminologia

Chi è il learner ?


Colui che impara da esempi in modo automatico, quindi nel
seguito, un algoritmo o un programma
Chi è il trainer ?

A volte parleremo di trainer riferendosi ad un modulo che
fornisce l’esperienza al learner
10
Sul compito T

Rispetto alla programmazione classica diversi sono i
compiti che possono avvantaggiarsi dell’apprendimento
attraverso esempi
Alcune ragioni e
alcuni esempi di applicazioni
11
Sul compito T : alcune ragioni

Più facile apprendere attraverso esempi che
codificare conoscenza o definire alcuni compiti


Il comportamento di una macchina in un ambiente
può non essere quello desiderato:


può risultare difficile, ad esempio, codificare conoscenza
avendo a disposizione grandi quantitativi di dati
l’ambiente può modificarsi con il tempo
Può essere difficoltoso ridisegnare un sistema ma
più semplice presentare nuovi esempi
12
Esempi di problemi di apprendimento



Identify the numbers in a handwritten ZIP code,
from a digitized image
Estimate the amount of glucose in the blood of a
diabetic person, from the infrared absorption
spectrum of that person’s blood
Identify the risk factors for prostate cancer,
based on clinical and demographic variables
13
Esempi di problemi di apprendimento



Predict whether a patient, hospitalized due to a
heart attack, will have a second heart attack. The
prediction is to be based on demographic, diet and
clinical measurements for that patient
Predict the price of a stock in 6 months from now,
on the basis of company performance measures
and economic data
Recognize email spam
14
Esempio 1: Email Spam

Objective: to design an automatic spam detector

Sample:



4601 email messages
true outcome (email type) email or spam available for
each
relative frequencies of 57 of the most commonly
occurring words and punctuation marks in the email
message
15
Esempio 1: Email Spam

Our learning method has to decide which features
to use and how: we might use a rule such as
if (%george < 0.6) & (%you > 1.5)

then spam
else email
Another form of a rule might be:
if (0.2 · %you − 0.3 · %george) > 0 then spam
else email
16
Example 1: Email Spam
supervised learning problem
with outcome the class variable email/spam.
It is also called a
classification problem
Note: For this problem not all errors are equal; we
want to avoid filtering out good email, while letting
spam get through is not desirable but less serious
in its consequences
17
Example 2: Face recognition



Task: identificare un volto
all’interno di un database
Una motivazione importante:
sicurezza
Prolematiche rispetto alla
programmazione tradizionale:
difficile codificare alcune
specifiche



modifiche ambientali:
l’ambiente di posa può
cambiare, illuminazione
soffusa / intensa, interno /
esterno;
modifiche della posa:
espressione del volto,
inclinazione;
modifiche dell’oggetto in posa:
persona con/senza barba,
con/senza occhiali.
18
Example 3: Prostate Cancer


Stamey et al. (1989): correlation between the level
of prostate specific antigen (PSA) and a number
of clinical measures, in 97 men who were about to
receive a radical prostatectomy
Goal: predict the log of PSA (lpsa) from a number
of measurements including log cancer volume
(lcavol), log prostate weight (lweight), age, log of
benign prostatic hyperplasia amount (lbph), seminal
vesicle invasion (svi), log of capsular penetration
(lcp), Gleason score (gleason), and percent of
Gleason scores 4 or 5 (pgg45)
19
20
Example 3: Prostate Cancer

Some correlations with lpsa are evident, but a
good predictive model is difficult to construct by
eye
supervised learning problem
known as a
regression problem
because the outcome measurement is quantitative
21
Example 4: Microarrays cDNA




Un insieme di probe univoci (sequenze di DNA a elica singola)
vengono immobilizzati su una superificie solida (vetro, nylon,
etc.)
L’mRNA estratto da campioni cellulari viene trattato in
modo da generare un campione di cDNA etichettato con una
particolare tintura (fluorescente o radioattiva)
Il campione viene poi incubato con l’array così che ogni
probe ibridizza con la molecola di cDNA campione
complementare (se presente)
Esperimenti con mRNA da diversi campioni possono essere
realizzati contemporaneamente, usando tinture diverse o
diversi array. I risultati vengono poi confrontati per dare
una stima qualitativa dell’abbondanza relativa dell’mRNA
nella popolazione cellulare in esame
22
Example 4: Microarrays cDNA
2
1
2
1
+
1
2
Array con probes immobilizzati
2
Soluzione di bersaglie da campione 1 e 2,
etichettati con tintura 1 e 2 rispettivamente
1
2
Array con molecole etichettate di bersagli
ibridizzate con i probes
12
Example 4: Microarrays cDNA

Hybridization does not give a quantitative measure of
gene expression: the efficiency in DNA extraction,
the synthesis of the sample, sample labeling and
hybridization reactions vary from sample to sample,
and between a gene and the other. You may only have
an estimate of the rate of change of the
concentration of mRNA between two samples
Gene Expression Matrix
24
Example 4: Microarrays cDNA

The figure displays the data set as a heat map, ranging from
green (negative) to red (positive)

6830 genes (rows)

Samples: 64 cancer tumors from different patients (columns)

Goal: understand how the genes and samples are organized

Typical questions include the following:



(a) which samples are most similar to each other, in terms of
their expression profiles across genes?
(b) which genes are most similar to each other, in terms of their
expression profiles across samples?
(c) do certain genes show very high (or low) expression for
certain cancer samples?
26
Example 4: Microarrays cDNA

We could view this task as a
regression problem
with two categorical predictor variables—genes
and samples—with the response variable being the
level of expression

However, it is probably more useful to view it as
unsupervised learning problem
For example, for question (a) above, we think of
the samples as points in 6830−dimensional space,
which we want to cluster together in some way
27
Inductive learning

Simplest form: learn a function from examples



Problem: find a hypothesis h



f is the target function
An example is a pair (x, f(x))
such that h ≈ f
given a training set of examples
This is a highly simplified model of real learning:


Ignores prior knowledge
Assumes examples are given
28
Inductive learning method


Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)
E.g., curve fitting:

29
Inductive learning method


Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)
E.g., curve fitting:

30
Inductive learning method


Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)
E.g., curve fitting:
31
Inductive learning method


Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)
E.g., curve fitting:
32
Inductive learning method


Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)
E.g., curve fitting:
33
Inductive learning method

Construct/adjust h to agree with f on training set
(h is consistent if it agrees with f on all examples)



E.g., curve fitting:
Occam’s razor: prefer the simplest hypothesis
consistent with data
34
Sulla performance P

Dobbiamo scegliere una misura che ci consenta di
valutare il successo del learner:


il sistema ha appreso? Oppure,
sta apprendendo ?
35
Sull’esperienza E

Da cosa impara il sistema ?


Osservazioni, esempi, …
È importante la scelta dell’esperienza:

il tipo di esperienza disponibile può influire
significamente sul successo dell’apprendimento.
la scelta
36
Sull’esperienza E: la scelta

Rappresentatività dell’esperienza


L’esperienza è rappresentativa per il compito che il sistema
deve svolgere?
Controllo dell’esperienza da parte del learner

Due esempi:



L’esperienza può essere fornita al learner senza che esso possa
interagire oppure
il learner può porre domande su quegli esempi che non risultano
chiari
Esperienza diretta – indiretta

Il learner può acquisire informazione utile direttamente dagli
esempi o dover inferire indirettamente da essi l’informazione
necessaria (può essere chiaramente più complicato)
37
Sull’esperienza E (alcune note)

ATTENZIONE a volte:

l’esperienza (gli esempi) deve essere presentata in
maniera casuale.


NON SEMPRE ( E LA MAGGIOR PARTE DELLE VOLTE E’
COSI‘!) E’ POSSIBILE disporre di tutti gli esempi
L’esperienza può essere scelta in maniera maliziosa da un
avversario
38
Giocare a dama
Un problema da “definire”:

Ricordiamo i 3 “attributi”


Task, Performance, Experience ...
Il problema



T : giocare a dama ovvero scegliere la mossa migliore per
migliorare la P
P : che ne dite della percentuale di partite vinte ? Contro
chi?
E:
L’Esperienza ?
Pensiamo alle diverse
possibilità prospettate
Esperienza diretta o indiretta ?
Controllabile ?
Rappresentativa ?
39
Giocare a dama
Esperienza diretta o indiretta ...

Il sistema potrebbe imparare direttamente dagli
esempi
(configurazione della scacchiera, mossa corretta)

o anche:
(sequenza di mosse, esito finale)
40
Giocare a dama
Esperienza indiretta ...

1° alternativa


in questo caso il learner deve inferire (indirettamente
dagli esempi presentati) sulla “correttezza” di ciascuna
mossa (al fine di migliorare la performance): dovrebbe
determinare il grado con cui ciascuna mossa influisce
sull’esito finale della partita (complicato!)
2° alternativa

(configurazione della scacchiera, mossa corretta)
(sequenza di mosse, esito finale)
Idem: il learner dovrebbe determinare il grado con cui
ciascuna mossa, in una sequenza di mosse, influisce sul
l’esito finale della partita (complicato!)
41
Giocare a dama
Esperienza diretta o indiretta ...

3° alternativa:


(configurazione della scacchiera, punteggio)
Più alto è il punteggio in un determinato istante più
vantaggioso sarà lo stato del gioco per il learner
Possibile algoritmo: nota l’associazione, si
potrebbe mettere in ordine di punteggio crescente
le varie configurazioni.

In qualunque istante di gioco (dato un ordinamento e la
configurazione attuale di gioco) il learner potrebbe
cercare di spostarsi (per mezzo di una mossa lecita) ad
una configurazione successiva nell’ordinamento
42
Giocare a dama
Il controllo



1° ALTERNATIVA: il giocatore può disporre solo
dell’informazione che l’insegnante mette a sua
disposizione in merito ad alcune configurazioni di
gioco (secondo la volontà dell’insegnante, la
disponibilità, il caso ecc.) e ai punteggi corretti per
quelle configurazioni;
2° ALTERNATIVA: il giocatore può interagire
con l’insegnante e chiedere il punteggio per una
specifica configurazione di gioco;
3° ALTERNATIVA: il giocatore può avere
completo controllo sull’esperienza e può fare
“esperimenti” sulle configurazioni ai fini di
effettuare la valutazione
43
Giocare a dama
La rappresentatività


Attenzione alla distribuzione degli esempi sui quali
poi la misura di finale di performance del sistema
viene valutata !
Se P è la percentuale di partite vinte in un torneo
mondiale e se E consiste solo di partite giocate
contro se stesso c’è un ovvio pericolo che E sia
poco rappresentativa di tutte le situazioni in cui il
sistema si può trovare

È probabile che il sistema durante la sua esperienza non
riesca mai a trovare alcune situazioni di gioco tipiche
giocate dal “campione del mondo”
44
Formulazione di un problema di
apprendimento automatico

Idea schematica iniziale (approssimativa) i tre
attributi T,P,E, abbiamo :


isolato un Task (giocare a dama)
capito di aver bisogno di una qualche esperienza


(configurazione, punteggio) ….
e parlato, intuitivamente, di performance (percentuale di
partite vinte)
Vogliamo ora individuare gli
elementi di base, gli oggetti
sui quali possa essere
costruita una teoria matematica
45
Formulazione di un problema di
apprendimento automatico


... gli elementi che seguono sono alla base (il
linguaggio) della maggior parte dei modelli
matematici per il machine learning
Riflettiamo su:

1° Formulazione del concetto da apprendere



2° Formulazione dell’esperienza


Che tipo di informazione vogliamo apprendere ?
Come rappresentiamo questa informazione ?
Insieme di esempi che consentono l’apprendimento
3° Formulazione della performance

Data la rappresentazione dell’informazione da apprendere e
gli esempi come esperienza la formulazione della misura
scelta per valutare la capacità del learner
46
Una classificazione
dei metodi di apprendimento

Con questi possiamo apprendere espressioni
simboliche



Con questi possiamo apprendere funzioni di
probabilità



Alberi di decisione
Regole di associazione
Bayesian learning
Hidden Markov models
Con questi possiamo apprendere funzioni algebriche


Gradient descent (neural networks)
Support Vector Machines
47
Un’altra possibile classificazione

In base all’informazione (esperienza) a
disposizione:




Supervisionato
Non supervisionato
Con rinforzo
In base al controllo che il learner ha
dell’esperienza


Apprendimento passivo
Apprendimento attivo
48
Una classificazione

Apprendimento supervisionato


Apprendimento non supervisionato


C’e’ un “insegnante” che comunica l’output corretto
Riconoscere “schemi” nell’input senza indicazioni sui
valori in uscita
Apprendimento per rinforzo

Più generale, apprendere sulla base della risposta
dell’ambiente alle proprie azioni
Apprendimento supervisionato

Nei modelli supervisionati vengono forniti al learner a
priori esempi di “comportamenti”


E’ come se si supponesse l’esistenza di un trainer (oracolo)
che, per ogni input fornito al sistema, dia la risposta
corretta.
L’esperienza è rappresentata da un insieme di esempi (xi,yi)
S º {( x1 , y1 ), ( x2 , y2 ),....( xn , yn )}

Per ogni input xi l’ipotetico trainer fornisce il risultato
corretto yi
50
Apprendimento non supervisionato

L’esperienza di apprendimento è rappresentata da esempi
“non classificati”: non esiste un trainer che fornisce le
risposte corrette agli input
S º {x1 , x2 ,.., xn }

Cosa si apprende? Regolarità, una strutturazione insita nello
spazio degli input.


Il clustering è un tipico problema di apprendimento non
supervisionato
E’ difficile trovare misure di prestazione. Spesso, sono date
valutazioni soggettive da parte di esperti umani.
51
Apprendimento per rinforzo



Il learner interagisce con l’ambiente e riceve una
ricompensa (es: numerica) positiva o negativa (es:
se un robot fa goal il “peso” della sequenza di
azioni che lo ha portato a fare goal viene
aumentato)
Cosa si apprende? Una strategia di comportamento
(un “piano” o sequenza di azioni)
Misura della prestazione: si cerca di massimizzare
“a lungo termine” la ricompensa complessivamente
ottenuta
52
Apprendimento attivo e passivo

Apprendimento passivo:


L’apprendista può apprendere solo dai dati che vengono
messi a disposizione (E)
Apprendimento attivo:


L’apprendista può fare domande ed esperimenti (es. un
web advisor può chiedere esplicitamente all’utente di
valutare il suo gradimento sull’operato dell’advisor)
Problema: come limitare l’intrusività dell’apprendista in
modo ottimale?
53