Метод Левенберга—Марквардта

Сентябрь 3, 2022

Главная
Алгебра
Метод Левенберга—Марквардта

Содержание

2. Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах. Является альтернативой
3. Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего
4. Функцию называют невязкой в предположении, что . LMA решает задачу нелинейной минимизации методом наименьших квадратов. Это
5. Метод Левенберга—Марквардта 07.11.2012 Теперь можно переписать как а ее производные представить с помощью матрицы Якоби Рассмотрим
6. Метод Левенберга—Марквардта 07.11.2012 Тогда градиент функции и . Решая задачу минимума , получим то есть -
7. Отличительной особенностью метода наименьших квадратов является то, что, имея матрицу Якоби , легко получить гессиан ,
8. LMA как комбинация простейшего градиентного метода и метода Ньютона— Гаусса Простейший градиентный метод – это наиболее
9. Другая проблема заключается в том, что кривизна поверхности невязки может быть не одинаковой по всем направлениям.
10. Пренебрегая членами более высокого порядка (считая квадратичной вблизи ) и решая задачу минимума, приравняв левую часть
11. Легко заметить, что простейший градиентный метод и метод Ньютона— Гаусса дополняют друг друга с точки зрения
12. Данное правило используется следующим образом: если на очередной итерации невязка сокращается, это значит, что предположение о
13. Таким образом, алгоритм Левенберга представляется в виде последовательности действий: 1. Вычислить параметр на очередной итерации по
14. Недостатком данного алгоритма является то, что если значение велико, вычисленная матрица Гессе никак не используется. Однако
15. Поскольку гессиан пропорционален кривизне f, правило приведет к большим шагам при малой кривизне (т.е. для почти
16. Метод доверительных интервалов Historically, the LM algorithm was presented by Marquardt as given in the previous
17. Метод доверительных интервалов By contrast, in a trust-region algorithm we build a model m(k) that approximates
18. Метод доверительных интервалов The iteration step itself is . A trust-region algorithm can thus be conceived
19. Метод доверительных интервалов It can be seen that basically states that if then but not otherwise.
20. Descriptions Detailed description of the algorithm can be found in Numerical Recipes in C, Chapter 15.5:
21. Implementations The oldest implementation still in use is lmdif, from MINPACK, in Fortran, in the public
22. In this example we try to fit the function y = a cos(bX) + b sin(aX)
23. Fig 1. Poor Fit Example (1-st of 3) 07.11.2012
24. Fig 2. Better Fit Example (2-nd of 3) 07.11.2012
26. Скачать презентацию

Слайд 2

Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах.

Является альтернативой методу Гаусса — Ньютона. Может рассматриваться как комбинация последнего с методом градиентного спуска или как метод доверительных интервалов. Алгоритм был сформулирован независимо Левенбергом (1944) и Марквардтом (1963).
Kenneth Levenberg (1944). "A Method for the Solution of Certain Non-Linear Problems in Least Squares". The Quarterly of Applied Mathematics 2: 164–168.
Donald Marquardt (1963). "An Algorithm for Least-Squares Estimation of Nonlinear Parameters". SIAM Journal on Applied Mathematics 11(2): 431–441. doi:10.1137/0111030.
Philip E. Gill and Walter Murray (1978). "Algorithms for the solution of the nonlinear least-squares problem". SIAM Journal on Numerical Analysis 15 (5): 977–992. doi:10.1137/0715063.

07.11.2012

Метод Левенберга—Марквардта

The algorithm was first published by Kenneth Levenberg, while working at the Frankford Army Arsenal. It was rediscovered by Donald Marquardt who worked as a statistician at DuPont and independently by Girard, Wynn and Morrison.

Слайд 3

Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он

превосходит по производительности метод наискорейшего спуска и другие методы сопряженных градиентов в различных задачах. Изначально считалось, что LMA – это комбинация простейшего градиентного метода и метода Гаусса-Ньютона, однако впоследствии выяснилось, что данный алгоритм можно также рассматривать как метод доверительных интервалов.

Метод Левенберга—Марквардта

07.11.2012

Слайд 4

Функцию называют невязкой в предположении, что .
LMA решает задачу нелинейной

минимизации методом наименьших квадратов. Это означает, что функция, которую необходимо минимизировать, выглядит следующим образом:

07.11.2012

Метод Левенберга—Марквардта

где - вектор, а - функция отображения из в .

Для простоты функция представляется вектором невязки вида:

Слайд 5

Метод Левенберга—Марквардта
07.11.2012
Теперь можно переписать как
а ее производные представить с

помощью матрицы Якоби

Рассмотрим линейный случай, когда каждая функция линейна. Здесь якобиан равен константе, можно представить как гиперплоскость в пространстве, а

Слайд 6

Метод Левенберга—Марквардта
07.11.2012
Тогда градиент функции и . Решая задачу минимума , получим

то есть - решение системы нормальных уравнений

Возвращаясь к общему (нелинейному) случаю, получим:

Слайд 7

Отличительной особенностью метода наименьших
квадратов является то, что, имея матрицу Якоби

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

07.11.2012

Метод Левенберга—Марквардта

Слайд 8

LMA как комбинация простейшего градиентного
метода и метода Ньютона— Гаусса
Простейший градиентный

метод – это наиболее интуитивно
понятный способ нахождения минимума функции. Вычисление
параметра на очередном шаге выполняется путем вычитания
градиента функции, умноженного на заданный положительный
коэффициент:
Однако при таком подходе имеют место различные проблемы
сходимости. Логично предположить, что желательно было бы
осуществлять большие шаги по направлению градиента там, где
градиент мал (т.е. наклон пологий), и, наоборот, маленькие шаги
там, где градиент большой, чтобы не пропустить минимум.

07.11.2012

Метод Левенберга—Марквардта

Однако в формуле выполняются прямо противоположные действия.

Слайд 9

Другая проблема заключается в том, что кривизна поверхности невязки
может быть не

одинаковой по всем направлениям. К примеру, если
есть длинная и узкая впадина на поверхности невязки, компонент
градиента в направлении, указывающем вдоль основания впадины,
очень мал, а компонент градиента вдоль стенок впадины, наоборот,
велик. Это приводит к движению по направлению к стенкам впадины,
тогда как необходимо перемещаться на большие расстояния вдоль
основания впадины и на малые – вдоль ее стенок.
Ситуацию можно улучшить, если учитывать информацию о кривизне и
градиенте, т. е. вторые производные. Один из способов сделать это –
использовать метод Ньютона для решения уравнения .
Раскладывая градиент в ряд Тейлора вокруг текущего состояния ,
получим

Метод Левенберга—Марквардта

07.11.2012

Слайд 10

Пренебрегая членами более высокого порядка (считая квадратичной
вблизи ) и решая задачу

минимума, приравняв левую часть
уравнения
к нулю, получим правило вычисления параметра на очередном шаге по
методу Ньютона:
Поскольку метод Ньютона напрямую использует предположение о
квадратичности (пренебрегая членами более высоких порядков при
разложении в ряд Тейлора), нет необходимости точно вычислять
гессиан, а достаточно использовать его аппроксимацию.
Главное достоинство такого подхода – быстрая сходимость. Однако
скорость сходимости зависит от начального положения (если быть
более точным - от линейности вокруг начального положения).

07.11.2012

Метод Левенберга—Марквардта

Слайд 11

Легко заметить, что простейший градиентный метод и метод
Ньютона— Гаусса дополняют друг

друга с точки зрения
предоставляемых преимуществ. Основываясь на этом наблюдении,
Левенберг предложил алгоритм, в котором правило вычисления
параметра
есть комбинация правил:
где – матрица Гессе, вычисленная в точке .

Метод Левенберга—Марквардта

07.11.2012

Слайд 12

Данное правило используется следующим образом:
если на очередной итерации невязка сокращается, это

значит, что предположение о квадратичности
работает, и мы уменьшаем (обычно в 10 раз), чтобы
понизить влияние градиентного спуска. С другой
стороны, если невязка увеличивается, необходимо
следовать направлению градиента, и мы увеличиваем (во столько же раз).

Метод Левенберга—Марквардта

07.11.2012

Слайд 13

Таким образом, алгоритм Левенберга представляется в
виде последовательности действий:
1. Вычислить параметр

на очередной итерации по правилу
2. Оценить невязку в новом векторе параметров.
3. Если в результате вычисления параметра невязка увеличилась, вернуться на шаг назад (т.е. восстановить прежние значения весов) и увеличить в 10 раз. Затем повторить выполнение, начиная с шага 1.
4. Если в результате вычисления параметра невязка уменьшилась, принять текущий шаг (т.е. оставить новые значения весов) и уменьшить в 10 раз.

Метод Левенберга—Марквардта

07.11.2012

Слайд 14

Недостатком данного алгоритма является то, что если значение
велико, вычисленная матрица Гессе

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

Метод Левенберга—Марквардта

07.11.2012

Слайд 15

Поскольку гессиан пропорционален кривизне f, правило приведет к большим шагам при

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

Метод Левенберга—Марквардта

07.11.2012

Слайд 16

Метод доверительных интервалов
Historically, the LM algorithm was presented by Marquardt as

given in the previous section where the parameter, , was manipulated directly to find the minimum. Subsequently, a trust-region approach to the algorithm has gained ground.
Trust-region algorithms work in a fundamentally different manner than those presented in the previous section, which are called line-search methods. In a line search method, we decide on a direction in which to descend the gradient and are then concerned about the step size, i.e. if is the direction of descent, and the stepsize, then our step is given by and the stepsize is obtained by solving the sub-problem

Метод Левенберга—Марквардта

07.11.2012

Слайд 17

Метод доверительных интервалов
By contrast, in a trust-region algorithm we build a

model m(k) that approximates the function f in a finite region near x(k). This region, Δ, where the model is a good approximation of f , is called the trust-region. Trust-region algorithms maintain Δ and update it at each iteration using heuristics.
The model m(k) is most often a quadratic obtained by a Taylor series expansion of f around x(k), i.e.
where H is the Hessian (or an approximation of the Hessian) matrix. The sub-problem to be solved to find the step to take during the iteration is

Метод Левенберга—Марквардта

07.11.2012

Слайд 18

Метод доверительных интервалов
The iteration step itself is . A trust-region algorithm

can thus be conceived of as a sequence of iterations, in each of which we model the function f by a quadratic and then jump to the minimum of that quadratic.
The solution of problem is given by a theorem which is as follows

Метод Левенберга—Марквардта

07.11.2012

Слайд 19

Метод доверительных интервалов
It can be seen that basically states that if

then
but not otherwise. Hence, we reach the same parameter update equation for the LM algorithm using a trust-region framework as we obtained using the line-search method. The heuristic to update the size of the trust-region usually depends on the ratio of the expected change in f to the predicted change, i.e.
If there is a good agreement between predicted and actual values , then Δ is increased; if the agreement is poor ( is small), then is decreased. If is smaller than a threshold value ( ), the step is rejected and the value of is retained but Δ is decreased as before. Thus, the algorithm is similar to the previous one but the value that is changed with each iteration is Δ and not .

Метод Левенберга—Марквардта

07.11.2012

Слайд 20

Descriptions
Detailed description of the algorithm can be found in Numerical Recipes in

C, Chapter 15.5: Nonlinear models
C. T. Kelley, Iterative Methods for Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, ISBN 0-89871-433-8. Online copy
History of the algorithm in SIAM news
A tutorial by Ananth Ranganathan
Methods for Non-Linear Least Squares Problems by K. Madsen, H.B. Nielsen, O. Tingleff is a tutorial discussing non-linear least-squares in general and the Levenberg-Marquardt method in particular
T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). Vieweg+Teubner, ISBN 978-3-8348-1022-9.

