Algorytm Levenberga-Marquardta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm Levenberga-Marquardtaalgorytm optymalizacji nieliniowej. Jest to algorytm iteracyjny, łączący w sobie cechy metody największego spadku i metody Gaussa-Newtona.

Sformułowanie problemu[edytuj]

Mając daną serię danych , gdzie , szukamy dopasowania , gdzie -- wektor parametrów. Zakładamy, że najlepszym dopasowaniem jest to minimalizujące funkcjonał:


Algorytm Levenberga-Marquardta w ogólności znajduje rozwiązanie zadania optymalizacji nieliniowej funkcji dającej się zapisać w postaci:


gdzie i zakładamy, że . Jak łatwo zauważyć, funkcjonał daje się zapisać w taki sposób. Dla uproszczenia, przedstawmy funkcje jako wektor (zwany wektorem rezydualnym). Wtedy . Pochodne funkcji można zapisać przy użyciu Macierzy Jacobiego funkcji , zdefiniowanego jako . W ogólnym przypadku gradient funkcji można zapisać:


a jej Macierz Hessego:


W przypadku, gdy funkcje można aproksymować funkcjami liniowymi w otoczeniu interesującego nas punktu (wtedy jest bliskie zeru), lub gdy jest małe, hesjan funkcji przyjmuje prostszą postać:


a więc hesjan można otrzymać wprost mając dany jakobian wektora rezydualnego , co jest charakterystyczne dla zadania najmniejszych kwadratów.

Opis metody[edytuj]

Najprostszym podejściem do problemu minimalizacji funkcji jest metoda największego spadku, opisana schematem:


która jest, w ogólnym przypadku, wolno zbieżna. Aby poprawić jej zbieżność, można skorzystać z wiedzy o drugiej pochodnej minimalizowanej funkcji w badanym punkcie. Jednym z możliwych podejść jest rozwinięcie gradientu minimalizowanej funkcji w szereg Taylora:


i przyjęcie przybliżenia kwadratowego funkcji w otoczeniu do rozwiązania równania . W ten sposób otrzymujemy metodę Gaussa-Newtona opisaną schematem:


gdzie hesjan funkcji nie musi być znany dokładnie i często wystarczy podane wcześniej przybliżenie. Niestety, szybkość zbieżności tej metody zależy od wyboru punktu początkowego, a konkretnie od liniowości minimalizowanej funkcji w otoczeniu punktu startowego. Kenneth Levenberg zauważył, że opisane metody (największego spadku i Gaussa-Newtona) nawzajem się uzupełniają i zaproponował następującą modyfikację kroku metody:

(*)


wraz z następującym algorytmem:

  1. oblicz wartość na podstawie i równania (*)
  2. oblicz wartość błędu w punkcie
  3. jeśli błąd wzrósł, wróć do wartości , zwiększ wartość -krotnie i wróć do kroku 1 (przybliżenie liniowe minimalizowanej funkcji w otoczeniu okazało się nie dość ścisłe, więc zwiększamy "wpływ" metody największego spadku)
  4. jeśli błąd zmalał, zaakceptuj ten krok i zmniejsz wartość -krotnie (założenie o liniowości minimalizowanej funkcji w otoczeniu okazało się wystarczająco ścisłe, więc zwiększamy "wpływ" metody Gaussa-Newtona)

W typowych zastosowaniach . W przypadku, gdy jest duże, hesjan w zasadzie nie jest wykorzystywany. Donald Marquardt zauważył, że nawet w takiej sytuacji można wykorzystać informację zawartą w drugiej pochodnej minimalizowanej funkcji, poprzez skalowanie każdego komponentu wektora gradientu w zależności od krzywizny w danym kierunku (co pomaga w źle uwarunkowanych zadaniach minimalizacji typu error valley). Po uwzględnieniu poprawki Marquardta otrzymujemy następującą postać kroku metody:


gdzie:


Największą zaletą algorytmu Levenberga-Marquardta jest jego szybka zbieżność, w porównaniu z konkurencyjnymi metodami. Najkosztowniejszą operacją jest natomiast wyznaczenie macierzy odwrotnej, które w praktyce jest przeprowadzane w sposób przybliżony, na przykład przy użyciu metody SVD. Tym niemniej, nawet w najoszczędniejszych przypadkach koszt jednego kroku rośnie niedopuszczalnie wraz ze wzrostem rozmiaru zadania powyżej tysiąca parametrów. Z drugiej dla zadań o umiarkowanej ilości parametrów (rzędu kilkuset), metoda Levenberga-Marquardta jest dużo szybsza od metody największego spadku.

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]