follow-the-regularized-leader proximal gradient nedstigning bruger dette opdateringstrin:
$$ 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 |) $$
-
Vi er på $ t + 1 $ runde, vi har allerede set $ t $ datapunkter .
-
$ g_s $ er gradienten for $ s $ -prøven.
-
$ \ sigma_s $ er en ikke-stigende læringsrate, defineret som $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
og til sidst $ \ lambda_1 $ er et reguleringsudtryk.
Kan du give en geometrisk / fysisk / anden enkel intuition for hvad laver vi med de første 2 termer? Repræsenterer den første en slags momentum? Kræver den anden, at vores nye placering er forskellig fra vores tidligere placeringer?
Vær tålmodig, hvis dette ser ud til at være et forsøg på at forenkle en tung teori …
Svar
Følger McMahan” s Follow-the-Regularized-Leader og Mirror Descent: Ækvivalenssætninger .
Papiret viser, at den simple gradientopdateringsregel kan skrives på en meget lignende måde til ovenstående regel.
Den intuitive opdateringsregel for FOBOS (en variant med gradientafstamning) er:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
hvor
- $ g_t $ er gradienten for den forrige prøve $ t $ – vi vil bevæge os i den retning, da det mindsker tabet af vores hypotese på den prøve.
- Vi ønsker dog ikke at ændre vores hypotese $ x_t $ for meget (af frygt for at forudsige dårligt på eksempler, vi allerede har set). $ \ mu_t $ er en trinstørrelse for denne prøve, og det skal gøre hvert trin mere konservativt.
Vi kan finde, hvor derivatet er 0, og få en eksplicit opdateringsregel:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Papiret fortsætter med at vise, at den samme intuitive opdateringsregel ovenfor også kan skrives som:
$$ 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}] $$
Hvilket ligner den FTRL-proximale formulering. Faktisk er gradientdelen (1. periode) og den proximale stærke konveksitet (3. periode) den samme, og disse var de interessante dele for mig.
Kommentarer
- Da papiret går ind i tekniske detaljer, der ligger uden for mig, ville jeg være glad for, hvis nogen kan kontrollere dette svar og sørge for denne forklaring giver mening …
Svar
for FOBOS, den originale formulering er dybest set en udvidelse af SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRL-papiret forsøger at give en samlet visning ved at formulere Duchi lukket form opdatering på samme måde som FTRL. udtrykket g * x (også nævnt i ihadannys svar) er lidt underligt, men hvis du arbejder ud fra ovenstående pdf, er det ret klart:
på side 8 i ovenstående pdf, hvis vi ignorerer reguleringsudtrykket R for nu,
$$ \ 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 {overvejer side 7 i 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} $$
$ \ mathbf {w} _t $ og $ \ mathbf {g} _t $ ovenfor er alle konstanter for argmin, så ignoreres, så har du den form, der er givet af ihadanny
$ \ mathbf {w} \ mathbf {g} _t $ form giver mening (efter ovenstående ækvivalensafledning fra Duchi-formen), men i denne form er den meget uintuitiv, og endnu mere er $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form i FTRL-papiret. for at forstå FTRL-formlen i den mere intuitive Duchi-form, skal du bemærke, at den største forskel mellem FTRL og FOBOS simpelthen er $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (se https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf bemærk, der er faktisk en tastefejl til FOBOS i tabellen på side 2, du skal se på ligninger i afsnit) så skal du bare ændre $ \ mathbf {g} _ {t} $ til $ \ mathbf {g} _ {1: t} $ i ovenstående ækvivalensafledning, og du vil opdage, at FTRL stort set er den lukkede- form FOBOS-opdatering med en mere “konservativ” værdi af $ \ mathbf {g} _ {t} $ ved hjælp af gennemsnittet af $ \ mathbf {g} _ {1: t} $