Метод Левенберга—Марквардта

07.11.2012

Слайд 21

Implementations
The oldest implementation still in use is lmdif, from MINPACK, in Fortran, in the public

domain. See also:
lmfit, a translation of lmdif into C/C++ with an easy-to-use wrapper for curve fitting, public domain.
The GNU Scientific Library library has a C interface to MINPACK.
C/C++ Minpack includes the Levenberg–Marquardt algorithm.
Several high-level languages and mathematical packages have wrappers for the MINPACK routines, among them:
Python library scipy, module scipy.optimize.leastsq,
IDL, add-on MPFIT.
R (programming language) has the minpack.lm package.
levmar is an implementation in C/C++ with support for constraints, distributed under the GNU General Public License.
levmar includes a MEX file interface for MATLAB
Perl (PDL), python and Haskell interfaces to levmar are available: see PDL::Fit::Levmar, PyLevmar and HackageDB levmar.
sparseLM is a C implementation aimed at minimizing functions with large, arbitrarily sparse Jacobians. Includes a MATLAB MEX interface.
InMin library contains a C++ implementation of the algorithm based on the eigen C++ linear algebra library. It has a pure C-language API as well as a Python binding
ALGLIB has implementations of improved LMA in C# / C++ / Delphi / Visual Basic. Improved algorithm takes less time to converge and can use either Jacobian or exact Hessian.

