A követi a rendszeresített vezetőt proximális gradiens süllyedés ezt a frissítési lépést használja:
$$ 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 |) $$
-
A $ t + 1 $ körön vagyunk, már láttunk $ t $ adatpontot .
-
$ g_s $ a $ s $ minta színátmenete.
-
$ \ sigma_s $ nem növekvő tanulási arány, amelyet $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
és végül a $ \ lambda_1 $ egy legalizációs kifejezés.
Tudna geometriai / fizikai / egyéb egyszerű megérzést adni arra, hogy mit csinálunk az első 2 kifejezéssel? Az első valamiféle lendületet képvisel? Szükség van-e a másodikra, hogy új helyszínünk eltérjen a korábbi helyeinktől?
Kérjük, legyen türelemmel, ha ez tetszik neked egy nehéz elmélet túlegyszerűsítésének kísérletére …
Válasz
McMahan követése a szabályosított vezető és a tükör leszármazása: ekvivalencia tételek alapján.
A cikk azt mutatja, hogy az egyszerű gradiens ereszkedési frissítési szabály a fenti szabályhoz hasonlóan írható.
A FOBOS (gradiens ereszkedési variáns) intuitív frissítési szabálya:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
ahol
- $ g_t $ az előző minta gradiense $ t $ – ebbe az irányba akarunk haladni, mivel ez csökkenti a hipotézisünk veszteségét az adott mintán.
- Azonban nem akarjuk megváltoztatni a hipotézisünket $ x_t $ túl sok (attól félve, hogy rosszul jósolunk a már látott példákon). A $ \ mu_t $ egy lépésméret ehhez a mintához, és konzervatívabbá kell tennie az egyes lépéseket.
Megtalálhatjuk, hol van a derivált 0, és kapunk egy kifejezett frissítési szabályt:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
A cikk azt mutatja, hogy ugyanaz a fenti intuitív frissítési szabály a következőképpen is írható:
$$ 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}] $$
Ami meglehetősen hasonlít az FTRL-proximális formulához. Valójában a gradiens rész (1. ciklus) és a proximális erős konvexitás (3. ciklus) megegyezik, és ezek voltak számomra érdekes részek.
Megjegyzések
- Mivel a cikk olyan technikai részletekbe megy át, amelyek túlmutattak rajtam, örülnék, ha valaki ellenőrizni tudná ezt a választ és meggyőződne erről a magyarázatról van értelme …
Válasz
FOBOS esetén az eredeti megfogalmazás alapvetően az SGD kiterjesztése: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
az FTRL-dokumentum a Duchi zárt forma megfogalmazásával próbál egységes képet adni frissítés az FTRL-hez hasonló módon. a g * x kifejezés (amelyet az ihadanny válaszában is megemlítenek) kissé furcsa, de ha a fenti pdf alapján dolgozol, akkor ez elég egyértelmű:
a fenti pdf 8. oldalán, ha egyelőre figyelmen kívül hagyjuk az R szabályosítási kifejezést,
$$ \ 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 {figyelembe véve a Duchi pdf 7. oldalát} \\ & = & (\ 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} $$
a fenti $ \ mathbf {w} _t $ és $ \ mathbf {g} _t $ mind az argin állandók, tehát figyelmen kívül hagyják, akkor megkapja az ihadanny által megadott formát
A $ \ mathbf {w} \ mathbf {g} _t $ formának van értelme (a fenti ekvivalencia-levezetés után a Duchi-alakból), de ebben a formában nagyon nem intuitív, és még inkább a $ \ mathbf {g} _ {1: t} \ mathbf {w} $ űrlap az FTRL dokumentumban. az FTRL képlet intuitívabb Duchi formában való megértéséhez vegye figyelembe, hogy az FTRL és a FOBOS közötti fő különbség egyszerűen a $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (lásd: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf megjegyzés: a FOBOS-nak valójában elírási hibája van a 2. oldalon található táblázatban, meg kell néznie a egyenletek a bekezdésekben), akkor egyszerűen módosítsa a $ \ mathbf {g} _ {t} $ értéket $ \ mathbf {g} _ {1: t} $ értékre a fenti egyenértékű levezetésben, és azt fogja tapasztalni, hogy az FTRL alapvetően a zárt- formázza a FOBOS-frissítést egy “konzervatívabb” értékkel a $ \ mathbf {g} _ {t} $ értékre a $ \ mathbf {g} _ {1: t} $ átlagának felhasználásával