В предыдущем посте мы рассмотрели, как работает выборка по важности. В предложении выборка по важности находит оценку математического ожидания некоторой функции fпри некотором распределении вероятностей Pпутем выборки из более простого распределения Qи вычислить математическое ожидание функции f при Q с членами в сумме, масштабированной по весам, полученным из отношения ненормализованные функции Q* и P*. Для более ясного и подробного понимания прочитайте этот пост.
Разве недостаточно выборки по важности?
Проблема с выборкой по важности заключается в том, что производительность алгоритма сильно зависит от распределения предложения Q. Эффект плохого предложения проявляется в более высоких измерениях. Плохое предложение может означать, что нам может потребоваться много времени для получения образцов из типичного набора P.
Решение: Метрополис Хастинг
Метод хеширования мегаполиса решает эту проблему, используя распределение предложений Q, которое зависит от текущего состояния. Простой пример: для заданного состояния x предложение может быть распределением Гаусса со средним значением при x и стандартным отклонением 1. В отличие от выборки по важности и отклонению, создание выборок в итерации мегаполиса хэшинг зависит от выборки, сгенерированной в предыдущей итерации.
Итерация в алгоритме мегаполиса выглядит следующим образом:
- Предложите новую выборку x’с учетом текущего значения выборки xᵗиспользуя распределение предложений Q
- Рассчитайте коэффициент приемлемости для нового предложенного образца x’
- Сгенерируйте случайное число в диапазоне от 0 до 1. Если сгенерированное число меньше рассчитанного коэффициента приемлемости, тогда примите, в противном случае отклоните.
Вероятность принятия рассчитывается как:
В случае симметричных распределений предложений, таких как гауссовское, где
коэффициент приемлемости принимает вид
Интуитивно это предполагает, что алгоритм склонен принимать точки, которые с высокой вероятностью находятся в целевом распределении P.
Можно показать, что для любой положительной функции предложения, когда время t, стремится к бесконечности, выборки xᵗ будут стремиться к распределению P(x). На практике, однако, часто бывает трудно проанализировать, сошелся ли алгоритм или нет, и как долго алгоритм должен выполняться. Однако есть определенные правила, которым можно следовать при использовании Метрополиса Гастинг в более высоких измерениях. Я не буду обсуждать их в этом посте, а заинтересованному читателю отсылаю к главе 24 учебника Кевина Мерфи.
Ссылка:
[1] Кевин Мерфи, Машинное обучение: вероятностная перспектива, глава 24.