Перегляд вихідного коду сторінки Стохастична градієнтна динаміка Ланжевена

[[Файл:Non-Convex_Objective_Function.gif|міні| SGLD можна використовувати для оптимізації невипуклих цільових функцій, які тут показані як сума гаусіан.]]
'''Стохастична градієнтна динаміка Ланжевена''' ('''SGLD''') — це метод [[Оптимізація (математика)|оптимізації]] та вибірки, що складається з характеристик [[Стохастичний градієнтний спуск|стохастичного градієнтного спуску]], {{нп|Алгоритм оптимізації Роббінса–Монро|алгоритму оптимізації Роббінса–Монро||Stochastic_approximation#Robbins–Monro_algorithm}}, і [[Динаміка Ланжевена|динаміки Ланжевена]], математичного розширення моделей [[Молекулярна динаміка|молекулярної динаміки]]. Подібно до стохастичного градієнтного спуску, SGLD — це ітеративний алгоритм оптимізації, який використовує мінібатчування для створення стохастичного оцінювача градієнта, який використовується в SGD для оптимізації [[Диференційовна функція|диференційованої]] [[Функція втрат|цільової функції]].<ref name=":0">{{Cite journal|last=Welling|first=Max|last2=Teh|first2=Yee Whye|date=2011|title=Bayesian Learning via Stochastic Gradient Langevin Dynamics|url=https://icml.cc/2011/papers/398_icmlpaper.pdf|journal=Proceedings of the 28th International Conference on Machine Learning|pages=681–688}}</ref> На відміну від традиційного SGD, SGLD можна використовувати для байєсівського навчання як метод вибірки. SGLD можна розглядати як динаміку Ланжевена, застосовану до апостеріорних розподілів, але ключова відмінність полягає в тому, що члени градієнта правдоподібності є мінібатчними, як у SGD. SGLD, як і динаміка Ланжевена, створює вибірки з апостеріорного розподілу параметрів на основі доступних даних. Вперше описаний Веллінгом і Техом у 2011 році, цей метод має застосування в багатьох контекстах, які потребують оптимізації, і найбільш помітно використовується в задачах [[Машинне навчання|машинного навчання]].

== Формальне означення ==
Нехай задано деякий вектор параметрів <math> \theta </math>, його апріорний розподіл <math> p(\theta) </math>, і набір точок даних <math> X = \{x_i\}_{i = 1}^N </math>, динаміка Ланжевена утворює вибірку з апостеріорного розподілу <math> p ( \theta \mid X ) \propto p (\theta) \prod_{i = 1}^N p(x_i \mid \theta) </math> шляхом оновлення ланцюжка:

: <math>\Delta \theta_t = \frac{\varepsilon_t} 2 \left( \nabla \log p(\theta_t) + \sum_{i=1}^N \nabla \log p(x_{t_i} \mid \theta_t) \right) + \eta_t. </math>

Стохастична градієнтна динаміка Ланжевена використовує модифіковану процедуру оновлення з мінібатченими членами правдоподібності:

: <math>\Delta \theta_t = \frac{\varepsilon_t} 2 \left( \nabla \log p(\theta_t) + \frac{N}{n} \sum_{i=1}^n \nabla \log p(x_{t_i} \mid \theta_t) \right) + \eta_t, </math>

де <math>n < N</math> є додатним цілим числом, <math> \eta_t \sim \mathcal{N}(0,\varepsilon_t) </math> гаусівський шум, <math> p(x \mid \theta) </math> правдоподібность даних, задана вектором параметрів <math> \theta </math>, і розміри кроку <math> \varepsilon_t </math> задовольняють наступні умови:

: <math>\sum_{t = 1}^\infty \varepsilon_t = \infty , \quad \sum_{t=1}^\infty \varepsilon_t^2 < \infty.</math>

Для початкових ітерацій алгоритму кожне оновлення параметра імітує стохастичний градієнтний спуск; однак, коли алгоритм наближається до локального мінімуму або максимуму, градієнт стискається до нуля, і ланцюжок виробляє вибірки, що оточують [[Баєсове висновування|максимальний апостериорний режим]], що дозволяє зробити апостериорне висновування. Цей процес генерує приблизну вибірку з апостеріору шляхом балансування дисперсії введеного шуму Гауса та обчислення стохастичного градієнта.

== Застосування ==
SGLD застосовний у будь-якому контексті оптимізації, для якого бажано швидко отримати апостериорну вибірку замість максимального апостериорного режиму. При цьому метод підтримує обчислювальну ефективність стохастичного градієнтного спуску порівняно з традиційним [[Градієнтний спуск|градієнтним спуском]], надаючи додаткову інформацію щодо околиці [[Критична точка (математика)|критичної точки]] цільової функції. На практиці SGLD можна використовувати для навчання [[Баєсове висновування|байєсівських]] [[Штучна нейронна мережа|нейронних мереж]] у [[Глибоке навчання|глибокому навчанні]], завдань, у яких метод надає розподіл за параметрами моделі. Вводячи інформацію про дисперсію цих параметрів, SGLD характеризує можливість узагальнення цих моделей на певних етапах навчання.<ref>{{cite arXiv|last1=Chaudhari|first1=Pratik|last2=Choromanska|first2=Anna|last3=Soatto|first3=Stefano|author-link3=Stefano Soatto|last4=LeCun|first4=Yann|author-link4=Yann LeCun|last5=Baldassi|first5=Carlo|last6=Borgs|first6=Christian|author-link6=Christian Borgs|last7=Chayes|first7=Jennifer|author-link7=Jennifer Tour Chayes|last8=Sagun|first8=Levent|last9=Zecchina|first9=Riccardo|title=Entropy-sgd: Biasing gradient descent into wide valleys|eprint=1611.01838|year=2017|class=cs.LG}}</ref> Крім того, отримання вибірки із апостеріорного розподілу дозволяє кількісно визначити невизначеність за допомогою довірчих інтервалів, що є неможливим за допомогою традиційного стохастичного градієнтного спуску.

== Варіанти та відповідні алгоритми ==
Якщо градієнтні обчислення є точними, SGLD зводиться до алгоритму ''Ланжевена Монте-Карло'',<ref>{{Cite book
|title=Probabilistic Methods in Quantum Field Theory and Quantum Gravity
|last=Kennedy
|first=A. D.
|year=1990
|publisher=Plenum Press
|pages=209–223
|chapter=The theory of hybrid stochastic algorithms
|isbn=0-306-43602-7
}}</ref> вперше згаданного в літературі [[Квантова теорія поля на ґратці|теорії ґраткового поля]]. Цей алгоритм також є модифікацією алгоритму {{нп|Гамільтоніан Монте-Карло|гамільтоніана Монте-Карло||Hamiltonian Monte Carlo}}, що складається з пропозиції єдиного кроку перекрокування, замість серії кроків.<ref>{{Cite book
|title=Handbook of Markov Chain Monte Carlo
|last=Neal
|first=R.
|year=2011
|publisher=CRC Press
|chapter=MCMC Using Hamiltonian Dynamics
|isbn=978-1-4200-7941-8
}}</ref> Оскільки SGLD можна сформулювати як модифікацію як стохастичного градієнтного спуску, так і методів [[Методи Монте-Карло марковських ланцюгів|MCMC]], метод лежить на перетині алгоритмів оптимізації та вибірки; метод зберігає здатність SGD швидко сходитися до регіонів з низькою вартістю, одночасно надаючи вибірку для полегшення апостериорного висновування.

Врахування послаблених обмежень на розмір кроку <math> \varepsilon_t </math> таких, що не наближаються до нуля асимптотично, SGLD не в змозі створити вибірку, для якої коефіцієнт відхилення [[Алгоритм Метрополіса — Гастінгса|Метрополіса Гастінгса]] дорівнює нулю, і, таким чином, крок відхилення MH стає необхідним.<ref name=":0"/> Отриманий алгоритм, який отримав назву "скоригований за Метрополісом алгоритм Ланжевена", <ref name=":1">{{cite arXiv|last1=Ma|first1=Y. A.|last2=Chen|first2=Y.|last3=Jin|first3=C.|last4=Flammarion|first4=N.|last5=Jordan|first5=M. I.|author-link5=Michael I. Jordan|year=2018|title=Sampling Can Be Faster Than Optimization|class=stat.ML|eprint=1811.08413}}</ref> вимагає наступного кроку:

: <math>\frac { p( \mathbf{\theta}^t \mid \mathbf{\theta}^{t+1}) p^* \left( \mathbf {\theta}^t \right) } { p \left( \mathbf{\theta}^{t+1} \mid \mathbf {\theta}^t \right) p^* (\mathbf{\theta}^{t+1})} < u, \quad \ u \sim \mathcal{U} [0,1], </math>

де <math>p(\theta^t \mid \theta^{t + 1})</math> є [[Нормальний розподіл|нормальним розподілом]] з центром в один крок градієнтного спуску від <math>\theta^{t}</math> та <math>p(\theta)</math> '''–''' наш цільовий розподіл.

== Швидкості перемішування та алгоритмічна збіжність ==
Останні дослідження вивели верхню межу часу змішування як для традиційного алгоритму Ланжевена, так і для скоригованого за Метрополісом алгоритма Ланжевена.<ref name=":1"/> Опубліковані в Ma et al., 2018, ці межі визначають швидкість, з якою алгоритми збігаються до справжнього апостеріорного розподілу, формально визначеного як:

: <math>\tau(\varepsilon ; p^0) = \min \left\{ k \mid \left\| p^k - p^* \right\|_{\mathrm{V}} \leq \varepsilon \right\},</math>

де <math>\varepsilon \in (0,1)</math> є довільним допуском до помилок, <math>p^0</math> є деяким початковим розподілом, <math>p^*</math> є апостеріорним розподілом, і <math>||*||_{TV}</math> є [[Варіація функції|загальною нормою варіації]] . За деяких умов регулярності <math>L</math>-ліпшицевої гладкої цільової функції <math>U(x)</math> яка є <math>m</math>-сильно [[Опукла множина|опуклою]] за межами області радіуса <math>R</math> з [[Число обумовленості|числом обумовленості]] <math>\kappa = \frac{L}{m}</math>, маємо оцінки меж швидкості перемішування:

: <math>\tau_{\mathrm{ULA}}(\varepsilon,p^0) \leq \mathcal{O} \left( e^{32LR^2} \kappa^2 \frac d {\varepsilon^2} \ln \left( \frac d {\varepsilon^2} \right) \right),</math>

: <math>\tau_{\mathrm{MALA}} (\varepsilon,p^0) \leq \mathcal{O} \left( e^{16LR^2} \kappa^{3/2} d^{1/2} \left( d \ln \kappa + \ln \left( \frac 1 \varepsilon \right) \right)^{3/2} \right),</math>

де <math>\tau_{\mathrm{ULA}}</math> і <math>\tau_{\mathrm{MALA}}</math> стосуються швидкості перемішування нескоригованого алгоритму Ланжевена та скоригованого за Метрополісом алгоритму Ланжевена відповідно. Ці межі важливі, оскільки вони показують, що обчислювальна складність є поліноміальною за розмірністю <math>d</math> за умовою, що <math>LR^2</math> перебуває в <math>\mathcal{O}(\log d)</math> .

== Див. також ==

* [[Задача оптимізації]]
* [[Стохастичний градієнтний спуск]]
* [[Рівняння Ланжевена]]
* [[Методи Монте-Карло марковських ланцюгів]]

== Список літератури ==
<references />
[[Категорія:Стохастична оптимізація]]
[[Категорія:Алгоритми оптимізації]]
[[Категорія:Градієнтні методи]]
[[Категорія:Обчислювальна статистика]]