[Optimization Algorithms] Gradient Descent (1) Batch, Stochastic, Mini-batch Gradient descent 배치, 확률적, 미니배치 경사하강법

[모델의 파라미터를 업데이트하는 방법 옵티마이저] - 배치/확률적/미니배치 경사하강법 개념과 차이를 정리합니다.

Optimization Algorithms

0. Gradient Descent - How it works
1. (Batch) Gradient Descent (배치)경사하강법
2. Stochastic Gradient Descent (SGD) 확률적경사하강법
3. Mini-Batch Gradient Descent 미니배치경사하강법

Optimization Algorithms

최적화 알고리즘은 비용함수를 최소화하는 파라미터 $w,b$를 구하는데 사용된다. optimizer generates a new and improved guess. how good or how badly the guess was done using the data from the loss function.

신경망 모델 훈련에 사용되는 최적화 알고리즘은 경사하강법을 시작으로 다양한 옵티마이저가 존재한다.

Gradient Descent (GD) 경사하강법

경사하강법은 비용함수를 최소화하는 파라미터 $w,b$를 찾는 방법 중 하나이다. 비용함수의 최솟값을 모르기 때문에 임의의 점을 골라 시작하게 되고, 가장 가파른 방향인 비용함수의 기울기를 따라 global minimum을 찾아 이동하면서, 모델의 파라미터 $weight, bias$를 업데이트한다.

Gradient Descent starts at an initial parameter and repeatedly takes small steps in the direction that minimizes COST FUNCTION to find the optimal set of parameters for a function, for which the function attains its *global minimum***.

Gradient Descent

$\theta=\theta-\eta \nabla_{\theta} J(\theta)$

• $J(\theta)$ : loss function, $\nabla_{\theta} J(\theta)$ : derivative, $\eta$ : learning rate

$w := w – \alpha \frac{\mathrm{d} J(w,b) }{\mathrm{d} w}$
$b := b – \alpha \frac{\mathrm{d} J(w,b) }{\mathrm{d} b}$

• $\alpha$ : Learning Rate 학습률, 얼만큼의 스텝으로 나아갈지를 결정한다. how big step we take on each iteration of Gradient Descent.
• $dw$ $= \frac{\mathrm{d} J(w) }{\mathrm{d} w}$ : Derivative, 도함수, 함수의 기울기
  어떤 함수의 기울기 도함수 는 변수 w를 조금만 변화했을 때, 함수 f(w) 가 얼만큼 변하는지는 측정하는 것이다.
  • $dw$ > 0 : 파라미터 w는 이전의 w값보다 작은 방향으로 업데이트
  • $dw$ < 0 : 파라미터 w는 이전의 w값보다 큰 방향으로 업데이트

다음 일련의 과정들을 반복적으로 수행한다.

1. Initialize random weight and bias.
2. Pass an input through the network and get values from the output layer.
3. Calculate the error between the actual value and the predicted value.
4. Go to each neuron which contributes to the error and then change its respective values to reduce the error.
5. Reiterate until you find the best weights of the network.

미분값이 0인 점을 바로 찾지 않고 경사하강법을 사용하는 이유 ?

Cost function의 형태가 convex 형태라면 경사하강법 대신 미분값이 0이되는 해를 찾는 closed form solution을 이용하면 된다. 그러나 신경망과 같이 non-linear의 경우, closed form solution이 존재하지 않거나 혹은 존재하더라도 경사하강법으로 연산하는 것이 효율적이기 때문이다.

(Batch) Gradient Descent (배치)경사하강법

Batch Size = Size of Training Set

• All training samples are used to create 1 batch.
• 1 iteration 마다 전체 훈련 데이터에 대한 gradients를 계산하고 파라미터를 업데이트한다.
• 1 iteration마다 전체 데이터를 다루기 때문에 학습속도가 매우 느려질 수 있어 큰 데이터에는 적합하지 않다.

