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 /∂w_ji, 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
  w_ji= w_ji -η∂ E /∂ w_ji
  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 /∂w_ji: Back Propagation (1)

Vediamo, ora, come calcolare ∂E /∂w_ji 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

a_j= ∑_iw_ji* z_i

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

Con valore di output del nodo j dato da:

z_j=g(a_j)

dove con g indichiamo la funzione di output.

Calcolo delle derivate della funzione di errore (segue)

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

Per calcolare ∂E/∂w_ji , dato che E=∑_nEⁿ, possiamo focalizzare la nostra attenzione sul calcolo di

∂Eⁿ/∂w_ji.

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 /∂w_ji: Back Propagation (3)

Dato una coppia (xⁿ, tⁿ) 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

a_j= ∑_iw_ji* z_i e z_j=g(a_j) (come visto, in questo caso, si ha una forward-propagation).

Per calcolare (∂Eⁿ/∂w_ji) osserviamo che Eⁿ dipende da w_ji attraverso aj. Si può dimostrare allora che:

(∂Eⁿ /∂w^ji)=δ_j z_i dove δ_j=(∂ Eⁿ /∂a_j)

Calcolo delle derivate della funzione di errore (segue)

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

L’equazione (∂Eⁿ /∂w_ji)=δ_j zi ci dice che:

la derivata richiesta è ottenuto semplicemente moltiplicando il valore di output del nodo allo “start” della connessione associata al peso w_ji 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)

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 /∂w_ji: Riassumendo

Possiamo riassumere la back-propagation per valutare le derivate della funzione di errore Eⁿ , 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=(∂ Eⁿ/∂a_k) per i nodi di output, dove a_k è l’input del nodo k di output.
• Calcolare tutti gli altri δ_j utilizzando la formula δ_j = g’(a_j)∑_kw_kj* δ_k, cioè propagando all’indietro il valore dei δ.
• Calcolare le derivate richieste utilizzando (∂Eⁿ/∂w_ji)=δ_jz_i

Aggiornamento dei pesi

Batch e on-line learning

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

(∂E/∂w_ji) = ∑n (∂Eⁿ/∂w_ji)

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è Δw_ji = -ηδ_j z_i.

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

E=∑_n Eⁿ

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

Δw^ji = -η∑_nδ_jn z_iⁿ

Quindi il valore di (∂E/∂w_ji)=∑_n (∂Eⁿ/∂w_ji) 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(W²) 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(w_ji +Δw_ji) – E(w_ji) per tutti W pesi della rete.

Quindi per ciascun variazione di peso, w_ji +Δw_ji, 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(W²)

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’(a_j)∑_kw_kj* δ_k . Quindi ancora temi di calcolo paria a: O(W)

Infine applicare la formula (∂Eⁿ/∂w_ji)=δ_jz_i . 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 (∂Eⁿ /∂w_ji)=δ_j z_i

Quelle per il calcolo dei δ_j.