В предыдущем посте мы рассмотрели, как работает выборка по важности. В предложении выборка по важности находит оценку математического ожидания некоторой функции fпри некотором распределении вероятностей Pпутем выборки из более простого распределения Qи вычислить математическое ожидание функции f при Q с членами в сумме, масштабированной по весам, полученным из отношения ненормализованные функции Q* и P*. Для более ясного и подробного понимания прочитайте этот пост.

Разве недостаточно выборки по важности?

Проблема с выборкой по важности заключается в том, что производительность алгоритма сильно зависит от распределения предложения Q. Эффект плохого предложения проявляется в более высоких измерениях. Плохое предложение может означать, что нам может потребоваться много времени для получения образцов из типичного набора P.

Решение: Метрополис Хастинг

Метод хеширования мегаполиса решает эту проблему, используя распределение предложений Q, которое зависит от текущего состояния. Простой пример: для заданного состояния x предложение может быть распределением Гаусса со средним значением при x и стандартным отклонением 1. В отличие от выборки по важности и отклонению, создание выборок в итерации мегаполиса хэшинг зависит от выборки, сгенерированной в предыдущей итерации.

Итерация в алгоритме мегаполиса выглядит следующим образом:

  1. Предложите новую выборку x’с учетом текущего значения выборки xᵗиспользуя распределение предложений Q
  2. Рассчитайте коэффициент приемлемости для нового предложенного образца x’
  3. Сгенерируйте случайное число в диапазоне от 0 до 1. Если сгенерированное число меньше рассчитанного коэффициента приемлемости, тогда примите, в противном случае отклоните.

Вероятность принятия рассчитывается как:

В случае симметричных распределений предложений, таких как гауссовское, где

коэффициент приемлемости принимает вид

Интуитивно это предполагает, что алгоритм склонен принимать точки, которые с высокой вероятностью находятся в целевом распределении P.

Можно показать, что для любой положительной функции предложения, когда время t, стремится к бесконечности, выборки xᵗ будут стремиться к распределению P(x). На практике, однако, часто бывает трудно проанализировать, сошелся ли алгоритм или нет, и как долго алгоритм должен выполняться. Однако есть определенные правила, которым можно следовать при использовании Метрополиса Гастинг в более высоких измерениях. Я не буду обсуждать их в этом посте, а заинтересованному читателю отсылаю к главе 24 учебника Кевина Мерфи.

Ссылка:

[1] Кевин Мерфи, Машинное обучение: вероятностная перспектива, глава 24.