Dereceli alçalma - Gradient descent

Dereceli alçalma bir birinci derece yinelemeli optimizasyon algoritma bulmak için yerel minimum türevlenebilir bir fonksiyon. Fikir, ters yönde tekrarlanan adımlar atmaktır. gradyan Geçerli noktadaki fonksiyonun (veya yaklaşık gradyan), çünkü bu en dik iniş yönüdür. Tersine, gradyan yönünde adım atmak bir yerel maksimum bu işlevin; prosedür daha sonra olarak bilinir gradyan tırmanışı.

Gradyan inişi genellikle Cauchy, bunu ilk kez 1847'de öneren,^[1] ancak doğrusal olmayan optimizasyon problemleri için yakınsama özellikleri ilk olarak Haskell Köri 1944'te.^[2]

Açıklama

Bir dizi gradyan iniş çizimi seviye setleri

Gradyan inişi şu gözlemlere dayanmaktadır: çok değişkenli işlev ${ displaystyle F ( mathbf {x})}$ dır-dir tanımlı ve ayırt edilebilir bir noktanın mahallesinde ${ displaystyle mathbf {a}}$, sonra ${ displaystyle F ( mathbf {x})}$ azalır en hızlı eğer biri buradan giderse ${ displaystyle mathbf {a}}$ negatif gradyan yönünde ${ displaystyle F}$ -de ${ displaystyle mathbf {a}, - nabla F ( mathbf {a})}$. Bunu takip eder, eğer

${ displaystyle mathbf {a} _ {n + 1} = mathbf {a} _ {n} - gamma nabla F ( mathbf {a} _ {n})}$

için ${ displaystyle gamma in mathbb {R} _ {+}}$ o zaman yeterince küçük ${ displaystyle F ( mathbf {a_ {n}}) geq F ( mathbf {a_ {n + 1}})}$. Başka bir deyişle, terim ${ displaystyle gamma nabla F ( mathbf {a})}$ -den çıkarılır ${ displaystyle mathbf {a}}$ çünkü eğime karşı, yerel minimuma doğru hareket etmek istiyoruz. Bu gözlem akılda tutularak, bir tahminle başlar ${ displaystyle mathbf {x} _ {0}}$ yerel minimum için ${ displaystyle F}$ve sırayı dikkate alır ${ displaystyle mathbf {x} _ {0}, mathbf {x} _ {1}, mathbf {x} _ {2}, ldots}$ öyle ki

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} - gamma _ {n} nabla F ( mathbf {x} _ {n}), n geq 0.}$

Biz var monoton sıra

${ displaystyle F ( mathbf {x} _ {0}) geq F ( mathbf {x} _ {1}) geq F ( mathbf {x} _ {2}) geq cdots,}$

Öyleyse umarım sıra ${ displaystyle ( mathbf {x} _ {n})}$ istenen yerel minimuma yakınsar. Değerinin adım boyutu ${ displaystyle gamma}$ her yinelemede değişmesine izin verilir. İşlevle ilgili belirli varsayımlarla ${ displaystyle F}$ (Örneğin, ${ displaystyle F}$ dışbükey ve ${ displaystyle nabla F}$ Lipschitz ) ve belirli seçimler ${ displaystyle gamma}$ (örneğin, bir satır arama tatmin eden Wolfe koşulları veya Barzilai – Borwein yöntemi^[3][4] aşağıdaki gibi gösterilmiştir),

${ displaystyle gamma _ {n} = { frac { sol | sol ( mathbf {x} _ {n} - mathbf {x} _ {n-1} sağ) ^ {T} sol [ nabla F ( mathbf {x} _ {n}) - nabla F ( mathbf {x} _ {n-1}) sağ] sağ |} { left | nabla F ( mathbf {x} _ {n}) - nabla F ( mathbf {x} _ {n-1}) sağ | ^ {2}}}}$

yakınsama minimum yerel düzeyde garanti edilebilir. Fonksiyon ne zaman ${ displaystyle F}$ dır-dir dışbükey, tüm yerel minimumlar aynı zamanda küresel minimumdur, bu nedenle bu durumda gradyan inişi küresel çözüme yaklaşabilir.

