Термін "метод сполучених градієнтів" - один із прикладів того, як безглузді словосполучення, ставши звичними, сприймаються самі по собі зрозумілі і не викликають ніякого здивування. Справа в тому, що, за винятком приватного і не представляє практичного інтересу випадку, градієнти не є пов'язаними, а пов'язані напряму не мають нічого спільного з градієнтами. Назва методу відображає той факт, що даний метод відшукання безумовного екстремуму поєднує в собі поняття градієнта цільової функції і пов'язаних напрямків.
Кілька слів про позначеннях, які використовуються далі.
Скалярний добуток двох векторів записується $ x ^ Ty $ і представляє суму скалярів: $ \ sum_ ^ n \, x_i \, y_i $. Зауважимо, що $ x ^ Ty = y ^ Tx $. Якщо x і y ортогональні, то $ x ^ Ty = 0 $. Загалом, вираження, які перетворюються до матриці 1х1, такі як $ x ^ Ty $ і $ x ^ TA_x $, розглядаються як скалярні величини.
Спочатку метод сполучених градієнтів був розроблений для вирішення систем лінійних алгебраїчних рівнянь виду:
де x - невідомий вектор, b - відомий вектор, а A - відома, квадратна, симетрична, позитивно-визначена матриця. Вирішення цієї системи еквівалентно знаходженню мінімуму відповідної квадратичної форми.
Квадратична форма - це просто скаляр, квадратична функція нікого вектора x такого вигляду:
Наявність такого зв'язку між матрицею лінійного перетворення A і скалярною функцією f (x) дає можливість проілюструвати деякі формули лінійної алгебри інтуїтивно зрозумілими малюнками. Наприклад, матриця А називається позитивно-певної, якщо для будь-якого ненульового вектора x справедливо наступне:
На малюнку 1 зображено як виглядають квадратичні форми відповідно для позитивно-певної матриці (а), негативно-певної матриці (b), позитивно-невизначеною матриці (с), невизначеною матриці (d).
Тобто, якщо матриця А - позитивно-визначена, то замість того, щоб вирішувати систему рівнянь 1, можна знайти мінімум її квадратичної функції. Причому, метод сполучених градієнтів зробить це за n-менш кроків, де n - розмірність невідомого вектора x. Так як будь-яка гладка функція в околицях точки свого мінімуму добре апроксимується квадратичної, цей же метод можна застосувати для мінімізації і неквадратічних функцій. При цьому метод перестає бути кінцевим, а стає ітеративним.
Розгляд методу сполучених градієнтів доцільно почати з розгляду більш простого методу пошуку екстремуму функції - методу найшвидшого спуску. На малюнку 2 зображено траєкторія руху в точку мінімуму методом найшвидшого спуску. Суть цього методу:
- в початковій точці x (0) обчислюється градієнт, і рух здійснюється в напрямку антіградіента до тих пір, поки зменшується цільова функція;
- в точці, де функція перестає зменшуватися, знову обчислюється градієнт, і спуск триває в новому напрямку;
- процес повторюється до досягнення точки мінімуму.
В даному випадку кожне нове напрямок руху ортогонально попереднього. Чи не існує більш розумного способу вибору нового напрямку руху? Існує, і він називається метод сполучених напрямків. А метод сполучених градієнтів якраз відноситься до групи методів пов'язаних напрямків. На малюнку 3 зображено траєкторія руху в точку мінімуму при використанні методу сполучених градієнтів.
Визначення пов'язаності формулюється так: два вектора x і y називають А-сполученими (або сполученими по відношенню до матриці А) або А-ортогональними, якщо скалярний твір x і Ay дорівнює нулю, тобто:
Спряженість можна вважати узагальненням поняття ортогональності. Дійсно, коли матриця А - одинична матриця, відповідно до рівністю 4, вектори x і y - ортогональні. Можна й інакше продемонструвати взаємозв'язок понять ортогональности і пов'язаності: подумки розтягніть малюнок 3 таким чином, щоб лінії рівного рівня з еліпсів перетворилися в окружності, при цьому пов'язані напрямки стануть просто ортогональними.
Залишається з'ясувати, яким чином обчислювати пов'язані напряму. Один з можливих способів - використовувати методи лінійної алгебри, зокрема, процес ортогоналізації Грамма-Шмідта. Але для цього необхідно знати матрицю А, тому для більшості завдань (наприклад, навчання багатошарових нейромереж) цей метод не годиться. На щастя, існують інші, ітеративні способи обчислення сполученого напрямки, найвідоміший - формула Флетчера-Ривса:
Формула 5 означає, що нове поєднане напрямок виходить складанням антіградіента в точці повороту і попереднього напрямку руху, помноженого на коефіцієнт, обчислений за формулою 6. Напрями, обчислені за формулою 5, виявляються пов'язаними, якщо мінімізується функція задана в формі 2. Тобто для квадратичних функцій методу сполучених градієнтів знаходить мінімум за n кроків (n - розмірність простору пошуку). Для функцій загального вигляду алгоритм перестає бути кінцевим і стає ітеративним. При цьому, Флетчер і Ривс пропонують відновлювати алгоритмічну процедуру через кожні n + 1 кроків.
Можна навести ще одну формулу для визначення сполученого напрямки, формула Полак-Райбер (Polak-Ribiere):
Метод Флетчера-Ривса сходиться, якщо початкова точка досить близька до необхідного мінімуму, тоді як метод Полак-Райбер може в окремих випадках нескінченно циклитися. Однак останній часто сходиться швидше першого методу. На щастя, збіжність методу Полак-Райбер може бути гарантована вибором $ \ beta = \ max \ $. Це еквівалентно рестарту алгоріма за умовою $ \ beta \ leq 0 $. Рестарт алгоритмічної процедури необхідний, щоб забути останній напрям пошуку і стартувати алгоритм заново в напрямку якнайшвидшого спуску.
Нижче наведено алгоритм сполучених градієнтів для мінімізації функцій загального вигляду (неквадратічних).
- Обчислюється антіградіента в довільній точці x (0).
З наведеного алгоритму випливає, що на кроці 2 здійснюється одномірна мінімізація функції. Для цього, зокрема, можна скористатися методом Фібоначчі, методом золотого перетину або методом бисекции. Швидшу збіжність забезпечує метод Ньютона-Рафсона, але для цього необхідно мати можливість обчислення матриці Гессе. В останньому випадку, змінна, по якій здійснюється оптимізація, обчислюється на кожному кроці ітерації за формулою:
Кілька слів про використання методу сполучених напрямків при навчанні нейронних мереж. У цьому випадку використовується навчання по епохах, тобто при обчисленні цільової функції пред'являються всі шаблони навчальної множини і обчислюється середній квадрат функції помилки (або якась її модифікація). Те ж саме - при обчисленні градієнта, тобто використовується сумарний градієнт по всьому навчальному набору. Градієнт для кожного прикладу обчислюється з використанням алгоритму зворотного поширення (BackProp).
Варіант методу сполучених напрямків, який використовує формулу Флетчера-Ривса для розрахунку пов'язаних напрямків.
r: = -f '(x) // антіградіента цільової функції
d: = r // початкове напрямок спуску збігається з антіградіентом
Sigmanew. = R T * r // квадрат модуля антіградіента
// Цикл пошуку (вихід за лічильником або помилку)
while i
begin
j. = 0
Sigmad. = D T * d
// Цикл одновимірної мінімізації (спуск у напрямку d)
repeat
a. =
x. = X + a
j. = J + 1
until (j> = jmax) or (a 2 * Sigmad <= Eps 2 )
r. = -f '(x) // антіградіента цільової функції в новій точці
Sigmaold. = Sigmanew
Sigmanew. = R T * r
beta. = Sigmanew / Sigmaold
d. = R + beta * d // Обчислення сполученого напрямки
k. = K + 1
if (k = n) or (r T * d <= 0) then // Рестарт алгоритма
begin
d. = r
k. = 0
end
Метод сполучених градієнтів є методом першого порядку, в той же час швидкість його збіжності квадратична. Цим він вигідно відрізняється від звичайних градієнтних методів. Наприклад, метод найшвидшого спуску і метод координатного спуску для квадратичної функції сходяться лише в межі, в той час як метод сполучених градієнтів оптимізує квадратичную функцію за кінцеве число ітерацій. При оптимізації функцій загального вигляду, метод сполучених напрямків сходиться в 4-5 разів швидше методу найшвидшого спуску. При цьому, на відміну від методів другого порядку, не потрібно трудомістких обчислень друге приватних похідних.