brunch

라이킷 댓글 공유 87 브런치 글을 SNS에 공유해보세요

You can make anything
by writing

- C.S.Lewis -

by Chris송호연 Sep 03. 2017

Gradient Descent Overview

다양한 그라디언트 디센트 알고리즘을 살펴봅시다

이 블로그 게시물은 Sebastian Ruder의 허락을 받고 번역하였습니다.

http://ruder.io/optimizing-gradient-descent


참고로, 제가 예전에 번역했던 '계산 그래프로 역전파 이해하기'가 같은 주제를 다루고 있어 공부하시는 데 도움이 될 것 같네요.

https://brunch.co.kr/@chris-song/22



이 블로그 게시물은 사용법을 결정하는 데 도움이되는 그라디언트 디센트를 최적화하기위한 다양한 알고리즘의 동작에 대한 인사이트를 제공하는 것을 목표로합니다. 먼저 그라디언트 디센트의 다양한 변형을 살펴볼 것입니다. 그런 다음 교육 과정에서 해결해야 할 과제를 간략하게 요약 해 보겠습니다. 그 다음에는 이러한 과제를 해결하기위한 동기부여와 이를 통해 업데이트 규칙을 유도하는 방법을 보여줌으로써 가장 일반적인 최적화 알고리즘을 소개합니다. 병렬 및 분산 설정에서 그래디언트 디센트를 최적화하는 알고리즘 및 아키텍처에 대해 간략히 살펴 보겠습니다. 마지막으로 그라데이션 강하 최적화에 도움이되는 추가 전략을 고려할 것입니다.


Gradient descent는 목적 함수의 기울기 

 반대 방향으로 파라미터를 업데이트하여 모델의 파라미터 

에 의해 파라미터화 된 목적 함수 

를 최소화하는 방법입니다. 



Learning rate η는 (로컬) 최소값에 도달하기 위해 취하는 단계의 크기를 결정합니다. 즉, 우리는 계곡에 도달 할 때까지 목적 함수에 의해 생성 된 지표면의 기울기 방향을 따라 내리막 길을 따릅니다. 그래디언트 강하에 익숙하지 않은 경우 여기에서 신경망 최적화에 대한 좋은 소개를 찾을 수 있습니다.


그라디언트 디센트 변형
(Gradient descent variants)


그라디언트 디센트의 세 가지 변형이 있는데, 목적 함수의 그라디언트를 계산하는 데 사용되는 데이터의 양이 다릅니다. 데이터 양에 따라 매개 변수 업데이트의 정확성과 업데이트를 수행하는 데 걸리는 시간 사이에 균형을 유지합니다.


배치 그라디언트 디센트
(Batch gradient descent)


바닐라 그래디언트 디센트 (일명 배치 그라디언트 디센트)는 전체 트레이닝 데이터 세트에 대한 파라미터 θ에 대한 비용 함수의 그래디언트를 계산합니다.



전체 데이터 세트가 하나의 업데이트만 수행하는 그라디언트를 계산할 필요가 있으므로 배치 그라디언트 디센트는 매우 느리고 메모리에 맞지 않는 데이터 세트의 경우 다루기가 어렵습니다. 일괄 그라디언트 디센트는 또한 온라인에서 모델을 온라인으로 업데이트하는 것을 허용하지 않습니다. 즉, 즉석에서 새로운 예제를 업데이트 할 수 있습니다.


코드에서 배치 그라디언트 디센트는 다음과 같이 보입니다.


for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)  
  params = params - learning_rate * params_grad


사전 정의 된 수의 epoch의 경우, 매개 변수 벡터 매개 변수와 관련하여 전체 데이터 집합에 대한 손실 함수의 기울기 벡터 params_grad를 먼저 계산합니다. 최첨단 딥러닝 라이브러리는 일부 매개 변수와 관련하여 그라디언트를 효율적으로 계산하는 자동 차별화 기능을 제공합니다. 그래디언트를 직접 파생 시키면 그래디언트 검사가 좋은 생각입니다. 그라디언트를 올바르게 확인하는 방법에 대한 유용한 정보는 여기를 참조하십시오.


그런 다음 우리가 수행하는 업데이트의 크기를 결정하는 학습 속도로 그라디언트 방향으로 매개 변수를 업데이트합니다. 일괄 그라디언트 디센트는 볼록한 오차 표면에 대한 전역 최소값과 볼록하지 않은 표면에 대한 국부 최소값으로 수렴하는 것이 보장됩니다.


스토케스틱 그라디언트 디센트
(Stochastic gradient descent)


Stochastic Gradient Descent (SGD)은 각 학습 예제 x (i) 및 레이블 y (i) 에 대한 매개 변수 업데이트를 수행합니다.


배치 그라데이션 디센트는 각 매개 변수를 업데이트하기 전에 비슷한 예제의 그라디언트를 다시 계산하므로 대규모 데이터 세트에 대한 중복 계산을 수행합니다. SGD는 한 번에 하나의 업데이트 만 수행하여이 중복성을 제거합니다. 따라서 대개 훨씬 빠르며 온라인 학습에 사용될 수도 있습니다.


SGD는 이미지 1에서와 같이 목적 함수가 크게 변동하는 높은 분산을 자주 업데이트합니다.


Image 1: SGD fluctuation (Source: Wikipedia)


