Day 8: Day 8 일변수 최적화 문제와 경사하강법

목차로 돌아가기

본 글은 인공지능을 활용하지 않고 작성된 글임을 알립니다.

일변수 최적화 문제

앞서 살펴본 예시에서 중학생 철수의 뇌에는 수많은 시냅스 연결 상태가 하나의 벡터 $\theta$로 표현되었고, 우리는 이 벡터를 변경해가며 최적해 $\theta_0$를 찾는 중에 있다. 너무 복잡한 상황이므로, 먼저 간단하게 만들어서 최대한 쉽게 바라볼 필요가 있다. 따라서 가장 쉬운 경우인 $n=1$인 케이스부터 다뤄보자. 일변수함수 $f(\theta)$를 어떻게 최적화할 수 있을까? 아래의 표준형 최적화 문제를 살펴보자.

\[\begin{equation}\begin{aligned}& \underset{\theta \in \mathbb{R}}{\text{minimize}}& & f(\theta)=\theta^2 \end{aligned}\end{equation}\]

$\text{subject to}$ 문구가 없으므로 제약 조건은 특별히 없는 상태다. 우리는 위의 함수를 최소화하는 문제를 이미 중학교 때 해결해 본 경험이 있다. 그때는 실수의 제곱 $x^2$이 항상 $0$ 이상이고, $x^2=0$이 되는 필요충분조건이 $x=0$이라는 사실을 받아들이고 사용했을 것이다. 이 두 사실을 알고 있다면 $x^2$의 최솟값이 $0$이라는 사실은 쉽게 도출된다.¹ 고등학교 수준으로 올라가면 이계도함수 판정법과 같은 조금 더 고차원적인 도구들을 활용하여 위의 문제를 접근하는 것도 가능해진다. (아니면 그냥 저 함수의 최솟값이 $0$이라는 사실을 외워버렸을 수도 있겠다…)

아무튼 위의 케이스는 너무 간단한 케이스라 최적해를 찾는 것이 그다지 어려운 일이 아니다. 하지만, 현실 문제는 이처럼 간단하지 않고 공식으로 외울 수 있는 최적해따윈 존재하지 않는 경우가 대부분이다. 미분해서 $0$이 되는 지점을 살펴보는 것은 그나마 일반적인 상황까지 적용할 수 있는 강력한 방법 중 하나이지만, 방정식 $f’(\theta)=0$이 일반해를 찾을 수 없는 방정식이라면 이또한 무용지물이지 않은가?² 그러니 위 사실을 모르는 상황에서도 최적화 문제를 해결할 수 있는 방법이 필요하다. 함수의 형태에 구애받지 않고 함수값을 최소화하려면 어떤 방법을 사용해야 할까?

일변수 경사하강법

$f’(\theta)=0$이 되는 지점을 전체 실수 구간에서 탐색하는 것은 어렵지만, 한 지점에서의 $f’(\theta)$을 계산하여 그 부호를 확인하는 것은 쉽다. 따라서 $f’(\theta)$가 $0$보다 크면 $\theta$를 조금 작게 하고, $f’(\theta)$가 $0$보다 작으면 $\theta$를 조금 키우는 과정을 계속 반복해보자. 이 과정을 계속하다보면 $f(\theta)$는 계속 작아지게 된다.

이 과정을 수식으로 표현하면 아래와 같다:

