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

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

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

Ответы

Ответ 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). Л. М. выясняет, насколько хороша аппроксимирующая функция, в основном делая шаг в определенном таким образом направлении и сравнивая, насколько линейное приближение к F уменьшалось до того, насколько фактическая функция F уменьшилась. Если они близки, аппроксимирующая функция хороша, и мы можем сделать небольшой шаг. Если они не близки, то функция аппроксимации не является хорошей, и мы должны отступить и сделать меньший шаг.

Ответ 3

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

Ответ 4

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

Ответ 5

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