home
Meet Our Team
home

Derivation of LBFGS Part 2 - SR1 Method

오태호 (Taeho Oh)
오태호 (Taeho Oh)
안녕하세요. 오태호입니다.
이 글에서는 Optimization 기법중에 하나인 LBFGS Method(Limited Memory Broyden–Fletcher–Goldfarb–Shanno Method)의 수식을 다음과 같이 4개의 Part에 걸쳐서 차근차근 유도하여 LBFGS Method의 구조를 조금 깊게 살펴보도록 하겠습니다.
•
Derivation of LBFGS Part 2 - SR1 Method

Quasi Newton Method

Newton’s Method를 사용하여 f(x)f(\mathbf{x})를 최소로 하는 x를 찾는 식은 다음과 같습니다. 다음 식을 x1\mathbf{x}_{1}, x2\mathbf{x}_{2}, x3\mathbf{x}_{3}, ⋯⋯ 와 같이 Iteration을 반복하면서 구하고자 하는 x에 점점 가까운 값을 구합니다.
xk+1=xk−tk[∇2f(xk)]−1∇f(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)
여기에서 x의 차원이 높은 경우에는 [∇2f(xk)]−1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}의 계산량이 매우 커서 계산이 매우 힘듭니다. 그래서 이런 경우를 극복하기 위해 [∇2f(xk)]−1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}을 정확하게 계산하는 것이 아니라 근사해서 구한 다음에 사용하는 다양한 기법이 있는데 이런 기법들을 Quasi Newton Method라고 합니다.
[∇2f(xk)]−1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}을 근사하기 위한 수식을 조금 더 간결하게 표기하기 위해 다음과 같이 몇가지 Vector와 Matrix를 정의합니다.
sk=xk+1−xkgk=∇f(xk)yk=gk+1−gkBk≈∇2f(xk)Hk=Bk−1\begin{array}{l}\mathbf{s}_{k}=\mathbf{x}_{k+1}-\mathbf{x}_{k} \\\mathbf{g}_{k}=\nabla f\left(\mathbf{x}_{k}\right) \\\mathbf{y}_{k}=\mathbf{g}_{k+1}-\mathbf{g}_{k} \\\mathbf{B}_{k} \approx \nabla^{2} f\left(\mathbf{x}_{k}\right) \\\mathbf{H}_{k}=\mathbf{B}_{k}^{-1}\end{array}
[∇2f(xk)]−1\left[\nabla^{2} f\left(\mathbf{x}_{k}\right)\right]^{-1}를 근사해서 구하기 위해 일단 ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)를 근사해서 Bk\mathbf{B}_{k}를 구하고 이를 기반으로 Hk\mathbf{H}_{k}를 구합니다. Bk\mathbf{B}_{k}를 구하는 방법으로는 Iteration마다 조금씩 Bk\mathbf{B}_{k}에 변화를 줘서 Bk\mathbf{B}_{k}가 ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)과 유사해 지도록 해서 구합니다.

Secant Equation

Bk+1\mathbf{B}_{k+1}를 ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)에 근사시키기 위해 다음과 같은 식을 만족시키도록 합니다. 이 식은 Secant Equation이라고 합니다.
Bk+1sk=yk\mathbf{B}_{k+1} \mathbf{s}_{k}=\mathbf{y}_{k}
이 식을 직관적으로 살펴보면, xk+1\mathbf{x}_{k+1}과 xk\mathbf{x}_{k}의 차이를 Bk+1\mathbf{B}_{k+1}에 곱해주면 ∇f(xk+1)\nabla f\left(\mathbf{x}_{k+1}\right)과 ∇f(xk)\nabla f\left(\mathbf{x}_{k}\right)의 차이가 된다는 것을 의미합니다. ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)의 정의를 생각해 보면 이것을 만족하는 Bk+1\mathbf{B}_{k+1}는 ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)에 가까울 것이라는 것을 추측할 수 있습니다.

Sherman Morrison Woodbury Formula

