2 minute read

경사하강법

gradient

  1. 경사 상승법(극대값 찾기) - 경사를 증가시키고 싶으면 미분값을 더하고 (빨간색),
  2. 경사 하강법(극솟값 찾기) - 셩사를 감소시키고 싶으면 미분값을 빼준다(파란색)

변수가 벡터일 경우(다변수함수) 편미분을 사용한다.
\(\partial{x_{i}}f(x) = \lim_{h\rightarrow 0}\frac{f(x+he_i) - f(x)}{h}\) 를 이용하여 편미분을 계산한다. 편미분 예시)

\(f(x,y) = x^2 + 2xy + 3 + cos(x+2y)\)
\(\partial{x}f(x,y) = 2x + 2y - \sin{x+2y}\)

각 변수 별로 편미분을 계산한 그레디언트(gradient) 벡터를 이용해 경사 하강/상승 에 사용한다 (벡터에 - 값을 붙이면 최소점으로 향한다.)

\[\nabla{f} = (\partial_{x_1}f,\partial_{x_2}f,\cdots ,\partial_{x_d}f)\]

경사하강법 알고리즘

# gradient : 그레디언트 벡터를 계산하는 함수
# init: 시작점, lr: 학습률, eps: 알고리즘 종료조건

var = init
grad = gradient(var)
while(norm(grad) > eps):
  var = var - lr * grad
  grad = gradient(var)

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

선형회귀 목적식 \(||y-X\beta||_{2}\) 이고 이를 최소하 하는 \(\beta\) 를 찾아야 한다.

\[\nabla{\beta}||y-X\beta||_2 = (\partial_{\beta_{1}} ||y-X\beta||_2, \cdots, \partial_{\beta_{d}} ||y-X\beta||_2)\]

위의 식을 사용하여도 되지만 좀더 쉽게 계산 위해 목적식 \(||y-X\beta||_{2}^{2}\) 사용.

\(\nabla{\beta}||y-X\beta||_{2}^{2} = (\partial_{\beta_{1}} ||y-X\beta||_{2}^{2}, \cdots, \partial_{\beta_{d}} ||y-X\beta||_{2}^{2})\) \(-\frac{2}{n}X^{T}(y-X\beta)\)

목적식을 최소화하는 \(\beta\)를 구하는 알고리즘

\[\beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{2\lambda }{n}X^{T}(y-X\beta^{(t)})\] 
# lr : 학습률
# T : 학습횟수
for t in range(T):
  error = y - X @ beta
  grad = -transpos(X) @ error
  beta = beta - lr * grad

확률적 경사 하강법(Stochastic gradient descent)

  • 모든 데이터 대신 한개 또는 일부를 활용하여 업데이트함 (연산자원을 효율적으로 활용)
  • 볼록이 아닌 목적식은 SGD를 통해 최적화 한다
  • 통상 부를 때 SGD하면 미니배치 SGD를 의미함
  • (x,y)를 쓰지않고 미니배치 (\(X_{b}, y_{b}\)) 를 써서 업데이트하면 연산량이 b/ 으로 감소함.
  • 미니배치는 확률적으로 선택하므로 목적식 모양이 바뀌게 됨.

Comments

You May Also Enjoy