배치 그라데이션 강하가 매개 변수가 배치 된 최소 유역으로 수렴하는 동안 SGD의 변동은 한편으로는 새롭고 잠재적으로 더 나은 로컬 최소 점으로 점프 할 수있게합니다. 반면에 SGD가 계속 과부하를 맺으므로 궁극적으로 수렴을 복잡하게 만듭니다. 그러나 학습 속도를 서서히 낮추면 SGD는 일괄 기울기 강하와 동일한 수렴 동작을 나타내며 비구면 및 볼록 최적화 각각에 대해 로컬 또는 전역 최소값으로 거의 수렴합니다.


코드 조각은 단순히 트레이닝 예제에 루프를 추가하고 각 예제와 관련하여 그라디언트를 평가합니다. 이 섹션에서 설명한대로 모든 신기원마다 훈련 데이터를 섞는다.

for i in range(nb_epochs):
   np.random.shuffle(data)
   for example in data:
     params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad


미니 배치 그라디언트 디센트
(Mini-batch gradient descent)


미니 배치 그라디언트 디센트는 마침내 양 쪽의 장점을 최대한 활용하고 n 트레이닝 예제의 모든 미니 배치에 대한 업데이트를 수행합니다.



이 방법은 a) 매개 변수 업데이트의 분산을 줄여보다 안정적인 수렴을 유도 할 수 있습니다. b) 그래디언트 컴퓨팅을 가능하게하는 최첨단 심층 학습 라이브러리에 공통으로 최적화 된 매트릭스 최적화를 사용할 수 있습니다. 매우 효율적인 미니 배치. 일반적인 미니 배치 크기의 범위는 50 ~ 256이지만 응용 프로그램마다 다를 수 있습니다. 미니 배치 그라디언트 디센트는 일반적으로 신경망을 학습 할 때 선택되는 알고리즘이며 SGD라는 용어는 일반적으로 미니 배치가 사용되는 경우에도 사용됩니다. 참고 :이 게시물의 나머지 부분에서 SGD를 수정하면 매개 변수 

코드에서 예제를 반복하는 대신 크기가 50 인 미니 배치를 반복합니다.


for i in range(nb_epochs):
  np.random.shuffle(data)
  for batch in get_batches(data, batch_size=50):
    params_grad = evaluate_gradient(loss_function, batch, params)
    params = params - learning_rate * params_grad


도전 (Challenges)

그러나 바닐라 미니 배치 그라디언트 디센트는 양호한 컨버전스를 보장하지는 않습니다. 그리고 해결해야 할 몇 가지 문제를 제공합니다.


적절한 학습 속도를 선택하는 것은 어려울 수 있습니다. 학습 속도가 너무 낮으면 너무 느리게 수렴되고 학습 속도가 너무 빠르면 수렴이 어려워지고 loss function이 최소 또는 그 이상으로 변동됩니다.


학습 속도 스케쥴 [11]은 예를 들어, 훈련 중 학습 속도를 조정하려고 시도합니다. (예를 들어, 어닐링 annealing) 즉 사전 정의 된 스케줄에 따라 또는 에포크들 간의 목표 변화가 임계치 아래로 떨어질 때 학습 속도를 감소시키는 단계를 포함합니다. 그러나 이러한 스케줄과 임계 값은 미리 정의되어야하므로 데이터 세트의 특성에 맞지 않습니다 [10].


또한 동일한 학습 속도가 모든 매개 변수 업데이트에 적용됩니다. 우리의 데이터가 희박하고 기능의 빈도가 매우 다른 경우, 모든 데이터를 동일한 정도로 업데이트하고 드물게 발생하는 기능에 대해서는 더 큰 업데이트를 수행하지 않을 수 있습니다.


신경망에 공통적으로 나타나는 높은 비 볼록 오차 기능을 최소화하는 또 다른 주요 과제는 수많은 차선책의 극소값에 갇히는 것을 피하는 것입니다. Dauphin et al. [19]는 어려움이 실제로 극소점이 아니라 안장 점, 즉 한 차원이 위로 기울고 다른 차원이 아래로 기울어 진 점으로부터 발생한다고 주장합니다. 이러한 안장 점은 대개 같은 오류가있는 고원으로 둘러싸여있어 SGD가 모든 차원에서 0에 가까워지면서 SGD가 도망가는 것을 악명 높게 나타냅니다.


그라디언트 디센트 최적화 알고리즘들
(Gradient descent optimization algorithms)


다음은 앞서 언급 한 문제를 해결하기 위해 심층 학습 커뮤니티에서 널리 사용되는 일부 알고리즘에 대해 설명합니다. 우리는 고차원 데이터 세트에 대해 실제로는 계산할 수없는 알고리즘을 논의하지 않을 것입니다. 뉴턴의 방법과 같은 2 차 법.


모멘텀(Momentum)


SGD는 계곡을 조종하는 데 어려움이 있습니다. 즉 표면이 다른 차원보다 훨씬 가파르게 커브하는 지역입니다. 이 시나리오에서 SGD는 계곡의 경사면을 가로 질러 진동하면서 이미지 2와 같이 국부 최적을 향한 바닥을 따라 주저없이 진행합니다.



Image 2: SGD without momentum


Image 3: SGD with momentum


Momentum [2]은 이미지 3에서 볼 수 있듯이 SGD를 관련 방향으로 가속하고 진동을 줄이는 데 도움이되는 방법입니다. 이는 과거 시간 단계의 업데이트 벡터의 분수 γ를 현재 업데이트 벡터에 추가하여 수행합니다.