Bk\mathbf{B}_{k}를 구한 후에 Hk\mathbf{H}_{k}를 구할 때 다음 식을 이용합니다. 이 식은 Sherman Morrison Woodbury Formula라고 합니다.
(A+UCV)−1=A−1−A−1U(C−1+VA−1U)−1VA−1(\mathbf{A}+\mathbf{U C V})^{-1}=\mathbf{A}^{-1}-\mathbf{A}^{-1} \mathbf{U}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1}
이 식은 다음과 같이 증명합니다.
(A+UCV)(A−1−A−1U(C−1+VA−1U)−1VA−1)=I−U(C−1+VA−1U)−1VA−1+UCVA−1−UCVA−1UC−1(C−1+VA−1U)−1VA−1=I+UCVA−1−[U(C−1+VA−1U)−1VA−1+UCVA−1U−1(C−1+VA−1U)−1VA−1)]=I+UCVA−1−(U+UCVA−1U)(C−1+VA−1U)−1VA−1=I+UCVA−1−UC(C−1+VA−1U)(C−1+VA−1U)−1VA−1=I+UCVA−1−UCVA−1=I\begin{array}{l}(\mathbf{A}+\mathbf{U C V})\left(\mathbf{A}^{-1}-\mathbf{A}^{-1} \mathbf{U}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1}\right) \\=\mathbf{I}-\mathbf{U}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1}+\mathbf{U C V A}^{-1}-\mathbf{U C V A}^{-1} \mathbf{U C}^{-1}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1} \\\left.=\mathbf{I}+\mathbf{U C V A}^{-1}-\left[\mathbf{U}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1}+\mathbf{U C V A}^{-1} \mathbf{U}^{-1}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1}\right)\right] \\=\mathbf{I}+\mathbf{U C V A}^{-1}-\left(\mathbf{U}+\mathbf{U C V A}^{-1} \mathbf{U}\right)\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1} \\=\mathbf{I}+\mathbf{U C V A}^{-1}-\mathbf{U C}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V A}^{-1} \\=\mathbf{I}+\mathbf{U C V A}^{-1}-\mathbf{U C V A}^{-1} \\=\mathbf{I}\end{array}
Sherman Morrison Woodbury Formula가 성립하기 위해서는 A−1\mathbf{A}^{-1}와 C−1\mathbf{C}^{-1}와 (C−1+VA−1U)−1\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1}가 존재해야 합니다.
이 글에서는 A가 Positive Definite Matrix이고 C=1\mathbf{C}=\mathbf{1}이고 V=UT\mathbf{V}=\mathbf{U}^{T}인 경우에 Sherman Morrison Woodbury Formula를 사용합니다. 이때 A−1\mathbf{A}^{-1}와 C−1\mathbf{C}^{-1}와 (C−1+VA−1U)−1\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1}가 존재한다는 것은 다음과 같이 확인합니다.
A가 Positive Definite Matrix라면, A의 Eigenvalue는 모두 Positive가 되어서, A는 Full Rank Matrix가 되어A−1\mathbf{A}^{-1}이 존재합니다.
C=I\mathbf{C}=\mathbf{I}라면 C−1\mathbf{C}^{-1}가 당연히 존재합니다.
A가 Positive Definite Matrix이기 때문에, A−1\mathbf{A}^{-1}도 Positive Definite Matrix가 되며, A−1\mathbf{A}^{-1}는 Cholesky Decomposition에 의해 LLT\mathbf{L} \mathbf{L}^{T}으로 표현할 수 있습니다.
P를 아래와 같이 정의합니다.
P=C−1+VA−1U\mathbf{P}=\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}
Px=0\mathbf{P}_{\mathbf{x}}=\mathbf{0}을 만족하는 경우가 x=0\mathbf{x}=\mathbf{0}이 유일한 경우라면 P−1\mathbf{P}^{-1}이 존재합니다.
Px=0\mathbf{P}_{\mathbf{x}}=\mathbf{0}을 만족하는 x≠0\mathbf{x} \neq \mathbf{0}인 x가 존재한다면 xTPx=0\mathbf{x}^{T} \mathbf{P x}=\mathbf{0}을 만족하는  x≠0\mathbf{x} \neq \mathbf{0}인 x가 존재합니다.
xTPx=0\mathbf{x}^{T} \mathbf{P x}=\mathbf{0}을 만족하는 x≠0\mathbf{x} \neq \mathbf{0}인 x가 존재하지 않는다면 Px=0\mathbf{P }_{\mathbf{x}}=\mathbf{0}을 만족하는 x≠0\mathbf{x} \neq \mathbf{0}인 x가 존재하지 않습니다.
xTPx=0\mathbf{x}^{T} \mathbf{P x}=\mathbf{0}을 만족하는 경우가 x=0\mathbf{x}=\mathbf{0}이 유일한 경우라면 Px=0\mathbf{P }_{\mathbf{x}}=\mathbf{0}을 만족하는 경우는 x=0\mathbf{x}=\mathbf{0}이 유일한 경우입니다.
xTPx=0\mathbf{x}^{T} \mathbf{P x}=\mathbf{0}을 만족하는 경우가 x=0\mathbf{x}=\mathbf{0}이 유일한 경우라면  P−1\mathbf{P}^{-1}이 존재합니다.
xTP=xT(C−1+VA−1U)x=xT(I−1+UTA−1U)x=xT(I+UTLLTU)x=xTx+(LTUx)T(LTUx)=∥x∥2+∥LTUx∥2\begin{aligned}\mathbf{x}^{T} \mathbf{P} & =\mathbf{x}^{T}\left(\mathbf{C}^{-1}+\mathbf{V} \mathbf{A}^{-1} \mathbf{U}\right) \mathbf{x} \\& =\mathbf{x}^{T}\left(\mathbf{I}^{-1}+\mathbf{U}^{T} \mathbf{A}^{-1} \mathbf{U}\right) \mathbf{x} \\& =\mathbf{x}^{T}\left(\mathbf{I}+\mathbf{U}^{T} \mathbf{L} \mathbf{L}^{T} \mathbf{U}\right) \mathbf{x} \\& =\mathbf{x}^{T} \mathbf{x}+\left(\mathbf{L}^{T} \mathbf{U} \mathbf{x}\right)^{T}\left(\mathbf{L}^{T} \mathbf{U} \mathbf{x}\right) \\& =\|\mathbf{x}\|^{2}+\left\|\mathbf{L}^{T} \mathbf{U} \mathbf{x}\right\|^{2}\end{aligned}
xT(C−1+VA−1U)x=0\mathbf{x}^{T}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right) \mathbf{x}=\mathbf{0}을 만족하는 경우는 x=0\mathbf{x}=\mathbf{0}인 경우가 유일하므로 (C−1+VA−1U)−1\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1}이 존재합니다.

