Czy istnieje jakakolwiek technika polegająca na wyszukiwaniu absolutnego minimum (maksimum) funkcji w przestrzeni wielowymiarowej?

11

Znam algorytm spadku gradientu, który może znaleźć lokalne minimum (maksimum) danej funkcji.

Czy jest jakaś modyfikacja spadku gradientu, która pozwala znaleźć absolutne minimum (maksimum), gdzie funkcja ma kilka ekstremów lokalnych?

Czy istnieją jakieś ogólne techniki, jak ulepszyć algorytm, który może znaleźć ekstremum lokalne, w celu znalezienia ekstremum ekstremalnego?

ds.algorithms approximation-algorithms machine-learning rzymski
źródło

Możesz sprawdzić Cross Validated lub AI Pytania i odpowiedzi połączone z FAQ .

Kaveh,

Myślę, że to jedna z wad opadania gradientu - może utknąć w ekstremalnych warunkach lokalnych. Inne techniki, takie jak symulowane wyżarzanie, mogą być mniej podatne na to, ale nadal nie mogę zagwarantować, z tego co rozumiem.

Joe

1

Nie jestem pewien, co ma z tym wspólnego „wielowymiarowa przestrzeń”. nawet funkcja R może mieć wiele lokalnych ekstremów, z którymi wyszukiwanie gradientowe będzie miało problemy.

Suresh Venkat

Jestem całkiem pewien, że istnieje twierdzenie wzdłuż linii, że jeśli funkcja jest ciągła i próbkowana w wystarczającej liczbie punktów, możesz zagwarantować, że zejście gradientu znajdzie globalne minimum, zaczynając od pewnego punktu. tj. coś podobnego do algorytmu Powella. literatura jest tak rozległa, że takie twierdzenie prawdopodobnie zostało gdzieś opublikowane, ale o nim nie słyszałem. dowodzi również, że lokalna optymalizacja może zbliżyć się do globalnych wartości optymalnych przy wystarczającym próbkowaniu, gdy próbkowanie rośnie.

vzn

nieco spokrewnione, patrz również tutaj komentarze , które mocno argumentują, że globalne NN lub metody numeryczne / typy heurystyczne nie są „algorytmami aproksymacyjnymi”

wer

17

Zakładam, że mówisz o nieograniczonej minimalizacji. Twoje pytanie powinno określać, czy rozważasz konkretną strukturę problemu. W przeciwnym razie odpowiedź brzmi „nie”.

Najpierw powinienem rozwiać mit. Klasyczna metoda opadania gradientu (zwana również metodą najbardziej stromego spadku ) nie gwarantuje nawet znalezienia lokalnego minimalizatora. Zatrzymuje się, gdy znajdzie punkt krytyczny pierwszego rzędu, tj. Punkt, w którym gradient zanika. W zależności od konkretnej funkcji, która jest minimalizowana i punktu początkowego, możesz bardzo dobrze skończyć w punkcie siodłowym lub nawet w globalnym maksymalizatorze!

Rozważmy na przykład i punkt początkowy . Najbardziej stromy kierunek zniżania to . Jeden krok metody z dokładnym wyszukiwaniem linii pozostawia cię w gdzie zanika gradient. Niestety, jest to punkt siodłowy. Można to zrealizować, badając warunki optymalności drugiego rzędu. Ale teraz wyobraź sobie, że funkcja to . Tutaj jest nadal punktem siodłowym, ale liczbowo warunki drugiego rzędu mogą ci nie powiedzieć. Ogólnie rzecz biorąc, powiedzmy, że ustalono, że Heski ma wartość własną równą $f(x,y) = x^2 - y^2$ $(x_0,y_0) := (1,0)$ $-\nabla f(1,0) = (-2,0)$ $(0,0)$ $f(x,y) = x^2 - 10^{-16} y^2$ $(0,0)$ $\nabla^2 f(x^*,y^*)$ $-10^{-16}$ . Jak to czytasz? Czy to ujemna krzywizna czy błąd numeryczny? Co powiesz na ? $+10^{-16}$

Rozważmy teraz funkcję taką jak