참고 : 일부 구현은 방정식의 부호를 교환합니다. 운동량 항 γ는 보통 0.9 또는 이와 유사한 값으로 설정됩니다.


근본적으로, 모멘텀을 사용할 때, 우리는 언덕 아래로 공을 밀어 넣습니다. 공은 내리막 길을 따라 운동량을 축적하여 도중에 더 빠르고 빨라집니다 (공기 저항이 있으면 γ <1). 매개 변수 업데이트에서도 같은 결과가 발생합니다. 기울기가 같은 방향을 가리키는 차원의 모멘텀은 증가하고 기울기는 방향을 변경하는 차원의 업데이트를 줄입니다. 결과적으로 우리는 더 빠른 수렴과 발진 감소를 얻습니다.


네스테로프 가속 그라디언트
(Nesterov accelerated gradient, NAG) 


그러나 언덕을 굴러 내려가는 사면은 맹목적으로 경사면을 따라 가며 매우 불만족 스럽습니다. 우리는 더 똑똑한 공을 가지고 싶습니다. 언덕은 언덕이 다시 위로 올라 가기 전에 천천히 움직이는 것을 알 수 있도록 어디로 가고 있는지에 대한 개념을 가진 공입니다.


네스테로프 가속 그라디언트 (Nesterov accelerated gradient, NAG) [7]는 우리의 운동량을 이런 종류의 관행이라고 부르는 방법입니다. 우리는 우리의 모멘텀 항을 θ 파라미터를 이동하기 위해 

로 사용한다는 것을 압니다. 따라서 

을 계산하면 매개 변수의 다음 위치에 대한 근사값을 얻을 수 있습니다 (전체 업데이트의 경우 그라디언트가 누락 됨). 매개 변수가있는 대략적인 아이디어입니다. 이제 우리는 현재 매개 변수 θ에 대한 것이 아니라 매개 변수의 대략적인 미래 위치에 대한 기울기를 계산하여 효과적으로 미리 볼 수 있습니다.



다시, 우리는 운동량 항 γ를 약 0.9의 값으로 설정했습니다. 모멘텀은 먼저 현재 그래디언트 (이미지 4의 작은 파란색 벡터)를 계산하고 업데이트 된 누적 그래디언트 (큰 파란색 벡터)의 방향으로 크게 점프하는 반면 NAG는 먼저 이전 누적 그래디언트의 방향으로 크게 점프합니다 ( 갈색 벡터), 그래디언트를 측정 한 다음 보정 (빨간색 벡터)을 수행하여 전체 NAG 업데이트 (녹색 벡터)를 얻습니다. 이 예상 업데이트는 우리가 너무 빨리 지나가는 것을 방지하고 응답 성을 향상시켜 여러 작업에서 RNN의 성능을 크게 향상시킵니다 [8].


이미지 4 : 네 스테 로프 업데이트 (출처 : G. Hinton 강의 6c)


IAGS의 인사이트에 대한 또 다른 설명은 여기를 참조하십시오. Ilya Sutskever는 박사 학위 논문에 대한 자세한 설명을 제공합니다 [9].


이제 우리의 업데이트 기능을 오류 기능의 기울기에 적용하고 SGD의 속도를 높일 수 있었으므로 각 개별 매개 변수에 업데이트를 적용하여 중요도에 따라 더 크거나 작은 업데이트를 수행하고자합니다.


아다그라드 (Adagrad)

Adagrad [3]는 다음을 수행하는 그래디언트 기반 최적화 알고리즘입니다. 학습 속도를 매개 변수에 맞게 조정하여 빈번한 매개 변수에 대한 업데이트 빈도를 낮추고 업데이트 횟수를 줄입니다. 이러한 이유 때문에 sparse 데이터를 처리하는 데 적합합니다. Dean et al. [4] 은 Adagrad가 SGD의 견고성을 크게 향상시키고 Google의 대규모 신경망을 훈련하는 데 사용한다는 사실을 발견했습니다. Google의 대규모 신경망 (neural net)은 Youtube 비디오에서 고양이를 인식하는 법을 배웠습니다. 또한, Pennington et al.은 드문 단어는 빈번한 단어보다 훨씬 더 큰 업데이트가 필요하기 때문에 Adagrad를 사용하여 GloVe 단어 삽입을 교육했습니다.


이전에는 모든 매개 변수 θi가 동일한 학습 속도 η을 사용하기 때문에 모든 매개 변수 θ에 대한 업데이트를 한 번에 수행했습니다. Adagrad는 매 단계 t마다 모든 매개 변수 θi에 대해 다른 학습 속도를 사용하므로 Adagrad의 매개 변수 별 업데이트를 먼저 벡터화 한 다음 벡터화합니다. 간결함을 위해 우리는

를 시간 단계 t에서의 파라미터 θi에 대한 목적 함수의 기울기로 설정합니다.



각 시간 단계 t에서 모든 매개 변수 θi에 대한 SGD 업데이트는 다음과 같습니다.

업데이트 규칙에서, Adagrad는 θi에 대해 계산 된 과거의 기울기를 기반으로 모든 매개 변수 θi에 대한 각 시간 단계 t에서 일반적인 학습 속도 η을 수정합니다.




여기에서 각 대각 원소 i, i는 시간 단계 t [25]까지의 θi에 대한 기울기의 제곱의 합이며, ε은 0으로 나누기를 피하는 smoothing term입니다 (일반적으로 1e-8의 차수). 흥미롭게도, 제곱근 연산이 없으면 알고리즘은 훨씬 더 나쁜 성능을 보입니다.


