Sistemi di supporto alle decisioni 3. Classificazione Ing. Leonardo Rigutini, Ph.D. Dipartimento di...

Sistemi di supporto alle decisioniSistemi di supporto alle decisioni

3. Classificazione3. Classificazione

Ing. Leonardo Rigutini, Ph.D.Ing. Leonardo Rigutini, Ph.D.

Dipartimento di Ingegneria dell’InformazioneDipartimento di Ingegneria dell’Informazione

Università di SienaUniversità di Siena

[email protected]@dii.unisi.it

http://www.dii.unisi.it/http://www.dii.unisi.it/~rigutini/~rigutini/

mailto:[email protected]

Sistemi di supporto alle decisioni - Leonardo RigutiniSistemi di supporto alle decisioni - Leonardo Rigutini

ClassificazioneClassificazione

Processo supervisionato in cui un teacher addestra un modello ad Processo supervisionato in cui un teacher addestra un modello ad assegnare una etichetta ad un patternassegnare una etichetta ad un pattern

Dati:Dati:

Insieme predefinito di k classi - C = {CInsieme predefinito di k classi - C = {C1 1 , C, C2 2 ,…, C,…, Ckk}}

Learning set = {<xLearning set = {<xii ,C ,Cjj>} con i=1,…, e j=1,…,k>} con i=1,…, e j=1,…,k

Scopo:Scopo:

Dato un pattern mai visto u, assegnarlo ad una delle k classiDato un pattern mai visto u, assegnarlo ad una delle k classi



Due tipi di classificazione:Due tipi di classificazione: Mono-classe (binario), in cui ogni patterrn viene assegnato ad Mono-classe (binario), in cui ogni patterrn viene assegnato ad

una ed una sola classeuna ed una sola classe Multi-classe, in cui un pattern può essere inserito in più di una Multi-classe, in cui un pattern può essere inserito in più di una

classeclasse

Il secondo caso è più complicato del primo (ovviamente) Il secondo caso è più complicato del primo (ovviamente) ma molto più vicino alla realtàma molto più vicino alla realtà

Spesso il secondo caso si risolve con k classificatori Spesso il secondo caso si risolve con k classificatori binaribinari


ClassificatoriClassificatori

Diversi tipi di classificatori in base all’approccio Diversi tipi di classificatori in base all’approccio utilizzato nello sviluppo del modello:utilizzato nello sviluppo del modello: A regole (rule-based)A regole (rule-based) StatisticiStatistici Profile-basedProfile-based Example-basedExample-based NeuraliNeurali Support Vector Machines (SVM)Support Vector Machines (SVM)

Classificatori a regoleClassificatori a regole


Alberi di decisione - 1Alberi di decisione - 1

Esempio: {Outlook=Esempio: {Outlook=SunnySunny,Humidity=,Humidity=HighHigh,Wind=,Wind=StrongStrong}}

WindWind

RainRain

OutlookOutlook

HumidityHumidity OvercastOvercast

SunnySunny

YesYes

YesYes

WeakWeakStrongStrong

NoNoYesYes

NormalNormalHighHigh

NoNo

Decidere se è la giornata ideale per giocare a tennis...Decidere se è la giornata ideale per giocare a tennis...

AttributoAttributo Valore Valore dell’attributodell’attributo


Alberi di decisione - 2Alberi di decisione - 2

Costruzione dell’albero di decisioneCostruzione dell’albero di decisione

2 fasi:2 fasi:

Fase di build Fase di build si costruisce l’albero, partizionando si costruisce l’albero, partizionando ripetutamente il training set sul valore di un attributo, finché ripetutamente il training set sul valore di un attributo, finché tutti gli esempi, in ogni partizione, appartengono ad una sola tutti gli esempi, in ogni partizione, appartengono ad una sola classeclasse

Fase di pruning Fase di pruning si pota l’albero, eliminando rami dovuti a si pota l’albero, eliminando rami dovuti a rumore o a fluttuazioni statisticherumore o a fluttuazioni statistiche


Case Study: alberi di decisione - 3Case Study: alberi di decisione - 3In un albero di decisione:In un albero di decisione:

Ogni nodo interno effettua un test su un attributoOgni nodo interno effettua un test su un attributoOgni ramo uscente da un nodo corrisponde ad uno dei possibili Ogni ramo uscente da un nodo corrisponde ad uno dei possibili valori che l’attributo può assumerevalori che l’attributo può assumereOgni foglia assegna una classificazioneOgni foglia assegna una classificazione

PerPer classificare un’istanzaclassificare un’istanza occorre, a partire dalla radice...occorre, a partire dalla radice...1)1) ...selezionare l’attributo dell’istanza associato al nodo corrente...selezionare l’attributo dell’istanza associato al nodo corrente2)2) ...seguire il ramo associato al valore assegnato a tale attributo ...seguire il ramo associato al valore assegnato a tale attributo

nell’istanzanell’istanza3)3) ...quando si raggiunge una foglia, restituire l’etichetta associata ...quando si raggiunge una foglia, restituire l’etichetta associata

alla foglia, altrimenti, a partire dal nodo corrente, ripetere il alla foglia, altrimenti, a partire dal nodo corrente, ripetere il passo 2)passo 2)


Case Study: alberi di decisione - 4Case Study: alberi di decisione - 4

Esempio: {Outlook=Esempio: {Outlook=SunnySunny,Humidity=,Humidity=HighHigh,Wind=,Wind=StrongStrong}}

WindWind

RainRain

OutlookOutlook

HumidityHumidity OvercasOvercastt

SunnySunny

YesYes

YesYes

WeakWeakStrongStrong

NoNoYesYes

NormalNormalHighHigh

NoNo


Un altro esempio …Un altro esempio …

AltoAlto

Decidere la tariffa assicurativa da applicare, in base alla classe di Decidere la tariffa assicurativa da applicare, in base alla classe di rischiorischio

Età < 26Età < 26

Tipo autoTipo auto

BassoBassoAltoAlto

sìsì nono

sportivasportivafamiliarefamiliare

AltoAlto

utilitariautilitaria

ETÀETÀ

40406565202025255050

CLASSE RISCHIOCLASSE RISCHIO

bassobassoaltoaltoaltoaltoaltoalto

bassobasso

TIPO AUTOTIPO AUTO

familiarefamiliaresportivasportivautilitariautilitariasportivasportivafamiliarefamiliare

Classificatori Probabilistici:Classificatori Probabilistici:Naive BayesNaive Bayes


Naive BayesNaive Bayes Un classificator Bayesiano, stima la probabilità marginale della Un classificator Bayesiano, stima la probabilità marginale della

classe dato l’esempio: classe dato l’esempio:

Questa quantità non può essere stimata direttamente ma Questa quantità non può essere stimata direttamente ma utilizzando la formula di Bayes possiamo scrivere:utilizzando la formula di Bayes possiamo scrivere:

Per stimare la quantità viene fatta una forte assunzione di Per stimare la quantità viene fatta una forte assunzione di indipendenza delle features (naive) e cioè che:indipendenza delle features (naive) e cioè che:


Naive BayesNaive Bayes E la stima delle singole probabilità è fatta semplicemente contando E la stima delle singole probabilità è fatta semplicemente contando

la frequenza relativa di una feature all’interno della classe:la frequenza relativa di una feature all’interno della classe:

Le rimanenti due probabilità possono essere considerate costanti (e Le rimanenti due probabilità possono essere considerate costanti (e quindi ignorate) oppure stimate a loro volta dai datiquindi ignorate) oppure stimate a loro volta dai dati


Naive BayesNaive Bayes Nel primo caso, la supposizione è la seguente: Nel primo caso, la supposizione è la seguente:

la probabilità a priori di ogni classe è la stessa per tutte le classi (classi equi-la probabilità a priori di ogni classe è la stessa per tutte le classi (classi equi-probabili)probabili)

La probabilità di un esempio è la stessa di tutti gli esempi (esempi equi-La probabilità di un esempio è la stessa di tutti gli esempi (esempi equi-probabili)probabili)

Nel secondo caso, invece si può sfruttare i dati per la stima dei due Nel secondo caso, invece si può sfruttare i dati per la stima dei due valori:valori: La probabilità della classe P(CLa probabilità della classe P(Ckk) può essere stimata contanto la percentuale ) può essere stimata contanto la percentuale

di documenti appartenencti alla classe rispetto al numero totale di documenti di documenti appartenencti alla classe rispetto al numero totale di documenti nel training setnel training set

La probabilità a priori del dato può essere stimata utilizzando l’ipotesi naive La probabilità a priori del dato può essere stimata utilizzando l’ipotesi naive fatta prima:fatta prima:


SmoothingSmoothing Problema: cosa accade se = 0? Questo vuol dire che tale Problema: cosa accade se = 0? Questo vuol dire che tale

feature non viene mai incontrata nella classe k durante feature non viene mai incontrata nella classe k durante l’apprendimento.l’apprendimento.

Tale caso implica Tale caso implica

Per evitare questo problema vengono utilizzate tecniche di Per evitare questo problema vengono utilizzate tecniche di smoothing che restituiscono valori molto piccoli ma non nulli per smoothing che restituiscono valori molto piccoli ma non nulli per le features mai osservate in apprendimentole features mai osservate in apprendimento


a) Additive smoothinga) Additive smoothing La formula di stima viene modificata in :La formula di stima viene modificata in :

con i vincoli checon i vincoli che

Ottenendo così:Ottenendo così:


b) Laplace smoothingb) Laplace smoothing Laplace smoothing pone a=1 nella formula precedente, ottenendo Laplace smoothing pone a=1 nella formula precedente, ottenendo

così:così:

La formula di ristima delle probabilità diventa:La formula di ristima delle probabilità diventa:


c) Good-Turingc) Good-Turing La tecnica di smoothing Good-Turing (dal nome dei due ricercatori La tecnica di smoothing Good-Turing (dal nome dei due ricercatori

che l’hanno proposta) stima la probabilità di una feature mai vistache l’hanno proposta) stima la probabilità di una feature mai vista

Essi trovarono che:Essi trovarono che:

con pcon p00 la probabilità di una feature mai vista, N la probabilità di una feature mai vista, N11 il numero di il numero di features osservate solamente una volta nel training set ed N il features osservate solamente una volta nel training set ed N il numero totale di featuresnumero totale di features

L’idea è che le features viste una volta sono casi fortunati di L’idea è che le features viste una volta sono casi fortunati di features mai vistefeatures mai viste

Classificatori probabilistici:Classificatori probabilistici:Complement Naive BayesComplement Naive Bayes


Complement Naive BayesComplement Naive Bayes Questo metodo utilizza l’approccio Bayesiano visto per il modello Questo metodo utilizza l’approccio Bayesiano visto per il modello

precedente per stimare le probabilità complementari:precedente per stimare le probabilità complementari:

Questo metodo ha lo stesso problema delle features mai viste e Questo metodo ha lo stesso problema delle features mai viste e quindi richiede l’utilizzo di tecniche di smoothingquindi richiede l’utilizzo di tecniche di smoothing

Inoltre ha il vantaggio rispetto a NB di avere a disposizione un Inoltre ha il vantaggio rispetto a NB di avere a disposizione un maggior numero di esempi per ogni classe (o meglio complemento maggior numero di esempi per ogni classe (o meglio complemento di classe)di classe)


Complement Naive BayesComplement Naive Bayes Per ogni complemento di classe infatti le statistiche vengono Per ogni complemento di classe infatti le statistiche vengono

stimate utilizzando tutti i documenti delle classi rimanenti, e cioè stimate utilizzando tutti i documenti delle classi rimanenti, e cioè che è sicuramente maggiore di che è sicuramente maggiore di

dove è l’intero training set e indica la parte del training dove è l’intero training set e indica la parte del training set contenente esempi della classe k. L’operatore su insiemi |A| set contenente esempi della classe k. L’operatore su insiemi |A| infine indica la cardinalità dell’insieme A.infine indica la cardinalità dell’insieme A.

Per questo motivo, tale modello è spesso utilizzato nei casi di Per questo motivo, tale modello è spesso utilizzato nei casi di scarsità di esempi di addestramentoscarsità di esempi di addestramento

Classificatori Profile-basedClassificatori Profile-based


Profile Based ClassifiersProfile Based Classifiers Questa famiglia di classificatori lavora memorizzando una Questa famiglia di classificatori lavora memorizzando una

rappresentazione esplicita delle categorie.rappresentazione esplicita delle categorie.

Durante il processo di classificazione, il modello computa la Durante il processo di classificazione, il modello computa la similarità dei nuovi patterns con i profili delle classi assegnandoli similarità dei nuovi patterns con i profili delle classi assegnandoli alla classe con score di similarità maggiore.alla classe con score di similarità maggiore.

Ad ogni feature vector sono assegnati dei pesi:Ad ogni feature vector sono assegnati dei pesi: I pesi possono essere valori reali propri del pattern oppure assegnati da I pesi possono essere valori reali propri del pattern oppure assegnati da

funzioni di pesatura (ad es. Tf-idf)funzioni di pesatura (ad es. Tf-idf)


Funzioni di similaritàFunzioni di similarità Una volta creati i profili per le classi, questi modelli utilizzando Una volta creati i profili per le classi, questi modelli utilizzando

una funzione per misurare la similarità dei pattern con i profili una funzione per misurare la similarità dei pattern con i profili della classedella classe

Esempi di funzioni di similaritàEsempi di funzioni di similarità

Manhattan distance (o City-block)Manhattan distance (o City-block)

Distanza Euclidea Distanza Euclidea

Distanza di MinkowskiDistanza di Minkowski


