Sistemi di supporto alle decisioni
3. Classificazione
Ing. Leonardo Rigutini, Ph.D.
Dipartimento di Ingegneria dell’Informazione
Università di Siena
[email protected]
http://www.dii.unisi.it/ ~rigutini/
Classificazione
Processo supervisionato in cui un teacher addestra un modello ad
assegnare una etichetta ad un pattern
Dati:
Insieme predefinito di k classi - C = {C1 , C2 ,…, Ck}
Learning set = {<xi ,Cj>} con i=1,…, e j=1,…,k
Scopo:
Dato un pattern mai visto u, assegnarlo ad una delle k classi
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificazione
 Due tipi di classificazione:
 Mono-classe (binario), in cui ogni patterrn viene assegnato ad
una ed una sola classe
 Multi-classe, in cui un pattern può essere inserito in più di una
classe
 Il secondo caso è più complicato del primo (ovviamente)
ma molto più vicino alla realtà
 Spesso il secondo caso si risolve con k classificatori
binari
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori
 Diversi tipi di classificatori in base all’approccio
utilizzato nello sviluppo del modello:






A regole (rule-based)
Statistici
Profile-based
Example-based
Neurali
Support Vector Machines (SVM)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori a regole
Alberi di decisione - 1
Decidere se è la giornata ideale per giocare a tennis...
Outlook
Sunny
Humidity
High
No
Rain
Wind
Overcast
Normal
Yes
Yes
Strong
No
Esempio: {Outlook=Sunny,Humidity=High,Wind=Strong}
Attributo
Valore dell’attributo
Sistemi di supporto alle decisioni - Leonardo Rigutini
Weak
Yes
Alberi di decisione - 2
Costruzione dell’albero di decisione
2 fasi:
Fase di build  si costruisce l’albero, partizionando
ripetutamente il training set sul valore di un attributo, finché
tutti gli esempi, in ogni partizione, appartengono ad una sola
classe
Fase di pruning  si pota l’albero, eliminando rami dovuti a
rumore o a fluttuazioni statistiche
Sistemi di supporto alle decisioni - Leonardo Rigutini
Case Study: alberi di decisione - 3
In un albero di decisione:
Ogni nodo interno effettua un test su un attributo
Ogni ramo uscente da un nodo corrisponde ad uno dei possibili
valori che l’attributo può assumere
Ogni foglia assegna una classificazione
Per classificare un’istanza occorre, a partire dalla radice...
1) ...selezionare l’attributo dell’istanza associato al nodo corrente
2) ...seguire il ramo associato al valore assegnato a tale attributo
nell’istanza
3) ...quando si raggiunge una foglia, restituire l’etichetta associata
alla foglia, altrimenti, a partire dal nodo corrente, ripetere il
passo 2)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Case Study: alberi di decisione - 4
Esempio: {Outlook=Sunny,Humidity=High,Wind=Strong}
Outlook
Sunny
Humidity
High
No
Rain
Wind
Overcast
Normal
Yes
Yes
Strong
No
Sistemi di supporto alle decisioni - Leonardo Rigutini
Weak
Yes
Un altro esempio …
Decidere la tariffa assicurativa da applicare, in base alla
classe di rischio
Età < 26
no
sì
Alto
ETÀ
TIPO AUTO
CLASSE RISCHIO
40
65
20
25
50
familiare
sportiva
utilitaria
sportiva
familiare
basso
alto
alto
alto
basso
Tipo auto
utilitaria
sportiva
familiare
Alto
Basso
Alto
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori Probabilistici:
Naive Bayes
Naive Bayes
 Un classificator Bayesiano, stima la probabilità marginale della
classe dato l’esempio:
 Questa quantità non può essere stimata direttamente ma utilizzando
la formula di Bayes possiamo scrivere:
 Per stimare la quantità
viene fatta una forte assunzione di
indipendenza delle features (naive) e cioè che:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Naive Bayes
 E la stima delle singole probabilità è fatta semplicemente contando
la frequenza relativa di una feature all’interno della classe:
 Le rimanenti due probabilità possono essere considerate costanti (e
quindi ignorate) oppure stimate a loro volta dai dati
Sistemi di supporto alle decisioni - Leonardo Rigutini
Naive Bayes
 Nel primo caso, la supposizione è la seguente:
 la probabilità a priori di ogni classe è la stessa per tutte le classi (classi equiprobabili)
 La probabilità di un esempio è la stessa di tutti gli esempi (esempi equiprobabili)
 Nel secondo caso, invece si può sfruttare i dati per la stima dei due
valori:
 La probabilità della classe P(Ck) può essere stimata contanto la percentuale
di documenti appartenencti alla classe rispetto al numero totale di documenti
nel training set
 La probabilità a priori del dato può essere stimata utilizzando l’ipotesi naive
fatta prima:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Smoothing
 Problema: cosa accade se
= 0? Questo vuol dire che tale
feature non viene mai incontrata nella classe k durante
l’apprendimento.
 Tale caso implica
 Per evitare questo problema vengono utilizzate tecniche di
smoothing che restituiscono valori molto piccoli ma non nulli per
le features mai osservate in apprendimento
Sistemi di supporto alle decisioni - Leonardo Rigutini
a) Additive smoothing
 La formula di stima viene modificata in :
con i vincoli che
 Ottenendo così:
Sistemi di supporto alle decisioni - Leonardo Rigutini
b) Laplace smoothing
 Laplace smoothing pone a=1 nella formula precedente, ottenendo
così:
 La formula di ristima delle probabilità diventa:
Sistemi di supporto alle decisioni - Leonardo Rigutini
c) Good-Turing
 La tecnica di smoothing Good-Turing (dal nome dei due ricercatori
che l’hanno proposta) stima la probabilità di una feature mai vista
 Essi trovarono che:
con p0 la probabilità di una feature mai vista, N1 il numero di
features osservate solamente una volta nel training set ed N il
numero totale di features
 L’idea è che le features viste una volta sono casi fortunati di
features mai viste
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori probabilistici:
Complement Naive Bayes
Complement Naive Bayes
 Questo metodo utilizza l’approccio Bayesiano visto per il modello
precedente per stimare le probabilità complementari:
 Questo metodo ha lo stesso problema delle features mai viste e
quindi richiede l’utilizzo di tecniche di smoothing
 Inoltre ha il vantaggio rispetto a NB di avere a disposizione un
maggior numero di esempi per ogni classe (o meglio complemento
di classe)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Complement Naive Bayes
 Per ogni complemento di classe infatti le statistiche vengono
stimate utilizzando tutti i documenti delle classi rimanenti, e cioè
che è sicuramente maggiore di
dove
è l’intero training set e
indica la parte del training
set contenente esempi della classe k. L’operatore su insiemi |A|
infine indica la cardinalità dell’insieme A.
 Per questo motivo, tale modello è spesso utilizzato nei casi di
scarsità di esempi di addestramento
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori Profile-based
Profile Based Classifiers
 Questa famiglia di classificatori lavora memorizzando una
rappresentazione esplicita delle categorie.
 Durante il processo di classificazione, il modello computa la
similarità dei nuovi patterns con i profili delle classi assegnandoli
alla classe con score di similarità maggiore.
 Ad ogni feature vector sono assegnati dei pesi:
 I pesi possono essere valori reali propri del pattern oppure assegnati da
funzioni di pesatura (ad es. Tf-idf)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Funzioni di similarità
 Una volta creati i profili per le classi, questi modelli utilizzando
una funzione per misurare la similarità dei pattern con i profili
della classe
 Esempi di funzioni di similarità
 Manhattan distance (o City-block)
 Distanza Euclidea
 Distanza di Minkowski
Sistemi di supporto alle decisioni - Leonardo Rigutini
Funzioni di similarità (2)
 Distanza del coseno
 Da notare che alcune funzioni ritornano valori alti per pattern
molto simili e bassi per pattern dissimili (es. coseno), altre
viceversa si comportano in modo opposto (es. Euclidea)
Sistemi di supporto alle decisioni - Leonardo Rigutini
1) Algoritmo di Rocchio
 Questo classificatore profile-based calcola il profilo della classe
secondo la seguente formula:
dove
e
degli esempi positivi per la classe
degli esempi negativi.
. Inoltre,
indica l’insieme
mentre
indica l’insieme
 I parametri beta e gamma pesano rispettivamente gli esempi
positivi e negativi nella costruzione del profilo
Sistemi di supporto alle decisioni - Leonardo Rigutini
1) Algoritmo di Rocchio
 In realtà questo modello stima il profilo medio tra il profilo
generato dagli esempi postivi e quello generato dagli esempi
negativi:
 E’ un classificatore lineare.
Sistemi di supporto alle decisioni - Leonardo Rigutini
2) Centroids-based
 Questo classificatore è un caso particolare del modello di Rocchio.
 Ponendo Beta=0 e quindi Gamma=1 si ottiene:
 Il profilo (vettore n-dimensionale) cj viene detto centroide e può
essere immaginato come un esempio “dummy” (virtuale) che sta
nel centro della classe:
 Generato dalla media degli esempi positivi per la classe
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatori Examples-based
Examples-based classifier: kNN
 Questo modello è molto simile ai modelli basati su profilo
(Rocchio) ed utilizza come essi una funzione di similarità.
 Questo modello però non costruisce un profilo per la classe, ma
mantiene in memoria tutti i pattern assegnati alla classe e li usa
ogni qualvolta deve classificare un nuovo esempio
 In tale situazione le distanze (similarità) tra tutti gli esempi
memorizzati ed il nuovo esempio sono calcolate e poi due strategie
sono possibili:
 Assegnare il nuovo pattern alla classe più presente nei k pattern più vicini
 Assegnare il nuovo pattern alla classe che contiene i primi k pattern più
simili
Sistemi di supporto alle decisioni - Leonardo Rigutini
Examples-based classifier: kNN
 Questo metodo è molto costoso
 È necessario ogni volta calcolare N valori di similarità con N il
