Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Roberto Prevete » 10.Discesa del gradiente e backpropagation


Introduzione

Abbiamo detto che il processo di apprendimento consiste nel:

Modificare i pesi e i bias della rete in modo da minimizzare una fissata funzione di errore E(w) sul training set
con il vincolo che anche sul validation set ci sia un errore “piccolo.

Nelle prossime slide mostreremo quale è il processo che ci permette di minimizzare la funzione di errore.

Algoritmi iterativi per minimizzare la funzione di errore

Molti algoritmi di apprendimento hanno una procedura iterativa per minimizzare la funzione di errore, con la determinazione dei valori dei pesi fatta in passi successivi.

Ad ogni passo si possono distinguere due differenti fasi:

  • Nella prima fase, sono calcolate le derivate della funzione d’errore rispetto ai pesi. Un metodo computazionale molto efficiente per il calcolo di tali derivate è la back-propagation.
  • Nella seconda fase, le derivate sono usate per calcolare i nuovi pesi della rete.

La più semplice di tale tecniche è detta discesa del gradiente (Rumelhart, 1986).

Algoritmi iterativi per minimizzare la funzione di errore (segue)

E’ fondamentale sottolineare che le due fasi sono distinte. Si procede, cioè, ad ogni passo del processo iterativo:

  • Prima, con il calcolo della derivata della funzione di errore, ∂E /∂wji, sulla base del training set
  • Dopo, si realizza una variazione del generico peso wji, con un qualche formula di aggiornamento. Ad esempio nel caso della classica discesa del gradiente
    wji= wji -η∂ E /∂ wji
    con η coefficiente costante in genere compreso tra 0 e 1.

Calcolo delle derivate della funzione di errore

Calcolo delle derivate della funzione di errore ∂E /∂wji: Back Propagation (1)

Vediamo, ora, come calcolare ∂E /∂wji utilizzando gli stessi valori di output dei nodi della rete.

Ricordo, innanzitutto, che in una rete feed-forward ciascun nodo j computa una somma pesata dei suoi input

aj= ∑iwji* zi

dove zi è l’output di un nodo il quale invia una connessione al nodo j.

Con valore di output del nodo j dato da:

zj=g(aj)

dove con g indichiamo la funzione di output.

Calcolo delle derivate della funzione di errore (segue)

Calcolo delle derivate della funzione di errore ∂E /∂wji: Back Propagation (2)

Per calcolare ∂E/∂wji , dato che E=∑nEn, possiamo focalizzare la nostra attenzione sul calcolo di

∂En/∂wji.

Una prima ipotesi necessaria per calcolare le derivate parziali della funzione di errore rispetto a i pesi è la seguente:

Supponiamo che En possa essere espresso come funzione differenziabile delle variabili d’output.

Calcolo delle derivate della funzione di errore (segue)

Calcolo delle derivate della funzione di errore ∂E /∂wji: Back Propagation (3)

Dato una coppia (xn, tn) del training set, supponiamo di dare in input alla rete xn e di calcolre le attivazioni di tutti i nodi interni e dei nodi d’output, per successive applicazioni di

aj= ∑iwji* zi e zj=g(aj) (come visto, in questo caso, si ha una forward-propagation).

Per calcolare (∂En/∂wji) osserviamo che En dipende da wji attraverso aj. Si può dimostrare allora che:

(∂En /∂wji)=δj zi dove δj=(∂ En /∂aj)

Calcolo delle derivate della funzione di errore (segue)

Calcolo delle derivate della funzione di errore ∂E /∂wji: Back Propagation (4)

L’equazione (∂En /∂wji)=δj zi ci dice che:

la derivata richiesta è ottenuto semplicemente moltiplicando il valore di output del nodo allo “start” della connessione associata al peso wji per un certo valore δj associato al nodo alla fine della connessione con peso wji

Osserviamo che, quindi, la derivata della funzione di errore rispetto al peso della connessione che va dal nodo i al nodo j è calcolato tramite una formula locale.

Calcolo delle derivate della funzione di errore (segue)

Calcolo dei delta

Come calcolare i δj?

Per le unità di output si ha:

  • δk=(∂ En /∂ak)= g’(ak) (∂ En /∂yk)

Per le restanti unità:

  • δj=(∂ En /∂aj)=g’(aj)∑kwkj* δk
Calcolo della derivata parziale della funzione di errore rispetto ad un peso tramite back-propagation.

Calcolo della derivata parziale della funzione di errore rispetto ad un peso tramite back-propagation.