Bu süreç yandaki resimde gösterilmektedir. Buraya ${ displaystyle F}$ düzlemde tanımlandığı ve grafiğinin bir çanak şekil. Mavi eğriler kontur çizgileri yani değerinin bulunduğu bölgeler ${ displaystyle F}$ sabittir. Bir noktadan çıkan kırmızı ok, o noktadaki negatif gradyanın yönünü gösterir. Bir noktadaki (negatif) gradyan dikey o noktadan geçen kontur çizgisine. Bu gradyanı görüyoruz iniş bizi kasenin dibine, yani fonksiyonun değerinin geldiği noktaya götürür. ${ displaystyle F}$ minimumdur.

Gradyan inişini anlamak için bir analoji

Dağlarda sis

Gradyan inişinin arkasındaki temel sezgi, varsayımsal bir senaryo ile gösterilebilir. Bir kişi dağlarda mahsur kalmış ve aşağı inmeye çalışıyor (yani küresel minimumu bulmaya çalışıyor). Görüşün son derece düşük olduğu yoğun sis var. Bu nedenle, dağın aşağısındaki yol görünmez, bu nedenle minimum yolu bulmak için yerel bilgileri kullanmaları gerekir. Mevcut konumlarında tepenin dikliğine bakmayı ve ardından en dik inişle (yani yokuş aşağı) yönde ilerlemeyi içeren gradyan iniş yöntemini kullanabilirler. Dağın tepesini (yani maksimum) bulmaya çalışıyorlarsa, en dik çıkış yönünde (yani yokuş yukarı) ilerlerlerdi. Bu yöntemi kullanarak, sonunda dağın aşağısında yollarını bulurlar veya muhtemelen bir delikte sıkışırlar (yani yerel minimum veya Eyer noktası ), bir dağ gölü gibi. Bununla birlikte, tepenin dikliğinin basit bir gözlemle hemen aşikar olmadığını, aksine, kişinin o anda sahip olduğu, ölçmek için karmaşık bir alet gerektirdiğini de varsayalım. Enstrümanla tepenin dikliğini ölçmek biraz zaman alır, bu nedenle gün batımından önce dağdan aşağı inmek istiyorlarsa enstrümanı kullanımlarını en aza indirmelidirler. O halde zorluk, yoldan çıkmamak için tepenin dikliğini ölçmeleri gereken frekansı seçmektir.

Bu benzetmede, kişi algoritmayı temsil eder ve dağdan inen yol, algoritmanın keşfedeceği parametre ayarları sırasını temsil eder. Tepenin dikliği, eğim Bu noktada hata yüzeyinin Dikliği ölçmek için kullanılan alet farklılaşma (hata yüzeyinin eğimi, türev karesi alınmış hata fonksiyonunun bu noktada). Seyahat etmeyi seçtikleri yön, gradyan Bu noktada hata yüzeyinin Başka bir ölçüm yapmadan önce seyahat ettikleri süre, algoritmanın öğrenme hızıdır. Görmek Geri yayılım § Sınırlamalar Bu tür "tepeden aşağı inen" algoritmanın sınırlamaları hakkında bir tartışma için.

Örnekler

Gradyan inişinde aşağıdaki gibi patolojik fonksiyonlarla ilgili sorunlar vardır: Rosenbrock işlevi burada gösterilmektedir.

${ displaystyle f (x_ {1}, x_ {2}) = (1-x_ {1}) ^ {2} +100 (x_ {2} - {x_ {1}} ^ {2}) ^ {2 }.}$

Rosenbrock işlevi, minimumu içeren dar ve kavisli bir vadiye sahiptir. Vadinin dibi çok düz. Eğimli düz vadi nedeniyle optimizasyon, minimuma doğru küçük adım boyutları ile yavaşça zikzak çiziyor.

Yöntemin zikzak doğası, gradyan iniş yönteminin uygulandığı aşağıda da görülmektedir.

${ displaystyle F (x, y) = sin sol ({ frac {1} {2}} x ^ {2} - { frac {1} {4}} y ^ {2} +3 sağ ) cos left (2x + 1-e ^ {y} sağ).}$

Adım boyutunu ve iniş yönünü seçme

