Метод Левенберга—Марквардта - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод Левенберга—Марквардта. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ Константин Ловецкий Ноябрь 2012

Слайд 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.

Слайд 3

Описание слайда:

Метод Левенберга—Марквардта Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего спуска и другие методы сопряженных градиентов в различных задачах. Изначально считалось, что LMA – это комбинация простейшего градиентного метода и метода Гаусса-Ньютона, однако впоследствии выяснилось, что данный алгоритм можно также рассматривать как метод доверительных интервалов.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 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

Слайд 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

Слайд 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

Слайд 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 .

Слайд 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.

Слайд 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.

Слайд 22

Описание слайда:

Example 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.