L'idea centrale dietro SGD

Sep 30 2020

Pr. Hinton nel suo popolare corso su Coursera si riferisce al fatto seguente :

Rprop non funziona davvero quando abbiamo set di dati molto grandi e dobbiamo eseguire aggiornamenti di pesi mini-batch. Perché non funziona con i mini-batch? Ebbene, le persone l'hanno provato, ma è stato difficile farlo funzionare. Il motivo per cui non funziona è che viola l'idea centrale alla base della discesa del gradiente stocastico , che è quando abbiamo un tasso di apprendimento abbastanza piccolo, calcola la media dei gradienti sui mini-batch successivi. Considera il peso, che ottiene il gradiente di 0,1 su nove mini-batch e il gradiente di -0,9 su decimi di mini-batch. Quello che vorremmo è che quei gradienti si annullino a vicenda, in modo che rimangano più o meno gli stessi. Ma non è quello che succede con rprop. Con rprop, aumentiamo il peso di 9 volte e lo diminuiamo solo una volta, quindi il peso cresce molto più grande.

Come puoi vedere, l'idea centrale alla base di SGD è che i gradienti successivi nei mini-batch dovrebbero essere mediati. Qualcuno ha una fonte formale valida per questo? c'è qualche giustificazione? Finora non ho riscontrato alcuna prova.

Risposte

2 JavierTG Oct 07 2020 at 04:39

Influenza della distribuzione che genera i dati

Per vedere questo, prima dobbiamo menzionare che, né utilizzando Batch gradiente discendente (utilizzando l'intero set di dati per calcolare il gradiente) né utilizzando mini-batch gradiente discesa, stiamo calcolando il valore vero (esatto) del gradiente.

Per calcolare il vero valore del gradiente dovremmo usare l'insieme di tutti i possibili valori delle caratteristiche, $x$, (e quindi gli output $y$).

Più formalmente, e facendo riferimento alla quantità che vogliamo minimizzare come valore atteso della funzione di perdita per esempio ($J(x,y,\theta)$, dove $\theta$ sono i parametri) rispetto a tutto il possibile $x,y$ valori, il vero gradiente $g$ è dato da: $$g = \frac{\partial}{\partial \theta}\mathbb{E}_{x,y\sim p_{data}}(J(x,y,\theta)) $$E se assumiamo determinate condizioni, abbiamo che:$$g = \mathbb{E}_{x,y\sim p_{data}}\left(\frac{\partial}{\partial \theta}J(x,y,\theta)\right) $$

Dove $p_{data}$è la distribuzione che genera i dati (la distribuzione da cui i valori di$x$ e $y$sono disegnate). Tuttavia, questa distribuzione di generazione di dati di solito è sconosciuta. Conosciamo solo il set di dati che ci viene fornito.

Per questo motivo, per aggiornare i parametri utilizzando tutte le informazioni fornite (il set di addestramento), utilizziamo invece la distribuzione empirica definita dai dati di addestramento ($\hat{p}_{data}$) che mette una probabilità di $1/m$ su ciascuno dei $m$ campioni $(x^{(1)}, y^{(1)}), \,(x^{(2)}, y^{(2)}),\,...\,,(x^{(m)}, y^{(m)})$del set di dati. Quindi il gradiente è approssimato da:$$ \begin{aligned} \hat{g}&=\frac{\partial}{\partial \theta}\mathbb{E}_{x,y\sim \hat{p}_{data}}(J(x,y,\theta))\\&=\frac{\partial}{\partial \theta}\left(\sum_{i=1}^m \frac{1}{m}J_i(x^{(i)},y^{(i)},\theta)\right)\\ &= \frac{1}{m}\sum_{i=1}^m\frac{\partial }{\partial \theta}J_i(x^{(i)},y^{(i)},\theta) \end{aligned} $$ Termina con la discesa del gradiente in batch.

Ma cosa succede con i mini-lotti?

Utilizzando gli aggiornamenti dei mini-bagni, vediamo continuamente nuovi dati (supponendo di calcolare solo un'epoca). Quindi in questo caso, utilizzando mini-batch, stiamo utilizzando la distribuzione che genera i dati.

Ciò significa che su ogni aggiornamento mini-batch, campionando questa distribuzione che genera dati, si ottiene una stima ($\hat{g}$) del vero gradiente ($g$) che è imparziale, ad es $\mathbb{E}_{x,y\sim p_{data}}(\hat{g})=g$. Per vedere questo e considerare$\text{s-sized}$ mini-lotti: $$\begin{aligned} \mathbb{E}_{x,y\sim p_{data}}(\hat{g})&=\mathbb{E}_{x,y\sim p_{data}}\left(\frac{g^{(1)}+...+g^{(s)}}{s}\right)\\ &=\frac{1}{s}(\mathbb{E}_{x,y\sim p_{data}}(g^{(1)}+...+g^{(s)}))\\ &=\frac{1}{s}s\,\,g=g \end{aligned} $$In tal modo, effettuando aggiornamenti mini-batch succesivi tendiamo in media (come mostrato da$\mathbb{E}_{x,y\sim p_{data}}(\hat{g})$) per aggiornare i nostri parametri con il valore reale del gradiente. E questo è ciò a cui penso si riferiscano gli autori nella citazione della domanda.

Grandi referenze:

Libro di Deep Learning, Ian Goodfellow et. al Capitolo 8.1
Risposte da qui

1 cmn Oct 09 2020 at 23:07

In una fase di discesa completa del gradiente, la funzione di perdita è definita come la media del termine di perdita nei singoli punti campione. Per ridurre al minimo la funzione di perdita, è necessario calcolare la media sui singoli gradienti.

Nella discesa del gradiente stocastico, se non vi è alcun bias nella selezione dei lotti, la media sui lotti risulterebbe in una stima imparziale dell'intero gradiente.