Jestem programistą, który chce się dowiedzieć, jak działa algorytm krzywej Levenberga-Marquardta, aby sam mógł go wdrożyć. Czy istnieje dobry tutorial, który może wyjaśnić, jak to działa w szczegółach, kiedy czytelnik jest programistą, a nie matematykiem.Jak działa algorytm Levenberga-Marquardta, ale w zrozumiały sposób?
Moim celem jest wdrożenie tego algorytmu w opencl, dzięki czemu mogę uruchomić sprzęt przyspieszony.
Tak, artykuł wiki jest dobry i zawiera linki do rozdziału "Przepisy liczbowe w C". http://www.fizyka.umk.pl/nrbook/c15-5.pdf Aby uzyskać coś praktycznego z równoległej wersji algorytmu, możesz spróbować wykonać go z rozwiniętymi pętlami równolegle używając unikalnego losowego uruchamiania punkt dla każdego obliczenia równoległego. Następnie na końcu weź minimum wszystkich odpowiedzi. –
Wypróbuj Numerical Recipes (Levenberg-Marquardt znajduje się w sekcji 15.5). Jest on dostępny online i uważam, że wyjaśniają algorytmy w sposób szczegółowy (mają kompletny kod źródłowy, o wiele bardziej szczegółowy ...), a jednak są dostępne.
@titus: Zaktualizowałem link –
Minimalizacja funkcji jest jak próbuje znaleźć najniższy punkt na powierzchnia. Pomyśl o sobie chodząc po pagórkowatej powierzchni i próbując dotrzeć do najniższego punktu. Odnajdziesz kierunek, który zjeżdża z górki i idziesz, dopóki nie zjedziesz już w dół. Wtedy wybrałbyś nowy kierunek, który idzie w dół i idzie w tym kierunku, dopóki nie zejdzie już w dół, i tak dalej. Ostatecznie (miejmy nadzieję) dotrzesz do punktu, w którym żaden kierunek nie zejdzie w dół. Będziesz wtedy w (lokalnym) minimum.
Algorytm LM i wiele innych algorytmów minimalizacji korzysta z tego schematu.
Załóżmy, że minimalizowana funkcja to F, a my znajdujemy się w punkcie x (n) w naszej iteracji. Chcemy znaleźć następne iteracyjne x (n + 1) takie, że F (x (n + 1)) < F (x (n)), tj. Wartość funkcji jest mniejsza. Aby wybrać x (n + 1), potrzebujemy dwóch rzeczy, kierunku od x (n) i wielkości kroku (jak daleko w tym kierunku). Algorytm LM określa następujące wartości -
Najpierw należy obliczyć aproksymację liniową do F w punkcie x (n). Łatwo jest ustalić kierunek zjazdu funkcji liniowej, więc wykorzystujemy funkcję przybliżania liniowego do wyznaczania kierunku zjazdu. Następnie musimy wiedzieć, jak daleko możemy się posunąć w tym wybranym kierunku. Jeśli nasza aproksymująca funkcja liniowa jest dobrym przybliżeniem F dla dużego obszaru wokół x (n), wówczas możemy wykonać dość duży krok. Jeśli jest to dobre przybliżenie tylko bardzo zbliżone do x (n), możemy zrobić tylko bardzo mały krok.
To właśnie robi LM - oblicza liniową aproksymację do F w punkcie x (n), dając w ten sposób kierunek zjazdu, następnie oblicza, jak duży krok należy podjąć w zależności od tego, jak dobrze funkcja liniowa jest zbliżona do F w punkcie x (n). LM wylicza, jak dobrze jest funkcja aproksymująca, w zasadzie robiąc krok w tak wyznaczonym kierunku i porównując, jak bardzo liniowe przybliżenie do F zmniejszyło się do tego, jak bardzo zmniejszyła się faktyczna funkcja F. Jeśli są blisko, przybliżona funkcja jest dobra i możemy zrobić nieco większy krok. Jeśli nie są blisko, to funkcja aproksymacji nie jest dobra i powinniśmy wycofać się i zrobić mniejszy krok.
Czy istnieje sposób na połączenie algorytmu Levenberga-Marquardta ze stochastycznym gradientem zniżania? – mertyildiran
kiedyś these notes from a course at Purdue University kodować się ogólny Levenberga Marquardt algorytm dopasowywania krzywej MATLAB, który oblicza pochodne numerycznych i dlatego przyjmuje żadnej funkcji formy f(x;p) gdzie p jest wektorem parametrów dopasowania.
Podstawowe idee algorytmu LM można wytłumaczyć na kilku stronach - ale do wykonania na poziomie produkcyjnym, które jest szybkie i niezawodne, konieczne są liczne subtelne optymalizacje. Najnowszą wersją jest nadal implementacja Minpack autorstwa Moré i wsp., Udokumentowana szczegółowo przez Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) oraz w podręczniku użytkownika Minpacka (http://www.mcs.anl.gov/~more/ANL8074b.pdf). Aby przestudiować kod, moje tłumaczenie C (http: apps.jcns.fz-juelich.de/lmfit) jest prawdopodobnie bardziej dostępne niż oryginalny kod Fortrana.
To fajny program C, który wykonałeś! Potrzebowałem czegoś podobnego (LM w C++, w moim przypadku), i tworzę dokumentację, twoja wersja wygląda obiecująco :) – tomsmeding
Dziękuję! Ponieważ lmfit jest osobno skompilowaną biblioteką C, działa po rozpadzie z C++. –
Czy udało Ci się wdrożyć ten algorytm w OpenCL? Byłbym również bardzo zainteresowany. – Dan
Właśnie skończyłem pisać o tym w miejmy nadzieję zrozumiały sposób. Poniższy link zawiera całą linię ewolucyjną 5 algorytmów optymalizacyjnych kończących się na LAM. Użyłem pewnych analogii ze sportów narciarskich, aby było to bardziej zrozumiałe. http://stackoverflow.com/a/22394465/457687 – Vlad