BIOINGEGNERIA S. Salinari Lezione 4. Problemi di Regressione e Classificazione Problemi di...

BIOINGEGNERIA

S. Salinari

Lezione 4

Problemi di Regressione e Classificazione

Problemi di regressione: Determinazione dei parametri di una funzione che lega gli insiemi di ingresso ed uscita (previsione)

Problemi di classificazione: Associazione di un ingresso ad una determinata classe (riconoscimento e diagnostica)

DIFFICOLTA’

Elevata dimensione dei datiApproccio manuale- Ad esempio: Caratteristiche morfologiche

ESTRAZIONE DI CARATTERISTICHE

Approccio automatico- Ad esempio: Componenti significative dello spettro

Dati non separabili

I dati di ingresso appartenenti alle varie classi possono non essere separabili


Entrambi i problemi possono essere visti come problemi di APPROSSIMAZIONE DI FUNZIONI.

Nella regressione si vuole approssimare la funzione che lega i dati ingresso-uscita

Nella classificazione si vuole approssimare la probabilità di appartenenza a varie classi espressa come funzione dell’ingresso


REGRESSIONE Algoritmo LMS (Least Mean Square)

y

x1

x2

xn

w1

w2

wn

x = [x1 x2.....xn]T

w = [w1 w2.....wn] T

Fornisce una regola per la determinazione dei pesi w nella regressione lineare:

cosxwxwy Tn

i

xw ii 1

Se ||x|| =1 y = ||w|| cos

x1

x2

x

w

||w|| ||x|| cos


REGRESSIONE Algoritmo LMS - Regola di variazione dei pesi

Si presuppone di avere un insieme di addestramento, cioè un certo numero di coppie ingresso-uscita:

La regola di aggiornamento dei pesi è:

w = (y i* - yi)xi

dove xi i-esimo ingresso dell’insieme di addestramento, y uscita corrispondente all’ingresso xi e ai pesi w, y*i uscita desiderata.

Per rendere l’algoritmo robusto si può usare:

w = (y i* - yi)xi 0 ≤ 2

Se ||x||1 0 2 /||x||

1211 x yxxxyx iin

iiM

iii .........


REGRESSIONE Algoritmo LMS

Si mostrano i primi due passi dell’aggiornamento di w. =1

x1

x2

x (2)

x (1)

w*

x2

x1

x (1)

y* (2)

y* (1)

y *(1)w (0)

w

w (1)x (2)

y *(2)

w

w (2)

w (1)

Passo 1Passo 2


REGRESSIONE Algoritmo LMS

•In generale può non esistere nessun w* per cui, i, la proiezione di w* su xi sia uguale a y i* .

•La soluzione w* è quella che minimizza la somma dei quadrati delle distanze, per ogni xi dai rispettivi iperpiani soluzione. L’algoritmo LMS individua quindi la “migliore retta” passante per l’origine che descrive l’andamento dei dati.

•Se si vuole che la retta di regressione non passi per l’origine si può considerare un vettore w = [b w1 w2 ……wn] e x = [1 x1 x2 ……xn]. In questo caso si ottiene:

•Si possono utilizzare anche funzioni di regressioni diverse. Ad es. La regressione polinomiale:

y = b + w1z + w2z2 + ....... + wnzn

•I dati d’ingresso debbono essere molto maggiori dei parametri da determinare

xwby Tn

i

ii xw1


Il Percettrone

E’ la più elementare rete neurale:non si hanno connessioni fra gli ingressi, non si hanno strati intermedi, non si hanno cammini indietro (rete feed-forward)

Si consideri per semplicità una sola uscita corrispondente ad una funzione Booleana 0,1. Ad esempio l’ingresso può corrispondere a dati diagnostici relativi ad un paziente e l’uscita alla classificazione Sano = 0, Malato = 1.

Si assume come funzione di attivazione (funzione f: Rn [0,1]) la funzione di Heaviside con soglia:

wTx- ≥ 0 y=1 wTx- 0 y=0

x1

x2

xn

-1

y {0,1}

w1

w2

wn

x = [x1 x2.....xn]T

w = [w1 w2.....wn] T


REGOLA DI APPRENDIMENTO

1. Si fissano i pesi iniziali w in modo arbitrario

2. Si sceglie un elemento nell’insieme xk C1( y=0)C2( y=1) di apprendimento.

3. Se xk viene classificato correttamente (cioè l’uscita della rete corrisponde alla yk dell’insieme di apprendimento) si lasciano i pesi w invariati

4. Altrimenti si pone:21

121 C come toclassifica vieneC se

C come toclassifica vieneC se

xw

xww

k

kk

Teorema di convergenza: Comunque si scelgano i pesi iniziali w se le classi C1 e C2 sono linearmente separabili la procedura di apprendimento termina in un numero finito di passi.


ESEMPIO

Come esempio consideriamo un percettrone che deve realizzare le funzioni logiche di AND OR ed EXOR. Di queste tre funzioni due (AND e OR) danno origine a classi linearmente separabili ed una no.

Il indica che l’uscita è pari ad 1 per l’ingresso indicato fra parentesi.

Si può immediatamente osservare che le uscite della funzione AND e OR sono linearmente separabili mentre ciò non avviene per l’EXOR

(0,1)

(0,0) (1,0)

(1,1)

(0,0) (1,0)

(1,1)

(0,0) (1,0)

(1,1)(0,1)(0,1)


ESEMPIO

Si può dimostrare che il percettrone non permette di realizzare la funzione EXOR. Infatti supponiamo di vor calcolare i pesi w1 e w2 imponendo le uscite dell’EXOR

H(x) funzione di Heaviside =0 se x<0 e =1 se x>0.

x1=0, x2=0 w1·0 + w2·0 - ·1 = - <0 H(0.0) = 0

x1=1, x2=1 w1·1 + w2·1 - ·1 = w1 +w2- <0 H(1.1) = 0

x1=1, x2=0 w1·1 + w2·0 - ·1 = w1->0 H(1.0) = 1

x1=0, x2=1 w1·0 + w2·1 - ·1 = w2- >0 H(0.1) = 1

Si ottiene quindi: 2 <w1+w2 < assurdo poichè >0

x1

x2

-1

w1

w2

H(w1x1+ w2x2-)

w1+w2-2 >0


ESEMPIO

Per superare la limitazione dovuta alla necessità di separabilità delle classi si introduce il percettrone generalizzato in cui vengono introdotti gli strati nascosti

Le connessioni sono unidirezionali

Non ci sono connessioni tra gli ingressi

I pesi vengono trovati minimizzando l’errore (uscita desiderata meno uscita attuale)

Non è garantita la convergenza

-1 -1

x1

x2 H1 H2

y

1.5 0.5

1

1-21

1

REALIZZAZIONE DELL’EXOR

x =(0,0) H1=H(1·0+1·0-1·1.5)<00 H2=H(1·0+1·0-2·0-1·0.5) <0 0

x =(1,0) H1=H(1·1+1·0-1·1.5)<00 H2=H(1·1+1·0-2·0-1·0.5) >0 1

x =(0,1) H1=H(1·0+1·1-1·1.5)<00 H2=H(1·0+1·1-2·0-1·0.5) >0 1

x =(1,1) H1=H(1·1+1·1-1·1.5)>01 H2=H(1·1+1·1-2·1-1·0.5) <0 0

BIOINGEGNERIA S. Salinari Lezione 4. Problemi di Regressione e Classificazione Problemi di...

Documents

Transcript of BIOINGEGNERIA S. Salinari Lezione 4. Problemi di Regressione e Classificazione Problemi di...