Метод Левенберга—Марквардта

07.11.2012

Слайд 22

In this example we try to fit the function
y = a cos(bX) + b

sin(aX)
using the Levenberg–Marquardt algorithm
implemented in GNU Octave as the leasqr function. The 3 graphs Fig 1,2,3 show progressively better
fitting for the parameters a=100, b=102 used in the
initial curve. Only when the parameters in Fig 3 are
chosen closest to the original, are the curves fitting
exactly. This equation is an example of very sensitive
initial conditions for the Levenberg–Marquardt
algorithm. One reason for this sensitivity is the
existence of multiple minima — the function
cos(βx) has minima at parameter value b* and b*+2pi.

Example

07.11.2012

Слайд 23

Fig 1. Poor Fit
Example (1-st of 3)
07.11.2012

Слайд 24

Метод Левенберга—Марквардта

Содержание

Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах.

Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он

Функцию называют невязкой в предположении, что . LMA решает задачу нелинейной

Метод Левенберга—Марквардта07.11.2012Теперь можно переписать как а ее производные представить с

Метод Левенберга—Марквардта07.11.2012Тогда градиент функции и . Решая задачу минимума , получим

Отличительной особенностью метода наименьших квадратов является то, что, имея матрицу Якоби

LMA как комбинация простейшего градиентногометода и метода Ньютона— Гаусса Простейший градиентный