numero di esempi utilizzati per l’addestramento
 Elevato costo computazionale
 Elevato costo di memorizzazione dati
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali artificiali
Introduzione  1
Nonostante gli straordinari successi nell’elaborazione
automatica dell’informazione, che stanno esercitando un
impatto di portata storica nella vita quotidiana, competenze
percettive, quali…
…localizzare un oggetto in una scena
…riconoscere la voce in condizioni reali
…prendere decisioni basate sul “senso comune”
sono compiti estremamente difficili per i calcolatori
elettronici
Sistemi di supporto alle decisioni - Leonardo Rigutini
Introduzione  2
Infatti, gli odierni sistemi di elaborazione hanno
automatizzato perfettamente processi ritenuti, fino a poche
decine di anni fa, di pertinenza umana, quali…
…svolgere calcoli molto complicati
…recuperare informazione in un archivio
Con l’Intelligenza Artificiale si sono spinti verso
l’automazione del ragionamento simbolico, fino ai sistemi
esperti, in grado di modellare e rendere fruibile la conoscenza
di esperti in settori specifici
Sistemi di supporto alle decisioni - Leonardo Rigutini
Introduzione  3
Tuttavia, i calcolatori mostrano un comportamento primitivo nella
simulazione della maggior parte dei processi percettivi
Le capacità percettive, infatti, sviluppate durante un processo evolutivo di
centinaia di migliaia di anni, risultano difficili da replicare usando i
modelli di calcolo simbolico, tipici degli elaboratori attuali
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  1
Attualmente, a differenza delle macchine, l’uomo è un ottimo
esempio di “sistema” in grado di elaborare informazione
sottosimbolica
Tali elaborazioni, come ogni altro processo cognitivo, hanno
sede nel cervello, una complessa struttura neurobiologica, oggi
accuratamente “decifrata”
Il “mattone elementare” dei
tessuti cerebrali è il neurone,
che è sede dei processi
elettrochimici che determinano
l’atto percettivo
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  2
Nel cervello umano sono presenti oltre 100 miliardi (1010) di
neuroni, ciascuno interconnesso a circa 10.000 altre unità
(modello di HodgkinHuxley)
Nelle interconnessioni ha luogo il processo di sinapsi, un
processo elettrochimico atto a rafforzare o ad inibire
l’interazione cellulare
I segnali rilevabili hanno un
potenziale dell’ordine delle decine
di mV e si presentano come treni
di impulsi con frequenza 100Hz e
con opportune modulazioni
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  3
È opinione condivisa nel mondo delle scienze cognitive che i
segnali elettrici presenti nei neuroni siano alla base
dell’elaborazione dell’informazione a livello cerebrale
Inoltre, c’è evidenza sperimentale per sostenere che la struttura
cerebrale e le sinapsi siano influenzate dalla vita degli
individui, dalle loro esperienze, dall’apprendimento di compiti
specifici
È il particolare pattern di interconnessioni, e la forza delle
sinapsi, che definiscono le proprietà funzionali di una
particolare porzione del cervello
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  4
È inoltre sperimentalmente provato che le funzioni cognitive
risiedono in particolari zone del cervello e che tali funzioni
possono essere…
...perdute a seguito della “rottura” dei legami sinaptici
...eventualmente (parzialmente) recuperate con successivi
processi di apprendimento atti ad instaurare nuovi pattern di
interconnessione sinaptica
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  5
Poiché la struttura cerebrale e l’attività elettromagnetica delle
singole cellule neuronali sono note, si possono operare induzioni sul
comportamento collettivo dei neuroni e si può trarre ispirazione per
la costruzione di macchine in grado di replicare compiti connotati da
una forte componente di elaborazione sottosimbolica
Mind no longer goes more ghostly than a ghost: il lavoro di
Mcculloch e Pitts (1943) contiene la prima analisi completa di come
semplici unità con sinapsi eccitatorie e inibitorie siano in grado, in
virtù di un processo collettivo, di rappresentare proposizioni logiche
complesse
Tuttavia, non è necessaria una perfetta emulazione dei processi
neurobiologici per l’emergenza di capacità cognitive
Sistemi di supporto alle decisioni - Leonardo Rigutini
La metafora neurobiologica  6
Molti modelli connessionistici sono
solo ispirati al paradigma biologico a
livello di unità neuronale, e si basano
sulla struttura fortemente connessa
delle cellule cerebrali, dove si eredita il
principio che l’attivazione neurale è
soggetta ad eccitazioni ed inibizioni ad
opera delle unità connesse
L’attivazione dell’unità i dipende dall’attivazione della generica
unità j, mediante un parametro associato alla connessione fra le due
unità, che modella il principio elettrochimico della sinapsi
Sistemi di supporto alle decisioni - Leonardo Rigutini
What’s new ?
Mon June 6, 2005 12:51 PM GMT
LONDRA (Reuters)  IBM si è accordata con un team di scienziati svizzeri per
creare il primo modello al mondo di cervello computerizzato, Blue Gene: i
ricercatori sperano così di fornire nuove prospettive nella conoscenza del più
complesso organo umano
L’obiettivo immediato è di riprodurre la trama di circuiti nella neocorteccia, che
comprende circa l’85% della massa cerebrale e si ritiene sia responsabile del
linguaggio, dell’apprendimento, della memoria e del pensiero articolato
Il sistema Blue Gene/L, attualmente in costruzione presso il Department of
Energy’s NNSA/Lawrence Livermore National Laboratory in California, avrà una
velocità massima di elaborazione di 360 trilioni di operazioni floatingpoint al
secondo, ossia 360 teraflops
Cinque anni fa, nessun supercomputer al mondo aveva una capacità maggiore di un
teraflop
Sistemi di supporto alle decisioni - Leonardo Rigutini
Softcomputing e reti neurali
Emulazione o ispirazione ?
I just want to point out that the componentry used in the memory
may be entirely different from the one that underlines the basic
active organs (John Von Neumann, 1958)
Molti modelli connessionistici utilizzati nelle applicazioni
sono solo ispirati dal paradigma biologico a livello di unità
neuronale…
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali  1
Le neuroscienze hanno permesso di stabilire che la struttura
cerebrale è caratterizzata dalla presenza di neuroni
specializzati e con pattern di connettività specifici al
particolare compito cognitivo
Per i modelli artificiali è stata seguita una metafora simile:
sono stati studiati diversi tipi di neuroni e diverse architetture,
associandovi le modalità di elaborazione concepite per
implementare un particolare compito cognitivo
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali  2
Le reti neurali artificiali sono esse stesse costituite da insiemi
di unità semplici, i neuroni, densamente interconnesse
Ciascuna unità riceve un certo numero di input reali (stimoli
esterni o output di altre unità) e produce, in uscita, un valore
reale (che potrà costituire l’ingresso per altre unità)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali  3
Il cervello umano…
…contiene una rete di 1011 neuroni; ciascun neurone è connesso, in
media, con 104 altre unità
…l’attività dei neuroni viene eccitata o inibita dagli stimoli ricevuti
dalle unità adiacenti: il tempo di “switch” è 103 sec (alto rispetto a
quello del calcolatore, 1010 sec)
…una qualsiasi scena può essere “compresa” in 0.1 secondi
Utilizzo massivo di calcolo parallelo
Le reti neurali artificiali…
…dovrebbero “catturare” questa forma di parallelismo, basato sulla
rappresentazione distribuita dell’informazione
…si discostano dai modelli biologici, di cui non hanno la potenza
…realizzano l’apprendimento mediante tecniche automatiche per il
“tuning” dei pesi di connessione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Un po’ di storia  1
La prima era: i modelli di neurone
1956: Dartmouth Summer Research Project on AI (Minsky, McCarty,
Rochester, Shannon,…)
1959: ADALINE di WidrowHoff con applicazione al riconoscimento
vocale
1962: Perceptron di Rosenblatt
1969: “Perceptrons” e le prime critiche alle reti neurali (Minsky e
Papert)
’70: Associatori di Anderson, modelli per apprendimento senza
supervisione di Kohonen, studi di Grossberg (ispirati alla
neurobiologia)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Un po’ di storia  2
La seconda era: le reti di neuroni
1982: Reti di Hopfield
1986: Parallel Distributed Processing e Backpropagation
1987: Prima conferenza sulle reti neurali dell’IEEE a San Diego
1989: Primi chip neurali
1990: J. Pollack e le reti neurali che elaborano dati strutturati
1994: Prima conferenza mondiale su Intelligenza Artificiale
1994: Nasce il progetto NeuroCOLT (Computational Learning Theory
)
2001: L’IEEE approva la creazione della Neural Networks Society
Sistemi di supporto alle decisioni - Leonardo Rigutini
Cos’è il softcomputing ?
Il requisito dell’hardcomputing “trova sempre la soluzione esatta”
diviene “trova spesso una soluzione approssimata”
L’elaborazione coinvolge informazione sottosimbolica: può non
esistere una soluzione algoritmica soddisfacente
Definizione di softcomputing di Lofti Zadeh
Softcomputing differs from conventional (hard) computing
in that, unlike hardcomputing, it is tolerant of imprecision,
uncertanty and partial truth. In effect, the role model for
softcomputing is the human mind. The guidance principle of
softcomputing is: exploit tolerance for imprecision, uncertanty and
partial truth to achieve tractability, robustness and low solution
cost.
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali singolo strato
ADALINE  1
ADALINE (ADAptive LInear NEuron)
Modello singleneuron con funzione di attivazione lineare
Apprendimento con algoritmo LMS (Least Mean Square), noto
anche come WidrowHoff Algorithm
Risolve problemi di regressione, ovvero di approssimazione
della funzione che definisce la relazione tra input e output
calcolando  (x,w)
f : n  
Sistemi di supporto alle decisioni - Leonardo Rigutini
ADALINE  2
Learning rule: Deltarule
Adattamento dei pesi in base all’errore che la rete commette
rispetto alla risposta desiderata
x1
w1
w0
w2
x2
y
:
xp
wp

