Apprendimento di Widrow-Hoff

L’apprendimento di Widrow-Hoff è un’approssimazione dell’algoritmo steepest descent nel quale come indice di performance viene utilizzato l’errore quadratico medio. Questo metodo di apprendimento è molto importante in quanto si pone come precursore dell’algoritmo di backpropagation per le reti multistrato che verrà presentato nel prossimo paragrafo. Questo tipo di apprendimento è stato ideato da Bernard Widrow e Marcian Hoff alla metà del secolo scorso: questi studiosi hanno introdotto la cosiddetta rete ADALINE (ADaptive Linear NEuron) e la regola di apprendimento che hanno chiamato algoritmo LMS (Least Mean Square). Questa rete neurale è molto simile al percettrone visto in precedenza, con l’unica differenza data dal fatto che la funzione di trasferimento è lineare anziché di tipo hard limit. Per questo motivo ha lo stesso, grande, punto di debolezza, ovvero non riesce a risolvere problemi non separabili linearmente. Nonostante ciò l’algoritmo LMS è molto più potente della perceptron learning rule in quanto minimizzando

15 _{La derivata direzionale è infatti data da} 𝑝𝑇𝛻𝐹(𝑥)

‖𝑝‖ .Dato che al numeratore si ha un prodotto tra vettori,

esso assumerà valore 0 quando il vettore di direzione sarà ortogonale al gradiente e assumerà valore massimo quando il vettore di direzione è lo stesso del gradiente.

42

l’errore quadratico medio muove il confine decisionale più lontano possibile dai punti con i quali è stata allenata la rete, evitando che la rete risultante sia troppo sensibile al rumore (il perceptron è molto sensibile al rumore, cioè crea problemi quando i pattern con i quali è stata allenata la rete sono molto vicini al confine decisionale).

La rete ADALINE è rappresentata nella figura seguente16_:

Sebbene gli output della rete siano dati dal vettore:

𝑎 = 𝑝𝑢𝑟𝑒𝑙𝑖𝑛(𝑊𝑝 + 𝑏) = 𝑊𝑝 + 𝑏

risulta spesso utile, come esposto nel caso del perceptron, andare ad identificare il singolo output, che in questo caso è dato da:

𝑎_𝑖 = 𝑝𝑢𝑟𝑒𝑙𝑖𝑛(𝑛_𝑖) = 𝑝𝑢𝑟𝑒𝑙𝑖𝑛( 𝑤_𝑖 𝑇_{𝑝 + 𝑏}

𝑖) = 𝑤𝑖 𝑇𝑝 + 𝑏𝑖

dove come in precedenza _𝑖𝑤𝑇 non è altro che la i-esima riga della matrice dei pesi W. A questo punto, prima di spiegare nel dettaglio il funzionamento dell’algoritmo di apprendimento LMS (che come la regola di apprendimento del percettrone è un tipo di apprendimento supervisionato nella quale alla rete vengono forniti gli input e i corrispondenti target da comparare poi con gli output della rete) è necessario soffermarsi su quella che è la particolarità che lo differenzia dalla regola di apprendimento del percettrone: l’errore quadratico medio. Tramite questo algoritmo infatti i parametri fondamentali della rete ADALINE vengono aggiustati in modo da minimizzare l’errore quadratico medio. Nel caso in cui questa rete abbia un singolo neurone, è possibile, al fine di indagare meglio le caratteristiche

16 _{Hagan M. T., Debuth H. B., Beale M.H., De Jeus O., 2014. Neural Network Design, 2nd edition, cap.}

43

di questo indice di performance, raggruppare tutti i parametri da aggiustare in un unico vettore x:

𝑥 = [ 𝑤1

𝑏 ]

e includere l’input “1” del bias nel vettore degli input z: 𝑧 = [𝑝_1]

Adesso l’output della rete, che in questo caso sarà uno scalare e che generalmente è dato da:

𝑎 = 𝑤1 𝑇𝑝 + 𝑏

può essere riscritto come:

𝑎 = 𝑥𝑇_𝑧

A questo punto è possibile esprimere l’errore quadratico medio della rete ADALINE come:

𝐹(𝑥) = 𝐸[𝑒2_{] = 𝐸[(𝑡 − 𝑎)}2_{] = 𝐸[(𝑡 − 𝑥}𝑇_𝑧)2_]

