[Paper Review] Overview of mini-batch gradient descent

 

https://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf

https://arxiv.org/pdf/1609.04747

 

Overview of mini-batch gradient descent

Reminder: The error surface for a linear neuron

• linear neuron의 error surfaces는 2차 보울(그릇) 형태를 갖는다.

Horizontal ~ ellipses. Vertical ~ parabolas

• multi layer, non-linear nets의 경우에는 훨씬 복잡한 형태의 error surface를 갖지만, 부분적으로 2차 보올 형태를 대략 차용한다. (locally)

left: linear neuron, right : non-linear neuron

Convergence speed of full batch learning when the error surface is a quadratic bowl

• small distance를 이동하고 싶을 때는 gradient big
• large distance를 이동하고 싶을 때는 gradient small
  • non linear, multi layer is locally qudartic bowl ... so same issues apply

How the learing goes wrong

• if learnig rate is too big (i.e. travel distance is big) ~ oscillation diverges
  • learing rate ~= step size ~= 이동 폭
• our goal
  • consistant gradient : move quickly, small
  • inconsistant gradient : move slowly, big

learing rate & distance

Stochastic Gradient Descent

• 데이터셋이 매우 중복되어 있을 경우, gradient on first half ~= gradient on second half
  • 전체를 계산하는 대신에, first half의 gradient를 이용해 가중치를 업데이트를 한 뒤 새롭게 second half의 gradient를 얻는다.
    
    • 극단적인 경우에, 각 단계마다 가중치를 업데이트하게 되는데, 이를 'online learning'이라고 부른다.
  • 임의로 선택한 데이터에 대해 gradient를 계산하여 속도가 빠르며 online으로 학습 가능
• mini-batches are better than online learning
  • less computation
  • matrix - matrix multiplies
  • but, neet to be balanced for classes
• neural networks가 커다랗고, 매우 중복되는 훈련 데이터셋일 경우엔 mini-batch를 사용하는게 거의 best.
• fancy method(모멘텀, 아다그라드 ...)를 적용하려면 mini-batch가 상당히 커야함

A basic mini-batch gradient descent algorithm

• initial learning rate
  • reduce : error going worse or oscillates wildly
  • increase : falling fairly consistently but slowly
• end of learning
  • reduce learning rate
    • mini-batch 간 차이로 인한 최종 가중치의 변동성 제거
  • stop learning rate
    • when error stops decreasing
    • Use the error on a separate validation set

learning rate scheduling

A bag of tricks for mini-batch gradient descent

Be careful about turning down the learning rate

• learning rate를 줄이게 되면 오차의 변동성이 줄어든다. (다른 미니배치들의 gradient로 인한)

learning rate에 따른 훈련, 테스트셋의 정확도

Initializing the weights

• break symmetry by initializing with small random values (무작위 값 배정)
• when hidden unit has a big fan-in (은닉충의 input 뉴런 개수가 큰 경우)
  • small changes of weights cause overshoot
  • initialize the weights to be proportional to sqrt(fan-in)

Shifting & Scaling the inputs

Batch Normalization

• Batch 단위간 데이터 분포 차이 발생 가능 (Batch 간 데이터 상이) ~ Internal Convariant Shift
  • shift, scaling을 통해 zero mean, unit variance를 갖도록 조정 ~ Batch Normalization
    • ex) 하이퍼볼릭 탄젠트 함수는 대략 0의 평균을 갖는 활성화 함수이므로 시그모이드 함수보다 나음

• PCA 등의 비상관화를 통해 차원 축소 가능
  • 선형 뉴런의 경우, 입력 요소끼리 연관시켜 효과를 얻을 수 있음
  • 축이 정렬된 타원형의 error surface를 원형의 error surface로 변환 가능

Common probelms that occurs in multilayer networks

• local minimum, plateau
  • learning rate가 매우 높으면 발산하거나 plateau에서 수렴하는 문제가 발생

local minimum & plateau with learning rate

The momentum Method

The equations & behavior of the momentum method

equations of momentum

