Spadek gradientu i wiele innych metod jest przydatnych do znajdowania lokalnych minimów w funkcjach kosztów. Mogą być wydajne, gdy funkcja kosztu może być szybko oszacowana w każdym punkcie, zarówno liczbowo, jak i analitycznie.

Mam coś, co wydaje mi się niezwykłą sytuacją. Każda ocena mojej funkcji kosztów jest kosztowna. Usiłuję znaleźć zestaw parametrów, które minimalizują powierzchnię 3D względem powierzchni prawdy gruntu. Ilekroć zmieniam parametr, muszę uruchomić algorytm dla całej kohorty próbki, aby zmierzyć jego efekt. Aby obliczyć gradient, muszę zmienić wszystkie 15 parametrów niezależnie, co oznacza, że ​​muszę zregenerować wszystkie powierzchnie i porównać z kohortą próbki zbyt wiele razy na gradient, a zdecydowanie zbyt wiele razy w trakcie optymalizacji.

Opracowałem metodę obejścia tego problemu i obecnie go oceniam, ale jestem zaskoczony, że w literaturze nie znalazłem wiele na temat kosztownych ocen funkcji kosztów. To sprawia, że ​​zastanawiam się, czy sprawiam, że problem jest trudniejszy niż jest, i czy może być już lepszy sposób.

Więc moje pytania są w zasadzie następujące: czy ktoś zna metody optymalizacji funkcji kosztowych, wypukłych czy nie, gdy ocena jest powolna? Czy też robię coś głupiego, uruchamiając ponownie algorytm i porównując tyle razy z próbką z kohorty?

TL; DR

Polecam korzystanie z LIPO. Jest to możliwe do udowodnienia, poprawne i lepsze niż zwykłe wyszukiwanie losowe (PRS). Jest także niezwykle prosty do wdrożenia i nie ma hiperparametrów. Nie przeprowadziłem analizy porównującej LIPO z BO, ale oczekuję, że prostota i wydajność LIPO implikuje, że przewyższy BO.

(Zobacz także: Jakie są niektóre z wad bayesowskiej optymalizacji hiperparametrów? )

Optymalizacja bayesowska

Metody typu Bayesian Optimization budują modele zastępcze procesu Gaussa do eksploracji przestrzeni parametrów. Główną ideą jest to, że krotki parametrów, które są bliżej siebie, będą miały podobne wartości funkcji, więc założenie struktury współwariancji między punktami pozwala algorytmowi na wykształcone domysły na temat tego, która krotka z najlepszym parametrem jest najbardziej warta wypróbowania w następnej kolejności. Ta strategia pomaga zmniejszyć liczbę ocen funkcji; w rzeczywistości motywacja metod BO polega na utrzymywaniu jak najniższej liczby ocen funkcji, przy jednoczesnym „korzystaniu z całego bawołu” w celu odgadnięcia, który punkt należy przetestować. Istnieją różne liczby zasług (oczekiwana poprawa, oczekiwana poprawa kwantylowa, prawdopodobieństwo poprawy ...), które są używane do porównywania punktów do odwiedzenia w następnej kolejności.

Porównaj to z czymś w rodzaju wyszukiwania siatki, która nigdy nie użyje żadnych informacji z poprzednich ocen funkcji, aby poinformować, gdzie iść dalej.

Nawiasem mówiąc, jest to również potężna technika optymalizacji globalnej i jako taka nie przyjmuje żadnych założeń dotyczących wypukłości powierzchni. Dodatkowo, jeśli funkcja jest stochastyczna (powiedzmy, że oceny zawierają pewne nieodłączne szumy losowe), można to bezpośrednio uwzględnić w modelu GP.

Z drugiej strony będziesz musiał dopasować co najmniej jednego lekarza ogólnego na każdej iteracji (lub kilka, wybierając „najlepsze” lub uśredniając alternatywy lub metody w pełni bayesowskie). Następnie model służy do tworzenia (prawdopodobnie tysięcy) prognoz, zwykle w postaci lokalnej optymalizacji wieloczęściowej, z obserwacją, że ocena funkcji prognozowania GP jest znacznie tańsza niż funkcja podlegająca optymalizacji. Ale nawet z tym narzutem obliczeniowym zdarza się, że nawet funkcje niewypukłe można zoptymalizować za pomocą stosunkowo niewielkiej liczby wywołań funkcji.

