Как работает алгоритм Левенберга-Марквардта подробно, но понятно?

Question

Я программист, который хочет узнать, как работает алгоритм аппроксимации кривой Левенберга-Марквардта, чтобы я мог реализовать его самостоятельно.Есть ли где-нибудь хороший учебник, который может подробно объяснить, как это работает, если читатель является программистом, а не математиком.

Моя цель — реализовать этот алгоритм в opencl, чтобы он работал с аппаратным ускорением.

Answer 1

• Пытаться http://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm
• PDF-руководство из Ананта Ранганатана
• JavaЧисловые числа имеет довольно читаемую реализацию
• В ИКС есть С/С++ выполнение

Answer 2

Минимизация функции аналогична попытке найти самую низкую точку на поверхности.Представьте себе, что вы идете по холмистой местности и пытаетесь добраться до самой низкой точки.Вы могли бы найти направление, ведущее вниз, и идти до тех пор, пока оно не перестанет идти под гору.Затем вы выберете новое направление, идущее вниз, и пойдете в этом направлении, пока оно не перестанет спускаться, и так далее.В конце концов (надеюсь) вы достигнете точки, в которой больше не будет никакого направления вниз.Тогда вы будете на (локальном) минимуме.

Алгоритм LM и многие другие алгоритмы минимизации используют эту схему.

Предположим, что минимизируемая функция — это F, и на нашей итерации мы находимся в точке x(n).Мы хотим найти следующую итерацию x(n+1) такую, что F(x(n+1)) < F(x(n)), т.е.значение функции меньше.Чтобы выбрать x(n+1), нам нужны две вещи: направление от x(n) и размер шага (как далеко идти в этом направлении).Алгоритм LM определяет эти значения следующим образом:

Сначала вычислите линейное приближение к F в точке x(n).Легко определить направление спуска линейной функции, поэтому мы используем линейную аппроксимирующую функцию, чтобы определить направление спуска.Далее нам нужно знать, как далеко мы можем зайти в этом выбранном направлении.Если наша аппроксимирующая линейная функция является хорошим приближением F для большой области вокруг x(n), то мы можем сделать довольно большой шаг.Если это хорошее приближение, очень близкое к x(n), то мы можем сделать лишь очень маленький шаг.

Это то, что делает LM: вычисляет линейную аппроксимацию F в точке x(n), таким образом определяя направление спуска, а затем определяет, какой большой шаг следует сделать, исходя из того, насколько хорошо линейная функция аппроксимирует F в точке x(n).LM определяет, насколько хороша аппроксимирующая функция, делая шаг в определенном таким образом направлении и сравнивая, насколько уменьшилась линейная аппроксимация F с тем, насколько уменьшилась фактическая функция F.Если они близки, аппроксимирующая функция хороша, и мы можем сделать шаг немного больше.Если они не близки, то функция аппроксимации не очень хороша, и нам следует отступить и сделать шаг поменьше.

Answer 3

Основные идеи алгоритма LM можно объяснить на нескольких страницах, но для быстрой и надежной реализации промышленного уровня необходимо множество тонких оптимизаций.Современным состоянием по-прежнему остается реализация Minpack, разработанная Море и др., подробно описанная Море в 1978 году (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) и в руководстве пользователя Minpack (http://www.mcs.anl.gov/~more/ANL8074b.pdf).Для изучения кода мой перевод на C (https://jugit.fz-juelich.de/mlz/lmfit), вероятно, более доступен, чем исходный код на Фортране.

Answer 4

Пытаться Численные рецепты (Левенберг-Марквардт находится в разделе 15.5).Он доступен в Интернете, и я обнаружил, что они объясняют алгоритмы подробно (у них есть полный исходный код, насколько более подробно вы можете получить...), но при этом доступно.

Answer 5

я использовал эти заметки из курса в Университете Пердью закодировать общий алгоритм аппроксимации кривой Левенберга-Марквардта в MATLAB, который вычисляет числовые производные и, следовательно, принимает любую функцию вида f(x;p) где p – вектор подгоночных параметров.