Стохастична градієнтна динаміка Ланжевена (SGLD) — це метод оптимізації та вибірки, що складається з характеристик стохастичного градієнтного спуску, алгоритму оптимізації Роббінса–Монро[en], і динаміки Ланжевена[en], математичного розширення моделей молекулярної динаміки. Подібно до стохастичного градієнтного спуску, SGLD — це ітеративний алгоритм оптимізації, який використовує мінібатчування для створення стохастичного оцінювача градієнта, який використовується в SGD для оптимізації диференційованої цільової функції.[1] На відміну від традиційного SGD, SGLD можна використовувати для байєсівського навчання як метод вибірки. SGLD можна розглядати як динаміку Ланжевена, застосовану до апостеріорних розподілів, але ключова відмінність полягає в тому, що члени градієнта правдоподібності є мінібатчними, як у SGD. SGLD, як і динаміка Ланжевена, створює вибірки з апостеріорного розподілу параметрів на основі доступних даних. Вперше описаний Веллінгом і Техом у 2011 році, цей метод має застосування в багатьох контекстах, які потребують оптимізації, і найбільш помітно використовується в задачах машинного навчання.
Формальне означення
Нехай задано деякий вектор параметрів , його апріорний розподіл , і набір точок даних , динаміка Ланжевена утворює вибірку з апостеріорного розподілу шляхом оновлення ланцюжка:
Стохастична градієнтна динаміка Ланжевена використовує модифіковану процедуру оновлення з мінібатченими членами правдоподібності:
де є додатним цілим числом, гаусівський шум, правдоподібность даних, задана вектором параметрів , і розміри кроку задовольняють наступні умови:
Для початкових ітерацій алгоритму кожне оновлення параметра імітує стохастичний градієнтний спуск; однак, коли алгоритм наближається до локального мінімуму або максимуму, градієнт стискається до нуля, і ланцюжок виробляє вибірки, що оточують максимальний апостериорний режим, що дозволяє зробити апостериорне висновування. Цей процес генерує приблизну вибірку з апостеріору шляхом балансування дисперсії введеного шуму Гауса та обчислення стохастичного градієнта.
Застосування
SGLD застосовний у будь-якому контексті оптимізації, для якого бажано швидко отримати апостериорну вибірку замість максимального апостериорного режиму. При цьому метод підтримує обчислювальну ефективність стохастичного градієнтного спуску порівняно з традиційним градієнтним спуском, надаючи додаткову інформацію щодо околиці критичної точки цільової функції. На практиці SGLD можна використовувати для навчання байєсівських нейронних мереж у глибокому навчанні, завдань, у яких метод надає розподіл за параметрами моделі. Вводячи інформацію про дисперсію цих параметрів, SGLD характеризує можливість узагальнення цих моделей на певних етапах навчання.[2] Крім того, отримання вибірки із апостеріорного розподілу дозволяє кількісно визначити невизначеність за допомогою довірчих інтервалів, що є неможливим за допомогою традиційного стохастичного градієнтного спуску.
Варіанти та відповідні алгоритми
Якщо градієнтні обчислення є точними, SGLD зводиться до алгоритму Ланжевена Монте-Карло,[3] вперше згаданного в літературі теорії ґраткового поля. Цей алгоритм також є модифікацією алгоритму гамільтоніана Монте-Карло[en], що складається з пропозиції єдиного кроку перекрокування, замість серії кроків.[4] Оскільки SGLD можна сформулювати як модифікацію як стохастичного градієнтного спуску, так і методів MCMC, метод лежить на перетині алгоритмів оптимізації та вибірки; метод зберігає здатність SGD швидко сходитися до регіонів з низькою вартістю, одночасно надаючи вибірку для полегшення апостериорного висновування.
Врахування послаблених обмежень на розмір кроку таких, що не наближаються до нуля асимптотично, SGLD не в змозі створити вибірку, для якої коефіцієнт відхилення Метрополіса Гастінгса дорівнює нулю, і, таким чином, крок відхилення MH стає необхідним.[1] Отриманий алгоритм, який отримав назву "скоригований за Метрополісом алгоритм Ланжевена", [5] вимагає наступного кроку:
де є нормальним розподілом з центром в один крок градієнтного спуску від та – наш цільовий розподіл.
Швидкості перемішування та алгоритмічна збіжність
Останні дослідження вивели верхню межу часу змішування як для традиційного алгоритму Ланжевена, так і для скоригованого за Метрополісом алгоритма Ланжевена.[5] Опубліковані в Ma et al., 2018, ці межі визначають швидкість, з якою алгоритми збігаються до справжнього апостеріорного розподілу, формально визначеного як:
де є довільним допуском до помилок, є деяким початковим розподілом, є апостеріорним розподілом, і є загальною нормою варіації . За деяких умов регулярності -ліпшицевої гладкої цільової функції яка є -сильно опуклою за межами області радіуса з числом обумовленості , маємо оцінки меж швидкості перемішування:
де і стосуються швидкості перемішування нескоригованого алгоритму Ланжевена та скоригованого за Метрополісом алгоритму Ланжевена відповідно. Ці межі важливі, оскільки вони показують, що обчислювальна складність є поліноміальною за розмірністю за умовою, що перебуває в .
Див. також
- Задача оптимізації
- Стохастичний градієнтний спуск
- Рівняння Ланжевена
- Методи Монте-Карло марковських ланцюгів
Список літератури
- ↑ а б Welling, Max; Teh, Yee Whye (2011). Bayesian Learning via Stochastic Gradient Langevin Dynamics (PDF). Proceedings of the 28th International Conference on Machine Learning: 681—688.
- ↑ Chaudhari, Pratik; Choromanska, Anna; Soatto, Stefano; LeCun, Yann; Baldassi, Carlo; Borgs, Christian; Chayes, Jennifer; Sagun, Levent; Zecchina, Riccardo (2017). Entropy-sgd: Biasing gradient descent into wide valleys. arXiv:1611.01838 [cs.LG].
- ↑ Kennedy, A. D. (1990). The theory of hybrid stochastic algorithms. Probabilistic Methods in Quantum Field Theory and Quantum Gravity. Plenum Press. с. 209—223. ISBN 0-306-43602-7.
- ↑ Neal, R. (2011). MCMC Using Hamiltonian Dynamics. Handbook of Markov Chain Monte Carlo. CRC Press. ISBN 978-1-4200-7941-8.
- ↑ а б Ma, Y. A.; Chen, Y.; Jin, C.; Flammarion, N.; Jordan, M. I. (2018). Sampling Can Be Faster Than Optimization. arXiv:1811.08413 [stat.ML].