📂최적화이론

수학에서의 경사하강법

정의 ¹

스칼라 함수 $\varphi : \mathbb{R}^{n} \to \mathbb{R}$ 을 비용 함수^{cost function}이라 한다. 비용 함수 $ \varphi ( \mathbf{x} )$ 의 극소값을 구하기 위해 $\mathbf{x} = \mathbf{x}_{n}$ 에서 $\varphi ( \mathbf{x}_{n+1} ) < \varphi ( \mathbf{x}_{n} )$ 를 만족시키는 $\mathbf{x}_{n+1}$ 를 찾는 알고리즘을 하강법^{descent method}이라 한다.

설명

$\varphi$ 를 비용 함수라고 부를만한 예로써 집을 한 채 짓는다고 하자. 집 한 채에 들어가는 자원은 목재, 석재, 철재, 유리, 인건비, 부동산 등등이 있을텐데 이는 결국 ‘얼마나 많은 돈을 써야하는가’의 문제로 귀결된다. 이 문제에서 $\varphi$ 는 각각의 자원을 성분으로 갖는 벡터를 비용이라는 스칼라로 매핑해주는 함수가 된다. 여기서 누구나 궁금해할만한 질문은 ‘그 최소비용이 얼마인가’하는 것이다. 한편 머신러닝 등에서는 비용 함수는 손실 함수라고도 부르는데, 이 경우 ‘실제 값과 예측 값의 차이가 가장 작아질 때가 언제인가’가 된다.

어떤 문제가 됐든 이를 수학적으로 추상화하면 ‘스칼라 함수의 최소값을 구하는 문제’로 요약할 수 있다. 하강법은 이 문제를 풀기 위해 $n$차원 매니폴드 상에서 스칼라가 극소값을 찾는 메소드다. 주의해야할 것은 최소값이 아니라 극소값이라는 것이다. $\varphi$ 가 컨벡스하다면 모르지만 일반적인 경우에서 하강법은 로컬 미니멈을 찾아낼 수 있을 뿐 그것이 글로벌 미니멈이라는 보장을 해줄 수 없다.

경사하강법

경사하강법은 여러가지 하강법 중에서도 가장 인기있는 메소드로써, 비용 함수의 그래디언트를 이용해 극소값을 찾는다. 이러한 방법의 실전적인 사용례를 알고 싶다면 머신러닝에서의 경사하강법에 대해 알아보는 게 좋다.

적절한 $\alpha>0$ 에 대해 $\mathbf{x}_{n+1} := \mathbf{x}_{n} - \alpha \nabla \varphi ( \mathbf{x}_{n} )$ 를 경사하강법이라 한다.

$- \nabla \varphi ( \mathbf{x}_{n} )$ 는 $\mathbf{x} = \mathbf{x}_{n}$ 에서 매니폴드가 가장 크게 감소하는 방향을 나타내므로 $\alpha$ 가 적절하다면 $\left\{ \mathbf{x}_{n} \right\}$ 는 극소점으로 수렴할 것이다.

다만 이 방법은 쉽고 간편한 한편 다른 메소드에 비해 수렴하는 속도가 빠르다고 하긴 어려우며, 일단 그리디 알고리즘이다. 다시 말해, 각 단계에서는 최선을 다해 감소해서 로컬하게는 가장 크게 감소하지만 글로벌하게 보았을 땐 별로 좋은 방법이 아닐 수 있다는 것이다.

코드

다음은 경사하강법을 R 코드로 구현한 것으로, 그래디언트를 구하기 위해 numDeriv 패키지를 사용했다.

library(numDeriv)
 
optimizer<-function(f,x0,alpha=0.01){
  while(abs(f(x0))>10^(-8)){
    x0<-x0-alpha*grad(f,x0)
  }
  return(x0)
}
 
z<-function(v){
  return((v[1]-2)^2+(v[2]-3)^2)
}
 
optimizer(z,c(0,0))
z(c(1.999945,2.999918))

위 코드를 실행시킨 결과는 다음과 같다.

위 결과는 아주 간단한 예제로써 $z(x,y) = (x-2)^2 + (y-3)^2$ 이 최소값을 갖도록 하는 점을 찾아냈음을 보여준다. 다음과 같은 곡면에서 $z$ 가 최소가 되는 점은 $(2,3)$ 이다.

같이보기

• 머신러닝에서의 경사하강법