Der Follow-the-Regularized-Leader proximale Gradientenabstieg verwendet diesen Aktualisierungsschritt:
$$ 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 |) $$
-
Wir befinden uns in der $ t + 1 $ -Runde, wir haben bereits $ t $ Datenpunkte gesehen .
-
$ g_s $ ist der Gradient für die $ s $ -Stichprobe.
-
$ \ sigma_s $ ist eine nicht steigende Lernrate, definiert als $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
und schließlich $ \ lambda_1 $ ist ein Regularisierungsbegriff.
Können Sie eine geometrische / physikalische / andere einfache Intuition dafür geben, was wir mit den ersten beiden Begriffen machen? Stellt der erste eine Art Schwung dar? Erfordert der zweite, dass sich unser neuer Standort von unseren vorherigen Standorten unterscheidet?
Bitte haben Sie etwas Geduld, wenn Ihnen dies wie ein Versuch erscheint, eine schwere Theorie zu stark zu vereinfachen …
Antwort
Nach McMahans Follow-the-Regularized-Leader- und Mirror-Abstieg: Äquivalenzsätze .
Das Papier zeigt dies Die einfache Regel zur Aktualisierung des Gradientenabstiegs kann auf sehr ähnliche Weise wie die obige Regel geschrieben werden.
Die intuitive Aktualisierungsregel von FOBOS (eine Variante des Gradientenabstiegs) lautet:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
wobei
- $ g_t $ ist der Gradient für die vorherige Stichprobe $ t $ – wir möchten uns in diese Richtung bewegen, da dies den Verlust unserer Hypothese für diese Stichprobe verringert.
- Wir möchten unsere Hypothese jedoch nicht ändern $ x_t $ zu viel (aus Angst, anhand von Beispielen, die wir bereits gesehen haben, schlechte Vorhersagen zu treffen). $ \ mu_t $ ist eine Schrittgröße für dieses Beispiel und sollte jeden Schritt konservativer machen.
Wir können herausfinden, wo die Ableitung 0 ist, und eine explizite Aktualisierungsregel erhalten:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Das Papier zeigt weiter, dass dieselbe intuitive Aktualisierungsregel wie folgt geschrieben werden kann:
$$ 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}] $$
Das ist der FTRL-proximalen Formulierung ziemlich ähnlich. Tatsächlich sind der Gradiententeil (1. Term) und die proximale starke Konvexität (3. Term) gleich, und dies waren die interessanten Teile für mich.
Kommentare
- Da das Papier auf technische Details eingeht, die über mich hinausgingen, würde ich mich freuen, wenn jemand diese Antwort überprüfen und diese Erklärung sicherstellen kann macht Sinn …
Antwort
für FOBOS ist die ursprüngliche Formulierung im Grunde eine Erweiterung von SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
Das FTRL-Papier versucht, durch Formulierung der geschlossenen Duchi-Form eine einheitliche Ansicht zu vermitteln Update auf ähnliche Weise wie FTRL. Der Begriff g * x (auch in der Antwort von ihadanny erwähnt) ist etwas seltsam, aber wenn Sie mit dem obigen PDF arbeiten, ist es ziemlich klar:
auf Seite 8 des obigen PDF, wenn Wir ignorieren vorerst den Regularisierungsterm 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 {unter Berücksichtigung von Seite 7 des 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} $$
die oben genannten $ \ mathbf {w} _t $ und $ \ mathbf {g} _t $ sind alle Konstanten für den Argmin, werden also ignoriert, dann haben Sie die von ihadanny
Die Form $ \ mathbf {w} \ mathbf {g} _t $ ist sinnvoll (nach der obigen Äquivalenzableitung aus der Duchi-Form), aber in dieser Form ist sie sehr unintuitiv, und noch mehr ist die Form $ \ mathbf {g} _ {1: t} \ mathbf {w} $ im FTRL-Papier. Um die FTRL-Formel in der intuitiveren Duchi-Form zu verstehen, beachten Sie, dass der Hauptunterschied zwischen FTRL und FOBOS einfach $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ ist (Siehe https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf Beachten Sie, dass in der Tabelle auf Seite 2 tatsächlich ein Tippfehler für FOBOS enthalten ist Gleichungen in den Absätzen) ändern Sie dann einfach $ \ mathbf {g} _ {t} $ in $ \ mathbf {g} _ {1: t} $ in der obigen Äquivalenzableitung, und Sie werden feststellen, dass FTRL im Grunde die geschlossene ist. Erstellen Sie ein FOBOS-Update mit einem „konservativeren“ Wert für den Wert von $ \ mathbf {g} _ {t} $, indem Sie den Durchschnitt von $ \ mathbf {g} _ {1: t} $
verwenden