follow-the-regularized-leader 근위 경사 하강 법은 다음 업데이트 단계를 사용합니다.
$$ 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 |) $$
-
우리는 $ t + 1 $ 라운드에 있으며 이미 $ t $ 데이터 포인트를 보았습니다 .
-
$ g_s $는 $ s $ 샘플의 그라디언트입니다.
-
$ \ sigma_s $는 $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
그리고 마지막으로 $ \ lambda_1 $는 정규화 용어입니다.
처음 두 용어로 무엇을하는지에 대해 기하학적 / 물리적 / 기타 간단한 직관을 줄 수 있습니까? 첫 번째는 어떤 종류의 추진력을 나타 냅니까? 두 번째 위치에서는 새 위치가 이전 위치와 달라야합니까?
무거운 이론을 지나치게 단순화하려는 시도처럼 보이면 잠시만 기다려주십시오 …
답변
McMahan s Follow-the-Regularized-Leader 및 Mirror Descent : 등가 정리 를 따릅니다.
이 논문은 단순 경사 하강 법 업데이트 규칙은 위의 규칙과 매우 유사한 방식으로 작성할 수 있습니다.
FOBOS (경사 하강 변형)의 직관적 인 업데이트 규칙은 다음과 같습니다.
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
여기서
- $ g_t $는 이전 샘플 $ t $에 대한 기울기입니다. 해당 샘플에 대한 가설의 손실을 줄이기 위해 그 방향으로 이동하려고합니다.
- 그러나 우리는 가설을 변경하고 싶지 않습니다. $ x_t $ 너무 많이 (이미 본 예제를 잘못 예측 할까봐 두려워). $ \ mu_t $는이 샘플의 단계 크기이며 각 단계를 더 보수적으로 만들어야합니다.
미분이 0 인 위치를 찾고 명시적인 업데이트 규칙을 얻을 수 있습니다.
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
이 문서는 위와 동일한 직관적 인 업데이트 규칙을 다음과 같이 작성할 수도 있음을 보여줍니다.
$$ 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}] $$
FTRL- 근위 공식과 매우 유사합니다. 사실 그래디언트 부분 (1 항)과 근위 강 볼록성 (3 항)은 똑같고 이것들이 저에게 흥미로운 부분이었습니다.
댓글
- 논문이 저를 넘어선 기술적 세부 사항에 대해 다루기 때문에 누군가이 답변을 확인하고이 설명을 확인할 수 있다면 기쁩니다. 의미가 있습니다 …
답변
FOBOS의 경우 원래 공식은 기본적으로 SGD의 확장입니다. http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRL 논문은 Duchi 폐쇄 형 형식을 공식화하여 통합 된 관점을 제공하려고합니다. FTRL과 유사한 방식으로 업데이트합니다. 용어 g * x (ihadanny의 답변에서도 언급 됨)는 약간 이상하지만 위의 pdf에서 작업하면 “상당히 명확합니다.
위 pdf의 8 페이지에서 지금은 정규화 용어 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 {Duchi pdf 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} $$
위의 $ \ mathbf {w} _t $ 및 $ \ mathbf {g} _t $는 모두 argmin에 대한 상수이므로 무시됩니다. 그러면 ihadanny가 지정한 형식이됩니다.
$ \ mathbf {w} \ mathbf {g} _t $ 형식은 의미가 있지만 (위의 Duchi 형식에서 등가 파생 후)이 형식에서는 매우 직관적이지 않으며 $ \ FTRL 논문의 mathbf {g} _ {1 : t} \ mathbf {w} $ 양식. 보다 직관적 인 Duchi 형식의 FTRL 공식을 이해하려면 FTRL과 FOBOS의 주요 차이점은 단순히 $ \ mathbf {g} _ {1 : t} $-> $ \ mathbf {g} _ {t} $입니다. ( https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf 참조) 2 페이지의 표에 실제로 FOBOS에 대한 오타가 있습니다. 그런 다음 위의 등가 유도에서 $ \ mathbf {g} _ {t} $를 $ \ mathbf {g} _ {1 : t} $로 변경하면 FTRL이 기본적으로 닫힌 $ \ mathbf {g} _ {1 : t} $
의 평균을 사용하여 $ \ mathbf {g} _ {t} $ 값에 대해보다 “보수적”인 FOBOS 업데이트 양식