-profimaalisen kaltevuuden lasku käyttää tätä päivitysvaihetta:
$$ 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 |) $$
-
Olemme $ t + 1 $ -kierroksella, olemme jo nähneet $ t $ datapisteitä .
-
$ g_s $ on $ s $ -näytön kaltevuus.
-
$ \ sigma_s $ on kasvava oppimisnopeus, joka määritellään muodossa $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
ja lopuksi $ \ lambda_1 $ on laillistustermi.
Voitteko antaa geometrisen / fyysisen / muun yksinkertaisen intuition siitä, mitä teemme kahdella ensimmäisellä termillä? Edustaako ensimmäinen jonkinlaista vauhtia? Edellyttääkö toinen, että uusi sijaintimme poikkeaa aiemmista sijainneistamme?
Ole kärsivällinen, jos tämä tuntuu yritykseltäsi yksinkertaistaa raskasta teoriaa liikaa …
Vastaa
Seurataan McMahanin noudattamia säänneltyjä johtajia ja peilien laskeutumista: vastaavuuslausekkeita .
Paperi osoittaa, että yksinkertainen kaltevuuslaskun päivityssääntö voidaan kirjoittaa hyvin samalla tavalla kuin yllä oleva sääntö.
FOBOS: n (kaltevuuslaskun muunnos) intuitiivinen päivityssääntö on:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
mistä
- $ g_t $ on edellisen otoksen gradientti $ t $ – haluamme siirtyä siihen suuntaan, koska se vähentää hypoteesimme menetystä kyseisessä näytteessä.
- Emme kuitenkaan halua muuttaa hypoteesiämme $ x_t $ liikaa (peläten ennustavan huonosti jo näkemiemme esimerkkien kanssa). $ \ mu_t $ on tämän näytteen askelkoko, ja sen pitäisi tehdä jokaisesta vaiheesta konservatiivisempi.
Voimme selvittää, missä johdannainen on 0, ja saat nimenomaisen päivityssäännön:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Tässä artikkelissa osoitetaan, että sama yllä oleva intuitiivinen päivityssääntö voidaan kirjoittaa myös seuraavasti:
$$ 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}] $$
Mikä on melko samanlainen kuin FTRL-proksimaalinen formulaatio. Itse asiassa kaltevuusosa (1. luku) ja proksimaalinen voimakas kuperuus (3. luku) ovat samat, ja nämä olivat mielenkiintoisia osia minulle. on järkevää …
Vastaa
FOBOSille alkuperäinen muotoilu on pohjimmiltaan SGD: n laajennus: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRL-paperi yrittää antaa yhtenäisen näkymän muotoilemalla Duchin suljetun muodon päivitä samalla tavalla kuin FTRL. termi g * x (mainittu myös ihadannyn vastauksessa) on vähän outo, mutta jos työskentelet yllä olevasta pdf: stä, se on melko selvä:
yllä olevan pdf: n sivulla 8, jos ohitamme toistaiseksi laillistustermin 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 {ottaen huomioon Duchin pdf-sivu 7} \\ & = & (\ 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} $$
Yllä olevat $ \ mathbf {w} _t $ ja $ \ mathbf {g} _t $ ovat kaikki argminin vakioita, joten ne jätetään huomioimatta, niin sinulla on ihadannyn antama muoto
$ \ mathbf {w} \ mathbf {g} _t $ -lomakkeella on järkeä (yllä olevan vastaavuusjohdannaisen jälkeen Duchi-muodosta), mutta tässä muodossa se on hyvin epäjohdonmukainen, ja vielä enemmän on $ \ mathbf {g} _ {1: t} \ mathbf {w} $ -lomake FTRL-paperissa. ymmärtääksesi FTRL-kaavan intuitiivisemmassa Duchi-muodossa, huomaa, että suurin ero FTRL: n ja FOBOS: n välillä on yksinkertaisesti $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (katso https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf Huomaa, että FOBOSille on itse asiassa kirjoitusvirhe sivun 2 taulukossa. kappaleiden yhtälöt) muuta sitten vain $ \ mathbf {g} _ {t} $ muotoon $ \ mathbf {g} _ {1: t} $ edellisessä vastaavuusjohdannaisessa, ja huomaat, että FTRL on periaatteessa suljettu- muodosta FOBOS-päivitys ”konservatiivisemmalla” arvolle $ \ mathbf {g} _ {t} $ käyttämällä $ \ mathbf {g} _ {1: t} $ keskiarvoa