Марковские цепи Монте-Карло (MCMC) и алгоритм Метрополиса-Гастингса

Байесовский вывод и проблема высоких размерностей

В современной статистике, биоинформатике и машинном обучении доминирует байесовский подход. В отличие от классической частотной статистики, байесовский вывод рассматривает параметры математических моделей не как фиксированные числа, а как случайные величины с определенными распределениями вероятностей. Цель байесовского обучения — найти апостериорное распределение параметров модели с учетом поступивших новых экспериментальных данных. Однако, согласно формуле Байеса, для этого необходимо вычислить знаменатель — так называемую обоснованность (evidence), которая представляет собой сложнейший многомерный интеграл по всему пространству параметров.

Если в нашей нейросети или генетической модели 100 параметров, нам нужно вычислить 100-мерный интеграл. Как мы уже знаем, классические методы интегрирования по сеткам (метод Симпсона) абсолютно бессильны из-за «проклятия размерности». Базовый стохастический метод Монте-Карло, который просто разбрасывает точки случайным образом, тоже терпит крах: в пространствах высоких размерностей область, где сосредоточена основная вероятность (типичное множество), занимает исчезающе малый объем. Случайные точки просто будут бесконечно долго летать в математической пустоте. На помощь приходит мощнейший алгоритмический класс — Марковские цепи Монте-Карло (MCMC).

Алгоритм Метрополиса-Гастингса: случайные блуждания с умом

В методах MCMC генерация случайных точек больше не является абсолютно независимой. Каждая следующая точка генерируется с оглядкой на то, где находилась предыдущая. Математически это формирует цепь Маркова — последовательность состояний, где вероятность перехода зависит только от текущего положения и не зависит от далекой предыстории.

Фундаментальным алгоритмом в семействе MCMC является алгоритм Метрополиса-Гастингса, опубликованный в 1953 году (для задач статистической физики) и обобщенный в 1970-х. Суть его гениальна и проста. Алгоритм берет текущую точку в пространстве и случайным образом «предлагает» сдвинуться в соседнюю точку (используя простое распределение, например, нормальное). Затем он вычисляет значение целевой функции вероятности в новой точке и сравнивает его со старым. Если в новой точке вероятность выше, алгоритм принимает этот шаг безусловно (мы идем в гору). Если же вероятность в новой точке ниже, алгоритм все равно может принять этот невыгодный шаг, но лишь с определенной долей вероятности, равной отношению этих функций. Это позволяет алгоритму не застревать в локальных максимумах и свободно исследовать весь ландшафт. Спустя достаточное время (период прогрева, burn-in), такая цепь начинает выдавать точки, которые строго подчиняются искомому сложному апостериорному распределению!

Гамильтоново Монте-Карло (HMC): градиенты указывают путь

Несмотря на свою универсальность, Метрополис-Гастингс страдает от медленной диффузии (случайного блуждания). В пространствах сотен измерений он совершает слишком много отбрасываемых шагов или мечется на месте, крайне медленно исследуя объем.

Революцией в байесовских вычислениях стало заимствование концепций из классической ньютоновской механики — Гамильтоново Монте-Карло (HMC). В алгоритме HMC каждой случайной точке пространства параметров искусственно приписывается виртуальный вектор «импульса». Пространство вероятностей рассматривается как физическая гравитационная потенциальная яма (вычисляемая через градиент функции с помощью автоматического дифференцирования). Запуск алгоритма симулирует полет «математического шарика» по этой искривленной многомерной поверхности в течение некоторого времени (интегрирование Гамильтоновых уравнений). Благодаря использованию градиентов, HMC делает гигантские, направленные и физически осмысленные шаги сквозь пространство параметров, кардинально ускоряя сходимость MCMC и делая возможным байесовское обучение сложнейших моделей глубокого обучения (Bayesian Neural Networks).