L-BFGS

L-BFGS (혹은 Limited-memory BFGS, LM-BFGS) 준-뉴턴 방식 ()의 최적화 알고리즘이다. 제한된 컴퓨터 메모리를 이용하여 기존 BFGS () 알고리즘을 속도면에서 개선한 알고리즘이다. (결과는 근사값). 본 알고리즘은 Adam과 함께 머신 러닝에 있어서 널리 사용되는 파라메터 추정 알고리즘이다. 본 알고리즘의 목적함수는 formula_1의 최소값을 찾는 것이며, 여기서, formula_2는 unconstrained value의 real-vector이고, formula_3는 미분가능한 스칼라 함수이다.
원래의 BFGS와 같이, L-BFGS 알고리즘은 variable space의 검색을 조정하는 추정된 inverse 를 이용한다. 하지만 BFGS는 inverse Hessian에서 추정된 전체 formula_4 을 이용하고, L-BFGS는 단지 몇개의 벡터만을 저장한다. 비록 일부의 벡터이지만 이런 일부의 벡터 역시 암시적으로 대표성을 지니고 있다. (주로 홀수개의 벡터를 지정하고 10 이하. 문헌에서 봤는데 이유는 기억이 가물가물.. ) 여기서 "n은" 문제에서 변수의 갯수를 의미한다. 선형 메모리의 요구사항으로 인해, L-BFGS는 많은 변수를 가진 최적화 문제에 적합하다고 알려져 있다. inverse Hessian H"k" 대신에 L-BFGS는 과거 m update의 기록과 gradient ∇"f"(x) 이용한다. 일반적으로 과거 기록인 m 의 크기는 주로 10 이하를 선정한다.
알고리즘 (Algorithm).
알고리즘은 최적 변수의 초기 추정값, formula_5,과 함께 시작하고, 반복적으로 더 나은 추정값 formula_6을 평가하는 과정으로 진행된다. 목적 함수의 미분, formula_7, steepest descent의 방향을 정하고, 이차 미분 함수인 Hessian 메트릭스의 추정를 구성하는데 아주 중요한 요소이다.
L-BFGS는 다른 quasi-Newton 알고리즘과 많은 특징을 공유하지만, 메트릭스-벡터의 곱, formula_8, 이 수행되는 방식에서 매우 다르다. 여기서, formula_9는 대략적인 뉴튼의 방향이고, formula_10는 현재의 gradient, formula_11는 Hessian 메트릭스의 역행렬이다. 이러한 방향 벡터를 정하기 위한 업데이트의 기록을 이용하는 많은 접근방식이 있으며, 여기서는 소위 "two loop recursion"이라고 불리는 일반적인 접근법 (알고리즘)을 소개한다.
k번째 iteration에서의 위치와 gradient를 formula_12, formula_13라 하자. 여기서 formula_3는 최소화되어야 함수이고, 모든 벡터들은 컬럼 벡터이다. 마지막 업데이트는 저장했다고 가정하자.
formula_17 이고, formula_18는 inverse Hessian의 초기 가정이라고 하자. BFGS를 기반으로 inverse Hessian은 아래와 같다.
하나의 고정된 에서 벡터의 시퀀스를 formula_20 as formula_21 와 formula_22 로 정의하자. 그때, formula_23로부터 formula_24를 계산하는 번복 알고리즘은 formula_25 로 정의하고, 다음과 같이 formula_26를 정한다.
또 하나의 벡터의 시퀀스 formula_27는 formula_28로 정한다. formula_29, formula_30, formula_31를 결정하는 또하나의 recursive 알고리즘이 있다. formula_32의 값은 이제 오르막 방향이며, 다음과 같이 내리막 방향을 계산할 수 있다.
상기의 공식은 최소화 문제 formula_34를 위한 방향 검색을 제공한다. 최대화 문제에 대해서는, 의 부호를 변경해야 한다. 초기 inverse Hessian formula_18 근사값은 대각 행렬값이나, 효율적인 계산 방식인 identity 메트릭스의 배수로 선택한다.
초기 메트릭스 formula_36의 스케일은 방향 검색이 잘 되도록 배율되어야 하고, 단위 스텝의 길이가 대부분의 iteration에서 적용가능하여야 한다. 는 curvature조건을 만족하고, BFGS의 업데이트를 안정시키기 위해 사용된다.
어떤 소프트웨어에서는 를 이용하지만, 이것은 선택된 스텝에 의해 curvature 조건 formula_37 만족되어 져야 함을 보증하지 못한다. 어떤 알고리즘 구현에서는 formula_38가 음수이거나, zero (영)에 가까우면 건너 뛰는 방식을 취하지만, 이런 접근법은 일반적으로 권장하지는 않는다. 왜냐하면 너무 자주 건너 뛰므로써 중요한 곡면 정보를 파악하기 힘들고, 적절한 Hessian 추정을 못할 수 있기 때문이다.
이러한 two loop update는 단지 inverse Hessian 잘 작동한다. 다른 방식으로 inverse Hessian 추정하는 직접 근사 Hessian formula_39를 이용하는 방식도 개발되어 있다.
변형된 알고리즘들 (Variants).
BFGS와 L-BFGS는 구속조건들 없이 Smooth 함수를 최적화하도록 설계되었기 때문에, L-BFGS 알고리즘은 미분이 되지 않은 함수나 구속들을 포함하는 함수에 적용하기 위해서는 수정이 필요하다. 가장 인기있는 변형된 알고리즘은 active-set방식이라 불린다. 이 아이디어는 현재 iterate의 작은 근사값으로 구속했을 때, 함수와 구속을 단순화 할 수 있다는 것이다.
L-BFGS-B.
L-BFGS-B 알고리즘은 simple box 구속들을 다루기 위해서 확장된 방식이다. 단순화된 구속은 하한과 상한 경계가 있는 형식이며, 각 를 위해, 양 방향 혹은 한쪽 방향의 경계는 제거되어 질 수도 있다 . 이 방법은 (단순 gradient 방식을 이용하는) 각 스텝에서 고정과 자유 변수들을 결정하고, 높은 정확도을 얻기 위해서 자유 변수에 L-BFGS를 이용하고, 과정을 반복함으로써 동작한다.
OWL-QN.
Orthant-wise limited-memory quasi-Newton (OWL-QN)는 formula_40-regularized 모델을 피팅하고, inherent sparsity 모델을 이용하기 위해 변형된 L-BFGS알고리즘이다. 아래의 형태의 함수를 최소화 (최적화)한다.
여기서 formula_42는 미분가능한 convex 손실 함수이다. 이 방식은 하나의 active-set 방식이며, 변수들의 각 요소의 부호를 평가(추정, 예측)하고, 같은 부호를 가지기 위해 서브 시퀀스 스텝을 제약한다. 일단 부호가 고정되면, 미분이 가능하지 않은 formula_43 term은 하나의 smooth linear term 이 된다. 이런 smooth linear term은 L-BFGS에 의해 이용될 수 있다. 하나의 L-BFGS스텝 이후, 이 방식은 부호를 변경하기 위한 일부 변수들을 허용하고, 과정을 반복한다.
O-LBFGS.
Schraudolph 둥은 BFGS와 L-BFGS에 대한 온라인 근사법을 제안했다. 와 유사하게, 이 방법은 에러 함수와 각 iteration에서의 전체 데이터 셋에 대한 randomly drawn subset의 gradient를 평가함으로써, 계산의 복잡성을 감소시키기 위해 사용될 수 있다. BFGS 혹은 O-BFGS의 온라인 근사법은 반드시 수렴하지는 않지만, O-LBFGS는 거의 글로벌하게 수렴함을 보여준다.