|
Kvazinyuton usullari. Bfgs, l-bfgs
|
| bet | 9/11 | | Sana | 14.05.2024 | | Hajmi | 345,07 Kb. | | #232474 |
Bog'liq GRADIENT TUSHISHKvazinyuton usullari. Bfgs, l-bfgs
Yuqorida ko‘rib o‘tilgan metodlardan tashqari, maqsadli xato funktsiyasining ikkinchi xususiy hosilalarini hisoblash asosida ikkinchi darajali usullar guruhi ham mavjud. Bunday usullar ancha aniq va tezroq yaqinlashishga ega, ammo ularni amalga oshirish murakkab va katta xotira xarajatlarini talab qiladi. Biz quyida Kvazinyuton usullari sinfini ko‘rib chiqamiz, unda vazn koeffitsientlarining yangilanishi xatolarning maqsadli funktsiyasining Gessian bahosini hisoblash orqali amalga oshiriladi, shu bilan birga ular shaklan birinchi darajali usullar bo‘lib qoladilar, chunki ular ikkinchi xususiy hosilalar matritsasini to‘g‘ridan-to‘g‘ri hisoblash va teskari aylantirish hosil qilmaydi.
Broyden-Fletcher-gol-dfarba-Shanno algoritmi (BFGS, [18])
Klassik BFGS algoritmining to‘liq shaklini ko‘rib chiqamiz. Algoritm maqsadli funktsiyaning teskari Hessian Hn bahosini yangilaydi, ηN parametri bir o‘lchovli qidirish protsedurasi yordamida aniqlanadi. BFGS algoritmining murakkabligi bahosi O(n2) tashkil etadi.
Klassik BFGS usuli algoritmi:
1-qadam. N := 0 ; 2-qadam. H0 = I
qadam. ∇E(wN) > ε bo‘lganda,
1. pN= −HN∇E(wN)
qadam. wN – echim
Broyden – Fletcher –Goldfarb – Shanno cheklangan xotira algoritmi (L-BFGS [19])
Ushbu algoritm O(n2 ) murakkablikni qo‘llash mumkin bo‘lmagan hollarda, katta ma’lumotlar ob'ektlarida optimallashtirish muammolarini hal qilish uchun maxsus ishlab chiqilgan BFGS algoritmining modifikatsiyasidir. L-BFGS uchun teskari gessianni baholash faqat so‘nggi m iteratsiyalari ma’lumotlari asosida amalga oshiriladi. Ushbu usulda kvazinyuton yo‘nalishi bo‘yicha harakat matritsalardan foydalanmasdan, s va y vektorlarining m oxirgi vektorlarini o‘z ichiga olgan halqa buferini hosil qilish orqali amalga oshiriladi.
Ushbu usulni amalga oshirish uchun yuqoridagi algoritmini quyidagicha o‘zgartirish kerak:
- 2 va 3.6-3.8-bosqichlarni chiqarib tashlash;
-3.1-bosqichni L-BFGS yo‘nalishini o‘zgartirish algoritmi bilan almashtirish.
Ushbu almashtirishlar natijasida, algoritmning murakkabligi O(n2 ) dan O(m⋅n) gacha kamayadi. L-BFGS usuli yo‘nalishlarini o‘zgartirish algoritmi:
Aytaylik ∀i =1, 2,..., min(t,m), bo‘lsin, sN-i , yN-i – parametrlar BFGS olinsin.
uchun:
3. N>0 bo‘lsa,
4. i = min(t, m),..., 2,1 uchun
|
| |