Funzioni di similarità (2)Funzioni di similarità (2)

Distanza del cosenoDistanza del coseno

Da notare che alcune funzioni ritornano valori alti per pattern Da notare che alcune funzioni ritornano valori alti per pattern molto simili e bassi per pattern dissimili (es. coseno), altre molto simili e bassi per pattern dissimili (es. coseno), altre viceversa si comportano in modo opposto (es. Euclidea)viceversa si comportano in modo opposto (es. Euclidea)


1) Algoritmo di Rocchio1) Algoritmo di Rocchio Questo classificatore profile-based calcola il profilo della classe Questo classificatore profile-based calcola il profilo della classe

secondo la seguente formula:secondo la seguente formula:

dove e . Inoltre, indica l’insieme dove e . Inoltre, indica l’insieme degli esempi positivi per la classe mentre indica l’insieme degli esempi positivi per la classe mentre indica l’insieme degli esempi negativi. degli esempi negativi.

I parametri beta e gamma pesano rispettivamente gli esempi I parametri beta e gamma pesano rispettivamente gli esempi positivi e negativi nella costruzione del profilopositivi e negativi nella costruzione del profilo


1) Algoritmo di Rocchio1) Algoritmo di Rocchio In realtà questo modello stima il profilo medio tra il profilo In realtà questo modello stima il profilo medio tra il profilo

generato dagli esempi postivi e quello generato dagli esempi generato dagli esempi postivi e quello generato dagli esempi negativi:negativi:

E’ un classificatore lineare.E’ un classificatore lineare.


2) Centroids-based2) Centroids-based Questo classificatore è un caso particolare del modello di Rocchio.Questo classificatore è un caso particolare del modello di Rocchio.

Ponendo Beta=0 e quindi Gamma=1 si ottiene:Ponendo Beta=0 e quindi Gamma=1 si ottiene:

Il profilo (vettore n-dimensionale) cIl profilo (vettore n-dimensionale) c jj viene detto centroide e può viene detto centroide e può

essere immaginato come un esempio “dummy” (virtuale) che sta essere immaginato come un esempio “dummy” (virtuale) che sta nel centro della classe:nel centro della classe: Generato dalla media degli esempi positivi per la classeGenerato dalla media degli esempi positivi per la classe

Classificatori Examples-basedClassificatori Examples-based


Examples-based classifier: kNNExamples-based classifier: kNN Questo modello è molto simile ai modelli basati su profilo Questo modello è molto simile ai modelli basati su profilo

(Rocchio) ed utilizza come essi una funzione di similarità.(Rocchio) ed utilizza come essi una funzione di similarità.

Questo modello però non costruisce un profilo per la classe, ma Questo modello però non costruisce un profilo per la classe, ma mantiene in memoria tutti i pattern assegnati alla classe e li usa mantiene in memoria tutti i pattern assegnati alla classe e li usa ogni qualvolta deve classificare un nuovo esempioogni qualvolta deve classificare un nuovo esempio

In tale situazione le distanze (similarità) tra tutti gli esempi In tale situazione le distanze (similarità) tra tutti gli esempi memorizzati ed il nuovo esempio sono calcolate e poi due strategie memorizzati ed il nuovo esempio sono calcolate e poi due strategie sono possibili:sono possibili: Assegnare il nuovo pattern alla classe più presente nei k pattern più viciniAssegnare 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ù Assegnare il nuovo pattern alla classe che contiene i primi k pattern più

similisimili


Examples-based classifier: kNNExamples-based classifier: kNN Questo metodo è molto costosoQuesto metodo è molto costoso

È necessario ogni volta calcolare N valori di similarità con N il È necessario ogni volta calcolare N valori di similarità con N il numero di esempi utilizzati per l’addestramentonumero di esempi utilizzati per l’addestramento Elevato costo computazionaleElevato costo computazionale Elevato costo di memorizzazione datiElevato costo di memorizzazione dati

Le reti neurali artificialiLe reti neurali artificiali


Nonostante gli straordinari successi nell’elaborazione Nonostante gli straordinari successi nell’elaborazione automatica dell’informazione, che stanno esercitando un automatica dell’informazione, che stanno esercitando un impatto di portata storica nella vita quotidiana, competenze impatto di portata storica nella vita quotidiana, competenze percettive, quali…percettive, quali…

……localizzare un oggetto in una scena localizzare un oggetto in una scena

……riconoscere la voce in condizioni realiriconoscere la voce in condizioni reali

……prendere decisioni basate sul “senso comune” prendere decisioni basate sul “senso comune”

sono compiti estremamente difficili per i calcolatori sono compiti estremamente difficili per i calcolatori elettronicielettronici

Introduzione Introduzione 1 1


Infatti, gli odierni sistemi di elaborazione hanno Infatti, gli odierni sistemi di elaborazione hanno automatizzato perfettamente processi ritenuti, fino a poche automatizzato perfettamente processi ritenuti, fino a poche decine di anni fa, di pertinenza umana, quali… decine di anni fa, di pertinenza umana, quali…

……svolgere calcoli molto complicati svolgere calcoli molto complicati

……recuperare informazione in un archiviorecuperare informazione in un archivio

Con l’Intelligenza Artificiale si sono spinti verso Con l’Intelligenza Artificiale si sono spinti verso l’automazione del ragionamento simbolico, fino ai sistemi l’automazione del ragionamento simbolico, fino ai sistemi esperti, in grado di modellare e rendere fruibile la conoscenza esperti, in grado di modellare e rendere fruibile la conoscenza di esperti in settori specificidi esperti in settori specifici



Tuttavia, i calcolatori mostrano un comportamento primitivo nella Tuttavia, i calcolatori mostrano un comportamento primitivo nella simulazione della maggior parte dei processi percettivisimulazione della maggior parte dei processi percettivi

Le capacità percettive, infatti, sviluppate durante un processo evolutivo di Le capacità percettive, infatti, sviluppate durante un processo evolutivo di centinaia di migliaia di anni, risultano difficili da replicare usando i centinaia di migliaia di anni, risultano difficili da replicare usando i modelli di calcolo simbolico, tipici degli elaboratori attualimodelli di calcolo simbolico, tipici degli elaboratori attuali



La metafora neurobiologica La metafora neurobiologica 1 1

Attualmente, a differenza delle macchine, l’uomo è un ottimo esempio di “sistema” in grado di elaborare informazione sottosimbolicaTali elaborazioni, come ogni altro processo cognitivo, hanno sede nel cervello, una complessa struttura neurobiologica, oggi accuratamente “decifrata”

Il “mattone elementare” dei tessuti cerebrali è il neuroneneurone, che è sede dei processi elettrochimici che determinano l’atto percettivo



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 sinapsisinapsi, 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



È 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



È 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


La metafora neurobiologica La metafora neurobiologica 5 5Poiché 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 sottosimbolicaMind no longer goes more ghostly than a ghostMind 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 complesseTuttavia, non è necessaria una perfetta emulazione dei processi neurobiologici per l’emergenza di capacità cognitive


La metafora neurobiologica La metafora neurobiologica 6 6Molti 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


What’s new ?What’s new ?

Mon June 6, 2005 12:51 PM GMTMon June 6, 2005 12:51 PM GMTLONDRA (Reuters) IBM si è accordata con un team di scienziati svizzeri per creare il primo modello al mondo di cervello computerizzato, Blue GeneBlue Gene: i ricercatori sperano così di fornire nuove prospettive nella conoscenza del più complesso organo umanoL’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/LBlue 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 teraflopsCinque anni fa, nessun supercomputer al mondo aveva una capacità maggiore di un teraflop

SoftSoftcomputing e reti neuralicomputing e reti neurali


Molti modelli connessionistici utilizzati nelle applicazioni sono solo ispirati dal paradigma biologico a livello di unità neuronale…

I I just want to point out that the componentry used in the memory just want to point out that the componentry used in the memory may be entirely different from the one that underlines the basic may be entirely different from the one that underlines the basic active organsactive organs (John Von Neumann, 1958) (John Von Neumann, 1958)

Emulazione o ispirazione ?Emulazione o ispirazione ?


Le reti neurali Le reti neurali 1 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


Le reti neurali Le reti neurali 2 2

Le reti neurali artificiali sono esse stesse costituite da insiemi di unità semplici, i neuronineuroni, 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à)


Le reti neurali Le reti neurali 3 3Il cervello umanocervello 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 paralleloUtilizzo massivo di calcolo parallelo Le reti neurali artificialireti 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


Un po’ di storia Un po’ di storia 1 1

La prima era: i modelli di neuroneLa prima era: i modelli di neurone1956: Dartmouth Summer Research Project on AI (Minsky, McCarty, Rochester, Shannon,…)1959: ADALINE di WidrowHoff con applicazione al riconoscimento vocale1962: Perceptron di Rosenblatt1969: “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)


Un po’ di storia Un po’ di storia 2 2

La seconda era: le reti di neuroniLa seconda era: le reti di neuroni1982: Reti di Hopfield1986: Parallel Distributed Processing e Backpropagation1987: Prima conferenza sulle reti neurali dell’IEEE a San Diego1989: Primi chip neurali 1990: J. Pollack e le reti neurali che elaborano dati strutturati1994: Prima conferenza mondiale su Intelligenza Artificiale1994: Nasce il progetto NeuroCOLT (Computational Learning Theory

)2001: L’IEEE approva la creazione della Neural Networks SocietyNeural Networks Society


Cos’è il softCos’è il softcomputing ?computing ?

Il requisito dell’hardcomputing “trova sempresempre la soluzione esattaesatta” diviene “trova spessospesso una soluzione approssimataapprossimata”L’elaborazione coinvolge informazione sottosimbolica: può non esistere una soluzione algoritmica soddisfacenteDefinizione di softsoftcomputingcomputing di Lofti Zadeh

SoftSoftcomputing differs from conventional (hard) computing computing differs from conventional (hard) computing in that, unlike hardin that, unlike hardcomputing, it is tolerant of imprecision, computing, it is tolerant of imprecision, uncertanty and partial truth. In effect, the role model for uncertanty and partial truth. In effect, the role model for softsoftcomputing is the human mind. The guidance principle of computing is the human mind. The guidance principle of softsoftcomputing is: exploit tolerance for imprecision, uncertanty and computing is: exploit tolerance for imprecision, uncertanty and partial truth to achieve tractability, robustness and low solution partial truth to achieve tractability, robustness and low solution cost.cost.

Le reti neurali singolo strato Le reti neurali singolo strato


ADALINE ADALINE 1 1

ADALINEADALINE (ADAptive LInear NEuron)Modello singlesingleneuronneuron con funzione di attivazione lineare Apprendimento con algoritmo LMSLMS (Least Mean Square), noto anche come WidrowWidrowHoff AlgorithmHoff AlgorithmRisolve problemi di regressione, ovvero di approssimazione della funzione che definisce la relazione tra input e output

calcolando (x,w)

f f : : nn


ADALINE ADALINE 2 2Learning rule: DeltaDeltarulerule

Adattamento dei pesi in base all’errore che la rete commette rispetto alla risposta desiderata

ww22xx22

ww00

wwppxxpp

xx11

yy

tt

::

ww11


ADALINE ADALINE 3 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


ADALINE ADALINE 4 4

Algoritmo Least Mean SquareLeast Mean Square (LMS): basato sulla stima istantanea delle funzioni di correlazione


Algoritmo LMS Algoritmo LMS 1 1

Procedura di training: dato il training settraining set L ={(x(m),t(m)) | m=1,2,…,M}

I pesi vengono inizializzati con valori casualiPer ogni esempio del training set:

Si presenta l’input x alla rete e si calcola la risposta ySi 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


Siae = (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




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



Condizione di convergenza asintoticaLa 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 < : costante positiva, 0 < < < maxmax, , maxmax=2/=2/maxmax

maxmax massimo autovalore della matrice di correlazione massimo autovalore della matrice di correlazione

degli ingressidegli ingressi


Interpretazione probabilistica Interpretazione probabilistica 1 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

yy==ww00++ww11xx11++ww22xx22+…++…+wwppxxpp

yy

xx


Interpretazione probabilistica Interpretazione probabilistica 2 2La 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

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)

yy==ww00++ww11zz++ww22zz22

ww22

zz22

ww00

11

yy

ww11zz

zz

yy

f f ((xx)=)=f f ((xx00)+)+f f ’(’(xx00)()(xxxx00)+)+½½f f ’’(’’(xx00)()(xxxx00))22++……


PerceptronPerceptronModello singlesingleneuronneuron con funzione di attivazione a soglia

Perceptron Perceptron 1 1


Risolve problemi di classificazione a due classi, C1 e C2, modellando la trasformazione

attraverso la funzione (x,w)


f f : : nn {{1,1}1,1}


Learning rule: Perceptron error correction rulePerceptron error correction rule Adattamento dei pesi in base all’errore che la rete commette rispetto

alla risposta desiderata, detta targettarget



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)




Procedura di training: dato il training settraining set linearmente separabile

L ={(x(m),t(m)) | m=1,2,…,M}Inizializzazione casuale dei pesiPresentazione 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 ruleperceptron error correction ruleRipetizione del passo 2) fino a quando la rete risponde

correttamente a tutti gli esempi di training


Teorema di convergenza Teorema di convergenza 1 1Supponiamo 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

NotaNotaÈ equivalente all’algoritmo

classico, con =1/2, produce cioè un rinforzo delle connessioni favorevoli al target ed un indebolimento di quelle sfavorevoli


Teorema di convergenza Teorema di convergenza 2 2Per 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


