Maksymalizacja nieznanej głośnej funkcji

10

Interesuje mnie maksymalizacja funkcji , gdzie .f(θ)θRp

Problem polega na tym, że nie znam formy analitycznej funkcji ani jej pochodnych. Jedyne, co mogę zrobić, to ocenić funkcję punktowo, wartość i w tym momencie uzyskać oszacowanie . Jeśli chcę, mogę zmniejszyć zmienność tych szacunków, ale muszę zapłacić rosnące koszty obliczeniowe. θf^(θ)

Oto, co próbowałem do tej pory:

  • Stochastyczne strome zejście ze skończonymi różnicami: może działać, ale wymaga dużo strojenia (np. Sekwencji wzmocnienia, współczynnika skalowania) i często jest bardzo niestabilne.

  • Symulowane wyżarzanie: działa i jest niezawodne, ale wymaga wielu ocen funkcji, więc stwierdziłem, że jest dość powolny.

Pytam więc o sugestie / pomysły na temat możliwej alternatywnej metody optymalizacji, która może działać w tych warunkach. Utrzymuję problem tak ogólny, jak to możliwe, aby zachęcić do sugestii z obszarów badań innych niż moje. Muszę dodać, że byłbym bardzo zainteresowany metodą, która pozwoliłaby mi oszacować Hesję przy zbieżności. Jest tak, ponieważ mogę go użyć do oszacowania niepewności parametrów . W przeciwnym razie będę musiał użyć różnic skończonych wokół maksimum, aby uzyskać oszacowanie.θ

Jugurtha
źródło
Jeśli nie możesz powiedzieć nic bardziej szczegółowego na temat szumu związanego z wyjściem funkcji, nie jestem pewien, że coś bardziej zaawansowanego niż symulowane wyżarzanie (będziesz musiał dostrajać to, do pewnego stopnia), będzie pomocne.
Aron Ahmadia,
Niestety niewiele wiem o losowym hałasie związanym z każdą oceną funkcji. Jego rozkład jest nieznany i może być funkcją . Z drugiej strony dźwięki wpływające na kolejne oceny funkcji są niezależne. Oczywiście zakładam, że wariancja hałasu nie jest ogromna, w przeciwnym razie maksymalizacja byłaby niemożliwa. θ
Jugurtha
Z drugiej strony, załóżmy, że wiem coś o rozkładzie szumu, na przykład, że f ( θ * ) ~ N ( f ( θ * ) , Ď ) . Czy ta wiedza by mi pomogła? fa^(θ)N.(fa(θ),σ)
Jugurtha,
Wygląda na to, że stoję skorygowany przez prof. Neumaiera :)
Aron Ahmadia,
Fizycy tutaj użyłem CMA-ES do optycznego kształtowania fazy (optymalizując fazę impulsu laserowego za pomocą pulsatora), co jest dość głośne.
tillsten

Odpowiedzi:

7

Nasz pakiet Matlab SnobFit został stworzony właśnie do tego celu. Nie jest wymagane założenie dotyczące rozkładu hałasu. Co więcej, wartości funkcji mogą być dostarczane przez pliki tekstowe, dzięki czemu można je zastosować do funkcji zaimplementowanych w dowolnym systemie zdolnym do napisania pliku tekstowego. Zobacz
http://www.mat.univie.ac.at/~neum/software/snobfit/

SnobFit został opracowany dla aplikacji, w których funkcja, która ma być zoptymalizowana, nawet nie istniała, a wartości funkcji (miara jakości produkcji) zostały uzyskane przez specjalistyczny, drogi sprzęt tworzący przykładowe produkty i mierzący je ręcznie, co daje około 50 funkcji oceny dziennie.

Arnold Neumaier
źródło
Bardzo dziękuję za odpowiedź. Zacząłem czytać twój artykuł dotyczący pakietu SnobFit i uważam, że jest naprawdę interesujący. Ponadto, czytając wprowadzenie do twojego artykułu, zdałem sobie sprawę, że problem, z którym mam do czynienia (w kontekście statystycznym) jest dość częsty w matematyce przemysłowej. Istnieje ogromna literatura, o której byłem całkowicie nieświadomy. W rzeczywistości podejście, nad którym pracowałem, jest nieco podobne do kwadratowego przybliżenia Powella (2002).
Jugurtha,
Czy snobfit działa dobrze przy 128 stopniach swobody? Żeby wiedzieć, że warto wypróbować moją sprawę.
tillsten
@tillsten: Żadne metody głośnego problemu nie działają dobrze przy 128 dof, chyba że możesz wydać ogromną liczbę wartości funkcji. Możesz jednak wypróbować nasz VXQR1, który jest przeznaczony dla nie hałaśliwych problemów, ale czasami dobrze radzi sobie z hałaśliwymi problemami.
Arnold Neumaier,
Limit dla Snobfit wynosi około 20 zmiennych. jeśli masz więcej, musisz wybrać grupy 20 zmiennych według zdrowego rozsądku, które z kolei częściowo optymalizujesz. Lub możesz pozwolić przesuwać niektóre zmienne jednocześnie, aby zmniejszyć wymiar.
Arnold Neumaier,
7

Istnieje kilka technik optymalizacji bayesowskiej , które można wypróbować. Najłatwiejsze są oparte na procesie Gaussa:

  • Harold J. Kushner. Nowa metoda lokalizowania maksimum dowolnej krzywej piku w obecności szumu. Journal of Basic Engineering, strony 86: 97–106, marzec 1964 r.
  • J. Mockus. Bayesowskie podejście do globalnej optymalizacji. Wykład notatki w naukach o kontroli i informacji, 38: 473–481, 1982.
  • Niranjan Srinivas, Andreas Krause, Sham Kakade i Matthias Seeger. Optymalizacja procesu gaussowskiego w środowisku bandyty: Bez żalu i eksperymentalny projekt. W Proc. Międzynarodowa konferencja na temat uczenia maszynowego (ICML), 2010.
  • Andreas Krause, Ajit Singh i Carlos Guestrin. Prawie optymalne rozmieszczenie czujników w procesach gaussowskich: teoria, wydajne algorytmy i badania empiryczne. J. Mach. Uczyć się. Res., 9: 235–284, czerwiec 2008 r.

Działają, tworząc tylne względem wiarygodnych funkcje, dają dotychczasowe obserwacje i sugerują kolejny punkt, aby szybko nauczyć się funkcji i znaleźć globalne maksima (patrz mój post na blogu ).

Kolejną zaletą jest to, że można oszacować Hesjan na maksima. Musisz jednak określić model hałasu.

Memming
źródło
4

Algorytm SPSA Jamesa Spalla (skrót od Stochastic Perturbation Simulation Annealing, jeśli dobrze pamiętam) został zaprojektowany dla dokładnie tego rodzaju problemu. Ma kilka artykułów, w których używa go do rozwiązywania problemów takich jak ten, który opisujesz.

Wolfgang Bangerth
źródło
Próbowałem podejścia Spall'a opartego na stochastycznej wersji najbardziej stromego zejścia i Raphsona Newtona. Próbowałem symulować wyżarzanie, ale nie wersja sugerowana przez Spall, powinienem spróbować. Nie jestem zbyt entuzjastycznie nastawiony do symulowanego wyżarzania, ponieważ nie mogę uzyskać oszacowania Hesji przy zbieżności (podczas gdy na przykład dzięki stochastycznemu Raphsonowi Newtonowi mogę uzyskać przybliżenie do Hesji „za darmo”).
Jugurtha