[최적화] (3) quasi Newton Method

다음은 Newton's Method를 변형한 quasi Newton Method다. 

기존 방법은 x_k에서의 순간변화율, 즉 미분값을 구해서 x_k+1을 구했다면, quasi newton method에서는 x_k와 x_k-1간의 평균변화율을 통해 x_k+1을 구한다. 평균변화율은 함수값 차분을 x값 차분으로 나눠주면 된다는 점에서 연산처리가 더욱 간편하다는 장점이 있다. 또한 실제로 미분을 통해 구한 x_k+1값이나 평균변화율을 통해 구한 값이 유사하기 때문에 비효율적이진 않다. 

 

다만 quasi newton을 배우기에 앞서 수식이 어마무시하기 때문에 이를 사전에 간편한 표현들로 약속하고 넘어가자. 

평균변화율을 Bk라는 matrix로 설정하는데 이는 y_k-1 / s_k-1 이다. 각 기호에 대한 정의는 좌측하단 박스에 있다. 

 

다시 우리의 목적을 상기해보자. 우리는 f(x*) = 0이 되는 x*를 찾아야한다. 

이 과정에서 newton과는 다르게 미분값의 역함수가 아닌 Bk의 역함수가 사용되는 것이다. 

근데 Bk를 구하려니 그 수식이 복잡하여 B_k+1과 Bk간의 관계식을 찾아 recursive하게 구해보자. 

 

B_k+1 = Bk + A가 둘간의 관계식이라면 이를 y_k = (B_k+1) * S_k 에 대입해본다. y_k = (B_k + A) * S_k를 풀어 쓰면 y_k - Bk * S_k = A * S_k가 되는데 좌변 전체를 vector Z로, S_k를 vector X로 약속해보자. 

B_k+1과 B_k 사이 관계식에서의 A를 알기 위해 Z=AX라는 좀 더 다루기 쉬운 format으로 변환했다고 생각하면 편하다. 

 

Broyden의 관찰에 의하면 B_k+1과 B_k 간에는 사실 큰 차이가 없다고 한다. 그리고 이 둘 사이에 큰 차이가 없도록해야 학습이 더 안정화되기 때문에 둘간의 차분인 A의 Frobenius Norm을 최소화하는 optimization problem을 풀어보겠다. 

 

Frobenius Norm은 행렬 A의 모든 원소의 norm을 뜻하는데 이 경우 제곱을 취해주니 root는 날라간다.

근데 이는 사실상 A(A^H)의 trace와 같다. A^H는 켤레전치인데 이는 일전에 올린 글(https://alba-tross.tistory.com/75)로 설명을 대체한다. optimization problem의 경우 대게 복소수가 아닌 실수를 다루기 때문에 켤레전치지만 사실상 그냥 전치와 같다. 따라서 objective fn이 tr(AA)로 바뀐다. 

 

앞서 말했듯이 이를 최소화하는 목적은 평균변화율이 급격하게 변화하는 것을 방지하기 위함이다. gradient method에서 learning rate를 작게하여 조심스레 학습하는 것과 그 목적이 같다고 볼 수 있다. 

 

자 그럼 위 optimization problem을 lagrange를 통해 풀어보자. 

Lagrange fn은 obj fn f(x)와 equality constraint인 g(x)에 lamda를 곱한 값으로 구성되어있다. 

이 Lagrange fn을 최소화하기 위해선 행렬 A와 vector lamda에 대해 미분해준 값이 0이 되는 (A, lamda)를 찾으면 된다. 

 

scalar인 largrange를 mtx A로 미분해주어야한다. 이는 이전글(https://alba-tross.tistory.com/78)에서 충분히 다뤘으므로 그 방법론에 대한 설명은 생략한다. 간략히 핵심만 말하자면 dL = tr( af/aA * dA)의 형태가 나오기 때문에 빠른 계산을 위해 위 식에도 tr를 씌어준다. 

 

A에 대해 미분을 취해준 dL을 전개하면 위와 같다. 이 때 aL/aA * dA의 형태로 깔끔하게 도출된다. 

구한 aL/aA = 0인 지점을 찾아주면 A= (1/2)(lamda)(x) 일때 lagrange = 0이 된다는 사실을 알게 된다. 

 

이렇게 구한 A 값을 Z = AX에 대입하면 lamda = 2Z / XX 임을 알게된다. 

 

구한 lamda를 기존 A에 대입하면 A = ZX/XX가 도출된다. 

 

맨처음에 확인하려고 했던 B_k+1 = B_k + A 관계식에 구한 A값을 대입하면 위와 같다. 

 

y_k = (B_k+1)*(S_k)에 구한 B_k+1 값을 대입한 것의 결과 y_k = y_k 라는 점에서 옳게 도출했음이 확인된다. 

 

수식이 많아지면 목적을 잊어먹게 되는데 다시 상기하자면 목적은 다음과 같다.

Hessian mtx를 계산해야하는 newton's method 대신 계산이 덜 복잡한 quasi newton을 활용한다. 순간변화율 대신 평균변화율을 사용하는데 이 때 순간변화율을 매순간 구하는 것 또한 계산이 복잡해지니 현재의 순간변화율과 다음의 순간변화율 간의 관계식을 구하여 그 계산을 편하게 하려는 것이었다.

그 결과 우리가 구한 B_k 관계식은 step4의 수식과 같다.

 

이를 기반으로 recursive하게 알고리즘을 돌리는 경우를 생각해보자. 

우선 시점 x0이 주어질 것이며, 함수 f(x)를 알고있으니 f(x0)은 구할 수 있다. 그런데 시점에서 평균변화율을 구하려면 이전 x에 대한 정보가 필요한데 시점은 그런것이 없으니 그냥 jacobian을 통해 B0을 구한다. 이때 B0는 순간변화율이다.

x0, f(x0), B0가 있으면 x1을 구할 수 있다. x1 = x0 - B0*f(x0)이기 때문이다. x1을 구하면 x1-x0 = s0을 구할 수 있고, f(x1)-f(x0)인 y0 또한 구할 수 있다. 이를 통해 B1또한 구할 수 있다. 이런 과정이 recursive하게 계속 반복되어 최종적으로 f(x*)=0이 되는 x*를 찾는 것이 quasi newton method다. 

 

 

https://blog.naver.com/kim_quant/223739323021