Teorema di convergenza Teorema di convergenza (Rosenblatt, (Rosenblatt, Principles of Neurodynamics, Principles of Neurodynamics, 1962)1962)

Dato un qualunque training set linearmente separabile con Dato un qualunque training set linearmente separabile con margine margine ((uu) rispetto ad un qualunque iperpiano separatore ) rispetto ad un qualunque iperpiano separatore uu, , l’error correction rule determina un iperpiano separatore l’error correction rule determina un iperpiano separatore w w

(generalmente diverso da (generalmente diverso da uu) dopo al più ) dopo al più M passi, conM passi, con

Teorema di convergenza Teorema di convergenza 3 3

€

M ≤max1≤ i≤m x i

γ(u)

⎛

⎝ ⎜

⎞

⎠ ⎟

2


DimostrazioneDimostrazioneSia 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, wT=w y x . Quindi…

ttMMttMM ttMM


yy ( (ww xx )<0, )<0, perché a tperché a tMM è avvenuto un aggiornamento. è avvenuto un aggiornamento.ttMMttMM ttMM


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:

Iterando per M volte si ottiene



Considerando entrambe le disuguaglianze, infine, si ha

Iterando per M volte si ottiene

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.



Comportamento del perceptron: cambiamento della pendenza della posizione del contorno di decisione

Ancora sul perceptron...Ancora sul perceptron...


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

Algoritmo Pocket Algoritmo Pocket 1 1


L’algoritmo PocketPocket è una variante dell’algoritmo di apprendimento del perceptron, proposta da Gallant (1990)

Durante l’apprendimento, i pesi “migliori” vengono conservati in una “tasca” pocketpocket e aggiornati solo quando viene calcolato un nuovo vettore dei pesi che classifica correttamente un maggior numero di pattern



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 correttamentePer ciascun insieme di pesi nuovo, viene mantenuto un contatore per la lunghezza della sequenza di pattern fino al primo fallimentoSe il nuovo insieme dei pesi classifica correttamente una sequenza di lunghezza maggiore, viene spostato nel “pocket”



Reti neurali a strato singoloReti neurali a strato singolo

Riassumendo…DeltaDeltarulerule

Risolve problemi lineari (nei parametri o pesi)Converge asintoticamente alla soluzione

Perceptron error correction rulePerceptron error correction ruleRisolve problemi linearmente separabiliConverge alla soluzione in un numero finito di passi, se

esiste la soluzioneAltrimenti, per pattern non linearmente separabili, si

può usare l’algoritmo Pocket

Le reti neurali multistrato Le reti neurali multistrato


Parallel distributed processingParallel distributed processing

Le reti neurali artificiali sono sistemi di calcolo distribuiti e massicciamente Le reti neurali artificiali sono sistemi di calcolo distribuiti e massicciamente paralleli, formati da un elevato numero di processori:paralleli, formati da un elevato numero di processori:

molto semplicimolto semplicistrutturalmente identicistrutturalmente identicifittamente interconnessifittamente interconnessidotati ciascuno di una propria memoria localedotati ciascuno di una propria memoria localeeventualmente provvisti di connessioni con l’esternoeventualmente provvisti di connessioni con l’esterno

Nella terminologia delle reti neurali i processori vengono detti neuroniNella terminologia delle reti neurali i processori vengono detti neuroni


Il flusso dell’informazioneIl flusso dell’informazione

Ciascun neurone elabora l’informazione contenuta:Ciascun neurone elabora l’informazione contenuta:nella propria memoria locale nella propria memoria locale negli stimoli provenienti dall’esterno e/o dagli altri neuroni della negli stimoli provenienti dall’esterno e/o dagli altri neuroni della rete, raccolti tramite le connessioni di ingressorete, raccolti tramite le connessioni di ingresso

L’elaborazione dà luogo a:L’elaborazione dà luogo a:uno stato interno, detto attivazioneuno stato interno, detto attivazioneun segnale di risposta, funzione dell’attivazione, il quale viene un segnale di risposta, funzione dell’attivazione, il quale viene propagato attraverso le connessioni di uscita per stimolare altri propagato attraverso le connessioni di uscita per stimolare altri neuroni e/o essere accessibile all’esternoneuroni e/o essere accessibile all’esterno


La natura distribuita delle reti neuraliLa natura distribuita delle reti neurali

I neuroni non hanno alcuna cognizione, né controllo, sulla I neuroni non hanno alcuna cognizione, né controllo, sulla provenienza degli stimoli, e quindi “ignorano” la struttura provenienza degli stimoli, e quindi “ignorano” la struttura della rete di cui fanno parte della rete di cui fanno parte

Effettuano un’elaborazione di tipo localeEffettuano un’elaborazione di tipo locale

La mutua influenza fra l’operato dei singoli neuroni e il La mutua influenza fra l’operato dei singoli neuroni e il comportamento globale della rete risiede nella disposizione comportamento globale della rete risiede nella disposizione delle connessionidelle connessioni

In breve:In breve:i neuroni trasformano gli stimoli in rispostei neuroni trasformano gli stimoli in rispostele connessioni distribuiscono le risposte in forma di le connessioni distribuiscono le risposte in forma di stimolistimoli


La memoria localeLa memoria locale

Il contenuto della memoria locale di ciascun neurone Il contenuto della memoria locale di ciascun neurone determina la modalità di risposta agli stimoli, e dunque determina la modalità di risposta agli stimoli, e dunque introduce una differenziazione funzionale fra elementi di introduce una differenziazione funzionale fra elementi di calcolo strutturalmente identicicalcolo strutturalmente identici

La memoria locale è costituita dai cosiddetti pesi sinaptici, La memoria locale è costituita dai cosiddetti pesi sinaptici, che modulano il contributo degli stimoli all’attivazione del che modulano il contributo degli stimoli all’attivazione del neuroneneurone

La maggior parte delle reti neurali sono provviste di La maggior parte delle reti neurali sono provviste di meccanismi in grado di alterare il contenuto delle meccanismi in grado di alterare il contenuto delle memorie, al fine di modificare il comportamento globale memorie, al fine di modificare il comportamento globale della retedella rete


Reti neurali: capacità computazionaleReti neurali: capacità computazionale

L’idea sottesa è quella di “ricostruire una funzione” tramite la L’idea sottesa è quella di “ricostruire una funzione” tramite la composizione di unità elementari, ciascuna delle quali è in grado di composizione di unità elementari, ciascuna delle quali è in grado di eseguire un numero limitato di semplici computazionieseguire un numero limitato di semplici computazioni

Le reti neurali non eseguono istruzioni programmate ma rispondono Le reti neurali non eseguono istruzioni programmate ma rispondono agli input tramite un procedimento paralleloagli input tramite un procedimento parallelo

Non sono sequenziali Non sono sequenziali

Forniscono risposte anche in corrispondenza di input mai visti (capacità Forniscono risposte anche in corrispondenza di input mai visti (capacità di generalizzazione)di generalizzazione)

Sono approssimatori universali di funzioniSono approssimatori universali di funzioni

Sono “black box”: incapacità di spiegare i risultatiSono “black box”: incapacità di spiegare i risultati

Reti feedforward e multistrato Reti feedforward e multistrato 1 1Le unità di calcolo sono basate su computazione nel continuo (a, attivazione del neurone)

neuroni sigmoidali: neuroni sigmoidali: yy==((aa)=)=((wwxx))

neuroni a base radiale: neuroni a base radiale: yy==ff((aa)=)=ff((xxww), con ), con nn+1,+1,nn+1+1, , definita positivadefinita positiva


Dal punto di vista architetturale sono rappresentate da grafi aciclici

Esiste un ordinamento parziale fra i vertici (neuroni) del grafoCiascun neurone può essere connesso sia ad altri neuroni che agli ingressi

Reti feedforward e multistrato Reti feedforward e multistrato 2 2


Propagazione in avantiPropagazione in avantiSia S un generico ordinamento topologico dei verticiPer 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 pipepipe sui livelli

Reti feedforward e multistrato Reti feedforward e multistrato 3 3


Reti multistratoReti multistrato

Le unità di elaborazione sono di tre tipiInputInput (ricevono input dall’esterno)HiddenHidden (ricevono input dalle unità di ingresso o da altre unità hidden del sistema)

OutputOutput (trasmettono segnali all’esterno del sistema) L’attività delle unità hidden non è visibile all’esternoTutta l’elaborazione della rete neurale è eseguita da semplici unità che si scambiano messaggi ed informazioni attraverso le connessioni

segnalesegnale


MultiLayer Perceptron (MLP)MultiLayer Perceptron (MLP)

+1+1

oo22xx22

+1+1

xx11oo11

11

22

33

44

44

11 22

33

Le unità di uscita Le unità di uscita combinano i contributi combinano i contributi delle diverse regionidelle diverse regioni

I neuroni nascosti I neuroni nascosti ripartiscono lo spazio in ripartiscono lo spazio in regioniregioni


L’apprendimento L’apprendimento 1 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’apprendimentoL’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 pesiL’apprendimento dipende significativamente dalla topologia della rete e dalle funzioni di attivazione dei neuroni


L’apprendimento è caratterizzato dal… Grado di supervisioneGrado 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 supervisionatoApprendimento supervisionato Apprendimento non supervisionatoApprendimento non supervisionato

DeterminismoDeterminismo gli algoritmi di apprendimento sono raggruppati, in base alla natura delle regole che utilizzano, in deterministici o stocastici



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



Apprendimento supervisionatoApprendimento supervisionatoSi basa sul caricamento dei pesicaricamento dei pesi di una rete neurale sulla base di un insieme di apprendimento dotato di targetDifferenza fondamentale rispetto alla soluzione algoritmica di problemi: il caricamento dei pesi deve garantire la generalizzazionegeneralizzazione a nuovi esempi



L’apprendimento si basa sulla terna {L’apprendimento si basa sulla terna {LL, , N,N, E E}, con}, con

L L ={(={(uuii,d,dii))UUTT, , ii=1,…,P}, insieme di training =1,…,P}, insieme di training

NN rete feedforward multistrato rete feedforward multistrato

EE “grado di matching” tra dati e risposta della rete “grado di matching” tra dati e risposta della rete

dove dove ee((uu) è una qualunque metrica che esprime la distanza tra ) è una qualunque metrica che esprime la distanza tra dd((uu) ) e e xx((ww,,uu); per esempio:); per esempio:

Apprendimento in reti feedforwardApprendimento in reti feedforward


L’ottimizzazione (minimizzazione) della funzione errore coinvolge L’ottimizzazione (minimizzazione) della funzione errore coinvolge tipicamente molti parametri tipicamente molti parametri

La discesa sul gradiente risulta la soluzione più verosimile per motivi di La discesa sul gradiente risulta la soluzione più verosimile per motivi di efficienza computazionaleefficienza computazionale

La traiettoria è attratta dai punti di minimo locale di La traiettoria è attratta dai punti di minimo locale di EE((ww))

Il gradiente viene calcolato mediante l’algoritmo di Il gradiente viene calcolato mediante l’algoritmo di BackpropagationBackpropagation

La discesa sul gradienteLa discesa sul gradiente


BackpropagationBackpropagation 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

Backpropagation Backpropagation 1 1


L’errore si propaga in direzione contraria rispetto al segnale, cioè dalle uscite verso gli strati hiddenIn particolare…

Se iO (uscite), alloraAltrimenti

Backpropagation Backpropagation 2 2

segnalsegnalee

erroreerrore


Una rete a due livelli con sigmoidi (o simili) su tutte le unità, può rappresentare Una rete a due livelli con sigmoidi (o simili) su tutte le unità, può rappresentare qualunque funzione booleana qualunque funzione booleana

Ogni funzione reale Ogni funzione reale nnmm limitata e continua, può essere approssimata con limitata e continua, può essere approssimata con errore arbitrariamente piccolo da una rete a due livelli con sigmoidi sulle unità errore arbitrariamente piccolo da una rete a due livelli con sigmoidi sulle unità nascoste e unità lineari sull’uscitanascoste e unità lineari sull’uscita

L’apprendimento ottimo viene conseguito con un numero di neuroni nascosti pari, L’apprendimento ottimo viene conseguito con un numero di neuroni nascosti pari, al più, alla cardinalità dell’ambiente di apprendimentoal più, alla cardinalità dell’ambiente di apprendimento

Quale potenza computazionale ? Quale potenza computazionale ? 1 1


Quale potenza computazionale ? Quale potenza computazionale ? 2 2


Ancora sull’apprendimento Ancora sull’apprendimento 1 1

Analogamente a quanto accade nei sistemi biologici, l’addestramento Analogamente a quanto accade nei sistemi biologici, l’addestramento delle reti neurali artificiali si fonda su due presupposti essenziali:delle reti neurali artificiali si fonda su due presupposti essenziali:

La disponibilità La disponibilità a priori a priori di un congruo repertorio di “comportamenti” di un congruo repertorio di “comportamenti” possibilipossibili

L’esistenza di un meccanismo atto a selezionare da tale repertorio, L’esistenza di un meccanismo atto a selezionare da tale repertorio, verosimilmente per tentativi ed errori, i “comportamenti” più verosimilmente per tentativi ed errori, i “comportamenti” più rispondenti alle sollecitazioni provenienti dall’ambiente (stimoli ed rispondenti alle sollecitazioni provenienti dall’ambiente (stimoli ed obiettivi)obiettivi)



La rete neurale viene addestrata su un learning setLa rete neurale viene addestrata su un learning set

Ogni esempio viene passato alla rete, calcolandone l’errore, che Ogni esempio viene passato alla rete, calcolandone l’errore, che verrà accumulato e successivamente usato per modificare i pesiverrà accumulato e successivamente usato per modificare i pesi

