Mini-batch gradient descent
인공지능에서 Optimization Algorithm은 neural network 를 더 빠르게 학습시키기 위한 방식이다.
이전 내용에서 m examples training 에서 vectorization은 더 효율적으로 빠르게 계산하도록 도와준다는 사실을 배웠었다.
X = [X^(1), X^(2), ... , X^(m)] # (n_x, m)
Y = [y^(1), y^(2), ... , y^(m)] # (1, m)
그렇다면, m 이 아주 큰 값, 예를 들어 5,000,000 or 50,000,000 그 이상이라면 어떻게 될까?
아주 많은 양의 training data set 를 전부 처리하고 나서야 겨우 한 단계의 gradient descent 를 할 수 있다. 그래서, 아주 많은 양의 training data set 전체를 처리하기 전에 gradient descent 를 진행되도록 해서 더 빠른 algorithm 을 얻을 수 있다. training set을 더 작게 나눠서 이를 실현할 수 있다. 이를 Mini-batch 라고 한다.
Mini-batch 를 1000으로 해보자. 여기서 m 은 5,000,000 이다.
X = [X^(1), X^(2), ... , X^(1000)| X^(1001), X^(1002), ..., | ... X^(m)] # (n_x, m)
= [X^{1}, X^{2}, ..., X^{5000}] # m = 5,000,000
Y = [Y^(1), Y^(2), ... , Y^(1000)| Y^(1001), Y^(1002), ..., | ... Y^(m)] # (1, m)
= [Y^{1}, Y^{2}, ..., Y^{5000}] # m = 5,000,000
Mini-batch t : (X^{t}, Y^{t}) 라고 할 때, t 가 가능한 값은 1~ (m / Mini-batch) 이다.
추가로, shape.X^{t} = (n_x, Mini-batch) 이고, shape.Y^{t} = (1, Mini-batch) 이다.
이를 바탕으로 어떻게 propagation 이 진행되는지 pseudo code를 보자.
for t = 1, ... ,5000 { # m / Mini-batch size
Forward propagation on X^{t}
Z^[1] = W^[1]*X^{t} + b^[1]
A^[1] = g^[1](Z^[1])
...
A^[L] = g^[L](Z^[L])
Compute cost function J^{t} = 1/1000 * Σ (i=1~L) L(ŷ^(i), y^(i)) + λ /2000 * Σ (i=1~L) ||w^[i]||^2
Backward propagation J^{t} (using X^{t}, Y^{t})
W^[L] = W^[L] - α * dw^[L]
b^[L] = b^[L] - α * db^[L]
}
위의 code를 바탕으로 Mini-batch gradient descent 를 진행하고 전체 데이터 셋을 한번 학습한 것을 1 epoch 라고 한다.
Mini-batch Gradient Descent 에 대해서 더 자세하게 살펴보자.
전체 데이터 셋에 대해서 학습을 했을 때, 반복 횟수에 따른 학습 model 의 cost function 은 감소한다.
반면에, Mini-batch 로 학습을 했을 때, Mini-batch 인덱스에 따른 학습 model 의 cost function은 항상 감소하지는 않지만, 감소하는 경향을 따른다.
전체 데이터 셋에서 일부만 sampling 하는 mini-batch를 사용해서 update를 하기 때문에, 전체 데이터 분포를 완벽하게 대표하지 않을 수 있기 때문에 약간의 noise가 발생한다.
BGD vs SGD
- BGD(Batch Gradient Descent) : Mini-batch size = m 일 때의 우리가 알고 있는 전체 데이터 셋에 대한 학습이다. 아래 그림은 BGD에 대한 cost function을 optimize 하는 과정이다.
아주 작은 noise 와 상대적으로 큰 step 를 취하면서 global optimal 에 가까워진다. 하지만, optimal 까지의 학습 시간
이 오래 걸린다.
- SGD(Stochastic Gradient Descent) : Mini-batch size = 1 일 때의 아주 세분하게 나눠서 하는 학습이다. 아래 그림은 SGD에 대한 cost function을 optimize 하는 과정이다.
아주 큰 noise 와 상대적으로 작은 step 을 취하면서 optimal 에 가까워진다. 학습 속도는 BGD와 비교했을 때 빠르다. 하지만, global minimum 에 수렴하기 쉽지 않다. 잘못된 방향으로 가거나 mimimum 주위를 헤맬 수 있다.
BGD를 사용하면, 수렴할 때까지 아주 오랜 시간이 걸리고, SGD를 사용하면 한번에 하나의 sample만 처리하기 때문에 vectorization 을 사용했을 때, 더 비효율적이다. 그래서 m이 클 때는, 적당히 Mini-batch size를 정해서 학습을 하는 것이 좋다.
그렇다면 언제 BGD, SGD를 쓰고 만약 Mini-batch 를 사용한다면 size를 어느 정도로 해야할까?
만약, training set가 많지 않다면, BGD를 사용하는 것이 유리하다. 이 경우, 전체 training set 을 학습하는 것은 오래 걸리지 않기 때문에 더 정확하게 global minimum 에 수렴할 수 있는 BGD 를 사용한다. (m <= 2000)
반대로, training set가 많은 경우에는 Mini-batch 를 사용하는 것이 유리하다. 이 경우, 전체 trianing set 을 학습하는 것은 오래 걸리기 때문에 training set 을 적절한 size 로 나눠서 학습을 진행하는 것이 좋다. 여기서 Mini-batch size는 64~ 512 정도의 값이 전형적이다. computer memory의 배치 방식과 접근 방식 때문에 2의 거듭제곱을 가질 때 더 빨리 실행된다. 따라서, Mini-batch size는 64, 128, 256, 512 으로 구현하는 것이 좋다. 다시 말해서, CPU나 GPU memory에 적합하지 않은 Mini-batch 를 처리한다면, 성능이 갑자기 많이 떨어질 것이다. 한편, Mini-batch는 hyper parameter 에 해당하며 어떤 값이 cost function 을 감소시키는데에 최적인지를 찾는 것이 중요하다.
이제, gradient descent 보다 더 빠른 몇몇의 optimization algorithms을 살펴보고자 한다. 이를 위해서는 Exponentially Weighted Averages에 대해서 우선 알아야 한다.
Exponentially Weighted Averages
: 데이터가 시간의 흐름에 따라 어떻게 움직이는지에 관한 경향선을 그릴 때, 단순히 전후 몇일간의 평균으로만 계산하면 오래된 데이터의 영향과 최신 데이터의 영향이 비슷해져서 원하는 추세를 나타내지 못할 것이다. 이러한 문제를 해결하기 위해 weight 를 부여하는 방식이 도입되었는데, 최신의 데이터에 높은 weight 를 부여하고 과거의 데이터에 낮은 weight 를 부여하기 위해서 시간의 흐름(현재로부터 과거)에 따라 지수적으로 감소하도록 설계한 방식이다.
작년 London 에서의 일일 Temeperature 에 대한 data를 살펴보자.
| days | θ1 | θ2 | θ3 | ... | θ180 | θ181 | ... |
| temperature | 40°F | 49°F | 45°F | ... | 60°F | 56°F | ... |
위의 plot에서 data가 temperature 의 평균으로 움직이는 경향을 살펴보고자 한다.
아래와 같이 v 를 설정해보자.
v0 = 0
v1 = 0.9 * v0 + 0.1 * θ1
v2 = 0.9 * v1 + 0.1 * θ2
v3 = 0.9 * v2 + 0.1 * θ3
...
vt = 0.9 * vt-1 + 0.1 * θt
...
vt 를 지수함수로 이루어진 식으로 표현할 수 있다.
vt = 0.9^t * v0 + 0.1 * Σ(i=0 ~ t-1) 0.9^i * θt-i
이를 바탕으로 v를 plot 해보면 아래와 같다. (빨간선)
이와 같이 moving average가 nomarlize 되도록 할 수 있다.
vt 를 generalize 하면 아래와 같이 β로 표현할 수 있다. 여기서 상관계수의 합이 1이 되도록 해야 한다.
vt = β * vt-1 + (1-β) * θt
여기서 β가 작다는 것은 이전 moving average 값에 더 적은 가중치를 부여하고 현재 temperature 값에 더 많은 가중치를 부여한다는 의미이다.
그래서, β가 작아지면 아래와 같이 data 와 거의 흡사해지며 noise 가 더 많아진다.
temperature 변화에 더 빠르게 적응할 수 있다.
Exponentially weighted average에 대해서 더 자세하게 살펴보자.
vt = β * vt-1 + (1-β) * θt
v100 = 0.9 * v99 + 0.1 * θ100
v99 = 0.9 * v98 + 0.1 * θ99
v98 = 0.9 * v97 + 0.1 * θ98
...
v100 을 이전 값들을 이용해서 표현하면 아래와 같다.
v100 = 0.1 * θ100 + 0.9 * v99
= 0.1 * θ100 + 0.9 * (0.1 * θ99 + 0.9 * v98)
= 0.1 * θ100 + 0.1 * (0.9) * θ99 + (0.9)^2 * v98
= 0.1 * θ100 + 0.1 * (0.9) * θ99 + (0.9)^2 * (0.1 * θ98 + 0.9 * v97)
= 0.1 * θ100 + 0.1 * (0.9) * θ99 + 0.1 * (0.9)^2 * θ98 + ...
즉, 이전의 temperature 에 대한 가중치가 더 적고 이는 지수적으로 감소한다는 것을 확인할 수 있다. 가중치에 대한 그래프는 아래와 같다.
즉, vt 는 1일 때부터 t일 때까지의 daily temperature 값에 각각 지수적으로 증가하는 가중치를 곱하고 모두 더한 값이 된다.
그렇다면, 해당 average 값은 몇일간의 기록으로 계산된 값일까?
마찬가지로, β = 0.9 일 때를 생각해보자.
(0.9)^10 ≈ 0.35 이다. 이는 1/e 에 근사한다. (여기서 e는 자연상수 2.718....) 이는 10일이 지나면 약 1/3이 감소한다는 것을 의미한다.
이번에는 β = 0.98 일 때를 생각해보자.
(0.98)^50 ≈ 0.35 이다. 이는 1/e 에 근사한다. 이는 50일이 지나야 약 1/3이 감소한다는 것을 의미한다. 즉 현재 시점으로부터 지난 50일간의 temperature에 대한 평균이다.
규칙성에 의해서 1 / ( β-1) 이 구하고자 하는 기간임을 알 수 있다. 즉, β 가 작아지면 해당 average 값은 해당 시점으로부터 아주 적은 기간 동안에 대한 값이기 때문에 주어진 original data와 거의 흡사하며 noise 가 많이 발생한다는 사실을 알 수 있다. 앞서 봤던 plot 을 통해 확인할 수 있다.
실제로 어떻게 구현하는지 아래 pseudo 코드를 보자.
Vθ := 0
Vθ := β*v + (1-β) * θ1
Vθ := β*v + (1-β) * θ2
...
-----------------------
Vθ = 0
Repear {
get next θt
Vθ = β*v + (1-β) * θt
}
이러한 exponentially weighted average 의 장점은 v0 initialization 에 대한 코드 한줄과 최신 값에 기반한 공식을 가지고 그 값에 계속해서 덮어쓰기 때문에 memory 가 아주 적게 든다는 것이다.
Bias Correction
: 앞서 언급한 average 값을 더 정확하게 계산할 수 있게 해주는 기술이다.
앞서 봤던 예시에서 β = 0.9 일 때 exponentially weighted average 를 plot 해보면 아래와 같다고 했었다.
하지만, 실제로 v0 = 0 으로 초기화했을 때는 초기 값이 아주 작다.
vt = β * vt-1 + (1-β) * θt
v0 = 0
v1 = 0.9 * v0 + 0.1 * θ1
= 0.1 * θ1 = "4"
v2 = 0.9 * v1 + 0.1 * θ2
= 0.09 * θ1 + 0.1 * θ2
= 0.09 * 4 + 0.1 * 49 = 0.36 + 4.9 = "5.26"
...
아래와 같이 plot 이 된다.
그래서 vt = β * vt-1 + (1-β) * θt 에서 1 - β^t 를 나눠주면 이러한 문제를 해결할 수 있다. 이를 Bias correction 이라고 한다.
vt = {β * vt-1 + (1-β) * θt} / (1-β^t)
v0 = 0
v1 = (0.9 * v0 + 0.1 * θ1) / 0.1
= 4 / 0.1 = "40"
v2 = (0.9 * v1 + 0.1 * θ2) / 0.19
= 5.26 / 0.19 = "27.7"
...
이를 통해 green line이 red line 에 가깝게 plot 되도록 설정해줄 수 있다.
Gradient Descent with Momentum
cost function 을 optimize 하는 과정을 살펴보자. 아래 그림과 같이 global minimum (빨간점) 에 도달하는 과정에서 느리게 진동을 하게 된다.
수직적으로는 덜 진동하기를 원하고, 수평적으로는 빠르게 학습이 되기를 원한다.
Momentum(관성)은 변수가 가던 방향으로 계속 가도록 하는 속도(velocity) 항을 추가하는 것이다. 이로 인해 local minumum 문제를 해결해줄 수 있다.
이는 gradient 의 exponentially weighted average 를 구하고 weight 를 update하기 위해 그 gradient 를 대신해서 사용한다.
On iteration t:
Compute dw, db on the current mini-batch
Vdw = βdw + (1-β)dw
Vdb = βdb + (1-β)db
w = w - α*vdw, b = b - α*vdb
RMSprop
: 수직적으로는 더 약하게 진동하고, 수평적으로는 더 빠르게 학습을 할 수 있도록 하기 위해서 도입된 방식이다.
On iteration t:
Compute dw, db on the current mini-batch
Sdw = βSw + (1-β)*(dw)^2
Sdb = βSb + (1-β)*(db)^2
w = w - α*(dw/sqrt(Sdw)), b = b - α*(db/sqrt(Sdb))
수직적으로 더 큰 움직임을 갖고 있기 때문에 db^2 의 누적치는 더 큰 값을 갖게 되고, 반대로 수평적으로 상대적으로 더 작은 움직임을 갖고 있기 때문에 dw^2 의 누적치는 상대적으로 더 작은 값을 갖게 된다.
그래서, 각각을 나눠줌으로써 w를 더 큰 값으로 업데이트 되도록 하고, b를 더 작은 값으로 업데이트 되도록 한다.
Momentum과 RMSprop를 비교해보면 다음과 같다.
"Adam Optimization Algorithm"
: 앞서 봤던 Momemtum 과 RMSprop 을 합친 Algorithm 이다.
On iteration t:
Compute dw, db on the current mini-batch
Vdw = β1*Sw + (1-β1)* dw , Vdb = β1*Sb + (1-β1)* db # momentum
Sdw = β2*Sw + (1-β2)*(dw)^2 , Sdb = β2*Sb + (1-β2)*(db)^2 # RMSprop
Vdw = Vdw / (1-(β1)^t), Vdb = Vdb / (1-(β1)^t) # bias correction
Sdw = Sdw / (1-(β2)^t), Sdb = Sdb / (1-(β2)^t) # bias correction
w = w - α*(Vdw/(sqrt(Sdw)+epsilon)), b = b - α*(Vdb/(sqrt(Sdb)+epsilon))
여기서 epsilon 은 분모가 0이되는 것을 방지하기 위해서 추가적으로 더해주는 아주 작은 값이다. (epsilon = 10^(-8))
- α : 학습을 해보면서 어느 값에서 가장 잘 동작하는지 tuning 해줘야 하는 hyper parameter 이다.
- β1 : default 값은 0.9 이며, 권장되는 값이다. 마찬가지로 추가적으로 tunning 을 할 수 있는 hyper parameter 이다.
- β2 : default 값은 0.999 이며 권장되는 값이다. 마찬가지로 추가적으로 tunning 을 할 수 있는 hyper parameter 이다.
Learning rate decay
: 시간이 지남에 따라 learning rate 를 더 작게 만들어서 수렴하도록 해주는 것이다.
learning rate 를 다르게 하지 않은 mini-batch 상황에서는 noise 를 갖으면서 minimum 주위를 헤매게 될 것이다.
하지만, learning rate 를 시간이 지남에 따라 작게 하면, minimum 에 수렴하도록 만들어 줄 수 있다.
1 epoch 은 전체 data set 을 한번 training 한 것이다.
epoch 를 거듭하는 과정에서 learning rate 를 아래의 식을 사용해서 감소시킬 수 있다.
α = α0 / (1+decay_rate * epoch_num)
α0 = 0.2, decay_rate = 1 이라고 할 때 Epoch 에 따른 α 의 값을 살펴보자
| Epoch | α |
| 1 | 0.1 |
| 2 | 0.67 |
| 3 | 0.5 |
| 4 | 0.4 |
| ... | ... |
다른 방식도 물론 있다.
α = 0.95^(epoch_num) * α0 - exponentially decayα = (k * α0) / sqrt(epoch_num) or (k * α0) / sqrt(t) # t = mini-batch number
# k = constant
The problem of Local Optima
이전에 봤었던 cost function 의 그림은 아래와 같았다.
대부분의 cost function 의 경우는 위와 같지만, 항상 그렇지는 않다. 아래와 같이 local minimum 이 존재하는 경우가 있다.
cost function 의 값이 가장 작지는 않지만 gradient 가 0인 경우이다. 이를 local minimum 이라고 하며, 학습하는 과정에서 이를 global minimum 이라고 오인하는 문제에 빠질 수 있다.
'연구실 > 인공지능(Coursera)' 카테고리의 다른 글
| [AI 8주차] Convolution Neural Network (CNN) 기초 (0) | 2024.08.05 |
|---|---|
| [AI 7주차] Hyperparameter Tuning, Batch Normarlization, and Programming Frameworks (0) | 2024.07.26 |
| [AI 5주차] Deep learning의 실용적인 측면 (0) | 2024.07.02 |
| [AI 4주차] DNN(깊은 신경망) (0) | 2024.06.27 |
| [AI 3주차] Swallow Neural Network(얕은 신경망) (0) | 2024.06.27 |