Bir adım boyutu kullandığından beri ${ displaystyle gamma}$ çok küçük olması yakınsamayı yavaşlatır ve ${ displaystyle gamma}$ çok büyük, sapmaya yol açar, iyi bir ${ displaystyle gamma}$ önemli bir pratik problemdir. Philip Wolfe pratikte "[alçalma] yönünün akıllıca seçimleri" nin kullanılmasını savundu.^[5] En dik iniş yönünden sapan bir yön kullanmak mantığa aykırı görünse de, fikir, daha küçük eğimin çok daha uzun bir mesafeden sürdürülerek telafi edilebileceğidir.

Bunu matematiksel olarak düşünmek için bir yön kullanalım ${ displaystyle mathbf {p} _ {n}}$ ve adım boyutu ${ displaystyle gamma _ {n}}$ ve daha genel güncellemeyi düşünün:

${ displaystyle mathbf {a} _ {n + 1} = mathbf {a} _ {n} - gamma _ {n} , mathbf {p} _ {n}}$.

İçin iyi ayarlar bulmak ${ displaystyle mathbf {p} _ {n}}$ ve ${ displaystyle gamma _ {n}}$ biraz düşünmeyi gerektirir. Öncelikle güncelleme yönünün yokuş aşağı bakmasını istiyoruz. Matematiksel olarak, izin verme ${ displaystyle theta _ {n}}$ arasındaki açıyı göstermek ${ displaystyle nabla F ( mathbf {a_ {n}})}$ ve ${ displaystyle mathbf {p} _ {n}}$, bunu gerektirir ${ displaystyle cos theta _ {n}> 0.}$ Daha fazlasını söylemek için, optimize ettiğimiz amaç işlevi hakkında daha fazla bilgiye ihtiyacımız var. Oldukça zayıf varsayım altında ${ displaystyle F}$ sürekli olarak farklılaştırılabilirse, şunu kanıtlayabiliriz:^[6]

${ displaystyle F ( mathbf {a} _ {n + 1}) leq F ( mathbf {a} _ {n}) - gamma _ {n} | nabla F ( mathbf {a} _ {n}) | _ {2} | mathbf {p} _ {n} | _ {2} left [ cos theta _ {n} - max _ {t in [0,1 ]} { frac { | nabla F ( mathbf {a} _ {n} -t gamma _ {n} mathbf {p} _ {n}) - nabla F ( mathbf {a} _ {n}) | _ {2}} { | nabla F ( mathbf {a} _ {n}) | _ {2}}} sağ]}$

(1)

Bu eşitsizlik, işlevden emin olabileceğimiz miktarın ${ displaystyle F}$ azalması, köşeli parantez içindeki iki terim arasındaki değiş tokuşa bağlıdır. Köşeli parantez içindeki ilk terim, iniş yönü ile negatif gradyan arasındaki açıyı ölçer. İkinci terim, eğimin iniş yönü boyunca ne kadar hızlı değiştiğini ölçer.

Prensipte eşitsizlik (1) üzerinde optimize edilebilir ${ displaystyle mathbf {p} _ {n}}$ ve ${ displaystyle gamma _ {n}}$ Optimal bir adım boyutu ve yönü seçmek için. Sorun, ikinci terimi köşeli parantez içinde değerlendirmenin, değerlendirmeyi gerektirmesidir. ${ displaystyle nabla F ( mathbf {a} _ {n} -t gamma _ {n} mathbf {p} _ {n})}$ve ekstra gradyan değerlendirmeleri genellikle pahalıdır ve istenmez. Bu sorunun etrafından dolaşmanın bazı yolları:

