Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно

Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно (англ. Broyden–Fletcher–Goldfarb–Shanno (BFGS)) - ітеративний метод числової оптимізації, призначений для знаходження локального максимуму / мінімуму нелінійної функції без обмежень (є спірними слова "без обмежень", див. примітка).

Даний метод є одним з найрозповсюдженіших серед класу квазіньютонівських методів. У квазіньютонівських методах гессіан функції не обчислюється безпосередньо, а визначається приблизно, на основі дій зроблених до цього з матрицею Гессіана за допомогою градієнтної оцінки. Вектор градієнта функції помилки вираховується за допомогою звичайної процедури зворотнього розповсюдження помилки.

Примітка: Метод Бройдена - Флетчера - Гольдфарба - Шанно не дає повного сходження та його рішення пошуку погрішності не вираховує до кінця погрішність в реальності часу, як наслідок в метод необхідно додавати нові складові для визначення збільшеності погрішності в часі, так як сама постановка задачі не має повноти визначення в алгоритмі (сама задача поставлена локально). Метод не вирішує визначення погрішності, необхідно метод розширити новими змінними для рішення розвитку сходження методу. Тобто: Погрішність повинна стати не врахуванням помилки для визначення поточного результату, погрішність методу повинна стати функцією зміни результату в залежності від зміни часу.

Детальна інформація

Матриця Гессіана (або Зворотній гессіан) - $V\approx H^{-1}$ - це матриця розміру n × n (де n - довжина вектора градієнта g).

Значення $V$ обчислюються на кожному кроці алгоритму наступним чином.

$V_{0}=1$

$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)

де

$r=\vartriangle g_{k}=g_{k}-g_{k-1}$ - це зміна градієнту,

$s=\vartriangle W_{k}=W_{k}-W_{k-1}$ - зміна ваг

Також існують модифікації даного методу. Наприклад алгоритм з обмеженим використанням пам'яті (L-BFGS), який призначений для рішення нелінійних задач з великою кількістю невідомих (зазвичай більше 1000). Або ж модифікація з обмеженим використанням пам'яті в багатовимірному кубі (L-BFGS-B).

Даний метод знаходить мінімум будь-якої подвійно диференційованої безперервно-випуклої функції. Метод Ньютона та методи BFGS не гарантують сходження, якщо функція не має квадратичного розкладу Тейлора близького до оптимального. Проте, BFGS довели свою ефективність навіть для негладких оптимізацій.

Алгоритм методу

Алгоритм складається з наступної послідовності кроків :

Ініціалізуємо вагові коефіцієнти (випадковими малими значеннями) і встановимо початкове значення наближення зворотнього гессіана.
Обчислимо значення градієнту g.
Виконаємо корекцію значень вагових коефіцієнтів ( $\vartriangle W=g\centerdot \tau$ ; $W_{k+1}=W_{k}-\vartriangle W$ ; де - $\tau$ параметр швидкості навчання)
Зберігаємо старе значення градієнту ( $g_{old}=g$ ) та обчислюємо нове значення ( $g=g(W)$ ) і зміну градієнту ( $\vartriangle g=g-g_{old}$ ).
Обчислимо значення зворотнього гессіана $V(\vartriangle g,\vartriangle W)$ за формулою 1.
Обчислимо зміну вагових коефіцієнтів ( $\vartriangle W=V\centerdot g$ ) і виконаємо корекцію параметрів ( $W=W-\vartriangle W$ )
Обчислимо похибку ( $E(W)$ )
Якщо отримане значення похибки менше, ніж задана точність ( $E(W)<\varepsilon$ ), то алгоритм зупиняється.
Якщо точність не досягнута, то повторюємо алгоритм з 4 кроку.

Програмна реалізація

Реалізація мовою С у рамках проекту GNU Scientific Library (детальніше).

Високоточна версія алгоритму мовою С++ - посилання.

Реалізація алгоритму BFGS та схожих алгоритмів (L-BFGS, L-BFGS-B, CG, метод Ньютона) мовою С++ - посилання.

Алгоритм реалізований у бібліотеці SciPy (детальніше) мовою Python.

Реалізація мовою R - посилання.

Функція з пакету Optimization toolbox мовою Matlab - посилання.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.