che, scritto in forma estesa risulta:

𝐹(𝑥) = 𝐸[𝑡2_{− 2𝑡𝑥}𝑇_{𝑧 + 𝑥}𝑇_𝑧𝑧𝑇_{𝑥] = 𝐸[𝑡}2_{] − 2𝑥}𝑇_{𝐸[𝑡𝑧] + 𝑥}𝑇_{𝐸[𝑧𝑧}𝑇_]𝑥

Ponendo ora 𝑐 = 𝐸[𝑡2] , ℎ = 𝐸[𝑡𝑧] e 𝑅 = 𝐸[𝑧𝑧𝑇]17 è possibile riscrivere l’equazione nel modo seguente:

𝐹(𝑥) = 𝑐 − 2𝑥𝑇_{ℎ + 𝑥}𝑇_𝑅𝑥

Si nota facilmente come quest’ultima equazione sia una funzione di tipo quadratico dove 𝑑 = −2ℎ e 𝐴 = 2𝑅. Questo è un risultato molto importante in quanto come esposto nel paragrafo 2.4 le caratteristiche di una funzione di tipo quadratico dipendono essenzialmente dalla matrice Hessiana A, che in questo caso è data dal doppio della matrice di correlazione R. Essendo possibile dimostrare che tutte le

17 _{Il vettore h è il vettore di correlazione incrociata tra il vettore degli input e quello dei target mentre la}

44

matrici di correlazione sono definite positive o semi-definite positive (ovvero non possono mai avere autovalori negativi), rimangono solo due possibilità: se R ha solo autovalori positivi allora la F(x) avrà un unico minimo globale; se invece R ha qualche autovalore uguale a zero la F(x) potrà sia avere un minimo debole, sia non avere un minimo (e ciò dipenderà dal vettore d). A questo punto, volendo calcolare il punto stazionario dell’indice di performance dato dalla funzione quadratica e sapendo dal paragrafo 2.4 che esso si trova nel punto in corrispondenza del quale il gradiente della funzione è uguale a zero, si avrà:

𝛻𝐹(𝑥) = 𝑑 + 𝐴𝑥 = −2ℎ + 2𝑅𝑥 −2ℎ + 2𝑅𝑥 = 0

Perciò se la matrice R è definita positiva avrà un unico punto stazionario, che sarà anche un minimo locale, in corrispondenza del punto:

𝑥∗ _{= 𝑅}−1_ℎ

Passando ora all’algoritmo LMS, il cui obiettivo è ovviamente quello di localizzare il punto di minimo della funzione F(x), appare superfluo specificare come avendo a disposizione l’inversa di R e h sarebbe possibile calcolare il punto di minimo direttamente dall'equazione precedente. In genere tuttavia non è conveniente calcolare la matrice di correlazione R e il vettore h, e per questo si utilizza un’approssimazione dell’algoritmo steepest descent nel quale il gradiente è sostituito con un gradiente stimato. Il punto di svolta nel lavoro di Widrow e Hoff è proprio questo, ovvero stimare l’errore quadratico medio F(x) come:

𝐹̂(𝑥) = (𝑡(𝑘) − 𝑎(𝑘))2 = 𝑒2_(𝑘)

In questo caso si può notare come l’aspettativa E sull’errore quadratico sia stata sostituita dai due autori con l’errore quadratico all’iterazione k. Ad ogni iterazione quindi il gradiente sarà un gradiente stimato, nella forma:

45

I primi R elementi di questo gradiente saranno le derivate rispetto ai pesi mentre l’elemento R+1 sarà la derivata rispetto al bias, ovvero:

[𝛻𝑒2_(𝑘)] 𝑗 = 𝑑𝑒2_(𝑘) 𝑑𝑤_1,𝑗 = 2𝑒(𝑘) 𝑑𝑒(𝑘) 𝑑𝑤_1,𝑗 𝑝𝑒𝑟 𝑗 = 1, … . 𝑅 e [𝛻𝑒2_(𝑘)] 𝑅+1 = 𝑑𝑒2_(𝑘) 𝑑𝑏 = 2𝑒(𝑘) 𝑑𝑒(𝑘) 𝑑𝑏 18 Considerando le derivate parziali alla fine di queste equazioni si ha:

