Classificazione - Dipartimento di Ingegneria dell`informazione e
by user
Comments
Transcript
Classificazione - Dipartimento di Ingegneria dell`informazione e
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 HodgkinHuxley) 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 floatingpoint 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 Softcomputing 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” è 103 sec (alto rispetto a quello del calcolatore, 1010 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 WidrowHoff 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 softcomputing ? Il requisito dell’hardcomputing “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 softcomputing di Lofti Zadeh Softcomputing differs from conventional (hard) computing in that, unlike hardcomputing, it is tolerant of imprecision, uncertanty and partial truth. In effect, the role model for softcomputing is the human mind. The guidance principle of softcomputing 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 singleneuron con funzione di attivazione lineare Apprendimento con algoritmo LMS (Least Mean Square), noto anche come WidrowHoff 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: Deltarule 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 deltarule 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 deltarule 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 = (twTx)T (twTx) Si vuole aggiornare il vettore dei pesi w per ottenere una diminuzione dell’errore e ee = (t(w w)Tx)T (t(w w)Tx) = e(twTx)T(wTx)(wTx)T(twTx) O(wTw) Scegliendo w = (twTx)x e 2 (twTx)T (twTx) < 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=(xx0) f (x)=f (x0)+f ’(x0)(xx0)+½f ’’(x0)(xx0)2+… Sistemi di supporto alle decisioni - Leonardo Rigutini Perceptron 1 Perceptron Modello singleneuron 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 nesima 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 1im (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(uxi)0, per 1im, e avente u =1, si definisce il margine (u) = min1im yi(uxi) 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 1im 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 T1 passi dell’algoritmo, per un qualunque T>1. Sia M il numero di aggiornamenti eseguiti nei T1 passi e siano 1t1…<tMT 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… Deltarule 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)=(wx) neuroni a base radiale: y=f(a)=f(xw), 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= (zpa[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)UT, 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 iO (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 nm 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 passabasso, 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 (01) 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 trialanderror 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 crossvalidation per early stopping) Aggiungere rumore ai dati Soluzioni che controllano il valore assunto dai parametri Sistemi di supporto alle decisioni - Leonardo Rigutini Crossvalidation 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 crossvalidation è 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 (online 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) = ea 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 VapnikChervonenkis (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), xiN, 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 VCdimension La VCdimension 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 VCdimension è una misura della complessità dell’insieme H Sistemi di supporto alle decisioni - Leonardo Rigutini VCdimension 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 VCdimension 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 VCdimension 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 VCdimension (tradeoff Remp e h/l) L’algoritmo SVM risolve efficacemente questo problema minimizzando contemporaneamente la VCdimension 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 xiC1 wxi+b < 0 per xiC2 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 wxb=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)=wxb e (w,D)=mini yi(wxib) Altrimenti… si fissa w in modo tale che (w,D)=1/w, cioè si impone mini yi(wxib)=1 è una parametrizzazione datadependent 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 wA, 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 KuhnTucker, i*(yi(w*xb*)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 KuhnTucker) 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: wxib 1 i per yi= 1 wxib 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 <w1 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 : dH 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 semidefinita positiva è un kernel L’impiego di funzioni kernel di fatto “nasconde” il mapping nello spazio multidimensionale 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 semidefinita 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)=(a11(x),a22(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 x2 e K(xi,xj)=(xi xj)2 In questo caso, lo spazio H e il mapping : 2H 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 (trialanderror) Sistemi di supporto alle decisioni - Leonardo Rigutini Software online 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. 125, 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. 955974, 1998 C.J.C. Burges, A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery, 2(2):955974, 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