BFGS z ograniczoną pamięcią - Limited-memory BFGS

Ograniczona pamięć BFGS ( L-BFGS lub LM-BFGS ) to algorytm optymalizacji z rodziny metod quasi-Newtona, który aproksymuje algorytm Broydena-Fletchera-Goldfarba-Shanno (BFGS) przy użyciu ograniczonej ilości pamięci komputera . Jest to popularny algorytm estymacji parametrów w uczeniu maszynowym . Zadaniem algorytmu jest minimalizacja ponad nieograniczonych wartości wektora rzeczywistego, gdzie jest różniczkowalna funkcja skalarna.

Podobnie jak w oryginalnym BFGS, L-BFGS wykorzystuje oszacowanie odwrotnej macierzy Hessian do sterowania przeszukiwaniem przestrzeni zmiennych, ale gdzie BFGS przechowuje gęste przybliżenie do odwrotnej macierzy Hessian ( n jest liczbą zmiennych w zadaniu), L-BFGS przechowuje tylko kilka wektorów, które niejawnie reprezentują przybliżenie. Ze względu na wynikające stąd zapotrzebowanie na pamięć liniową, metoda L-BFGS jest szczególnie odpowiednia do rozwiązywania problemów optymalizacji z wieloma zmiennymi. Zamiast odwrotności Hess H k , L-BFGS utrzymuje historię ostatnich m aktualizacji pozycji x i gradientu ∇ f ( x ), gdzie generalnie rozmiar historii m może być mały (często ). Te aktualizacje są używane do niejawnego wykonywania operacji wymagających produktu wektorowego H k .

Algorytm

Algorytm rozpoczyna się od wstępnego oszacowania optymalnej wartości i kontynuuje iteracyjne udoskonalanie tego oszacowania sekwencją lepszych oszacowań . Pochodne funkcji są wykorzystywane jako kluczowy sterownik algorytmu do identyfikacji kierunku najbardziej stromego opadania, a także do oszacowania macierzy Hessian (druga pochodna) .

L-BFGS ma wiele wspólnych cech z innymi algorytmami quasi-Newtona, ale bardzo różni się sposobem przeprowadzania mnożenia macierzy-wektora , gdzie jest przybliżonym kierunkiem Newtona, jest bieżącym gradientem i jest odwrotnością macierzy Hess. Istnieje wiele opublikowanych podejść wykorzystujących historię aktualizacji do utworzenia tego wektora kierunku. Tutaj podajemy wspólne podejście, tak zwaną „rekurencję dwupętlową”.

Przyjmujemy, jak podano , pozycję w k -tej iteracji i gdzie jest minimalizowana funkcja, a wszystkie wektory są wektorami kolumnowymi. Zakładamy również, że zapisaliśmy ostatnie m aktualizacji formularza

.

Zdefiniujemy , i będziemy „początkowym” przybliżeniem odwrotnego Hessu, od którego zaczyna się nasze oszacowanie w iteracji k .

Algorytm oparty jest na rekurencji BFGS dla odwrotności hessyjskiej as

Dla ustalonego k definiujemy ciąg wektorów jako i . Następnie rekurencyjny algorytm obliczania od ma na celu zdefiniowanie i . Inną sekwencję wektorów definiujemy również jako . Istnieje inny rekurencyjny algorytm obliczania tych wektorów, który polega na zdefiniowaniu, a następnie rekurencyjnym zdefiniowaniu i . Wartością jest wtedy nasz kierunek wznoszenia.

W ten sposób możemy obliczyć kierunek opadania w następujący sposób:


Sformułowanie to wyznacza kierunek poszukiwań problemu minimalizacji, tj . . W przypadku problemów z maksymalizacją należy zatem zamiast tego użyć -z . Należy zauważyć, że początkowa przybliżona odwrotność hesjańska jest wybierana jako macierz diagonalna lub nawet wielokrotność macierzy jednostkowej, ponieważ jest to wydajna numerycznie.