fa (x) = {\begin{cases} 1 & Jeśli x \leq 0 \\ sałata (x) & Jeśli 0 < x < π \\ - 1 & Jeśli x \geq π . \end{cases}

$f(x) = \begin{cases} 1 & \text{if } x \leq 0 \\ \cos(x) & \text{if } 0 < x < \pi \\ -1 & \text{if } x \geq \pi. \end{cases}$

$x_0 = -2$

Obecnie praktycznie wszystkie metody optymalizacji oparte na gradiencie cierpią z tego powodu. Twoje pytanie naprawdę dotyczy globalnej optymalizacji . Ponownie odpowiedź brzmi nie, nie ma ogólnych przepisów na modyfikację metody, aby zagwarantować zidentyfikowanie globalnego minimalizatora. Po prostu zadaj sobie pytanie: jeśli algorytm zwraca wartość i mówi, że jest globalnym minimalizatorem, w jaki sposób sprawdziłbyś, czy to prawda?

Istnieją globalne metody optymalizacji. Niektórzy wprowadzają randomizację. Niektórzy stosują strategie wielokrotnego startu. Niektórzy wykorzystują strukturę problemu, ale są to przypadki szczególne. Wybierz książkę o globalnej optymalizacji. Spodoba ci się.

Dominique
źródło

@Roman: Bardzo mile widziane.

Dominique

3

Prawdopodobnie nie ma jednej uniwersalnej odpowiedzi na twoje pytanie. Ale możesz przyjrzeć się symulowanym algorytmom wyżarzania lub innym podejściom, które opierają się na metodach Markowa w łańcuchu Monte Carlo (MCMC). Można je również łączyć z lokalnymi metodami, takimi jak opadanie gradientu.

mrig
źródło

1

istnieje wiele odniesień do „globalnej optymalizacji sieci neuronowych”. techniki są podobne do symulowanego wyżarzania [patrz inna odpowiedź]. podstawową ideą jest ponowne uruchomienie opadania gradientu sieci, rozpoczynając od wielu różnych punktów początkowych masy, losowo lub systematycznie próbkowanych. każdy wynik spadku gradientu jest wtedy jak „próbka”. im więcej próbek zostanie pobranych, tym większe prawdopodobieństwo, że jedna z próbek jest globalnym optymalnym, szczególnie jeśli funkcja celu jest „dobrze zachowana” w sensie ciągłości, różniczkowania itp.

referencje online

[1] Globalna optymalizacja wag sieci neuronowych autorstwa Hamm et al

[2] Globalne podejście optymalizacyjne do szkolenia sieci neuronowej Voglis / Lagaris

[3] Kalibracja sztucznych sieci neuronowych przez Global Optimization Pinter

[4] Globalna optymalizacja sieci neuronowych za pomocą deterministycznego podejścia hybrydowego Beliakov

[5] Globalna optymalizacja do szkolenia w sieci neuronowej Shang / Wah

vzn
źródło

1

Zasadniczo trudno jest pod względem obliczeniowym zoptymalizować wielowymiarowe funkcje niewypukłe. Twardość występuje w różnych smakach (kryptograficzna, NP-twarda). Jednym ze sposobów na to jest to, że modele mieszanki (takie jak mieszanka Guassianów lub HMM) są trudne do nauczenia, ale byłoby to łatwe (*), gdyby można było skutecznie zmaksymalizować prawdopodobieństwo. Aby uzyskać wyniki dotyczące trudności uczenia się HMM, patrz http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http: // www.math.ru.nl/~terwijn/publications/icgiFinal.pdf

(*) modulo zwykłe warunki niedegeneracji i identyfikowalności

Aryeh
źródło

0

muszę się nie zgodzić z Dominique. w połowie lat osiemdziesiątych Hajek wykazał, że wyżarzanie nie wypukłego problemu w pewnych ściśle określonych warunkach gwarantuje osiągnięcie globalnego minimum: http://dx.doi.org/10.1287/moor.13.2.311

Aaron Brick
źródło

2

W świetle wspomnianych powyżej wyników twardości warunki te muszą być rzeczywiście dość surowe!

Aryeh

Czy istnieje jakakolwiek technika polegająca na wyszukiwaniu absolutnego minimum (maksimum) funkcji w przestrzeni wielowymiarowej?

Odpowiedzi: