Алгоритм Левенберга–Марквардта (англ.Levenberg–Marquardt algorithm, LMA або просто LM), також відомий як метод сгасних найменших квадратів (англ.damped least-squares, DLS) використовується у математиці та обчислювальній техніці для розв'язування нелінійних задач найменших квадратів. Такі задачі мінімізації особливо актуальні при підборі кривої методом найменших квадратів. LMA інтерполює між алгоритмом Гаусса–Ньютона (GNA) та методом градієнтного спуску. LMA є більш надійним, ніж GNA, що означає, що в багатьох випадках він знаходить рішення, навіть якщо воно починається дуже далеко від кінцевого мінімуму. Для нормальної роботи функцій і розумних стартових параметрів LMA, як правило, повільніше, ніж GNA. LMA також можна розглядати як Гаусса–Ньютона, використовуючи підхід довіри до регіону.
LMA використовується в багатьох програмних додатках для розв'язання загальних задач допасовування кривої[en]. Використовуючи алгоритм Гаусса–Ньютона, він часто сходиться швидше, ніж методи першого порядку.[6] Однак, як і інші алгоритми ітераційної оптимізації, LMA знаходить лише локальний мінімум, який не обов'язково є глобальним мінімумом.
Основне застосування алгоритму Левенберга–Марквардта полягає в задачі допасовування кривої[en] методом найменших квадратів: для заданого набору емпіричних пар незалежних і залежних змінних, знайти параметри модельної кривої так, щоб суму квадратів відхилень було зведено до мінімуму:
набір вважається непорожнім.
Рішення
Як і інші алгоритми чисельної мінімізації, алгоритм Левенберга–Марквардта є ітераційною процедурою. Щоб почати мінімізацію, користувач повинен надати початкове припущення для вектора параметрів . У випадках лише з одним мінімумом, ненавчені стандартні припущення, як буде працювати нормально; у випадках з кількома мінімумами алгоритм сходить до глобального мінімуму лише в тому випадку, якщо початкове припущення вже дещо близько до остаточного рішення.
На кожному кроці ітерації вектор параметрів замінюється на нову оцінку . Щоб визначити , функція апроксимується його лінеаризацією:
де
є градієнтом (в даному випадку вектором рядка) з відношенням до .
Сума квадратних відхилень має свій мінімум при нульовому градієнті по відношенню до . Наведене вище наближення першого порядку дає
або у векторному позначенні,
Візьмемо похідну від з відношенням до і встановлення результату на нуль, що дає
де є матриця Якобі, у якій -й ряд дорівнює , і де і є векторами з -ї компоненти і відповідно. Наведений вище вираз отримано для підпадає під метод Гаусса–Ньютона. Матриця Якобі, як визначено вище, є (загалом) не квадратною матрицею, а прямокутною матрицею розміру , де — кількість параметрів (розмір вектора ). Матричне множення дає необхідну квадратну матрицю і добуток матриці-вектору з правого боку дають вектор розміру . В результаті виходить набір лінійних рівнянь, які можна розв'язувати для .А
Внесок Левенберга полягає в тому, щоб замінити це рівняння на «згасну версію»:
де є одиничною матрицею, що дає приріст до розрахункового вектора параметрів .
Коефіцієнт (невід'ємного) демпфування коригується на кожній ітерації. Якщо зменшення є швидким, можна використовувати менше значення, наближаючи алгоритм до алгоритму Гаусса–Ньютона, тоді як, якщо ітерація дає недостатнє зменшення залишку, можна збільшити, наблизивши на крок до напрямку градієнтного спуску. Зверніть увагу, що градієнт з відношенням до дорівнює . Тому для великих значень , крок буде зроблено приблизно в напрямку, протилежному градієнту. Якщо будь-яка довжина обчисленого кроку або зменшення суми квадратів з останнього вектора параметрів падають нижче попередньо визначених меж, ітерація зупиняється та останній вектор параметра вважається рішенням.
Коли коефіцієнт демпфування є великим відносно , інвертувати не потрібно, оскільки оновлення добре апроксимується невеликим кроком градієнта .
Щоб зробити масштаб рішення інваріантним, алгоритм Марквардта розв'язав модифіковану задачу з кожним компонентом градієнта, масштабованим відповідно до кривизни. Це забезпечує більший рух уздовж напрямків, де градієнт менший, що дозволяє уникнути повільної збіжності в напрямку малого градієнта. Флетчер у своїй статті 1971 року Модифікована підпрограма Марквардта для нелінійних найменших квадратів спростив форму, замінивши ідентичну матрицю з діагональною матрицею, що складається з діагональних елементів :
Для кращого вибору параметра демпфування були висунуті різні більш-менш евристичні аргументи . Існують теоретичні аргументи, які показують, чому деякі з цих варіантів гарантують локальну збіжність алгоритму; однак ці варіанти можуть призвести до того, що глобальна збіжність алгоритму страждає від небажаних властивостей найкрутішого спуску, зокрема, дуже повільної збіжності, близької до оптимальної.
Абсолютні значення будь-якого вибору залежать від того, наскільки добре масштабована початкова проблема. Марквардт рекомендував починати зі значення і фактор . Спочатку налаштування і обчислення залишкової суми квадратів через один крок від початкової точки з коефіцієнтом демпфування а по-друге з . Якщо обидва ці показники гірші за початкову точку, то згасання збільшується шляхом послідовного множення на поки не буде знайдено кращу точку з новим коефіцієнтом демпфування для деяких .
Якщо використати коефіцієнт демпфування це призводить до зменшення квадрата залишку, то це приймається за нове значення (і нове оптимальне розташування приймається як те, що отримано з цим коефіцієнтом демпфування) і процес продовжується; якщо використовувати це призведе до гіршого залишку, але використання призведе до кращого залишку, тоді залишається без змін, а новий оптимум приймається за значення, отримане с як демпфуючий фактор.
Ефективна стратегія для контролю параметра демпфування, що називається відкладеним задоволенням, полягає у збільшенні параметра на невелику величину для кожного кроку на підйом і зменшення на велику величину для кожного кроку вниз. Ідея цієї стратегії полягає в тому, щоб уникнути занадто швидкого спуску на початку оптимізації, отже, обмежуючи кроки, доступні в майбутніх ітераціях, і, отже, сповільнюючи зближення[7]. Збільшення в 2 рази і зменшення в 3 рази виявилося ефективним у більшості випадків, тоді як для великих проблем більш екстремальні значення можуть працювати краще, зі збільшенням у 1,5 раза та зменшенням у 5 раз.[8]
Геодезичне прискорення
При інтерпретації кроку Левенберга–Марквардта як швидкості вздовж геодезичної траєкторії в просторі параметрів можна покращити метод, додавши член другого порядку, що враховує прискорення вздовж геодезичної
де є рішенням
Оскільки цей член геодезичного прискорення залежить лише від похідної за напрямком вздовж напрямку швидкості , він не вимагає обчислення повної похідної матриці другого порядку, вимагаючи лише невеликих накладних обчислювальних витрат.[9] Оскільки похідна другого порядку може бути досить складним виразом, може бути зручно замінити її наближенням скінченної різниці
де і вже були обчислені за допомогою алгоритму, тому для обчислення потрібна лише одна додаткова оцінка функції . Вибір скінченного різницевого кроку може вплинути на стабільність алгоритму, вибір значення близько 0,1 зазвичай є розумним.
Оскільки прискорення може вказувати в напрямку, протилежному швидкості, щоб запобігти зупинці методу, якщо демпфування занадто мале, додається додатковий критерій прискорення, щоб прийняти крок, який вимагає, що
де зазвичай фіксується до значення менше ніж 1, з меншими значеннями для складніших задач.[8]
Додавання геодезичного члена прискорення може дозволити суттєво збільшити швидкість збіжності, і це особливо корисно, коли алгоритм рухається через вузькі каньйони в ландшафті цільової функції, де дозволені кроки менші, а точність вища завдяки другому порядку термін дає значні покращення.[8]
Приклад
У цьому прикладі ми намагаємося підібрати функції використовуючи алгоритм Левенберга–Марквардта, реалізований в GNU Octave, як функцію leasqr. Графіки показують, що вони все краще відповідають параметрам , що використовується на початковій кривій. Лише тоді, коли параметри останнього графіка вибрано найближчими до оригіналу, криві точно підходять. Це рівняння є прикладом дуже чутливих початкових умов для алгоритму Левенберга–Марквардта. Однією з причин такої чутливості є існування кількох мінімумів — функції що має мінімуми при значенні параметра і .
↑Morrison, David D. (1960). Methods for nonlinear least squares problems and convergence proofs. Proceedings of the Jet Propulsion Laboratory Seminar on Tracking Programs and Orbit Determination: 1—9.
↑ абвTranstrum, Mark K; Sethna, James P (2012). Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization. arXiv:1201.5885 [physics.data-an].
T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg, 2016, ISBN 978-3-658-11455-8.
Japanese professional wrestler Milano Collection A. T.Sawafuji as Milano Collection A. T. in June 2007, after winning the 2007 Best of the Super JuniorsBirth nameAkihito Sawafuji[1]Born (1976-08-27) August 27, 1976 (age 47)[2]Morioka, Iwate[2]Professional wrestling careerRing name(s)Milano Collection A. T.Masked ItalianoBilled height1.83 m (6 ft 0 in)[2]Billed weight85 kg (187 lb)[3]Billed fromMilan, Italy[2]Trained...
Цискарішвілі Габріель Дмитровичгруз. გაბრიელ დიმიტრის ძე ცისკარიშვილი Народився 1892Земо-Алвані, муніципалітет Ахмета, ГрузіяПомер 30 серпня 1924(1924-08-30)Тифліс, Закавказька РФСР, СРСР·розстрілДіяльність політикAlma mater Історико-філологічний факультет Московсь
Nota: Para outros significados, veja Geminação de cidades. Foram assinalados vários problemas nesta página ou se(c)ção: Não tem fontes. Texto necessita de revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Cidades gêmeas correspondem a adensamentos populacionais cortados pela linha de fronteira (terrestre ou fluvial, articulada ou não por obra de infraestrutura). Essas cidades contam com grande potencial de integração econômica e cultural. Há intensa...
Ronnie Coleman Datos personalesNombre completo Ronald Dean ColemanApodo(s) The KingNacimiento Monroe, Luisiana, Estados Unidos13 de mayo de 1964 (59 años)Nacionalidad(es) EstadounidenseAltura 1,80 m (5′ 11″)Carrera deportivaDeporte CulturismoEquipo universitario GSUEstado Retirado Títulos Mister Olympia (1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005) Página web oficial[editar datos en Wi...
High Priestess of Soul Album de Nina Simone Sortie 1967 Enregistré New York Durée 35:51 Genre Soul, Jazz Format LP Producteur Hal Mooney Label Philips Critique AllMusic [1] Albums de Nina Simone Wild Is the Wind (1966) Nina Simone Sings the Blues (1967)modifier High Priestess of Soul ((fr) Haute prêtresse de la soul) est un album de la chanteuse, pianiste et compositrice Nina Simone (1933-2003), enregistré en studio en 1967. Nina Simone est accompagné d'un grand orchestre dirig...
Minoru ChiakiMinoru Chiaki sebagai imam di dalam Rashomon (1950).Nama asal千秋 実LahirKatsuji Sasaki(1917-04-28)28 April 1917Onnenai, Nakagawa, Kamikawa, Hokkaido, JepangMeninggal1 November 1999(1999-11-01) (umur 82)Fuchu, Tokyo, JepangPekerjaanAktorTahun aktif1949 - 1999Suami/istriFumie SasakiAnakKatsuhiko Sasaki Minoru Chiaki (千秋 実code: ja is deprecated , Chiaki Minoru, 28 April 1917 – 1 November 1999) adalah aktor Jepang yang muncul dalam film sepert...
Town in Vermont, United StatesLincoln, VermontTown SealLocation in Addison County and the state of Vermont.Coordinates: 44°5′31″N 72°58′53″W / 44.09194°N 72.98139°W / 44.09194; -72.98139CountryUnited StatesStateVermontCountyAddisonChartered1780Settled1790Organized1798CommunitiesLincolnDowningvilleSouth LincolnWest LincolnArea • Total44.6 sq mi (115.5 km2) • Land44.4 sq mi (115.0 km2) •...
Political backlash against LGBT people 2020s anti-LGBT movement in the United StatesPart of homophobia, transphobia and LGBT history in the United StatesU.S. representative Marjorie Taylor Greene of Georgia and Libs of TikTok creator Chaya Raichik holding a sign in March 2023 stating that there are only two genders.Date2021[a] – ongoingLocationUnited StatesCaused byIncreasing transparency, relevance, and acceptance of LGBT identity in the United StatesGoalsTo reverse social change i...
قاعدة إدواردز الجوية إياتا: EDW – ايكاو: KEDW[1] موجز المشغل القوات الجوية الأمريكية البلد الولايات المتحدة الموقع وسيط property غير متوفر. الارتفاع 704.4 متر[2] إحداثيات 34°55′26″N 117°53′29″W / 34.923890144075°N 117.89125635636°W / 34.923890144075; -117.89125635636 الموقع ا...
Улица Мукусаласлатыш. Mūkusalas iela Общая информация Страна Латвия Город Рига Исторический район Торнякалнс, Зиепниеккалнс Протяжённость 4081 м Прежние названия Мукенгольмская,Оскара (Оскаровская), Радиотехникас Медиафайлы на Викискладе Улица Му́кусалас (латыш. Mūkusalas ...
2012 mixtape by Lloyd BanksV.6: The GiftMixtape by Lloyd BanksReleasedJuly 24, 2012Recorded2011-2012GenreEast Coast Rap, Hardcore Rap, Gangsta RapLabelG-Unit RecordsProducer Automatik Doe Pesci Superiors A6 V Don Beat Butcha Tha Jerm Cardiak Lloyd Banks chronology The Cold Corner 2(2011) V.6: The Gift(2012) A.O.N. (All Or Nothing) Series Vol. 1: F.N.O. (Failure's No Option)(2013) Singles from V.6: The Gift Open ArmsReleased: March 30, 2012 Professional ratingsReview scoresSourceRating...
Comune in Veneto, ItalyMonselice Monséłexe (Venetian)ComuneComune di Monselice Coat of armsLocation of Monselice MonseliceLocation of Monselice in ItalyShow map of ItalyMonseliceMonselice (Veneto)Show map of VenetoCoordinates: 45°14′N 11°45′E / 45.233°N 11.750°E / 45.233; 11.750CountryItalyRegionVenetoProvincePadua (PD)FrazioniMarendole, Monticelli, Ca' Oddo, San Cosma, San Bortolo, CarmineGovernment • MayorGiorgia Bedin (since 2019) (Leg...
Unincorporated community in Pennsylvania, United StatesLaytonUnincorporated communityLaytonLocation of Layton, PennsylvaniaCoordinates: 40°5′24″N 79°43′22″W / 40.09000°N 79.72278°W / 40.09000; -79.72278Country United StatesState PennsylvaniaCountyFayetteElevation250 m (810 ft)Time zoneUTC-5 (EST) • Summer (DST)UTC-4 (EDT)ZIP code15428 Layton is an unincorporated community in Fayette County, Pennsylvania. History Layton Bridge...