Gt에는 과거 그라디언트의 제곱합이 포함되어 있습니다. 대각선을 따라 모든 파라미터 θ에 요소 별 행렬 벡터 곱셈을 수행하여 구현을 벡터화 할 수 있습니다. Gt와 gt 사이의 ⊙ :



Adagrad의 주요 이점 중 하나는 학습 속도를 수동으로 조정할 필요가 없기 때문입니다. 대부분의 구현에서는 기본값 0.01을 사용합니다.


Adagrad의 가장 큰 약점은 분모에 제곱 된 기울기가 축적된다는 것입니다. 추가 된 모든 용어가 양수이므로 누적 합계가 계속 증가하는 것입니다. 이것은 차례로 학습 속도를 줄이고 궁극적으로 극히 작아지며 알고리즘이 더 이상 지식을 습득 할 수 없게됩니다. 다음 알고리즘은이 결함을 해결하는 것을 목표로합니다.


Adadelta

Adadelta [6]는 적극적이고 단조롭게 감소하는 학습 속도를 줄이기 위해 노력하는 Adagrad의 확장판입니다. 과거의 모든 제곱 된 그라디언트를 축적하는 대신 Adadelta는 축적 된 과거의 그라데이션의 창을 고정 된 크기로 제한합니다.


이전의 제곱 된 그라디언트를 비효율적으로 저장하는 대신에, 그라디언트의 합계는 모든 과거 제곱 된 그라디언트의 부식 평균으로 재귀 적으로 정의됩니다. 시간 단계 tt에서의 이동 평균 E [g2] t는 이전 평균 및 현재 기울기에서만 (모멘텀 항과 유사하게 분수 γ에 따라)



우리는 γ를 모멘텀 항과 비슷한 값 0.9로 설정했습니다. 명확성을 위해 이제 우리는 바닐라 SGD 업데이트를 매개 변수 업데이트 벡터 Δθt로 다시 작성합니다.

이전에 파생 된 Adagrad의 매개 변수 업데이트 벡터는 다음과 같은 형식을 취합니다.

우리는 이제 대각선 행렬 Gt를 과거 제곱 된 기울기에 대한 감쇠 평균으로 대체합니다. E [g2] t :

분모는 그라디언트의 평균 제곱근 (RMS) 오차 기준이므로,이를 단시간 기준으로 대체 할 수 있습니다.

작성자는이 업데이트의 단위 (SGD, 모멘텀 또는 Adagrad)가 일치하지 않음을 알립니다. 즉, 업데이트의 매개 변수와 동일한 가상 단위가 있어야합니다. 이를 실현하기 위해 먼저 지수 기하 급수적으로 다른 평균을 정의합니다. 이번에는 기울기를 제곱하지 않고 매개 변수 업데이트를 제곱합니다.

매개 변수 업데이트의 제곱 평균 제곱근 오차는 다음과 같습니다.

RMS [Δθ] t는 알려지지 않았으므로 이전 시간 단계까지 매개 변수 업데이트의 RMS로 근사합니다. RMS [Δθ] t-1로 이전 업데이트 규칙의 학습률 η을 대체하면 최종적으로 Adadelta 업데이트 규칙이 생성됩니다.

Adadelta를 사용하면 업데이트 규칙에서 제거되었으므로 기본 학습 속도를 설정할 필요조차 없습니다.


RMSprop

RMSprop은 Geoff Hinton이 Coursera 강의 6e에서 제안한 미발표의 적응 학습 속도 방법입니다.

RMSprop과 Adadelta는 Adagrad의 근본적으로 감소하는 학습 속도를 해결해야 할 필요성 때문에 동시에 독자적으로 개발되었습니다. 실제로 RMSprop은 위에서 파생 한 Adadelta의 첫 번째 업데이트 벡터와 동일합니다.



또한 RMSprop은 학습 속도를 기하 급수적으로 감소하는 평균 제곱 평균으로 나눕니다. Hinton은 γγ가 0.9로 설정되는 것을 제안하지만 학습 속도 ηη에 대한 양호한 기본값은 0.001입니다.


Adam

적응 모멘트 추정 (Adaptive Moment Estimation, Adam) [15]은 각 매개 변수에 대한 적응 학습 률을 계산하는 또 다른 방법입니다. Adadelta와 RMSprop과 같이 과거 제곱 된 그라디언트 vt의 기하 급수적으로 감소하는 평균을 저장하는 것 외에도 Adam은 모멘텀과 비슷한 과거 그라디언트 mt의 기하 급수적 인 평균을 유지합니다.



mt와 vt는 각각 그라디언트의 첫 번째 모멘트 (평균)와 두 번째 모멘트 (집중되지 않은 분산)의 추정치이므로 메서드의 이름입니다. mt와 vt가 0의 벡터로 초기화됨에 따라 Adam의 저자는 특히 초기 시간 간격 동안, 특히 감쇠율이 작은 경우 (즉, β1과 β2가 1에 가까워짐) 0으로 편향되어 있음을 관찰합니다.

이들은 바이어스 보정 된 1 차 및 2 차 모멘트 추정치를 계산함으로써 이들 바이어스를 방해합니다 :



그런 다음 Adadelta 및 RMSprop에서 보았 듯이 매개 변수를 업데이트하여 Adam 업데이트 규칙을 생성합니다.



