Corso di
APPRENDIMENTO E
APPROSSIMAZIONE
Prof. Giancarlo Mauri
Lezione 1 Introduzione
Programma










Introduzione all’apprendimento automatico
Apprendimento di concetti
Apprendimento di alberi di decisione
Teoria computazionale dell’apprendimento
Apprendimento statistico con dati completi
Apprendimento statistico con variabili nascoste
Reti neurali
Metodi kernel - Support Vector Machines
Apprendimento basato su istanze
Apprendimento per rinforzo
2
Materiale

Libro di testo


S. Russel, P. Norvig
Intelligenza Artificiale, vol.2. Capp.18-21
Pearson - Prentice Hall
Testi ulteriori


Tom M. Mitchell
Machine Learning, McGraw Hill,1997
Richard Sutton
Reinforcement Learning – An Introduction, MIT Press,
1998
3
Informazioni utili
Pagina web del corso:
http://www.bio.disco.unimib.it/
4
Apprendimento Automatico Definizioni


Fenomeno di acquisizione di conoscenza in assenza
di programmazione esplicita
Processo di costruzione di un programma per
eseguire un compito sulla base di informazioni che
non forniscono una descrizione esplicita del
programma stesso
5
Apprendimento Automatico Definizioni




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
6
Discipline rilevanti per l’AA








Intelligenza Artificiale
Metodi Bayesiani
Teoria del Controllo
Teoria dell’Informazione
Teoria della Complessità Computazionale
Filosofia
Psicologia e Neurobiologia
Statistica
7
Gli elementi di base
Apprendere in maniera
automatica

=
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
8
Nota sulla terminologia

Chi è il learner ?


Colui che impara de 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
9
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
10
Sul compito T : alcune ragioni

Può essere 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
11
Sul compito T : un’applicazione
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.
Link:
http://vismod.media.mit.edu/
http://noodle.med.yale.edu/
12
Sul compito T : altri esempi
DNA array
Speech recognition
Pilota automatico
13
Sulla performance P

Dobbiamo scegliere una misura che ci consenta di
valutare il successo del learner:


il sistema ha appreso? Oppure,
sta apprendendo ?
14
Sull’esperienza E


Da cosa impara il sistema ?
È importante la scelta dell’esperienza:

il tipo di esperienza disponibile può influire significamente
sul successo dell’apprendimento.
la scelta
15
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)
16
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
17
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 ?
18
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)
19
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!)
20
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
21
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
22
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 consite 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
riuscirà mai a trovare alcune situazioni di gioco tipiche
giocate dal “campione del mondo”
23
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
24
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
25
Scelta della funzione obiettivo


Abbiamo detto …perchè non assegnare un punteggio
ad ogni configurazione della scacchiera ?
ScegliMossa : B  M : stato  mossa


Mappa uno stato dela scacchiera in una mossa lecita
Valuta : BV : stato  punteggio


Assegna un punteggio numerico ad ogni stato della
scacchiera (punteggio più alto=stato migliore)
Seleziona la mossa migliore valutando tutti gli stati
raggiunngibili con una mossa e scegliendo quello di
punteggio maggiore
26
Una possibile funzione obiettivo





Se b è uno stato finale vincente allora V(b) = 100
Se b è uno stato finale perdente allora V(b) = -100
Se b è uno stato finale di patta allora V(b)=0
Se b non è uno stato finale, allora V(b)=V(b’), ove b’
è il miglior stato finale raggiungibile partendo da b e
giocando in modo ottimale fino alla fine della partita.
Dà valori corretti, ma non è utilizzabile
operativamente
27
Formulazione del problema
per mezzo del giocatore di scacchi
Formulazione del concetto da
apprendere (la sua rappresentazione)

Che tipo di informazione abbiamo a disposizione ?







x1: numero di pezzi del giocatore;
x2 numero di pezzi dell’avversario;
x3 numero di re (regina) del giocatore;
x4 numero di re (regina) dell’avversario;
x5 numero di pezzi mangiati dal giocatore;
x6 numero di pezzi mangiati dall’avversario;
…