\[\begin{equation}\theta^{(k+1)}=\theta^{(k)}-\alpha\:\text{sgn}\:f'(\theta^{(k)}) \end{equation}\]

여기서 $\alpha$는 충분히 작은 양수이고, $\text{sgn} \;\cdot$이라고 나타낸 것은 $\cdot$의 부호를 뜻한다.³ 또한, $\theta^{(k)}$라고 적은 것은 $k$번째 단계step에서의 $\theta$를 의미한다. 앞서 이야기한 직관이 틀리지 않았다면, 실변수 $\theta$는 가장 처음 단계인 $k=0$ 단계에서 초기값 $\theta^{(0)}$로 출발하여, 위의 재귀식recurrence relation에 의해 최소값을 향해 점차 다가갈 것이다. 구체적으로, $f(\theta)$가 이상한 함수가 아니라면 $\theta$는 $f(\theta)$의 골짜기 지점인 $\theta=0$로 다가가게 된다. $k$의 값이 증가함에 따라 $\theta^{(k)}$가 (일반적으로) 감소할 것임을 확인해보자.

하지만, 위의 방식에는 한 가지 문제점이 있다. $\alpha\:\text{sgn}\:f’(\theta^{(k)})$의 크기

\[\left|\alpha\:\text{sgn}\:f'(\theta^{(k)})\right|=\left|\alpha \cdot(\pm1)\right|\]

는 항상 $\alpha$이기 때문에, 최소값에 다다를 때 즈음에도 계속 크기-$\alpha$의 step-size로만 $\theta^{(k)}$를 변경하게 된다. 즉, 최소값 근처에 다가갈 때는 서서히 감속하여 정확한 위치에 수렴할 수 있도록 해야 하는데, 부호만을 따지는 위의 상황에서는 최소값으로 수렴하지 못하고 크기-$\alpha$로 진동하게 되는 것이다!

한편, 최소값 근처에 다가왔다는 것은 $\lvert f’(\theta)\rvert$의 크기가 작아졌다는 사실, 즉 $f’(\theta)$이 $0$에 가까워졌다는 것으로부터 짐작할 수 있다. 이 정보를 활용하여 위의 식을 개선할 수는 없을까? 사실 곰곰히 생각해보면 $f’(\theta^{(k)})$가 이미 부호를 가지는 실수이기 때문에 $\text{sgn}$ 함수를 반드시 사용할 필요는 없을 것 같다. 따라서 $\text{sgn}$ 함수를 제거하면 아래의 식을 얻는다:

\[\begin{equation} \theta^{(k+1)}=\theta^{(k)}-\alpha f'(\theta^{(k)}) \end{equation}\]

위의 식은 앞선 식 $(3)$에서 step-size가 $\alpha$로 고정되어 있는 문제를 해결한다. $f’(\theta^{(k)})$의 크기(절대값)가 감소하면 $\alpha f’(\theta^{(k)})$의 크기도 감소한다. 움직이는 방향은 이전 경우와 똑같이 $f$의 값을 감소시키는 방향이다. 따라서 좀 전의 진동 문제는 어느 정도 해결된 듯하다. 식 $(4)$와 같은 방식으로 함수를 최적화하는 것을 경사하강법Gradient Descent, GD이라고 부른다.

$f(\theta)=\theta^2$와 같이 간단한 함수의 경우에는 (놀랍게도) 고등학교에서 배우는 수열과 미분의 개념만을 활용하여 $\theta^{(k)}$가 $f(\theta)$의 값이 가장 작아지는 $\theta=0$ 상태로 수렴할 조건을 구하고 증명할 수 있다. $\alpha=0.01$로 두고, $\theta^{(0)}=1$에서 출발한다고 가정하자. $f’(\theta)=2\theta$이므로 이를 기존 식에 대입하면

\[\begin{equation} \begin{aligned} \theta^{(k+1)}&=\theta^{(k)}-0.02\:\theta^{(k)}=0.98\:\theta^{(k)}, \newline \theta^{(k)}&=0.98^k, \newline \theta^{(0)}&=0.98^k. \end{aligned} \end{equation}\]

$0<0.98<1$이므로, 실수열 $\theta^{(k)}$는 $k$가 $\infty$로 갈 때 $0$으로 수렴한다.

\[\theta^{(k)}=0.98^k \rightarrow 0 \;\;\text{as}\;\; k\rightarrow \infty.\]

하지만 $\alpha$의 크기가 너무 클 경우에는 $\theta^{(k)}$의 수열이 발산할 수도 있다! 예를 들어, $\alpha=2$이고 $\theta^{(0)}=1$로 동일한 경우에는

\[\begin{equation}\begin{aligned}\theta^{(k+1)}&=\theta^{(k)}-4\:\theta^{(k)}=(-3)\,\theta^{(k)},\newline \theta^{(k)}&=(-3)^k \theta^{(0)}=(-3)^k .\end{aligned}\end{equation}\]

위의 경우 실수열 $\theta^{(k)}$는 $k$가 $\infty$로 갈 때 진동하며 발산한다.⁴

\[\theta^{(k)}=(-3)^k \;\;\text{oscillates as}\;\; k\rightarrow \infty.\]

문제 2.1

$f(\theta)=\theta^2$에 경사하강법을 적용할 때, $\theta^{(k)}$가 최적해 $\theta=0$으로 수렴하기 위한 $\alpha, \theta^{(0)}$의 조건은 무엇인가? 단, $\alpha>0$이다.

• 정답

  $0<\alpha<1$ 또는 $\theta^{(0)}=0.$

문제 2.2

$f(\theta)=(\theta+3)^2$에 경사하강법을 적용해보자. 구체적으로, $\alpha=0.7$로 두고 $\theta^{(0)}=-4$인 조건에서 출발하여 식 $(4)$에 의해 $\theta$의 값을 업데이트한다고 할 때, $\theta^{(0)}$부터 $\theta^{(30)}$까지의 $\theta$값을 리스트로 만든 다음 print()함수를 이용하여 출력하시오.

• 정답

    # 코드
      
    alpha = 0.7
    theta = -4
    thetas = []               # 비어있는 리스트 생성
    thetas.append(theta)      # 초기 theta 값 저장하기
    for i in range(30):
        theta = theta - alpha * (2 * (theta + 3))  # 경사하강
        thetas.append(theta)
    print(thetas)             # theta값 출력
  

    # 출력값
      
    [-4, -2.6, -3.16, -2.936, -3.0256, -2.98976, -3.004096, -2.9983616, -3.00065536, -2.999737856, -3.0001048576000002, -2.9999580569599997, -3.000016777216, -2.9999932891136, -3.00000268435456, -2.999998926258176, -3.0000004294967297, -2.9999998282013083, -3.0000000687194768, -2.9999999725122093, -3.0000000109951164, -2.9999999956019536, -3.0000000017592185, -2.9999999992963127, -3.000000000281475, -2.99999999988741, -3.000000000045036, -2.9999999999819855, -3.000000000007206, -2.999999999997118, -3.000000000001153]
  

---