Математика для штучних нейронних мереж для новачків, частина 2
Градієнтний спуск
У попередній частині було показано приклад обчислення параметрів лінійної регресії з допомогою методу найменших квадратів. Параметри знайшли аналітично — , де — псевдооборотна матриця. Це рішення наочне, точне та коротке. Але є проблема, яку можна вирішити чисельно. Градієнтний спуск – метод чисельної оптимізації, який може бути використаний у багатьох алгоритмах, де потрібно знайти екстремум функції – нейронні мережі, SVM, k-середні, регресії. Однак простіше його сприйняти у чистому вигляді (і простіше модифікувати).
Проблема полягає в тому, що обчислення псевдооборотної матриці дуже затратно: 2 множення по , знаходження зворотної матриці - , множення матриці вектор , де n - кількість елементів у матриці A (кількість ознак * кількість елементів у тестовій вибірці) Якщо кількість елементів у матриці A велика (> 10^6 — наприклад), навіть якщо в наявності 10000 ядер, знаходження рішення аналітично може затягтися. Також перша похідна може виявитися нелінійною, що ускладнить рішення, аналітичного рішення може виявитися зовсім або дані можуть просто не влізти в пам'ять і знадобиться ітеративний алгоритм. Буває, що плюси записують і те, що чисельне рішення не ідеально точне. У зв'язку із цим функцію вартості мінімізують чисельними методами. Завдання перебування екстремуму називають завданням оптимізації. У цій частині зупинюся на методі оптимізації, який називається градієнтний спуск.
Не відходитимемо від лінійної регресії та МНК і позначимо функцію втрат як вона залишилася незмінною. Нагадаю, що градієнт – це вектор виду, де – це приватна похідна. Однією з властивостей градієнта є те,що він вказує напрямок, у якому деяка функція f зростає найбільше. Доказ цього випливає із визначення похідної. Пара доказів. Візьмемо деяку точку a - в околиці цієї точки функція F повинна бути визначена і диференційована, тоді вектор антиградієнта буде вказувати на напрямок, в якому функція F зменшується найшвидше. Звідси робиться висновок, що в деякій точці b, що дорівнює , при деякому малому значення функції буде менше або дорівнює значенню в точці а. Можна уявити це, як рух униз пагорбом — зробивши крок униз, поточна позиція буде нижчою, ніж попередня. Таким чином, на кожному наступному кроці висота як мінімум не збільшуватиметься. Формальне визначення. Виходячи з цих визначень, можна отримати формулу для знаходження невідомих параметрів (це просто переписана версія формули вище):
- Це крок методу. У задачах машинного навчання його називають швидкістю навчання.
Метод дуже простий та інтуїтивний, візьмемо простий двовимірний приклад для демонстрації:
Необхідно мінімізувати функцію виду. Мінімізувати означає знайти при якому значенні функція набуває мінімального значення. Визначимо послідовність дій:
1) Необхідна похідна за : 2) Встановимо початкове значення = 0 3) Встановимо розмір кроку - спробуємо кілька значень - 0.1, 0.9, 1.2, щоб подивитися, як цей вибір вплине на збіжність. 4) 25 разів поспіль виконаємо зазначену вище формулу: Оскільки невідомий параметр лише один, то й формула лише одна.
Код дуже простий. Виключаючи визначення функцій, весь алгоритм вмістився у 3 рядки:
Весь процес можна візуалізувати приблизно так (синя точка – значення на попередньому кроці, червона – поточне):
Або ж для крокуіншого розміру:
При значенні, що дорівнює 1.2, метод розходиться, кожен крок опускаючись не нижче, а навпаки вище, спрямовуючи в нескінченність. Крок у простій реалізації підбирається вручну і його розмір залежить від даних - на якихось ненормалізованих значеннях з великим градієнтом і 0.0001 може призводити до розбіжності.
Ось ще приклад із «поганою» функцією. У першій анімації метод також розходиться і довго блукатиме пагорбами через занадто високий крок. У другому випадку було знайдено локальний мінімум і варіюючи значення швидкості не вдасться змусити метод знайти мінімум глобальний. Цей факт є одним недоліком методу — він може знайти глобальний мінімум тільки якщо опукла і гладка функція. Або якщо пощастить із початковими значеннями.
Також можна розглянути роботу алгоритму на тривимірному графіку. Часто малюють лише ізолінії якоїсь фігури. Я взяв простий параболоїд обертання: . У 3D виглядає він так:
Також зверніть увагу, що всі лінії градієнта, спрямовані перпендикулярно до ізоліній. Це означає, що, рухаючись у бік антиградієнта, не вийде за один крок відразу ж стрибнути в мінімум — градієнт вказує зовсім не туди.
Після графічного пояснення знайдемо формулу для обчислення невідомих параметрів лінійної регресії з МНК.
Якби кількість елементів у тестовій вибірці дорівнювала одиниці, то формулу можна було б так і залишити і рахувати. У разі, коли в наявності n елементів алгоритм виглядає так:
Повторювати v разів для кожного j одночасно. >, де n - кількість елементів у навчальній вибірці, v - кількість ітерацій
Вимога одночасності означає, що похідна має бутиобчислена зі старими значеннями theta, не варто обчислювати спочатку окремо перший параметр, потім другий і т.д., тому що після зміни першого параметра окремо, похідна також змінить своє значення. Псевдокод одночасної зміни:
Якщо обчислювати значення параметрів поодинці, це вже буде не градієнтний спуск. Припустимо, у нас тривимірна фігура і якщо обчислювати параметри один за одним, то можна уявити цей процес як рух тільки по одній координаті за раз - один крок по x координаті, потім крок по y координаті і т.д. сходинками замість руху у бік вектора антиградієнта.
Наведений варіант алгоритму називають пакетний градієнтний спуск. Кількість повторень можна замінити на фразу «Повторювати, доки зійдеться». Ця фраза означає, що параметри будуть коригуватися доти, доки попереднє та поточне значення функції вартості не зрівняються. Це означає, що локальний чи глобальний мінімум знайдено і далі алгоритм не піде. На практиці рівності досягти неможливо і вводиться межа збіжності. Його встановлюють якоюсь малою величиною і критерієм зупинки є те, що різниця попереднього та поточного значень менша за межу збіжності — це означає, що мінімум досягнуто з потрібною, встановленою точністю. Вище точності (менше) – більше ітерацій алгоритму. Виглядає це якось так:
Так як пост несподівано розтягнувся, я хотів би його на цьому завершити — в наступній частині я продовжу розбір градієнтного спуску для лінійної регресії з МНК.