Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно (англ. Broyden–Fletcher–Goldfarb–Shanno (BFGS)) - ітеративний метод числової оптимізації, призначений для знаходження локального максимуму / мінімуму нелінійної функції без обмежень (є спірними слова "без обмежень", див. примітка).
Даний метод є одним з найрозповсюдженіших серед класу квазіньютонівських методів. У квазіньютонівських методах гессіан функції не обчислюється безпосередньо, а визначається приблизно, на основі дій зроблених до цього з матрицею Гессіана за допомогою градієнтної оцінки. Вектор градієнта функції помилки вираховується за допомогою звичайної процедури зворотнього розповсюдження помилки.
Примітка: Метод Бройдена - Флетчера - Гольдфарба - Шанно не дає повного сходження та його рішення пошуку погрішності не вираховує до кінця погрішність в реальності часу, як наслідок в метод необхідно додавати нові складові для визначення збільшеності погрішності в часі, так як сама постановка задачі не має повноти визначення в алгоритмі (сама задача поставлена локально). Метод не вирішує визначення погрішності, необхідно метод розширити новими змінними для рішення розвитку сходження методу. Тобто: Погрішність повинна стати не врахуванням помилки для визначення поточного результату, погрішність методу повинна стати функцією зміни результату в залежності від зміни часу.
Детальна інформація
Матриця Гессіана (або Зворотній гессіан) - - це матриця розміру n × n (де n - довжина вектора градієнта g).
Значення обчислюються на кожному кроці алгоритму наступним чином.
(1)
де
- це зміна градієнту,
- зміна ваг
Також існують модифікації даного методу. Наприклад алгоритм з обмеженим використанням пам'яті (L-BFGS), який призначений для рішення нелінійних задач з великою кількістю невідомих (зазвичай більше 1000). Або ж модифікація з обмеженим використанням пам'яті в багатовимірному кубі (L-BFGS-B).
Даний метод знаходить мінімум будь-якої подвійно диференційованої безперервно-випуклої функції. Метод Ньютона та методи BFGS не гарантують сходження, якщо функція не має квадратичного розкладу Тейлора близького до оптимального. Проте, BFGS довели свою ефективність навіть для негладких оптимізацій.
Алгоритм методу
Алгоритм складається з наступної послідовності кроків :
- Ініціалізуємо вагові коефіцієнти (випадковими малими значеннями) і встановимо початкове значення наближення зворотнього гессіана.
- Обчислимо значення градієнту g.
- Виконаємо корекцію значень вагових коефіцієнтів (; ; де - параметр швидкості навчання)
- Зберігаємо старе значення градієнту () та обчислюємо нове значення () і зміну градієнту ().
- Обчислимо значення зворотнього гессіана за формулою 1.
- Обчислимо зміну вагових коефіцієнтів () і виконаємо корекцію параметрів ()
- Обчислимо похибку ()
- Якщо отримане значення похибки менше, ніж задана точність (), то алгоритм зупиняється.
- Якщо точність не досягнута, то повторюємо алгоритм з 4 кроку.
Програмна реалізація
Реалізація мовою С у рамках проекту GNU Scientific Library (детальніше [ 8 грудня 2017 у Wayback Machine.]).
Високоточна версія алгоритму мовою С++ - посилання [ 23 серпня 2017 у Wayback Machine.].
Реалізація алгоритму BFGS та схожих алгоритмів (L-BFGS, L-BFGS-B, CG, метод Ньютона) мовою С++ - посилання [ 11 липня 2017 у Wayback Machine.].
Алгоритм реалізований у бібліотеці SciPy (детальніше [ 29 жовтня 2020 у Wayback Machine.]) мовою Python.
Реалізація мовою R - посилання [ 4 травня 2020 у Wayback Machine.].
Функція з пакету [en] мовою Matlab - посилання.
Посилання
Ця стаття не містить . (листопад 2017) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Brojdena Fletchera Goldfarba Shanno angl Broyden Fletcher Goldfarb Shanno BFGS iterativnij metod chislovoyi optimizaciyi priznachenij dlya znahodzhennya lokalnogo maksimumu minimumu nelinijnoyi funkciyi bez obmezhen ye spirnimi slova bez obmezhen div primitka Danij metod ye odnim z najrozpovsyudzhenishih sered klasu kvazinyutonivskih metodiv U kvazinyutonivskih metodah gessian funkciyi ne obchislyuyetsya bezposeredno a viznachayetsya priblizno na osnovi dij zroblenih do cogo z matriceyu Gessiana za dopomogoyu gradiyentnoyi ocinki Vektor gradiyenta funkciyi pomilki virahovuyetsya za dopomogoyu zvichajnoyi proceduri zvorotnogo rozpovsyudzhennya pomilki Primitka Metod Brojdena Fletchera Goldfarba Shanno ne daye povnogo shodzhennya ta jogo rishennya poshuku pogrishnosti ne virahovuye do kincya pogrishnist v realnosti chasu yak naslidok v metod neobhidno dodavati novi skladovi dlya viznachennya zbilshenosti pogrishnosti v chasi tak yak sama postanovka zadachi ne maye povnoti viznachennya v algoritmi sama zadacha postavlena lokalno Metod ne virishuye viznachennya pogrishnosti neobhidno metod rozshiriti novimi zminnimi dlya rishennya rozvitku shodzhennya metodu Tobto Pogrishnist povinna stati ne vrahuvannyam pomilki dlya viznachennya potochnogo rezultatu pogrishnist metodu povinna stati funkciyeyu zmini rezultatu v zalezhnosti vid zmini chasu Detalna informaciyaMatricya Gessiana abo Zvorotnij gessian V H 1 displaystyle V approx H 1 ce matricya rozmiru n n de n dovzhina vektora gradiyenta g Znachennya V displaystyle V obchislyuyutsya na kozhnomu kroci algoritmu nastupnim chinom V0 1 displaystyle V 0 1 Vk 1 Vk Vk s sT VksT Vk s r rTsT s displaystyle V k 1 V k frac V k centerdot s centerdot s T centerdot V k s T centerdot V k centerdot s frac r centerdot r T s T centerdot s 1 de r gk gk gk 1 displaystyle r vartriangle g k g k g k 1 ce zmina gradiyentu s Wk Wk Wk 1 displaystyle s vartriangle W k W k W k 1 zmina vag Takozh isnuyut modifikaciyi danogo metodu Napriklad algoritm z obmezhenim vikoristannyam pam yati L BFGS yakij priznachenij dlya rishennya nelinijnih zadach z velikoyu kilkistyu nevidomih zazvichaj bilshe 1000 Abo zh modifikaciya z obmezhenim vikoristannyam pam yati v bagatovimirnomu kubi L BFGS B Danij metod znahodit minimum bud yakoyi podvijno diferencijovanoyi bezperervno vipukloyi funkciyi Metod Nyutona ta metodi BFGS ne garantuyut shodzhennya yaksho funkciya ne maye kvadratichnogo rozkladu Tejlora blizkogo do optimalnogo Prote BFGS doveli svoyu efektivnist navit dlya negladkih optimizacij Algoritm metoduAlgoritm skladayetsya z nastupnoyi poslidovnosti krokiv Inicializuyemo vagovi koeficiyenti vipadkovimi malimi znachennyami i vstanovimo pochatkove znachennya nablizhennya zvorotnogo gessiana Obchislimo znachennya gradiyentu g Vikonayemo korekciyu znachen vagovih koeficiyentiv W g t displaystyle vartriangle W g centerdot tau Wk 1 Wk W displaystyle W k 1 W k vartriangle W de t displaystyle tau parametr shvidkosti navchannya Zberigayemo stare znachennya gradiyentu gold g displaystyle g old g ta obchislyuyemo nove znachennya g g W displaystyle g g W i zminu gradiyentu g g gold displaystyle vartriangle g g g old Obchislimo znachennya zvorotnogo gessiana V g W displaystyle V vartriangle g vartriangle W za formuloyu 1 Obchislimo zminu vagovih koeficiyentiv W V g displaystyle vartriangle W V centerdot g i vikonayemo korekciyu parametriv W W W displaystyle W W vartriangle W Obchislimo pohibku E W displaystyle E W Yaksho otrimane znachennya pohibki menshe nizh zadana tochnist E W lt e displaystyle E W lt varepsilon to algoritm zupinyayetsya Yaksho tochnist ne dosyagnuta to povtoryuyemo algoritm z 4 kroku Programna realizaciyaRealizaciya movoyu S u ramkah proektu GNU Scientific Library detalnishe 8 grudnya 2017 u Wayback Machine Visokotochna versiya algoritmu movoyu S posilannya 23 serpnya 2017 u Wayback Machine Realizaciya algoritmu BFGS ta shozhih algoritmiv L BFGS L BFGS B CG metod Nyutona movoyu S posilannya 11 lipnya 2017 u Wayback Machine Algoritm realizovanij u biblioteci SciPy detalnishe 29 zhovtnya 2020 u Wayback Machine movoyu Python Realizaciya movoyu R posilannya 4 travnya 2020 u Wayback Machine Funkciya z paketu en movoyu Matlab posilannya PosilannyaCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno listopad 2017