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

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 не может создать образцы, для которых процент отбраковки Metropolis Hastings равен нулю, и, таким образом, становится необходимым этап отбраковки 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,\ 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 _{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 _{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 _{ULA}$ и $\tau _{MALA}$обратитесь к скоростям смешивания нескорректированного алгоритма Ланжевена и алгоритма Ланжевена с поправкой на Метрополис соответственно. Эти границы важны, поскольку они показывают, что сложность вычислений полиномиальна по размерности. $d$ при условии $LR^{2}$ существование ${\mathcal {O}}(\log d)$.