t
Sistemi di supporto alle decisioni - Leonardo Rigutini
ADALINE  3
L’applicazione iterativa della deltarule comporta la
minimizzazione di una funzione errore (costo), che è una
misura scalare di quanto la risposta della rete devia dalla
risposta desiderata, rispetto all’intero training set
Può essere interpretata come un metodo iterativo per
determinare i valori ottimi dei parametri di un sistema
Sistemi di supporto alle decisioni - Leonardo Rigutini
ADALINE  4
Algoritmo Least Mean Square (LMS): basato sulla stima
istantanea delle funzioni di correlazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo LMS  1
Procedura di training: dato il training set
L ={(x(m),t(m)) | m=1,2,…,M}
I pesi vengono inizializzati con valori casuali
Per ogni esempio del training set:
Si presenta l’input x alla rete e si calcola la risposta y
Si applica la deltarule per modificare i pesi
Si ripete il punto 2) fino a quando l’errore quadratico medio
scende al di sotto di una soglia prestabilita, o il numero di
iterazioni non supera un valore predeterminato
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo LMS  2
Sia
e = (twTx)T (twTx)
Si vuole aggiornare il vettore dei pesi w per ottenere una
diminuzione dell’errore e
ee = (t(w w)Tx)T (t(w w)Tx)
= e(twTx)T(wTx)(wTx)T(twTx) O(wTw)
Scegliendo
w =  (twTx)x  e  2 (twTx)T (twTx) < 0
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo LMS  3
Algoritmo LMS (Stocastic Gradient Algorithm)
Determina una stima dei valori ottimi dei parametri,
scegliendo, localmente, la traiettoria di massima discesa
lungo la superficie dell’errore
Non richiede la conoscenza delle caratteristiche statistiche dei
dati
Minimizza l’errore istantaneo al passo n riducendo al minimo
la quantità di informazione da mantenere in memoria
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo LMS  4
Condizione di convergenza asintotica
La stabilità di un sistema con feedback è determinata
dalle caratteristiche statistiche del vettore di input
x(n) e dal parametro : dato x(n) è necessaria una
selezione opportuna di  affinché l’algoritmo
converga
Convergenza garantita per  strettamente minore di 2
: costante positiva, 0 <  < max, max=2/max
max massimo autovalore della matrice di correlazione
degli ingressi
Sistemi di supporto alle decisioni - Leonardo Rigutini
Interpretazione probabilistica  1
Il risultato della rete ADALINE è una combinazione lineare
degli ingressi
In termini probabilistici, l’algoritmo LMS…
…fornisce una tecnica per effettuare la regressione lineare:
assegnato un insieme di esempi, individua un vettore peso w*
tale che l’iperpiano (w*)T x descrive l’andamento dei dati
…è lineare nei coefficienti, cioè nei pesi
y
y=w0+w1x1+w2x2+…+wpxp
x
Sistemi di supporto alle decisioni - Leonardo Rigutini
Interpretazione probabilistica  2
La trasformazione da x a y può essere polinomiale in x: in tal caso
l’algoritmo corrisponde alla tecnica di regressione polinomiale e
determina una superficie curva
z
z2
y
1
w1
w0
w2
y
y=w0+w1z+w2z2
z
Sviluppando in serie di Taylor una funzione f (x) si ottiene un
polinomio in z i cui coefficienti possono essere determinati con
l’algoritmo LMS, ponendo z=(xx0)
f (x)=f (x0)+f ’(x0)(xx0)+½f ’’(x0)(xx0)2+…
Sistemi di supporto alle decisioni - Leonardo Rigutini
Perceptron  1
Perceptron
Modello singleneuron con funzione di attivazione a soglia
Sistemi di supporto alle decisioni - Leonardo Rigutini
Perceptron  2
Risolve problemi di classificazione a due classi, C1 e C2,
modellando la trasformazione
f : n {1,1}
attraverso la funzione  (x,w)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Perceptron  3
Learning rule: Perceptron error correction rule
Adattamento dei pesi in base all’errore che la rete commette rispetto
alla risposta desiderata, detta target
Sistemi di supporto alle decisioni - Leonardo Rigutini
Perceptron  4
Rinforzo delle connessioni favorevoli al target ed
indebolimento di quelle sfavorevoli
Alla nesima iterazione, t(n)={1,1} , y(n)={1,1}
y(n) uguale a t(n) pesi invariati
y(n) diverso da t(n) pesi modificati
Ovvero, per xi(n)>0…
y(n)=+1, t(n)=1: decremento del peso e di y(n+1)
y(n)=1, t(n)=+1: incremento del peso e di y(n+1)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Perceptron  5
Procedura di training: dato il training set linearmente
separabile
L ={(x(m),t(m)) | m=1,2,…,M}
Inizializzazione casuale dei pesi
Presentazione di un vettore di input x=(x1,…,xp) e della risposta
desiderata t
Calcolo della risposta attuale y
Modifica dei pesi mediante la perceptron error correction rule
Ripetizione del passo 2) fino a quando la rete risponde
correttamente a tutti gli esempi di training
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  1
Supponiamo che al perceptron vengano presentate le coppie
(xi,yi), per 1im (training set)
Si utilizzi la seguente versione (semplificata) dell’algoritmo di
aggiornamento dei pesi
Nota
È equivalente all’algoritmo
classico, con  =1/2, produce
cioè un rinforzo delle
connessioni favorevoli al
target ed un indebolimento di
quelle sfavorevoli
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  2
Per ogni iperpiano separatore u di norma unitaria, cioè tale che
yi(uxi)0, per 1im, e avente u =1, si definisce il
margine
(u) = min1im yi(uxi)
come la distanza dall’iperpiano separatore u dell’elemento
del training set ad esso più vicino
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  3
Teorema di convergenza
(Rosenblatt, Principles of Neurodynamics, 1962)
Dato un qualunque training set linearmente separabile con
margine (u) rispetto ad un qualunque iperpiano separatore u,
l’error correction rule determina un iperpiano separatore w
(generalmente diverso da u) dopo al più M passi, con
max 1im x i 
M  

  (u)

2
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  4
Dimostrazione
Sia w1=(0,0,…,0) l’ipotesi iniziale. Indichiamo con wT
l’ipotesi dopo T1 passi dell’algoritmo, per un qualunque T>1. Sia
M il numero di aggiornamenti eseguiti nei T1 passi e siano
1t1…<tMT i passi in cui gli aggiornamenti sono stati effettuati.
Dato che wT è stato aggiornato l’ultima volta al passo tM, wtTM=w tM ytM
x . Quindi…
y t (w t x t )<0, perché a tM è avvenuto un aggiornamento.
M
M
M
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  5
Iterando per M volte si ottiene
Viceversa, si consideri un qualunque iperpiano separatore u
con u=1 e sia  l’angolo fra u e wT. Per la definizione di (u), si
ha:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Teorema di convergenza  6
Iterando per M volte si ottiene
Considerando entrambe le disuguaglianze, infine, si ha
che, risolvendo rispetto ad M, dimostra l’asserto. Infatti,
dato che (u) è costante, il perceptron esegue sempre un numero di
aggiornamenti maggiorato da una costante, e quindi converge ad un
iperpiano separatore in un numero di iterazioni pari, al più, a detta
costante.
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sul perceptron...
Comportamento del perceptron: cambiamento della pendenza
della posizione del contorno di decisione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo Pocket  1
Quando l’insieme di apprendimento non è linearmente separabile, il
perceptron non può apprendere in maniera ottima e, in particolare, il
training non converge in un numero finito di passi e la dinamica
dell’error correction rule può divenire oscillatoria
Nei problemi reali, è sufficiente talvolta calcolare la separazione
lineare “migliore”, relativamente ad un ambiente di apprendimento
non separabile
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo Pocket  2
L’algoritmo Pocket è una variante dell’algoritmo di apprendimento
del perceptron, proposta da Gallant (1990)
Durante l’apprendimento, i pesi “migliori” vengono conservati in
una “tasca”  pocket  e aggiornati solo quando viene calcolato
un nuovo vettore dei pesi che classifica correttamente un maggior
numero di pattern
Sistemi di supporto alle decisioni - Leonardo Rigutini
Algoritmo Pocket  3
Implementa un meccanismo di ricompensa dei pesi “buoni”,
piuttosto che penalizzare (correggere) i pesi a fronte di pattern non
classificati correttamente
Si definisce il “miglior” insieme dei pesi come quello che fornisce la
sequenza più lunga di responsi corretti sui pattern dell’insieme di
apprendimento: lo si conserva nel “pocket” con la lunghezza della
sequenza di pattern classificati correttamente
Per ciascun insieme di pesi nuovo, viene mantenuto un contatore per la
lunghezza della sequenza di pattern fino al primo fallimento
Se il nuovo insieme dei pesi classifica correttamente una sequenza di
lunghezza maggiore, viene spostato nel “pocket”
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti neurali a strato singolo
Riassumendo…
Deltarule
Risolve problemi lineari (nei parametri o pesi)
Converge asintoticamente alla soluzione
Perceptron error correction rule
Risolve problemi linearmente separabili
Converge alla soluzione in un numero finito di passi, se
esiste la soluzione
Altrimenti, per pattern non linearmente separabili, si
può usare l’algoritmo Pocket
Sistemi di supporto alle decisioni - Leonardo Rigutini
Le reti neurali multistrato
Parallel distributed processing
Le reti neurali artificiali sono sistemi di calcolo distribuiti e massicciamente
paralleli, formati da un elevato numero di processori:
molto semplici
strutturalmente identici
fittamente interconnessi
dotati ciascuno di una propria memoria locale
eventualmente provvisti di connessioni con l’esterno
Nella terminologia delle reti neurali i processori vengono detti neuroni
Sistemi di supporto alle decisioni - Leonardo Rigutini
Il flusso dell’informazione
Ciascun neurone elabora l’informazione contenuta:
nella propria memoria locale
negli stimoli provenienti dall’esterno e/o dagli altri neuroni della
rete, raccolti tramite le connessioni di ingresso
L’elaborazione dà luogo a:
uno stato interno, detto attivazione
un segnale di risposta, funzione dell’attivazione, il quale viene
propagato attraverso le connessioni di uscita per stimolare altri
neuroni e/o essere accessibile all’esterno
Sistemi di supporto alle decisioni - Leonardo Rigutini
La natura distribuita delle reti neurali
I neuroni non hanno alcuna cognizione, né controllo, sulla
provenienza degli stimoli, e quindi “ignorano” la struttura
della rete di cui fanno parte
Effettuano un’elaborazione di tipo locale
La mutua influenza fra l’operato dei singoli neuroni e il
comportamento globale della rete risiede nella disposizione
delle connessioni
In breve:
i neuroni trasformano gli stimoli in risposte
le connessioni distribuiscono le risposte in forma di
stimoli
Sistemi di supporto alle decisioni - Leonardo Rigutini
La memoria locale
Il contenuto della memoria locale di ciascun neurone
determina la modalità di risposta agli stimoli, e dunque
introduce una differenziazione funzionale fra elementi di
calcolo strutturalmente identici
La memoria locale è costituita dai cosiddetti pesi sinaptici,
che modulano il contributo degli stimoli all’attivazione del
neurone
La maggior parte delle reti neurali sono provviste di
meccanismi in grado di alterare il contenuto delle
memorie, al fine di modificare il comportamento globale
della rete
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti neurali: capacità computazionale
L’idea sottesa è quella di “ricostruire una funzione” tramite la
composizione di unità elementari, ciascuna delle quali è in grado di
eseguire un numero limitato di semplici computazioni
Le reti neurali non eseguono istruzioni programmate ma rispondono
agli input tramite un procedimento parallelo
Non sono sequenziali
Forniscono risposte anche in corrispondenza di input mai visti (capacità
di generalizzazione)
Sono approssimatori universali di funzioni
Sono “black box”: incapacità di spiegare i risultati
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti feedforward e multistrato  1
Le unità di calcolo sono basate su computazione nel continuo
(a, attivazione del neurone)
neuroni sigmoidali: y=(a)=(wx)
neuroni a base radiale: y=f(a)=f(xw), con n+1,n+1,
definita positiva
Reti feedforward e multistrato  2
Dal punto di vista architetturale sono rappresentate da grafi
aciclici
Esiste un ordinamento parziale fra i vertici (neuroni) del grafo
Ciascun neurone può essere connesso sia ad altri neuroni che
agli ingressi
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti feedforward e multistrato  3
Propagazione in avanti
Sia S un generico ordinamento topologico dei vertici
Per ogni v, siano pa[v] i genitori di v, allora…
foreach v  S
xv= (zpa[v] wv,z xz)
Per reti multistrato lo schema di calcolo si riduce ad una
pipe sui livelli
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti multistrato
Le unità di elaborazione sono di tre tipi
Input (ricevono input dall’esterno)
Hidden (ricevono input dalle unità di ingresso o da altre unità hidden
del sistema)
Output (trasmettono segnali all’esterno del sistema)
L’attività delle unità hidden non è visibile all’esterno
Tutta l’elaborazione della rete neurale è eseguita da semplici unità
che si scambiano messaggi ed informazioni attraverso le
connessioni
segnale
Sistemi di supporto alle decisioni - Leonardo Rigutini
MultiLayer Perceptron (MLP)
Le unità di uscita combinano i
contributi delle diverse regioni
1
2
x1
o1
3
x2
3
o2
1
2
4
+1
+1
I neuroni nascosti ripartiscono
lo spazio in regioni
Sistemi di supporto alle decisioni - Leonardo Rigutini
4
L’apprendimento  1
L’apprendimento si riferisce al processo attraverso cui la rete si
adatta agli stimoli esterni in modo da essere capace di produrre le
risposte desiderate
Una “funzione errore”, definita sull’output della rete, o una funzione
“energia”, definita sul valore di attivazione di tutte le unità,
caratterizza la qualità dell’apprendimento
L’apprendimento avviene modificando i pesi sulle connessioni in
modo da minimizzare la “funzione errore” o “l’energia”
Algoritmi di apprendimento differenti impiegano euristiche diverse per
modificare i valori dei pesi
L’apprendimento dipende significativamente dalla topologia della rete
e dalle funzioni di attivazione dei neuroni
Sistemi di supporto alle decisioni - Leonardo Rigutini
L’apprendimento  2
L’apprendimento è caratterizzato dal…
Grado di supervisione  gli algoritmi di apprendimento sono
raggruppati in base al tipo di feedback che possono ricevere (o
non ricevere) da un istruttore esterno:
Apprendimento supervisionato
Apprendimento non supervisionato
Determinismo  gli algoritmi di apprendimento sono
raggruppati, in base alla natura delle regole che utilizzano, in
deterministici o stocastici
Sistemi di supporto alle decisioni - Leonardo Rigutini
L’apprendimento  3
Le reti neurali implementano “l’apprendimento da esempi”,
formalizzato matematicamente come:
Sia T={z1,…,zn} l’insieme di “training”
La rete tenta di apprendere una certa funzione sui dati
Se l’apprendimento è supervisionato zi = (ui,yi), cioè
per ogni esempio ui è specificata la rappresentazione
simbolica yi corrispondente ad ui
Nell’apprendimento non supervisionato, l’insieme di
training è specificato dagli esempi ui e nessuna
informazione viene data riguardo alla loro corretta
interpretazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
L’apprendimento  4
Apprendimento supervisionato
Si basa sul caricamento dei pesi di una rete neurale sulla base
di un insieme di apprendimento dotato di target
Differenza fondamentale rispetto alla soluzione algoritmica di
problemi: il caricamento dei pesi deve garantire la
generalizzazione a nuovi esempi
Sistemi di supporto alle decisioni - Leonardo Rigutini
Apprendimento in reti feedforward
L’apprendimento si basa sulla terna {L, N, E}, con
L ={(ui,di)UT, i=1,…,P}, insieme di training
N rete feedforward multistrato
E “grado di matching” tra dati e risposta della rete
dove e(u) è una qualunque metrica che esprime la distanza tra d(u)
e x(w,u); per esempio:
Sistemi di supporto alle decisioni - Leonardo Rigutini
La discesa sul gradiente
L’ottimizzazione (minimizzazione) della funzione errore coinvolge
tipicamente molti parametri
La discesa sul gradiente risulta la soluzione più verosimile per motivi di
efficienza computazionale
La traiettoria è attratta dai punti di minimo locale di E(w)
Il gradiente viene calcolato mediante l’algoritmo di Backpropagation
Sistemi di supporto alle decisioni - Leonardo Rigutini
Backpropagation  1
Backpropagation  Bryson & Ho (1969), Werbos (1974), le Cun
(1995), Rumelhart, Hinton & Williams (1996)
Si sfrutta la struttura grafica della rete
Si accumulano i contributi di errore su tutti gli elementi del training set
(U insieme degli ingressi)
Dall’ipotesi di architettura a grafo aciclico, segue la fattorizzazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Backpropagation  2
L’errore si propaga in direzione contraria rispetto al segnale,
cioè dalle uscite verso gli strati hidden
In particolare…
Se iO (uscite), allora
Altrimenti
segnale
Sistemi di supporto alle decisioni - Leonardo Rigutini
errore
Quale potenza computazionale ?  1
Una rete a due livelli con sigmoidi (o simili) su tutte le unità, può rappresentare
qualunque funzione booleana
Ogni funzione reale nm limitata e continua, può essere approssimata con
errore arbitrariamente piccolo da una rete a due livelli con sigmoidi sulle unità
nascoste e unità lineari sull’uscita
L’apprendimento ottimo viene conseguito con un numero di neuroni nascosti pari,
al più, alla cardinalità dell’ambiente di apprendimento
Sistemi di supporto alle decisioni - Leonardo Rigutini
Quale potenza computazionale ?  2
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  1
Analogamente a quanto accade nei sistemi biologici, l’addestramento delle
reti neurali artificiali si fonda su due presupposti essenziali:
La disponibilità a priori di un congruo repertorio di “comportamenti”
possibili
L’esistenza di un meccanismo atto a selezionare da tale repertorio,
verosimilmente per tentativi ed errori, i “comportamenti” più
rispondenti alle sollecitazioni provenienti dall’ambiente (stimoli ed
obiettivi)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  2
La rete neurale viene addestrata su un learning set
Ogni esempio viene passato alla rete, calcolandone l’errore, che
verrà accumulato e successivamente usato per modificare i pesi
Il learning set viene presentato alla rete un certo numero di volte; la
presentazione dell’intero insieme costituisce un’epoca di
apprendimento
L’errore medio diminuisce progressivamente
Troppe epoche possono causare overfitting (eccessiva specializzazione
sulle istanze contenute nel learning set)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  3
L’addestramento delle reti neurali si basa sulla constatazione che se l’errore
cambia al variare dei pesi allora può essere inteso come una funzione dei
pesi stessi, E(W)
E(W) avrà dei punti di minimo (corrispondenti a particolari configurazioni
dei pesi)
Tali punti possono pertanto essere
calcolati con le tecniche di ricerca del
minimo di una funzione, che si basano
sullo studio della sua derivata
Ad ogni iterazione i pesi vengono modificati di
una percentuale  (learning rate);  piccolo
comporta un apprendimento più lento ma spesso
più accurato
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  4
Il fatto di muoversi nella direzione indicata dal gradiente non significa
necessariamente raggiungere il minimo della funzione!
Se il learning rate è troppo grande si può saltare lontano dal minimo
(eventualmente fuori dal suo bacino di attrazione)
Oltre al minimo globale, la superficie di errore, per problemi
significativi, è solitamente costellata da minimi locali, che sono
attrattori per la dinamica di discesa del gradiente
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  5
Problemi legati al dominio
Maggiore la cardinalità dello spazio degli ingressi maggiore la
possibilità di lineare separabilità dei dati, ma anche la difficoltà nel
discernere le feature significative
Esempio: x1 può variare fra 0.05 e 0.02, mentre x2 può variare fra
100 e 10000; numericamente x2 pesa più di x1, ma x1 potrebbe
essere più rilevante nel definire il comportamento della funzione
Problemi legati ai dati
Possono essere costosi da ottenere
Possono essere poco rappresentativi, perché concentrati in
particolari aree del dominio
Possono essere affetti da errore
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  6
Backpropagation è un algoritmo ottimo nel senso della teoria
della complessità: O(W) invece di O(W 2)
La discesa del gradiente può rimanere intrappolata in minimi
locali della funzione errore
Una volta caricati i pesi per l’insieme di apprendimento,
non c’è garanzia di un buon apprendimento del concetto...
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sull’apprendimento  7
Dalla teoria del PAC (Probably Approximately Correct) learning: per
ottenere un errore non superiore a  sul test set…
…si apprende il training set fino ad un errore inferiore a /2
…si usano almeno
32W

