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

Стохастична градієнтна динаміка Ланжевена (SGLD) — це метод оптимізації та вибірки, що складається з характеристик стохастичного градієнтного спуску, алгоритму оптимізації Роббінса–Монро^[en], і динаміки Ланжевена^[en], математичного розширення моделей молекулярної динаміки. Подібно до стохастичного градієнтного спуску, SGLD — це ітеративний алгоритм оптимізації, який використовує мінібатчування для створення стохастичного оцінювача градієнта, який використовується в SGD для оптимізації диференційованої цільової функції.^[1] На відміну від традиційного SGD, SGLD можна використовувати для байєсівського навчання як метод вибірки. SGLD можна розглядати як динаміку Ланжевена, застосовану до апостеріорних розподілів, але ключова відмінність полягає в тому, що члени градієнта правдоподібності є мінібатчними, як у SGD. SGLD, як і динаміка Ланжевена, створює вибірки з апостеріорного розподілу параметрів на основі доступних даних. Вперше описаний Веллінгом і Техом у 2011 році, цей метод має застосування в багатьох контекстах, які потребують оптимізації, і найбільш помітно використовується в задачах машинного навчання.

Формальне означення

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

\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}.

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

\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},

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

\sum _{t=1}^{\infty }\varepsilon _{t}=\infty ,\quad \sum _{t=1}^{\infty }\varepsilon _{t}^{2}<\infty .

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

Застосування

SGLD застосовний у будь-якому контексті оптимізації, для якого бажано швидко отримати апостериорну вибірку замість максимального апостериорного режиму. При цьому метод підтримує обчислювальну ефективність стохастичного градієнтного спуску порівняно з традиційним градієнтним спуском, надаючи додаткову інформацію щодо околиці критичної точки цільової функції. На практиці SGLD можна використовувати для навчання байєсівських нейронних мереж у глибокому навчанні, завдань, у яких метод надає розподіл за параметрами моделі. Вводячи інформацію про дисперсію цих параметрів, SGLD характеризує можливість узагальнення цих моделей на певних етапах навчання.^[2] Крім того, отримання вибірки із апостеріорного розподілу дозволяє кількісно визначити невизначеність за допомогою довірчих інтервалів, що є неможливим за допомогою традиційного стохастичного градієнтного спуску.

Варіанти та відповідні алгоритми

Якщо градієнтні обчислення є точними, SGLD зводиться до алгоритму Ланжевена Монте-Карло,^[3] вперше згаданного в літературі теорії ґраткового поля. Цей алгоритм також є модифікацією алгоритму гамільтоніана Монте-Карло^[en], що складається з пропозиції єдиного кроку перекрокування, замість серії кроків.^[4] Оскільки SGLD можна сформулювати як модифікацію як стохастичного градієнтного спуску, так і методів MCMC, метод лежить на перетині алгоритмів оптимізації та вибірки; метод зберігає здатність SGD швидко сходитися до регіонів з низькою вартістю, одночасно надаючи вибірку для полегшення апостериорного висновування.

Врахування послаблених обмежень на розмір кроку $\varepsilon _{t}$ таких, що не наближаються до нуля асимптотично, SGLD не в змозі створити вибірку, для якої коефіцієнт відхилення Метрополіса Гастінгса дорівнює нулю, і, таким чином, крок відхилення MH стає необхідним.^[1] Отриманий алгоритм, який отримав назву "скоригований за Метрополісом алгоритм Ланжевена", ^[5] вимагає наступного кроку:

{\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],

де $p(\theta ^{t}\mid \theta ^{t+1})$ є нормальним розподілом з центром в один крок градієнтного спуску від $\theta ^{t}$ та $p(\theta )$ – наш цільовий розподіл.

Швидкості перемішування та алгоритмічна збіжність

Останні дослідження вивели верхню межу часу змішування як для традиційного алгоритму Ланжевена, так і для скоригованого за Метрополісом алгоритма Ланжевена.^[5] Опубліковані в Ma et al., 2018, ці межі визначають швидкість, з якою алгоритми збігаються до справжнього апостеріорного розподілу, формально визначеного як:

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

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

\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),

\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),

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

Див. також

Список літератури

↑ ^а ^б 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].

[:0-1] а ^б 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.

[2] 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].

[3] 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.

[4] Neal, R. (2011). MCMC Using Hamiltonian Dynamics. Handbook of Markov Chain Monte Carlo. CRC Press. ISBN 978-1-4200-7941-8.

[:1-5] а ^б Ma, Y. A.; Chen, Y.; Jin, C.; Flammarion, N.; Jordan, M. I. (2018). Sampling Can Be Faster Than Optimization. arXiv:1811.08413 [stat.ML].

[1]

[2]

[3]

[4]

[5]