• Ayarlayarak akıllı bir iniş yönünün faydalarından vazgeçin ${ displaystyle mathbf {p} _ {n} = nabla F ( mathbf {a_ {n}})}$, ve kullan satır arama uygun bir adım boyutu bulmak için ${ displaystyle gamma _ {n}}$örneğin, tatmin edici Wolfe koşulları.
• Varsayalım ki ${ displaystyle F}$ iki kez türevlenebilir, Hessian'ı kullanın ${ displaystyle nabla ^ {2} F}$ tahmin ${ displaystyle | nabla F ( mathbf {a} _ {n} -t gamma _ {n} mathbf {p} _ {n}) - nabla F ( mathbf {a} _ {n} ) | _ {2} yaklaşık | t gamma _ {n} nabla ^ {2} F ( mathbf {a} _ {n}) mathbf {p} _ {n} |.}$Sonra seçin ${ displaystyle mathbf {p} _ {n}}$ ve ${ displaystyle gamma _ {n}}$ eşitsizliği optimize ederek (1).
• Varsayalım ki ${ displaystyle nabla F}$ dır-dir Lipschitz, Lipschitz sabitini kullanın ${ displaystyle L}$ bağlanmak ${ displaystyle | nabla F ( mathbf {a} _ {n} -t gamma _ {n} mathbf {p} _ {n}) - nabla F ( mathbf {a} _ {n} ) | _ {2} leq Lt gamma _ {n} | mathbf {p} _ {n} |.}$ Sonra seçin ${ displaystyle mathbf {p} _ {n}}$ ve ${ displaystyle gamma _ {n}}$ eşitsizliği optimize ederek (1).
• Özel bir model oluşturun ${ displaystyle max _ {t in [0,1]} { frac { | nabla F ( mathbf {a} _ {n} -t gamma _ {n} mathbf {p} _ { n}) - nabla F ( mathbf {a} _ {n}) | _ {2}} { | nabla F ( mathbf {a} _ {n}) | _ {2}}} }$ için ${ displaystyle F}$. Sonra seçin ${ displaystyle mathbf {p} _ {n}}$ ve ${ displaystyle gamma _ {n}}$ eşitsizliği optimize ederek (1).
• İşleve ilişkin daha güçlü varsayımlar altında ${ displaystyle F}$ gibi dışbükeylik, Daha gelişmiş teknikler belki mümkün.

Genellikle yukarıdaki tariflerden birini takip ederek, yakınsama minimum yerel düzeyde garanti edilebilir. Fonksiyon ne zaman ${ displaystyle F}$ dır-dir dışbükey, tüm yerel minimumlar aynı zamanda küresel minimumdur, bu nedenle bu durumda gradyan inişi küresel çözüme yakınlaşabilir.

Doğrusal bir sistemin çözümü

En dik iniş algoritması Wiener filtresi.^[7]

Gradyan inişi, ikinci dereceden bir minimizasyon problemi olarak yeniden formüle edilmiş bir doğrusal denklem sistemini çözmek için kullanılabilir, örn. doğrusal en küçük kareler. Çözümü

${ displaystyle A mathbf {x} - mathbf {b} = 0}$

Doğrusal en küçük kareler anlamında işlevi küçültmek olarak tanımlanır

${ displaystyle F ( mathbf {x}) = sol | A mathbf {x} - mathbf {b} sağ | ^ {2}.}$

Gerçek için geleneksel doğrusal en küçük karelerde ${ displaystyle A}$ ve ${ displaystyle mathbf {b}}$ Öklid normu kullanılır, bu durumda

${ displaystyle nabla F ( mathbf {x}) = 2A ^ {T} (A mathbf {x} - mathbf {b})}$

Bu durumda, satır arama minimizasyon, yerel olarak en uygun adım boyutunu bulma ${ displaystyle gamma}$ her yinelemede, analitik olarak gerçekleştirilebilir ve yerel olarak optimum için açık formüller ${ displaystyle gamma}$ bilinmektedir.^[8]

Algoritma, doğrusal denklemleri çözmek için nadiren kullanılır. eşlenik gradyan yöntemi en popüler alternatiflerden biri. Gradyan iniş yinelemelerinin sayısı genellikle spektral ile orantılıdır. durum numarası ${ displaystyle kappa (A)}$ sistem matrisinin ${ displaystyle A}$ (maksimumun minimuma oranı özdeğerler nın-nin ${ displaystyle A ^ {T} A}$)yakınsama sırasında eşlenik gradyan yöntemi tipik olarak durum numarasının bir karekökü ile belirlenir, yani çok daha hızlıdır. Her iki yöntem de fayda sağlayabilir ön koşullandırma, gradyan inişinin ön koşullandırıcı üzerinde daha az varsayım gerektirebileceği durumlarda.^[9]

Doğrusal olmayan bir sistemin çözümü

Gradyan inişi, bir sistemi çözmek için de kullanılabilir. doğrusal olmayan denklemler. Aşağıda, üç bilinmeyen değişkeni çözmek için gradyan inişinin nasıl kullanılacağını gösteren bir örnek bulunmaktadır: x₁, x₂, ve x₃. Bu örnek, gradyan inişinin bir yinelemesini göstermektedir.

