follow-the-regularized-leader proximal gradient nedstigning bruker dette oppdateringstrinnet:
$$ 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 sett $ t $ datapunkter .
-
$ g_s $ er gradienten for $ s $ -prøven.
-
$ \ sigma_s $ er en ikke-økende læringsfrekvens, definert som $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
og til slutt er $ \ lambda_1 $ et reguleringsbegrep.
Kan du gi en geometrisk / fysisk / annen enkel intuisjon for hva gjør vi med de to første begrepene? Representerer den første en slags fremdrift? Krever den andre at den nye lokasjonen vår skal være annerledes enn våre tidligere steder?
Vær tålmodig hvis dette virker som et forsøk på å forenkle en tung teori …
Svar
Følger McMahan» s Follow-the-Regularized-Leader and Mirror Descent: Equivalence theorems .
Papiret viser at den enkle oppgraderingsoppdateringsregelen for gradient kan skrives på en veldig lik måte som ovennevnte regel.
Den intuitive oppdateringsregelen til FOBOS (en variant med stigningskurs) er:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
hvor
- $ g_t $ er gradienten for forrige prøve $ t $ – vi vil bevege oss i den retningen ettersom det reduserer tapet av hypotesen vår på det prøven.
- Vi ønsker imidlertid ikke å endre hypotesen vår $ x_t $ for mye (av frykt for å forutsi dårlig på eksempler vi allerede har sett). $ \ mu_t $ er en trinnstørrelse for dette eksemplet, og det skal gjøre hvert trinn mer konservativt.
Vi kan finne hvor derivatet er 0 og få en eksplisitt oppdateringsregel:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Papiret viser videre at den samme intuitive oppdateringsregelen 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}] $$
Som er ganske lik FTRL-proksimal formulering. Faktisk er gradientdelen (1. termin) og den proksimale sterke konveksiteten (3. periode) den samme, og dette var de interessante delene for meg.
Kommentarer
- Når papiret går inn i tekniske detaljer som var utenfor meg, ville jeg være glad om noen kan sjekke dette svaret og sørge for denne forklaringen gir mening …
Svar
for FOBOS, den opprinnelige formuleringen er i utgangspunktet en utvidelse av SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRL-papiret prøver å gi et enhetlig syn ved å formulere Duchi-lukket form oppdatering på samme måte som FTRL. Begrepet g * x (også nevnt i ihadannys svar) er litt rart, men hvis du arbeider ut fra ovennevnte pdf, er det ganske klart:
på side 8 i ovennevnte pdf, hvis vi ignorerer reguleringsbetegnelsen R for nå,
$$ \ 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 {vurderer 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å blir ignorert, så har du skjemaet gitt av ihadanny
$ \ mathbf {w} \ mathbf {g} _t $ form gir mening (etter ovenstående ekvivalensavledning fra Duchi-formen), men i denne formen er den veldig uintuitiv, og enda mer er $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form i FTRL-papiret. for å forstå FTRL-formelen i den mer intuitive Duchi-formen, vær oppmerksom på at den største forskjellen mellom FTRL og FOBOS bare er $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (se https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf merk at det faktisk er en skrivefeil for FOBOS i tabellen på side 2, du bør se på ligningene i avsnittene) så er det bare å endre $ \ mathbf {g} _ {t} $ til $ \ mathbf {g} _ {1: t} $ i ovenstående ekvivalensderivasjon, og du vil finne at FTRL i utgangspunktet er den lukkede- skjema FOBOS-oppdatering med en mer «konservativ» verdi for $ \ mathbf {g} _ {t} $ ved å bruke gjennomsnittet av $ \ mathbf {g} _ {1: t} $