저자는 β1에 대해 0.9, β2에 대해 0.999, ε에 대해 10-8의 기본값을 제안합니다. 그들은 Adam이 실제로 잘 작동하고 다른 적응 학습 방법 알고리즘에 유리하게 비교된다는 것을 경험적으로 보여줍니다.


AdaMax

Adam 업데이트 규칙의 vt 요소는 vt-1 항을 통한 과거 그라데이션의 ℓ2 표준과 현재 그라디언트 | gt | ^ 2에 반비례하여 그라데이션의 크기를 조정합니다.




이 업데이트를 ℓp norm으로 일반화 할 수 있습니다. Kingma와 Ba는 또한 beta2를 βp2로 매개 변수화합니다.



큰 p 값에 대한 표준은 일반적으로 수치 적으로 불안정 해지므로 실제로 ℓ1과 ℓ2의 표준이 가장 일반적입니다. 그러나, ℓ∞는 또한 일반적으로 안정적인 행동을 보입니다. 이러한 이유로 저자는 AdaMax (Kingma and Ba, 2015)를 제안하고 ℓ∞의 vt가 다음과 같이 보다 안정된 값으로 수렴한다는 것을 보여 주었습니다. Adam과의 혼동을 피하기 위해 ut을 사용하여 무한대의 norm-constrained vt를 나타냅니다.



AdaMax 업데이트 규칙을 얻기 위해 

을 

로 바꿈으로써 이것을 Adam 업데이트 방정식에 연결할 수 있습니다.



ut가 max 연산에 의존하기 때문에 Adam에서 mt 및 vt와 같이 0으로 편향되는 것은 권장 할만한 바가 아니므로 utut에 대한 바이어스 보정을 계산할 필요가없는 것입니다. 좋은 기본값은 다시 η = 0.002, β1 = 0.9, β2 = 0.999입니다.


Nadam

이전에 보았 듯이 Adam은 RMSprop과 운동량의 조합으로 볼 수 있습니다. RMSprop는 과거 제곱 된 그라디언트 vt의 기하 급수적으로 감소하는 평균에 기여하며 모멘텀은 과거의 그라디언트 mt의 기하 급수적 인 감소를 나타냅니다. 우리는 Nesterov 가속도 그레디언트 (NAG)가 바닐라 운동량보다 우수함을 보았습니다.

Nadam (Nesterov 가속화 적응 모멘트 추정) [24]은 Adam과 NAG를 결합합니다. NAG를 Adam에 통합하기 위해서는 운동량 항을 mt로 수정해야합니다.


먼저, 우리의 현재 표기법을 사용하여 운동량 업데이트 룰을 회상 해봅시다.



여기서 J는 우리의 목적 함수이고, γ는 운동량 쇠퇴 기간이며, η은 우리의 스텝 크기입니다. 위의 세 번째 방정식을 확장하면 다음과 같이됩니다.



이것은 다시 운동량이 이전 운동량 벡터의 방향으로 한 발짝 내딛는 것과 현재의 그라디언트 방향으로 나아가는 단계를 포함한다는 것을 보여줍니다.


그런 다음 NAG는 그라디언트를 계산하기 전에 운동량 단계로 매개 변수를 업데이트하여 그라디언트 방향에서보다 정확한 단계를 수행 할 수있게합니다. 따라서 우리는 그라디언트 gt를 수정하여 NAG에 도달해야합니다.



Dozat은 다음과 같은 방법으로 NAG를 수정할 것을 제안합니다. 모멘텀 단계를 두 번 적용합니다 - 기울기 gt를 업데이트하는 데 한 번, 매개 변수 θt + 1을 업데이트하는 데 두 번째 시간을 적용합니다. 이제 Look-ahead 모멘텀 벡터를 직접 적용합니다 현재 매개 변수를 업데이트하려면 :



위의 확장 된 운동량 업데이트 규칙의 방정식에서와 같이 이전의 운동량 벡터 mt-1을 사용하는 대신, 현재의 운동량 벡터 mt를 사용하여 미리 살펴볼 수 있습니다. Adam에게 Nesterov 모멘텀을 추가하기 위해 이전의 모멘텀 벡터를 유사하게 현재 모멘텀 벡터로 대체 할 수 있습니다. 먼저, Adam 업데이트 규칙은 다음과 같습니다



mtm ^ t와 mt의 정의로 두 번째 방정식을 확장하면 다음과 같이됩니다.



는 이전 시간 단계의 운동량 벡터의 바이어스 보정 된 추정값입니다. 따라서 그것을 

로 대체 할 수 있습니다.



이 방정식은 위의 확장 된 운동량 업데이트 규칙과 매우 유사합니다. 우리는 이전의 시간 단계 m t-1m ^ t-1의 운동량 벡터의 바이어스 보정 된 추정치를 현재의 운동량 벡터 m tm ^ 1의 바이어스 보정 된 추정치로 단순히 대체함으로써 네 스테 로프 모멘텀을 추가 할 수 있습니다. t는 Nadam 업데이트 규칙을 제공합니다.



Visualization of algorithms


다음 두 애니메이션 (Image Credit : Alec Radford)은 제시된 최적화 알고리즘의 최적화 동작에 대한 몇 가지 직관을 제공합니다. 또한 Karpathy의 동일한 이미지에 대한 설명과 논의 된 알고리즘에 대한 간략한 개요를 살펴보십시오.


