Peer Session Badge

Gradient descent

  • Differentiation (미분)
    • 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구
    • 최적화에서 많이 사용하는 기법
    • 변화율(기울기)의 극한
    • $f^\prime(x) = \lim_{h\rightarrow0}{\frac{f(x+ h) - f(x)}{h}}$
    • sympy.diff()
  • 미분 활용
    • 함수 f의 주어진 점 (x, f(x)) 에서 접선의 기울기 구함
    • 이를 활용해, 어느 방향으로 움직여야 함수값이 증가/감소하는지 알 수 있음
    • 경사상승법(gradient ascent): 미분값을 더해가며 함수의 극대값의 위치를 구할 때 사용
    • 경사하강법(gradient descent): 미분값을 빼가며 함수의 극소값의 위치를 구할 때 사용 
        # gradient: 미분 계산 함수
  # eps: 알고리즘 종료 조건 (컴퓨터 계산 시 미분이 정확히 0이 되는 것이 불가능하기 때문에 설정하는 작은 수)
        
  var = init
  grad = gradient(var)
  while(abs(grad) > eps):
      var = var - lr * grad
      grad = gradient(var)
  • 변수가 벡터인 경우
    • $\partial_{x_i}f(X) = \lim_{h\rightarrow0}{\frac{f(X+ he_i) - f(X)}{h}}$
    • gradient vector: $\nabla f = (\partial_{x_1} f, \partial_{x_2} f, \dots, \partial_{x_d} f)$
    • gradient vector를 이용해 변수 x1 ~ xd를 동시에 업데이트 가능 
        # abs 대신 norm
  while(norm(grad) > eps):
      var = var - lr * grad
      grad = gradient(var)
  • 선형회귀분석
    • np.linalg.pinv 이용해 데이터를 linear model로 해석하는 선형회귀식을 찾을 수 있음 (L2 노름을 최소화)
    • 선형회귀의 목적식: $\Vert y - X\beta \Vert_2 \text{ (minimize } \beta)$
  • 경사하강법으로 선형회귀 계수 구하기
    • $\nabla_\beta\Vert y - X\beta \Vert_2 = (\partial_{\beta_1}\Vert y - X\beta \Vert_2, \dots, \partial_{\beta_d}\Vert y - X\beta \Vert_2)$

    • $\partial_{\beta_k}\Vert y - X\beta \Vert_2 = \partial_{\beta_k} \begin{Bmatrix} \frac{1}{n} \sum_{i = 1}^n \Big( y_i - \sum_{j = 1}^d{X_{ij}\beta_j} \Big) ^2 \end{Bmatrix} ^{1/2}$

      $= -\frac{X_{.k}^T(y - X\beta)}{n \Vert y - X \beta \Vert_2}$

      \[\begin{equation} \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} = \begin{bmatrix} x_{11} & x_{12} & \cdots && x_{1d} \\ x_{21} \\ \vdots \\ x_{n1} & & & & x_{nd} \end{bmatrix} \begin{bmatrix}\beta_1 \\ \beta_2 \\ \vdots \\ \beta_d \end{bmatrix} \end{equation}\]
    • $\beta^{(t + 1)} \leftarrow \beta^{(t)} - \lambda\nabla_{\beta} \Vert y - X\beta^{(t)} \Vert$ ($\lambda$: learning rate)
  • L2 norm에 제곱을 해서 식을 단순화하기
    • $\Vert y - X\beta \Vert_2$ 대신 $\Vert y - X\beta \Vert_2^2$ 최소화

    • $\nabla_\beta\Vert y - X\beta \Vert_2^2 = (\partial_{\beta_1}\Vert y - X\beta \Vert_2^2, \dots, \partial_{\beta_d}\Vert y - X\beta \Vert_2^2)$

      $= -\frac{2}{n}X^T(y - X \beta)$

    • $\beta^{(t + 1)} \leftarrow \beta^{(t)} -\frac{2\lambda}{n}X^T(y - X \beta^{(t)})$
      # Input: X, y, lr, T
  # Output: beta
  # norm: L2 norm 계산 함수, T: 학습횟수

  for t in range(T):
      error = y - x @ beta
      grad = - transpose(X) @ error
      beta = beta - lr * grad
  • 경사하강법 알고리즘에서 중요한 hyperparameter
    • learning rate
    • 학습횟수 (T)
  • 경사하강법
    • 이론적으로, 미분가능하고 convex한 함수에 대해 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장됨
    • 선형회귀의 경우 목적식이 회귀계수 beta에 대해 볼록함수이기 때문에 알고리즘을 충분히 돌리면 수렴 보장
    • 비선형회귀 문제의 경우 목적식이 non-convex일 수 있으므로 수렴 보장되지 않음

Stochastic gradient descent

  • 확률적 경사하강법 (SGD)
    • 모든 데이터를 사용해 업데이트하는 대신, 데이터 한 개 또는 일부(mini batch)를 활용해 업데이트
    • non-convex 목적식도 SGD를 통해 최적화 가능
    • 데이터의 일부를 가지고 파라미터를 업데이트하기 때문에 연산자원을 더 효율적으로 사용 $O(d^2n) \rightarrow O(d^2b)$
  • 경사하강법
    • 데이터: $D = (X, y)$
    • 목적식: $\nabla_{\theta}L(D, \theta)$
  • SGD의 데이터와 목적식
    • 데이터: $D_{(b)} = (X_{(b)}, y_{(b)}) \subset D$
    • 목적식: $\nabla_{\theta}L(D_b^{(t)}, \theta)$
  • 미니배치 SGD
    • 확률적으로 선택하므로 목적식의 모양이 계속 바뀜 (그렇기 때문에 non-convex의 최솟값도 찾을 수 있음)
    • 일반적으로 기존 경사하강법보다 학습에 효율적임
    • 데이터셋이 클 때 경사하강법처럼 모든 데이터를 업로드하면 out-of-memory 발생할 수 있음
    • SGD 미니배치의 경우 GPU에서 행렬 연산과 모델 파라미터를 업데이트하는 동안, CPU는 전처리와 업로드할 데이터를 준비할 수 있음