Doğrusal olmayan denklem sistemini düşünün

${ displaystyle { begin {case} 3x_ {1} - cos (x_ {2} x_ {3}) - { tfrac {3} {2}} = 0 4x_ {1} ^ {2} - 625x_ {2} ^ {2} + 2x_ {2} -1 = 0 exp (-x_ {1} x_ {2}) + 20x_ {3} + { tfrac {10 pi -3} {3 }} = 0 end {vakalar}}}$

İlişkili işlevi tanıtalım

${ displaystyle G ( mathbf {x}) = { begin {bmatrix} 3x_ {1} - cos (x_ {2} x_ {3}) - { tfrac {3} {2}} 4x_ { 1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 exp (-x_ {1} x_ {2}) + 20x_ {3} + { tfrac {10 pi -3} {3}} son {bmatrix}},}$

nerede

${ displaystyle mathbf {x} = { begin {bmatrix} x_ {1} x_ {2} x_ {3} end {bmatrix}}.}$

Şimdi amaç işlevi tanımlanabilir

${ displaystyle F ( mathbf {x}) = { frac {1} {2}} G ^ { mathrm {T}} ( mathbf {x}) G ( mathbf {x}) = { frac {1} {2}} sol [ sol (3x_ {1} - cos (x_ {2} x_ {3}) - { frac {3} {2}} sağ) ^ {2} + sol (4x_ {1} ^ {2} -625x_ {2} ^ {2} + 2x_ {2} -1 sağ) ^ {2} + left ( exp (-x_ {1} x_ {2}) + 20x_ {3} + { frac {10 pi -3} {3}} sağ) ^ {2} sağ],}$

en aza indirmeye çalışacağız. İlk tahmin olarak kullanalım

${ displaystyle mathbf {x} ^ {(0)} = mathbf {0} = { begin {bmatrix} 0 0 0 end {bmatrix}}.}$

Biz biliyoruz ki

${ displaystyle mathbf {x} ^ {(1)} = mathbf {0} - gamma _ {0} nabla F ( mathbf {0}) = mathbf {0} - gamma _ {0} J_ {G} ( mathbf {0}) ^ { mathrm {T}} G ​​( mathbf {0}),}$

nerede Jacobian matrisi ${ displaystyle J_ {G}}$ tarafından verilir

${ displaystyle J_ {G} ( mathbf {x}) = { başla {bmatrix} 3 & sin (x_ {2} x_ {3}) x_ {3} ve sin (x_ {2} x_ {3} ) x_ {2} 8x_ {1} & - 1250x_ {2} + 2 & 0 - x_ {2} exp {(-x_ {1} x_ {2})} & - x_ {1} exp ( -x_ {1} x_ {2}) & 20 end {bmatrix}}.}$

Hesaplıyoruz:

${ displaystyle J_ {G} ( mathbf {0}) = { begin {bmatrix} 3 & 0 & 0 0 & 2 & 0 0 & 0 & 20 end {bmatrix}}, qquad G ( mathbf {0}) = { begin { bmatrix} -2.5 - 1 10.472 end {bmatrix}}.}$

Böylece

${ displaystyle mathbf {x} ^ {(1)} = mathbf {0} - gamma _ {0} { begin {bmatrix} -7.5 - 2 209.44 end {bmatrix}},}$

ve

${ displaystyle F ( mathbf {0}) = 0,5 sol ((- 2,5) ^ {2} + (- 1) ^ {2} + (10,472) ^ {2} sağ) = 58,456.}$

Bu örneğe uygulanan gradyan inişinin ilk 83 yinelemesini gösteren bir animasyon. Yüzeyler izo yüzeyler nın-nin ${ displaystyle F ( mathbf {x} ^ {(n)})}$ mevcut tahminle ${ displaystyle mathbf {x} ^ {(n)}}$ve oklar iniş yönünü gösterir. Küçük ve sabit adım boyutu nedeniyle yakınsama yavaştır.

Şimdi uygun ${ displaystyle gamma _ {0}}$ öyle bulunmalı ki

${ displaystyle F sol ( mathbf {x} ^ {(1)} sağ) leq F sol ( mathbf {x} ^ {(0)} sağ) = F ( mathbf {0}) .}$

Bu, çeşitli satır arama algoritmalar. Bir de basitçe tahmin edebilir ${ displaystyle gamma _ {0} = 0,001,}$ hangi verir

${ displaystyle mathbf {x} ^ {(1)} = { begin {bmatrix} 0.0075 0.002 - 0.20944 end {bmatrix}}.}$

Amaç fonksiyonunu bu değerde değerlendirmek,

${ displaystyle F sol ( mathbf {x} ^ {(1)} sağ) = 0,5 sol ((- 2,48) ^ {2} + (- 1,00) ^ {2} + (6,28) ^ {2 } sağ) = 23.306.}$

Düşüş ${ displaystyle F ( mathbf {0}) = 58.456}$ sonraki adımın değerine

${ displaystyle F sol ( mathbf {x} ^ {(1)} sağ) = 23.306}$

amaç işlevinde önemli bir azalmadır. Diğer adımlar, sisteme yaklaşık bir çözüm bulunana kadar değerini daha da düşürür.

Yorumlar

Gradyan inişi, sonsuz boyutlu olanlarda bile, herhangi bir sayıda boyuttaki boşluklarda çalışır. İkinci durumda, arama alanı tipik olarak bir işlev alanı ve biri hesaplanır Fréchet türevi alçalma yönünü belirlemek için küçültülecek işlevin.^[10]

Bu gradyan inişi herhangi bir sayıda boyutta (en azından sonlu sayı) çalışır, bunun bir sonucu olarak görülebilir. Cauchy-Schwarz eşitsizliği. Bu makale, herhangi bir boyuttaki iki vektörün iç (nokta) ürününün büyüklüğünün eş doğrusal olduklarında maksimize edildiğini kanıtlıyor. Gradyan inişi durumunda, bu, bağımsız değişken ayarlamalarının vektörünün, kısmi türevlerin gradyan vektörü ile orantılı olduğu durumdur.

Gradyan inişi, yerel bir minimumun gerekli bir değerle hesaplanması için birçok yineleme alabilir. doğruluk, Eğer eğrilik farklı yönlerde verilen işlev için çok farklıdır. Bu tür işlevler için, ön koşullandırma gibi işlev düzeyi setlerini şekillendirmek için uzayın geometrisini değiştiren eşmerkezli daireler, yavaş yakınsamayı iyileştirir. Bununla birlikte, ön koşullandırmanın oluşturulması ve uygulanması hesaplama açısından pahalı olabilir.

Gradyan inişi, bir satır arama, yerel olarak en uygun adım boyutunu bulma ${ displaystyle gamma}$ her yinelemede. Hat araması yapmak zaman alıcı olabilir. Tersine, sabit bir küçük ${ displaystyle gamma}$ zayıf yakınsama sağlayabilir.

Dayalı yöntemler Newton yöntemi ve tersine çevirme Hessian kullanma eşlenik gradyan teknikler daha iyi alternatifler olabilir.^[11][12] Genel olarak, bu tür yöntemler daha az sayıda yinelemede birleşir, ancak her yinelemenin maliyeti daha yüksektir. Bir örnek, BFGS yöntemi Bu, her adımda gradyan vektörünün "daha iyi" bir yöne gitmek için çarpıldığı bir matrisin hesaplanmasından ve daha karmaşık bir satır arama algoritması, "en iyi" değerini bulmak için ${ displaystyle gama.}$ Bilgisayar belleği sorunlarının baskın olduğu son derece büyük sorunlar için, sınırlı bellek yöntemi gibi L-BFGS BFGS veya en dik iniş yerine kullanılmalıdır.

Gradyan inişi uygulama olarak görülebilir Euler yöntemi çözmek için adi diferansiyel denklemler ${ Displaystyle x '(t) = - nabla f (x (t))}$ bir gradyan akışı. Buna karşılık, bu denklem optimal bir kontrolör olarak türetilebilir^[13] kontrol sistemi için ${ displaystyle x '(t) = u (t)}$ ile ${ displaystyle u (t)}$ geri bildirim formunda verilmiştir ${ Displaystyle u (t) = - nabla f (x (t))}$.

Uzantılar

Gradyan inişi işlemek için uzatılabilir kısıtlamalar ekleyerek projeksiyon kısıtlamalar üzerine. Bu yöntem, yalnızca projeksiyon bir bilgisayarda verimli bir şekilde hesaplanabildiğinde uygulanabilir. Uygun varsayımlar altında bu yöntem birleşir. Bu yöntem, belirli bir durumdur. ileri-geri algoritması monoton kapanımlar için (aşağıdakileri içerir dışbükey programlama ve varyasyonel eşitsizlikler ).^[14]

Hızlı gradyan yöntemleri

Gradyan inişinin bir başka uzantısı da Yurii Nesterov 1983'ten itibaren^[15] ve sonradan genelleştirilmiştir. Dışbükey problemler için daha hızlı yakınsama sağlayan basit bir algoritma değişikliği sağlar. Kısıtlanmamış pürüzsüz problemler için yönteme Hızlı Gradyan Yöntemi (FGM) veya Hızlandırılmış Gradyan Yöntemi (AGM). Spesifik olarak, türevlenebilir fonksiyon ${ displaystyle F}$ dışbükey ve ${ displaystyle nabla F}$ dır-dir Lipschitz ve bunun varsayılmadığı ${ displaystyle F}$ dır-dir kuvvetli dışbükey, ardından her adımda oluşturulan amaç değerindeki hata ${ displaystyle k}$ gradyan iniş yöntemi ile ile sınırlı ${ textstyle { mathcal {O}} sol ({ tfrac {1} {k}} sağ)}$. Nesterov hızlandırma tekniğini kullanarak hata şu anda azalır ${ textstyle { mathcal {O}} sol ({ tfrac {1} {k ^ {2}}} sağ)}$.^[16] Oranın ${ displaystyle { mathcal {O}} sol ({k ^ {- 2}} sağ)}$ azalması için maliyet fonksiyonu birinci dereceden optimizasyon yöntemleri için idealdir. Bununla birlikte, sabit faktörü azaltarak algoritmayı geliştirme fırsatı vardır. optimize edilmiş gradyan yöntemi (OGM)^[17] bu sabiti iki kat azaltır ve büyük ölçekli problemler için en uygun birinci dereceden yöntemdir.^[18]

Kısıtlı veya pürüzsüz olmayan sorunlar için Nesterov'un FGM'sine hızlı proksimal gradyan yöntemi (FPGM), bir ivme proksimal gradyan yöntemi.

İtme

Yerel minimumda takılma riskini azaltan ve sürecin aksi takdirde yoğun şekilde zikzak yapacağı durumlarda yakınsamayı önemli ölçüde hızlandıran bir başka uzantı da, momentum yöntemi"Konservatif bir kuvvet alanında viskoz bir ortamda hareket eden Newton parçacıklarının kütlesine" benzer şekilde bir momentum terimi kullanan.^[19] Bu yöntem genellikle bir uzantı olarak kullanılır. geri yayılım eğitmek için kullanılan algoritmalar yapay sinir ağları.^[20][21]

Ayrıca bakınız

Referanslar

daha fazla okuma

• Boyd, Stephen; Vandenberghe, Lieven (2004). "Kısıtlamasız Minimizasyon" (PDF). Dışbükey Optimizasyon. New York: Cambridge University Press. s. 457–520. ISBN  0-521-83378-7.
• Chong, Edwin K. P .; Şak, Stanislaw H. (2013). "Gradyan Yöntemleri". Optimizasyona Giriş (Dördüncü baskı). Hoboken: Wiley. s. 131–160. ISBN  978-1-118-27901-4.
• Himmelblau, David M. (1972). "Türevleri Kullanan Kısıtlamasız Minimizasyon Prosedürleri". Uygulamalı Doğrusal Olmayan Programlama. New York: McGraw-Hill. s. 63–132. ISBN  0-07-028921-2.

Dış bağlantılar

• Doğrusal regresyon için C ++, Boost, Ublas'ta gradyan inişini kullanma
• Khan Academy videoları dizisi gradyan tırmanışını tartışıyor
• Derin sinir ağı bağlamında çevrimiçi kitap öğretimi gradyan inişi
• "Gradyan İniş, Sinir Ağları Nasıl Öğrenir?". 3 Mavi 1 Kahverengi. 16 Ekim 2017 - üzerinden Youtube.