이미지 5에서 시간 경과에 따른 손실 표면 (Beale 함수)의 윤곽에 대한 동작을 확인합니다. Adagrad, Adadelta 및 RMSprop는 거의 즉시 오른쪽 방향으로 향하고 비슷한 속도로 수렴하며 모멘텀 및 NAG는 언덕을 따라 굴러가는 공의 이미지를 불러 일으키는 오프 트랙입니다. 그러나 NAG는 앞을 내다 보면서 응답 성이 향상되어 코스를 빨리 수정할 수 있습니다.


이미지 6은 안장 지점, 즉 한 차원이 양의 기울기를 갖는 지점에서 알고리즘의 동작을 보여줍니다. 다른 차원은 음의 기울기를 가지며 이전에 언급했듯이 SGD에 어려움을줍니다. Adagrad, RMSprop 및 Adadelta가 빠르게 음의 기울기로 내려가는 동안 SGD, Momentum 및 NAG는 대칭을 깨뜨리는 것이 어렵다는 것을 알게됩니다. 두 명의 후자가 결국 안장 지점을 벗어날 수 있습니다.

    

SGD optimization on loss surface contours



SGD optimization on saddle point


그림에서 알 수 있듯이 Adagrad, Adadelta, RMSprop 및 Adam과 같은 적응 학습 속도 방법이 가장 적합하며 이러한 시나리오에 가장 적합한 수렴을 제공합니다.


Which optimizer to use?

이제 어느 옵티마이저를 사용해야합니까? 입력 데이터가 희소 한 경우 적응 학습 속도 방법 중 하나를 사용하면 최상의 결과를 얻을 수 있습니다. 또 다른 이점은 학습 속도를 조정할 필요가 없지만 기본값으로 최상의 결과를 얻는 것입니다.


요약하면 RMSprop은 근본적으로 감소하는 학습 속도를 다루는 Adagrad의 확장입니다. Adadelta가 numinator 업데이트 규칙에서 매개 변수 업데이트의 RMS를 사용한다는 점을 제외하면 Adadelta와 동일합니다. Adam은 마지막으로 RMSprop에 바이어스 보정 및 모멘텀을 추가합니다. RMSprop, Adadelta 및 Adam은 유사한 환경에서 잘 작동하는 매우 유사한 알고리즘입니다. Kingma et al. [15]는 바이어스 보정을 통해 Adam이 그라디언트가 희박 해짐에 따라 최적화가 끝날 때 RMSprop보다 약간 우수한 것으로 나타났습니다. 아담은 최상의 선택 일 수 있습니다.


흥미롭게도 최근의 많은 논문에서는 바닐라 SGD를 모멘텀과 간단한 학습 속도 어닐링 일정없이 사용합니다. 표시된 바와 같이 SGD는 일반적으로 최소값을 찾지 만 일부 옵티 마이저의 경우보다 훨씬 오래 걸리고 강력한 초기화 및 어닐링 일정에 훨씬 더 의존하며 로컬 최소값이 아닌 안장 점에 걸릴 수 있습니다. 결론적으로, 빠른 수렴을 신경 쓰고 깊거나 복잡한 신경망을 훈련하는 경우 적응 학습 속도 방법 중 하나를 선택해야합니다.


Parallelizing and distributing SGD

대규모 데이터 솔루션의 보편화와 저품목 클러스터의 가용성을 고려할 때 SGD를 배포하면 속도를 높이기 위해 분명한 선택입니다.


SGD 자체는 본질적으로 순차적입니다. 단계별로 진행하면서 최소 수준으로 나아갑니다. 이를 실행하면 좋은 컨버전스를 얻을 수 있지만 특히 대규모 데이터 세트에서 느려질 수 있습니다. 반대로 SGD를 비동기 적으로 실행하는 것이 더 빠르지 만 작업자 간의 차선책 통신은 컨버전스가 불량해질 수 있습니다. 또한 대규모 컴퓨팅 클러스터를 사용하지 않고도 한 시스템에서 SGD를 병렬 처리 할 수 있습니다. 다음은 병렬화되고 분산 된 SGD를 최적화하기 위해 제안 된 알고리즘 및 아키텍처입니다.


Hogwild!

Niu et al. [23]은 Hogwild라는 업데이트 체계를 소개합니다! CPU에서 SGD 업데이트를 병렬로 수행 할 수 있습니다. 프로세서는 매개 변수를 잠그지 않고 공유 메모리에 액세스 할 수 있습니다. 이것은 각 업데이트가 모든 매개 변수의 일부만 수정하기 때문에 입력 데이터가 희박한 경우에만 작동합니다. 그들은이 경우 프로세서가 유용한 정보를 덮어 쓰지 않을 가능성이 거의 없기 때문에 업데이트 체계가 거의 최적의 수렴 속도를 달성한다는 것을 보여줍니다.


Downpour SGD

Downpour SGD는 Dean 등이 사용한 SGD의 비동기 변형입니다. [4] DistBelief 프레임 워크 (TensorFlow의 전신)에서. 교육 데이터의 하위 집합에서 모델의 여러 복제본을 병렬로 실행합니다. 이 모델은 매개 변수 서버로 업데이트를 보내며 여러 컴퓨터로 분할됩니다. 각 기계는 모델 매개 변수의 일부분을 저장하고 업데이트해야합니다. 그러나 복제본은 서로 통신하지 않으므로 예를 들어. 가중치 또는 업데이트를 공유함으로써 매개 변수가 계속 분기 될 위험이있어 수렴을 방해합니다.


