Введение
Алгоритм Монте-Карло
В статистике и статистической физике алгоритм Метрополиса — Хестингса является методом Монте-Карло на основе цепей Маркова (MCMC) для получения последовательности случайных выборок из распределения вероятностей, из которого прямой отбор проб затруднен. Новые выборки добавляются в последовательность в два этапа: сначала предлагается новая выборка на основе предыдущей, затем предложенная выборка либо принимается и добавляется в последовательность, либо отклоняется в зависимости от значения функции вероятности в этой точке. Полученная последовательность может быть использована для аппроксимации распределения (например, для построения гистограммы) или для вычисления интеграла (например, математического ожидания). Алгоритмы Метрополиса — Хестингса и другие алгоритмы MCMC обычно используются для выборки из многомерных распределений, особенно когда размерность высока. Для одномерных распределений обычно существуют другие методы (например, адаптивный отбор-отторжение), которые могут напрямую возвращать независимые выборки из распределения, и они не подвержены проблеме автокорреляции выборок, свойственной методам MCMC.
История
Алгоритм частично назван в честь Николаса Метрополиса, первого соавтора статьи 1953 года под названием «Вычисление уравнений состояния с помощью быстрых вычислительных машин» совместно с Арианной В. Розенблут, Маршаллом Розенблутом, Августой Х. Теллер и Эдвардом Теллером. В течение многих лет алгоритм был известен просто как алгоритм Метрополиса. В статье алгоритм был предложен для случая симметричных предложений, но в 1970 году У. К. Гастингс расширил его на более общий случай. У алгоритмов Metropolis–Hastings и других MCMC есть ряд недостатков: выборки автокоррелированы. Даже если в долгосрочной перспективе они корректно следуют распределению, набор близких выборок будет коррелировать друг с другом и не будет правильно отражать распределение. Это означает, что эффективный размер выборки может быть значительно меньше, чем количество фактически взятых выборок, что приводит к большим ошибкам. Хотя цепь Маркова в конечном итоге сходится к желаемому распределению, начальные выборки могут следовать совершенно иному распределению, особенно если начальная точка находится в области низкой плотности. В результате обычно требуется период прогрева, в течение которого начальное количество выборок отбрасывается. С другой стороны, большинство простых методов отбора проб с отклонением страдают от «проклятия размерности», когда вероятность отклонения экспоненциально возрастает с увеличением числа измерений. Metropolis–Hastings, наряду с другими методами MCMC, в меньшей степени подвержены этой проблеме и поэтому часто являются единственным доступным решением, когда число измерений распределения, из которого производится отбор проб, велико. В результате методы MCMC часто являются предпочтительными для получения выборок из иерархических байесовских моделей и других многомерных статистических моделей, которые в настоящее время используются во многих областях науки. В многомерных распределениях классический алгоритм Metropolis–Hastings, описанный выше, предполагает выбор новой многомерной точки выборки. Когда число измерений велико, найти подходящее распределение перемещения может быть сложно, поскольку различные отдельные измерения ведут себя по-разному, и ширина перемещения (см. выше) должна быть «точно подобрана» для всех измерений одновременно, чтобы избежать чрезмерно медленного перемешивания. Альтернативный подход, который часто работает лучше в таких ситуациях, известный как выборка Гиббса, предполагает выбор новой выборки для каждого измерения отдельно от других, а не выборку для всех измерений сразу. Таким образом, задача выборки из потенциально многомерного пространства сводится к набору задач выборки из пространства малой размерности. Это особенно применимо, когда многомерное распределение состоит из набора отдельных случайных переменных, в которых каждая переменная обусловлена только небольшим числом других переменных, как это обычно бывает в типичных иерархических моделях. Затем отдельные переменные отбираются по одной, при этом каждая переменная обусловлена последними значениями всех остальных. Для выбора этих отдельных выборок могут использоваться различные алгоритмы, в зависимости от точной формы многомерного распределения: некоторые варианты включают адаптивные методы отбора проб с отклонением, простой одномерный шаг Metropolis–Hastings или выборку среза.
The samples are autocorrelated. Even though over the long term they do correctly follow , a set of nearby samples will be correlated with each other and not correctly reflect the distribution. This means that effective sample sizes can be significantly lower than the number of samples actually taken, leading to large errors. Although the Markov chain eventually converges to the desired distribution, the initial samples may follow a very different distribution, especially if the starting point is in a region of low density. As a result, a burn in period is typically necessary, where an initial number of samples are thrown away. On the other hand, most simple rejection sampling methods suffer from the "curse of dimensionality", where the probability of rejection increases exponentially as a function of the number of dimensions. Metropolis–Hastings, along with other MCMC methods, do not have this problem to such a degree, and thus are often the only solutions available when the number of dimensions of the distribution to be sampled is high. As a result, MCMC methods are often the methods of choice for producing samples from hierarchical Bayesian models and other high dimensional statistical models used nowadays in many disciplines. In multivariate distributions, the classic Metropolis–Hastings algorithm as described above involves choosing a new multi dimensional sample point. When the number of dimensions is high, finding the suitable jumping distribution to use can be difficult, as the different individual dimensions behave in very different ways, and the jumping width (see above) must be "just right" for all dimensions at once to avoid excessively slow mixing. An alternative approach that often works better in such situations, known as Gibbs sampling, involves choosing a new sample for each dimension separately from the others, rather than choosing a sample for all dimensions at once. That way, the problem of sampling from potentially high dimensional space will be reduced to a collection of problems to sample from small dimensionality. This is especially applicable when the multivariate distribution is composed of a set of individual random variables in which each variable is conditioned on only a small number of other variables, as is the case in most typical hierarchical models. The individual variables are then sampled one at a time, with each variable conditioned on the most recent values of all the others. Various algorithms can be used to choose these individual samples, depending on the exact form of the multivariate distribution: some possibilities are the adaptive rejection sampling methods, a simple one dimensional Metropolis–Hastings step, or slice sampling.
Формальное выведение
Целью алгоритма Метрополиса–Хестингса является генерация набора состояний в соответствии с заданным распределением. Для этого алгоритм использует марковский процесс, который асимптотически достигает уникального стационарного распределения, так что для распределений на дискретных пространствах состояний, его порядок должен соответствовать времени автокорреляции марковского процесса. Если это значение слишком мало, цепь будет перемешиваться медленно (то есть, скорость принятия будет высокой, но последовательные выборки будут медленно перемещаться в пространстве состояний, и цепь будет медленно сходиться к ). С другой стороны, если это значение слишком велико, скорость принятия будет очень низкой, поскольку предложенные варианты, скорее всего, попадут в области с гораздо меньшей плотностью вероятности, следовательно, будет очень мало, и цепь снова будет сходиться очень медленно. Обычно распределение предложений настраивается таким образом, чтобы алгоритм принимал около 30% всех выборок – в соответствии с теоретическими оценками, упомянутыми в предыдущем абзаце.
if is too large, the acceptance rate will be very low because the proposals are likely to land in regions of much lower probability density, so will be very small, and again the chain will converge very slowly. One typically tunes the proposal distribution so that the algorithms accepts on the order of 30% of all samples – in line with the theoretical estimates mentioned in the previous paragraph.