L-BFGS

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
- 2.1. Two-loop recursion
- 2.2. 수렴 조건 및 탐색 방법
3. 변형 알고리즘
4. 응용
5. 구현
참조

1. 개요

L-BFGS는 최적화 문제를 해결하기 위한 반복적인 알고리즘으로, 특히 머신 러닝 분야에서 널리 사용된다. 기울기와 헤시안 행렬의 추정치를 사용하여 더 나은 추정값을 찾아가며, "two-loop recursion" 방식을 통해 계산 효율성을 높인다. L-BFGS는 L-BFGS-B, OWL-QN, O-LBFGS 등 다양한 변형 알고리즘이 존재하며, Box 제약 조건, 정규화 모델, 온라인 근사법 등을 지원한다. C++, C#, R, SciPy 등 다양한 프로그래밍 언어와 라이브러리에서 구현되어 활용되고 있다.

더 읽어볼만한 페이지

최적화 알고리즘 - 기댓값 최대화 알고리즘
최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

L-BFGS
알고리즘 정보
종류	최적화 알고리즘
설계	준 뉴턴 방법
특징	제한된 메모리 사용
최적화 문제 유형	비선형 최적화
메모리 요구 사항	비교적 낮음 (스토리지 제한)
개발 및 발표
개발자	D. C. Liu, J. Nocedal
발표 연도	1989년
논문	On the Limited Memory Method for Large Scale Optimization
상세 정보
사용 분야	대규모 최적화 문제 기계 학습 (최대 엔트로피 모델, 조건부 확률장)
장점	대규모 문제에 적합 비교적 적은 메모리 사용 준 뉴턴 방법의 장점 유지
단점	전역 수렴 보장 없음 매개변수 설정에 민감할 수 있음
관련 알고리즘	BFGS 알고리즘, 켤레 기울기법

2. 알고리즘

L-BFGS 알고리즘은 최적화 문제를 해결하기 위한 반복적인 방법이다. 초기 추정값 $\mathbf{x}_0$ 에서 시작하여, 점차 더 나은 추정값 $\mathbf{x}_1, \mathbf{x}_2, \ldots$ 를 찾아 나간다. 이 과정에서 목적 함수 $f(\mathbf{x})$ 의 기울기(gradient) $g_k:=\nabla f(\mathbf{x}_k)$ 는 가장 가파른 하강 방향을 나타내며, 헤시안 행렬(Hessian Matrix, 이차 미분 함수)의 추정치를 구성하는 데 중요한 역할을 한다.^[38]^[39]

L-BFGS는 다른 준 뉴턴(quasi-Newton) 알고리즘들과 유사하지만, 행렬-벡터 곱 $d_k=-H_k g_k$ 를 계산하는 방식에서 차이가 있다. 여기서 $d_k$ 는 근사적인 뉴턴 방향, $g_k$ 는 현재 기울기, $H_k$ 는 헤시안 행렬의 역행렬이다. L-BFGS 알고리즘의 핵심은 "two-loop recursion"이라고 불리는 효율적인 방법을 사용하여 이 방향 벡터를 계산하는 것이다.
Two-loop recursion을 활용한 탐색 방향 계산L-BFGS는 two-loop recursion을 활용하여 탐색 방향을 계산한다. 기본적인 알고리즘은 다음과 같다.

$k$ 번째 반복에서의 위치 $x_k$ 와 기울기 $g_k\equiv\nabla f(x_k)$ 가 주어지고, 최근 $m$ 번의 업데이트 정보 ( $s_k = x_{k+1} - x_k$ , $y_k = g_{k+1} - g_k$ )를 저장한다.
$\rho_k = \frac{1}{y^{\top}_k s_k}$ 를 계산하고, 초기 역 헤시안 근사 $H^0_k$ 를 설정한다.
Two-loop recursion을 통해 탐색 방향 $z$ 를 계산한다.

Two-loop recursion에 대한 자세한 내용은 하위 섹션에서 별도로 설명한다.

초기 행렬

\gamma_k