Una configurazione ?
–
Potrebbe venire rappresentata da una tupla di
valori (x1, x2,.., xn)
28
Ricerca nello spazio degli stati
V(b)= ?
V(b)= maxi V(bi)
m1 : bb1
m2 : bb2
m3 : bb3
29
Ricerca nello spazio degli stati
V(b1)= ?
V(b1)= mini V(bi)
m4 : bb4
m5 : bb5
m6 : bb6
30
Stati finali
Black wins: V(b)=-100
Red wins: V(b)=100
draw: V(b)=0
31
Ricerca in profondità
32
Ricerca in ampiezza
33
Numero di stati della scacchiera
Tic-Tac-Toe:
#board states < 9!/(5! 4!) + 9!/(1! 4! 4!) + …
… + 9!/(2! 4! 3!) + … 9 = 6045
4 x 4 checkers: (no queens)
#board states = ?
#board states < 8x7x6x5*22/(2!*2!) = 1680
Regular checkers (8x8 board, 8 pieces each)
#board states < 32!*216/(8! * 8! * 16!) = 5.07*1017
34
Rappresentazione della funzione
obiettivo





Table look-up
Collection of rules
Neural networks
Polynomial function of board features
Trade-off in choosing an expressive representation:


Approximation accuracy
Number of training examples to learn the target function
35
Rappresentazione della funzione
obiettivo








V(b)=0 + 1bp(b) + 2rp(b) +
3bk(b) + 4rk(b) + 5bt(b) + 6rt(b)
bp(b): #black pieces
rb(b): #red pieces
bk(b): #black kings
rk(b): #red kings
bt(b): #red pieces threatened by black
rt(b): #black pieces threatened by red
36
Obtaining Training Examples





V(b) : true target function
V’(b) : learned target function
Vtrain(b) : training value
Rule for estimating training values:
Vtrain(b)  V’(Successor(b))
37
Choose Weight Training Rule



LMS weight update rule:
Select a training example b at random
1. Compute error(b)



error(b) = Vtrain(b) – V’(b)
2. For each board feature fi, update weight i  i +
 fi error(b)
 : learning rate approx. 0.1
38
Esempio: dama: 4x4
V(b)=0 + 1rp(b) + 2bp(b)
Initial weights: 0=-10, 1 =75, 2 =-60
V(b0)=0 + 1*2 + 2*2 = 20
m1 : bb1
V(b1)=20
m2 : bb2
V(b2)=20
m3 : bb3
V(b3)=20
39
Esempio: dama: 4x4
V(b0)=20
V(b1)=20
1. Compute error(b0) = Vtrain(b) – V(b0) = V(b1) – V(b0) = 0
2. For each board feature fi, update weight
i  i +  fi error(b)
0  0 + 0.1 * 1 * 0
1  1 + 0.1 * 2 * 0
2  2 + 0.1 * 2 * 0
40
Esempio: dama: 4x4
V(b0)=20
V(b3)=20
V(b1)=20
V(b2)=20
41
Esempio: dama: 4x4
V(b3)=20
V(b4a)=20
V(b4b)=-55
42
Esempio: dama: 4x4
V(b3)=20
V(b4)=-55
1. Compute error(b3) = Vtrain(b) – V(b3) = V(b4) – V(b3) = -75
2. For each board feature fi, update weight
i  i +  fi error(b) : 0=-10, 1 =75, 2 =-60
0  0 - 0.1 * 1 * 75, 0 = -17.5
1  1 - 0.1 * 2 * 75, 1 = 60
2  2 - 0.1 * 2 * 75, 2 = -75
43
Esempio: dama: 4x4
0 = -17.5 , 1 = 60, 2 = -75
V(b4)=-107.5
V(b5)=-107.5
44
Esempio: dama: 4x4
V(b5)=-107.5
V(b6)=-167.5
error(b5) = Vtrain(b) – V(b5) = V(b6) – V(b5) = -60
0=-17.5, 1 =60, 2 =-75
i  i +  fi error(b)
0  0 - 0.1 * 1 * 60, 0 = -23.5
1  1 - 0.1 * 1 * 60, 1 = 54
2  2 - 0.1 * 2 * 60, 2 = -87
45
Esempio: dama: 4x4
Final board state: black won Vf(b)=-100
V(b6)=-197.5
error(b6) = Vtrain(b) – V(b6) = Vf(b6) – V(b6) = 97.5
0=-23.5, 1 =54, 2 =-87
i  i +  fi error(b)
0  0 + 0.1 * 1 * 97.5, 0 = –13.75
1  1 + 0.1 * 0 * 97.5, 1 = 54
2  2 + 0.1 * 2 * 97.5, 2 = -67.5
46
Formulazione del problema
per mezzo del giocatore di scacchi
Formulazione del concetto da apprendere
il concetto che vogliamo apprendere :
c(x)  w  x  w1 x1  w2 x2  w3 x3  w4 x4  w5 x5  w6 x6  b


