Meet Our Team
home

Derivation of LBFGS Part 1 - Newton's Method

오태호 (Taeho Oh)
오태호 (Taeho Oh)
안녕하세요. 오태호입니다.
이 글에서는 Optimization 기법중에 하나인 LBFGS Method(Limited Memory Broyden–Fletcher–Goldfarb–Shanno Method)의 수식을 다음과 같이 4개의 Part에 걸쳐서 차근차근 유도하여 LBFGS Method의 구조를 조금 깊게 살펴보도록 하겠습니다.
Derivation of LBFGS Part 1 - Newton’s Method
pytorch.optim 패키지에 보면 SGD, Adadelta, Adagrad, RMSprop, Adam와 같은 Optimizer는 여러 곳에서 자세한 설명을 찾아볼 수 있습니다. 하지만 LBFGS Method의 경우에는 여러 곳에서 설명을 찾아 봐도 자세한 설명을 찾아보기가 쉽지 않아서 정리해 보았습니다.
이 글을 이해하기 위해서는 Calculus, Linear Algebra, Machine Learning에 대한 기초지식이 필요합니다.
이 글에서 굵은 글자체 대문자는 Matrix를 의미하고, 굵은 소문자는 Vector를 의미하며, 일반 소문자는 Scalar를 의미합니다. Vector는 특별히 언급이 없으면 Column Vector를 의미합니다.

Taylor Series