Często cytowanym artykułem na ten temat jest Jones i in. , „Skuteczna globalna optymalizacja drogich funkcji czarnej skrzynki”. Istnieje jednak wiele odmian tego pomysłu.

Wyszukiwanie losowe

$p$ $q$

$q = 0.95$$p=0.95$$100\times (1-q)=5$$n$$q^n = 0.95^n$$1 - 0.95^n$. Łącząc to wszystko, mamy

$n \ge 59$

$n=60$$n=60$

Ponieważ masz probabilistyczną gwarancję tego, jak dobre są wyniki, może to być przekonujące narzędzie, aby przekonać szefa, że ​​nie trzeba przeprowadzać więcej eksperymentów.

LIPO i jego warianty

To ekscytujące przybycie, które, jeśli nie jest nowe , z pewnością jest dla mnie nowe. Przebiega przez naprzemienne umieszczanie świadomych granic funkcji i próbkowanie od najlepszej granicy oraz stosowanie przybliżeń kwadratowych. Nadal pracuję nad wszystkimi szczegółami, ale myślę, że jest to bardzo obiecujące. To jest miły artykuł na blogu , a artykuł napisali Cédric Malherbe i Nicolas Vayatis „ Globalna optymalizacja funkcji Lipschitza ”.

$f(x)$$x$

Powiedziałbym, że obecny złoty standard oceny (bardzo) kosztownej funkcji czarnej skrzynki to (globalna) optymalizacja bayesowska (BO). Sycorax już opisał niektóre funkcje BO, więc dodam tylko informacje, które mogą być przydatne.

Na początek warto przeczytać ten dokument poglądowy 1 . Istnieje również nowsza wersja [2].

W ostatnich latach optymalizacja Bayesowska stale rośnie jako dziedzina, dzięki serii dedykowanych warsztatów (np. BayesOpt i sprawdź te filmy z warsztatów Sheffield na BO), ponieważ ma ona bardzo praktyczne zastosowania w uczeniu maszynowym, takim jak optymalizacja hiperparametrów algorytmów ML - patrz np. ten artykuł [3] i powiązany zestaw narzędzi, SpearMint . Istnieje wiele innych pakietów w różnych językach, które implementują różne rodzaje algorytmów optymalizacji Bayesa.

Jak wspomniałem, podstawowym wymaganiem jest to, że ocena każdej funkcji jest bardzo kosztowna, tak że obliczenia związane z BO dodają znikomy narzut. Aby dać boisko, BO może być zdecydowanie pomocne, jeśli twoja funkcja ocenia w czasie rzędu minut lub więcej. Możesz go również zastosować do szybszych obliczeń (np. Dziesiątki sekund), ale w zależności od używanego algorytmu konieczne może być przyjęcie różnych przybliżeń. Jeśli twoja funkcja ocenia się w skali czasu w sekundach , myślę, że przekraczasz granice obecnych badań i być może inne metody mogą stać się bardziej przydatne. Muszę też powiedzieć, że BO rzadko jest naprawdę czarną skrzynką i często trzeba modyfikować algorytmy, czasem dużo , aby działało z pełnym potencjałem z konkretnym problemem w świecie rzeczywistym.

BO na bok, w celu przeglądu ogólnych metod optymalizacji bez pochodnych można spojrzeć na ten przegląd [4] i sprawdzić algorytmy, które mają dobre właściwości szybkiej konwergencji. Na przykład wyszukiwanie współrzędnych wielopoziomowe (MCS) zwykle bardzo szybko zbliża się do sąsiedztwa minimum (oczywiście nie zawsze globalnego minimum). MCS jest uważany za globalną optymalizację, ale można go ustawić lokalnie, ustawiając odpowiednie ograniczenia powiązane.

Wreszcie, jesteś zainteresowany BO dla funkcji docelowych, które są zarówno kosztowne, jak i głośne , zobacz moją odpowiedź na to pytanie .

Bibliografia:

1 Brochu i in., „Samouczek na temat bayesowskiej optymalizacji funkcji kosztownych, z zastosowaniem do aktywnego modelowania użytkowników i uczenia się hierarchicznego wzmacniania” (2010).

