SGD (Stochastic Gradient Descent)

목적: train loss를 최소화 하는 것

loss function은 loss를 구하는 것

target function은 loss function을 통해 나온 loss값으로 loss가 최소가 되도록 weight를 갱신하는 것

 

1. Gradient Descent (GD)

objective (or cost) function to minimize: f(x) = x^3 – 2x^2 + 2

to find a local minimum,

 

            n

        min ∑ wi(x - bi)^2

           i=1

          loss(w)
            | \
            |  \
            |   |
            |    \          /
            |     +-      -+
            |       \    /
            |        +--+
            +---------------------- w
                |   |   |   |
               w   w  w  w
               (1)(2)(4)(3)

w를 random하게 정함

입력으로 구해진 loss에 대해 w로 미분

 

w(1), w(2)는 각각 시점 1에서의 w, 시점 2에서의 w를 의미함 (w들의 차원을 의미하지 않음)

 

            d loss

            ------ = gradient

            d w(1)

 

w <- w(1) - 기울기

w(1)은 음수 기울기 -> 우측 이동 (반대 방향으로 이동해야 w가 작아지는 방향으로 갱신됨)

w(2)도 음수 기울기 -> 우측 이동 (값이 커짐)

w(3)은 양수 기울기 -> 좌측 이동 (값이 작아짐)

w(4)에서 0 -> 수렴

 

w가 vector인 경우, (즉 변수가 많은 경우)

모든 변수의 편미분을 벡터로 표현한 것을 '기울기'라 함

 

gradient는 vector: 함수가 가장 증가하는 방향 vector

1차원에서는 방향이 우측 혹은 좌측

증가하는 방향은 우측 (+) 의 반대 방향으로 이동하는 것이 gradient descent

 

w들의 다 변수임 (즉, 편미분 필요)

 

 

2. Gradient

w <- w – learning_rate * TrainLoss(w)’

 > w에서 loss에 w로 미분한 (다차원이면 gradient vector) 것에 learning rate를 곱한 것을 빼서 새로운 w로 갱신

이로서 loss와 weight의 space에서 최적 loss를 찾기위해 x축(w) 상 좌/우로 이동

 

            for t in range(T):
                w <- w -  step_size * d TrainLoss(w)
                                      ------------
                                       dw

                w - 기울기가 바로 w의 이동 방향임(그래프 상에서)
                    빼주기에 반대방향으로 가는 것 임
                step_size는 learning rate

hyperparamters

preset 해야 하는 parameters

iteration 수

 

1) Least square regression

 

gradient(use chain rule)

 

w를 w1, w2,. ..로 각각 편미분 하는 것

w전체로 미분 시 2*…가 되고, 이후 각 w1, w2에 대해 편미분 적용(즉, skip) 하여 계산

 

                        d g(w)
                        -----  = 𝜙(w)
                        dw

 

 

2) Gradient Descent 특징

w <- w – learning_rate * TrainLoss(w)’

모든 train data에 대해 다 더해서 곱하여 w를 갱신 (즉, w의 갱신이 오래걸림)

너무 느려서 SGD가 나옴

 

GD는 trainloss에 대한 gradient를 구함

GD는 local의 최적화를 찾음

 

그런데 실제 loss space의 그래프는 굴곡이 많음 매우 복잡한 다차원 함수

global optimization을 찾는것이 쉽지 않음

 

 

3. 가중치 갱신 방법

SGD, batch, mini batch

 

1) SGD

Stochastic (random 성)

SGD는 학습 시 마다 가중치를 갱신

N개 data면 N번 가중치를 갱신

 

학습 시마다 신경망 성능이 들쑥날쑥하며 정답에 가까워짐        

train data에서 random으로 취한 data로 loss를 구함

 

w <- w - 𝜂∇Loss_hinge(x, y, w)

 

loss function의 gradient를 구함 (w에 대해 편미분)

loss_hinge는 scalar를 주나 scalar를 편미분 하면 vector가 됨

w는 vector임

 

• 𝜂*loss(x,y,w1) < 0 -> 우측 이동 (커지도록)
• 𝜂*loss(x,y,w2) > 0 -> 좌측 이동 (작아지도록)

w vector는 여러 방향이니, 포물선 경사의 하강을 따라가게 됨

 

ex.

Loss_hinge(x,y,w) = max{0, 1 - w ⋅ 𝜙(x)y}

 

이를 w로 미분 

w는 벡터이나 1차 함수임

 

max, min 함수는 구간을 나눠서 미분함

1 - w ⋅ 𝜙(x)y    if 1 - w ⋅ 𝜙(x)y > 0

0                otherwise

 

미분하면

-𝜙(x)y           if 1 - w ⋅ 𝜙(x)y > 0

