Levenberg – Marquardt algoritması - Levenberg–Marquardt algorithm

Gelen matematik ve bilgi işlem, Levenberg-Marquardt algoritmasını ( LMA veya LM olarak da bilinir), sönümlü en küçük kareler ( DLS ) yöntemine çözmek için kullanılan en küçük kareler doğrusal olmayan bir sorun. Bu minimizasyon sorunları özellikle en küçük kareler eğri uydurmada ortaya çıkar .

LMA, genel eğri uydurma problemlerini çözmek için birçok yazılım uygulamasında kullanılır. Ancak, birçok uydurma algoritmasında olduğu gibi, LMA yalnızca yerel bir minimum bulur ve bu mutlaka global minimum değildir . LMA, Gauss – Newton algoritması (GNA) ve gradyan iniş yöntemi arasında enterpolasyon yapar . LMA, GNA'dan daha sağlamdır , bu da çoğu durumda nihai minimumdan çok uzakta başlasa bile bir çözüm bulduğu anlamına gelir. İyi niyetli işlevler ve makul başlangıç ​​parametreleri için LMA, GNA'dan daha yavaş olma eğilimindedir. LMA, bir güven bölgesi yaklaşımı kullanılarak Gauss – Newton olarak da görülebilir .

Algoritma ilk olarak 1944'te Kenneth Levenberg tarafından Frankford Army Arsenal'de çalışırken yayınlandı . Bu 1963 yeniden keşfedilen Donald Marquardt bir şekilde çalışan, istatistikçiye de DuPont Girard, Wynne ve Morrison, bağımsız bir şekilde, ve.

Sorun

Levenberg-Marquardt algoritmasının birincil uygulaması, en küçük kareler eğri uydurma problemidir: bağımsız ve bağımlı değişkenlerin bir dizi ampirik çifti verildiğinde , model eğrisinin parametrelerini bulun, böylece sapmaların karelerinin toplamı en aza indirilir. : ${\görüntüleme stili m}$${\displaystyle \sol(x_{i},y_{i}\sağ)}$${\ displaystyle {\ boldsymbol {\ beta}}}$${\displaystyle f\sol(x,{\boldsymbol {\beta }}\sağ)}$${\ displaystyle S \ sol ({\ boldsymbol {\ beta}} \ sağ)}$

${\displaystyle {\hat {\boldsymbol {\beta }}}\in \operatöradı {argmin} \limits _{\boldsymbol {\beta }}S\left({\boldsymbol {\beta }}\sağ)\eşdeğer \operatöradı {argmin} \limits _{\boldsymbol {\beta }}\sum _{i=1}^{m}\left[y_{i}-f\left(x_{i},{\boldsymbol {\ beta}} \ sağ) \ sağ] ^ {2},}$ boş olmadığı varsayılır.

Çözüm

Diğer sayısal küçültme algoritmaları gibi, Levenberg – Marquardt algoritması da yinelemeli bir prosedürdür. Bir minimizasyonu başlatmak için, kullanıcının parametre vektörü için bir başlangıç ​​tahmini sağlaması gerekir . Yalnızca bir minimumun olduğu durumlarda, bilgisiz bir standart tahmin işe yarayacaktır; Birden fazla minimumun olduğu durumlarda , algoritma yalnızca ilk tahmin zaten nihai çözüme biraz yakınsa global minimuma yakınlaşır. ${\ displaystyle {\ boldsymbol {\ beta}}}$${\displaystyle {\boldsymbol {\beta }}^{\text{T}}={\begin{pmatrix}1,\ 1,\ \dots ,\ 1\end{pmatrix}}}$

Her yineleme adımında, parametre vektörü yeni bir tahminle değiştirilir . Belirlemek için , fonksiyon doğrusallaştırmasıyla yaklaşık olarak belirlenir : ${\ displaystyle {\ boldsymbol {\ beta}}}$${\ displaystyle {\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}}}$${\displaystyle {\boldsymbol {\delta }}}$${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\sağ)}$

${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\sağ)\yaklaşık f\left(x_{i},{\boldsymbol {\beta } } \ sağ) + \ mathbf {J} _ {i} {\ boldsymbol {\ delta}},}$

nerede

${\ displaystyle \ mathbf {J} _ {i} = {\ frac {\ kısmi f \ sol (x_ {i}, {\ boldsymbol {\ beta}} \ sağ)} {\ kısmi {\ kalın sembol {\ beta} }}}}$

