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

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

Стохастична градієнтна динаміка Ланжевена (SGLD) — це метод оптимізації та вибірки, що складається з характеристик стохастичного градієнтного спуску, алгоритму оптимізації Роббінса–Монро, і динаміки Ланжевена, математичного розширення моделей молекулярної динаміки. Подібно до стохастичного градієнтного спуску, SGLD — це ітеративний алгоритм оптимізації, який використовує мінібатчування для створення стохастичного оцінювача градієнта, який використовується в SGD для оптимізації диференційованої цільової функції. На відміну від традиційного 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 характеризує можливість узагальнення цих моделей на певних етапах навчання. Крім того, отримання вибірки із апостеріорного розподілу дозволяє кількісно визначити невизначеність за допомогою довірчих інтервалів, що є неможливим за допомогою традиційного стохастичного градієнтного спуску.

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

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

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

${\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 )$ – наш цільовий розподіл.

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

Останні дослідження вивели верхню межу часу змішування як для традиційного алгоритму Ланжевена, так і для скоригованого за Метрополісом алгоритма Ланжевена. Опубліковані в 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)$ .

Див. також

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