0

 

결과는 vector (방향, 크기)

즉,

 

∇ Loss(x,y,w) = -𝜙(x)y    if Loss(x,y,w) > 0

                         0         otherwise

 

 

Loss(x,y,w) > 0 인 경우

w <- w(1) - 기울기

                w(1)은 음수 기울기 -> 우측 이동

                w(2)도 음수 기울기 -> 우측 이동

                w(3)은 양수 기울기 -> 좌측 이동

 

w <- w + 𝜂 𝜙(x) y

 

 

ex.

최초 w의 모든 원소는 0 값을 지님

 

loss = max(0, 1 - w ⋅ 𝜙(x)y))

w ⋅ 𝜙(x)은 모두 0인 0 vector가 됨

 

loss = max(0, 1 - w + 𝜂*0vector*y))

최초 입력 𝜙(x) feature vector의 값이 무엇인지에 관계 없이 loss는 1이됨

loss값이 0보다 크니, 좌측으로 이동해야 함

 

w = w + 𝜂*0vector*y

w = w - 𝜂*(-𝜙(x))y

w = w + 𝜂*𝜙(x)*y

w vector는 최초 입력 𝜙(x) vector의 값을 갖게 됨

 

두 번째 입력값 𝜙(x)

와 현재 w간 space에 같은 값을 가진 것이 없다면, 즉, 서로 직교라면,

역시 loss는 1이 나오게 되고,

 

w = w + 𝜂*𝜙(x)*y

 

... 

SGD의 경우 매 입력마다 이런식으로 w값이 계속 갱신되게 됨

 

 

2) Batch

전체 학습 data를 모두 학습한 후 가중치를 갱신

-> 모든 데이터의 loss의 평균으로 가중치를 갱신

 

Δω = 1/N ∑(k=1, N) Δω(k)

 

3) Mini-batch (mini-batch SGD)

SGD와 배치를 섞은 것

전체 데이터를 N 등분하여 각각의 학습 데이터를 배치 방식으로 학습

일부 학습 데이터의 가중치 갱신값을 계산한 후 이 값들의 평균으로 가중치 갱신

 

학습 데이터가 100개고, 배치 하나를 20으로 잡았으면 총 5번의 가중치 갱신이 필요

 

GD와 SGD의 사이 정도

data를 batch로 구성(전체보단 작고, 하나보단 많은)

이 mini-batch 내 loss로 w를 update

 

Adam (ADAptive Moment estimation)은 mini-batch, batch 등을 가지고 새롭게 고안된 알고리즘

이전 w 방향을 기억하다가, 너무 갑자기 방향이 바뀌지 않도록 update를 진행

실험적으로 이렇게 했더니 더 잘 찾더라 라는 것임

 

그래서 SGD와 mini-batch는 공존 가능 함

adam = adaptive ~~ 임

 

4) Summary

SGD는 어떤 data에 대한 gradient를 구함

train data에서 random으로 취한 data

그 데이터에 대한 loss를 train loss로 '가정'

 

더 많은 w 값의 이동은 하지만, data를 한번만 읽기에 실제적으로 훨씬 적은 시간에 수렴함

 

data가 10만

T가 100

 

 

min-batch (=batch size)

gradient를 구할때 몇 개씩 data를 뽑아서 구하는지가 batch size

batch size = 1 -> SGD

batch size = data size -> GD

 

data를 한 번씩이 아니라, 100번씩 빼서 64, 128개씩 하는 경우도 있음

좀 더 gradient를 정확하게 하자는 것

 

batch size 커질수록 -> gradient는 정확해 지나 오래걸림

batch size 작을수록 -> gradient는 부정확 하나 빠름

 

batch는 묶음

batch size 가 크면

GPU들이 일을 더 잘 쪼개서 수행함

 

5) 기타 고려사항

epoch (밖의 loop): data 전체를 쭉 읽는 것 (이팍)

batch (안의 loop): 각 data에 대한 subset

 

random sampling 방법

Random sampling with replication

쓰고 다시 원래 bucket에 넣음 (복원추출)

이 경우 여러번 읽을 수 있고 아무것도 안 읽은게 나올 수 있음

 

Random sampling without replication

쓴건 재사용 안 함 (비복원추출)

하나의 epoch 시 처음부터 한 번씩 읽음

 

step size(=learning rate)

step size가 크면, 경사가 0인 곳으로 가지 못하고 주위에서 왔다갔다

그래서 step size를 처음에는 크게 하다 점차 줄임

 

lr = 1/sqrt(# updates made so far)

 

성능에 지대한 영향을 줌

step size에 민감하게 반응하지 않게 하기 위한 heuristics

 

• RMSP
• Adam: 평균적으로 제일 괜찮은 성능
• AdamGround