bir gradyan arasında (bu durumda sıra vektör) ile ilgili olarak için . ${\ displaystyle f}$${\ displaystyle {\ boldsymbol {\ beta}}}$

Kare sapmaların toplamı , 'ye göre sıfır eğimde minimuma sahiptir . Yukarıda belirtilen bir birinci dereceden yaklaşım sağlar ${\ displaystyle S \ sol ({\ boldsymbol {\ beta}} \ sağ)}$${\ displaystyle {\ boldsymbol {\ beta}}}$${\displaystyle f\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\sağ)}$

${\ displaystyle S \ sol ({\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}} \ sağ) \ yaklaşık \ toplam _ {i = 1} ^ {m} \ sol [y_ {i} -f \left(x_{i},{\boldsymbol {\beta }}\sağ)-\mathbf {J} _{i}{\boldsymbol {\delta }}\sağ]^{2},}$

veya vektör gösteriminde,

${\ displaystyle {\ begin {align} S \ sol ({\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}} \ sağ) & \ yaklaşık \ sol \ | \ mathbf {y} - \ mathbf {f } \ left ({\ boldsymbol {\ beta}} \ right) - \ mathbf {J} {\ boldsymbol {\ delta}} \ right \ | ^ {2} \\ & = \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) - \ mathbf {J} {\ boldsymbol {\ delta}} \ right] ^ {\ mathrm {T}} \ left [\ mathbf { y} -\mathbf {f} \left({\boldsymbol {\beta }}\sağ)-\mathbf {J} {\boldsymbol {\delta }}\sağ]\\&=\left[\mathbf {y } -\mathbf {f} \left({\boldsymbol {\beta }}\sağ)\sağ]^{\mathrm {T} }\left[\mathbf {y} -\mathbf {f} \left({ \ boldsymbol {\ beta}} \ right) \ right] - \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm { T} }\mathbf {J} {\boldsymbol {\delta }}-\left(\mathbf {J} {\boldsymbol {\delta }}\sağ)^{\mathrm {T} }\left[\mathbf { y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] + {\ boldsymbol {\ delta}} ^ {\ mathrm {T}} \ mathbf {J} ^ {\ matematik {T} }\mathbf {J} {\boldsymbol {\delta }}\\&=\left[\mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm {T}} \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ kalın sembol {\ beta}} \ sağ) \ sağ] -2 \ sol [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ sağ) \ sağ] ^ {\ mathrm { T}} \ mathbf {J} {\ boldsymbol {\ delta}} + {\ boldsymbol {\ delta}} ^ {\ mathrm {T}} \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J } {\ boldsymbol {\ delta}}. \ end {hizalı}}}$

Türevini almak ile ilgili olarak ve sonucu sıfır ile ayar verir ${\ displaystyle S \ sol ({\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}} \ sağ)}$${\displaystyle {\boldsymbol {\delta }}}$

${\displaystyle \left(\mathbf {J} ^{\mathrm {T} }\mathbf {J} \sağ){\boldsymbol {\delta }}=\mathbf {J} ^{\mathrm {T} }\ sol[\mathbf {y} -\mathbf {f} \left({\boldsymbol {\beta }}\sağ)\sağ],}$

burada bir jakobiyen matrisi olan, inci satır eşittir ve ve vektörleri, birlikte -inci bileşen ve sırasıyla. için elde edilen yukarıdaki ifade Gauss-Newton yöntemine tabidir. Yukarıda tanımlandığı gibi Jacobian matrisi (genel olarak) bir kare matris değil, dikdörtgen bir matristir , burada parametre sayısı (vektörün boyutu ). Matris çarpımı gerekli kare matrisi verir ve sağ taraftaki matris-vektör çarpımı bir boyut vektörü verir . Sonuç, çözülebilecek bir dizi doğrusal denklemdir . ${\displaystyle \mathbf {J} }$${\görüntüleme stili ben}$${\ displaystyle \ mathbf {J} _ {i}}$${\displaystyle \mathbf {f} \sol({\boldsymbol {\beta }}\sağ)}$${\ displaystyle \ mathbf {y}}$${\görüntüleme stili ben}$${\ displaystyle f \ sol (x_ {i}, {\ boldsymbol {\ beta}} \ sağ)}$${\ displaystyle y_ {i}}$${\ displaystyle {\ boldsymbol {\ beta}}}$${\displaystyle m\times n}$${\görüntüleme stili n}$${\ displaystyle {\ boldsymbol {\ beta}}}$${\ displaystyle \ sol (\ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J} \ sağ)}$${\ displaystyle n \ kere n}$${\görüntüleme stili n}$${\görüntüleme stili n}$${\displaystyle {\boldsymbol {\delta }}}$