ln
32M

pattern per l’apprendimento, dove W è il numero dei pesi ed M il
numero totale di unità nascoste (E. Baum, Neural Computation,
1989)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Backpropagation con momento  1
La presenza del termine momento garantisce che la rete non
reagisca solo alle variazioni locali del gradiente, ma tenga
anche conto della storia recente di tali variazioni
Agendo da filtro passabasso, il momento assicura inoltre che
il comportamento della rete non risenta delle piccole
oscillazioni della superficie d’errore
Senza il momento, l’apprendimento può venire
intrappolato in un minimo locale “poco profondo”, mentre
in presenza del momento i piccoli bacini di attrazione
possono essere “saltati”
Sistemi di supporto alle decisioni - Leonardo Rigutini
Backpropagation con momento  2
L’aggiornamento dei pesi viene modificato aggiungendo un
termine relativo all’aggiornamento al passo precedente:
normalmente, i termini relativi al contributo locale del
gradiente ed al momento vengono composti a formare una
combinazione lineare convessa (01)
w(t+1) =  (E(t+1)) + (1)w(t)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Resilient Propagation  1
Gli MLP utilizzano, di solito, funzioni di trasferimento sigmoidali nello strato
hidden
Tali funzioni vengono anche dette “squashing”, data la loro capacità di
comprimere input infiniti in un intervallo limitato di output
Le funzioni sigmoidali sono caratterizzate da una derivata che approssima zero al
tendere di x a ; questo causa problemi quando si utilizzano tecniche di discesa
lungo il gradiente per l’apprendimento, dato che il gradiente può assumere valori
molto piccoli nelle zone di “saturazione” della sigmoide, non garantendo
aggiornamenti significativi di pesi e soglie, anche per valori lontani dall’ottimo
Sistemi di supporto alle decisioni - Leonardo Rigutini
Resilient Propagation  2
Nell’algoritmo di Resilient Propagation viene utilizzata soltanto
l’informazione sul segno del gradiente per determinare la “direzione” di
aggiornamento dei pesi, mentre la norma del gradiente non ha nessun
effetto sull’apprendimento
Sistemi di supporto alle decisioni - Leonardo Rigutini
Resilient Propagation  3
Il tasso di apprendimento viene determinato ed adattato singolarmente per ogni
peso
i viene incrementato ogni volta che la derivata della funzione costo,
relativamente a quel peso, mantiene il segno per due iterazioni successive
i viene decrementato se la derivata cambia segno
Il valore di i rimane costante se il gradiente è nullo in quella direzione
Tutte le volte che i pesi mostrano un andamento oscillante, il tasso di
apprendimento viene ridotto, ed aumentato se, viceversa, il cambiamento avviene
sempre nella stessa direzione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Quante unità nascoste ?
Usando un numero arbitrariamente grande di unità nascoste si può approssimare qualunque
funzione finita in un dominio finito
Non c’è regola a priori per determinarne il numero degli hidden
Il numero di unità nascoste definisce il numero di possibili suddivisioni dello spazio degli
ingressi
Se si ha conoscenza a priori sul problema da risolvere, si possono fare stime grossolane sulla
dimensione dello strato interno (stati da codificare), altrimenti la selezione architetturale
viene fatta per mezzo di tecniche di tipo trialanderror
Suggerimento: selezionare, inizialmente, architetture “piccole” (ad es., log2(Nin+Nout)
neuroni nascosti) ed aumentare la complessità della rete (e la sua capacità computazionale)
solo se necessario
Sistemi di supporto alle decisioni - Leonardo Rigutini
Overfitting
Il problema dell’overfitting è in parte legato al problema del
dimensionamento dell’architettura della rete per uno specifico compito
L’architettura della rete è troppo complessa per il problema in esame
L’architettura della rete è troppo semplice per il problema in esame
 La rete perde la capacità di generalizzare
Sistemi di supporto alle decisioni - Leonardo Rigutini
Come prevenire l’overfitting
Apprendimento incrementale: la rete aggiunge nodi alla sua struttura
durante l’apprendimento (growing)
Apprendimento competitivo: le unità hidden sono forzate a rispondere ad
un dato input in tempi diversi
Strategie evoluzionistiche: la rete modifica la sua struttura parametrica
durante l’apprendimento
Fermare il processo di training in anticipo (tecniche di
crossvalidation per early stopping)
Aggiungere rumore ai dati
 Soluzioni che controllano il valore assunto dai parametri
Sistemi di supporto alle decisioni - Leonardo Rigutini
Crossvalidation
L’addestramento di una rete è un processo iterativo in cui i parametri
della rete vengono modificati con l’obiettivo di minimizzare l’errore
commesso
La crossvalidation è il processo attraverso il quale si controlla
l’andamento dell’errore su dati non noti alla rete (sui quali non è stata
addestrata) per fermare il training quando l’errore su tali dati comincia a
crescere
Sistemi di supporto alle decisioni - Leonardo Rigutini
Addestramento con dati rumorosi
Per ogni pattern x dell’insieme di training, alla rete viene
presentato il pattern (x), dove  è un vettore di rumore
casuale: ogni nuova presentazione di x alla rete risulterà
alterata da un diverso rumore
L’introduzione di rumore riduce la possibilità che la rete si
specializzi troppo sui dati di training
È stato provato che addestrare le reti con dati affetti da
rumore migliora la loro capacità di generalizzazione
(Sietsma e Dow, 1991)
Un altro modo per introdurre rumore nel processo di
training consiste nell’aggiornare i pesi dopo ogni
presentazione e riordinare gli esempi casualmente alla fine
di ogni iterazione (online learning)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Cambiando il modello neuronale…
Reti Radial Basis Function (RBF)
Architettura composita per problemi di classificazione ed
approssimazione funzionale
Modello a due strati