Il learning set viene presentato alla rete un certo numero di volte; la Il learning set viene presentato alla rete un certo numero di volte; la presentazione dell’intero insieme costituisce un’presentazione dell’intero insieme costituisce un’epoca di epoca di apprendimentoapprendimento

L’errore medio diminuisce progressivamenteL’errore medio diminuisce progressivamente

Troppe epoche possono causare Troppe epoche possono causare overfittingoverfitting (eccessiva specializzazione (eccessiva specializzazione sulle istanze contenute nel learning set)sulle istanze contenute nel learning set)


Tali punti possono pertanto essere calcolati con le tecniche di ricerca del minimo di una funzione, che si basano sullo studio della sua derivata

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)

Ad ogni iterazione i pesi vengono modificati di Ad ogni iterazione i pesi vengono modificati di una percentualeuna percentuale (learning rate); (learning rate); piccolo piccolo comporta un apprendimento più lento ma spesso comporta un apprendimento più lento ma spesso più accuratopiù accurato



Il fatto di muoversi nella direzione indicata dal gradiente non significa Il fatto di muoversi nella direzione indicata dal gradiente non significa necessariamente raggiungere il minimo della funzione!necessariamente raggiungere il minimo della funzione!

Se il learning rate è troppo grande si può saltare lontano dal minimo Se il learning rate è troppo grande si può saltare lontano dal minimo (eventualmente fuori dal suo bacino di attrazione)(eventualmente fuori dal suo bacino di attrazione)

Oltre al minimo globale, la superficie di errore, per problemi Oltre al minimo globale, la superficie di errore, per problemi significativi, è solitamente costellata da minimi locali, che sono significativi, è solitamente costellata da minimi locali, che sono attrattori per la dinamica di discesa del gradienteattrattori per la dinamica di discesa del gradiente




Problemi legati al dominioProblemi legati al dominioMaggiore la cardinalità dello spazio degli ingressi maggiore la Maggiore la cardinalità dello spazio degli ingressi maggiore la possibilità di lineare separabilità dei dati, ma anche la difficoltà nel possibilità di lineare separabilità dei dati, ma anche la difficoltà nel discernere le feature significativediscernere le feature significative

Esempio: Esempio: xx11 può variare fra 0.05 e 0.02, mentre può variare fra 0.05 e 0.02, mentre xx22 può variare fra può variare fra

100 e 10000; numericamente 100 e 10000; numericamente xx22 pesa più di pesa più di xx11, ma , ma xx11 potrebbe potrebbe

essere più rilevante nel definire il comportamento della funzioneessere più rilevante nel definire il comportamento della funzione

Problemi legati ai datiProblemi legati ai datiPossono essere costosi da ottenerePossono essere costosi da ottenere

Possono essere poco rappresentativi, perché concentrati in Possono essere poco rappresentativi, perché concentrati in particolari aree del dominioparticolari aree del dominio

Possono essere affetti da errorePossono essere affetti da errore



Backpropagation è un algoritmo ottimo nel senso della teoria Backpropagation è un algoritmo ottimo nel senso della teoria della complessità: della complessità: OO((WW ) invece di ) invece di OO((W W 22))

La discesa del gradiente può rimanere La discesa del gradiente può rimanere intrappolata intrappolata in minimi in minimi locali della funzione errorelocali della funzione errore

Una volta caricati i pesi per l’insieme di apprendimento, Una volta caricati i pesi per l’insieme di apprendimento, non c’è garanzia di un non c’è garanzia di un buon buon apprendimento del concetto...apprendimento del concetto...



Dalla teoria del Dalla teoria del PACPAC ( (Probably Approximately CorrectProbably Approximately Correct) learning: per ) learning: per ottenere un errore non superiore a ottenere un errore non superiore a sul test set… sul test set…

……si apprende il training set fino ad un errore inferiore a si apprende il training set fino ad un errore inferiore a /2/2……si usano almeno si usano almeno

pattern per l’apprendimento, dove pattern per l’apprendimento, dove WW è il numero dei pesi ed è il numero dei pesi ed MM il il numero totale di unità nascoste (E. Baum, Neural Computation, numero totale di unità nascoste (E. Baum, Neural Computation, 1989)1989)

3232MM

3232WW

lnln


La presenza del termine La presenza del termine momentomomento garantisce che la rete non garantisce che la rete non reagisca solo alle variazioni locali del gradiente, ma tenga reagisca solo alle variazioni locali del gradiente, ma tenga anche conto della storia recente di tali variazionianche conto della storia recente di tali variazioni

Agendo da filtro passaAgendo da filtro passabasso, il momento assicura inoltre che basso, il momento assicura inoltre che il comportamento della rete non risenta delle piccole il comportamento della rete non risenta delle piccole oscillazioni della superficie d’erroreoscillazioni della superficie d’errore

Senza il momento, l’apprendimento può venire Senza il momento, l’apprendimento può venire intrappolato in un minimo locale “poco profondo”, mentre intrappolato in un minimo locale “poco profondo”, mentre in presenza del momento i piccoli bacini di attrazione in presenza del momento i piccoli bacini di attrazione possono essere “saltati”possono essere “saltati”

Backpropagation con momento Backpropagation con momento 1 1


L’aggiornamento dei pesi viene modificato aggiungendo un L’aggiornamento dei pesi viene modificato aggiungendo un termine relativo all’aggiornamento al passo precedente: termine relativo all’aggiornamento al passo precedente: normalmente, i termini relativi al contributo locale del normalmente, i termini relativi al contributo locale del gradiente ed al momento vengono composti a formare una gradiente ed al momento vengono composti a formare una combinazione lineare convessa (0combinazione lineare convessa (01)1)

ww(t+1) =(t+1) = ((EE(t+1)) + (1(t+1)) + (1))ww(t)(t)

Backpropagation con momento Backpropagation con momento 2 2


Resilient Propagation Resilient Propagation 1 1Gli MLP utilizzano, di solito, funzioni di trasferimento sigmoidali nello strato Gli MLP utilizzano, di solito, funzioni di trasferimento sigmoidali nello strato hiddenhidden

Tali funzioni vengono anche dette “Tali funzioni vengono anche dette “squashingsquashing”, data la loro capacità di ”, data la loro capacità di comprimere input infiniti in un intervallo limitato di outputcomprimere input infiniti in un intervallo limitato di output

Le funzioni sigmoidali sono caratterizzate da una derivata che approssima zero al Le funzioni sigmoidali sono caratterizzate da una derivata che approssima zero al tendere di tendere di xx a a ; questo causa problemi quando si utilizzano tecniche di discesa ; questo causa problemi quando si utilizzano tecniche di discesa lungo il gradiente per l’apprendimento, dato che il gradiente può assumere valori lungo il gradiente per l’apprendimento, dato che il gradiente può assumere valori molto piccoli nelle zone di “saturazione” della sigmoide, non garantendo molto piccoli nelle zone di “saturazione” della sigmoide, non garantendo aggiornamenti significativi di pesi e soglie, anche per valori lontani dall’ottimoaggiornamenti significativi di pesi e soglie, anche per valori lontani dall’ottimo


Nell’algoritmo di Nell’algoritmo di Resilient PropagationResilient Propagation viene utilizzata soltanto viene utilizzata soltanto l’informazione sul segno del gradiente per determinare la “direzione” di l’informazione sul segno del gradiente per determinare la “direzione” di aggiornamento dei pesi, mentre la norma del gradiente non ha nessun aggiornamento dei pesi, mentre la norma del gradiente non ha nessun effetto sull’apprendimentoeffetto sull’apprendimento

Resilient Propagation Resilient Propagation 2 2


Il tasso di apprendimento viene determinato ed adattato singolarmente per ogni Il tasso di apprendimento viene determinato ed adattato singolarmente per ogni pesopeso

ii viene incrementato ogni volta che la derivata della funzione costo, viene incrementato ogni volta che la derivata della funzione costo, relativamente a quel peso, mantiene il segno per due iterazioni successiverelativamente a quel peso, mantiene il segno per due iterazioni successiveii viene decrementato se la derivata cambia segnoviene decrementato se la derivata cambia segno

Il valore di Il valore di i i rimane costante se il gradiente è nullo in quella direzionerimane costante se il gradiente è nullo in quella direzione

Tutte le volte che i pesi mostrano un andamento oscillante, il tasso di Tutte le volte che i pesi mostrano un andamento oscillante, il tasso di apprendimento viene ridotto, ed aumentato se, viceversa, il cambiamento avviene apprendimento viene ridotto, ed aumentato se, viceversa, il cambiamento avviene sempre nella stessa direzionesempre nella stessa direzione

Resilient Propagation Resilient Propagation 3 3


Usando un numero arbitrariamente grande di unità nascoste si può approssimare qualunque Usando un numero arbitrariamente grande di unità nascoste si può approssimare qualunque funzione finita in un dominio finitofunzione finita in un dominio finitoNon c’è regola a priori per determinarne il numero degli hiddenNon c’è regola a priori per determinarne il numero degli hiddenIl numero di unità nascoste definisce il numero di possibili suddivisioni dello spazio degli Il numero di unità nascoste definisce il numero di possibili suddivisioni dello spazio degli ingressiingressiSe si ha conoscenza a priori sul problema da risolvere, si possono fare stime grossolane sulla 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 dimensione dello strato interno (stati da codificare), altrimenti la selezione architetturale viene fatta per mezzo di tecniche di tipo viene fatta per mezzo di tecniche di tipo trialtrialandanderrorerrorSuggerimento: selezionare, inizialmente, architetture “piccole” (ad es., logSuggerimento: selezionare, inizialmente, architetture “piccole” (ad es., log22(N(Ninin+N+Noutout) neuroni ) neuroni nascosti) ed aumentare la complessità della rete (e la sua capacità computazionale) solo se nascosti) ed aumentare la complessità della rete (e la sua capacità computazionale) solo se necessarionecessario

Quante unità nascoste ?Quante unità nascoste ?


Il problema dell’overfitting è in parte legato al problema del Il problema dell’overfitting è in parte legato al problema del dimensionamento dell’architettura della rete per uno specifico compitodimensionamento dell’architettura della rete per uno specifico compito

L’architettura della rete è troppo complessa per il problema in esame L’architettura della rete è troppo complessa per il problema in esame

L’architettura della rete è troppo semplice per il problema in esameL’architettura della rete è troppo semplice per il problema in esameLa rete perde la capacità di generalizzareLa rete perde la capacità di generalizzare

OverfittingOverfitting


Come prevenire l’overfittingCome prevenire l’overfitting

Apprendimento incrementale: la rete aggiunge nodi alla sua struttura Apprendimento incrementale: la rete aggiunge nodi alla sua struttura durante l’apprendimento (durante l’apprendimento (growinggrowing ) ) Apprendimento competitivo: le unità hidden sono forzate a rispondere ad Apprendimento competitivo: le unità hidden sono forzate a rispondere ad un dato input in tempi diversiun dato input in tempi diversiStrategie evoluzionistiche: la rete modifica la sua struttura parametrica Strategie evoluzionistiche: la rete modifica la sua struttura parametrica durante l’apprendimentodurante l’apprendimento

Fermare il processo di training in anticipo (tecniche di Fermare il processo di training in anticipo (tecniche di crosscrossvalidationvalidation per per early stoppingearly stopping) ) Aggiungere rumore ai datiAggiungere rumore ai dati

Soluzioni che controllano il valore assunto dai parametriSoluzioni che controllano il valore assunto dai parametri


L’addestramento di una rete è un processo iterativo in cui i parametri L’addestramento di una rete è un processo iterativo in cui i parametri della rete vengono modificati con l’obiettivo di minimizzare l’errore della rete vengono modificati con l’obiettivo di minimizzare l’errore

commessocommesso

La crossLa crossvalidation è il processo attraverso il quale si controlla validation è il processo attraverso il quale si controlla l’andamento dell’errore su dati non noti alla rete (sui quali non è stata 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 addestrata) per fermare il training quando l’errore su tali dati comincia a crescerea crescere

CrossCrossvalidationvalidation


Addestramento con dati rumorosiAddestramento con dati rumorosi

Per ogni pattern Per ogni pattern xx dell’insieme di training, alla rete viene dell’insieme di training, alla rete viene presentato il pattern (presentato il pattern (xx), dove ), dove è un vettore di rumore è un vettore di rumore casuale: ogni nuova presentazione di casuale: ogni nuova presentazione di xx alla rete risulterà alla rete risulterà alterata da un diverso rumore alterata da un diverso rumore L’introduzione di rumore riduce la possibilità che la rete si L’introduzione di rumore riduce la possibilità che la rete si specializzi troppo sui dati di trainingspecializzi troppo sui dati di trainingÈ È stato provato che addestrare le reti con dati affetti da stato provato che addestrare le reti con dati affetti da rumore migliora la loro capacità di generalizzazione rumore migliora la loro capacità di generalizzazione (Sietsma e Dow, 1991) (Sietsma e Dow, 1991) Un altro modo per introdurre rumore nel processo di Un altro modo per introdurre rumore nel processo di training consiste nell’aggiornare i pesi dopo ogni training consiste nell’aggiornare i pesi dopo ogni presentazione e riordinare gli esempi casualmente alla fine presentazione e riordinare gli esempi casualmente alla fine di ogni iterazione (di ogni iterazione (ononline learningline learning))


Cambiando il modello neuronale…Cambiando il modello neuronale…

Reti Reti Radial Basis FunctionRadial Basis Function (RBF) (RBF)