의 스케일링은 탐색 방향이 적절한 크기를 갖도록 보장하며, Wolfe 선형 탐색을 사용하여 BFGS 업데이트의 안정성을 확보한다. 일부 구현에서는 Armijo 백트래킹 탐색 (backtracking line search)을 사용하기도 하지만, 곡률 조건 (

\mathbf{y}_k^\top \mathbf{s}_k > 0

)이 항상 만족되지 않을 수 있다.

\mathbf{y}_k^\top \mathbf{s}_k

가 음수이거나 0에 가까운 경우 BFGS 업데이트를 건너뛰는 것은 헤시안 근사가 중요한 곡률 정보를 놓칠 수 있으므로 권장되지 않는다.

2. 1. Two-loop recursion

L-BFGS 알고리즘에서 "two-loop recursion"은 현재 탐색 방향을 계산하기 위해 사용되는 핵심적인 방법이다. 이 방법은 과거의 기울기와 위치 변화 정보를 활용하여 현재의 헤시안 행렬(Hessian Matrix)의 역행렬을 근사하고, 이를 통해 탐색 방향을 결정한다.

알고리즘은 다음과 같이 진행된다.
초기 설정

$k$ 번째 반복에서의 위치 $\mathbf{x}_k$ 와 기울기 $\mathbf{g}_k = \nabla f(\mathbf{x}_k)$ 가 주어져 있다. ( $f$ 는 최소화하려는 함수)
최근 $m$ 번의 업데이트 정보 ( $\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k$ , $\mathbf{y}_k = \mathbf{g}_{k+1} - \mathbf{g}_k$ )를 저장한다.
$\rho_k = \frac{1}{\mathbf{y}_k^\top \mathbf{s}_k}$ 를 계산한다.
초기 역 헤시안 근사 $\mathbf{H}^0_k$ 를 설정한다. (단위 행렬 또는 스케일링된 단위 행렬을 주로 사용)

Two-loop Recursion1. 첫 번째 루프 (Backward Loop):

$\mathbf{q} = \mathbf{g}_k$ 로 초기화한다.
$i = k-1, k-2, \ldots, k-m$ 에 대해 다음을 반복한다:
$\alpha_i = \rho_i \mathbf{s}_i^\top \mathbf{q}$
$\mathbf{q} = \mathbf{q} - \alpha_i \mathbf{y}_i$

2. 초기값 설정:

$\gamma_k = \frac{\mathbf{s}_{k-1}^\top \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^\top \mathbf{y}_{k-1}}$ 를 계산한다.
$\mathbf{H}^0_k = \gamma_k \mathbf{I}$ 로 설정한다. (단위 행렬에 스케일링)
$\mathbf{z} = \mathbf{H}^0_k \mathbf{q}$ 로 초기화한다.

3. 두 번째 루프 (Forward Loop):

$i = k-m, k-m+1, \ldots, k-1$ 에 대해 다음을 반복한다:
$\beta_i = \rho_i \mathbf{y}_i^\top \mathbf{z}$
$\mathbf{z} = \mathbf{z} + \mathbf{s}_i (\alpha_i - \beta_i)$

4. 탐색 방향 결정:

최종적으로 $\mathbf{z} = -\mathbf{z}$ 로 설정하여 탐색 방향을 얻는다. (최소화 문제의 경우)

수식 설명

$\mathbf{s}_k$ : 위치 변화량 ( $k+1$ 번째 위치 - $k$ 번째 위치)
$\mathbf{y}_k$ : 기울기 변화량 ( $k+1$ 번째 기울기 - $k$ 번째 기울기)
$\rho_k$ : $\mathbf{s}_k$ 와 $\mathbf{y}_k$ 의 내적(inner product)의 역수
$\mathbf{H}^0_k$ : 초기 역 헤시안 근사 행렬 (주로 단위 행렬 또는 스케일링된 단위 행렬)
$\alpha_i$ , $\beta_i$ : 각 루프에서 계산되는 스칼라 값
$\mathbf{q}$ , $\mathbf{z}$ : 중간 계산에 사용되는 벡터

핵심 아이디어

