Coborârea de gradient proximal follow-the-regularized-leader utilizează acest pas de actualizare:
$$ 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 |) $$
-
Suntem în runda $ t + 1 $, am văzut deja $ t $ puncte de date .
-
$ g_s $ este gradientul pentru eșantionul $ s $.
-
$ \ sigma_s $ este o rată de învățare care nu crește, definită ca $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
și în cele din urmă $ \ lambda_1 $ este un termen de regularizare.
Puteți da o intuiție simplă geometrică / fizică / de altă natură pentru ce facem cu primii 2 termeni? Primul reprezintă un fel de impuls? Cea de-a doua necesită ca noua noastră locație să fie diferită de locațiile noastre anterioare?
Vă rugăm să aveți răbdare dacă vi se pare o încercare de simplificare excesivă a unei teorii grele …
Răspuns
În urma McMahan” Follow-the-Regularized-Leader și Mirror Descent: Teoreme de echivalență .
Lucrarea arată că regula simplă de actualizare a coborârii în gradient poate fi scrisă într-un mod foarte similar cu regula de mai sus.
Regula de actualizare intuitivă a FOBOS (o variantă de coborâre în gradient) este:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
unde
- $ g_t $ este gradientul pentru eșantionul anterior $ t $ – vrem să ne deplasăm în direcția respectivă, deoarece scade pierderea ipotezei noastre asupra eșantionului respectiv.
- Cu toate acestea, nu vrem să ne schimbăm ipoteza. $ x_t $ prea mult (de teamă să nu prezicem prost pe exemplele pe care le-am văzut deja). $ \ mu_t $ este o dimensiune de pas pentru acest eșantion și ar trebui să facă fiecare pas mai conservator.
Putem găsi unde derivatul este 0 și putem obține o regulă explicită de actualizare:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Lucrarea continuă pentru a arăta că aceeași regulă de actualizare intuitivă de mai sus poate fi scrisă și ca:
$$ 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}] $$
Care este destul de similar cu formularea FTRL-proximală. De fapt, partea de gradient (primul termen) și convexitatea puternică proximală (al treilea termen) sunt aceleași și acestea au fost părțile interesante pentru mine.
Comentarii
- Pe măsură ce lucrarea intră în detalii tehnice care mă depășeau, aș fi bucuros dacă cineva poate verifica acest răspuns și se asigură că această explicație are sens …
Răspuns
pentru FOBOS, formularea originală este practic o extensie a SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
lucrarea FTRL încearcă să ofere o vizualizare unificată formulând forma închisă Duchi actualizați în mod similar cu FTRL. termenul g * x (menționat și în răspunsul lui ihadanny) este puțin ciudat, dar dacă funcționezi din pdf-ul de mai sus, este destul de clar:
la pagina 8 din pdf-ul de mai sus, dacă ignorăm termenul de regularizare R pentru moment,
$$ \ 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 {luând în considerare pagina 7 din pdf-ul Duchi} \\ & = & (\ 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} $$
$ \ mathbf {w} _t $ și $ \ mathbf {g} _t $ de mai sus sunt toate constante pentru argmin, deci sunt ignorate, atunci aveți forma dată de ihadanny
forma $ \ mathbf {w} \ mathbf {g} _t $ are sens (după derivarea de echivalență de mai sus din forma Duchi), dar în această formă este foarte neintuitivă și cu atât mai mult este $ \ mathbf {g} _ {1: t} \ mathbf {w} $ în hârtie FTRL. pentru a înțelege formula FTRL în forma Duchi mai intuitivă, rețineți că diferența majoră dintre FTRL și FOBOS este pur și simplu $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (vezi https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf rețineți că există de fapt o greșeală de tipar pentru FOBOS în tabelul de la pagina 2, ar trebui să vă uitați ecuațiile din paragrafe) apoi schimbați doar $ \ mathbf {g} _ {t} $ în $ \ mathbf {g} _ {1: t} $ în derivarea de echivalență de mai sus și veți descoperi că FTRL este practic închisul- formați actualizarea FOBOS cu o valoare mai „conservatoare” pentru valoarea $ \ mathbf {g} _ {t} $ utilizând media $ \ mathbf {g} _ {1: t} $