Architettura composita per problemi di classificazione ed Architettura composita per problemi di classificazione ed approssimazione funzionaleapprossimazione funzionale

Modello a due stratiModello a due strati hidden layer: neuroni con funzione di attivazione che simula un campo hidden layer: neuroni con funzione di attivazione che simula un campo

recettivo localizzato recettivo localizzato output layer: neuroni con funzione di attivazione lineare o sigmoidaleoutput layer: neuroni con funzione di attivazione lineare o sigmoidale

MLP e RBF: modelli equivalenti da un punto di vista funzionaleMLP e RBF: modelli equivalenti da un punto di vista funzionale


Non solo rette!Non solo rette!

Rete neurale di tipo Radial Basis Function (RBF)Rete neurale di tipo Radial Basis Function (RBF)

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”


La rete neurale è un MLP, con neuroni nascosti a base La rete neurale è un MLP, con neuroni nascosti a base radiale; il modello di neurone a base radiale presuppone il radiale; il modello di neurone a base radiale presuppone il calcolo dell’attivazione secondo la formulacalcolo dell’attivazione secondo la formula

aa((ww11, , uu00) = ) = ww11 uu00//

mentre la funzione di uscita èmentre la funzione di uscita è

oo((aa) = e) = eaa

con la classicacon la classica forma a campanaforma a campana

La rete feedforward può essere addestrata tramite La rete feedforward può essere addestrata tramite Backpropagation (tutte le funzioni coinvolte sono Backpropagation (tutte le funzioni coinvolte sono differenziabili)differenziabili)

Reti neurali RBF Reti neurali RBF 1 1

2


Si dimostra che un siffato MLP (con neuroni di output sigmoidali o lineari, in 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, dipendenza dal problema) e con un numero sufficiente di neuroni hidden RBF, è in grado di modellare in maniera ottima insiemi di apprendimento separabili è in grado di modellare in maniera ottima insiemi di apprendimento separabili per ipersfere (iperellissoidi)per ipersfere (iperellissoidi)

Dopo l’apprendimento, i pesi Dopo l’apprendimento, i pesi ww11 approssimano le posizioni dei centroidi, approssimano le posizioni dei centroidi, mentre mentre approssima il raggio dell’ipersfera minima contenente la classe approssima il raggio dell’ipersfera minima contenente la classe

Le reti neurali con neuroni a base radiale nello strato hidden e neuroni lineari 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 nello strato di uscita sono approssimatori universali, così come gli MLP, se dotate di un numero sufficiente di neuroni hidden: qualsiasi funzione continua dotate di un numero sufficiente di neuroni hidden: qualsiasi funzione continua può essere approssimata con un qualsiasi grado di accuratezzapuò essere approssimata con un qualsiasi grado di accuratezza

Reti neurali RBF Reti neurali RBF 2 2


Gli autoassociatori Gli autoassociatori 1 1

Un Un autoassociatoreautoassociatore neurale è una rete multistrato con un neurale è una rete multistrato con un numero di uscite pari al numero degli ingressinumero di uscite pari al numero degli ingressiL’autoassociatore viene addestrato in modo da riprodurre L’autoassociatore viene addestrato in modo da riprodurre sulle uscite il vettore di ingresso, minimizzando la norma sulle uscite il vettore di ingresso, minimizzando la norma quadratica del vettore differenza quadratica del vettore differenza Se il numero di neuroni nascosti è inferiore alle componenti Se il numero di neuroni nascosti è inferiore alle componenti di input, l’attivazione dei neuroni nascosti realizza una di input, l’attivazione dei neuroni nascosti realizza una rappresentazione rappresentazione compressacompressa della informazione in ingresso; della informazione in ingresso; in particolare…in particolare…

……i pesi dagli ingressi ai neuroni nascosti rappresentano i parametri di i pesi dagli ingressi ai neuroni nascosti rappresentano i parametri di compressionecompressione ……i pesi dai neuroni nascosti alle uscite definiscono la i pesi dai neuroni nascosti alle uscite definiscono la decompressione decompressione della rappresentazione contenuta nello strato nascostodella rappresentazione contenuta nello strato nascosto


La rappresentazione nello strato nascosto è ricavata La rappresentazione nello strato nascosto è ricavata ottimizzando l’errore di ricostruzione su un insieme di dati ottimizzando l’errore di ricostruzione su un insieme di dati di esempiodi esempio

In tal senso, gli autoassociatori neurali realizzano un In tal senso, gli autoassociatori neurali realizzano un algoritmo di algoritmo di estrazione delle componenti principali estrazione delle componenti principali non non linearelineare

Gli autoassociatori possono inoltre essere utilizzati come Gli autoassociatori possono inoltre essere utilizzati come classificatori, in base al principio secondo il quale riescono classificatori, in base al principio secondo il quale riescono ad associare bene solo vettori provenienti dalla ad associare bene solo vettori provenienti dalla distribuzione dei dati con cui sono stati addestratidistribuzione dei dati con cui sono stati addestrati



In altre parole, una volta addestrato con dati estratti da una In altre parole, una volta addestrato con dati estratti da una certa distribuzione, l’autoassociatore rappresenta un certa distribuzione, l’autoassociatore rappresenta un prototipoprototipo per tale classe per tale classe

Si può verificare se un vettore appartiene ad una classe di cui Si può verificare se un vettore appartiene ad una classe di cui l’autoassociatore è il modello (o prototipo) calcolando la l’autoassociatore è il modello (o prototipo) calcolando la distanza fra il vettore di ingresso e l’uscita prodotta distanza fra il vettore di ingresso e l’uscita prodotta



Un classificatore per più classi può essere costruito in modo modulare Un classificatore per più classi può essere costruito in modo modulare definendo un autoassociatore (prototipo) per ogni classe definendo un autoassociatore (prototipo) per ogni classe

Un vettore di ingresso viene classificato presentandolo in parallelo Un vettore di ingresso viene classificato presentandolo in parallelo a tutti gli autoassociatori e attribuendolo alla classe corrispondente a tutti gli autoassociatori e attribuendolo alla classe corrispondente all’autoassociatore per il quale la distanza fra ingresso e uscita è all’autoassociatore per il quale la distanza fra ingresso e uscita è minimaminimaSi può anche introdurre una Si può anche introdurre una soglia di reiezione, soglia di reiezione, considerando non considerando non classificati quei vettori per i quali la distanza è superiore a tale classificati quei vettori per i quali la distanza è superiore a tale soglia o per i quali la differenza di distanza fra due o più soglia o per i quali la differenza di distanza fra due o più autoassociatori è inferiore alla sogliaautoassociatori è inferiore alla soglia

L’apprendimento di ogni autoassociatore può essere effettuato L’apprendimento di ogni autoassociatore può essere effettuato utilizzando solo esempi della classe a cui corrispondeutilizzando solo esempi della classe a cui corrisponde



Per migliorare le prestazioni possono essere introdotti nell’insieme dei dati usati Per migliorare le prestazioni possono essere introdotti nell’insieme dei dati usati per l’apprendimento anche esempi per l’apprendimento anche esempi negativi, negativi, in genere appartenenti a quelle classi in genere appartenenti a quelle classi che più si confondono con quella che si deve riconoscereche più si confondono con quella che si deve riconoscere

Apprendimento e superfici di decisione per un autoassociatore Apprendimento e superfici di decisione per un autoassociatore addestrato con e senza esempi negativiaddestrato con e senza esempi negativi


Support Vector MachineSupport Vector Machine



Le Le Support Vector MachineSupport Vector Machine (SVM) sono state sviluppate (SVM) sono state sviluppate presso gli AT&T Bell Laboratories, a partire dai primi anni presso gli AT&T Bell Laboratories, a partire dai primi anni `90,`90, da Vapnik e colleghi (Boser et al., 1992, Guyon et al., da Vapnik e colleghi (Boser et al., 1992, Guyon et al., 1993, Cortes e Vapnik, 1995, Schölkopf et al., 1995, 1993, Cortes e Vapnik, 1995, Schölkopf et al., 1995, Vapnik et al., 1997)Vapnik et al., 1997)

Dato il contesto industriale, la ricerca sulle SVM ha finora Dato il contesto industriale, la ricerca sulle SVM ha finora avuto una decisa inclinazione applicativa avuto una decisa inclinazione applicativa



Primi lavori relativi a: Primi lavori relativi a:

OCR (OCR (Optical Character RecognitionOptical Character Recognition, dove in breve le , dove in breve le SVM divennero competitive con i metodi migliori) SVM divennero competitive con i metodi migliori)

Riconoscimento di oggetti (Blanz et al., 1996)Riconoscimento di oggetti (Blanz et al., 1996)

Identificazione di oratori (Schmidt, 1996)Identificazione di oratori (Schmidt, 1996)

Identificazione di volti in immagini (Osuna, et al. 1997) Identificazione di volti in immagini (Osuna, et al. 1997)

Classificazione di testi (Joachims, 1997)Classificazione di testi (Joachims, 1997)

Bioinformatica: classificazione di sequenze di proteine, Bioinformatica: classificazione di sequenze di proteine, gene expression, informazioni filogenetichegene expression, informazioni filogenetiche



L’algoritmo L’algoritmo Support VectorSupport Vector, alla base delle SVM, , alla base delle SVM,

……è una generalizzazione dell’algoritmo è una generalizzazione dell’algoritmo Generalized Generalized PortraitPortrait, sviluppato in Russia nei primi anni , sviluppato in Russia nei primi anni `60`60 (Vapnik e Lerner, 1963, Vapnik e Chervonenkis, 1964)(Vapnik e Lerner, 1963, Vapnik e Chervonenkis, 1964)

……appartiene alla categoria degli algoritmi appartiene alla categoria degli algoritmi di di statistical statistical learning theorylearning theory, la teoria di Vapnik, la teoria di VapnikChervonenkis Chervonenkis (Vapnik, Chervonenkis 1974, Vapnik 1982, 1995) (Vapnik, Chervonenkis 1974, Vapnik 1982, 1995)

Essenzialmente, la teoria VC caratterizza le proprietà degli Essenzialmente, la teoria VC caratterizza le proprietà degli algoritmi di apprendimento che permettono loro di algoritmi di apprendimento che permettono loro di “estendere la conoscenza” a dati nuovi, in base ad elementi “estendere la conoscenza” a dati nuovi, in base ad elementi appresi in precedenza appresi in precedenza



Una SVM è un classificatore binario che apprende il Una SVM è un classificatore binario che apprende il confine fra esempi appartenenti a due diverse classi confine fra esempi appartenenti a due diverse classi Funziona proiettando gli esempi in uno spazio Funziona proiettando gli esempi in uno spazio multidimensionale e cercando un iperpiano di separazione multidimensionale e cercando un iperpiano di separazione in questo spazioin questo spazioL’iperpiano di separazione massimizza la sua distanza (il L’iperpiano di separazione massimizza la sua distanza (il “margine”) dagli esempi di training più vicini “margine”) dagli esempi di training più vicini Proprietà generali delle SVM: Proprietà generali delle SVM:

improbabile l’overfitting improbabile l’overfitting capacità di gestire dati con molte featurecapacità di gestire dati con molte featureestrazione dell’informazione “più significativa” estrazione dell’informazione “più significativa” contenuta nel data set in inputcontenuta nel data set in input



Nel caso della classificazione di dati appartenenti a due sole classi, il Nel caso della classificazione di dati appartenenti a due sole classi, il processo di apprendimento può essere formulato come segue: processo di apprendimento può essere formulato come segue:

dato un insieme di funzioni di soglia dato un insieme di funzioni di soglia

dove dove è un insieme di parametri reali, e dato un insieme di esempi è un insieme di parametri reali, e dato un insieme di esempi preclassificati (preclassificati (xx11,y,y11),…,(),…,(xxmm,y,ymm), ), xxiiNN, , yyii{{1,1,1}, presi da una 1}, presi da una

distribuzione sconosciuta distribuzione sconosciuta PP((xx,,yy), si vuole calcolare una funzione ), si vuole calcolare una funzione ff

che minimizzi l’errore teorico: che minimizzi l’errore teorico:


Errore teoricoErrore teorico

L’insieme di parametri reali L’insieme di parametri reali genera una macchina in grado di genera una macchina in grado di risolvere un particolare problema (ad esempio risolvere un particolare problema (ad esempio può corrispondere ai può corrispondere ai pesi delle sinapsi di una rete neurale)pesi delle sinapsi di una rete neurale)

Le funzioni Le funzioni ff sono le ipotesi, e l’insieme {sono le ipotesi, e l’insieme {ff((xx): ): } è lo spazio } è lo spazio HH delle ipotesi delle ipotesi

L’errore teorico rappresenta una misura di quanto sia buona un’ipotesi L’errore teorico rappresenta una misura di quanto sia buona un’ipotesi nel predire la classe nel predire la classe yyi i di un punto di un punto xx

L’insieme delle funzioni può essere realizzato da un MLP classico o L’insieme delle funzioni può essere realizzato da un MLP classico o con neuroni RBF, con un numero opportuno di unità nascostecon neuroni RBF, con un numero opportuno di unità nascoste


Errore empiricoErrore empirico

La distribuzione di probabilità La distribuzione di probabilità PP((xx,,yy) non è nota, quindi non è possibile ) non è nota, quindi non è possibile calcolare l’errore teorico calcolare l’errore teorico RR((); tuttavia è disponibile un campione di ); tuttavia è disponibile un campione di PP((xx,,yy): il training set ): il training set

si può calcolare un’approssimazione di si può calcolare un’approssimazione di RR((), l’errore empirico ), l’errore empirico RRempemp((): ):