과거의 정보 ( $\mathbf{s}_i$ , $\mathbf{y}_i$ )를 이용하여 현재의 기울기 $\mathbf{g}_k$ 를 점진적으로 변형시켜 나간다. (첫 번째 루프)
초기 역 헤시안 근사 $\mathbf{H}^0_k$ 를 이용하여 중간 벡터 $\mathbf{z}$ 를 계산하고, 이를 다시 과거 정보를 이용하여 업데이트한다. (두 번째 루프)
최종적으로 얻어진 $\mathbf{z}$ 벡터가 탐색 방향이 된다.

추가 사항

초기 행렬 $\gamma_k$ 의 스케일링은 탐색 방향이 적절한 크기를 갖도록 보장한다.
Wolfe 선형 탐색을 사용하여 BFGS 업데이트의 안정성을 확보한다.
일부 구현에서는 후진 선형 탐색(backtracking line search)을 사용하기도 하지만, 곡률 조건 ( $\mathbf{y}_k^\top \mathbf{s}_k > 0$ )이 항상 만족되지 않을 수 있다.
$\mathbf{y}_k^\top \mathbf{s}_k$ 가 음수이거나 0에 너무 가까우면 BFGS 업데이트를 건너뛰는 경우도 있지만, 이는 권장되지 않는다.

2. 2. 수렴 조건 및 탐색 방법

L-BFGS 알고리즘은 최적해를 찾기 위해 반복적으로 탐색 방향을 결정하고, 이 방향으로 이동하는 방식을 사용한다. 이때, 탐색 방향은 주로 현재 위치에서의 기울기(gradient) 정보를 기반으로 결정된다.

알고리즘의 수렴을 보장하기 위해, 탐색 방향과 이동 거리는 울프 조건(Wolfe conditions)을 만족하도록 결정된다. 울프 조건은 다음과 같은 두 가지 조건을 포함한다.

충분 감소 조건 (Armijo 조건): 이동 후 함수의 값이 충분히 감소해야 한다.
곡률 조건: 탐색 방향이 함수의 곡률을 충분히 반영해야 한다. 즉, 탐색 방향과 기울기의 내적이 양수여야 한다.

BFGS 업데이트의 안정성을 확보하기 위해 곡률 조건(

y_k^{\top} s_k > 0

)을 만족하는 것이 중요하다. 이 조건은 헤시안 행렬(Hessian matrix)의 역행렬이 양의 정부호(positive definite)를 유지하도록 보장하며, 이는 알고리즘의 수렴에 필수적이다.

일부 구현에서는 곡률 조건을 만족시키기 위해 Armijo 백트래킹 탐색 (backtracking line search)을 사용하기도 하지만, 이 방법은 곡률 조건을 완벽하게 보장하지 못할 수 있다. 따라서,

y_k^{\top} s_k

가 음수이거나 0에 가까운 경우 BFGS 업데이트를 건너뛰는 방식은 권장되지 않는다. 이는 헤시안 근사가 중요한 곡률 정보를 놓칠 수 있기 때문이다.

대신, 곡률 조건을 만족시키기 위해

s_k

와

y_k

를 수정하는 댐핑된 (L)BFGS 업데이트를 사용하는 방법이 더 효과적일 수 있다.

3. 변형 알고리즘

BFGS와 L-BFGS는 매끄러운 함수의 제약 조건이 없는 함수를 최소화하도록 설계되었기 때문에, 미분 가능 함수가 아닌 요소나 제약 조건을 포함하는 함수를 처리하려면 알고리즘을 수정해야 한다. 널리 사용되는 방법은 활성 집합 기반의 활성 집합 방법인데, 이는 현재 반복 지점의 작은 주변 영역으로 제한하면 함수와 제약 조건을 단순화할 수 있다는 아이디어에 기반한다.

