Czy nie ma sensu używać algorytmów optymalizacji opartych na gradiencie, jeśli można podać tylko gradient liczbowy? Jeśli nie, to po co podawać gradient liczbowy, jeśli przeprowadzanie różnicowania skończonego dla samej biblioteki optymalizacji jest banalne?
[EDYTOWAĆ]
Aby wyjaśnić, moje pytanie rzeczywiście ma bardziej ogólny sens niż konkretne zastosowanie. Chociaż moim obszarem zastosowania jest optymalizacja prawdopodobieństwa w różnych ramach statystycznych.
Mój problem z automatycznym różnicowaniem polega na tym, że zawsze wydaje się, że jest jakiś haczyk. Zarówno biblioteka AD nie może się propagować do zewnętrznych wywołań bibliotecznych (jak BLAS), albo musisz przeprojektować swój przepływ pracy tak drastycznie, że trudno jest sobie z tym poradzić ... szczególnie jeśli pracujesz z językami wrażliwymi na typy. Moje problemy z AD to zupełnie osobny problem. Ale chcę wierzyć!
Chyba muszę lepiej sformułować swoje pytanie, ale robię to źle. Jeśli masz opcję albo użycia algorytmu optymalizacji bez pochodnych, albo algorytmu optymalizacji opartego na pochodnych z zastrzeżeniem, że mogę dać mu tylko gradient liczbowy, który z nich będzie lepszy?
źródło
Odpowiedzi:
Aby uzupełnić doskonałą odpowiedź Briana, pozwólcie, że przedstawię nieco (redakcyjne) tło. Metody optymalizacji bez pochodnych są zdefiniowane jako metody, które wykorzystują tylko oceny funkcji, i są w zasadzie wszystkimi odmianami „próbkowania dopuszczalnego zestawu mniej więcej systematycznie i zapisywania najlepszej wartości funkcji” - to wszystko, co możesz zrobić, biorąc pod uwagę informacje. Metody te można z grubsza podzielić
Metody stochastyczne , w których wybór próbek jest zasadniczo losowy (co oznacza, że losowość jest kluczowym składnikiem; mogą istnieć inne, deterministyczne składniki). Metody te są często motywowane procesami fizycznymi lub biologicznymi i mają odpowiednie nazwy, takie jak „symulowane wyżarzanie”, „algorytmy genetyczne” lub „metoda roju cząstek / świetlika / mrowiska”. Rzadko istnieje jakakolwiek teoria konwergencji poza „jeśli spróbujesz wystarczająco długo, trafisz wszystkie punkty (w tym minimalizator) z prawdopodobieństwem1 „(czy to się stanie - z dużym prawdopodobieństwem - przed śmiercią wszechświata przed upałem to inna sprawa ...) Jako matematyk rozważałbym te metody w ostateczności: jeśli nie wiesz nic o swojej funkcja, to wszystko, co możesz zrobić, i możesz mieć szczęście.
Metody deterministyczne , w których dobór próbek nie jest przypadkowy, tj. Oparty wyłącznie na wcześniejszych ocenach funkcji. Najbardziej znanym przykładem jest prawdopodobnie metoda simpleksowa Neldera-Meada; inne generują metody wyszukiwania zestawów . Ważne jest, aby zdać sobie sprawę, że może to zadziałać tylko wtedy, gdy istnieje jakakolwiek (możliwa do wykorzystania) zależność między wartością funkcji w różnych punktach - tj. Pewna płynność funkcji. W rzeczywistości teoria zbieżności dla np. Metody Neldera-Meada opiera się na konstruowaniu niejednorodnościprzybliżenie różnic skończonych gradientu na podstawie wartości funkcji w wierzchołkach simpleksu i pokazanie, że zbiega się on zarówno z dokładnym gradientem, jak i zerem, gdy simpleks kurczy się do punktu. (Wariant oparty na standardowym przybliżeniu różnic skończonych nazywa się wyszukiwaniem kompasu ).
Metody oparte na modelu , w których wartości funkcji są wykorzystywane do budowy lokalnego modelu funkcji (np. Przez interpolację), który jest następnie minimalizowany przy użyciu standardowych metod (opartych na gradiencie / Hesji). Ponieważ przybliżenie skończonej różnicy jest równoważne dokładnej pochodnej interpolantu wielomianowego, klasyczne podejście „gradientu numerycznego” również należy do tej klasy.
Jak widać, granice między tymi klasami są płynne, a często tylko kwestią interpretacji. Ale morał powinien być jasny: upewnij się, że wykorzystujesz wszystkie dostępne informacje o funkcji, którą minimalizujesz. Cytując Corneliusa Lanczosa:
W końcu, jeśli nie wiesz nic o swojej funkcji, równie dobrze może ona być całkowicie losowa, a minimalizowanie losowej wartości jest zadaniem głupca ...
źródło
Jeśli twój cel jest płynny, to zastosowanie przybliżenia różnic skończonych do pochodnej jest często bardziej skuteczne niż użycie algorytmu optymalizacji bez pochodnych. Jeśli masz kod, który dokładnie oblicza pochodne, zwykle najlepiej jest użyć tego kodu, a nie przybliżonych różnic skończonych.
Chociaż niektóre biblioteki optymalizacyjne obliczą przybliżone różnice skończone dla Ciebie automatycznie za pomocą heurystyki w celu ustalenia parametrów wielkości kroku, lepiej może być użycie własnych procedur do obliczenia przybliżonych różnic skończonych, ponieważ masz lepszą wiedzę na temat odpowiednich rozmiarów kroków lub z powodu specjalna struktura w funkcji, którą twój kod może wykorzystać.
Inną opcją, która często się opłaca, jest zastosowanie technik automatycznego różnicowania w celu utworzenia podprogramu, który oblicza pochodne analityczne z kodu źródłowego do obliczania samej funkcji celu.
źródło
Twoje pytanie dotyczy optymalizatorów opartych na gradiencie, więc myślę, że Brian miał rację. Chciałbym jedynie podzielić się niektórymi problemami, ponieważ sam obecnie mam z tym problem.
Problemy z różnicą skończoną to 1) wydajność, ponieważ musisz ponownie ocenić funkcję dla każdego wymiaru i 2) może być trudne wybranie dobrego rozmiaru kroku. Jeśli krok jest zbyt duży, założenie liniowości funkcji może się nie utrzymać. Jeśli krok jest zbyt mały, może napotkać szum w samej funkcji, ponieważ pochodne wzmacniają hałas. To ostatnie może stanowić prawdziwy problem, jeśli funkcja wymaga rozwiązania równań różniczkowych. Jeśli możliwe jest obliczenie gradientów analitycznie lub za pomocą równań wrażliwości, z pewnością będzie ono dokładniejsze i być może szybsze.
Istnieje inne podejście, które możesz wypróbować, jeśli nie zainwestowałeś już zbyt wiele czasu w oprogramowanie, a mianowicie uruchomić go ze złożoną arytmetyką. Nazywa się to złożonym różnicowaniem stopni . Podstawową ideą jest to, że kiedy oceniasz funkcję, jeśli chcesz jej gradient w stosunku do parametru X, ustaw wyobrażoną część X na bardzo małą liczbę eps . Po wykonaniu obliczeń urojoną częścią wartości funkcji podzielonej przez eps jest gradient w odniesieniu do X. Jeśli chcesz gradient w odniesieniu do Y, musisz oczywiście zrobić to wszystko ponownie. Interesujące jest to, że epsmoże być bardzo mały. Powodem tego jest fakt, że normalne reguły rachunku różniczkowego są dokładnie odzwierciedlone w regułach złożonej arytmetyki.
To powiedziawszy, uważam to za nie panaceum, ponieważ nie zawsze łatwo jest wykonać skomplikowaną funkcję w złożonej arytmetyce, nie warto, jeśli gradient można obliczyć analitycznie, aw przypadku równań różniczkowych jest to dokładnie równanie z równaniami wrażliwości , co robię w razie potrzeby.
źródło