Day 9: Day 9 국소 최소점과 전역 최소점

본 글은 영어로 최초 작성되었으며, Notion AI 기능을 활용하여 한국어로 번역되었음을 알립니다.

국소 최소점과 전역 최소점

Untitled

함수 $f(\theta)$의 국소 최소점local minimum $\theta_\text{local}$은 자신의 근방¹에 있는 모든 점에 대해 $f(\theta)\ge f(\theta_\text{local})$을 만족하는 점이다. 일변수 실함수 $f$를 그린 위의 그래프에서 가로축을 $\theta$-축으로 둘 때, $\theta=0$과 $\theta=10$은 자신의 근방에 있는 점들보다 항상 함수값이 작기 때문에 국소 최소점이다. 최소점에서의 함수값을 최소값이라고 한다. 따라서, 함수 $f$는 국소 최소점 $\theta=0$에서 국소 최소값 $f(0)=0$를 가지고, 국소 최소점 $\theta=10$에서 국소 최소값 $f(10)=50$을 갖는다.

한편 함수 $f(\theta)$의 전역 최소점global minimum $\theta_\text{global}$은 정의역 내의 모든 점에 대해 $f(\theta)\ge f(\theta_\text{global})$을 만족하는 점이다. 위의 경우 $\theta=0$은 국소 최소점이면서 전역 최소점이다. 하지만 $\theta=10$은 국소 최소점이지만 전역 최소점은 아니다. $\theta=0$에서의 함수값 $f(0)=0$가 $\theta=10$에서의 함수값 $f(10)=50$보다 작기 때문이다.

앞서 언급한 경사하강법을 함수 $f(\theta)=\theta^2$에 적용하였을 시에는 $\alpha$가 충분히 작기만 하다면 $\theta^{(k)}$가 최적해인 $\theta=0$을 향해 잘 수렴한다는 것을 확인할 수 있었다. 하지만 $f(\theta)=\theta^2$는 국소 최소점이 유일하고 $\theta$가 $\pm \infty$로 갈 때 $\infty$로 발산하기 때문에 국소 최소점=전역 최소점인 경우이다. 하지만, 위의 그래프에서와 같이 국소 최소점이 여러 개인 함수를 $f$로 둘 경우 어느 최소점이 전역 최소점이 될지는 모른다.

예를 들어, 어떤 경우에는 회사의 수익 구조가 현재 구조에서의 약간의 수정(점진적 개선)으로 좋아지기 힘들 수 있다. 회사가 현재 수익 구조를 약간만 수정할 경우에는 어떻게 수정하더라도 수익성이 악화되기만 한다면 회사는 구조를 전면으로 재검토하여 완전히 갈아엎어야 더 큰 수익 창출을 기대할 수 있다. 이는 일종의 국소 최소점으로부터 탈출하기 위한 노력으로 해석될 수 있다. 또 다른 예시로는 학습 과정 중 발생하는 오개념이 있다. 오개념이 있더라도 해석하고자 하는 현상이 잘 설명되는 경우도 있지만, 결국 더 많은 정보를 접할수록 오개념으로부터 탈피하여 다시 학습하는 것이 현상을 설명하는 능력을 키우는 것에 있어서 더 효과적이다. 즉, 오개념(국소 최소점)을 탈출하여 현상을 더 잘 설명하는 제대로 된 개념(전역 최소점)을 다시 학습하는 것이 더 바람직하다.

경사하강법은 적절한 가정 하에 국소 최소점으로의 수렴은 보장하지만, 전역 최소점으로의 수렴은 보장하지 않는다.² 그래서 Momentum이나 Adam과 같이 관성항을 추가하여 얕은 국소 최소점을 빠져나와 더 깊은(함수값이 더 작은) 전역 최소점을 향해 찾아가는, 경사하강법을 비롯한 최적화 알고리즘이 개발되었다. Momentum, Adam과 같이 다양한 종류의 최적화 기법을 탐구하고 싶다면 아래의 블로그 글을 참고하자.

Optimizer의 종류와 간단한 정리