• 가중치를 갱신하기 전, 이전 기울기의 방향을 참고하여 관성을 획득
• a(알파)는 모멘텀 계수로, 물체가 아무런 힘도 받지 않을 때 서서히 하강하도록 도움
  • 1에 가까워질수록 속도가 훨씬 빨라짐 
• gradient가 매우 높은 경우엔 작은  모멘텀을 사용함 (e.g. a = 0.5)
• gradient가 좀 줄어들고 계곡에 갇힌다면 높은 모멘텀을 사용함 (e.g. 0.9, 0.95 0.99)

• overshoot의 위협
  • 이전 기울기 방향으로 너무 많이 이동해 최적점을 지나치는 문제 발생

A better type of momentum (Netrov 1983)

• 기존의 모멘텀 
  • 현재 위치에서 gradient를 계산 후 축적된 gradient 방향으로 크게 점프

picture of the Neterov method

• 관성 방향에 따라 먼저 움직인 후, 이동한 자리에서 기울기 계산 후 재이동

A separate, adaptive learning rate for each connection

The intuition

• appropriate learning rate
  • 초기 가중치가 작은 경우 ~ 레이어마다 gradient 크기가 매우 다름
  • 유닛의 fan-in 크기에 따라 overshoot의 크기가 결정됨
    • overshoot: 동일 오류를 수정하기 위해 많은 가중치를 동시에 변경할 때 or 학습률이 너무 높을 때
  • global learning rate에 각 가중치 누적합을 고려해 계산하는건 어떨까? ~ Adaptive learning rate

One way to determine the individual learning rates

• 모든 가중치의 local gain은 1로 시작
• 만약 현재 시점과 이전 시점의 gradient의 부호가 같다면 조금 더해주고, 다르다면 곱하여 감소시킴
  • 진동이 시작되는 경우, 빠르게 변화량을 감소시킬 수 있음

individual learnig rates using signs of gradient

Tricks for making adaptive learning rates work better

• full batch learning, big mini-batches를 사용
  • gradient의 부호 변화가 mini-batch를 샘플링하면서 발생하는 것이 아님을 보증
• Adaptive learning rates는 momentum과 결합 가능
  • 가중치에 대한 현재 gradient와 속도의 부호의 결합을 통해 사용
• Adaptive learning rates는 축 정렬 효과를 갖음
  • momentum은 축 정렬 효과 X

RMSprop: Divide the gradient by a running average of its recent magnitude

About Rprop : Using only the sign of the gradient

• 가중치마다 gradient가 다 다를 수 있고 이는 학습 동안에 계속 변화할 수 있음
  • 하나의 global learning rate를 고르는 건 어려움
  • 부호만 고려하면 어떨까?
• Rprop : Gradient의 부호 (방향성) + 개별적인 학습률 (step-size)
  • 기울기 방향이 동일하면 multiple로 increase
  • 기울기 방향이 반대라면 multiple로 decrease
  • 1/1,000,000 < step-size < 50
• mini-batch는 각 배치마다의 gradient가 다르며 가중치 업데이트 또한 독립적으로 진행됨
  • 따라서 각 미니 배치마다 다른 gradient의 크기로 나누게 되어(부호만 사용하려면) 사용하기가 어려움
    • 경향성 반영이 안됨
      • ex) 10개의 미니 배치 중 9개에서 +0.1만큼, 마지막 10번째에서 -0.9만큼의 gradient를 얻었을 때, 부호만을 반영하는 rprop의 성질 때문에 -0.9라는 커다란 크기는 무시되고 부호만 고려되어 최종적으로 '증가'할 것
    • 인접한 mini-batch에 대해 나누는 숫자가 유사하다면 어떨까?

About RMSprop

• 지수이동 평균(EMA)을 활용하여 최근 값을 더 잘 반영하도록 더 많은 가중치를 부여함
• *Adagrad 옵티마이저에서 기울기의 누적합이 무한대로 커지게되면 학습이 정체되는 현상이 발생하는데, 이를 방지하고자 제안됨

지수이동평균, EMA

RMSprop 수식