home
Meet Our Team
home

Derivation of LBFGS Part 4 - LBFGS Method

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

LBFGS Method

Quasi Newton Method중에 하나인 BFGS Method는 HkHk의 크기가 너무 커서 저장이 쉽지 않은 문제가 있습니다. 여기서는 HkHk를 저장하지 않고 BFGS Method를 사용하는 LBFGS Method(Limited Memory Broyden Fletcher Goldfarb Shanno Method)를 살펴보겠습니다.
앞에서 정의했던 각종 수식을 다시 정리하면 다음과 같습니다.
x=[x1x2⋮xn]∇f(x)=[∂∂x1f(x)∂∂x2f(x)⋮∂∂xnf(x)]∇2f(x)=[∂2∂x12f(x)∂2∂x1∂x2f(x)⋯∂2∂x1∂xnf(x)∂2∂x2x1f(x)∂2∂x22f(x)⋯∂2∂x2∂xnf(x)⋮⋮⋱⋮∂2∂f(x)∂2ρf(x)⋯∂2nf(x)\begin{array}{l}\mathbf{x}=\left[\begin{array}{c}x_{1} \\x_{2} \\\vdots \\x_{n}\end{array}\right] \\\nabla f(\mathbf{x})=\left[\begin{array}{c}\frac{\partial}{\partial x_{1}} f(\mathbf{x}) \\\frac{\partial}{\partial x_{2}} f(\mathbf{x}) \\\vdots \\\frac{\partial}{\partial x_{n}} f(\mathbf{x})\end{array}\right] \\\nabla^{2} f(\mathbf{x})=\left[\begin{array}{cccc}\frac{\partial^{2}}{\partial x_{1}^{2}} f(\mathbf{x}) & \frac{\partial^{2}}{\partial x_{1} \partial x_{2}} f(\mathbf{x}) & \cdots & \frac{\partial^{2}}{\partial x_{1} \partial x_{n}} f(\mathbf{x}) \\\frac{\partial^{2}}{\partial x_{2} x_{1}} f(\mathbf{x}) & \frac{\partial^{2}}{\partial x_{2}^{2}} f(\mathbf{x}) & \cdots & \frac{\partial^{2}}{\partial x_{2} \partial x_{n}} f(\mathbf{x}) \\\vdots & \vdots & \ddots & \vdots \\\frac{\partial^{2}}{\partial} f(\mathbf{x}) & \frac{\partial^{2}}{\rho} f(\mathbf{x}) & \cdots & \frac{\partial^{2}}{n} f(\mathbf{x})\end{array}\right.\end{array}
Quasi Newton Method를 다시 살펴보면 다음과 같습니다.
xk+1=xk−tkHkgk\mathbf{x}_{k+1}=\mathbf{x}_{k}-t_{k} \mathbf{H}_{k} \mathbf{g}_{k}
BFGS Method를 다시 살펴보면 다음과 같습니다.
Bk+1=Bk+aukukT+bvkvkT=Bk−BkskskTBkskTBksk+ykykTykTskHk+1=(I−skykTykTsk)Hk(I−ykskTykTsk)+skskTykTsk\begin{aligned}\mathbf{B}_{k+1} & =\mathbf{B}_{k}+a \mathbf{u}_{k} \mathbf{u}_{k}^{T}+b \mathbf{v}_{k} \mathbf{v}_{k}^{T} \\& =\mathbf{B}_{k}-\frac{\mathbf{B}_{k} \mathbf{s}_{k} \mathbf{s}_{k}^{T} \mathbf{B}_{k}}{\mathbf{s}_{k}^{T} \mathbf{B}_{k} \mathbf{s}_{k}}+\frac{\mathbf{y}_{k} \mathbf{y}_{k}^{T}}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}} \\\mathbf{H}_{k+1} & =\left(\mathbf{I}-\frac{\mathbf{s}_{k} \mathbf{y}_{k}^{T}}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}}\right) \mathbf{H}_{k}\left(\mathbf{I}-\frac{\mathbf{y}_{k} \mathbf{s}_{k}^{T}}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}}\right)+\frac{\mathbf{s}_{k} \mathbf{s}_{k}^{T}}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}}\end{aligned}
BFGS Method를 설명할 때 Hk\mathbf{H}_{k}를 구하는 방법을 알아보았습니다. 그런데 Quasi Newton Method를 자세히 살펴보면 결국 필요한 것은 Hk\mathbf{H}_{k}가 아니라 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}입니다. x가 n차원 Vector일 때 Hk\mathbf{H}_{k}를 저장하기 위해서는  Element의 Memory가 필요하지만  Hkgk\mathbf{H}_{k} \mathbf{g}_{k}는 n Element의 Memory만이 필요합니다. 그리고 Hk\mathbf{H}_{k}는 Iteration마다 n차원 Vector 2개를(uk\mathbf{u}_{k}와 vk\mathbf{v}_{k}를) 사용해서 Update를 하기 때문에 Hk\mathbf{H}_{k}의 변화정보를 n×2n \times 2  Element의 저장공간에 저장할 수 있습니다. 이런 특징을 보면 Hk\mathbf{H}_{k}의 n2n^{2} Element의 저장공간보다 훨씬 적은 저장공간을 사용하면서 BFGS Method를 사용할 수 있는 방법이 있을 것으로 상상할 수 있습니다. 이런 특징을 활용한 방법이 LBFGS Method입니다.
BFGS Method를 좀 더 간결하게 표현하기 위해 ρk\rho_{k}를 다음과 같이 정의합니다.
ρk=1ykTsk\rho_{k}=\frac{1}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}}
ρk\rho_{k}를 이용해서 BFGS Method를 다음과 같이 간결하게 표현합니다.
Hk+1=(I−ρkskykT)Hk(I−ρkykskT)+ρkskskT\mathbf{H}_{k+1}=\left(\mathbf{I}-\rho_{k} \mathbf{s}_{k} \mathbf{y}_{k}^{T}\right) \mathbf{H}_{k}\left(\mathbf{I}-\rho_{k} \mathbf{y}_{k} \mathbf{s}_{k}^{T}\right)+\rho_{k} \mathbf{s}_{k} \mathbf{s}_{k}^{T}
Hk\mathbf{H}_{k}는 다음과 같습니다.
Hk=(I−ρk−1sk−1yk−1T)Hk−1(I−ρk−1yk−1sk−1T)+ρk−1sk−1sk−1T\mathbf{H}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right) \mathbf{H}_{k-1}\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right)+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T}
BFGS는 를 구하려고 노력하지만, LBFGS Method는 Hk\mathbf{H}_{k}대신에 다음과 같이 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 구하려고 노력합니다.
Hkgk=(I−ρk−1sk−1yk−1T)Hk−1(I−ρk−1yk−1sk−1T)gk+ρk−1sk−1sk−1Tgk\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right) \mathbf{H}_{k-1}\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right) \mathbf{g}_{k}+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{g}_{k}
이 식을 살펴보면 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 최대한 정확하게 구하기 위해서는 이전 Iteration인 Hk−1\mathbf{H}_{k-1}을 최대한 정확하게 구해야 합니다. 그리고 Hk−1\mathbf{H}_{k-1}을 최대한 정확하게 구하기 위해서는 Hk−2\mathbf{H}_{k-2}을 최대한 정확하게 구해야 합니다. 하지만 그렇다고 해도 Hk−1000\mathbf{H}_{k-1000}같이 상당히 이전 Iteration 정보가 중요하지는 않습니다. 그래서 LBFGS Method에서는 적당히 이전 Iteration 정보까지만을 사용해서 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 구하려고 노력합니다. 얼마나 이전 Iteration 정보를 사용하는가를 History Size라고 합니다. History Size가 클수록 Memory를 많이 사용하게 되고 계산결과가 더 정확해집니다.
History Size가 22인 경우의 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 계산해서 규칙성을 찾아보겠습니다.
Hkgk=(I−ρk−1sk−1yk−1T)Hk−1(I−ρk−1yk−1sk−1T)gk+ρk−1sk−1sk−1Tgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2(I−ρk−2yk−2sk−2T)+ρk−2sk−2sk−2T)(I−ρk−1yk−1sk−1T)gk+ρk−1sk−1sk−1Tgkqk=gkαk−1=ρk−1sk−1Tqkqk−1=qk−αk−1yk−1Hkgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2(I−ρk−2yk−2sk−2T)+ρk−2sk−2sk−2T)qk−1+αk−1sk−1αk−2=ρk−2sk−2Tqk−1qk−2=qk−1−αk−2yk−2Hkgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2qk−2+αk−2sk−2)+αk−1sk−1rk−2=Hk−2qk−2βk−2=ρk−2yk−2Trk−2Hkgk=(I−ρk−1sk−1yk−1T)(rk−2−βk−2sk−2+αk−2sk−2)+αk−1sk−1rk−1=rk−2+(αk−2−βk−2)sk−2βk−1=ρk−1yk−1Trk−1Hkgk=rk−1−βk−1sk−1+αk−1sk−1rk=rk−1+(αk−1−βk−1)sk−1Hkgk=rk=rk−1+(αk−1−βk−1)sk−1=rk−2+(αk−2−βk−2)sk−2+(αk−1−βk−1)sk−1=Hk−2qk−2+(αk−2−βk−2)sk−2+(αk−1−βk−1)sk−1Hkgk=(I−ρk−1sk−1yk−1T)Hk−1(I−ρk−1yk−1sk−1T)gk+ρk−1sk−1sk−1Tgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2(I−ρk−2yk−2sk−2T)+ρk−2sk−2sk−2T)(I−ρk−1yk−1sk−1T)gk+ρk−1sk−1sk−1Tgkqk=gkαk−1=ρk−1sk−1Tqkqk−1=qk−αk−1yk−1Hkgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2(I−ρk−2yk−2sk−2T)+ρk−2sk−2sk−2T)qk−1+αk−1sk−1αk−2=ρk−2sk−2Tqk−1qk−2=qk−1−αk−2yk−2Hkgk=(I−ρk−1sk−1yk−1T)((I−ρk−2sk−2yk−2T)Hk−2qk−2+αk−2sk−2)+αk−1sk−1rk−2=Hk−2qk−2βk−2=ρk−2yk−2Trk−2Hkgk=(I−ρk−1sk−1yk−1T)(rk−2−βk−2sk−2+αk−2sk−2)+αk−1sk−1rk−1=rk−2+(αk−2−βk−2)sk−2βk−1=ρk−1yk−1Trk−1Hkgk=rk−1−βk−1sk−1+αk−1sk−1rk=rk−1+(αk−1−βk−1)sk−1Hkgk=rk=rk−1+(αk−1−βk−1)sk−1=rk−2+(αk−2−βk−2)sk−2+(αk−1−βk−1)sk−1=Hk−2qk−2+(αk−2−βk−2)sk−2+(αk−1−βk−1)sk−1\begin{array}{l}\begin{array}{l}\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right) \mathbf{H}_{k-1}\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right) \mathbf{g}_{k}+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{g}_{k} \\=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2}\left(\mathbf{I}-\rho_{k-2} \mathbf{y}_{k-2} \mathbf{s}_{k-2}^{T}\right)+\rho_{k-2} \mathbf{s}_{k-2} \mathbf{s}_{k-2}^{T}\right)\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right) \mathbf{g}_{k}+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{g}_{k} \\\mathbf{q}_{k}=\mathbf{g}_{k} \\\alpha_{k-1}=\rho_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{q}_{k} \\\mathbf{q}_{k-1}=\mathbf{q}_{k}-\alpha_{k-1} \mathbf{y}_{k-1} \\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2}\left(\mathbf{I}-\rho_{k-2} \mathbf{y}_{k-2} \mathbf{s}_{k-2}^{T}\right)+\rho_{k-2} \mathbf{s}_{k-2} \mathbf{s}_{k-2}^{T}\right) \mathbf{q}_{k-1}+\alpha_{k-1} \mathbf{s}_{k-1} \\\alpha_{k-2}=\rho_{k-2} \mathbf{s}_{k-2}^{T} \mathbf{q}_{k-1} \\\mathbf{q}_{k-2}=\mathbf{q}_{k-1}-\alpha_{k-2} \mathbf{y}_{k-2} \\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2} \mathbf{q}_{k-2}+\alpha_{k-2} \mathbf{s}_{k-2}\right)+\alpha_{k-1} \mathbf{s}_{k-1} \\\mathbf{r}_{k-2}=\mathbf{H}_{k-2} \mathbf{q}_{k-2} \\\beta_{k-2}=\rho_{k-2} \mathbf{y}_{k-2}^{T} \mathbf{r}_{k-2} \\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\mathbf{r}_{k-2}-\beta_{k-2} \mathbf{s}_{k-2}+\alpha_{k-2} \mathbf{s}_{k-2}\right)+\alpha_{k-1} \mathbf{s}_{k-1} \\\mathbf{r}_{k-1}=\mathbf{r}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2} \\\beta_{k-1}=\rho_{k-1} \mathbf{y}_{k-1}^{T} \mathbf{r}_{k-1} \\\mathbf{H}_{k} \mathbf{g}_{k}=\mathbf{r}_{k-1}-\beta_{k-1} \mathbf{s}_{k-1}+\alpha_{k-1} \mathbf{s}_{k-1} \\\mathbf{r}_{k}=\mathbf{r}_{k-1}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1} \\\mathbf{H}_{k} \mathbf{g}_{k}=\mathbf{r}_{k} \\=\mathbf{r}_{k-1}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1} \\=\mathbf{r}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1} \\=\mathbf{H}_{k-2} \mathbf{q}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1}\end{array}\\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right) \mathbf{H}_{k-1}\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right) \mathbf{g}_{k}+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{g}_{k}\\=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2}\left(\mathbf{I}-\rho_{k-2} \mathbf{y}_{k-2} \mathbf{s}_{k-2}^{T}\right)+\rho_{k-2} \mathbf{s}_{k-2} \mathbf{s}_{k-2}^{T}\right)\left(\mathbf{I}-\rho_{k-1} \mathbf{y}_{k-1} \mathbf{s}_{k-1}^{T}\right) \mathbf{g}_{k}+\rho_{k-1} \mathbf{s}_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{g}_{k}\\\mathbf{q}_{k}=\mathbf{g}_{k}\\\alpha_{k-1}=\rho_{k-1} \mathbf{s}_{k-1}^{T} \mathbf{q}_{k}\\\mathbf{q}_{k-1}=\mathbf{q}_{k}-\alpha_{k-1} \mathbf{y}_{k-1}\\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2}\left(\mathbf{I}-\rho_{k-2} \mathbf{y}_{k-2} \mathbf{s}_{k-2}^{T}\right)+\rho_{k-2} \mathbf{s}_{k-2} \mathbf{s}_{k-2}^{T}\right) \mathbf{q}_{k-1}+\alpha_{k-1} \mathbf{s}_{k-1}\\\alpha_{k-2}=\rho_{k-2} \mathbf{s}_{k-2}^{T} \mathbf{q}_{k-1}\\\mathbf{q}_{k-2}=\mathbf{q}_{k-1}-\alpha_{k-2} \mathbf{y}_{k-2}\\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\left(\mathbf{I}-\rho_{k-2} \mathbf{s}_{k-2} \mathbf{y}_{k-2}^{T}\right) \mathbf{H}_{k-2} \mathbf{q}_{k-2}+\alpha_{k-2} \mathbf{s}_{k-2}\right)+\alpha_{k-1} \mathbf{s}_{k-1}\\\mathbf{r}_{k-2}=\mathbf{H}_{k-2} \mathbf{q}_{k-2}\\\beta_{k-2}=\rho_{k-2} \mathbf{y}_{k-2}^{T} \mathbf{r}_{k-2}\\\mathbf{H}_{k} \mathbf{g}_{k}=\left(\mathbf{I}-\rho_{k-1} \mathbf{s}_{k-1} \mathbf{y}_{k-1}^{T}\right)\left(\mathbf{r}_{k-2}-\beta_{k-2} \mathbf{s}_{k-2}+\alpha_{k-2} \mathbf{s}_{k-2}\right)+\alpha_{k-1} \mathbf{s}_{k-1}\\\mathbf{r}_{k-1}=\mathbf{r}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2}\\\beta_{k-1}=\rho_{k-1} \mathbf{y}_{k-1}^{T} \mathbf{r}_{k-1}\\\mathbf{H}_{k} \mathbf{g}_{k}=\mathbf{r}_{k-1}-\beta_{k-1} \mathbf{s}_{k-1}+\alpha_{k-1} \mathbf{s}_{k-1}\\\mathbf{r}_{k}=\mathbf{r}_{k-1}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1}\\\mathbf{H}_{k} \mathbf{g}_{k}=\mathbf{r}_{k}\\=\mathbf{r}_{k-1}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1}\\=\mathbf{r}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1}\\=\mathbf{H}_{k-2} \mathbf{q}_{k-2}+\left(\alpha_{k-2}-\beta_{k-2}\right) \mathbf{s}_{k-2}+\left(\alpha_{k-1}-\beta_{k-1}\right) \mathbf{s}_{k-1}\end{array}
여기서 Hk−2\mathbf{H}_{k-2}에는 적당한 Matrix를 넣어줍니다. History Size가 큰 경우에는 II를 넣어도 큰 문제가 없지만 LBFGS Method에서는 보통 Heuristic으로 sk−1Tyk−1yk−1Tyk−1I\frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}를 많이 사용합니다. 보통 이런 Heuristic을 사용하는 이유는 Initial Inverse Hessian를 참조하기 바랍니다.
위에서 알아본 History Size 2의 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}의 계산과정을 일반화하여 History Size가 m일 때 계산과정을 정리하면 다음과 같습니다.
•
qk←gk\mathbf{q}_{k} \leftarrow \mathbf{g}_{k}
•
For i=k−1,k−2,⋯ ,k−mi=k-1, k-2, \cdots, k-m
◦
αi←ρisiTqi+1\alpha_{i} \leftarrow \rho_{i} \mathbf{s}_{i}^{T} \mathbf{q}_{i+1}
◦
qi←qi+1−αiyi\mathbf{q}_{i} \leftarrow \mathbf{q}_{i+1}-\alpha_{i} \mathbf{y}_{i}
•
γk←sk−1Tyk−1yk−1Tyk−1I\gamma_{k} \leftarrow \frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}
•
Hk−m←γkI\mathbf{H}_{k-m} \leftarrow \gamma_{k} \mathbf{I}
•
rk−m←Hk−mqk−m\mathbf{r}_{k-m} \leftarrow \mathbf{H}_{k-m} \mathbf{q}_{k-m}
•
For i=k−m,k−m+1,⋯ ,k−1i=k-m, k-m+1, \cdots, k-1
◦
βi←ρiyiTri\beta_{i} \leftarrow \rho_{i} \mathbf{y}_{i}^{T} \mathbf{r}_{i}
◦
ri+1←ri+(αi−βi)si\mathbf{r}_{i+1} \leftarrow \mathbf{r}_{i}+\left(\alpha_{i}-\beta_{i}\right) \mathbf{s}_{i}
•
Hkgk←rk\mathbf{H}_{k} \mathbf{g}_{k} \leftarrow \mathbf{r}_{k}
그런데 여기서 자세히 살펴보면 qi\mathbf{q}_{i}와 ri\mathbf{r}_{i}는 굳이 Index별로 여러 개를 저장할 필요가 없습니다. 그래서 아래와 같이 더 간단하게 정리할 수 있습니다.
•
q←gk\mathbf{q} \leftarrow \mathbf{g}_{k}
•
For i=k−1,k−2,⋯ ,k−mi=k-1, k-2, \cdots, k-m
◦
αi←ρisiTq\alpha_{i} \leftarrow \rho_{i} \mathbf{s}_{i}^{T} \mathbf{q}
◦
q←q−αiyi\mathbf{q} \leftarrow \mathbf{q}-\alpha_{i} \mathbf{y}_{i}
•
γk←sk−1Tyk−1yk−1Tyk−1I\gamma_{k} \leftarrow \frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}
•
Hk−m←γkI\mathbf{H}_{k-m} \leftarrow \gamma_{k} \mathbf{I}
•
r←Hk−mq\mathbf{r} \leftarrow \mathbf{H}_{k-m} \mathbf{q}
•
For i=k−m,k−m+1,⋯ ,k−1i=k-m, k-m+1, \cdots, k-1
◦
βi←ρiyiTr\beta_{i} \leftarrow \rho_{i} \mathbf{y}_{i}^{T} \mathbf{r}
◦
r←r+(αi−βi)si\mathbf{r} \leftarrow \mathbf{r}+\left(\alpha_{i}-\beta_{i}\right) \mathbf{s}_{i}
•
Hkgk←r\mathbf{H}_{k} \mathbf{g}_{k} \leftarrow \mathbf{r}
LBFGS Method는 이와 같이 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 직접 계산하고 다음의 Iteration을 수행하는 것을 반복하여 f(X)f(\mathbf{X})를 최소화시키는 x를 구하는 방법입니다. 이때, tk\mathbf{t}_{k}는 Wolfe Conditions를 사용해서 구한 적절한 값을 사용합니다.
xk+1=xk−tkHkgk\mathbf{x}_{k+1}=\mathbf{x}_{k}-t_{k} \mathbf{H}_{k} \mathbf{g}_{k}
BFGS Method는 Hk\mathbf{H}_{k}를 계산하고 이것을 이용해 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}을 계산하기 때문에 Memory 사용량이 매우 높지만 LBFGS Method는 Hkgk\mathbf{H}_{k} \mathbf{g}_{k}를 직접 계산하여 Memory 사용량을 BFGS Method에 비해 크게 낮출 수 있습니다.