Taylor Series를 이용하여 xx가 x0x_0의 근처의 값을 가질 때 f(x)f(x)를 근사해서 표현하면 다음과 같습니다.
f(x)f(x0)+(xx0)xf(x0)+(xx0)222x2f(x0)f(x) \approx f\left(x_{0}\right)+\left(x-x_{0}\right) \frac{\partial}{\partial x} f\left(x_{0}\right)+\frac{\left(x-x_{0}\right)^{2}}{2} \frac{\partial^{2}}{\partial x^{2}} f\left(x_{0}\right)
마찬가지로 Taylor Series를 이용하여 3차원 공간에서 xx가 x0x_0의 근처의 값을 가지고 yy가 y0y_0의 근처의 값을 가질 때, f(x,y)f(x,y)를 근사해서 표현하면 다음과 같습니다.
f(x,y)f(x0,y0)+(xx0)xf(x0,y0)+(yy0)yf(x0,y0)+(xx0)222x2f(x0,y0)+(xx0)(yy0)22xyf(x0,y0)+(yy0)(xx0)22yxf(x0,y0)+(yy0)222y2f(x0,y0)=f(x0,y0)+([xy][x0y0])[xf(x0,y0)yf(x0,y0)]+12([xy][x0y0])[2x2f(x0,y0)2xyf(x0,y0)2yxf(x0,y0)2y2f(x0,y0)]([xy][x0y0])\begin{aligned}f(x, y) \approx & f\left(x_{0}, y_{0}\right)+\left(x-x_{0}\right) \frac{\partial}{\partial x} f\left(x_{0}, y_{0}\right)+\left(y-y_{0}\right) \frac{\partial}{\partial y} f\left(x_{0}, y_{0}\right)+ \\& \frac{\left(x-x_{0}\right)^{2}}{2} \frac{\partial^{2}}{\partial x^{2}} f\left(x_{0}, y_{0}\right)+\frac{\left(x-x_{0}\right)\left(y-y_{0}\right)}{2} \frac{\partial^{2}}{\partial x \partial y} f\left(x_{0}, y_{0}\right)+ \\& \frac{\left(y-y_{0}\right)\left(x-x_{0}\right)}{2} \frac{\partial^{2}}{\partial y \partial x} f\left(x_{0}, y_{0}\right)+\frac{\left(y-y_{0}\right)^{2}}{2} \frac{\partial^{2}}{\partial y^{2}} f\left(x_{0}, y_{0}\right) \\= & f\left(x_{0}, y_{0}\right)+\left(\left[\begin{array}{ll}x & y\end{array}\right]-\left[\begin{array}{ll}x_{0} & y_{0}\end{array}\right]\right)\left[\begin{array}{c}\frac{\partial}{\partial x} f\left(x_{0}, y_{0}\right) \\\frac{\partial}{\partial y} f\left(x_{0}, y_{0}\right)\end{array}\right]+ \\& \frac{1}{2}\left(\left[\begin{array}{ll}x & y\end{array}\right]-\left[\begin{array}{ll}x_{0} & y_{0}\end{array}\right]\right)\left[\begin{array}{cc}\frac{\partial^{2}}{\partial x^{2}} f\left(x_{0}, y_{0}\right) & \frac{\partial^{2}}{\partial x \partial y} f\left(x_{0}, y_{0}\right) \\\frac{\partial^{2}}{\partial y \partial x} f\left(x_{0}, y_{0}\right) & \frac{\partial^{2}}{\partial y^{2}} f\left(x_{0}, y_{0}\right)\end{array}\right]\left(\left[\begin{array}{l}x \\y\end{array}\right]-\left[\begin{array}{l}x_{0} \\y_{0}\end{array}\right]\right)\end{aligned}
x\mathbf{x}x0\mathbf{x}_0f(x)f(\mathbf{x}), Gradient f(x0)\nabla f\left(\mathbf{x}_{0}\right), Hessian 2f(x0)\nabla^{2} f\left(\mathbf{x}_{0}\right)을 다음과 같이 정의합니다.
x=[xy]x0=[x0y0]f(x0)=f(x0,y0)f(x0)=[xf(x0,y0)yf(x0,y0)]2f(vn)[2x2f(x0,y0)2xyf(x0,y0)\begin{array}{l}\mathbf{x}=\left[\begin{array}{l}x \\y\end{array}\right] \\\mathbf{x}_{0}=\left[\begin{array}{l}x_{0} \\y_{0}\end{array}\right] \\f\left(\mathbf{x}_{0}\right)=f\left(x_{0}, y_{0}\right) \\\nabla f\left(\mathbf{x}_{0}\right)=\left[\begin{array}{l}\frac{\partial}{\partial x} f\left(x_{0}, y_{0}\right) \\\frac{\partial}{\partial y} f\left(x_{0}, y_{0}\right)\end{array}\right] \\\nabla^{2} f\left(\mathbf{v}_{n}\right)-\left[\begin{array}{ll}\frac{\partial^{2}}{\partial x^{2}} f\left(x_{0}, y_{0}\right) & \frac{\partial^{2}}{\partial x \partial y} f\left(x_{0}, y_{0}\right)\end{array}\right.\end{array}
위의 f(x,y)f(x, y)를 Vector를 사용하여 간결하게 다시 정리하면 다음과 같습니다.
f(x)f(x0)+(xx0)Tf(x0)+12(xx0)T2f(x0)(xx0)f(\mathbf{x}) \approx f\left(\mathbf{x}_{0}\right)+\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla f\left(\mathbf{x}_{0}\right)+\frac{1}{2}\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)
참고로 이 식은 x\mathbf{x}가 여기에서 다룬 2차원 Vector가 아니라 더 높은 고차원의 Vector인 경우에도 성립합니다.

Vector Differentiation

Vector x\mathbf{x}를 다음과 같이 정의합니다.
x=[x1x2xn]\mathbf{x}=\left[\begin{array}{c}x_{1} \\x_{2} \\\vdots \\x_{n}\end{array}\right]
Scalar f(x)f(\mathbf{x})를 Vector x\mathbf{x}로 미분하는 경우 두 가지 방법으로 할 수 있습니다.
첫 번째 방법은 다음과 같은 Numerator Layout입니다.
f(x)x=[f(x)x1f(x)x2f(x)xn]\frac{\partial f(\mathbf{x})}{\partial \mathbf{x}}=\left[\begin{array}{ll}\frac{\partial f(\mathbf{x})}{\partial x_{1}} & \frac{\partial f(\mathbf{x})}{\partial x_{2}} \cdots \frac{\partial f(\mathbf{x})}{\partial x_{n}}\end{array}\right]
두 번째 방법은 다음과 같은 Denominator Layout입니다.
f(x)x=[f(x)x1f(x)x2f(x)xn]\frac{\partial f(\mathbf{x})}{\partial \mathbf{x}}=\left[\begin{array}{c}\frac{\partial f(\mathbf{x})}{\partial x_{1}} \\\frac{\partial f(\mathbf{x})}{\partial x_{2}} \\\vdots \\\frac{\partial f(\mathbf{x})}{\partial x_{n}}\end{array}\right]
학계에서 사용되는 것을 살펴보면 표준화된 방법 없이 두 가지 방법 모두가 많이 사용되는 것을 볼 수 있습니다. 어떤 경우에는 두 방법을 섞어가며 사용하는 경우도 있습니다. Machine Learning 분야에서는 Denominator Layout을 사용하는 경우가 더 많은 편입니다. 이 글에서는 특별히 언급이 없으면 Denominator Layout을 사용하도록 하겠습니다.
다음은 몇 가지 유용한 Vector 미분에 관한 정리입니다.
x(xTa)=[x1(a1x1+a2x2++anxn)x2(a1x1+a2x2++anxn)xn(a1x1+a2x2++anxn)]=[a1a2an]=ax(xTAx)=[xk(ijaijxixj)]k=[xk(akkxk2+jkakjxkxj+ikaikxixk)]k=[2akkxk+ikakjxj+i±kaikxi]\begin{aligned}\frac{\partial}{\partial \mathbf{x}}\left(\mathbf{x}^{T} \mathbf{a}\right)= & {\left[\begin{array}{c}\frac{\partial}{\partial x_{1}}\left(a_{1} x_{1}+a_{2} x_{2}+\cdots+a_{n} x_{n}\right) \\\frac{\partial}{\partial x_{2}}\left(a_{1} x_{1}+a_{2} x_{2}+\cdots+a_{n} x_{n}\right) \\\vdots \\\frac{\partial}{\partial x_{n}}\left(a_{1} x_{1}+a_{2} x_{2}+\cdots+a_{n} x_{n}\right)\end{array}\right]=\left[\begin{array}{c}a_{1} \\a_{2} \\\vdots \\a_{n}\end{array}\right]=\mathbf{a} } \\\frac{\partial}{\partial \mathbf{x}}\left(\mathbf{x}^{T} A \mathbf{x}\right) & =\left[\frac{\partial}{\partial x_{k}}\left(\sum_{i} \sum_{j} a_{i j} x_{i} x_{j}\right)\right]_{k} \\& =\left[\frac{\partial}{\partial x_{k}}\left(a_{k k} x_{k}^{2}+\sum_{j \neq k} a_{k j} x_{k} x_{j}+\sum_{i \neq k} a_{i k} x_{i} x_{k}\right)\right]_{k} \\& =\left[2 a_{k k} x_{k}+\sum_{i \neq k} a_{k j} x_{j}+\sum_{i \pm k} a_{i k} x_{i}\right]\end{aligned}
간략하게 다시 정리하면 다음과 같습니다.
x(xTa)=ax(xTAx)=(A+AT)x\begin{array}{l}\frac{\partial}{\partial \mathbf{x}}\left(\mathbf{x}^{T} \mathbf{a}\right)=\mathbf{a} \\\frac{\partial}{\partial \mathbf{x}}\left(\mathbf{x}^{T} A \mathbf{x}\right)=\left(\mathbf{A}+\mathbf{A}^{T}\right) \mathbf{x}\end{array}

Newton’s Method

f(x)f(\mathbf{x})를 최소로 하는 x\mathbf{x}를 찾으려고 합니다. 그런 x\mathbf{x}를 찾기 위해 f(x)=0\nabla f(\mathbf{x})=\mathbf{0}을 만족하는 x\mathbf{x}를 찾는 것을 시도합니다. 처음에는 f(x)=0\nabla f(\mathbf{x})=\mathbf{0}으로 하는 x\mathbf{x}를 x0\mathbf{x}_{0}로 추정하고, x0\mathbf{x}_{0}보다 더 개선된 x\mathbf{x}를 찾습니다. f(x)f(\mathbf{x})의 형태는 Taylor Series를 사용하여 다음과 같이 근사한 형태를 사용합니다.
f(x)f(x0)+(xx0)Tf(x0)+12(xx0)T2f(x0)(xx0)f(\mathbf{x}) \approx f\left(\mathbf{x}_{0}\right)+\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla f\left(\mathbf{x}_{0}\right)+\frac{1}{2}\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)
f(x)=0\nabla f(\mathbf{x})=\mathbf{0}을 만족하는 x\mathbf{x}는 Vector Differentiation을 참고하여 다음과 같이 구합니다. 가 Continuous하다면 2f(x)\nabla^{2} f(\mathbf{x})는 Symmetric한 성질도 이용합니다. (여기서 f(x)f(\mathbf{x})는 Continuous하다고 가정합니다.)
f(x)=xf(x)x(f(x0)+(xx0)Tf(x0)+12(xx0)T2f(x0)(xx0))=0+f(x0)+12(2f(x0)+[2f(x0)]T)(xx0)=f(x0)+2f(x0)(xx0)=0f(x0)+2f(x0)(xx0)=0x=x0[2f(x0)]1f(x0)\begin{aligned}\nabla f(\mathbf{x}) & =\frac{\partial}{\partial \mathbf{x}} f(\mathbf{x}) \\& \approx \frac{\partial}{\partial \mathbf{x}}\left(f\left(\mathbf{x}_{0}\right)+\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla f\left(\mathbf{x}_{0}\right)+\frac{1}{2}\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} \nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)\right) \\& =\mathbf{0}+\nabla f\left(\mathbf{x}_{0}\right)+\frac{1}{2}\left(\nabla^{2} f\left(\mathbf{x}_{0}\right)+\left[\nabla^{2} f\left(\mathbf{x}_{0}\right)\right]^{T}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right) \\& =\nabla f\left(\mathbf{x}_{0}\right)+\nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right) \\& =\mathbf{0} \\\nabla f\left(\mathbf{x}_{0}\right) & +\nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)=\mathbf{0} \\\mathbf{x}=\mathbf{x}_{0} & -\left[\nabla^{2} f\left(\mathbf{x}_{0}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{0}\right)\end{aligned}
이렇게 찾은 x\mathbf{x}를 x1\mathbf{x}_{1}라고 하고 위의 방법을 다시 수행하여 x1\mathbf{x}_{1}보다 더 개선된 x\mathbf{x}를 찾아서 이것을 x2\mathbf{x}_{2}라고 합니다. 이런 식으로 반복하여 f(x)f(\mathbf{x})를 최소로 하는 x\mathbf{x}를 찾습니다. 이렇게 f(x)f(\mathbf{x})를 최소로 하는 x\mathbf{x}를 찾는 방법을 Newton’s Method라고 합니다.
정리하면 다음과 같이 조금씩 개선된 x\mathbf{x}를 하나씩 구합니다. 여기서 는 Newton Direction이라고 합니다. x\mathbf{x}가 Newton Direction 방향으로 움직이면서 f(x)f(\mathbf{x})를 최소로 하는 x\mathbf{x}값을 찾습니다.
xk+1=xk[2f(xk)]1f(xk)\mathbf{x}_{k+1}=\mathbf{x}_{k}-\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{k}\right)
이 Newton’s Method를 그대로 사용하면 x\mathbf{x}가 Diverge하면서 제대로 x\mathbf{x}를 구하지 못할 수도 있기 때문에 다음과 같이 Newton’s Method를 살짝 수정한 Relaxed Newton’s Method를 사용하는 경우가 많이 있습니다. 여기서 tk\mathbf{t}_{k}는 Step Size라고 합니다. tk\mathbf{t}_{k}가 작은 값을 가지면 x\mathbf{x}가 Diverge하지 않도록 돕는 역할을 합니다.
xk+1=xktk[2f(xk)]1f(xk)\mathbf{x}_{k+1}=\mathbf{x}_{k}-t_{k}\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{k}\right)
Gradient Descent와 비교해 보도록 하겠습니다. Gradient Descent는 다음과 같이 x\mathbf{x}를 구합니다.
xk+1=xktkf(xk)\mathbf{x}_{k+1}=\mathbf{x}_{k}-t_{k} \nabla f\left(\mathbf{x}_{k}\right)
Gradient Descent는 x\mathbf{x}의 이동방향을 결정할 때 Gradientf(xk)\nabla f\left(\mathbf{x}_{k}\right)만을 활용하지만 Newton’s Method에서는 x\mathbf{x}의 이동방향을 결정할 때 Hessian 2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)도 함께 활용하여 좀 더 정확한 방향으로 x\mathbf{x}를 이동시키는 것을 확인할 수 있습니다.

