이전 포스팅의 수치최적화법에서 한단계만 더 나아가자!
이정도 이해 할 수 있다면 수치 최적화법은 상당부분 개념을 잡은 것이니 머신러닝의 optimization을 이야기 할때 굉장히 유용한 양분이 될것이다. Newton method가 뭔지 모른다면 이전 포스팅을 참고하자.
>> 이전 포스팅 바로가기 Newton method
수치최적화법 - Newton method(Gradient descent) #1
중학교 2학년때쯤인가 교육과정에서 이차함수를 배우는 것으로 기억한다. $ax^{2}+bx+c=0 \qquad eq.1$ 꼭지점좌표, 위로볼록, 아래로볼록 등등 여러 이차함수의 함수형태를 배웠지만, 식 1을 만족시키
toddlemillionaire.tistory.com
지난 포스팅을 요약하자면,
1. 해석적으로 풀 수 없는 문제는 수치적으로 문제를 푸는것이 효과적이다.
2. 수치방식으로 특정 함수값을 구하는 방식으로 Newton 반복(iteration) 방식을 이용한다.
그 예시로 이차함수 같은 볼록한 함수에서 함수값이 0이되는 지점을 찾는 방법으로 Newton 반복법을 단계별로 확인하였고 간단한 코드까지 구비를 하였다.
이번에 사용할 재료함수는 4차 다항식으로 풀어보겠다.
(이차함수는 너무 쉬우니까 재미없을거다. 분명 재미없을거다.)
자! 아래 함수가 한동안 가지고 놀 재료함수의 식과 개형이다.
$f(x) = x^4-11.2x^3+44.25x^2-72.45x+43. \qquad eq.1$
"독자 여러분, 이 함수의 최소값을 구해보세요!"라고 문제를 툭 던지면 여러분은 손으로 바로 풀 자신이 있는가? 쉽지않다. 소수점으로 지저분하게 엮여진 함수니까 인수분해도 하기 쉽지않고 대략 $x=4$ 지점쯤에서 어렴풋이 제일 작은값 같긴한데 확신이 서지 않는다.
위 함수의 최소값은 무조건 극값(1차 미분함수가 0인 지점)에서 결정된다는 전제가 있다. 감소할대로 감소하고감소하다가 증가하는 바로 그 지점이 함수의 최소값이 결정되는 부분이다. 애석하게도 위 4차함수는 최소값처럼 보여지는 지점인 극값이 2개가 있으므로 두 지점의 대,소비교를 명확히 해야한다(하나는 진짜 최소값, 나머지는 진짜처럼 보이는 국부 최소값이라고 하는데 영어로 local minima라고 한다 - 최적화 문제에서 한계로 지적되는 부분이다).
여튼 위 문단의 글을 보고 생각해보면 우리는 원래함수를 그냥 사용하기보다 1차 미분함수가 0이되는 지점을 찾음으로 최소값을 찾는 방식으로 문제를 접근해도 된다는 말로 연결된다.
$x_{t+1} {\leftarrow} x_{t} - {{f'(x_{t})}\over{f''(x_{t})}}. \qquad eq.2$
식 2의 분모는 1차함수를 한번 더 미분한 2차 미분함수가 된다. 이전 포스팅을 복습한다 셈치고 4차함수의 문제를 한번 풀어보자. 그런데, 생각해보니 수치미분에 대해서 한번 언급해주는 것도 좋겠다는 생각이 들어서 말한다.
잠시 수치최적화법에서 벗어나 수치 미분이야기를 할 것이므로 머리 아플 것 같으면 지금 문단은 건너뛰어도된다.
미분은 매우 작은구간에서 함수의 변화량을 의미하는 연산으로 수학적으로 표현하면 다음 식으로 정의된다.
$f'(x)={{df(x)}\over{dx}}$
${\qquad}= \lim\limits_{h \to 0}{{f(x+h)-f(x)}\over{h}} \qquad eq.3$
식 3은 해석적인 방식의 미분식이다. 하지만 실제로 극한 연산은 시뮬레이션을 할 수 없는 개념이므로 극한의 미분식을 근사법인 유한차분(Finite differential)방식으로 작성하면 다음과 같다.
$f'(x) = {{f(x+\Delta x)-f(x)}\over{(x+\Delta x) - x}} \qquad eq.4$
식 4를 다음과 같이 적절히 변형이 가능하다.
$x+\Delta x = x+{{f(x+\Delta x)-f(x)}\over{f'(x)}} \qquad eq.5$
식 5의 오른쪽 항 중 $f(x+\Delta x)$를 0으로 치환해보면 식 5를 다음과 같이 쓸 수 있다.
$x+\Delta x \leftarrow x-{{f(x)}\over{f'(x)}} \qquad eq.6$
식 6의 $x+\Delta x$를 수치 반복법의 다음회 차시의 $x_k+1$, $x$를 이번회 차시 $x_k$라고 표현하면 이전 포스팅의 식과 같은 모양이 되는 것이다. 붉게 작성한 문구가 '우리가 목표로 하는 함수의 값은 0이다'라는 뜻을 내포한 문장임을 파악할수 있다. 이렇게 뉴턴 방식이 유도 될 수도 있다.
많이 돌아왔지만 뉴턴방식으로 최적화 문제를 풀때 함수를 바로 0으로 보내는 방식을 적용하여 1차 미분함수(그래디언트)를 0으로 보내는 목표함수로 삼아 문제를 푸는 방식을 적용할 수 있다. 복습의 의미로 식 1번의 최소값 문제를 풀고 다음단계로 넘어가보겠다. 아래는 풀이 코드와 해법이다.
# 문제함수 정의 --> 독자들은 이 함수를 문제에 맞게 수정하면 된다. # 1차 미분함수를 넣어보자 def example_function(x): return 4*x**3-33.6*x**2+88.5*x-72.45 # 문제함수의 미분함수 정의 --> 미분정도는 여러분의 몫으로 남겨두겠다. # 2차 미분함수를 넣어보자 def gradient_example_function(x): return 12*x**2-67.2*x+88.5 x0 = 5 #초기 임의의 해 설정 for i in range(10): x1 = x0-example_function(x0)/gradient_example_function(x0) print('{:d}회차 수치해: {:.4f}'.format(i+1,x1)) x0 = x1결과는 다음과 같다.
1회차 수치해: 4.4276 2회차 수치해: 4.1262 3회차 수치해: 4.0190 4회차 수치해: 4.0045 5회차 수치해: 4.0043 6회차 수치해: 4.0043 7회차 수치해: 4.0043 8회차 수치해: 4.0043 9회차 수치해: 4.0043 10회차 수치해: 4.0043코드블럭을 더 넣지는 않겠지만 초기값을 $x=1$에서 부터 최소값 문제를 푼다고 가정해보자. 위에서 Local minima에 빠질 염려가 있다. 그림을 보면 대략 $x=1.6$지점에서 국부최소값으로 빠질 염려가 있는데 실험을 해보도록 하겠다.
그렇다. 1.6435지점에서 컴퓨터는 저 함수의 최소값을 뱉어낼 것이라고 예상했다. 전체적인 함수의 정보를 모르면 수치해석의 큰 단점이 되는 것이다. 따라서 우리는 수치 최적화 문제를 풀 때 적절한 초기값을 잘 설정해주어야 한다의 뜻을 캐치하였고 앞으로의 예시에서 염두해둬야 할 부분이다. 많은 수학자들이 초기값문제, 국부최소화 문제를 해결하는 방법에 대하여 연구를 하고 있으니 관심있는 사람들은 상세히 봐두는것이 좋겠다(머신러닝에서는 최적화 문제 해결법을 아는 것은 감히 말하지만 필수다! 무조건 알아야 한다!!)
한 단계 업그레이드 해보자.
지금까지는 변수 $x$ 하나에 대해서 최적화 문제를 풀었지만 여러개의 종속변수
$X=[x_1, x_2, ... x_n]$를 동시에 풀어야 하는 문제를 만났다고 가정해보자(여기서 아래첨자를 반복회차가 아니라 종속변수의 항임을 유의하라!).
딱딱하게 생각해보지 말고 음... 생각 중!
예를 들면 자동차의 최고 효율적인 연비를 얻어야 할때 고려 할 수 있는 환경이 자동차의 RPM, 공기저항력, 에어컨 가동정도라고 하면 수식 연비 모델링을 다음과 같이 할 수 있다.
$\textit{연비} = F(RPM, \textit{공기저항력}, \textit{에어컨 가동정도})$
연비를 최대화를 하려면 위 관계식중 좌측항을 -값으로 부호를 바꾸고 최적화 문제를 풀어버리면 된다.
하지만 종속변수가 무려 3개나 된다. 이럴때 어떻게 문제풀이를 하는지 알아보자.
재료함수로 유명한 test function중 Booth function을 들고왔다.
함수 식
$F(X) = f(x_1,x_2) = (x_1+2x_2-7)^2+(2x_1+x_2-5)^2 \qquad eq.7$
최소값 지점은 $X_min = [x_1,x_2] = [1,3]$ 이다. 아래 그림을 같이 확인해보자.
다변수 함수의 최적화 문제 중 그나마 가장 간단한 문제를 가지고 왔다.
다변수 함수의 문제도 식 2번에서 부터 출발하는데, 한번 2번 식을 다시 써보도록 하겠다.
$x_{t+1} {\leftarrow} x_{t} - {{f'(x_{t})}\over{f''(x_{t})}}. \qquad eq.2$
식 2번을 기준으로 문자를 다변수 함수 문제 형태로 바꿔써보자.
1. 소문자 $x$는 단일 변수 스칼라, 대문자 $X$는 $[x_1,x_2]$인 벡터를 의미하고 아래첨자는 반복차시로 정의된다.
2. $f(x)$는 단일변수에서 정의된 목표함수, $F(X)$는 다변수에서 정의된 목표함수로 정의된다.
3. $f'(x)$는 단일변수에서 정의된 목표함수의 1차 미분함수, $\nabla F(X)$는 다변수에서 정의된 목표함수의 1차미분, 그래디언트(gradient)벡터 함수이다.
4. $f''(x)$는 단일 변수에서 정의된 목표함수의 2차 미분함수, $H(X)$는 다변수에서 정의된 목표함수의 2차미분, 헤시안(Hessian)행렬이다.
1~4까지 무슨말인지 모르겠지만 일단 쭉 가보겠다(어려워도 그냥 쭉 따라가보자).
$X_{t+1} {\leftarrow} X_{t} - H(X)^{-1} \nabla F(X). \qquad eq.8$
1번과 2번은 언급했으니 넘어가고, 3번부터 이야기해보겠다.
단일변수로 만들어진 함수를 미분하면 뭐~ 그냥 미분이 되는 것이다. 하지만 다변수(변수 2개라고 가정하자) 함수를 미분할때 생각해보면 $F(X) = f(x_1,x_2)$에서 변수가 2개인데 뭐는 미분하고 뭐는 안하고 하면 옳지가 않으니 둘다 똑같이 한번씩 미분을 해줘야 한다. 그래서 결과는 다변수 함수의 차원만큼의 벡터로 나온다.
$\nabla F(X) = [{{df(x_1,x_2)}\over{d x_1}},{{df(x_1,x_2)}\over{dx_2}}]. \qquad eq.9$
4번 과정은 식 9번의 결과를 한번 더 미분해주는 것이다. 위에선 2개의 차원이 나왔는데, 각각을 $x_1, x_2$로 미분하니까 2x2 크기의 행렬로 나온다!
거기에 벡터와 행렬은 나눗셈 연산이 되지 않으니 역행렬 연산을 통해서 다변수의 함수에서 2차미분함수를 나눠주는 역할로 식 2를 확장시켜나갔다.
Beale function을 수치 최적화기법으로 풀어보자(상당히 긴 코드가 될것 같은 예감이 든다).
# Booth function의 그래디언트 벡터, 식 9 def grad_booth(x,y): # 그래디언트 벡터의 첫번째 요소: 2*(x+2*y-7)+4*(2*x+y-5) fir = 10*x+8*y-34 # 그래디언트 벡터의 두번째 요소: 4*(x+2*y-7)+2*(2*x+y-5) sec = 8*x+10*y-38 return np.array([fir,sec]) # Booth function의 헤시안 행렬, 식 10 def hessian_booth(x,y): # 1행 1열 요소 ele_11 = 10 # 1행 2열 요소 ele_12 = 8 # 2행 1열 요소 ele_21 = 8 # 2행 2열 요소 ele_22 = 10 return np.array([[10,8],[8,10]]) X0 = np.array([5,-1]) # 초기값 위치 for i in range(10): x,y = X0 X_new = X0 - 0.5*np.matmul(np.linalg.inv(hessian_booth(x,y)),grad_booth(x,y)) # 식 8 print('{:d}회차 '.format(i+1)) print('위치 x1: {:.4f}, x2: {:.4f}'.format(X_new[0],X_new[1])) X0 = X_new #업데이트결과는 다음과 같다.
1회차 위치 x1: 3.0000, x2: 1.0000 2회차 위치 x1: 2.0000, x2: 2.0000 3회차 위치 x1: 1.5000, x2: 2.5000 4회차 위치 x1: 1.2500, x2: 2.7500 5회차 위치 x1: 1.1250, x2: 2.8750 6회차 위치 x1: 1.0625, x2: 2.9375 7회차 위치 x1: 1.0312, x2: 2.9688 8회차 위치 x1: 1.0156, x2: 2.9844 9회차 위치 x1: 1.0078, x2: 2.9922 10회차 위치 x1: 1.0039, x2: 2.996110회차쯤 가면 $(1,3)$ 최소값 근처로 감을 확인할 수 있다.
코드를 보다가 하나 의문점이 들수 있는 부분이 아래 부분일텐데
X_new = X0 - 0.5*np.matmul(np.linalg.inv(hessian_booth(x,y)),grad_booth(x,y)) # 식 8이 부분에서 0.5가 왜 곱해졌는지 의아해 하는 분들이 있을 수 있다. 1보다 작은 양수값을 곱해주는 효과는 다음차시에서 수치해를 추적할때 업데이트 정도를 늦추는 효과를 보인다. 머신러닝에서는 학습률(Learning rate)라고 하는데 커지면 커질수록 학습하는 정도가 빨라지나 수치적으로 불안정한 효과를 높이게 된다. 대략 다변수함수는 수치 최적화를 할때 불안정한 요소가 있으므로 상수를 곱해줘서 천천히 업데이트 시키더라도 이상한 값으로 쫓아오지 못하게하는 트릭(?)을 써야한다.
이렇게 하면 위에서 자동차 연비 문제도 어떻게 풀어야할지 접근이 가능할 것이다. 이제 최적화 문제에 관련하여 앞으로 남은 몫은 여러분에게 맡기겠다.
p.s 어려운 부분이 있었다면 댓글로 남겨주기 바란다. 최대한 성심 성의껏 답 or 새로운 포스팅으로 이해시키려고 노력해보겠다. +티스토리 Latex는 잘 안된다.... 힘들었다.