Delay-tolerant Algorithms for SGD

McMahan과 Streeter [12]는 과거의 그래디언트뿐만 아니라 업데이트 지연에도 적용 할 수있는 지연 허용 알고리즘을 개발함으로써 AdaGrad를 병렬 설정으로 확장합니다. 이것은 실제로 잘 작동하는 것으로 나타났습니다.


TensorFlow


TensorFlow [13]는 대규모 기계 학습 모델 구현 및 배포를위한 Google의 최근 공개 된 프레임 워크입니다. DistBelief에 대한 경험을 바탕으로하며 이미 대규모 모바일 장치는 물론 대규모 분산 시스템에서 계산을 수행하기 위해 내부적으로 사용됩니다. 분산 실행의 경우 계산 그래프가 모든 장치에 대한 하위 그래프로 분할되고 보내기 / 받기 노드 쌍을 사용하여 통신이 수행됩니다. 그러나 TensorFlow의 오픈 소스 버전은 현재 분산 기능을 지원하지 않습니다 (여기 참조). 업데이트 13.04.16 : TensorFlow의 분산 버전이 출시되었습니다.


Elastic Averaging SGD


Zhang et al. [14]는 비동기식 SGD의 작업자의 매개 변수를 탄성력, 즉 매개 변수 서버에 저장된 중앙 변수와 연결하는 탄성 평균화 SGD (EASGD)를 제안합니다. 이것은 지역 변수가 이론적으로 매개 변수 공간의 더 많은 탐구를 허용하는 중심 변수에서 더 멀리 변동하게합니다. 그들은 경험적으로 탐사 능력을 향상시킴으로써 새로운 지역 최적의 발견을 통해 성능을 향상시킬 수 있음을 보여줍니다.


Additional strategies for optimizing SGD

마지막으로 SGD의 성능을 향상시키기 위해 앞에서 언급 한 알고리즘과 함께 사용할 수있는 추가 전략을 소개합니다. 다른 일반적인 트릭에 대한 개요는 [22]를 참조하십시오.


Shuffling and Curriculum Learning

일반적으로 우리는 우리의 모델에 의미있는 순서로 훈련 예제를 제공하는 것을 피하기를 원합니다. 최적화 알고리즘에 편향 될 수 있기 때문입니다. 결과적으로, 매 epoch 이후에 교육 데이터를 섞는 것이 좋습니다.

반면에, 우리가 점차 더 어려운 문제를 해결하고자하는 경우, 의미있는 순서로 교육 예제를 제공하면 실제로 성능이 개선되고 융합이 개선 될 수 있습니다. 이 의미있는 질서를 확립하는 방법을 커리큘럼 학습 [16]이라고 부른다.

Zaremba와 Sutskever [17]는 LSTM을 교육하여 Curriculum Learning을 사용하여 간단한 프로그램을 평가하고 결합 된 또는 혼합 된 전략이 어려움을 증가시켜 사례를 정렬하는 순진한 전략보다 낫다는 것을 보여줄 수있었습니다.



Batch normalization


학습을 용이하게하기 위해 일반적으로 매개 변수의 초기 값을 제로 평균 및 단위 분산으로 초기화하여 정규화합니다. 교육이 진행되고 매개 변수를 다른 범위로 업데이트하면이 정상화가 없어져 네트워크가 심화됨에 따라 교육 속도가 느려지고 변경 사항이 증폭됩니다.

일괄 정규화 [18]는 모든 미니 배치에 대해 이러한 정규화를 다시 설정하고 변경 사항은 작업을 통해 다시 전파됩니다. 정규화를 모델 아키텍처의 일부로 만들어줌으로써 더 높은 학습 속도를 사용하고 초기화 매개 변수에 덜주의를 기울일 수 있습니다. 일괄 정규화는 정규 표현식으로 추가 기능을 수행하여 삭제 필요성을 줄입니다.


Early stopping

Geoff Hinton에 따르면, "Early stopping (is) beautiful free lunch"(NIPS 2015 Tutorial 슬라이드, 슬라이드 63) 따라서 검증 오류가 충분히 개선되지 않으면 교육 과정에서 유효성 검사 세트에서 오류를 모니터링하고 중지해야합니다 (인내심을 가지고).


Gradient noise

Neelakantan et al. [21] 각 기울기 업데이트에 대한 가우스 분포 N (0, σ2t) N (0, σt2)을 따르는 잡음을 추가합니다.



그들은 다음 일정에 따라 분산을 어닐링합니다.



그들은이 노이즈를 추가하면 네트워크가 불량한 초기화에보다 강력 해지고 특히 심층적이고 복잡한 네트워크를 교육하는 데 도움이된다는 것을 보여줍니다. 그들은 추가 된 소음이 모델에 더 많은 모델을 제공 할 수있는 기회를 제공하고 새로운 모델을 발견 할 수있는 기회를 제공합니다.


Conclusion

이 블로그 게시물에서 처음에는 그라디언트 디센트의 세 가지 변형을 살펴 보았으며 그 중에서 미니 배치 그라디언트 디센트가 가장 많이 사용되었습니다. 그런 다음 SGD를 최적화하는 데 가장 일반적으로 사용되는 알고리즘 인 모멘텀, 네 스테 로브 가속 그라디언트, Adagrad, Adadelta, RMSprop, Adam 및 비동기 SGD를 최적화하는 다양한 알고리즘을 조사했습니다. 마지막으로 셔플 및 커리큘럼 학습, 일괄 정규화 및 조기 중단과 같은 SGD를 개선하기위한 다른 전략을 고려했습니다.