Initial Inverse Hessian

LBFGS Method을 살펴보면 Initial Inverse Hessian Hk−m\mathbf{H}_{k-m}가 필요합니다. History Size가 큰 경우에는 II를 사용해도 무방하지만 조금 더 개선된 Heuristic으로 다음과 같이 Hk−m\mathbf{H}_{k-m}를 구해서 사용하는 경우가 많습니다. Gk−1\mathbf{G}_{k-1}을 Hessian의 근사치라고 정의합니다.
Gk−1sk−1=yk−1zk−1=Gk−1sk−1yk−1=Gk−1sk−1=Gk−1zk−1sk−1=1Gk−1zk−1sk−1Tyk−1yk−1Tyk−1I=(1Gk−1zk−1)T(Gk−1zk−1)(Gk−1zk−1)T(Gk−1zk−1)I=zk−1Tzk−1zk−1TGk−1zk−1IGk−1sk−1=yk−1zk−1=Gk−1sk−1yk−1=Gk−1sk−1=Gk−1zk−1sk−1=1Gk−1zk−1sk−1Tyk−1yk−1Tyk−1I=(1Gk−1zk−1)T(Gk−1zk−1)(Gk−1zk−1)T(Gk−1zk−1)I=zk−1Tzk−1zk−1TGk−1zk−1I\begin{array}{l}\begin{array}{l}\mathbf{G}_{k-1} \mathbf{s}_{k-1}=\mathbf{y}_{k-1} \\\mathbf{z}_{k-1}=\sqrt{\mathbf{G}_{k-1}} \mathbf{s}_{k-1} \\\mathbf{y}_{k-1}=\mathbf{G}_{k-1} \mathbf{s}_{k-1}=\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1} \\\mathbf{s}_{k-1}=\frac{1}{\sqrt{\mathbf{G}_{k-1}}} \mathbf{z}_{k-1} \\\frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}=\frac{\left(\frac{1}{\sqrt{\mathbf{G}_{k-1}}} \mathbf{z}_{k-1}\right)^{T}\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)}{\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)^{T}\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)} \mathbf{I} \\=\frac{\mathbf{z}_{k-1}^{T} \mathbf{z}_{k-1}}{\mathbf{z}_{k-1}^{T} \mathbf{G}_{k-1} \mathbf{z}_{k-1}} \mathbf{I}\end{array}\\\mathbf{G}_{k-1} \mathbf{s}_{k-1}=\mathbf{y}_{k-1}\\\mathbf{z}_{k-1}=\sqrt{\mathbf{G}_{k-1}} \mathbf{s}_{k-1}\\\mathbf{y}_{k-1}=\mathbf{G}_{k-1} \mathbf{s}_{k-1}=\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\\\mathbf{s}_{k-1}=\frac{1}{\sqrt{\mathbf{G}_{k-1}}} \mathbf{z}_{k-1}\\\frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}=\frac{\left(\frac{1}{\sqrt{\mathbf{G}_{k-1}}} \mathbf{z}_{k-1}\right)^{T}\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)}{\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)^{T}\left(\sqrt{\mathbf{G}_{k-1}} \mathbf{z}_{k-1}\right)} \mathbf{I}\\=\frac{\mathbf{z}_{k-1}^{T} \mathbf{z}_{k-1}}{\mathbf{z}_{k-1}^{T} \mathbf{G}_{k-1} \mathbf{z}_{k-1}} \mathbf{I}\end{array}
자세히 살펴보면 zk−1TGk−1zk−1zk−1Tzk−1I\frac{\mathbf{z}_{k-1}^{T} \mathbf{G}_{k-1} \mathbf{z}_{k-1}}{\mathbf{z}_{k-1}^{T} \mathbf{z}_{k-1}} \mathbf{I}의 Eigenvalue는 Hessian의 Eigenvalue와 유사하기 때문에 zk−1Tzk−1zk−1TGk−1zk−1I\frac{\mathbf{z}_{k-1}^{T} \mathbf{z}_{k-1}}{\mathbf{z}_{k-1}^{T} \mathbf{G}_{k-1} \mathbf{z}_{k-1}} \mathbf{I}의 Eigenvalue는 Inverse Hessian의 Eigenvalue와 유사하게 됩니다. 즉, sk−1Tyk−1yk−1Tyk−1I\frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}의 Eigenvalue는 Inverse Hessian의 Eigenvalue와 유사하게 되므로 sk−1Tyk−1yk−1Tyk−1I\frac{\mathbf{s}_{k-1}^{T} \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^{T} \mathbf{y}_{k-1}} \mathbf{I}을 Initial Inverse Hessian으로 사용합니다.

Conclusion

LBFGS Method를 처음부터 차근차근 유도해 보았습니다. 이 글이 LBFGS Method를 이해하는데 유용한 자료로 사용되기를 희망합니다.
작성자
오태호 (Taeho Oh)
Senior Machine Learning Engineer
안녕하세요, AI팀 오태호입니다.
관련된 글 더 보기
편향 없는 추천 시스템을 위한 통합 학습 전략: 어떻게 숨겨진 변수를 제어할까?
Recommendation System
Machine Learning
AI Team
2024/11/15
유튜브는 어떻게 수십억 명에게 개인화 영상 추천을 할까?
Recommendation System
Machine Learning
AI Team
2024/11/15
추천 시스템에서 전환율을 예측하는 새로운 접근: 반사실적 추론을 활용한 모델
AI Team
Recommendation System
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
Load more