[2] Shahriari i in., „Wyjmowanie człowieka z pętli: przegląd optymalizacji bayesowskiej” (2015).

[3] Snoek i in., „Practical Bayesian Optimization of Machine Learning Algorytmy”, NIPS (2012).

[4] Rios i Sahinidis, „Optymalizacja bez instrumentów pochodnych: przegląd algorytmów i porównanie implementacji oprogramowania”, Journal of Global Optimization (2013).

Sam nie znam algorytmów, ale uważam, że rodzaj algorytmu optymalizacji, którego szukasz, to optymalizacja bez pochodnych , która jest używana, gdy cel jest kosztowny lub hałaśliwy .

Na przykład spójrz na ten artykuł (Björkman, M. & Holmström, K. „Globalna optymalizacja kosztownych funkcji niekonwypukłych za pomocą funkcji radialnych.” Optymalizacja i inżynieria (2000) 1: 373. doi: 10.1023 / A: 1011584207202) którego streszczenie wydaje się wskazywać, że właśnie tego chcesz:

Artykuł rozważa globalną optymalizację kosztownych funkcji celu, tj. Problem znalezienia globalnego minimum, gdy istnieje kilka lokalnych minimów, a każda wartość funkcji wymaga znacznego czasu procesora. Takie problemy często pojawiają się w aplikacjach przemysłowych i finansowych, w których wartość funkcji może być wynikiem czasochłonnej symulacji komputerowej lub optymalizacji. Pochodne są najczęściej trudne do uzyskania, a przedstawione algorytmy nie wykorzystują takich informacji.

Nie jesteś sam.

Drogie do oceny systemy są bardzo powszechne w inżynierii, takie jak modele metodą elementów skończonych (FEM) i modele obliczeniowej dynamiki płynów (CFD). Optymalizacja tych kosztownie obliczeniowych modeli jest bardzo potrzebna i stanowi wyzwanie, ponieważ algorytmy ewolucyjne często wymagają dziesiątek tysięcy ocen problemu, co nie jest rozwiązaniem dla kosztownych problemów. Na szczęście istnieje wiele metod (algorytmów) dostępnych do rozwiązania tego problemu. O ile mi wiadomo, większość z nich opiera się na modelach zastępczych (metamodelach). Niektóre są wymienione poniżej.

• Efficient Global Optimization (EGO) [1]. Algorytm EGO został wspomniany powyżej i może być najbardziej znanym algorytmem optymalizacji opartym na surogacie. Opiera się na modelu Kriginga i kryterium wypełnienia zwanym oczekiwaną funkcją poprawy (EI). Pakiety R, w tym algorytm EGO, to DiceOptim i DiceKriging.
• Metoda próbkowania modowego (MPS) [2]. Algorytm MPS jest zbudowany na modelu RBF, a do zbierania punktów kandydujących stosuje się przejmującą strategię próbkowania. Kod MATLAB jest opublikowany przez autorów pod adresem http://www.sfu.ca/~gwa5/software.html . Algorytm MPS może wymagać więcej ocen, aby uzyskać optymalne, ale może poradzić sobie z bardziej skomplikowanymi problemami niż algorytm EGO z mojego osobistego doświadczenia.
• Zestaw modeli zastępczych Juliane Müller [3]. Użyła wielu surogatów, aby poprawić zdolność wyszukiwania. Przybornik MATLAB MATSuMoTo jest dostępny pod adresem https://github.com/Piiloblondie/MATSuMoTo .

Podsumowując, te oparte na zastępczych algorytmach optymalizacyjnych próbują znaleźć globalne optimum problemu przy użyciu jak najmniejszej liczby ocen. Osiąga się to poprzez pełne wykorzystanie informacji dostarczonych przez surogat (surogaty). Opinie na temat optymalizacji problemów obliczeniowych są w [4-6].

Odniesienie:

