Jak działa L-BFGS?

Celem artykułu była optymalizacja niektórych parametrów poprzez maksymalizację znormalizowanego prawdopodobieństwa dziennika. Następnie obliczają pochodne częściowe. A potem autorzy wspominają, że optymalizują równanie za pomocą L-BFGS, standardowej procedury quasi-Newtona w celu optymalizacji płynnych funkcji wielu zmiennych (bez dalszych szczegółów).

Jak to działa ?

Zasadniczo myśl o L-BFGS jako sposobie znajdowania (lokalnego) minimum funkcji celu, wykorzystując wartości funkcji celu i gradient funkcji celu. Ten poziom opisu obejmuje jednak wiele metod optymalizacji oprócz L-BFGS. Więcej informacji na ten temat można znaleźć w sekcji 7.2 Nocedal and Wright „Optymalizacja numeryczna, wydanie drugie” http://www.springer.com/us/book/9780387303031 . Bardzo pobieżna dyskusja na temat L-BFGS znajduje się na stronie https://en.wikipedia.org/wiki/Limited-memory_BFGS .

Metoda pierwszego rzędu oznacza, że ​​stosowane są gradienty (pierwsze pochodne) (i być może wartości funkcji obiektywnych), ale nie Hesjan (drugie pochodne). Pomyśl na przykład o spadku gradientowym i stromym, między innymi.

Metoda drugiego rzędu oznacza, że ​​używane są gradienty i Hesjan (i być może wartości funkcji obiektywnych). Metody drugiego rzędu mogą być oparte na

1. „Dokładna” macierz heskańska (lub skończone różnice gradientów), w którym to przypadku są znane jako metody Newtona lub

2. Metody quasi-Newtona, które przybliżają Hesję na podstawie różnic gradientów w kilku iteracjach, poprzez nałożenie warunku „siecznego” (quasi-Newtona). Istnieje wiele różnych metod Quasi-Newtona, które na różne sposoby szacują Hesję. Jednym z najbardziej popularnych jest BFGS. Przybliżenie BFGS Hesji może być oparte na pełnej historii gradientów, w którym to przypadku jest określane jako BFGS, lub może być oparte tylko na najnowszych gradientach m, w którym to przypadku jest znane jako ograniczona pamięć BFGS, w skrócie jako L-BFGS. Zaletą L-BFGS jest to, że wymaga tylko zachowania najnowszych gradientów m, gdzie m wynosi zwykle około 10 do 20, co jest znacznie mniejszym wymaganiem do przechowywania niż n * (n + 1) / 2 elementów wymaganych do przechowywania pełnego (trójkąt) szacunku Hesji, zgodnie z wymaganiami BFGS, gdzie n jest wymiarem problemowym. W przeciwieństwie do (pełnego) BFGS, oszacowanie Hesji nigdy nie jest jawnie formowane ani przechowywane w L-BFGS (chociaż niektóre implementacje BFGS jedynie tworzą i aktualizują czynnik Choelsky'ego przybliżenia Hesji, a nie samego przybliżenia Hesji); raczej obliczenia, które byłyby wymagane przy oszacowaniu Hesji, są wykonywane bez wyraźnego ich sformułowania. L-BFGS jest używany zamiast BFGS w przypadku bardzo dużych problemów (gdy n jest bardzo duży), ale może nie działać tak dobrze jak BFGS. Dlatego BFGS jest lepszy niż L-BFGS, gdy można spełnić wymagania dotyczące pamięci BFGS. Z drugiej strony L-BFGS może nie być znacznie gorszy w działaniu niż BFGS. oszacowanie Hesji nigdy nie jest jawnie formowane ani przechowywane w L-BFGS (chociaż niektóre implementacje BFGS jedynie tworzą i aktualizują współczynnik Choelsky'ego przybliżenia Hesji, a nie samego przybliżenia Hesji); raczej obliczenia, które byłyby wymagane przy oszacowaniu Hesji, są wykonywane bez wyraźnego ich sformułowania. L-BFGS jest używany zamiast BFGS w przypadku bardzo dużych problemów (gdy n jest bardzo duży), ale może nie działać tak dobrze jak BFGS. Dlatego BFGS jest lepszy niż L-BFGS, gdy można spełnić wymagania dotyczące pamięci BFGS. Z drugiej strony L-BFGS może nie być znacznie gorszy w działaniu niż BFGS. oszacowanie Hesji nigdy nie jest jawnie formowane ani przechowywane w L-BFGS (chociaż niektóre implementacje BFGS jedynie tworzą i aktualizują współczynnik Choelsky'ego przybliżenia Hesji, a nie samego przybliżenia Hesji); raczej obliczenia, które byłyby wymagane przy oszacowaniu Hesji, są wykonywane bez wyraźnego ich sformułowania. L-BFGS jest używany zamiast BFGS w przypadku bardzo dużych problemów (gdy n jest bardzo duży), ale może nie działać tak dobrze jak BFGS. Dlatego BFGS jest lepszy niż L-BFGS, gdy można spełnić wymagania dotyczące pamięci BFGS. Z drugiej strony L-BFGS może nie być znacznie gorszy w działaniu niż BFGS. obliczenia, które byłyby wymagane przy oszacowaniu Hesji, zostały wykonane bez wyraźnego ich sformułowania. L-BFGS jest używany zamiast BFGS w przypadku bardzo dużych problemów (gdy n jest bardzo duży), ale może nie działać tak dobrze jak BFGS. Dlatego BFGS jest lepszy niż L-BFGS, gdy można spełnić wymagania dotyczące pamięci BFGS. Z drugiej strony L-BFGS może nie być znacznie gorszy w działaniu niż BFGS. obliczenia, które byłyby wymagane przy oszacowaniu Hesji, zostały wykonane bez wyraźnego ich sformułowania. L-BFGS jest używany zamiast BFGS w przypadku bardzo dużych problemów (gdy n jest bardzo duży), ale może nie działać tak dobrze jak BFGS. Dlatego BFGS jest lepszy niż L-BFGS, gdy można spełnić wymagania dotyczące pamięci BFGS. Z drugiej strony L-BFGS może nie być znacznie gorszy w działaniu niż BFGS.

Nawet na tym poziomie opisu istnieje wiele wariantów. Na przykład metody mogą być całkowicie niezabezpieczone, w którym to przypadku wszystko idzie, i mogą się nie zbiegać, nawet w przypadku problemów wypukłych. Lub można je zabezpieczyć. Metody zabezpieczone są zwykle oparte na regionach zaufania lub wyszukiwaniu linii i mają na celu zapewnienie konwergencji do czegoś. Bardzo ważne jest, że sama wiedza o metodzie L-BFGS sama w sobie nie mówi, jaki rodzaj zabezpieczenia, jeśli w ogóle, jest stosowany. To trochę tak, jakby powiedzieć, że samochód to 4-drzwiowy sedan - ale oczywiście nie wszystkie 4-drzwiowe sedany mają takie same osiągi lub niezawodność. To tylko jeden atrybut algorytmu optymalizacji.