Il vettore x è una configurazione di valori sugli
attributi espressi precedentemente x’ = (x1, x2,.., xn)
c (x) è il punteggio assegnato alla configurazione
(fissati i parametri w e b che sono i pesi corretti)
47
Formulazione del problema
per mezzo del giocatore di scacchi
nota


Potremmo anche dire che stiamo cercando un’ipotesi
hw ,b (x)  w  x  w1 x1  w2 x2  w3 x3  w4 x4  w5 x5  w6 x6  b
Dove w e b sono i parametri (pesi e soglia) modificabili (apprendibili)
dall’algoritmo

E’ ovvio che la rappresentazione dell’ipotesi dipende dalla
rappresentazione del concetto

Si può pensare che l’ipotesi cercata sia all’interno di una certa classe
H per apprendere il concetto c

Ovvero cerchiamo un’ipotesi h tale che h(x) = c(x) per ogni x nell’insieme
delle istanze del problema
48
Formulazione del problema
per mezzo del giocatore di scacchi
Formuliamo, quindi, l’esperienza

L’esperienza viene data sotto forma di un insieme di
esempi (training set)


Nell’ esempio introdotto: supponiamo che l’esperienza sia
direttamente utile, in questo caso il training set è
caratterizzato da una raccolta di coppie (x, c(x))
x configurazioni e c(x) punteggio
S  ( x1 , c( x1 )), ( x2 , c( x2 )),....( xn , c( xn ))
49
Formulazione del problema
per mezzo del giocatore di scacchi
Formuliamo, quindi, la performance

Usiamo ancora una funzione
V : H 

h  V (h)
Ad esempio (tenendo presente la
formulazione dell’esperienza data):
S  (x1 , c(x1 )), (x 2 , c(x 2 )),....( x n , c(x n ))
1 m
V (h)   (h(x i )  c(x i )) 2
m i 1
50
Formulazuone del problema
per mezzo del giocatore di scacchi

E l’algoritmo ?
- Un principio -
Un approccio comune è (ad
esempio) quello di trovare
una algoritmo che cerchi
l’ipotesi che rende minimo
V(h)

Diversi metodi noti !
1 m
min  (h(x i )  c(x i )) 2
hH m
i 1
51
Formulazione del problema
per mezzo del giocatore di scacchi
L’algoritmo

L’algoritmo, dunque, ha in ingresso l’esperienza (gli
esempi) e come output un’ipotesi
A : ( X  ) m  Z m  H
z  A( z )
52
Riassumendo:
la formulazione del problema

Dati:





Un insieme di osservazioni (esempi, istanze) xX (es:se x è
un vettore di caratteristiche : x’ = (x1, x2,.., xn)
Una funzione obiettivo o concetto da apprendere (target) c
(es. valutazione dell’interesse di una pagina web per un
utente):
Interessante: X0,1 dove X è l’insieme delle pagine web
Uno spazio delle ipotesi H (che dipende dalla modalità di
rappresentazione diSc)
(es: se c è una funzione lineare in n
 (x1 , c(x1 )), (x 2 , c(x 2 )),....( x n , c(x n ))
variabili, h è un iperpiano n-dimensionale)
Un training set di esempi
Determinare:

un’ipotesi h in H tale che h(x)=c(x) x in S
53
NOTA: apprendimento automatico e
approssimazione di funzioni


La formulazione data è tipica dei problemi di
apprendimento supevisionato (vedremo …)
In questo caso il problema è stato (formalmente)
definito come un problema di stima di una funzione

Molte volte non disponiamo di tutti gli esempi: viene
presentato un training che non comprende alcuni punti;
apprendere, in questo caso, vuol dire generalizzare:
comportarsi correttamente su esempi non osservati (test) !

Vogliamo stimare la funzione nei punti dove non sono stati
forniti i valori assunti dalla funzione stessa
54
Una classificazione
dei metodi di apprendimento



Con questi possiamo apprendere funzioni di probabilità
 Bayesian learning
 Hidden Markov models
Con questi possiamo apprendere funzioni algebriche
 Gradient descent (neural networks)
 Support Vector Machines
Con questi possiamo apprendere espressioni simboliche
 Alberi di decisione
 Regole di associazione
55
Un’altra possibile classificazione

In base all’informazione (esperienza) a disposizione:




Supervisionato
Con rinforzo
Non supervisionato
In base al controllo che il learner ha dell’esperienza


Apprendimento passivo
Apprendimento attivo
56
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.

Nel giocatore l’esperienza era data sotto forma di esempi (xi,yi)

S  ( x1 , y1 ), ( x2 , y2 ),....( xn , yn )
Per ogni input xi l’ipotetico trainer formiva il punteggio corretto
yi
57
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.
58
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
59
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?
60
Alcuni aspetti correlati all’apprendimento di
concetti da esempi:


Sovradattamento (overfitting)
Rumore
61
Sovradattamento (overfitting)

Dato uno spazio delle ipotesi H, una ipotesi h si dice
sovradattata (overfit) rispetto all’insieme di training S
se esiste un’ipotesi alternativa h’ tale che h commette
un errore minore di h’ sul set di addestramento S, ma
h’ produce un errore minore sui dati di test
62
Diverse cause




Errori nella classificazione dei dati
Distribuzioni di probabilità in D diversa che in T
Regolarità incidentali tra i dati
Attributi irrilevanti nel training
63
Rumore
In alcuni casi, due o più esempi con la stessa descrizione possono
avere classificazioni diverse (questo può essere dovuto ad
ambiguità, oppure ad errori, o ad un insieme di attributi non
sufficentemente descrittivo)
(Esempio: optical character recognition)
64
… Sarebbe bello
avere una teoria che …






What algorithms are available for learning a concept? How
well do they perform?
How much training data is sufficient to learn a concept with
high confidence?
When is it useful to use prior knowledge?
Are some training examples more useful than others?
What are best tasks for a system to learn?
What is the best way for a system to represent its
knowledge?
65
Software Packages &
DatasetsLearning & Adaptation
• MLC++
• Machine learning library in C++
• http://www.sig.com/Technology/mlc
• GALIB
• MIT GALib in C++
• http://lancet.mit.edu/ga
• UCI
• Machine Learning Data Repository UC Irvine
• http://www.ics.uci.edu/~mlearn/ML/Repository.html
66
Applications of ML

Learning to recognize spoken words


Learning to drive an autonomous vehicle


(Fayyad et al 1995)
Learning to play world-class backgammon


ALVINN (Pomerleau 1989)
Learning to classify celestial objects


SPHINX (Lee 1989)
TD-GAMMON (Tesauro 1992)
Designing the morphology and control structure of electromechanical artefacts

GOLEM (Lipton, Pollock 2000)
67
Evolution of Value Function
Training data:
before
after
68
Design Choices
Determine Type of
Training Experience
Games against
Games
experts
against self
Determine
Target Function
BoardMove
Table of correct
moves
BoardValue
Determine Representation
of Learned Function
polynomial
Artificial neural
Linear function of
network
six features
Determine
Learning Algorithm
69
Gradient descent
Linear programming
Learning Problem Examples

Credit card applications




Task T: Distinguish ”good” applicants from ”risky” applicants.
Performance measure P : ?
Experience E : ? (direct/indirect)
Target function : ?
70
Performance Measure P:

Error based: minimize percentage of incorrectly classified
customers : P = Nfp + Nfn / N
Nfp: # false positives (rejected good customers)
Nfn: # false negatives (accepted bad customers)

Utility based: maximize expected profit of credit card
business: P = Ncp *Ucp+ Nfn *Ufn
Ucp : expected utility of an accepted good customer
Ufn : expected utility/loss of an accepted bad customer
71
Experience E:

Direct: Decisions on credit card applications made by a
human financial expert
Training data: <customer inf., reject/accept>

Direct: Actual customer behavior based on previously
accepted customers
Training data: <customer inf., good/bad>
Problem: Distribution of applicants Papplicant is not identical with
training data Ptrain

Indirect: Evaluate a decision policy based on the profit
you made over the past N years.
72
Distribution of Applicants
Good customers
Bad customers
Cw=38
Assume we want to minimize
classification error:
What is the optimal decision
boundary?
73
Distribution of Accepted
Customers
Good customers
Bad customers
Cw=43
What is the optimal decision
boundary?
74
Target Function
Customer record:
income, owns house, credit history, age, employed, accept
$40000, yes, good, 38, full-time, yes
$25000, no, excellent, 25, part-time, no
$50000, no, poor, 55, unemployed, no



T: Customer data  accept/reject
T: Customer data  probability good customer
T: Customer data  expected utility/profit
75
Learning methods

Decision rules:


Bayesian network:



If income < $30.000 then reject
P(good | income, credit history,….)
Neural Network:
Nearest Neighbor:

Take the same decision as for the customer in the data base
that is most similar to the applicant
76
Learning Problem Examples

Obstacle Avoidance Behavior of a Mobile Robot




Task T: Navigate robot safely through an environment.
Performance measure P : ?
Experience E : ?
Target function : ?
77
Performance Measure P:




P: Maximize time until collision with obstacle
P: Maximize distance travelled until collision with
obstacle
P: Minimize rotational velocity, maximize
translational velocity
P: Minimize error between control action of a human
operator and robot controller in the same situation
78
Training Experience E:

Direct: Monitor human operator and use her control
actions as training data:


E = { <perceptioni, actioni>}
Indirect: Operate robot in the real world or in a
simulation. Reward desirable states, penalize
undesirable states
V(b) = +1 if v > 0.5 m/s
 V(b) = +2 if  < 10 deg/s
 V(b) = -100 if bumper state = 1
Question: Internal or external reward ?

79
Target Function

Choose action:



Evaluate perception/state:




A: perception  action
Sonar readings: s1(t)…sn(t)  <v, >
V: s1(t)…sn(t)  V(s1(t)…sn(t))
Problem: states are only partially observable therefore world
seems non-deterministic
Markov Decision Process : successor state s(t+1) is a
probabilistic function of current state s(t) and action a(t)
Evaluate state/action pairs:

V: s1(t)…sn(t), a(t)  V(s1(t)…sn(t),a(t))
80
Issues in Machine Learning





What algorithms can approximate functions well and
when?
How does the number of training examples influence
accuracy?
How does the complexity of hypothesis
representation impact it?
How does noisy data influence accuracy?
What are the theoretical limits of learnability?
81
Learning element

Design of a learning element is affected by
 Which components of the performance element are to be
learned
 What feedback is available to learn these components
 What representation is used for the components

Type of feedback:
 Supervised learning: correct answers for each example
 Unsupervised learning: correct answers not given
 Reinforcement learning: occasional rewards
82
Inductive learning

Simplest form: learn a function from examples

f is the target function
An example is a pair (x, f(x))
Problem: find a hypothesis h
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)
83
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:

84
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:

85
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:
86
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:
87
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:
88
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
89