hidden layer: neuroni con funzione di attivazione che simula un campo
recettivo localizzato
output layer: neuroni con funzione di attivazione lineare o sigmoidale
MLP e RBF: modelli equivalenti da un punto di vista funzionale
Sistemi di supporto alle decisioni - Leonardo Rigutini
Non solo rette!
RBF è una rete neurale in grado di riconoscere pattern
“clusterizzati”: molti problemi di classificazione presentano dati in
ingresso concentrati attorno ad un insieme di “centroidi”
Rete neurale di tipo Radial Basis Function (RBF)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti neurali RBF  1
La rete neurale è un MLP, con neuroni nascosti a base
radiale; il modello di neurone a base radiale presuppone il
calcolo dell’attivazione secondo la formula
a(w1, u0) = w1 u0/
mentre la funzione di uscita è
o(a) = ea
con la classica forma a campana
2
La rete feedforward può essere addestrata tramite
Backpropagation (tutte le funzioni coinvolte sono
differenziabili)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Reti neurali RBF  2
Si dimostra che un siffato MLP (con neuroni di output sigmoidali o lineari, in
dipendenza dal problema) e con un numero sufficiente di neuroni hidden RBF, è
in grado di modellare in maniera ottima insiemi di apprendimento separabili per
ipersfere (iperellissoidi)
Dopo l’apprendimento, i pesi w1 approssimano le posizioni dei centroidi,
mentre  approssima il raggio dell’ipersfera minima contenente la classe
Le reti neurali con neuroni a base radiale nello strato hidden e neuroni lineari
nello strato di uscita sono approssimatori universali, così come gli MLP, se
dotate di un numero sufficiente di neuroni hidden: qualsiasi funzione continua
può essere approssimata con un qualsiasi grado di accuratezza
Sistemi di supporto alle decisioni - Leonardo Rigutini
Gli autoassociatori  1
Un autoassociatore neurale è una rete multistrato con un
numero di uscite pari al numero degli ingressi
L’autoassociatore viene addestrato in modo da riprodurre sulle
uscite il vettore di ingresso, minimizzando la norma
quadratica del vettore differenza
Se il numero di neuroni nascosti è inferiore alle componenti di
input, l’attivazione dei neuroni nascosti realizza una
rappresentazione compressa della informazione in ingresso; in
particolare…
…i pesi dagli ingressi ai neuroni nascosti rappresentano i parametri di
compressione
…i pesi dai neuroni nascosti alle uscite definiscono la decompressione
della rappresentazione contenuta nello strato nascosto
Sistemi di supporto alle decisioni - Leonardo Rigutini
Gli autoassociatori  2
La rappresentazione nello strato nascosto è ricavata
ottimizzando l’errore di ricostruzione su un insieme di dati
di esempio
In tal senso, gli autoassociatori neurali realizzano un
algoritmo di estrazione delle componenti principali non
lineare
Gli autoassociatori possono inoltre essere utilizzati come
classificatori, in base al principio secondo il quale riescono
ad associare bene solo vettori provenienti dalla
distribuzione dei dati con cui sono stati addestrati
Sistemi di supporto alle decisioni - Leonardo Rigutini
Gli autoassociatori  3
In altre parole, una volta addestrato con dati estratti da una
certa distribuzione, l’autoassociatore rappresenta un prototipo
per tale classe
Si può verificare se un vettore appartiene ad una classe di cui
l’autoassociatore è il modello (o prototipo) calcolando la
distanza fra il vettore di ingresso e l’uscita prodotta
Sistemi di supporto alle decisioni - Leonardo Rigutini
Gli autoassociatori  4
Un classificatore per più classi può essere costruito in modo modulare
definendo un autoassociatore (prototipo) per ogni classe
Un vettore di ingresso viene classificato presentandolo in parallelo a
tutti gli autoassociatori e attribuendolo alla classe corrispondente
all’autoassociatore per il quale la distanza fra ingresso e uscita è
minima
Si può anche introdurre una soglia di reiezione, considerando non
classificati quei vettori per i quali la distanza è superiore a tale
soglia o per i quali la differenza di distanza fra due o più
autoassociatori è inferiore alla soglia
L’apprendimento di ogni autoassociatore può essere effettuato
utilizzando solo esempi della classe a cui corrisponde
Sistemi di supporto alle decisioni - Leonardo Rigutini
Gli autoassociatori  5
Per migliorare le prestazioni possono essere introdotti nell’insieme dei dati usati
per l’apprendimento anche esempi negativi, in genere appartenenti a quelle classi
che più si confondono con quella che si deve riconoscere
Apprendimento e superfici di decisione per un autoassociatore
addestrato con e senza esempi negativi
Sistemi di supporto alle decisioni - Leonardo Rigutini
Support Vector Machine
Introduzione  1
Le Support Vector Machine (SVM) sono state sviluppate
presso gli AT&T Bell Laboratories, a partire dai primi anni
`90, da Vapnik e colleghi (Boser et al., 1992, Guyon et al.,
1993, Cortes e Vapnik, 1995, Schölkopf et al., 1995, Vapnik
et al., 1997)
Dato il contesto industriale, la ricerca sulle SVM ha finora
avuto una decisa inclinazione applicativa
Sistemi di supporto alle decisioni - Leonardo Rigutini
Introduzione  2
Primi lavori relativi a:
OCR (Optical Character Recognition, dove in breve le
SVM divennero competitive con i metodi migliori)
Riconoscimento di oggetti (Blanz et al., 1996)
Identificazione di oratori (Schmidt, 1996)
Identificazione di volti in immagini (Osuna, et al. 1997)
Classificazione di testi (Joachims, 1997)
Bioinformatica: classificazione di sequenze di proteine,
gene expression, informazioni filogenetiche
Sistemi di supporto alle decisioni - Leonardo Rigutini
Introduzione  3
L’algoritmo Support Vector, alla base delle SVM,
…è una generalizzazione dell’algoritmo Generalized
Portrait, sviluppato in Russia nei primi anni `60 (Vapnik
e Lerner, 1963, Vapnik e Chervonenkis, 1964)
…appartiene alla categoria degli algoritmi di statistical
learning theory, la teoria di VapnikChervonenkis
(Vapnik, Chervonenkis 1974, Vapnik 1982, 1995)
Essenzialmente, la teoria VC caratterizza le proprietà degli
algoritmi di apprendimento che permettono loro di
“estendere la conoscenza” a dati nuovi, in base ad elementi
appresi in precedenza
Sistemi di supporto alle decisioni - Leonardo Rigutini
Introduzione  4
Una SVM è un classificatore binario che apprende il
confine fra esempi appartenenti a due diverse classi
Funziona proiettando gli esempi in uno spazio
multidimensionale e cercando un iperpiano di separazione
in questo spazio
L’iperpiano di separazione massimizza la sua distanza (il
“margine”) dagli esempi di training più vicini
Proprietà generali delle SVM:
improbabile l’overfitting
capacità di gestire dati con molte feature
estrazione dell’informazione “più significativa”
contenuta nel data set in input
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificazione
Nel caso della classificazione di dati appartenenti a due sole classi, il
processo di apprendimento può essere formulato come segue:
dato un insieme di funzioni di soglia
dove  è un insieme di parametri reali, e dato un insieme di esempi
preclassificati (x1,y1),…,(xm,ym), xiN, yi{1,1}, presi da una
distribuzione sconosciuta P(x,y), si vuole calcolare una funzione f
che minimizzi l’errore teorico:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Errore teorico
L’insieme di parametri reali  genera una macchina in grado di
risolvere un particolare problema (ad esempio  può corrispondere ai
pesi delle sinapsi di una rete neurale)
Le funzioni f sono le ipotesi, e l’insieme {f(x): } è lo spazio H
delle ipotesi
L’errore teorico rappresenta una misura di quanto sia buona un’ipotesi
nel predire la classe yi di un punto x
L’insieme delle funzioni può essere realizzato da un MLP classico o con
neuroni RBF, con un numero opportuno di unità nascoste
Sistemi di supporto alle decisioni - Leonardo Rigutini
Errore empirico
La distribuzione di probabilità P(x,y) non è nota, quindi non è possibile
calcolare l’errore teorico R(); tuttavia è disponibile un campione di
P(x,y): il training set
si può calcolare un’approssimazione di R(), l’errore empirico
Remp():
La legge dei grandi numeri garantisce che l’errore empirico converge in
probabilità all’errore teorico
Sistemi di supporto alle decisioni - Leonardo Rigutini
VCdimension
La VCdimension dello spazio di ipotesi H (o del classificatore f) è un
numero naturale che corrisponde al più grande numero di punti che
possono essere separati in tutti i modi possibili dall’insieme di funzioni
f
In altre parole, dato un insieme di l punti, se per ognuna delle 2l
possibili classificazioni (1,1) esiste una funzione in {f} che assegna
correttamente le classi, allora si dice che l’insieme di punti viene
separato dall’insieme di funzioni
La VCdimension è una misura della complessità dell’insieme H
Sistemi di supporto alle decisioni - Leonardo Rigutini
VCdimension ottima
La teoria della convergenza uniforme in probabilità, sviluppata da
Vapnik e Chervonenkis, fornisce anche un limite alla deviazione
dell’errore empirico dall’errore teorico
Fissato , con 0 1, vale la disuguaglianza:
dove h è la VCdimension di f
Sistemi di supporto alle decisioni - Leonardo Rigutini
Minimizzazione dell’errore teorico
Per ottenere l’errore teorico minimo, occorre minimizzare sia l’errore
empirico sia il rapporto tra la VCdimension ed il numero di punti (h/l)
L’errore empirico è solitamente una funzione decrescente di h, quindi,
per ogni dato numero di punti, esiste un valore ottimale della
VCdimension (tradeoff Remp e h/l)
L’algoritmo SVM risolve efficacemente questo problema minimizzando
contemporaneamente la VCdimension ed il numero di errori sul
training set
Sistemi di supporto alle decisioni - Leonardo Rigutini
Caso 1:
dati linearmente separabili
Classificatore lineare su
dati linearmente separabili  1
Ipotesi: insieme di dati linearmente separabili; si vuole
calcolare il miglior iperpiano separatore
Un insieme di dati è linearmente separabile quando esiste
una coppia (w,b) tale che
wxi+b  0
per xiC1
wxi+b < 0
per xiC2
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatore lineare su
dati linearmente separabili  2
Lo spazio delle ipotesi in questo caso è formato
dall’insieme di funzioni
(sign, discriminatore binario: +/, 0/1, vero/falso, etc.)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Separazione lineare
(es. perceptron)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Separatori lineari
Quale separatore è ottimo?
Sistemi di supporto alle decisioni - Leonardo Rigutini
Iperpiani di separazione  1
La distanza tra un punto x e l’iperpiano associato alla
coppia (w,b) è:
Se l’iperpiano wxb=0 separa il training set D, si definisce
margine la quantità (w,D)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Iperpiani di separazione  2
Come scegliere la parametrizzazione?
Un iperpiano separatore è parametrizzato dai coefficienti
w e b, ma la scelta non è unica: moltiplicando i
parametri per una costante positiva si ottiene lo stesso
iperpiano
Occorre fissare w
Prima soluzione: si fissa w=1, nel qual caso
dw(x)=wxb e (w,D)=mini yi(wxib)
Altrimenti… si fissa w in modo tale che
(w,D)=1/w, cioè si impone mini yi(wxib)=1
è una parametrizzazione datadependent
Sistemi di supporto alle decisioni - Leonardo Rigutini
Iperpiani di separazione  3
Più in generale, la distanza tra l’iperpiano (w,b) e il più
vicino punto dell’insieme dei dati è funzione di
1/w
Se si impone wA, la distanza dell’iperpiano dal punto
più vicino deve essere maggiore di 1/A
• Si considerano solo gli iperpiani
che non intersecano nessuna
delle sfere di raggio 1/A centrate
sui punti dell’insieme di dati
Sistemi di supporto alle decisioni - Leonardo Rigutini
Iperpiani di separazione  4
Se i dati sono linearmente separabili, lo scopo della SVM è
quello di trovare, tra tutti gli iperpiani che classificano
correttamente il training set, l’iperpiano che ha norma
minima (w minima), cioè margine massimo rispetto ai
punti del training set
Le classi dei cerchi e dei quadrati
sono separate dal piano
tratteggiato, con un margine
piccolo (a), o grande (b)
(a)
(b)
Nel caso (b) ci si aspetta un minor
rischio di overfitting, ovvero una
maggiore capacità di
generalizzazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Massimo margine
L’iperpiano ottimo è quello che massimizza il margine, cioè
la distanza tra se stesso e i punti più vicini dell’insieme di
dati
Per costruire l’iperpiano ottimo, occorre classificare
correttamente i punti del training set nelle due classi
yi{1,1} minimizzando la norma di w
Il problema può essere formulato come segue:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Lagrangiana  1
Questo problema si può risolvere con la tecnica dei
moltiplicatori di Lagrange in cui si introduce un
moltiplicatore per ogni vincolo
La lagrangiana del problema è:
i
in cui =(1,…,l) è il vettore dei moltiplicatori di
Lagrange
Sistemi di supporto alle decisioni - Leonardo Rigutini
Lagrangiana  2
La lagrangiana deve essere minimizzata rispetto a w e b e
contemporaneamente massimizzata rispetto a ≥0: si cerca
un punto di sella
Differenziando rispetto a w e b si ottiene…
Sistemi di supporto alle decisioni - Leonardo Rigutini
Lagrangiana  3
w* può essere scritto come una combinazione lineare dei
vettori xi del training set:
w* = i i *yi xi  f(x) = w*x + b = i i *yi xi  x + b
I dati appaiono solo all’interno di prodotti scalari
Sostituendo il valore calcolato w* nella lagrangiana si può
riformulare il problema in una forma duale più semplice
Nella formulazione duale, la funzione da ottimizzare è una
funzione quadratica nei i
Sistemi di supporto alle decisioni - Leonardo Rigutini
Lagrangiana  4
Sistemi di supporto alle decisioni - Leonardo Rigutini
Lagrangiana  5
Nel nuovo problema i vincoli originali sono sostituiti da
vincoli sui moltiplicatori ed i vettori del training set appaiono
solo sotto forma di prodotti scalari
La complessità del problema duale non dipende dalla
dimensione degli ingressi, ma dalla cardinalità del training set
Sistemi di supporto alle decisioni - Leonardo Rigutini
Support vector  1
La soluzione del nuovo problema fornisce i moltiplicatori di
Lagrange
L’iperpiano ottimo si ricava…
…dall’espressione di w*, dopo la sostituzione dei moltiplicatori
calcolati
…mentre il valore di b* deriva dall’applicazione delle condizioni
KuhnTucker, i*(yi(w*xb*)1)=0
*

Il classificatore è dato da
per ogni vettore x
Sistemi di supporto alle decisioni - Leonardo Rigutini
*
Support vector  2
Nella soluzione, tutti i punti xi per cui il corrispondente
moltiplicatore i è strettamente maggiore di zero vengono
detti support vector e si trovano su uno dei due iperpiani
H1, H2 equidistanti dall’iperpiano ottimo e ad esso paralleli
(per le condizioni di KuhnTucker)
Tutti gli altri punti del training set hanno il corrispondente
i uguale a zero e non influenzano il classificatore
I support vector sono i punti critici del training set e sono i
più vicini all’iperpiano di separazione; se tutti gli altri punti
venissero rimossi o spostati senza oltrepassare i piani H1 e
H2 e l’algoritmo di apprendimento venisse ripetuto,
darebbe esattamente lo stesso risultato
Sistemi di supporto alle decisioni - Leonardo Rigutini
Da notare…
L’iperpiano ottimo di separazione è determinato solo in base ai
support vector che, in generale, sono in numero esiguo rispetto
alla cardinalità l del training set
Tutta l’informazione contenuta nel training set è concentrata nei
soli vettori di supporto, che sono gli unici dati sui quali si effettua
l’apprendimento

r
Sistemi di supporto alle decisioni - Leonardo Rigutini
Caso 2:
classificatore lineare su dati non
linearmente separabili
Classificatore lineare su
dati non linearmente separabili  1
Per come è stato definito, il classificatore a supporto
vettoriale lineare non è in grado gestire casi in cui le classi
non siano linearmente separabili
Come risolvere il problema?
Rilassare i vincoli di corretta classificazione, tollerando
un certo numero di errori
Realizzare altre superfici di separazione oltre l’iperpiano
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatore lineare su
dati non linearmente separabili  2
Piano separatore per un insieme di punti non linearmente
separabili; il piano ha distanza b/w dall’origine e viene
determinato dai support vector (i punti cerchiati)
Il punto in posizione anomala dista /w  dalla sua classe
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  1
Generalizzazione dell’iperpiano ottimo
Nella fase di ottimizzazione si rilassa il vincolo di esatta
classificazione dei campioni del training set (soft
margin), introducendo delle variabili slack i
I vincoli diventano:
wxib  1  i
per yi= 1
wxib  1  i
per yi= 1
con i  0, per ogni i
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  2
In base al valore assunto dalla corrispondente variabile di
slack, i punti del training set saranno:
disposti al di là degli iperpiani H1 e H2 e correttamente
classificati (i=0)
posti tra gli iperpiani H1 e H2 e correttamente
classificati (0<i<1)
erroneamente classificati (i >1)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  3
Il problema può essere formulato come
dove C e k sono parametri che devono essere determinati a
priori: ad un alto valore di C corrisponde un’alta penalità
dovuta agli errori
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  4
Le variabili di slack si introducono per rilassare il vincolo
di separabilità
i  0  xi ha margine <w1
In pratica, l’algoritmo SVM cerca di minimizzare w e di
separare i punti dati commettendo il numero minimo di
errori possibile
La soluzione al problema di ottimizzazione si trova in modo
analogo al caso linearmente separabile
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  5
La lagrangiana del problema è:
in cui i moltiplicatori =(1,…,l), =(1,…,l) sono
associati ai vincoli
L deve essere minimizzata rispetto a w, b e
=[1,…,l] e massimizzata rispetto a ≥0 e ≥0
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  6
Supponendo k=1 per semplificare i calcoli, si arriva ad una
riformulazione duale del problema simile ancora al caso
linearmente separabile
Sistemi di supporto alle decisioni - Leonardo Rigutini
Dati non linearmente separabili  7
La soluzione del problema è identica a quella del caso
separabile tranne per il vincolo sui moltiplicatori, che
adesso sono limitati superiormente da C
Il classificatore è:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Caso 3:
classificatore non lineare
Classificatore non lineare  1
Alternativamente, nel caso di dati non linearmente
separabili, si introduce un mapping (x) verso uno spazio
di dimensione “molto più grande”, in cui gli esempi che
compongono l’insieme degli ingressi siano linearmente
separabili
Invece di aumentare la complessità del classificatore
(che resta un iperpiano) si aumenta la dimensione dello
spazio delle feature
In dipendenza della dimensione dello spazio in cui è
formulato il problema originale, il mapping può portare a
spazi “trasformati” a dimensione molto elevata (fino a 106)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatore non lineare  2
Le due classi rappresentate dai cerchi e dai quadrati nello
spazio di input non sono linearmente separabili, ma
attraverso la funzione  i punti vengono mappati in uno
spazio in cui divengono linearmente separabili
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio: le due spirali  1
Esiste un iperpiano nello spazio delle feature per cui i dati
sono linearmente separabili
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio: le due spirali  2
Sistemi di supporto alle decisioni - Leonardo Rigutini
Un’altra situazione possibile…
: x (x)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Funzioni kernel
Supponiamo di mappare i dati iniziali non linearmente
separabili in uno spazio di dimensione superiore in cui essi
siano linearmente separabili, usando una funzione di mapping
: dH
Uno spazio di dimensione maggiore causa però seri problemi
di calcolo, perché l’algoritmo di apprendimento deve lavorare
con vettori di grandi dimensioni (con molte componenti)
Tuttavia, in questa situazione, l’algoritmo di apprendimento
dipende dai dati solamente tramite il prodotto delle loro
immagini attraverso  in H, cioè tramite funzioni della
forma (xi)·(xj)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Kernel
Per ovviare al problema dell’aumento della dimensione dei
vettori di feature si introduce quindi una funzione kernel
che restituisce il prodotto delle immagini, attraverso , dei
suoi due argomenti:
K(xi,xj)= (xi)(xj)
 è possibile evitare di eseguire il prodotto esplicito tra le