L-BFGS 알고리즘의 주요 변형 알고리즘으로는 L-BFGS-B, OWL-QN, O-LBFGS 등이 있다. L-BFGS-B는 변수에 대한 간단한 상자 제약 조건(경계 제약 조건)을 처리하도록 L-BFGS를 확장한 알고리즘이다. OWL-QN(Orthant-Wise Limited-memory Quasi-Newton)은 희소(sparse) 모델에 특화된 L-BFGS 변형 알고리즘으로, L1 정규화 모델을 적합하는 데 사용된다. O-LBFGS(Online L-BFGS)는 확률적 경사 하강법(SGD)처럼 계산 복잡성을 줄이기 위해 사용되는 온라인 근사법이다.

3. 1. L-BFGS-B

L-BFGS-B 알고리즘은 변수에 대한 간단한 박스 제약 조건 (바운드 제약 조건이라고도 함)을 처리하도록 L-BFGS를 확장한 것이다. 즉, ''l''_i ≤ ''x''_i ≤ ''u''_i 형태의 제약 조건이며, 여기서 ''l''_i와 ''u''_i는 각 변수 ''x''_i에 대한 상수 하한 및 상한이다 (각 변수에 대해 두 경계 중 하나 또는 둘 다 생략될 수 있음).^[7]^[8] 이 방법은 각 단계에서 고정 변수와 자유 변수를 식별한 다음 (간단한 기울기 방법을 사용) 자유 변수에 대해서만 L-BFGS 방법을 사용하여 더 높은 정확도를 얻은 다음 이 과정을 반복하여 작동한다.

3. 2. OWL-QN

직교사분면 제한 메모리 준 뉴턴 (Orthant-Wise Limited-memory Quasi-Newton, OWL-QN)은

\ell_1

노름(정규화) 모델을 적합하기 위한 L-BFGS 변형 알고리즘으로, 이러한 모델의 고유한 희소 행렬을 활용한다.^[6]

OWL-QN은 다음 형태의 함수를 최소화한다.

:

f(\vec x) = g(\vec x) + C \|\vec x\|_1

여기서

g

는 미분 가능 함수인 볼록 함수 손실 함수이다. 이 방법은 활성 집합 유형의 방법으로, 각 반복에서 변수의 각 구성 요소의 부호를 추정하고, 후속 단계가 동일한 부호를 갖도록 제한한다. 부호가 고정되면 미분 불가능한

\|\vec x\|_1

항은 L-BFGS로 처리할 수 있는 부드러운 선형 항이 된다. L-BFGS 단계를 거친 후, 이 방법은 일부 변수가 부호를 변경하도록 허용하고, 과정을 반복한다.

3. 3. O-LBFGS

Schraudolph 등은 BFGS와 L-BFGS에 대한 온라인 근사법을 제안했다.^[43] 이는 확률적 경사 하강법(SGD)과 유사하게, 각 반복마다 전체 데이터 집합이 아닌 임의로 추출된 부분 집합에 대한 오차 함수와 기울기를 평가함으로써 계산 복잡성을 줄이는 데 사용될 수 있다. O-LBFGS는 전역적으로 거의 확실하게 수렴하는 것으로 나타났지만,^[45] BFGS의 온라인 근사(O-BFGS)는 반드시 수렴하지는 않는다.^[44]

4. 응용

L-BFGS는 로그-선형(MaxEnt) 모델과 조건부 무작위장을 $\ell_2$ -정규화로 적합시키는 데 "선택 알고리즘"이라고 불려왔다.^[2]^[6] L-BFGS 방법은 Multinomial logistic regression|다항 로지스틱 회귀^영어나 $\ell_2$ 정규화가 있는 조건부 확률장의 피팅에 "the algorithm of choice"로 여겨진다.^[22]^[23]

5. 구현

L-BFGS 알고리즘 및 변형 알고리즘들의 주요 구현체는 다음과 같다.

오픈 소스 구현
ALGLIB: C++ 및 C#으로 L-BFGS 및 상자/선형 제약 버전인 BLEIC를 구현한다.
R: `optim` 범용 최적화 루틴은 L-BFGS-B 메서드를 사용한다.
SciPy: `scipy.optimize` 모듈의 `minimize` 메서드는 L-BFGS-B를 구현한다.
Fortran 77 (및 Fortran 90 인터페이스 포함) 참조 구현.^[13]^[14] 다른 많은 언어로도 변환되었다.