Skalowanie macierzy początkowej zapewnia, że ​​kierunek wyszukiwania jest dobrze wyskalowany, a zatem długość kroku jednostkowego jest akceptowana w większości iteracji. Wyszukiwania linia Wolfe jest używany w celu zapewnienia, że warunek jest spełniony i krzywizna aktualizację BFGS jest stabilny. Należy zauważyć, że niektóre implementacje oprogramowania wykorzystują wyszukiwanie linii Armijo z wycofywaniem , ale nie mogą zagwarantować, że warunek krzywizny zostanie spełniony przez wybrany krok, ponieważ długość kroku jest większa niż może być potrzebna do spełnienia tego warunku. Niektóre implementacje rozwiązują ten problem przez pominięcie aktualizacji BFGS, gdy jest ona ujemna lub zbyt bliska zeru, ale to podejście nie jest ogólnie zalecane, ponieważ aktualizacje mogą być pomijane zbyt często, aby umożliwić przybliżenie Hessowi uchwycenie ważnych informacji o krzywiźnie.

Ta aktualizacja z dwiema pętlami działa tylko dla odwrotnego hesjanu. Opracowano również podejścia do implementacji L-BFGS przy użyciu bezpośredniego przybliżenia hesjanu , podobnie jak inne sposoby przybliżania odwrotności hessu.

Aplikacje

L-BFGS został nazwany "algorytmem wyboru" do dopasowywania modeli log-liniowych (MaxEnt) i warunkowych pól losowych z -regularyzacją .

Warianty

Od BFGS (a więc BFGS L) jest zaprojektowany, aby zminimalizować gładkie funkcje, bez ograniczeń , algorytm L BFGS może być modyfikowany na funkcje, które obejmują uchwyt innych niż różniczkowalną składników lub ograniczenia. Popularną klasą modyfikacji są metody aktywnego zbioru, oparte na koncepcji aktywnego zbioru . Pomysł polega na tym, że gdy ograniczymy się do małego sąsiedztwa bieżącego iteracji, funkcję i ograniczenia można uprościć.

L-BFGS-B

L-BFGS B algorytm obejmuje L-BFGS obsługiwać ograniczenia proste pudełka (ps) ograniczeń związanych zmiennych; to znaczy, ograniczenia postaci l ix iu i gdzie l i i u i są odpowiednio stałymi dolnymi i górnymi granicami dla każdej zmiennej (dla każdego x i można pominąć jedną lub obie granice). Metoda działa poprzez identyfikację stałych i wolnych zmiennych na każdym kroku (przy użyciu prostej metody gradientowej), a następnie użycie metody L-BFGS na wolnych zmiennych tylko w celu uzyskania większej dokładności, a następnie powtórzenie procesu.

SOWA-QN

Orthant-mądry o ograniczonej pamięci quasi-Newton ( OWL-QN ) to wariant L-BFGS do dopasowywania - uregulowanych modeli, wykorzystujący wrodzoną rzadkość takich modeli. Minimalizuje funkcje formy

gdzie jest różniczkowalną wypukłą funkcją straty . Metoda jest metodą typu active-set: w każdej iteracji szacuje znak każdego składnika zmiennej i ogranicza kolejny krok do tego samego znaku. Po ustaleniu znaku termin nieróżnicujący staje się gładkim terminem liniowym, który może być obsługiwany przez L-BFGS. Po kroku L-BFGS metoda pozwala niektórym zmiennym na zmianę znaku i powtarza proces.

O-LBFGS

Schraudolph i in. przedstawić internetowe przybliżenie zarówno BFGS, jak i L-BFGS. Podobnie jak w przypadku gradientu stochastycznego , można to wykorzystać do zmniejszenia złożoności obliczeniowej poprzez ocenę funkcji błędu i gradientu na losowo wylosowanym podzbiorze ogólnego zbioru danych w każdej iteracji. Wykazano, że O-LBFGS ma globalną prawie pewną zbieżność, podczas gdy aproksymacja online BFGS (O-BFGS) niekoniecznie jest zbieżna.

Realizacja wariantów

Wariant L-BFGS-B istnieje również jako algorytm ACM TOMS 778. W lutym 2011 roku niektórzy autorzy oryginalnego kodu L-BFGS-B opublikowali dużą aktualizację (wersja 3.0).

Implementacja referencyjna jest dostępna w Fortran 77 (oraz z interfejsem Fortran 90 ). Ta wersja, podobnie jak starsze wersje, została przekonwertowana na wiele innych języków.

Implementacja OWL-QN jest dostępna jako implementacja C++ przez jej projektantów.

Prace cytowane

Dalsza lektura