문제 3.1

4차 함수 $f(\theta)=\theta^2(\theta-1)(\theta-2)$에 대하여,

(a) 국소 최소점을 구하시오.

(b) 전역 최소점을 구하시오.

정답

(a) 국소 최소점: $\theta=0,\;\theta=\frac{9+\sqrt{17}}{8}\approx1.640$

(b) 전역 최소점: $\theta =\frac{9+\sqrt{17}}{8}\approx1.640$

(c) $f(0)=0$

문제 3.2

위의 4차 함수 $f(\theta)=\theta^2(\theta-1)(\theta-2)$에 경사하강법을 적용해보자.

(a) $\alpha=0.05$로 두고 $\theta^{(0)}=3$인 조건에서 출발하여 식 $(4)$에 의해 $\theta$의 값을 업데이트한다고 할 때, $\theta^{(0)}$부터 $\theta^{(30)}$까지의 $\theta$값을 리스트로 만든 다음 print()함수를 이용하여 출력하시오.

(b) $\theta$가 전역 최소점으로 수렴하는지 확인하고, 만일 전역 최소점으로 수렴한다면 $f(\theta^{(k)})$의 수렴값을 구하시오.

정답

(a)

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

  # 출력값
    
  [3, 1.0499999999999998, 1.1045999999999998, 1.1631899369327998, 1.2246451065084327, 1.2872724414731267, 1.3488794094514513, 1.4070169240305987, 1.4593836892273668, 1.5042779940878397, 1.540914144056721, 1.5694643322257227, 1.5908330465698923, 1.6063037620026415, 1.6172175322689708, 1.6247689357696435, 1.629921406541151, 1.6334027143439558, 1.6357390290643616, 1.6372997348435627, 1.6383390867159184, 1.6390298045931315, 1.6394881953333464, 1.6397921226262633, 1.6399935122140699, 1.640126903506169, 1.6402152319777135, 1.6402737104854812, 1.6403124220218963, 1.6403380462312662, 1.640355006705482]

(b)

전역 최소점 1.640으로 수렴하고 있음을 확인할 수 있다. 이때의 함수값을 구하려면

  # 코드
    
  theta_global = thetas[30]  # 30번째 theta가 전역 최소값에 충분히 가깝다고 가정
  print(theta_global**2 * (theta_global - 1) * (theta_global - 2))

  # 출력값
    
  -0.6196843457001793

(c)

$\theta^{(0)}=-1$로 코드를 돌리면

  # 출력값
    
  [-1, -0.1499999999999999, -0.10919999999999994, -0.08173347786239996, -0.06227141782417553, -0.0480238616518109, -0.037359106839121914, -0.029248790740098913, -0.023009056880295777, -0.018166571714116383, -0.01438354734163941, -0.011413143825789467, -0.00907160079235181, -0.0072200990529043794, -0.0057525455421655915, -0.004587107060241312, -0.0036601976461915, -0.002922119638721227, -0.0023338482682754252, -0.001864624990714408, -0.0014901341241158653, -0.0011911074126556803, -0.0009522471605601266, -0.0007613895071587255, -0.0006088506461576267, -0.00048691365718682596, -0.00038942421445218494, -0.00031147111670195584, -0.0002491332309026941, -0.00019927865131451355, -0.00015940504907746946]

국소 최소점이지만 전역 최소점은 아닌 $\theta=0$ 지점으로 수렴하고 있음을 확인할 수 있다.

한 점의 ‘근방’은 그 점을 포함하는 개구간을 의미한다. ↩
구체적으로, 함수 $f$가 미분가능하고 도함수 $f’$이 $L$-립시츠 연속$L$-Lipschitz continuous인 조건 하에서 $0 < \alpha < 2/L$인 경우에만 $f’$이 $0$으로 수렴함을 보장할 수 있다. 여기에 더하여 $f(\theta^{(k)})$가 국소 최소값으로 수렴하기 위해서는 함수 $f$가 안장점saddle point을 가지지 않는다는 조건 등이 추가되어야 할 것이다. ↩