Levenberg'in katkısı, bu denklemi "sönümlü bir versiyon" ile değiştirmektir:

${\ displaystyle \ sol (\ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J} + \ lambda \ mathbf {I} \ sağ) {\ boldsymbol {\ delta}} = \ mathbf {J} ^ {\ mathrm {T}} \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ sağ) \ sağ],}$

Kimlik matrisi nerede , tahmin edilen parametre vektörüne artış olarak verilir . ${\ displaystyle \ mathbf {I}}$${\displaystyle {\boldsymbol {\delta }}}$${\ displaystyle {\ boldsymbol {\ beta}}}$

(Negatif olmayan) sönümleme faktörü her yinelemede ayarlanır. Eğer azalma hızlıysa, algoritmayı Gauss-Newton algoritmasına yaklaştırarak daha küçük bir değer kullanılabilir, oysa bir yineleme kalıntıda yetersiz azalma sağlıyorsa, gradyan-iniş yönüne bir adım daha yakınlaştırarak artırılabilir. Not bu gradyan arasında göre eşitler . Bu nedenle, büyük değerler için , adım yaklaşık olarak gradyanın tersi yönde atılacaktır. Hesaplanan adımın uzunluğu veya en son parametre vektöründen kareler toplamının azaltılması önceden tanımlanmış sınırların altına düşerse, yineleme durur ve son parametre vektörü çözüm olarak kabul edilir. ${\ displaystyle \ lambda}$${\ displaystyle S}$${\ displaystyle \ lambda}$${\ displaystyle S}$${\ displaystyle {\ boldsymbol {\ beta}}}$${\ displaystyle -2 \ sol (\ mathbf {J} ^ {\ mathrm {T}} \ sol [\ mathbf {y} - \ mathbf {f} \ sol ({\ boldsymbol {\ beta}} \ sağ) \ sağ] \ doğru) ^ {\ mathrm {T}}}$${\ displaystyle \ lambda}$${\displaystyle {\boldsymbol {\delta }}}$${\ displaystyle {\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}}}$${\ displaystyle {\ boldsymbol {\ beta}}}$

Levenberg'in algoritması, sönümleme faktörünün değeri büyükse, tersine çevirmenin hiç kullanılmaması dezavantajına sahiptir . Fletcher, degradenin her bir bileşenini eğriliğe göre ölçekleyebileceğimizi, böylece degradenin daha küçük olduğu yönlerde daha büyük hareket olmasını sağladı. Bu, küçük gradyan yönünde yavaş yakınsamayı önler. Bu nedenle, Fletcher 1971 tarihli makalesinde, doğrusal olmayan en küçük kareler için değiştirilmiş bir Marquardt alt yordamı , birim matrisini köşegen elemanlarından oluşan köşegen matrisle değiştirdi , böylece çözüm ölçeğini değişmez hale getirdi: ${\ displaystyle \ lambda}$${\displaystyle \mathbf {J} ^{\text{T}}\mathbf {J} +\lambda \mathbf {I} }$${\ displaystyle \ mathbf {I}}$${\displaystyle \mathbf {J} ^{\text{T}}\mathbf {J} }$

${\ displaystyle \ sol [\ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J} + \ lambda \ operatorname {diag} \ sol (\ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J} \ right) \ right] {\ boldsymbol {\ delta}} = \ mathbf {J} ^ {\ mathrm {T}} \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ kalın sembol {\ beta}} \ sağ) \ sağ].}$

Benzer bir sönümleme faktörü , doğrusal olmayan sorunları çözmek için kullanılan Tikhonov düzenlileştirmesinde ve ayrıca istatistikte bir tahmin tekniği olan sırt regresyonunda ortaya çıkar .

Sönümleme parametresi seçimi

Sönümleme parametresi için en iyi seçim için az çok çeşitli buluşsal argümanlar öne sürülmüştür . Bu seçimlerden bazılarının neden algoritmanın yerel yakınsamasını garanti ettiğini gösteren teorik argümanlar mevcuttur; bununla birlikte, bu seçimler, algoritmanın küresel yakınsamasını, özellikle optimuma yakın çok yavaş yakınsama olmak üzere en dik inişin istenmeyen özelliklerinden muzdarip hale getirebilir . ${\ displaystyle \ lambda}$

