proximální gradient follow-the-regularized-leader používá tento krok aktualizace:
$$ 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 |) $$
-
Jsme v kole $ t + 1 $, již jsme viděli $ t $ datové body .
-
$ g_s $ je přechod pro vzorek $ s $.
-
$ \ sigma_s $ je nerostoucí rychlost učení, definovaná jako $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
a nakonec $ \ lambda_1 $ je regularizační výraz.
Můžete dát geometrickou / fyzickou / jinou jednoduchou intuici pro to, co děláme s prvními 2 termíny? Představuje první určitý druh hybnosti? Vyžaduje druhá, aby se naše nové umístění lišilo od našich předchozích?
Buďte trpěliví, pokud se vám to zdá jako pokus o přílišné zjednodušení těžké teorie …
Odpověď
Následující McMahanův následný-regulovaný vůdce a Mirror Descent: věty o rovnocennosti .
Příspěvek ukazuje, že jednoduché pravidlo aktualizace sestupu gradientu lze napsat velmi podobným způsobem jako výše uvedené pravidlo.
Pravidlo intuitivní aktualizace FOBOS (varianta sestupu sestupu) je:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
kde
- $ g_t $ je gradient pro předchozí vzorek $ t $ – chceme se pohybovat tímto směrem, protože to snižuje ztrátu naší hypotézy o tomto vzorku.
- Nechceme však naši hypotézu měnit $ x_t $ příliš mnoho (ze strachu před špatným předpovídáním na příkladech, které jsme již viděli). $ \ mu_t $ je velikost kroku pro tuto ukázku a každý krok by měl být konzervativnější.
Můžeme zjistit, kde je derivace 0, a získat explicitní pravidlo aktualizace:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Příspěvek dále ukazuje, že stejné výše uvedené intuitivní pravidlo aktualizace lze také napsat 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ž je docela podobné proximální formulaci FTRL. Ve skutečnosti jsou gradientní část (1. člen) a proximální silná konvexita (3. člen) stejné a pro mě to byly zajímavé části.
Komentáře
- Jelikož příspěvek pojednává o technických detailech, které byly mimo mě, byl bych rád, kdyby někdo mohl tuto odpověď zkontrolovat a ujistit se, že toto vysvětlení dává smysl …
Odpověď
pro FOBOS je původní formulace v podstatě rozšířením SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
článek FTRL se pokouší poskytnout jednotný pohled formulováním Duchiho uzavřené formy aktualizace podobným způsobem jako FTRL. termín g * x (zmíněný také v odpovědi ihadanny) je trochu divný, ale pokud pracujete z výše uvedeného pdf, je to docela jasné:
na straně 8 výše uvedeného pdf, pokud prozatím ignorujeme regularizační člen 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 {s ohledem na stránku 7 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} $$
výše uvedené $ \ mathbf {w} _t $ a $ \ mathbf {g} _t $ jsou všechny konstanty pro argmin, takže jsou ignorovány, pak máte formu danou ihadanny
forma $ \ mathbf {w} \ mathbf {g} _t $ má smysl (po výše uvedené derivaci ekvivalence z Duchiho formy), ale v této podobě je velmi neintuitivní a ještě více je $ \ mathbf {g} _ {1: t} \ mathbf {w} $ formulář v dokumentu FTRL. abyste pochopili vzorec FTRL v intuitivnější podobě Duchi, nezapomeňte, že hlavní rozdíl mezi FTRL a FOBOS je jednoduše $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (viz https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf poznámka, že ve skutečnosti je v tabulce na straně 2 překlep pro FOBOS, měli byste se podívat na rovnice v odstavcích), pak stačí změnit $ \ mathbf {g} _ {t} $ na $ \ mathbf {g} _ {1: t} $ ve výše uvedené derivaci ekvivalence a zjistíte, že FTRL je v podstatě uzavřený- vytvořte aktualizaci FOBOS s „konzervativnějším“ způsobem v hodnotě $ \ mathbf {g} _ {t} $ s průměrem $ \ mathbf {g} _ {1: t} $