Розуміння стохастичного середнього градієнта

Градієнтний спуск є найпопулярнішим методом оптимізації в моделюванні машинного навчання (ML). Алгоритм мінімізує похибку між прогнозованими значеннями та основною правдою. Оскільки методика розглядає кожну точку даних, щоб зрозуміти та мінімізувати помилку, її ефективність залежить від розміру навчальних даних. Такі методи, як стохастичний градієнтний спуск (SGD), призначені для покращення продуктивності обчислень, але ціною точності конвергенції.

Стохастичний середній градієнт врівноважує класичний підхід, відомий як повний градієнтний спуск і SGD, і пропонує обидві переваги. Але перш ніж ми зможемо використовувати алгоритм, ми повинні спочатку зрозуміти його значення для оптимізації моделі.

Оптимізація цілей машинного навчання за допомогою градієнтного спуску

Кожен алгоритм ML має пов’язану функцію втрат, яка спрямована на мінімізацію або покращення продуктивності моделі. Математично втрату можна визначити як:

Це просто різниця між фактичним і прогнозованим результатом, і мінімізація цієї різниці означає, що наша модель наближається до базових значень істинності.

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

Звичайний градієнтний спуск

Звичайний алгоритм градієнтного спуску використовує середнє значення всіх градієнтів, обчислених для всього набору даних. Життєвий цикл одного навчального прикладу виглядає так:

Рівняння оновлення ваги виглядає так:

Де W являє собою ваги моделі, а dJ/dW є похідною функції втрат відносно ваги моделі. Звичайний метод має високу швидкість збіжності, але стає обчислювально дорогим при роботі з великими наборами даних, що містять мільйони точок даних.

Стохастичний градієнтний спуск (SGD)

Методологія SGD залишається такою ж, як і звичайна GD, але замість використання всього набору даних для обчислення градієнтів, вона використовує невелику партію вхідних даних. Цей метод є набагато ефективнішим, але може занадто сильно стрибати навколо глобальних мінімумів, оскільки кожна ітерація використовує лише частину даних для навчання.

Стохастичний середній градієнт

Підхід стохастичного середнього градієнта (SAG) був представлений як середина між GD і SGD. Він вибирає випадкову точку даних і оновлює її значення на основі градієнта в цій точці та середньозваженого значення попередніх градієнтів, збережених для цієї конкретної точки даних.

Подібно до SGD, SAG моделює кожну проблему як кінцеву суму опуклих диференційованих функцій. На будь-якій заданій ітерації він використовує поточні градієнти та середнє значення попередніх градієнтів для оновлення ваги. Рівняння має такий вигляд:

Швидкість конвергенції

Серед двох популярних алгоритмів, повного градієнта (FG) і стохастичного градієнтного спуску (SGD), алгоритм FG має кращу швидкість збіжності, оскільки він використовує весь набір даних під час кожної ітерації для обчислення.

Хоча SAG має структуру, подібну до SGD, його швидкість збіжності порівнянна з повним градієнтним підходом, а іноді й краща за неї. Таблиця 1 нижче підсумовує результати експериментів Шмідт та ін. ал .

Подальші модифікації

Незважаючи на його дивовижну продуктивність, було запропоновано кілька модифікацій оригінального алгоритму SGD, щоб допомогти покращити продуктивність.

• Повторне зважування на ранніх ітераціях: конвергенція SAG залишається повільною протягом перших кількох ітерацій, оскільки алгоритм нормалізує напрямок за допомогою n (загальна кількість точок даних). Це дає неточну оцінку, оскільки алгоритму ще потрібно побачити багато точок даних. Модифікація пропонує нормалізувати за m замість n, де m – це кількість точок даних, які бачили принаймні один раз до цієї конкретної ітерації.
• Міні-пакети: Стохастичний градієнтний підхід використовує міні-пакети для обробки кількох точок даних одночасно. Такий же підхід можна застосувати до SAG. Це дозволяє векторизувати та розпаралелювати для покращення ефективності комп’ютера. Це також зменшує навантаження на пам’ять, що є серйозною проблемою для алгоритму SAG.
• Експерименти з розміром кроку: розмір кроку, згаданий раніше (116 л), дає дивовижні результати, але автори далі експериментували, використовуючи розмір кроку 1 л. Останнє забезпечило ще кращу конвергенцію. Однак автори не змогли представити офіційний аналіз покращених результатів. Вони дійшли висновку, що з розміром кроку слід експериментувати, щоб знайти оптимальний для конкретної проблеми.

Заключні думки

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

Повний градієнтний спуск (FG) і стохастичний градієнтний спуск (SGD) є двома популярними варіаціями алгоритму. FG використовує весь набір даних під час кожної ітерації та забезпечує високу швидкість збіжності при високій вартості обчислень. На кожній ітерації SGD використовує підмножину даних для запуску алгоритму. Це набагато ефективніше, але з невизначеною конвергенцією.

Стохастичний середній градієнт (SAG) — ще один варіант, який забезпечує переваги обох попередніх алгоритмів. Він використовує середнє значення попередніх градієнтів і підмножини набору даних, щоб забезпечити високий рівень збіжності з низькими обчисленнями. Алгоритм можна додатково модифікувати для підвищення його ефективності за допомогою векторизації та міні-пакетів.