Herhangi bir seçimin mutlak değerleri, ilk problemin ne kadar iyi ölçeklendiğine bağlıdır. Marquardt bir değer ve bir faktörle başlamayı önerdi . Başlangıçta , başlangıç ​​noktasından bir adım sonra artık karelerin toplamını sönümleme faktörü ve ikinci olarak ile ayarlama ve hesaplama . Bunların her ikisi de başlangıç ​​noktasından daha kötü ise, bu durumda sönümleme, bazıları için yeni bir sönüm faktörüyle daha iyi bir nokta bulunana kadar ardışık çarpma ile artırılır . ${\ displaystyle \ lambda _ {0}}$${\displaystyle \nu >1}$${\displaystyle \lambda =\lambda _{0}}$${\ displaystyle S \ sol ({\ boldsymbol {\ beta}} \ sağ)}$${\displaystyle \lambda =\lambda _{0}}$${\ displaystyle \ lambda _ {0} / \ nu}$${\ displaystyle \ nu}$${\displaystyle \lambda _{0}\nu ^{k}}$${\görüntüleme stili k}$

Sönümleme faktörünün kullanılması, artık karede bir azalmaya neden olursa , bu yeni değer olarak alınır (ve bu sönümleme faktörü ile elde edilen yeni optimum konum alınır) ve işlem devam eder; kullanım daha kötü bir kalıntı ile sonuçlanmışsa , ancak kullanım daha iyi bir kalıntı ile sonuçlanmışsa, değiştirilmeden bırakılır ve sönüm faktörü olarak elde edilen değer olarak yeni optimum alınır . ${\ displaystyle \ lambda / \ nu}$${\ displaystyle \ lambda}$${\ displaystyle \ lambda / \ nu}$${\ displaystyle \ lambda}$${\ displaystyle \ lambda}$${\ displaystyle \ lambda}$

Gecikmeli tatmin olarak adlandırılan sönümleme parametresinin kontrolü için etkili bir strateji , parametrenin her yokuş yukarı adım için küçük bir miktar artırılması ve her yokuş aşağı adım için büyük miktarda azaltılmasıdır. Bu stratejinin arkasındaki fikir, optimizasyonun başlangıcında yokuş aşağı çok hızlı hareket etmekten kaçınmak, bu nedenle gelecekteki yinelemelerde mevcut adımları kısıtlamak ve dolayısıyla yakınsamayı yavaşlatmaktır. Çoğu durumda 2 kat artış ve 3 kat azalmanın etkili olduğu gösterilmiştir, büyük problemler için ise 1,5 kat artış ve faktör azalma ile daha uç değerler daha iyi çalışabilir. arasında 5.

jeodezik ivme

Levenberg – Marquardt adımını parametre uzayında bir jeodezik yol boyunca hız olarak yorumlarken, jeodezik boyunca ivmeyi açıklayan ikinci dereceden bir terim ekleyerek yöntemi iyileştirmek mümkündür.${\ displaystyle {\ boldsymbol {v}} _ {k}}$${\displaystyle {\boldsymbol {a}}_{k}}$

${\ displaystyle {\ boldsymbol {v}} _ {k} + {\ frac {1} {2}} {\ boldsymbol {a}} _ {k}}$

çözümü nerede${\displaystyle {\boldsymbol {a}}_{k}}$

${\ displaystyle {\ boldsymbol {J}} _ {k} {\ boldsymbol {a}} _ {k} = - f_ {vv}.}$

Bu jeodezik ivme terimi, yalnızca hızın yönü boyunca yönlü türevine bağlı olduğundan , tam ikinci dereceden türev matrisinin hesaplanmasını gerektirmez, hesaplama maliyeti açısından yalnızca küçük bir ek yük gerektirir. İkinci mertebeden türev oldukça karmaşık bir ifade olabileceğinden, onu sonlu bir fark yaklaşımıyla değiştirmek uygun olabilir.${\ displaystyle f_ {vv} = \ toplam _ {\ mu \ nu} v _ {\ mu} v _ {\ nu} \ kısmi _ {\ mu} \ kısmi _ {\ nu} f ({\ kalın sembol {x}} )}$${\ displaystyle {\ boldsymbol {v}}}$

${\ displaystyle {\ begin {align} f_ {vv} ^ {i} & \ yaklaşık {\ frac {f_ {i} ({\ boldsymbol {x}} + h {\ boldsymbol {\ delta}}) - 2f_ { i} ({\ boldsymbol {x}}) + f_ {i} ({\ boldsymbol {x}} - h {\ boldsymbol {\ delta}})} {h ^ {2}}} \\ & = {\ frac {2} {h}} \ left ({\ frac {f_ {i} ({\ boldsymbol {x}} + h {\ boldsymbol {\ delta}}) - f_ {i} ({\ kalın sembol {x} })}{h}}-{\boldsymbol {J}}_{i}{\boldsymbol {\delta }}\sağ)\end{hizalı}}}$