SR1 Method

Xk\mathbf{X}_{k}, Xk+1\mathbf{X}_{k+1}, ∇f(xk)\nabla f\left(\mathbf{x}_{k}\right), ∇f(xk+1)\nabla f\left(\mathbf{x}_{k+1}\right)를 구한 후에, sk\mathbf{s}_{k}와 yk\mathbf{y}_{k}를 구하고, Secant Equation을 만족하는 Bk+1\mathbf{B}_{k+1}를 구하는데 이것은 Bk\mathbf{B}_{k}을 조금만 변형시켜서 구합니다. Secant Equation을 만족하는 Bk+1\mathbf{B}_{k+1}는 여러가지가 존재하며 Bk\mathbf{B}_{k}을 조금만 변형시키는 방법도 여러가지가 존재합니다. 여기서는 Bk+1\mathbf{B}_{k+1}를 구하는 Quasi Newton Method중에 하나인 SR1 Method(Symmetric Rank 1 Method)를 살펴보겠습니다.
SR1 Method는 다음과 같이 Bk+1\mathbf{B}_{k+1}을 구할 때 Bk\mathbf{B}_{k}을 다음과 같이 조금만 변형 시켜서 구합니다.
Bk+1=Bk+aukukT\mathbf{B}_{k+1}=\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}
aukukTa \mathbf{u}_{k} \mathbf{u}_{k}^{T}은 Symmetric Matrix이고 Rank 1 Matrix입니다. aukukTa \mathbf{u}_{k} \mathbf{u}_{k}^{T}가 구체적으로 어떤 값을 가지는지 Secant Equation을 이용해서 계산해 보겠습니다.
Bk+1=Bk+aukukTBk+1sk=yk(Bk+aukukT)sk=ykaukukTsk=yk−Bksk(aukTsk)uk=yk−Bkskuk=yk−BkskaukTskskT(aukTsk)uk=skT(yk−Bksk)a(ukTsk)(skTuk)=skT(yk−Bksk)a(ukTsk)2=skT(yk−Bksk)=(yk−Bksk)TskBk+1=Bk+aukukT\begin{array}{l}\mathbf{B}_{k+1}=\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T} \\\mathbf{B}_{k+1} \mathbf{s}_{k}=\mathbf{y}_{k} \\\left(\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}\right) \mathbf{s}_{k}=\mathbf{y}_{k} \\a \mathbf{u}_{k} \mathbf{u}_{k}^{T} \mathbf{s}_{k}=\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k} \\\left(a \mathbf{u}_{k}^{T} \mathbf{s}_{k}\right) \mathbf{u}_{k}=\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k} \\\mathbf{u}_{k}=\frac{\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}}{a \mathbf{u}_{k}^{T} \mathbf{s}_{k}} \\\mathbf{s}_{k}^{T}\left(a \mathbf{u}_{k}^{T} \mathbf{s}_{k}\right) \mathbf{u}_{k}=\mathbf{s}_{k}^{T}\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right) \\a\left(\mathbf{u}_{k}^{T} \mathbf{s}_{k}\right)\left(\mathbf{s}_{k}^{T} \mathbf{u}_{k}\right)=\mathbf{s}_{k}^{T}\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right) \\a\left(\mathbf{u}_{k}^{T} \mathbf{s}_{k}\right)^{2}=\mathbf{s}_{k}^{T}\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)=\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)^{T} \mathbf{s}_{k} \\\mathbf{B}_{k+1}=\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}\end{array}
정리하면 다음과 같습니다.
Bk+1=Bk+(yk−Bksk)(yk−Bksk)T(yk−Bksk)Tsk\mathbf{B}_{k+1}=\mathbf{B}_{k}+\frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)^{T}}{\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)^{T} \mathbf{s}_{k}}
이제 여기서 구한 Bk+1\mathbf{B}_{k+1}을 이용해서 Hk+1\mathbf{H}_{k+1}를 구해야 합니다. Bk+1\mathbf{B}_{k+1}을 이용해서 Hk+1\mathbf{H}_{k+1}를 구하기 위해 Sherman Morrison Woodbury Formula을 이용합니다.
Sherman Morrison Woodbury Formula는 다음과 같습니다.
(A+UCV)−1=A−1−A−1U(C−1+VA−1U)−1VA−1(\mathbf{A}+\mathbf{U C V})^{-1}=\mathbf{A}^{-1}-\mathbf{A}^{-1} \mathbf{U}\left(\mathbf{C}^{-1}+\mathbf{V A}^{-1} \mathbf{U}\right)^{-1} \mathbf{V} \mathbf{A}^{-1}
.Hk+1\mathbf{H}_{k+1}은 다음과 같이 구합니다.
A=BkC=IU=aukV=aukTHk+1=Bk+1−1=(Bk+aukukT)−1=Bk−1−Bk−1aukaukTBk−11+aukTBk−1auk=Hk−aHkukukTHk1+aukTHkuk=Hk−aHk(yk−BkkskaukTsk(yk−Bksk)TaukTkskHk(yk−Bksk)T⋯(yk−Bksk)A=BkC=IU=aukV=aukTHk+1=Bk+1−1=(Bk+aukukT)−1=Bk−1−Bk−1aukaukTBk−11+aukTBk−1auk=Hk−aHkukukTHk1+aukTHkuk=Hk−aHk(yk−BkkskaukTsk(yk−Bksk)TaukTkskHk(yk−Bksk)T⋯(yk−Bksk)\begin{array}{l}\begin{array}{l}\mathbf{A}=\mathbf{B}_{k} \\\mathbf{C}=\mathbf{I} \\\mathbf{U}=\sqrt{a} \mathbf{u}_{k} \\\mathbf{V}=\sqrt{a} \mathbf{u}_{k}^{T} \\\mathbf{H}_{k+1}=\mathbf{B}_{k+1}^{-1} \\=\left(\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}\right)^{-1} \\=\mathbf{B}_{k}^{-1}-\frac{\mathbf{B}_{k}^{-1} \sqrt{a} \mathbf{u}_{k} \sqrt{a} \mathbf{u}_{k}^{T} \mathbf{B}_{k}^{-1}}{1+\sqrt{a} \mathbf{u}_{k}^{T} \mathbf{B}_{k}^{-1} \sqrt{a} \mathbf{u}_{k}} \\=\mathbf{H}_{k}-\frac{a \mathbf{H}_{k} \mathbf{u}_{k} \mathbf{u}_{k}^{T} \mathbf{H}_{k}}{1+a \mathbf{u}_{k}^{T} \mathbf{H}_{k} \mathbf{u}_{k}} \\=\mathbf{H}_{k}-\frac{a \mathbf{H}_{k} \frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k_{k}} s_{k}\right.}{a \mathbf{u}_{k}^{T} s_{k}} \frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)^{T}}{a \mathbf{u}_{k}^{T_{k}} s_{k}} \mathbf{H}_{k}}{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)^{T} \cdots\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)}\end{array}\\\mathbf{A}=\mathbf{B}_{k}\\\mathbf{C}=\mathbf{I}\\\mathbf{U}=\sqrt{a} \mathbf{u}_{k}\\\mathbf{V}=\sqrt{a} \mathbf{u}_{k}^{T}\\\mathbf{H}_{k+1}=\mathbf{B}_{k+1}^{-1}\\=\left(\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}\right)^{-1}\\=\mathbf{B}_{k}^{-1}-\frac{\mathbf{B}_{k}^{-1} \sqrt{a} \mathbf{u}_{k} \sqrt{a} \mathbf{u}_{k}^{T} \mathbf{B}_{k}^{-1}}{1+\sqrt{a} \mathbf{u}_{k}^{T} \mathbf{B}_{k}^{-1} \sqrt{a} \mathbf{u}_{k}}\\=\mathbf{H}_{k}-\frac{a \mathbf{H}_{k} \mathbf{u}_{k} \mathbf{u}_{k}^{T} \mathbf{H}_{k}}{1+a \mathbf{u}_{k}^{T} \mathbf{H}_{k} \mathbf{u}_{k}}\\=\mathbf{H}_{k}-\frac{a \mathbf{H}_{k} \frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k_{k}} s_{k}\right.}{a \mathbf{u}_{k}^{T} s_{k}} \frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)^{T}}{a \mathbf{u}_{k}^{T_{k}} s_{k}} \mathbf{H}_{k}}{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)^{T} \cdots\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)}\end{array}
정리하면 다음과 같습니다.
Hk+1=Hk+(sk−Hkyk)(sk−Hkyk)T(sk−Hkyk)Tyk\mathbf{H}_{k+1}=\mathbf{H}_{k}+\frac{\left(\mathbf{s}_{k}-\mathbf{H}_{k} \mathbf{y}_{k}\right)\left(\mathbf{s}_{k}-\mathbf{H}_{k} \mathbf{y}_{k}\right)^{T}}{\left(\mathbf{s}_{k}-\mathbf{H}_{k} \mathbf{y}_{k}\right)^{T} \mathbf{y}_{k}}
SR1 Method에는 몇 가지 단점이 있습니다.
(yk−Bksk)Tsk≈0\left(\mathbf{y}_{k}-\mathbf{B}_{k} \mathbf{s}_{k}\right)^{T} \mathbf{s}_{k} \approx 0이 되면 Bk+1=Bk+(yk−Bksk)(yk−Bksk)T(yk−BkskTTsk\mathbf{B}_{k+1}=\mathbf{B}_{k}+\frac{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k}\right)^{T}}{\left(\mathbf{y}_{k}-\mathbf{B}_{k} s_{k} T^{T} s_{k}\right.}에서 분모가 0이 되기 때문에 Bk+1\mathbf{B}_{k+1}과 Hk+1\mathbf{H}_{k+1}을 안정적으로 구할 수 없습니다.
그리고 Newton’s Method에서 f(x)f(\mathbf{x})의 최소값을 구하기 위해서는 ∇2f(xk)\nabla^{2} f\left(\mathbf{x}_{k}\right)이 Positive Definite Matrix가 되어야 하기 때문에 Quasi Newton Method에서도 Bk\mathbf{B}_{k}와 Hk\mathbf{H}_{k}가 Positive Definite Matrix가 되어야 합니다. 하지만 SR1 Method에서는 Bk\mathbf{B}_{k}와 Hk\mathbf{H}_{k}가 Positive Definite Matrix임을 보장하지 않습니다.

Conclusion

이 글에서는 LBFGS Method를 살펴보기 위한 과정으로 SR1 Method에 대해 살펴보았습니다.
SR1 Method는Hk+1\mathbf{H}_{k+1}을 안정적으로 구할 수 없는 문제가 있습니다.
Derivation of LBFGS Part 3 - BFGS Method에서는 안정적으로 Hk+1\mathbf{H}_{k+1}을 구하는 방법을 알아보도록 하겠습니다.
작성자
오태호 (Taeho Oh)
Senior Machine Learning Engineer
안녕하세요, AI팀 오태호입니다.
관련된 글 더 보기
추천 시스템에서 전환율을 예측하는 새로운 접근: 반사실적 추론을 활용한 모델
AI Team
Machine Learning
2024/09/20
언어 모델의 Fine-Tuning 성능 올리기
Machine Learning
AI Team
2024/07/15
Bid Shading이란?
AI Team
Machine Learning
2024/07/09
딥러닝 추천 모델에 인과추론 접목시켜 전환율 예측 성능을 향상시키자!
AI Team
데이터분석
Machine Learning
2024/05/16
SHAP
Machine Learning
통계학
2024/05/06
머신러닝으로 만드는 개인화 추천 시스템
AI Team
Machine Learning
데이터분석
2024/05/04
Derivation of LBFGS Part 4 - LBFGS Method
Machine Learning
2020/09/27
Derivation of LBFGS Part 3 - BFGS Method
Machine Learning
2020/09/26
Derivation of LBFGS Part 2 - SR1 Method
Machine Learning
2020/09/25
Derivation of LBFGS Part 1 - Newton's Method
Machine Learning
2020/09/23
Load more