La discesa del gradiente prossimale follow-the-regularized-leader utilizza questo passaggio di aggiornamento:
$$ 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 |) $$
-
Siamo nel giro $ t + 1 $, abbiamo già visto $ t $ punti dati .
-
$ g_s $ è il gradiente per il campione $ s $.
-
$ \ sigma_s $ è un tasso di apprendimento non crescente, definito come $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
e infine $ \ lambda_1 $ è un termine di regolarizzazione.
Puoi dare una semplice intuizione geometrica / fisica / altro per quello che stiamo facendo con i primi 2 termini? Il primo rappresenta una sorta di slancio? Il secondo richiede che la nostra nuova posizione sia diversa dalle nostre posizioni precedenti?
Per favore sii paziente se questo ti sembra un tentativo di semplificare eccessivamente una teoria pesante …
Risposta
Seguendo McMahan” s Follow-the-Regularized-Leader e Mirror Descent: teoremi di equivalenza .
Larticolo mostra che la semplice regola di aggiornamento della discesa del gradiente può essere scritta in modo molto simile alla regola precedente.
La regola di aggiornamento intuitiva di FOBOS (una variante della discesa del gradiente) è:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
dove
- $ g_t $ è il gradiente per il campione precedente $ t $ – vogliamo muoverci in quella direzione poiché diminuisce la perdita della nostra ipotesi su quel campione.
- Tuttavia, non vogliamo cambiare la nostra ipotesi $ x_t $ troppo (per paura di fare previsioni sbagliate su esempi che abbiamo già visto). $ \ mu_t $ è una dimensione del passo per questo campione e dovrebbe rendere ogni passo più conservativo.
Possiamo trovare dove la derivata è 0 e ottenere una regola di aggiornamento esplicita:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Il documento prosegue mostrando che la stessa regola di aggiornamento intuitiva sopra può essere scritta anche come:
$$ 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}] $$
Che è abbastanza simile alla formulazione FTRL-prossimale. In effetti, la parte del gradiente (1 ° termine) e la convessità forte prossimale (3 ° termine) sono le stesse, e queste erano le parti interessanti per me.
Commenti
- Dato che il documento entra in dettagli tecnici che erano al di là di me, sarei felice se qualcuno potesse controllare questa risposta e assicurarsi questa spiegazione ha senso …
Risposta
per FOBOS, la formulazione originale è fondamentalmente unestensione di SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
il documento FTRL cerca di fornire una vista unificata formulando la forma chiusa di Duchi aggiornamento in modo simile a FTRL. il termine g * x (menzionato anche nella risposta di ihadanny) è un po strano, ma se lavori dal pdf sopra, è abbastanza chiaro:
a pagina 8 del pdf sopra, se ignoriamo il termine di regolarizzazione R per ora,
$$ \ 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 {considerando la pagina 7 del 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 $ e $ \ mathbf {g} _t $ sopra sono tutte costanti per argmin, quindi vengono ignorate, quindi hai la forma data da ihadanny
la forma $ \ mathbf {w} \ mathbf {g} _t $ ha senso (dopo la derivazione dellequivalenza di cui sopra dalla forma Duchi), ma in questa forma è molto poco intuitiva, e ancora di più lo è $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form nel documento FTRL. per comprendere la formula FTRL nella forma Duchi più intuitiva, nota che la principale differenza tra FTRL e FOBOS è semplicemente $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (vedi https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf nota che in realtà cè un errore di battitura per FOBOS nella tabella a pagina 2, dovresti guardare il equazioni nei paragrafi) quindi cambia semplicemente $ \ mathbf {g} _ {t} $ in $ \ mathbf {g} _ {1: t} $ nella derivazione di equivalenza sopra, e troverai che FTRL è fondamentalmente chiuso- form FOBOS aggiornamento con un valore più “conservativo” per il valore di $ \ mathbf {g} _ {t} $ utilizzando la media di $ \ mathbf {g} _ {1: t} $