burada ve zaten bu yüzden hesaplamak için yalnızca bir ek fonksiyon değerlendirme gerektiren, algoritma ile hesaplanan edilmiştir . Sonlu fark adımının seçimi , algoritmanın kararlılığını etkileyebilir ve genel olarak 0.1 civarında bir değer genellikle mantıklıdır. ${\displaystyle f({\boldsymbol {x}})}$${\ displaystyle {\ boldsymbol {J}}}$${\ displaystyle f ({\ kalın sembol {x}} + h {\ kalın sembol {\ delta}})}$${\ displaystyle h}$

İvme, hıza zıt yönü gösterebileceğinden, sönümlemenin çok küçük olması durumunda yöntemin durmasını önlemek için, bir adımı kabul etmek için ivme üzerinde ek bir kriter eklenir.

${\ displaystyle {\ frac {2 \ sol \ | {\ boldsymbol {a}} _ {k} \ sağ \ |} {\ sol \ | {\ boldsymbol {v}} _ {k} \ sağ \ |}} \ leq \ alpha}$

burada genellikle 1'den küçük bir değere sabitlenir, daha zor problemler için daha küçük değerlere sahiptir. ${\görüntüleme stili \alfa }$

Bir jeodezik hızlandırma teriminin eklenmesi, yakınsama hızında önemli artışa izin verebilir ve özellikle algoritma, amaç fonksiyonunun peyzajındaki dar kanyonlarda hareket ederken, izin verilen adımların daha küçük ve ikinci dereceden dolayı daha yüksek doğrulukta olduğu durumlarda yararlıdır. terim önemli gelişmeler sağlar.

Misal

Kötü uyum

Daha uygun

En uygun

Bu örnekte , leasqr işlevi olarak GNU Octave'de uygulanan Levenberg–Marquardt algoritmasını kullanarak işlevi uydurmaya çalışıyoruz. Grafikleri kademeli iyi parametreleri için montaj göstermektedir , ilk eğri kullanılır. Yalnızca son grafikteki parametreler orijinale en yakın seçildiğinde, eğriler tam olarak uyuyor. Bu denklem, Levenberg – Marquardt algoritması için çok hassas başlangıç ​​koşullarına bir örnektir. Bu hassasiyetin bir nedeni, çoklu minimumların varlığıdır - fonksiyonun parametre değerinde minimum değerleri vardır ve . ${\ Displaystyle y = a \ çünkü \ sol (bX \ sağ) + b \ sin \ sol (aX \ sağ)}$${\ displaystyle a = 100}$${\görüntüleme stili b=102}$${\görüntüleme stili \çünkü \sol(\beta x\sağ)}$${\ displaystyle {\ hat {\ beta}}}$${\ displaystyle {\ hat {\ beta}} + 2n \ pi}$

Ayrıca bakınız

• Güven bölgesi
• Nelder-Mead yöntemi
• Doğrusal olmayan denklem sistemlerini çözmek için Levenberg-Marquardt algoritmasının varyantları da kullanılmıştır.

Referanslar

daha fazla okuma

Dış bağlantılar

• Algoritmanın ayrıntılı açıklaması Sayısal Tarifler C, Bölüm 15.5: Doğrusal olmayan modeller bölümünde bulunabilir.
• CT Kelley, Optimizasyon için Yinelemeli Yöntemler , Uygulamalı Matematikte SIAM Sınırları, no 18, 1999, ISBN  0-89871-433-8 . Çevrimiçi kopya
• SIAM haberlerinde algoritmanın tarihi
• Ananth Ranganathan tarafından bir öğretici
• K. Madsen, HB Nielsen, O. Tingleff, Doğrusal Olmayan En Küçük Kareler Problemleri için Yöntemler (doğrusal olmayan en küçük kareler öğreticisi; LM kodu: analitik Jacobian sekant )
• T. Strutz: Veri Uydurma ve Belirsizlik (Ağırlıklı en küçük kareler ve ötesine pratik bir giriş). 2. baskı, Springer Vieweg, 2016, ISBN  978-3-658-11455-8 .
• HP Gavin, Doğrusal olmayan en küçük kareler eğri uydurma problemleri için Levenberg-Marquardt yöntemi ( MATLAB uygulaması dahil)