Другая проблема заключается в том, что кривизна поверхности невязкиможет быть не

Пренебрегая членами более высокого порядка (считая квадратичнойвблизи ) и решая задачу

Легко заметить, что простейший градиентный метод и методНьютона— Гаусса дополняют друг

Данное правило используется следующим образом:если на очередной итерации невязка сокращается, это

Таким образом, алгоритм Левенберга представляется ввиде последовательности действий: 1. Вычислить параметр

Недостатком данного алгоритма является то, что если значениевелико, вычисленная матрица Гессе

Поскольку гессиан пропорционален кривизне f, правило приведет к большим шагам при

Метод доверительных интерваловHistorically, the LM algorithm was presented by Marquardt as

Метод доверительных интерваловBy contrast, in a trust-region algorithm we build a

Метод доверительных интерваловThe iteration step itself is . A trust-region algorithm

Метод доверительных интерваловIt can be seen that basically states that if

DescriptionsDetailed description of the algorithm can be found in Numerical Recipes in

ImplementationsThe oldest implementation still in use is lmdif, from MINPACK, in Fortran, in the public

In this example we try to fit the function y = a cos(bX) + b

Fig 1. Poor FitExample (1-st of 3)07.11.2012

Fig 2. Better FitExample (2-nd of 3)07.11.2012

Похожие презентации

Функцию называют невязкой в предположении, что .
LMA решает задачу нелинейной

Метод Левенберга—Марквардта
07.11.2012
Теперь можно переписать как
а ее производные представить с

Метод Левенберга—Марквардта
07.11.2012
Тогда градиент функции и . Решая задачу минимума , получим

Отличительной особенностью метода наименьших
квадратов является то, что, имея матрицу Якоби

LMA как комбинация простейшего градиентного
метода и метода Ньютона— Гаусса
Простейший градиентный

Другая проблема заключается в том, что кривизна поверхности невязки
может быть не

Пренебрегая членами более высокого порядка (считая квадратичной
вблизи ) и решая задачу

Легко заметить, что простейший градиентный метод и метод
Ньютона— Гаусса дополняют друг

Данное правило используется следующим образом:
если на очередной итерации невязка сокращается, это

Таким образом, алгоритм Левенберга представляется в
виде последовательности действий:
1. Вычислить параметр

Недостатком данного алгоритма является то, что если значение
велико, вычисленная матрица Гессе

Метод доверительных интервалов
Historically, the LM algorithm was presented by Marquardt as

Метод доверительных интервалов
By contrast, in a trust-region algorithm we build a

Метод доверительных интервалов
The iteration step itself is . A trust-region algorithm

Метод доверительных интервалов
It can be seen that basically states that if

Descriptions
Detailed description of the algorithm can be found in Numerical Recipes in

Implementations
The oldest implementation still in use is lmdif, from MINPACK, in Fortran, in the public

In this example we try to fit the function
y = a cos(bX) + b

Fig 1. Poor Fit
Example (1-st of 3)
07.11.2012

Fig 2. Better Fit
Example (2-nd of 3)
07.11.2012