Proksymalne zejście w gradiencie follow-the-regulized-lead korzysta z tego kroku aktualizacji:
$$ w_ {t + 1} = argmin_w (w \ cdot \ sum_ {s = 1} ^ t g_s + \ frac {1} {2} \ sum_ {s = 1} ^ t \ sigma_s (w-w_s) ^ 2 + \ lambda_1 | w |) $$
-
Jesteśmy na rundzie $ t + 1 $, widzieliśmy już $ t $ punktów danych .
-
$ g_s $ jest gradientem próbki $ s $.
-
$ \ sigma_s $ to nierosnąca stopa uczenia się, zdefiniowana jako $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
i wreszcie $ \ lambda_1 $ jest terminem regularyzacyjnym.
Czy możesz podać geometryczną / fizyczną / inną prostą intuicję dotyczącą tego, co robimy z pierwszymi dwoma wyrazami? Czy ten pierwszy reprezentuje jakiś rozmach? Czy druga wymaga, aby nasza nowa lokalizacja była inna niż poprzednie?
Prosimy o cierpliwość, jeśli wydaje Ci się, że jest to próba nadmiernego uproszczenia ciężkiej teorii …
Odpowiedź
Następujące McMahan” s Follow-the-Regularized-Leader i Mirror Descent: Equivalence theorems .
Artykuł pokazuje, że prostą regułę aktualizacji gradientu zstępującego można zapisać w bardzo podobny sposób do powyższej reguły.
Intuicyjna reguła aktualizacji FOBOS (wariant gradientu zstępującego) to:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
gdzie
- $ g_t $ jest gradientem dla poprzedniej próbki $ t $ – chcemy iść w tym kierunku, ponieważ zmniejsza to utratę naszej hipotezy na tej próbce.
- Nie chcemy jednak zmieniać naszej hipotezy $ x_t $ za dużo (z obawy przed złym przewidywaniem na przykładach, które już widzieliśmy). $ \ mu_t $ jest wielkością kroku dla tej próbki i powinien sprawić, że każdy krok będzie bardziej konserwatywny.
Możemy znaleźć pochodną 0 i otrzymać wyraźną regułę aktualizacji:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Artykuł pokazuje, że ta sama intuicyjna reguła aktualizacji powyżej może być również zapisana jako:
$$ x_ {t + 1} = argmin_x [g_ {1: t} x + \ phi_ {1: t-1} x + \ psi (x) + \ frac {1} {2} \ sum_ {s = 1} ^ t {| x-x_s | ^ 2}] $$
Co jest dość podobne do sformułowania FTRL-proksymalnego. W rzeczywistości część gradientowa (1. człon) i proksymalna silna wypukłość (3. człon) są takie same i były to dla mnie interesujące części.
Komentarze
- Ponieważ w artykule omawiam szczegóły techniczne, które były poza mną, byłbym zadowolony, gdyby ktoś mógł sprawdzić tę odpowiedź i upewnić się, że to wyjaśnienie ma sens …
Odpowiedź
W przypadku FOBOS oryginalna formuła jest w zasadzie rozszerzeniem SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
artykuł FTRL próbuje dać jednolity pogląd, formułując zamkniętą formę Duchiego aktualizacja w podobny sposób jak FTRL. termin g * x (również wspomniany w odpowiedzi ihadanny) jest trochę dziwny, ale jeśli pracujesz na powyższym pliku PDF, jest całkiem jasny:
na stronie 8 powyższego pliku PDF, jeśli na razie ignorujemy człon regularyzacyjny R,
$$ \ begin {eqnarray} \ mathbf {w} _ {t + 1} & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – \ mathbf {w} _ {t + 1/2} \ | ^ 2 \} \\ & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – (\ mathbf {w} _ {t} – \ eta \ mathbf {g} _t) \ | ^ 2 \} \ mbox {biorąc pod uwagę stronę 7 pliku Duchi pdf} \\ & = & (\ mathbf {w} – \ mathbf {w} _t) ^ t (\ mathbf {w} – \ mathbf {w} _t) + 2 \ eta (\ mathbf {w} – \ mathbf {w} _t) ^ t \ mathbf {g} _t + \ eta ^ 2 \ mathbf {g} _t ^ t \ mathbf {g} _t \ end {eqnarray} $$
powyższe $ \ mathbf {w} _t $ i $ \ mathbf {g} _t $ są stałymi dla argmin, więc są ignorowane, wtedy masz postać podaną przez ihadanny
forma $ \ mathbf {w} \ mathbf {g} _t $ ma sens (po powyższym wyprowadzeniu równoważności z postaci Duchiego), ale w tej formie jest bardzo nieintuicyjna, a tym bardziej jest to $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form w dokumencie FTRL. aby zrozumieć formułę FTRL w bardziej intuicyjnej formie Duchiego, zauważ, że główna różnica między FTRL i FOBOS to po prostu $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (patrz https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf zauważ, że w tabeli na stronie 2 znajduje się literówka dotycząca FOBOS, należy spojrzeć na równania w akapitach), a następnie po prostu zmień $ \ mathbf {g} _ {t} $ na $ \ mathbf {g} _ {1: t} $ w powyższym wyprowadzeniu równoważności, a zobaczysz, że FTRL jest w zasadzie zamkniętą- uformuj aktualizację FOBOS z bardziej „konserwatywną” wartością $ \ mathbf {g} _ {t} $, używając średniej $ \ mathbf {g} _ {1: t} $