이 블로그 게시물을 통해 다양한 최적화 알고리즘의 동기와 행동에 대한 직감을 얻을 수 있기를 바랍니다. 내가 놓친 SGD를 향상시키는 확실한 알고리즘이 있습니까? SGD 교육을 용이하게하기 위해 어떤 트릭을 사용하고 있습니까? 아래 코멘트에서 알려주십시오.


Acknowledgements

Denny Britz와 Cesar Salgado에게 감사의 말을 전합니다.


Printable version and citation

이 블로그 게시물은 arXiv에 대한 기사로도 사용할 수 있습니다. 나중에 참조 할 수 있습니다.

도움이되는 경우에는 해당 arXiv 기사를 다음과 같이 인용하십시오.

Sebastian Ruder (2016). An overview of gradient descent optimisation algorithms. arXiv preprint arXiv:1609.04747.


Translations

이 블로그 게시물은 다음 언어로 번역되었습니다.

Japanese

Chinese

업데이트 21.06.16 :이 게시물은 Hacker News에 게시되었습니다. 이 토론에서는 관련 연구 및 기타 기술에 대한 흥미로운 정보를 제공합니다.


References

Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society. 


Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural Networks : The Official Journal of the International Neural Network Society, 12(1), 145–151. http://doi.org/10.1016/S0893-6080(98)00116-6 


Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. Retrieved from http://jmlr.org/papers/v12/duchi11a.html 


Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Le, Q. V, … Ng, A. Y. (2012). Large Scale Distributed Deep Networks. NIPS 2012: Neural Information Processing Systems, 1–11. http://doi.org/10.1109/ICDAR.2011.95 


Pennington, J., Socher, R., & Manning, C. D. (2014). Glove: Global Vectors for Word Representation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 1532–1543. http://doi.org/10.3115/v1/D14-1162 


Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701 


Nesterov, Y. (1983). A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady ANSSSR (translated as Soviet.Math.Docl.), vol. 269, pp. 543– 547. 


Bengio, Y., Boulanger-Lewandowski, N., & Pascanu, R. (2012). Advances in Optimizing Recurrent Networks. Retrieved from http://arxiv.org/abs/1212.0901 


Sutskever, I. (2013). Training Recurrent neural Networks. PhD Thesis. 


Darken, C., Chang, J., & Moody, J. (1992). Learning rate schedules for faster stochastic gradient search. Neural Networks for Signal Processing II Proceedings of the 1992 IEEE Workshop, (September), 1–11. http://doi.org/10.1109/NNSP.1992.253713 


H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951. 


Mcmahan, H. B., & Streeter, M. (2014). Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning. Advances in Neural Information Processing Systems (Proceedings of NIPS), 1–9. Retrieved from http://papers.nips.cc/paper/5242-delay-tolerant-algorithms-for-asynchronous-distributed-online-learning.pdf 


Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., … Zheng, X. (2015). TensorFlow : Large-Scale Machine Learning on Heterogeneous Distributed Systems. 


Zhang, S., Choromanska, A., & LeCun, Y. (2015). Deep learning with Elastic Averaging SGD. Neural Information Processing Systems Conference (NIPS 2015), 1–24. Retrieved from http://arxiv.org/abs/1412.6651 


Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13. 


Bengio, Y., Louradour, J., Collobert, R., & Weston, J. (2009). Curriculum learning. Proceedings of the 26th Annual International Conference on Machine Learning, 41–48. http://doi.org/10.1145/1553374.1553380 


Zaremba, W., & Sutskever, I. (2014). Learning to Execute, 1–25. Retrieved from http://arxiv.org/abs/1410.4615 


Ioffe, S., & Szegedy, C. (2015). Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariate Shift. arXiv Preprint arXiv:1502.03167v3. 


Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv, 1–14. Retrieved from http://arxiv.org/abs/1406.2572 


Sutskever, I., & Martens, J. (2013). On the importance of initialization and momentum in deep learning. http://doi.org/10.1109/ICASSP.2013.6639346 


Neelakantan, A., Vilnis, L., Le, Q. V., Sutskever, I., Kaiser, L., Kurach, K., & Martens, J. (2015). Adding Gradient Noise Improves Learning for Very Deep Networks, 1–11. Retrieved from http://arxiv.org/abs/1511.06807 


LeCun, Y., Bottou, L., Orr, G. B., & Müller, K. R. (1998). Efficient BackProp. Neural Networks: Tricks of the Trade, 1524, 9–50. http://doi.org/10.1007/3-540-49430-8_2 


Niu, F., Recht, B., Christopher, R., & Wright, S. J. (2011). Hogwild! : A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, 1–22. 


Dozat, T. (2016). Incorporating Nesterov Momentum into Adam. ICLR Workshop, (1), 2013–2016. 


Duchi et al. [3] give this matrix as an alternative to the full matrix containing the outer products of all previous gradients, as the computation of the matrix square root is infeasible even for a moderate number of parameters dd. 


Image credit for cover photo: Karpathy's beautiful loss functions tumblr



keyword
카카오 크루 & Microsoft AI MVP
댓글

    매거진 선택

    키워드 선택 0 / 3 0
    브런치는 최신 브라우저에서 최적화 되어있습니다. IE chrome safari