1. DR Jones, M. Schonlau i WJ Welch, „Skuteczna globalna optymalizacja drogich funkcji czarnej skrzynki”, Journal of Global Optimization, t. 13, s. 455–492, 1998.
2. L. Wang, S. Shan i GG Wang, „Metoda próbkowania w celu optymalizacji globalnej w zakresie drogich funkcji czarnej skrzynki”, „Engineering Optimization, vol. 36, ss. 419–438, 2004.
3. J. Müller, „Algorytmy modelu zastępczego dla kosztownie obliczeniowych problemów globalnej optymalizacji czarnej skrzynki”, Tampere University of Technology, 2012.
4. GG Wang i S. Shan, „Przegląd technik metamodelowania wspierających optymalizację projektowania inżynierskiego”, Journal of Mechanical Design, vol. 129, s. 370–380, 2007.
5. AI Forrester i AJ Keane, „Ostatnie postępy w optymalizacji opartej na surogatach”, Progress in Aerospace Sciences, vol. 45, s. 50–79, 2009.
6. FAC Viana, TW Simpson, V. Balabanov i V. Toropov, „Metamodelowanie w multidyscyplinarnej optymalizacji projektowania: jak daleko się naprawdę przydaliśmy?”, AIAA Journal, vol. 52, s. 670–690, 2014/04/01 2014.

Dwie proste strategie, które z powodzeniem stosowałem w przeszłości:

1. Jeśli to możliwe, spróbuj znaleźć prostszą funkcję zastępczą przybliżającą pełną ocenę funkcji kosztu - typowy model analityczny zastępujący symulację. Zoptymalizuj tę prostszą funkcję. Następnie sprawdź poprawność i dostosuj powstałe rozwiązanie za pomocą funkcji dokładnego kosztu.
2. Jeśli to możliwe, spróbuj znaleźć sposób na oszacowanie dokładnej funkcji „kosztu delta” - dokładnej, a nie przybliżonej z wykorzystaniem gradientu. To znaczy, od początkowego 15-wymiarowego punktu, dla którego oszacowano pełny koszt, znajdź sposób, aby dowiedzieć się, jak zmieniłby się koszt, wprowadzając niewielką zmianę w jednym (lub kilku) z 15 składników bieżącego punktu. Będziesz musiał wykorzystać właściwości lokalizacyjne małej perturbacji, jeśli takie występują w twoim konkretnym przypadku, i prawdopodobnie będziesz musiał zdefiniować, buforować i zaktualizować wewnętrzną zmienną stanu po drodze.

Te strategie są bardzo specyficzne dla konkretnego przypadku, nie wiem, czy mogą mieć zastosowanie w twoim przypadku, czy nie, przepraszam, jeśli nie są. Oba mogą mieć zastosowanie (tak jak w moich przypadkach użycia): zastosuj strategię „delta-cost” do prostszego modelu analitycznego - wydajność może poprawić się o kilka rzędów wielkości.

Inną strategią byłoby zastosowanie metody drugiego rzędu, która zazwyczaj zmniejsza liczbę iteracji (ale każda iteracja jest bardziej złożona) - np. Algorytm Levenberga-Marquardta . Ale biorąc pod uwagę, że nie masz możliwości bezpośredniej i efektywnej oceny gradientu, prawdopodobnie nie jest to opłacalna opcja w tym przypadku.

Jak wspomnieli inni, model zastępczy (zwany również powierzchnią odpowiedzi) jest potężnym podejściem. Moim zdaniem, jedną z kluczowych rzeczy, o których ludzie zapominają, jest to, że możesz wykonywać kilka ocen funkcji równolegle , jeśli używasz procesorów wielordzeniowych.

Sugerowałbym przyjrzenie się temu kodowi , używa on prostego modelu odpowiedzi, ale skaluje się na procesorach wielordzeniowych, co daje przyspieszenie równe ilości użytych rdzeni. Matematyka metody jest opisana w tym artykule .

Istnieje wiele sztuczek stosowanych w stochastycznym spadku gradientu, które można również zastosować do oceny funkcji celu. Ogólnym pomysłem jest próba przybliżenia funkcji celu za pomocą podzbioru danych .

Moje odpowiedzi w tych dwóch postach omawiają, dlaczego działa gradient stochastyczny: intuicja za nim polega na przybliżeniu gradientu za pomocą podzbioru danych.

Jak stochastyczne obniżanie gradientu może zaoszczędzić czas w porównaniu ze standardowym spadkiem gradientu?

Jak uruchomić regresję liniową w sposób równoległy / rozproszony dla ustawienia dużych zbiorów danych?

Ta sama sztuczka dotyczy funkcji celu.

$\|Ax-b\|^2$$A$$A$$b$