Główna idea SGD

Sep 30 2020

Pr. Hinton w swoim popularnym kursie na Coursera odnosi się do następującego faktu :

Rprop tak naprawdę nie działa, gdy mamy bardzo duże zbiory danych i musimy wykonywać aktualizacje wag mini-partii. Dlaczego nie działa z mini-partiami? Cóż, ludzie tego próbowali, ale ciężko im było sprawić, by to działało. Powodem, dla którego to nie działa, jest to, że narusza główną ideę stochastycznego zejścia w gradiencie , która polega na tym, że gdy mamy wystarczająco mały współczynnik uczenia się, uśrednia on gradienty w kolejnych mini-partiach. Rozważ wagę, która daje gradient 0,1 na dziewięciu minipartiach i gradient -0,9 na minipartiach dziesiątych. Chcielibyśmy, aby te gradienty z grubsza znosiły się nawzajem, aby pozostały w przybliżeniu takie same. Ale to nie jest to, co dzieje się z rprop. W przypadku rprop zwiększamy wagę 9-krotnie i zmniejszamy tylko raz, dzięki czemu waga rośnie znacznie.

Jak widać, główną ideą SGD jest to, że należy uśredniać kolejne gradienty w mini partiach. Czy ktoś ma jakieś ważne oficjalne źródło tego? czy jest jakieś uzasadnienie? Do tej pory nie spotkałem się z żadnym dowodem.

Odpowiedzi

2 JavierTG Oct 07 2020 at 04:39

Wpływ dystrybucji danych generujących

Aby to zobaczyć, najpierw musimy wspomnieć, że ani przy użyciu Batch gradient descent (używając całego zestawu danych do obliczenia gradientu), ani używając mini-wsadowego gradientu gradientu, nie obliczamy prawdziwej (dokładnej) wartości gradientu.

Aby obliczyć prawdziwą wartość gradientu, musielibyśmy użyć zbioru wszystkich możliwych wartości cech, $x$, (a tym samym wyjścia $y$).

Bardziej formalnie i odnosząc się do ilości, którą chcemy zminimalizować, jako oczekiwanej wartości funkcji straty na przykładzie ($J(x,y,\theta)$, gdzie $\theta$ są parametrami) z wszystkimi możliwymi parametrami $x,y$ wartości, prawdziwy gradient $g$ jest dany przez: $$g = \frac{\partial}{\partial \theta}\mathbb{E}_{x,y\sim p_{data}}(J(x,y,\theta)) $$A jeśli przyjmiemy pewne warunki, mamy to:$$g = \mathbb{E}_{x,y\sim p_{data}}\left(\frac{\partial}{\partial \theta}J(x,y,\theta)\right) $$

Gdzie $p_{data}$to dystrybucja generująca dane (dystrybucja, z której wartości$x$ i $y$są rysowane). Jednak ta dystrybucja generowania danych jest zwykle nieznana. Po prostu znamy otrzymany zbiór danych.

Z tego powodu, aby zaktualizować parametry przy użyciu wszystkich podanych informacji (zestawu uczącego ), zamiast tego używamy empirycznego podziału zdefiniowanego przez dane uczące ($\hat{p}_{data}$), co daje prawdopodobieństwo $1/m$ na każdym z $m$ próbki $(x^{(1)}, y^{(1)}), \,(x^{(2)}, y^{(2)}),\,...\,,(x^{(m)}, y^{(m)})$zbioru danych. Więc gradient jest przybliżony przez:$$ \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} $$ Kończy się zejściem gradientu wsadowego.

Ale co się dzieje z mini-partiami?

Korzystając z aktualizacji mini-kąpieli, stale widzimy nowe dane (zakładając, że obliczamy tylko jedną epokę). Więc w tym przypadku, używając mini-paczek, używamy dystrybucji generującej dane.

Oznacza to, że przy każdej aktualizacji mini-partii, próbkując tej dystrybucji generującej dane, otrzymujemy oszacowanie ($\hat{g}$) prawdziwego gradientu ($g$), który jest bezstronny, tj $\mathbb{E}_{x,y\sim p_{data}}(\hat{g})=g$. Aby to zobaczyć i zastanowić się$\text{s-sized}$ mini-partie: $$\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} $$W ten sposób, dokonując kolejnych aktualizacji mini-partii, będziemy średnio dążyć (jak pokazano na$\mathbb{E}_{x,y\sim p_{data}}(\hat{g})$) do aktualizacji naszych parametrów o prawdziwą wartość gradientu. I do tego, jak sądzę, autorzy odwołują się w cytowaniu pytania.

Świetne referencje:

Książka Deep Learning, Ian Goodfellow et. al Rozdział 8.1
Odpowiedzi z tego miejsca

1 cmn Oct 09 2020 at 23:07

Na etapie opadania z pełnym gradientem funkcję straty definiuje się jako średnią składnika strat w poszczególnych punktach próbkowania. Aby zminimalizować funkcję strat, musimy uśredniać poszczególne gradienty.

W stochastycznym spadku gradientu, jeśli nie ma odchylenia w wyborze partii, uśrednienie dla partii dałoby nieobciążone oszacowanie pełnego gradientu.