Wolfe Conditions

Newton’s Method에서 Step Size tk\mathbf{t}_{k}를 정할 때 뭔가 기준을 가지고 정해야 하는데 이때 많이 사용하는 기준이 Wolfe Conditions입니다. Wolfe Conditions는 Armijo Rule과 Curvature Condition로 구성되어 있습니다.
Armijo Rule은 다음과 같습니다.
f(xk+tkpk)f(xk)+c1tkpkTf(xk)pk=[2f(xk)]1f(xk)c1=104\begin{array}{l}f\left(\mathbf{x}_{k}+t_{k} \mathbf{p}_{k}\right) \leq f\left(\mathbf{x}_{k}\right)+c_{1} t_{k} \mathbf{p}_{k}^{T} \nabla f\left(\mathbf{x}_{k}\right) \\\mathbf{p}_{k}=-\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{k}\right) \\c_{1}=10^{-4}\end{array}
여기서 pk\mathbf{p}_{k}는 Newton Direction입니다. c1\mathbf{c}_{1}은 Hyperparameter로 0<c1<10<c_{1}<1의 범위의 값에서 적당히 설정하는데 보통 0에 가까운 값으로 설정합니다. 직관적으로 설명하면, x를 Newton Direction으로 tk\mathbf{t}_{k}만큼 이동시켰을 때 실제 f(x)f(\mathbf{x})의 값이 Newton’s Method로 계산한 f(x)f(\mathbf{x})의 근사치 보다 충분히 작게 되도록 tk\mathbf{t}_{k}를 정해야 된다는 뜻입니다. 얼마나 충분히 작아야 하는지는 설정한 c1\mathbf{c}_{1}의 값에 의해 결정됩니다. c1\mathbf{c}_{1}의 값이 작아지면 허용되는 tk\mathbf{t}_{k}의 범위가 넓어지면서 tk\mathbf{t}_{k}가 더 큰 값을 가질 수 있게 됩니다. c1\mathbf{c}_{1}은 tk\mathbf{t}_{k}가 가질 수 있는 최대값을 결정합니다.
Curvature Condition은 다음과 같습니다.
pkTf(xk+tkpk)c2pkTf(xk)pk=[2f(xk)]1f(xk)c2=0.9\begin{array}{l}\mathbf{p}_{k}^{T} \nabla f\left(\mathbf{x}_{k}+t_{k} \mathbf{p}_{k}\right) \geq c_{2} \mathbf{p}_{k}^{T} \nabla f\left(\mathbf{x}_{k}\right) \\\mathbf{p}_{k}=-\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{k}\right) \\c_{2}=0.9\end{array}
여기서 pk\mathbf{p}_{k}는 Newton Direction입니다. c2\mathbf{c}_{2}은 Hyperparameter로 0<c2<10<c_{2}<1의 범위의 값에서 적당히 설정하는데 보통 1에 가까운 값으로 설정합니다. 직관적으로 설명하면, f(x)f(\mathbf{x})의 Gradient보다 x\mathbf{x}를 Newton Direction으로 tk\mathbf{t}_{k}만큼 이동시켰을 때의 f(x)f(\mathbf{x})의 Gradient가 충분히 크도록(Negative이던 것이 0에 가까워 지도록) tk\mathbf{t}_{k}를 정해야 된다는 뜻입니다. 얼마나 충분히 커야 하는지는 설정한 c2\mathbf{c}_{2}의 값에 의해 결정됩니다. c2\mathbf{c}_{2}의 값이 커지면 tk\mathbf{t}_{k}의 범위가 넓어지면서 tk\mathbf{t}_{k}가 더 작은 값을 가질 수 있게 됩니다. c2\mathbf{c}_{2}은 tk\mathbf{t}_{k}가 가질 수 있는 최소값을 결정합니다.
Wolfe Conditions에서 위에서 언급한 Curvature Condition대신에 다음과 같은 Curvature Condition을 사용하는 경우도 있습니다.
pkTf(xk+tkpk)c2pkTf(xk)pk=[2f(xk)]1f(xk)c2=0.9\begin{array}{l}\left|\mathbf{p}_{k}^{T} \nabla f\left(\mathbf{x}_{k}+t_{k} \mathbf{p}_{k}\right)\right| \leq c_{2}\left|\mathbf{p}_{k}^{T} \nabla f\left(\mathbf{x}_{k}\right)\right| \\\mathbf{p}_{k}=-\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1} \nabla f\left(\mathbf{x}_{k}\right) \\c_{2}=0.9\end{array}
이와 같은 Curvature Condition을 사용하는 경우에는 Strong Wolfe Conditions라고 합니다.

Conclusion

이 글에서는 LBFGS Method를 살펴보기 위한 첫단계로 Newton’s Method에 대해 살펴보았습니다.
Newton’s Method는 Gradient Descent에 비해서 방향을 잘 결정한다는 장점이 있지만 큰 단점이 하나 있습니다. Newton Direction을 계산하기 위해서는 Inverse Hessian [2f(xk)]1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}을 계산해야 하는데 이것은 x\mathbf{x}의 차원이 높아지면 계산이 매우 힘들어집니다.
Derivation of LBFGS Part 2 - SR1 Method에서는 x\mathbf{x}가 고차원일 경우에 어떻게 Inverse Hessian [2f(xk)]1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}를 계산해서 Newton’s Method를 사용할 수 있는지 알아보도록 하겠습니다.
작성자
관련된 글 더 보기