A descida gradiente proximal siga o líder regularizado usa esta etapa de atualização:
$$ 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 |) $$
-
Estamos na rodada $ t + 1 $, já vimos $ t $ pontos de dados .
-
$ g_s $ é o gradiente da amostra $ s $.
-
$ \ sigma_s $ é uma taxa de aprendizagem não crescente, definida como $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
e finalmente $ \ lambda_1 $ é um termo de regularização.
Você pode dar uma intuição geométrica / física / outra simples para o que estamos fazendo com os primeiros 2 termos? O primeiro representa algum tipo de momentum? O segundo exige que nosso novo local seja diferente de nossos locais anteriores?
Seja paciente se isso lhe parecer uma tentativa de simplificar demais uma teoria pesada …
Resposta
Seguindo McMahan” s Follow-the-Regularized-Leader e Mirror Descent: Equivalence teoremas .
O artigo mostra que a regra de atualização de gradiente descendente simples pode ser escrita de uma maneira muito semelhante à regra acima.
A regra de atualização intuitiva de FOBOS (uma variante de gradiente descendente) é:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
onde
- $ g_t $ é o gradiente para a amostra anterior $ t $ – queremos nos mover nessa direção, pois isso diminui a perda de nossa hipótese nessa amostra.
- No entanto, não queremos mudar nossa hipótese. $ x_t $ demais (por medo de prever mal em exemplos que já vimos). $ \ mu_t $ é um tamanho de etapa para esta amostra e deve tornar cada etapa mais conservadora.
Podemos descobrir onde a derivada é 0 e obter uma regra de atualização explícita:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
O papel continua mostrando que a mesma regra de atualização intuitiva acima também pode ser escrita como:
$$ 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}] $$
O que é muito semelhante à formulação FTRL-proximal. Na verdade, a parte do gradiente (1º termo) e a convexidade forte proximal (3º termo) são iguais, e essas foram as partes interessantes para mim.
Comentários
- À medida que o artigo entra em detalhes técnicos que estão além de mim, eu ficaria feliz se alguém pudesse verificar esta resposta e garantir esta explicação faz sentido …
Resposta
para FOBOS, a formulação original é basicamente uma extensão de SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
o artigo FTRL tenta dar uma visão unificada formulando a forma fechada de Duchi atualizar de forma semelhante ao FTRL. o termo g * x (também mencionado na resposta de ihadanny) é um pouco estranho, mas se você trabalhar com o pdf acima, fica bem claro:
na página 8 do pdf acima, se ignoramos o termo de regularização R por enquanto,
$$ \ 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 a página 7 do pdf Duchi} \\ & = & (\ 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} $$
o $ \ mathbf {w} _t $ e $ \ mathbf {g} _t $ acima são constantes para o argmin, então são ignorados, então você tem a forma dada por ihadanny
a forma $ \ mathbf {w} \ mathbf {g} _t $ faz sentido (após a derivação de equivalência acima da forma Duchi), mas nesta forma é muito pouco intuitiva, e ainda mais é $ \ mathbf {g} _ {1: t} \ mathbf {w} $ formulário no papel FTRL. para entender a fórmula FTRL na forma Duchi mais intuitiva, observe que a principal diferença entre FTRL e FOBOS é simplesmente $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (consulte https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf observe que, na verdade, há um erro de digitação para FOBOS na tabela da página 2, você deve olhar para o equações nos parágrafos), então apenas altere $ \ mathbf {g} _ {t} $ para $ \ mathbf {g} _ {1: t} $ na derivação de equivalência acima, e você verá que FTRL é basicamente o formulário FOBOS atualização com um mais “conservador” para o valor de $ \ mathbf {g} _ {t} $ usando a média de $ \ mathbf {g} _ {1: t} $