Przejdź do zawartości

Algorytm Levenberga-Marquardta

Z Wikipedii, wolnej encyklopedii

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

Linki zewnętrzne

[edytuj | edytuj kod]