Calcolo delle derivate della funzione di errore (segue)

Nota bene.

Si ha, quindi, una formula ricorsiva tramite la quale a partire dalle nodi “più esterni” (i nodi di output) possiamo “risalire”, in maniera inversa alla forward-propagation delle attivazioni dei nodi, al valore δj di tutti i nodi, da qui il nome di back-propagation.

Calcolo delle derivate della funzione di errore (segue)

Calcolo delle derivate della funzione di errore ∂E /∂wji: Riassumendo

Possiamo riassumere la back-propagation per valutare le derivate della funzione di errore En , rispetto ai pesi, in quattro fasi:

  • Applicare un vettore di input (pattern) xn alla rete provocando una propagazione in avanti (forward propagation).
  • Calcolare i δk=(∂ En/∂ak) per i nodi di output, dove ak è l’input del nodo k di output.
  • Calcolare tutti gli altri δj utilizzando la formula δj = g’(aj)∑kwkj* δk, cioè propagando all’indietro il valore dei δ.
  • Calcolare le derivate richieste utilizzando (∂En/∂wji)=δjzi

Aggiornamento dei pesi

Batch e on-line learning

Le derivate rispetto all’intera funzione di errore allora sono date da

(∂E/∂wji) = ∑n (∂En/∂wji)

Su tale sommatoria, però, sono da fare alcune osservazioni legate al “tempo” in cui aggiorniamo i pesi. L’aggiornamento dei pesi può procedere in due modi:

  • On-line learning.
  • Batch learning.

Aggiornamento dei pesi (segue)

On-line learning

I pesi vengono aggiornati dopo che ciascun pattern xn è presentato alla rete e sono calcolate le derivate di En, cioè Δwji = -ηδj zi.

In questo caso la rete “cambia” ad ogni presentazione di un pattern e l’errore totale

E=∑n En

deve essere calcolato al termine di un “ciclo” di addestramento, cioè dopo che sono stati modificati i pesi e i bias per tutti gli elementi del training set.

Aggiornamento dei pesi (segue)

Batch learning

I pesi vengono aggiornati dopo che sono state calcolate le derivate della funzione di errore totale E (cioè della funzione di errore relativo a tutto il training set), si ha allora un aggiustamento di pesi dato da

Δwji = -η∑nδjn zin

Quindi il valore di (∂E/∂wji)=∑n (∂En/∂wji) cambia a seconda se operiamo un on-line learning o un batch learning.

Vantaggi della back-propagation

Quale è il vantaggio di utilizzare la back-propagation per calcolare le derivate della funzione di errore?

  • Supponiamo di avere una rete con W pesi.
  • Se scriviamo esplicitamente le formule delle derivate della funzione di errore e poi calcoliamo numericamente tale derivate (derivate alle differenze finite), il calcolo di tali derivate richiede un complessità computazionale pari a O(W2) per ogni input
  • Utilizzando la back-propagation, invece, si ha una complessità computazionale pari a O(W) per ogni input.

Vantaggi della back-propagation (segue)

Calcolo tempi computazionali nel caso delle derivate alle differenze finite.

In questo caso dobbiamo calcolare E(wji +Δwji) – E(wji) per tutti W pesi della rete.

Quindi per ciascun variazione di peso, wji +Δwji, dobbiamo calcolare una nuova risposta della rete.

Dato che per il calcolo della propagazione in avanti di una rete con W pesi, abbiamo un tempo di calcolo pari a O(W)

Per fare tale calcolo per tutte le variazioni dei pesi, otteniamo

O(W2)

Vantaggi della back-propagation (segue)

Calcolo tempi computazionali nel caso della back-propagation.

In questo caso dobbiamo calcolare una unica propagazione in avanti, e quindi tempi di calcolo pari a: O(W)

Quindi applicare la formula δj = g’(aj)∑kwkj* δk . Quindi ancora temi di calcolo paria a: O(W)

Infine applicare la formula (∂En/∂wji)=δjzi . Quindi ancora tempi di calcolo pari a: O(W)

Allora, nel complesso abbimo tempi di calcolo pari a: O(W)

Vantaggi della back-propagation (segue)

La back-propagation risulta, allora, una tecnica per il calcolo della derivata della funzione di errore rispetto ai pesi che permette un drastico guadagno da un punto di vista della complessità computazionale.

Prossime lezioni

Nella prossima lezione daremo la dimostrazione di:

la formula (∂En /∂wji)=δj zi

Quelle per il calcolo dei δj.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion