SGD(Stochastic Gradient Descent)

• $J(\theta) = E_{x,y \sim \hat{p}(data)}L(x,y,\theta) = \frac{1}{m}\sum_{i=1}^m L(x^{(i)},y^{(i)},\theta)$

  • $L(x,y,\theta)= -logp(y|x;\theta)$ (각각 데이터에 대한 Loss)

  ⇒ 우리의 Sample Data가 m개 있다고 하면, 데이터 m개에 대해서 Loss를 구하고 평균을 취한 것

우리는 $\theta$를 최적화해야하니, $\theta$에 대한 미분을 구해서 Gradient Descent해야하는 것이 일반적이다. (x와 y는 입력값과 예측결과값)

⇒ $\nabla_\theta J(\theta) = \frac{1}{m} \sum_{i=1}^{m}\nabla_{\theta}L(x^{(i)},y^{(i)},\theta)$

⇒ 각각의 데이터에 대한 그래디언트 로스를 더한 값

위 계산식에 대한 연산량은 $O(m)$이 되겠다.

만약 데이터 개수가 너무 크면 연산량이 그만큼 크게 된다.

이를 개선하기 위해 MiniBatch라는 개념을 사용한다.

$B = ({x^{(1)},...x^{(m')}})$ ⇒ 트레이닝 데이터셋에서 uniform 하게 m개의 데이터셋에서 데이터 m’개 만큼을 끌어온다.

• $g= \frac{1}{m'}\sum_{i=1}^{m'}\nabla_\theta L(x^{(i)},y^{(i)},\theta)$ ⇒ m’개 만큼의 손실함수의 합

⇒ 첫 미니배치만큼 Gradient Descent 반영하고 그 다음 미니배치만큼 Gradient Descent를 반영,… 쭉쭉쭉 끝까지 미니배치만큼 Gradient Descent를 반영한다. ($\theta_{i+1}= \theta_i-eg$)

• SGD는 GD보다 K배 더 빠르게 학습이 가능하다.
• SGD는 Local Minimum을 잘 빠져나오게 된다.
• SGD는 이외에도 좋은 영향을 끼치는 경우들이 많다.

The curse of Dimensionality

우리에게 주어진 Input의 Dimension이 많아지면 많아질 수록 추정하기 힘들어진다.