AI Math

경사하강법(1)

미분 (Differentiation)

• 미분은 변화율의 극한(함수의 순간 기울기)을 측정하기 위한 도구
  $f'(x)=\lim_{h→0}\cfrac{f(x+h)-f(x)}{h}$

• cf) 주요 함수에 대한 미분 (참고 - Youtube채널 동빈나)

  • 기본 미분 공식
    • $(constant)'=0$
    • $(ax^k)'=kax^{k-1}$
  • 지수 함수 미분 공식
    • $(e^x)'=e^x$
    • $(a^x)'=a^x\ln{a}$
    • $(e^{f(x)})'=e^{f(x)}*f'(x)$
    • $(a^{f(x)})'=a^{f(x)}*\ln{a}*f'(x)$
  • 로그 함수 미분 공식
    • $(\ln{x})'=\cfrac{1}{x}$
    • $(log_ax)'=\cfrac{1}{x\ln{a}}$
    • $(\ln{f(x)})'=\cfrac{f'(x)}{f(x)}$
  • 삼각 함수 미분 공식
    • $(\sin{x})'=\cos{x}$
    • $(\cos{x})'=-\sin{x}$
    • $(\tan{x})'=\sec^2{x}$

• 미분은 sympy.diff() 함수를 이용하여 계산할 수 있음

• 함수값을 증가시키고 싶으면 미분값을 더하고, 감소시키고 싶으면 미분값을 뺌

  • 함수의 부호에 따라 미분값도 함께 변하기 때문
  • 미분값을 더하면 경사상승법(Gradiend Ascent): 함수의 극대값 좌표 계산
  • 미분값을 빼면 경사하강법(Gradiend Descent): 함수의 극소값 좌표 계산. 목적함수 최소화
  • 위 두 방법은 극값에서 미분값이 0이 되므로 업데이트 종료

편미분 (Partial Differentiation)

• 편미분은 벡터가 입력되는 다변수 함수에서 사용
  $\partial_{x_i}f(x)=\lim_{h→0}\cfrac{f(x+he_i)-f(x)}{h}$
  (여기에서 $e_i$는 $x$의 $i$번째 벡터에만 영향을 주는 단위벡터)
• 각 변수별로 편미분을 계산한 Gradient Vector를 사용하여 경사하강/상승법에 사용 가능

경사하강법(2)

경사하강법(GD)으로 선형회귀 계수 구하기

• 선형회귀의 목적식은 $||y-X\beta||_2$ or $||y-X\beta||_2^2$이고, 이를 최소화하는 $\beta$를 찾아야 함

• 계산해야하는 Gradient Vector는 다음과 같음

  $\partial_{\beta_k}||y-X\beta||_2=\partial_{\beta_k}\Bigg\lbrace{\frac{1}{n}\sum_{i=1}^n\Bigg(y_i-\sum_{j=1}^{d}X_{ij}\beta_j\Bigg)^2} \Bigg\rbrace^{\frac{1}{2}}$

• 위 식을 정리하면, $\beta_k$에 대한 목적식의 편미분값을 $n$과 원래 목적식의 L2노름 값의 곱으로 나눈 값에 음수를 취해준 것과 같음.

  $=-\frac{X^T_{·k}(y-X\beta)}{n||y-X\beta||_2}$

  다시 말해, $X_\beta$를 계수 $\beta$에 대해 미분한 결과에 $X^T$를 곱해주는 것과 동일함.

• 이에 따라 목적식을 최소화하는 $\beta$를 구하는 알고리즘은 아래와 같음.

  $\beta^{t+1} \gets \beta^t + \frac{\lambda}{n}\frac{X^T(y-X\beta^t)}{||y-X\beta^t||}$

• $||y-X\beta||_2$ 대신 $||y-X\beta||_2^2$를 사용하면 식이 조금 더 간단해짐.

  $\beta^{t+1} \gets \beta^t + \frac{2\lambda}{n}{X^T(y-X\beta^t)}$

• 경사하강법 기반 선형회귀 알고리즘은 무어-펜로즈 역행렬처럼 정확한 수렴값을 찾는 것이 아니므로, "적절한" 학습률/학습횟수가 필요함.

  • 학습률과 학습횟수가 너무 낮으면 수렴하지 않고, 너무 높으면 알고리즘이 불안정해짐.

확률적 경사하강법(SGD)

• 경사하강법은 미분 가능하고, 볼록함수(Convex)에 대해서만 이론적으로 수렴이 보장됨. (eg. 선형회귀의 목적식 $||y-X\beta||_2$)

• 하지만 비선형회귀 문제는 목적식이 볼록하지 않을(Non-convex) 수 있기 때문에 수렴이 항상 보장되지 않고, 이에 따라 변형된 경사하강법이 필요함.

• 확률적 경사하강법(Stochastic Gradient Descent)은 전체 데이터를 사용하는 대신 데이터 일부를 활용하여 파라미터를 업데이트함.
  (학습률, 학습횟수 조정이 필요하므로 만능은 아니지만, 실증적으로 GD보다 낫다고 검증됨)

• Mini-batch SGD는 (전체 데이터)$\mathscr{D}=(X, y)$를 가지고 목적식의 Gradient Vector인 $\nabla_\theta{L(\mathscr{D}, \theta)}$를 계산함.
  ($L$: 목적식, $\mathscr{D}$: 전체 데이터, $\theta$: 주어진 파라미터)

• 또한 매번 다른 미니배치를 확률적으로 선택하여 사용하기 때문에 목적식의 곡선 모영이 바뀌게 되고, Non-convex한 곡선의 경우 Local Point의 결과값이 극소점|극대점을 확률적으로 탈출할 수 있다는 원리를 차용하였음.

회고

• 처음보는 수학기호들이 난무해서 어렵게 느껴졌던 부분인데, 생각보다 원리는 간단했다.
• Gradient Vector를 계산하는 방법만 익숙해지고, 실제 코드로 구현하는 연습을 좀 해봐야할 것 같다. 심화과제로 주어졌던 코드들은 주말에 뜯어보는 걸로...