𝑑𝑒(𝑘) 𝑑𝑤1,𝑗 = 𝑑[𝑡(𝑘) − 𝑎(𝑘)] 𝑑𝑤1,𝑗 = 𝑑 𝑑𝑤1,𝑗[𝑡(𝑘) − ( 𝑤1 𝑇_{𝑝(𝑘) + 𝑏)]} = 𝑑 𝑑𝑤_1,𝑗[𝑡(𝑘) − (∑ 𝑤1,𝑖𝑝𝑖(𝑘) + 𝑏 𝑅 𝑖=1 )]

dove 𝑝𝑖(𝑘) è l’i-esimo elemento del vettore degli input alla k-esima iterazione. Ciò

può essere semplificato come:

𝑑𝑒(𝑘)

𝑑𝑤1,𝑗 = −𝑝𝑗(𝑘)

E allo stesso modo l’elemento R+1 sarà dato da: 𝑑𝑒(𝑘)

𝑑𝑏 = −1

𝑝_𝑗(𝑘) e 1 sono gli elementi del vettore degli input z, e quindi il gradiente dell’errore quadratico all’iterazione k può essere scritto come:

𝛻̂𝐹(𝑥) = 𝛻𝑒2_{(𝑘) = −2𝑒(𝑘)𝑧(𝑘)}

o analogamente, in forma estesa,

18 _{Queste due equazioni, ed in particolare i passaggi} 𝑑𝑒2(𝑘)

𝑑𝑤_1,𝑗 = 2𝑒(𝑘) 𝑑𝑒(𝑘) 𝑑𝑤_1,𝑗 e 𝑑𝑒2(𝑘) 𝑑𝑏 = 2𝑒(𝑘) 𝑑𝑒(𝑘) 𝑑𝑏 sono stati

ottenuti tenendo conto della regola della derivata del prodotto di due funzioni, cioè 𝑑(𝑒(𝑥) ⋅ 𝑒(𝑥)) = 𝑑𝑒(𝑥) ⋅ 𝑒(𝑥) + 𝑒(𝑥) ⋅ 𝑑𝑒(𝑥) = 2𝑒(𝑥) ⋅ 𝑑𝑒(𝑥)

46 𝛻̂𝐹(𝑥) = 𝛻𝑒2_{(𝑘) =} [ −2𝑒(𝑘)𝑝₁(𝑘) −2𝑒(𝑘)𝑝₂(𝑘) ⋮ −2𝑒(𝑘)𝑝_𝑗(𝑘) +2𝑒(𝑘)(−1) ]

Da qui è possibile notare la funzionalità dell’approssimare l’errore quadratico medio con il singolo errore all’iterazione k: in tal modo infatti per calcolare il gradiente approssimato basta semplicemente moltiplicare l’errore per il vettore degli input. A questo punto si utilizza l’approssimazione del gradiente nell’algoritmo steepest descent. Ipotizzando che il tasso di apprendimento sia costante, come visto nel paragrafo 2.5 l’equazione fondamentale dell’algoritmo è:

𝑥_𝑘+1 = 𝑥_𝑘 − 𝛼𝑔_𝑘

Sostituendo il gradiente all’iterazione k con 𝛻̂𝐹(𝑥) si ottiene: 𝑥_𝑘+1 = 𝑥_𝑘+ 2𝛼𝑒(𝑘)𝑧(𝑘) oppure: 𝑤(𝑘 + 1) = 𝑤(𝑘) + 2𝛼𝑒(𝑘)𝑝(𝑘)₁ 1 e 𝑏(𝑘 + 1) = 𝑏(𝑘) + 2𝛼𝑒(𝑘)

Queste equazioni, che formano l’algoritmo LMS (spesso detto anche delta rule), possono poi essere generalizzate nel caso in cui vi siano output multipli, e quindi neuroni multipli. Per far ciò è conveniente scrivere le equazioni di aggiornamento della matrice dei pesi e del vettore dei bias in forma matriciale nel modo seguente:

𝑊(𝑘 + 1) = 𝑊(𝑘) + 2𝛼𝑒(𝑘)𝑝𝑇_(𝑘)

e

𝑏(𝑘 + 1) = 𝑏(𝑘) + 2𝛼𝑒(𝑘) dove b ed e sono adesso dei vettori.

47