La legge dei grandi numeri garantisce che l’errore empirico converge in La legge dei grandi numeri garantisce che l’errore empirico converge in probabilità all’errore teoricoprobabilità all’errore teorico


VCVCdimensiondimension

La La VCVCdimensiondimension dello spazio di ipotesi dello spazio di ipotesi HH (o del classificatore (o del classificatore ff) è un ) è un

numero naturale che corrisponde al più grande numero di punti che numero naturale che corrisponde al più grande numero di punti che possono essere separati in tutti i modi possibili dall’insieme di funzioni possono essere separati in tutti i modi possibili dall’insieme di funzioni ff

In altre parole, dato un insieme di In altre parole, dato un insieme di l l punti, se per ognuna delle 2punti, se per ognuna delle 2l l

possibili classificazioni (possibili classificazioni (1,1,1) esiste una funzione in {1) esiste una funzione in {ff} che assegna } che assegna

correttamente le classi, allora si dice che l’insieme di punti viene correttamente le classi, allora si dice che l’insieme di punti viene separato dall’insieme di funzioni separato dall’insieme di funzioni

La VCLa VCdimension è una misura della complessità dell’insieme dimension è una misura della complessità dell’insieme HH


VCVCdimension ottimadimension ottima

La teoria della convergenza uniforme in probabilità, sviluppata da La teoria della convergenza uniforme in probabilità, sviluppata da Vapnik e Chervonenkis, fornisce anche un limite alla deviazione Vapnik e Chervonenkis, fornisce anche un limite alla deviazione dell’errore empirico dall’errore teoricodell’errore empirico dall’errore teorico

Fissato Fissato , con 0, con 0 1, vale la disuguaglianza: 1, vale la disuguaglianza:

dove dove h h è la VCè la VCdimension di dimension di ff


Minimizzazione dell’errore teoricoMinimizzazione dell’errore teorico

Per ottenere l’errore teorico minimo, occorre minimizzare sia l’errore Per ottenere l’errore teorico minimo, occorre minimizzare sia l’errore empirico sia il rapporto tra la VCempirico sia il rapporto tra la VCdimension ed il numero di punti (dimension ed il numero di punti (hh//ll ))

L’errore empirico è solitamente una funzione decrescente di L’errore empirico è solitamente una funzione decrescente di hh, quindi, , quindi, per ogni dato numero di punti, esiste un valore ottimale della per ogni dato numero di punti, esiste un valore ottimale della VCVCdimension (tradeoff dimension (tradeoff RRempemp e e hh//ll ))

L’algoritmo SVM risolve efficacemente questo problema L’algoritmo SVM risolve efficacemente questo problema minimizzando contemporaneamente la VCminimizzando contemporaneamente la VCdimension ed il numero di dimension ed il numero di errori sul training set errori sul training set

Caso 1: Caso 1: dati linearmente separabilidati linearmente separabili


Classificatore lineare su Classificatore lineare su dati linearmente separabili dati linearmente separabili 1 1

Ipotesi: insieme di dati linearmente separabili; si vuole Ipotesi: insieme di dati linearmente separabili; si vuole calcolare il miglior iperpiano separatorecalcolare il miglior iperpiano separatore

Un insieme di dati è linearmente separabile quando esiste Un insieme di dati è linearmente separabile quando esiste una coppia (una coppia (ww,,bb) tale che) tale che

wxwxii++bb 0 per 0 per xxiiCC11

wxwxii++bb < 0 < 0 per per xxiiCC22


Classificatore lineare su Classificatore lineare su dati linearmente separabili dati linearmente separabili 2 2

Lo spazio delle ipotesi in questo caso è formato Lo spazio delle ipotesi in questo caso è formato dall’insieme di funzionidall’insieme di funzioni

((signsign, discriminatore binario: +/, discriminatore binario: +/, 0/1, vero/falso, etc.), 0/1, vero/falso, etc.)


Separazione lineare Separazione lineare (es. perceptron)(es. perceptron)


Separatori Separatori llineariineari

Quale separatore è ottimo?Quale separatore è ottimo?


La distanza tra un punto La distanza tra un punto xx e l’iperpiano associato alla e l’iperpiano associato alla coppia (coppia (ww,,bb) è:) è:

Se l’iperpiano Se l’iperpiano wxwxbb=0 separa il training set =0 separa il training set DD, si definisce , si definisce marginemargine la quantità la quantità ((ww,,DD))

Iperpiani di separazione Iperpiani di separazione 1 1


Come scegliere la parametrizzazione?Come scegliere la parametrizzazione?

Un iperpiano separatore è parametrizzato dai Un iperpiano separatore è parametrizzato dai coefficienti coefficienti ww e e b, b, ma la scelta non è unica: ma la scelta non è unica: moltiplicando i parametri per una costante positiva si moltiplicando i parametri per una costante positiva si ottiene lo stesso iperpianoottiene lo stesso iperpiano

Occorre fissare Occorre fissare wwPrima soluzione: si fissa Prima soluzione: si fissa ww=1, nel qual caso =1, nel qual caso ddww((xx)=)=wwxxbb e e ((ww,,DD)=min)=minii yyii((wwxxiibb))

Altrimenti… si fissa Altrimenti… si fissa ww in modo tale che in modo tale che ((ww,,DD)=1/)=1/ww, cioè si impone min, cioè si impone minii yyii((wwxxiibb)=1)=1

è una parametrizzazione è una parametrizzazione datadatadependentdependent



Più in generale, la distanza tra l’iperpiano (Più in generale, la distanza tra l’iperpiano (ww,,bb) e il più vicino ) e il più vicino punto dell’insieme dei dati è funzione di punto dell’insieme dei dati è funzione di 1/1/ww

Se si impone Se si impone wwAA, la distanza dell’iperpiano dal punto , la distanza dell’iperpiano dal punto più vicino deve essere maggiore di 1/più vicino deve essere maggiore di 1/AA


• Si considerano solo gli iperpiani Si considerano solo gli iperpiani che non intersecano nessuna che non intersecano nessuna delle sfere di raggio 1/delle sfere di raggio 1/AA centrate sui punti dell’insieme centrate sui punti dell’insieme di datidi dati



Se i dati sono linearmente separabili, lo scopo della SVM è Se i dati sono linearmente separabili, lo scopo della SVM è quello di trovare, tra tutti gli iperpiani che classificano quello di trovare, tra tutti gli iperpiani che classificano correttamente il training set, l’iperpiano che ha norma correttamente il training set, l’iperpiano che ha norma minima (minima (ww minima), cioè margine massimo rispetto ai minima), cioè margine massimo rispetto ai punti del training setpunti del training set

Le classi dei cerchi e dei quadrati Le classi dei cerchi e dei quadrati sono separate dal piano sono separate dal piano tratteggiato, con un margine tratteggiato, con un margine piccolo (a), o grande (b) piccolo (a), o grande (b)

Nel caso (b) ci si aspetta un minor Nel caso (b) ci si aspetta un minor rischio di overfitting, ovvero una rischio di overfitting, ovvero una maggiore capacità di maggiore capacità di generalizzazionegeneralizzazione(b)(b)(a)(a)


Massimo margineMassimo margine L’iperpiano ottimo è quello che massimizza il margine, L’iperpiano ottimo è quello che massimizza il margine, cioè la distanza tra se stesso e i punti più vicini dell’insieme cioè la distanza tra se stesso e i punti più vicini dell’insieme di datidi dati

Per costruire l’iperpiano ottimo, occorre classificare Per costruire l’iperpiano ottimo, occorre classificare correttamente i punti del training set nelle due classi correttamente i punti del training set nelle due classi yyii{{1,1} minimizzando la norma di 1,1} minimizzando la norma di ww

Il problema può essere formulato come segue: Il problema può essere formulato come segue:


Questo problema si può risolvere con la tecnica dei Questo problema si può risolvere con la tecnica dei moltiplicatori di Lagrange in cui si introduce un moltiplicatori di Lagrange in cui si introduce un moltiplicatore per ogni vincolo moltiplicatore per ogni vincolo

La lagrangiana del problema è: La lagrangiana del problema è:

in cui in cui =(=(11,…,,…,ll) è il vettore dei moltiplicatori di ) è il vettore dei moltiplicatori di LagrangeLagrange

i

Lagrangiana Lagrangiana 1 1


La lagrangiana deve essere minimizzata rispetto a La lagrangiana deve essere minimizzata rispetto a ww e e bb e e contemporaneamente massimizzata rispetto a contemporaneamente massimizzata rispetto a ≥0: si cerca ≥0: si cerca un punto di sellaun punto di sella

Differenziando rispetto a Differenziando rispetto a ww e e bb si ottiene… si ottiene…




ww** può essere scritto come una combinazione lineare dei può essere scritto come una combinazione lineare dei vettori vettori xxii del training set: del training set:

ww** = = i i ii **yyi i xxi i ff((xx) = ) = ww**x + x + b = b = i i ii

**yyi i xxi i xx + b + b

I dati appaiono solo all’interno di prodotti scalariI dati appaiono solo all’interno di prodotti scalari

Sostituendo il valore calcolato Sostituendo il valore calcolato ww** nella lagrangiana si può nella lagrangiana si può riformulare il problema in una forma riformulare il problema in una forma dualeduale più semplice più semplice

Nella formulazione duale, la funzione da ottimizzare è una Nella formulazione duale, la funzione da ottimizzare è una funzione quadratica nei funzione quadratica nei ii



Nel nuovo problema i vincoli originali sono sostituiti da Nel nuovo problema i vincoli originali sono sostituiti da vincoli sui moltiplicatori ed i vettori del training set appaiono vincoli sui moltiplicatori ed i vettori del training set appaiono solo sotto forma di prodotti scalarisolo sotto forma di prodotti scalari

La complessità del problema duale non dipende dalla La complessità del problema duale non dipende dalla dimensione degli ingressi, ma dalla cardinalità del training setdimensione degli ingressi, ma dalla cardinalità del training set


Support vector Support vector 1 1

La soluzione del nuovo problema fornisce i moltiplicatori La soluzione del nuovo problema fornisce i moltiplicatori di Lagrangedi LagrangeL’iperpiano ottimo si ricava… L’iperpiano ottimo si ricava…

……dall’espressione di dall’espressione di ww**, dopo la sostituzione dei moltiplicatori , dopo la sostituzione dei moltiplicatori calcolaticalcolati……mentre il valore di mentre il valore di bb* * deriva dall’applicazione delle condizioni deriva dall’applicazione delle condizioni KuhnKuhnTucker, Tucker, ii

**((yyii((ww**xxbb**))1)=01)=0

Il classificatore è dato daIl classificatore è dato da

per ogni vettore per ogni vettore xx

**


Support vector Support vector 2 2Nella soluzione, tutti i punti Nella soluzione, tutti i punti xxii per cui il corrispondente per cui il corrispondente moltiplicatore moltiplicatore ii è strettamente maggiore di zero vengono è strettamente maggiore di zero vengono detti detti support vectorsupport vector e si trovano su uno dei due iperpiani e si trovano su uno dei due iperpiani HH11, , HH22 equidistanti dall’iperpiano ottimo e ad esso paralleli equidistanti dall’iperpiano ottimo e ad esso paralleli (per le condizioni di Kuhn(per le condizioni di KuhnTucker)Tucker)Tutti gli altri punti del training set hanno il corrispondente Tutti gli altri punti del training set hanno il corrispondente ii uguale a zero e non influenzano il classificatore uguale a zero e non influenzano il classificatoreI support vector sono i punti critici del training set e sono i I support vector sono i punti critici del training set e sono i più vicini all’iperpiano di separazione; se tutti gli altri punti più vicini all’iperpiano di separazione; se tutti gli altri punti venissero rimossi o spostati senza oltrepassare i piani venissero rimossi o spostati senza oltrepassare i piani HH1 1 e e HH22 e l’algoritmo di apprendimento venisse ripetuto, darebbe e l’algoritmo di apprendimento venisse ripetuto, darebbe esattamente lo stesso risultatoesattamente lo stesso risultato


rr

Da notare…Da notare…L’iperpiano ottimo di separazione è determinato solo in base ai L’iperpiano ottimo di separazione è determinato solo in base ai support vector che, in generale, sono in numero esiguo rispetto support vector che, in generale, sono in numero esiguo rispetto alla cardinalità alla cardinalità l l del training setdel training set

Tutta l’informazione contenuta nel training set è concentrata nei Tutta l’informazione contenuta nel training set è concentrata nei soli vettori di supporto, che sono gli unici dati sui quali si soli vettori di supporto, che sono gli unici dati sui quali si effettua l’apprendimentoeffettua l’apprendimento

Caso 2:Caso 2:classificatore lineare su dati non classificatore lineare su dati non

linearmente separabililinearmente separabili


Per come è stato definito, il classificatore a supporto Per come è stato definito, il classificatore a supporto vettoriale lineare non è in grado gestire casi in cui le classi vettoriale lineare non è in grado gestire casi in cui le classi non siano linearmente separabilinon siano linearmente separabili

Come risolvere il problema?Come risolvere il problema?

Rilassare i vincoli di corretta classificazione, tollerando Rilassare i vincoli di corretta classificazione, tollerando un certo numero di erroriun certo numero di errori

Realizzare altre superfici di separazione oltre l’iperpianoRealizzare altre superfici di separazione oltre l’iperpiano

Classificatore lineare su Classificatore lineare su dati non linearmente separabili dati non linearmente separabili 1 1


Classificatore lineare su Classificatore lineare su dati non linearmente separabili dati non linearmente separabili 2 2

Piano separatore per un insieme di punti non linearmente Piano separatore per un insieme di punti non linearmente separabili; il piano ha distanza separabili; il piano ha distanza bb//ww dall’origine e viene dall’origine e viene determinato dai support vector (i punti cerchiati) determinato dai support vector (i punti cerchiati) Il punto in posizione anomala dista Il punto in posizione anomala dista //w w dalla sua classe dalla sua classe


Dati non linearmente separabili Dati non linearmente separabili 1 1

Generalizzazione dell’iperpiano ottimoGeneralizzazione dell’iperpiano ottimo

Nella fase di ottimizzazione si rilassa il vincolo di esatta Nella fase di ottimizzazione si rilassa il vincolo di esatta classificazione dei campioni del training set (classificazione dei campioni del training set (soft soft marginmargin), introducendo delle variabili ), introducendo delle variabili slack slack ii

I vincoli diventano:I vincoli diventano:

wwxxiib b 1 1 i i per per yyii= = 11

wwxxiib b 1 1 i i per per yyii= = 11

con con i i 0, per ogni 0, per ogni ii



In base al valore assunto dalla corrispondente variabile di In base al valore assunto dalla corrispondente variabile di slack, i punti del training set saranno:slack, i punti del training set saranno:

disposti al di là degli iperpiani disposti al di là degli iperpiani HH11 e e HH22 e correttamente e correttamente

classificati (classificati (ii=0) =0)

posti tra gli iperpiani posti tra gli iperpiani HH11 e e HH22 e correttamente classificati e correttamente classificati

(0<(0<ii<1) <1)

erroneamente classificati (erroneamente classificati (i i >1)>1)


Dati non linearmente separabili Dati non linearmente separabili 3 3Il problema può essere formulato comeIl problema può essere formulato come

dove dove CC e e kk sono parametri che devono essere determinati a sono parametri che devono essere determinati a priori: ad un alto valore di priori: ad un alto valore di CC corrisponde un’alta penalità corrisponde un’alta penalità dovuta agli erroridovuta agli errori



Le variabili di Le variabili di slackslack si introducono per rilassare il vincolo si introducono per rilassare il vincolo di separabilitàdi separabilità

i i 0 0 x xii ha margine < ha margine <ww11

In pratica, l’algoritmo SVM cerca di minimizzare In pratica, l’algoritmo SVM cerca di minimizzare ww e e di separare i punti dati commettendo il numero minimo di di separare i punti dati commettendo il numero minimo di errori possibileerrori possibile

La soluzione al problema di ottimizzazione si trova in La soluzione al problema di ottimizzazione si trova in modo analogo al caso linearmente separabilemodo analogo al caso linearmente separabile



La lagrangiana del problema è:La lagrangiana del problema è:

in cui i moltiplicatori in cui i moltiplicatori =(=(11,…,,…,ll), ), =(=(11,…,,…,ll)) sono sono associati ai vincoli associati ai vincoli

LL deve essere minimizzata rispetto a deve essere minimizzata rispetto a ww, , b b e e =[=[11,…,,…,ll]] e massimizzata rispetto a e massimizzata rispetto a ≥0 e ≥0 e ≥0≥0



Supponendo Supponendo kk=1 per semplificare i calcoli, si arriva ad una =1 per semplificare i calcoli, si arriva ad una riformulazione duale del problema simile ancora al caso riformulazione duale del problema simile ancora al caso linearmente separabilelinearmente separabile



La soluzione del problema è identica a quella del caso La soluzione del problema è identica a quella del caso separabile tranne per il vincolo sui moltiplicatori, che separabile tranne per il vincolo sui moltiplicatori, che adesso sono limitati superiormente da adesso sono limitati superiormente da CC

Il classificatore è: Il classificatore è:

Caso 3:Caso 3:classificatore non lineareclassificatore non lineare


Classificatore non lineare Classificatore non lineare 1 1

Alternativamente, nel caso di dati non linearmente Alternativamente, nel caso di dati non linearmente separabili, si introduce un mapping separabili, si introduce un mapping ((xx)) verso uno spazio verso uno spazio di dimensione “molto più grande”, in cui gli esempi che di dimensione “molto più grande”, in cui gli esempi che compongono l’insieme degli ingressi siano linearmente compongono l’insieme degli ingressi siano linearmente separabiliseparabiliInvece di aumentare la complessità del classificatore Invece di aumentare la complessità del classificatore

(che resta un iperpiano) si aumenta la dimensione dello (che resta un iperpiano) si aumenta la dimensione dello spazio delle featurespazio delle feature

In dipendenza della dimensione dello spazio in cui è In dipendenza della dimensione dello spazio in cui è formulato il problema originale, il mapping può portare a formulato il problema originale, il mapping può portare a spazi “trasformati” a dimensione molto elevata (fino a 10spazi “trasformati” a dimensione molto elevata (fino a 1066) )



Le due classi rappresentate dai cerchi e dai quadrati nello Le due classi rappresentate dai cerchi e dai quadrati nello spazio di input non sono linearmente separabili, ma spazio di input non sono linearmente separabili, ma attraverso la funzione attraverso la funzione i punti vengono mappati in uno i punti vengono mappati in uno spazio in cui divengono linearmente separabili spazio in cui divengono linearmente separabili


Esempio: le due spirali Esempio: le due spirali 1 1

Esiste un iperpiano nello spazio delle feature per cui i dati Esiste un iperpiano nello spazio delle feature per cui i dati sono linearmente separabilisono linearmente separabili


Esempio: le due spirali Esempio: le due spirali 2 2


UnUn’’altra situazione possibile…altra situazione possibile…

: : xx ((xx))


Funzioni kernelFunzioni kernel

Supponiamo di mappare i dati iniziali non linearmente Supponiamo di mappare i dati iniziali non linearmente separabili in uno spazio di dimensione superiore in cui essi separabili in uno spazio di dimensione superiore in cui essi siano linearmente separabili, usando una funzione di siano linearmente separabili, usando una funzione di mapping mapping : : ddHH

Uno spazio di dimensione maggiore causa però seri problemi Uno spazio di dimensione maggiore causa però seri problemi di calcolo, perché l’algoritmo di apprendimento deve di calcolo, perché l’algoritmo di apprendimento deve lavorare con vettori di grandi dimensioni (con molte lavorare con vettori di grandi dimensioni (con molte componenti)componenti)

Tuttavia, in questa situazione, l’algoritmo di apprendimento Tuttavia, in questa situazione, l’algoritmo di apprendimento dipende dai dati solamente tramite il prodotto delle loro dipende dai dati solamente tramite il prodotto delle loro immagini attraverso immagini attraverso in in HH, cioè tramite funzioni della , cioè tramite funzioni della forma forma ((xxii))··((xxjj))


KernelKernelPer ovviare al problema dell’aumento della dimensione dei Per ovviare al problema dell’aumento della dimensione dei vettori di feature si introduce quindi una vettori di feature si introduce quindi una funzione kernelfunzione kernel che restituisce il prodotto delle immagini, attraverso che restituisce il prodotto delle immagini, attraverso , dei , dei suoi due argomenti:suoi due argomenti:

KK((xxii,x,xjj)= )= ((xxii))((xxjj))

è possibile evitare di eseguire il prodotto esplicito tra le è possibile evitare di eseguire il prodotto esplicito tra le immagini dei vettori, è sufficiente conoscerne la “forma immagini dei vettori, è sufficiente conoscerne la “forma funzionale” funzionale”

Pertanto è possibile sostituire Pertanto è possibile sostituire KK all’interno dell’algoritmo e all’interno dell’algoritmo e ignorare la forma esplicita di ignorare la forma esplicita di


Quali funzioni sono Quali funzioni sono kkernelernel ??

Per alcune funzioni Per alcune funzioni KK((xxii,,xxjj) verificare che) verificare che KK((xxii,,xxjj)=)=((xxii))TT((xxjj) è complesso) è complesso

Teorema di Mercer Teorema di Mercer Ogni funzione simmetrica semiOgni funzione simmetrica semidefinita positiva è un kerneldefinita positiva è un kernel

L’impiego di funzioni kernel di fatto “nasconde” il L’impiego di funzioni kernel di fatto “nasconde” il mapping nello spazio multimapping nello spazio multidimensionaledimensionale


Matrice kernelMatrice kernel

È È una rappresentazione matriciale della funzione kernel una rappresentazione matriciale della funzione kernel (argomenti: gli (argomenti: gli mm vettori di apprendimento): vettori di apprendimento):

Contiene tutte le informazioni necessarie per Contiene tutte le informazioni necessarie per l’apprendimentol’apprendimento

Riassume informazioni sui dati e sul kernel Riassume informazioni sui dati e sul kernel

È È simmetrica e semisimmetrica e semidefinita positivadefinita positiva


Ancora sulla lineare separabilità…Ancora sulla lineare separabilità…

Sostituendo Sostituendo ((xxii)) ((xxjj)) con con KK((xxii,x,xjj) nell’algoritmo, si ) nell’algoritmo, si

genera una Support Vector Machine che “lavora” in genera una Support Vector Machine che “lavora” in HH e e fornisce il risultato nella stessa quantità di tempo che fornisce il risultato nella stessa quantità di tempo che impiegherebbe se lavorasse con i dati originali non impiegherebbe se lavorasse con i dati originali non trasformati trasformati

Tutte le considerazioni fatte nel caso linearmente separabile Tutte le considerazioni fatte nel caso linearmente separabile restano valide, poiché si sta costruendo un classificatore restano valide, poiché si sta costruendo un classificatore lineare in uno spazio differente lineare in uno spazio differente

In pratica, l’estensione a superfici di decisione complesse In pratica, l’estensione a superfici di decisione complesse avviene in maniera semplice: mappando la variabile in input avviene in maniera semplice: mappando la variabile in input xx in uno spazio di dimensione maggiore e lavorando poi con in uno spazio di dimensione maggiore e lavorando poi con una classificazione lineare nel nuovo spaziouna classificazione lineare nel nuovo spazio


Feature expansionFeature expansion



Un punto Un punto xx viene mappato in un vettore di “feature” tramite viene mappato in un vettore di “feature” tramite la funzione la funzione : : xx((xx)=()=(aa1111((xx),),aa2222((xx),…) dove gli ),…) dove gli aaii

sono numeri reali e le sono numeri reali e le ii sono funzioni realisono funzioni reali

Quindi, si applica lo stesso algoritmo del caso linearmente Quindi, si applica lo stesso algoritmo del caso linearmente separabile sostituendo la variabile separabile sostituendo la variabile xx con un nuovo vettore di con un nuovo vettore di feature feature ((xx) )



La funzione di decisione con il mapping diventa quindi:La funzione di decisione con il mapping diventa quindi:

Sostituendo i prodotti scalari Sostituendo i prodotti scalari ((xxii))··((xxjj) con una funzione ) con una funzione kernel:kernel:

si ottienesi ottiene


Esempio Esempio 1 1

Supponiamo Supponiamo xx22 e e KK((xxii,,xxjj)=()=(xxii x xjj))2 2

In questo caso, lo spazio In questo caso, lo spazio HH e il mapping e il mapping : : 22HH tale che tale che ((xxii x xjj))22==((xxii)·)·((xxjj) sono dati da ) sono dati da H H ==33 ee

Infatti…Infatti…


Esempio Esempio 2 2

L’XORL’XOR diventa linearmente separabile per diventa linearmente separabile per : : 22 33, con , con ((xx11,,xx22)=()=(xx11, , xx22, , xx11 xx22))


Esempio Esempio 3 3

L’immagine di L’immagine di può esistere in uno spazio anche di può esistere in uno spazio anche di dimensione infinita, ma è solo una superficie, anche se dimensione infinita, ma è solo una superficie, anche se molto “contorta”, la cui dimensione intrinseca, il numero di molto “contorta”, la cui dimensione intrinseca, il numero di parametri necessari per specificare un punto, è la stessa parametri necessari per specificare un punto, è la stessa dello spazio dei vettori dello spazio dei vettori xx


Tipi di kernel Tipi di kernel 1 1

La funzione kernel va scelta accuratamente per il La funzione kernel va scelta accuratamente per il particolare tipo di problema: è sempre possibile trasformare particolare tipo di problema: è sempre possibile trasformare l’input in uno spazio di dimensione maggiore del numero di l’input in uno spazio di dimensione maggiore del numero di punti del training set e produrre un classificatore perfetto…punti del training set e produrre un classificatore perfetto…

……Tuttavia, questi generalizzerebbe malissimo su dati Tuttavia, questi generalizzerebbe malissimo su dati nuovi, a causa dell’overfittingnuovi, a causa dell’overfitting


Tipi di kernel Tipi di kernel 2 2

Tipi di kernel comunemente usati sono:Tipi di kernel comunemente usati sono:


ModularitàModularità

Una SVM è composta da due moduli: Una SVM è composta da due moduli:

Un modulo generale di apprendimento Un modulo generale di apprendimento

Una funzione kernel specifica per il problema da Una funzione kernel specifica per il problema da affrontare affrontare

Qualsiasi SVM può operare con qualsiasi kernel Qualsiasi SVM può operare con qualsiasi kernel

Il problema di apprendere un compito difficile si sposta nel Il problema di apprendere un compito difficile si sposta nel problema di scegliere opportunamente una funzione kernel problema di scegliere opportunamente una funzione kernel (di nuovo un problema difficile…) per trasformarlo in un (di nuovo un problema difficile…) per trasformarlo in un compito facile (perché linearmente separabile)compito facile (perché linearmente separabile)


Come scegliere un classificatore SVMCome scegliere un classificatore SVM ??

Per impiegare una SVM è allora necessario definire:Per impiegare una SVM è allora necessario definire: tipo di kernel da impiegaretipo di kernel da impiegare parametri del particolare kernelparametri del particolare kernel valore di Cvalore di C

Non esistono criteri teorici per queste scelte; tipicamente Non esistono criteri teorici per queste scelte; tipicamente occorre una verifica su un insieme di validazioneoccorre una verifica su un insieme di validazione


Classificazione multiclasse Classificazione multiclasse 1 1

Le SVM si applicano solo a problemi di classificazione Le SVM si applicano solo a problemi di classificazione binaria (cioè sono capaci di predire il valore di una binaria (cioè sono capaci di predire il valore di una variabile booleana)variabile booleana)

Come fare per problemi multiclasse ad Come fare per problemi multiclasse ad NN classi? classi?

Si addestrano Si addestrano NN support vector machine support vector machine SVM 1 apprende “Output==1” vs “Output != 1”SVM 1 apprende “Output==1” vs “Output != 1”SVM 2 apprende “Output==2” vs “Output != 2”SVM 2 apprende “Output==2” vs “Output != 2”……SVM SVM NN apprende “Output== apprende “Output==NN” vs “Output != ” vs “Output != NN””


Classificazione multiclasse Classificazione multiclasse 2 2

Per predire l’output relativo ad un nuovo input, si sceglie Per predire l’output relativo ad un nuovo input, si sceglie quella SVM che mappa il pattern nel semipiano positivo, quella SVM che mappa il pattern nel semipiano positivo, con massimo margine rispetto all’iperpiano separatorecon massimo margine rispetto all’iperpiano separatore


Esempio: IRIS dataset Esempio: IRIS dataset 1 1L’iris dataset contiene i dati relativi a 150 iris, appartenenti L’iris dataset contiene i dati relativi a 150 iris, appartenenti a 3 diversi tipi: a 3 diversi tipi: Iris setosaIris setosa, , Iris versicolorIris versicolor ed ed Iris virginicaIris virginica, , descrivendone le caratteristiche in termini di larghezza e descrivendone le caratteristiche in termini di larghezza e lunghezza di foglie e petali (in cm)lunghezza di foglie e petali (in cm)

Iris setosa Iris versicolor Iris virginicaIris setosa Iris versicolor Iris virginica


Esempio: IRIS dataset Esempio: IRIS dataset 2 2

Per semplicità, si considerano solo i due attributi che Per semplicità, si considerano solo i due attributi che portano maggior informazione riguardo alla classe di portano maggior informazione riguardo alla classe di appartenenza: la lunghezza e la larghezza del petalo appartenenza: la lunghezza e la larghezza del petalo

La distribuzione dei dati èLa distribuzione dei dati è


Esempio: IRIS dataset Esempio: IRIS dataset 3 3

RBF (RBF (=1.0, =1.0, CC==)) Polinomiale (grado 2, Polinomiale (grado 2, CC=10)=10)

OVERFITTING!OVERFITTING!

SVM lineareSVM lineare

Le classi Le classi setosasetosa e e versicolor versicolor vengono vengono separate facilmente da separate facilmente da un classificatore lineareun classificatore lineare

Polinomiale (grado 2, Polinomiale (grado 2, CC==)) Polinomiale (grado 10, Polinomiale (grado 10, CC==))

CC==: non si accettano : non si accettano errorierrori


Conclusioni Conclusioni 1 1Il perceptron è lo strumento più semplice per costruire un classificatoreIl perceptron è lo strumento più semplice per costruire un classificatore

Problemi: uso inefficiente dei dati, overfitting, mancanza di Problemi: uso inefficiente dei dati, overfitting, mancanza di espressivitàespressività

Le SVM risolvono questi problemi, mediante l’utilizzo di margini e di Le SVM risolvono questi problemi, mediante l’utilizzo di margini e di tecniche di tecniche di feature expansionfeature expansion

Per realizzare l’espansione dello spazio di input con un carico Per realizzare l’espansione dello spazio di input con un carico computazionale accettabile si ricorre al trucco della definizione dei computazionale accettabile si ricorre al trucco della definizione dei kernelkernel

La presenza del kernel evita calcoli onerosi di prodotti scalari fra La presenza del kernel evita calcoli onerosi di prodotti scalari fra vettori ad alta dimensionalità (grazie all’uso dei moltiplicatori di vettori ad alta dimensionalità (grazie all’uso dei moltiplicatori di Lagrange ed al Representer Theorem)Lagrange ed al Representer Theorem)


Conclusioni Conclusioni 2 2

Le SVM sono diventate popolari perché capaci di Le SVM sono diventate popolari perché capaci di apprendere dataset “difficili”, con buone prestazioni in apprendere dataset “difficili”, con buone prestazioni in generalizzazionegeneralizzazione

Le SVM sono attualmente fra i migliori classificatori in una Le SVM sono attualmente fra i migliori classificatori in una varietà di problemi (es. varietà di problemi (es. cclassificazione di testi e genomica)lassificazione di testi e genomica)

Il tuning dei parametri nelle SVM è un’Il tuning dei parametri nelle SVM è un’artearte: la selezione di : la selezione di uno specifico kernel e dei relativi parametri viene eseguita in uno specifico kernel e dei relativi parametri viene eseguita in modo empirico (modo empirico (ttrialrialandanderrorerror))


Software onSoftware online e bibliografialine e bibliografia

SVMLight: http://svmlight.joachims.org (in C)SVMLight: http://svmlight.joachims.org (in C)

SVMFu: http://five-percent-nation.mit.edu/SvmFu/ (in C++)SVMFu: http://five-percent-nation.mit.edu/SvmFu/ (in C++)

SVMTorch: http://www.idiap.ch/learning/SVMTorch.html (in C++)SVMTorch: http://www.idiap.ch/learning/SVMTorch.html (in C++)

SVMToolbox: http://theoval.sys.uea.ac.uk/~gcc/svm/toolbox/SVMToolbox: http://theoval.sys.uea.ac.uk/~gcc/svm/toolbox/

B. B. Boser, I. M. Guyon, V. N. Vapnik, B. B. Boser, I. M. Guyon, V. N. Vapnik, A training algorithm for optimal margin A training algorithm for optimal margin classifiersclassifiers, Proc. of the 5, Proc. of the 5thth Workshop on Computational Learning Theory, 1992. Workshop on Computational Learning Theory, 1992.

C. Cortes and V. N. Vapnik, C. Cortes and V. N. Vapnik, Support vector networksSupport vector networks, Machine Learning, 20, pp. , Machine Learning, 20, pp. 1125, 199525, 1995

V. N. Vapnik, V. N. Vapnik, Statistical learning theoryStatistical learning theory. Wiley and Sons, 1998. Wiley and Sons, 1998

M. Pontil and A. Verri, M. Pontil and A. Verri, Properties of Support Vector MachinesProperties of Support Vector Machines, Neural , Neural Computation, 10(4), pp. 955Computation, 10(4), pp. 955974, 1998974, 1998

C.J.C. Burges, A C.J.C. Burges, A tutorial on support vector machines for pattern recognition,tutorial on support vector machines for pattern recognition, Data Data Mining and Knowledge Discovery, 2(2):955Mining and Knowledge Discovery, 2(2):955974, 1998. 974, 1998. http://citeseer.nj.nec.com/burges98tutorial.htmlhttp://citeseer.nj.nec.com/burges98tutorial.html

Valutazione della classificazioneValutazione della classificazione


Confusion tableConfusion table Si costruisce una tabella con k righe e k colonne, dove k è il Si costruisce una tabella con k righe e k colonne, dove k è il

numero delle classi:numero delle classi: Le righe indicano le classi originaliLe righe indicano le classi originali Le colonne indicano le classi predetteLe colonne indicano le classi predette Ogni elemento della tabella aOgni elemento della tabella aijij rappresenta il numero di esempi appartenenti rappresenta il numero di esempi appartenenti

alla classe Calla classe Cii classificati dal modello nella classe C classificati dal modello nella classe Cjj


Confusion tableConfusion table

Dalla confusion table è possibile individuare tre tipi di Dalla confusion table è possibile individuare tre tipi di valori:valori: Veri positivi: Veri positivi: elementi classificati correttamente. Corrisponde elementi classificati correttamente. Corrisponde

agli elementi sulla diagonale della confusion table:agli elementi sulla diagonale della confusion table:

Falsi positivi: Falsi positivi: elementi classificati nella classe j sbagliandoelementi classificati nella classe j sbagliando


Confusion tableConfusion table Falsi negativi: Falsi negativi: elementi che dovrebbero appartenere alla classe elementi che dovrebbero appartenere alla classe

j , ma che non vi sono stati assegnati dal classificatorej , ma che non vi sono stati assegnati dal classificatore

Veri negativi: Veri negativi: elementi che giustamente non sono stati elementi che giustamente non sono stati assegnati alla classe jassegnati alla classe j


Micro e Macro averagingMicro e Macro averaging I valori elencati precedentemente sono utilizzati per calcolare una I valori elencati precedentemente sono utilizzati per calcolare una

misura di qualità della classificazionemisura di qualità della classificazione Accuracy, Precision e RecallAccuracy, Precision e Recall

Tali valori possono essere calcolati in due modi:Tali valori possono essere calcolati in due modi: Macro-Average:Macro-Average: la misura globale è ottenuta mediando i valori calcolati la misura globale è ottenuta mediando i valori calcolati

per ogni classeper ogni classe Micro-Average:Micro-Average: la misura delle prestazioni è ottenuta calcolando i valori di 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 TP,FP,TN e FN globali (somme per i rispettivi valori di ogni classe) e poi applicando la formula di calcoloapplicando la formula di calcolo


1. Accuracy1. Accuracy Misura l’accuratezza del classificatore, ossia il numero di risultati Misura l’accuratezza del classificatore, ossia il numero di risultati

corretti rispetto al numero possibile di risultati corretti. corretti rispetto al numero possibile di risultati corretti.

NB: tra i risultati corretti sono inseriti anche i TNNB: tra i risultati corretti sono inseriti anche i TN


2. Precision e Recall2. Precision e Recall Precision e Recall sono due misure di prestazioni che derivano Precision e Recall sono due misure di prestazioni che derivano

dalla teoria dell’Information Retrievaldalla teoria dell’Information Retrieval

La Precision misura la percentuale di risposte giuste del sistema La Precision misura la percentuale di risposte giuste del sistema rispetto al numero totale di risultati che il sistema stesso ha rispetto al numero totale di risultati che il sistema stesso ha ritornato:ritornato: Quanto di quello che il classificatore ha inserito nella classe è corretto, la Quanto di quello che il classificatore ha inserito nella classe è corretto, la

precisione dei risultati, quanto fidarsi dei risultati ottenutiprecisione dei risultati, quanto fidarsi dei risultati ottenuti

La recall, invece, indica la percentuale di esempi originariamente La recall, invece, indica la percentuale di esempi originariamente nella classe che invece non sono stati classificati bene:nella classe che invece non sono stati classificati bene: Quanto il classificatore ha “lasciato” fuori dalla classificazioneQuanto il classificatore ha “lasciato” fuori dalla classificazione


Precision e RecallPrecision e Recall


F1 e Breakeven-pointF1 e Breakeven-point Nessuna delle due misure viste prima (Pr e Re) hanno un senso Nessuna delle due misure viste prima (Pr e Re) hanno un senso

senza l’altra.senza l’altra.

Diversi metodi per comporre i due valori in una misura unica di Diversi metodi per comporre i due valori in una misura unica di prestazioni sono stati propostiprestazioni sono stati proposti F1F1, ossia la media armonica di essi:, ossia la media armonica di essi:

Breakeven-point:Breakeven-point: variare la soglia di classificazione/reject fino a trovare il variare la soglia di classificazione/reject fino a trovare il punto in cui Pr=Re. Aumentando la soglia di rejection, aumentiamo la Pr e punto in cui Pr=Re. Aumentando la soglia di rejection, aumentiamo la Pr e diminuiamo la Re (accettare poco ma classificato con molta precisione). diminuiamo la Re (accettare poco ma classificato con molta precisione). Viceversa se invece abbassiamo la soglia (accettiamo tutto, ma con bassa Viceversa se invece abbassiamo la soglia (accettiamo tutto, ma con bassa precisione).precisione).

NB: la F1 è massimizzata quando Pr=Re, ossia proprio al NB: la F1 è massimizzata quando Pr=Re, ossia proprio al breakeven-pointbreakeven-point


ConclusioniConclusioni E’ stata data una formalizzazione del problema di classificazione E’ stata data una formalizzazione del problema di classificazione

automatica:automatica: Task supervisionatoTask supervisionato

Sono stati illustrati i modelli più comunemente utilizzati nella Sono stati illustrati i modelli più comunemente utilizzati nella classificazione automatica di pattern vettoriali:classificazione automatica di pattern vettoriali: RegoleRegole ProbabilisticiProbabilistici Profile/Example-BasedProfile/Example-Based ANNANN SVMSVM

Inoltre sono state illustrate le misure utilizzate comunemente per Inoltre sono state illustrate le misure utilizzate comunemente per misurare le prestazioni di un classificatoremisurare le prestazioni di un classificatore

Sistemi di supporto alle decisioni 3. Classificazione Ing. Leonardo Rigutini, Ph.D. Dipartimento di...

Documents

Transcript of Sistemi di supporto alle decisioni 3. Classificazione Ing. Leonardo Rigutini, Ph.D. Dipartimento di...