Optymalizacja, gdy funkcja kosztu wolno ocenia

59

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?

Jared Becksfort
źródło
5
Czy słyszałeś o stochastycznym spadku? W przypadku głębokich sieci neuronowych stosowanych do dużych zestawów treningowych masz podobny problem (ale możesz ewaluować gradient gradientu analitycznie), a standardowym rozwiązaniem jest wykonanie spadku gradientu na podstawie tylko jednej próbki (stochastycznej) względem całej kohorty (partia)
seanv507
3
Znam tylko tę okolicę, więc jest to komentarz, a nie odpowiedź. Ale to, o czym dyskutujesz, brzmi bardzo podobnie do tematu Kwantyfikacji niepewności, z którym często spotykają się inżynierowie, gdzie ocena pojedynczej funkcji docelowej zajęła tygodnie (przynajmniej w przypadku problemów, z jakimi borykają się moi współpracownicy inżynierscy). Moje bardzo ograniczone rozumienie tego, jak to się robi, polega na tym, że dokonuję przybliżenia zastępczego, które jest o wiele łatwiejsze do oszacowania na podstawie wcześniejszych ocen i prostszych modeli inżynierskich, a następnie używam tych modeli zastępczych do wyboru następnej oceny ...
Cliff AB
2
... droższej funkcji celu. Nienawidzę tego mówić, ale w tej chwili nie wiem na ten temat; Powiedziano mi o tym tylko krótko podczas omawiania tematów badawczych ze wspomnianymi inżynierami. Co ciekawe, wydaje się to bardzo trudnym obszarem badawczym: uważam, że dobre modele wymagają zarówno dobrego zrozumienia fizyki, jak i statystyki.
Cliff AB
1
@ seanv507 Tak, dziękuję, ale uniknąłem tego z podobnego powodu. Wykonanie jednej próbki zajmuje około 30 sekund do minuty. Jeśli mam 15 parametrów, patrzę na prawie 8 minut na obliczenie gradientu, nawet jeśli używam tylko jednej próbki. Jeśli przestrzeń jest duża, może to potrwać bardzo długo. Popraw mnie, jeśli masz na myśli inne pomysły.
Jared Becksfort
5
„wydaje mi się, że jest to niezwykła sytuacja. Każda ocena mojej funkcji kosztów jest kosztowna.”. Zasadniczo nie jest to wcale niezwykła sytuacja. Pokazuje się wszędzie, na przykład gdy kiedykolwiek twoja funkcja kosztów pochodzi z uruchomienia symulacji (np. W tym dokumencie: white.ucc.asn.au/publications/White2015PsoTransistorSizing.pdf symulujemy obwód w SPICE trwający 10 sekund ). Mówiąc bardziej ogólnie, w nauce eksperymentalnej ewaluacje mogą trwać wieki. Jeden z moich projektów Masters, mój przyjaciel, zasadniczo optymalizuje 5 parametrów, aby znaleźć najlepszy sposób na wstawienie DNA. Każda ocena trwa 24 godziny.
Lyndon White

Odpowiedzi:

59

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,95p=0,95100×(1-q)=5nqn=0,95n1-0,95n. Łącząc to wszystko, mamy

1-qnpnlog(1-p)log(q)

n59

n=60n=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 ”.

Przywróć Monikę
źródło
1
To wydaje się być nowoczesnym wariantem metod powierzchni reakcji!
kjetil b halvorsen
1
W rzeczywistości losowe wyszukiwanie może działać wyjątkowo dobrze: argmin.net/2016/06/20/hypertuning
Tim
1
@Tim Tak, masz rację. Nie chciałem „decydować” o tym, która kwestia jest lepsza w tym poście, ponieważ na BO istnieją zasadniczo niekończące się permutacje, z których każda twierdzi, że jest „najlepszym” optymalizatorem czarnej skrzynki - uniemożliwiając ostateczne określenie. Zgadzam się, że losowe wyszukiwanie może działać całkiem dobrze, ale tak naprawdę poleciłbym LIPO zamiast PRS. LIPO jest poprawne i zdecydowanie przewyższa PRS (średnio) we wszystkich moich eksperymentach. LIPO ma również minimalny koszt oszacowania: jeśli możesz zminimalizować QP, możesz użyć LIPO, a LIPO ma zero hiperparametrów (w przeciwieństwie do BO).
Przywróć Monikę
Cieszę się, że ponownie sprawdziłem to pytanie. LIPO wydaje się świetne.
Jared Becksfort
LIPO jest świetne. Kiedy mam chwilę, poszerzę swoją odpowiedź, aby lepiej rozliczać LIPO.
Przywróć Monikę
40

fa(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).

Lacerbi
źródło
4
+1 To świetna odpowiedź. W szczególności dokumenty te są doskonałym dodatkiem do tego wątku; faktycznie nie wiedziałem, że ogólna metoda, którą opisałem, nazywa się Optymalizacja Bayesowska. Obawiam się jednak, że z czasem linki mogą się zepsuć. Czy miałbyś coś przeciwko dodaniu pełniejszych informacji o cytatach, aby przyszli użytkownicy mieli dostęp do tych dokumentów?
Przywróć Monikę
Bayesowskie dokumenty optymalizacyjne są dość pomocne. Dziękuje za odpowiadanie.
Jared Becksfort
1
@ user777: Dobra uwaga. Na końcu dodano wyraźną listę referencyjną, która powinna wystarczyć do odzyskania dokumentów.
lacerbi
6

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.

Mehrdad
źródło
2
Podaj pełne informacje o cytowanych dokumentach i innych zasobach. Chcemy zbudować trwałe repozytorium informacji, a linki z czasem się psują.
Przywróć Monikę
Björkman, M. & Holmström, K. „Globalna optymalizacja kosztownych funkcji niekonwypukłych z wykorzystaniem funkcji radialnych”. Optimization and Engineering (2000) 1: 373. doi: 10.1023 / A: 1011584207202
jkdev
4

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.
Zhan Dawei
źródło
3

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.

Patrick
źródło
3

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 .

Paweł
źródło
Zakładam, że jesteś pierwszym autorem na papierze - prawdopodobnie powinieneś o tym wspomnieć. W artykule brakuje porównania z najnowocześniejszymi metodami, takimi jak optymalizacja bayesowska lub inne metody zastępcze (w rzeczywistości nie zapewnia ono żadnych punktów odniesienia). Czy możesz powiedzieć coś więcej?
lacerbi
Nie twierdzę, że zastosowany tam model jest lepszy. Po prostu mówię, że ludzie są zbyt zaniepokojeni jakością modelu i czasami zapominają o równoległości, co może być dużym problemem, gdy w grę wchodzi wiele rdzeni.
Paul
Podaj pełne informacje o cytowanych dokumentach i innych zasobach. Chcemy zbudować trwałe repozytorium informacji, a linki z czasem się psują.
Przywróć Monikę
2
Nie jestem pewien, jak bardzo terminologia różni się w zależności od społeczności, ale często tutaj powierzchnia odpowiedzi jest używana jako synonim „wielomianowego modelu zastępczego” (zazwyczaj kwadratowego). Dlatego myślę o modelowaniu zastępczym jako o nadzorze modelowania powierzchni odpowiedzi. (Może to być niepoprawne.)
GeoMatt22,
0

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.

ZAx-b2)ZAZAb

Haitao Du
źródło