비(非) 오픈 소스 구현
L-BFGS-B: ACM TOMS 알고리즘 778로 구현.^[8]^[12] 2011년 2월, 원저자들의 주요 업데이트(버전 3.0)가 있었다.
OWL-QN C++ 구현.^[6]^[15]

참조

_[1] 논문 On the Limited Memory Method for Large Scale Optimization http://www.ece.north[...]
_[2] 간행물 A comparison of algorithms for maximum entropy parameter estimation https://dl.acm.org/c[...] 2002
_[3] 논문 The solution of non linear finite element equations
_[4] 논문 Updating Quasi-Newton Matrices with Limited Storage
_[5] 논문 Representations of Quasi-Newton Matrices and their use in Limited Memory Methods
_[6] 서적 Proceedings of the 24th International Conference on Machine Learning
_[7] 논문 A Limited Memory Algorithm for Bound Constrained Optimization https://digital.libr[...]
_[8] 논문 L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization
_[9] 간행물 A stochastic quasi-Newton method for online convex optimization
_[10] 논문 Global convergence of online limited memory BFGS http://www.jmlr.org/[...]
_[11] 논문 RES: Regularized Stochastic BFGS Algorithm
_[12] 웹사이트 TOMS Home http://toms.acm.org/
_[13] 논문 Remark on "algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization"
_[14] 웹사이트 L-BFGS-B Nonlinear Optimization Code http://users.iems.no[...]
_[15] 웹사이트 Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives https://www.microsof[...]
_[16] 논문 On the Limited Memory Method for Large Scale Optimization http://www.ece.north[...]
_[17] 간행물 A comparison of algorithms for maximum entropy parameter estimation https://dl.acm.org/c[...] 2002
_[18] 서적 Proceedings of the 24th International Conference on Machine Learning
_[19] 논문 The solution of non linear finite element equations
_[20] 논문 Updating Quasi-Newton Matrices with Limited Storage
_[21] 논문 Representations of Quasi-Newton Matrices and their use in Limited Memory Methods
_[22] 간행물 A comparison of algorithms for maximum entropy parameter estimation https://dl.acm.org/c[...] 2002
_[23] 서적 Proceedings of the 24th International Conference on Machine Learning
_[24] 논문 A Limited Memory Algorithm for Bound Constrained Optimization https://digital.libr[...]
_[25] 논문 L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization
_[26] 서적 Proceedings of the 24th International Conference on Machine Learning
_[27] 간행물 A stochastic quasi-Newton method for online convex optimization
_[28] 논문 Global convergence of online limited memory BFGS http://www.jmlr.org/[...]
_[29] 논문 RES: Regularized Stochastic BFGS Algorithm
_[30] 논문 L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization
_[31] 웹사이트 TOMS Home http://toms.acm.org/ 2022-11-03
_[32] 논문 Remark on "algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization"
_[33] 웹사이트 L-BFGS-B Nonlinear Optimization Code http://users.iems.no[...] 2022-11-03
_[34] 서적 Proceedings of the 24th International Conference on Machine Learning
_[35] 웹사이트 Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives https://www.microsof[...] 2022-11-03
_[36] 컨퍼런스 A comparison of algorithms for maximum entropy parameter estimation https://dl.acm.org/c[...] 2002
_[37] 서적 Proceedings of the 24th International Conference on Machine Learning
_[38] 저널 The solution of non linear finite element equations
_[39] 저널 Updating Quasi-Newton Matrices with Limited Storage
_[40] 저널 Representations of Quasi-Newton Matrices and their use in Limited Memory Methods
_[41] 저널 A Limited Memory Algorithm for Bound Constrained Optimization https://digital.libr[...]
_[42] 저널 L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization
_[43] 컨퍼런스 A stochastic quasi-Newton method for online convex optimization
_[44] 저널 RES: Regularized Stochastic BFGS Algorithm
_[45] 저널 Global convergence of online limited memory BFGS http://www.jmlr.org/[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com