Stochastic Gradient Descent (SGD) 확률적경사하강법

Batch Size = 1 (sample)

• Calculate the gradient for a single training sample and update parameters. 1 iteration마다 전체 학습세트가 아니라 하나의 학습 샘플에 대해서만 gradient를 계산하고 파라미터를 업데이트한다.
• Stochastic 은 mini-batch가 전체 훈련 데이터에서 무작위로 선택됨을 의미한다.
• as it uses just a single example at a time cannot use vectorized operations ⇒ computations much slower

SGD vs GD

• 훈련세트가 클 때, SGD는 각 단계를 계산하는 속도가 GD보다는 빠르지만, 파라미터 업데이트 전 1개의 훈련 샘플만 사용하기 때문에 매끄럽게 수렴하지 않고 oscillate toward the minimum 진동문제가 존재한다.
  • Noise can be reduced by using smaller learning rate

Mini-Batch Gradient Descent 미니배치경사하강법

1(sample) < Batch Size < Size of Training Set(Samples)

• 전체 훈련 샘플을 작은 훈련 세트인 mini-batch 미니배치에 대해 gradients를 계산하고 파라미터를 업데이트한다.
  • mini-batch : intermedieate number of examples, subset of the training set
  • mini-batch 사이즈는 하이퍼파라미터로, 2의 제곱수(~GPU 메모리 관련)일 때 훈련 속도가 가장 빠르기 때문에 일반적으로 64-512 사이 값을 사용한다.
• Random shuffling of training set ⇒ Partition
  
• if the dataset does not divide evenly by the batch size then the final batch has fewer samples than the others.

Mini-Batch Size

• 일반적으로 Mini-Batch Size가 작을수록 모델의 성능이 좋고 iteration마다 연산이 적기 때문에 속도가 빠르다.(Rule of thumb)
• 그러나 Mini-Batch Size가 작을수록 전체 훈련 데이터의 특징을 반영하기 어려울 수 있다.

SGD vs Mini-Batch GD

a single sample at a time vsbatches of 10-1000 data points at a time

• a mixture of BGD and SGD : Mini-Batch GD $=$ (BGD) to obtain smoother curves and converge directly to the minimal $+$ (SGD) for huge datasets as it converges faster
• Mini-Batch GD는 SGD의 noise를 줄이고 BGD보다 효율적으로 훈련한다.

Summary 📌

(Mini) batch size	Optimization Methods
mini batch size = m	Batch gradient descent
mini batch size = 1	Stochastic gradient descent (SGD)
mini batch size = between 1 and m	Mini-batch gradient descent

1. Batch gradient descent 배치 경사하강법 : 한 번의 iteration/epoch 시간이 길다.
2. Stochastic gradient descent (SGD) 확률적 경사하강법
   • 비용함수 최소값 탐색 과정이 큰 진동으로 too noisy 비효율적이다.
   • 벡터 연산을 활용하지 못해 연산 속도가 느릴 수 있다.
   • 진동으로 최소값에 수렴하지 않는다.
3. Mini-batch gradient descent
   • full-batch가 아닌 mini-batch를 사용해 보다 빠른 훈련이 가능하다.
   • 여전히 진동이 존재하기 때문에 정확히 수렴하지 않을 수도 있다.
   • 전체 훈련 데이터에 대해 미니배치 사이즈를 어떻게 선택하느냐에 따라 학습 속도에 차이가 있고, 최적의 값을 찾아내는 것이 중요하다. Make sure that mini-batch(a power of 2) fits in CPU/GPU memory. CPU/GPU 메모리에 맞는 미니배치 사이즈 2의 제곱수를 설정하는 것이 좋다.

• 훈련세트가 작은 경우 (2000개 이하) 배치경사하강법을 사용하고, 이보다 클 경우 미니배치 경사하강법을 사용한다.

---

Source&Reference : interview preparation materials, Optimizers