immagini dei vettori, è sufficiente conoscerne la “forma
funzionale”
Pertanto è possibile sostituire K all’interno dell’algoritmo e
ignorare la forma esplicita di 
Sistemi di supporto alle decisioni - Leonardo Rigutini
Quali funzioni sono kernel ?
Per alcune funzioni K(xi,xj) verificare che
K(xi,xj)=(xi)T(xj) è complesso
Teorema di Mercer
Ogni funzione simmetrica semidefinita positiva è un
kernel
L’impiego di funzioni kernel di fatto “nasconde” il mapping
nello spazio multidimensionale
Sistemi di supporto alle decisioni - Leonardo Rigutini
Matrice kernel
È una rappresentazione matriciale della funzione kernel
(argomenti: gli m vettori di apprendimento):
Contiene tutte le informazioni necessarie per
l’apprendimento
Riassume informazioni sui dati e sul kernel
È simmetrica e semidefinita positiva
Sistemi di supporto alle decisioni - Leonardo Rigutini
Ancora sulla lineare separabilità…
Sostituendo (xi) (xj) con K(xi,xj) nell’algoritmo, si genera
una Support Vector Machine che “lavora” in H e fornisce il
risultato nella stessa quantità di tempo che impiegherebbe se
lavorasse con i dati originali non trasformati
Tutte le considerazioni fatte nel caso linearmente separabile
restano valide, poiché si sta costruendo un classificatore
lineare in uno spazio differente
In pratica, l’estensione a superfici di decisione complesse
avviene in maniera semplice: mappando la variabile in input
x in uno spazio di dimensione maggiore e lavorando poi con
una classificazione lineare nel nuovo spazio
Sistemi di supporto alle decisioni - Leonardo Rigutini
Feature expansion
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatore non lineare  1
Un punto x viene mappato in un vettore di “feature” tramite
la funzione : x(x)=(a11(x),a22(x),…) dove gli ai
sono numeri reali e le i sono funzioni reali
Quindi, si applica lo stesso algoritmo del caso linearmente
separabile sostituendo la variabile x con un nuovo vettore di
feature (x)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificatore non lineare  2
La funzione di decisione con il mapping diventa quindi:
Sostituendo i prodotti scalari (xi)·(xj) con una funzione
kernel:
si ottiene
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio  1
Supponiamo x2 e K(xi,xj)=(xi xj)2
In questo caso, lo spazio H e il mapping : 2H tale
che (xi xj)2=(xi)·(xj) sono dati da H =3 e
Infatti…
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio  2
L’XOR diventa linearmente separabile per : 2 3, con
(x1,x2)=(x1, x2, x1 x2)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio  3
L’immagine di  può esistere in uno spazio anche di
dimensione infinita, ma è solo una superficie, anche se
molto “contorta”, la cui dimensione intrinseca, il numero di
parametri necessari per specificare un punto, è la stessa
dello spazio dei vettori x
Sistemi di supporto alle decisioni - Leonardo Rigutini
Tipi di kernel  1
La funzione kernel va scelta accuratamente per il
particolare tipo di problema: è sempre possibile trasformare
l’input in uno spazio di dimensione maggiore del numero di
punti del training set e produrre un classificatore perfetto…
…Tuttavia, questi generalizzerebbe malissimo su dati
nuovi, a causa dell’overfitting
Sistemi di supporto alle decisioni - Leonardo Rigutini
Tipi di kernel  2
Tipi di kernel comunemente usati sono:
Sistemi di supporto alle decisioni - Leonardo Rigutini
Modularità
Una SVM è composta da due moduli:
Un modulo generale di apprendimento
Una funzione kernel specifica per il problema da
affrontare
Qualsiasi SVM può operare con qualsiasi kernel
Il problema di apprendere un compito difficile si sposta nel
problema di scegliere opportunamente una funzione kernel
(di nuovo un problema difficile…) per trasformarlo in un
compito facile (perché linearmente separabile)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Come scegliere un classificatore SVM ?
Per impiegare una SVM è allora necessario definire:
 tipo di kernel da impiegare
 parametri del particolare kernel
 valore di C
Non esistono criteri teorici per queste scelte; tipicamente
occorre una verifica su un insieme di validazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificazione multiclasse  1
Le SVM si applicano solo a problemi di classificazione
binaria (cioè sono capaci di predire il valore di una variabile
booleana)
Come fare per problemi multiclasse ad N classi?
Si addestrano N support vector machine
 SVM 1 apprende “Output==1” vs “Output != 1”
 SVM 2 apprende “Output==2” vs “Output != 2”
…
 SVM N apprende “Output==N” vs “Output != N”
Sistemi di supporto alle decisioni - Leonardo Rigutini
Classificazione multiclasse  2
Per predire l’output relativo ad un nuovo input, si sceglie
quella SVM che mappa il pattern nel semipiano positivo,
con massimo margine rispetto all’iperpiano separatore
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio: IRIS dataset  1
L’iris dataset contiene i dati relativi a 150 iris, appartenenti
a 3 diversi tipi: Iris setosa, Iris versicolor ed Iris virginica,
descrivendone le caratteristiche in termini di larghezza e
lunghezza di foglie e petali (in cm)
Iris setosa
Iris versicolor
Iris virginica
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio: IRIS dataset  2
Per semplicità, si considerano solo i due attributi che
portano maggior informazione riguardo alla classe di
appartenenza: la lunghezza e la larghezza del petalo
La distribuzione dei dati è
Sistemi di supporto alle decisioni - Leonardo Rigutini
Esempio: IRIS dataset  3
SVM lineare
Polinomiale (grado 2, C=)
Le classi setosa e
versicolor
vengono
separate facilmente da
un classificatore lineare
C=: non si accettano
errori
RBF (=1.0, C=)
Polinomiale (grado 10, C=)
OVERFITTING!
Polinomiale (grado 2, C=10)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Conclusioni  1
Il perceptron è lo strumento più semplice per costruire un classificatore
Problemi: uso inefficiente dei dati, overfitting, mancanza di
espressività
Le SVM risolvono questi problemi, mediante l’utilizzo di margini e di
tecniche di feature expansion
Per realizzare l’espansione dello spazio di input con un carico
computazionale accettabile si ricorre al trucco della definizione dei
kernel
La presenza del kernel evita calcoli onerosi di prodotti scalari fra
vettori ad alta dimensionalità (grazie all’uso dei moltiplicatori di
Lagrange ed al Representer Theorem)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Conclusioni  2
Le SVM sono diventate popolari perché capaci di
apprendere dataset “difficili”, con buone prestazioni in
generalizzazione
Le SVM sono attualmente fra i migliori classificatori in una
varietà di problemi (es. classificazione di testi e genomica)
Il tuning dei parametri nelle SVM è un’arte: la selezione di
uno specifico kernel e dei relativi parametri viene eseguita in
modo empirico (trialanderror)
Sistemi di supporto alle decisioni - Leonardo Rigutini
Software online e bibliografia
SVMLight: http://svmlight.joachims.org (in C)
SVMFu: http://five-percent-nation.mit.edu/SvmFu/ (in C++)
SVMTorch: http://www.idiap.ch/learning/SVMTorch.html (in C++)
SVMToolbox: http://theoval.sys.uea.ac.uk/~gcc/svm/toolbox/
B. B. Boser, I. M. Guyon, V. N. Vapnik, A training algorithm for optimal margin
classifiers, Proc. of the 5th Workshop on Computational Learning Theory, 1992.
C. Cortes and V. N. Vapnik, Support vector networks, Machine Learning, 20, pp.
125, 1995
V. N. Vapnik, Statistical learning theory. Wiley and Sons, 1998
M. Pontil and A. Verri, Properties of Support Vector Machines, Neural
Computation, 10(4), pp. 955974, 1998
C.J.C. Burges, A tutorial on support vector machines for pattern recognition, Data
Mining and Knowledge Discovery, 2(2):955974, 1998.
http://citeseer.nj.nec.com/burges98tutorial.html
Sistemi di supporto alle decisioni - Leonardo Rigutini
Valutazione della classificazione
Confusion table
 Si costruisce una tabella con k righe e k colonne, dove k è il
numero delle classi:
 Le righe indicano le classi originali
 Le colonne indicano le classi predette
 Ogni elemento della tabella aij rappresenta il numero di esempi appartenenti
alla classe Ci classificati dal modello nella classe Cj
Sistemi di supporto alle decisioni - Leonardo Rigutini
Confusion table
 Dalla confusion table è possibile individuare tre tipi di
valori:
 Veri positivi: elementi classificati correttamente. Corrisponde
agli elementi sulla diagonale della confusion table:
 Falsi positivi: elementi classificati nella classe j sbagliando
Sistemi di supporto alle decisioni - Leonardo Rigutini
Confusion table
 Falsi negativi: elementi che dovrebbero appartenere alla classe
j , ma che non vi sono stati assegnati dal classificatore
 Veri negativi: elementi che giustamente non sono stati
assegnati alla classe j
Sistemi di supporto alle decisioni - Leonardo Rigutini
Micro e Macro averaging
 I valori elencati precedentemente sono utilizzati per calcolare una
misura di qualità della classificazione
 Accuracy, Precision e Recall
 Tali valori possono essere calcolati in due modi:
 Macro-Average: la misura globale è ottenuta mediando i valori calcolati per
ogni classe
 Micro-Average: la misura delle prestazioni è ottenuta calcolando i valori di
TP,FP,TN e FN globali (somme per i rispettivi valori di ogni classe) e poi
applicando la formula di calcolo
Sistemi di supporto alle decisioni - Leonardo Rigutini
1. Accuracy
 Misura l’accuratezza del classificatore, ossia il numero di risultati
corretti rispetto al numero possibile di risultati corretti.
 NB: tra i risultati corretti sono inseriti anche i TN
Sistemi di supporto alle decisioni - Leonardo Rigutini
2. Precision e Recall
 Precision e Recall sono due misure di prestazioni che derivano
dalla teoria dell’Information Retrieval
 La Precision misura la percentuale di risposte giuste del sistema
rispetto al numero totale di risultati che il sistema stesso ha
ritornato:
 Quanto di quello che il classificatore ha inserito nella classe è corretto, la
precisione dei risultati, quanto fidarsi dei risultati ottenuti
 La recall, invece, indica la percentuale di esempi originariamente
nella classe che invece non sono stati classificati bene:
 Quanto il classificatore ha “lasciato” fuori dalla classificazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Precision e Recall
Sistemi di supporto alle decisioni - Leonardo Rigutini
F1 e Breakeven-point
 Nessuna delle due misure viste prima (Pr e Re) hanno un senso
senza l’altra.
 Diversi metodi per comporre i due valori in una misura unica di
prestazioni sono stati proposti
 F1, ossia la media armonica di essi:
 Breakeven-point: variare la soglia di classificazione/reject fino a trovare il
punto in cui Pr=Re. Aumentando la soglia di rejection, aumentiamo la Pr e
diminuiamo la Re (accettare poco ma classificato con molta precisione).
Viceversa se invece abbassiamo la soglia (accettiamo tutto, ma con bassa
precisione).
 NB: la F1 è massimizzata quando Pr=Re, ossia proprio al
breakeven-point
Sistemi di supporto alle decisioni - Leonardo Rigutini
Conclusioni
 E’ stata data una formalizzazione del problema di classificazione
automatica:
 Task supervisionato
 Sono stati illustrati i modelli più comunemente utilizzati nella
classificazione automatica di pattern vettoriali:





Regole
Probabilistici
Profile/Example-Based
ANN
SVM
 Inoltre sono state illustrate le misure utilizzate comunemente per
misurare le prestazioni di un classificatore
Sistemi di supporto alle decisioni - Leonardo Rigutini
Scarica

Classificazione - Dipartimento di Ingegneria dell`informazione e