MCMC, или как бродить с умом.
обычный Монте-Карло тычет в пространство случайными точками. но что, если нужное распределение слишком сложное, чтобы тыкать наугад? тогда из точек делают цепь: блуждание, которое само стекается туда, где плотность выше. так Марков встречает Монте-Карло — буквально в названии.
| тема | MCMC · Метрополис–Гастингс · цепи Маркова · байесовский вывод · стационарное распределение |
| читать | ~7 минут |
| связано | Марков · Монте-Карло · случайное блуждание · симуляция · Байес |
Базовый Монте-Карло прост: разбросай случайные точки равномерно и усредни. Но он работает, пока ты умеешь эти точки бросать. А чаще всего распределение, которое тебя интересует, известно лишь «с точностью до множителя»: ты можешь сказать, во сколько раз одна точка вероятнее другой, но не можешь сэмплировать из него напрямую — нормировка неизвестна, измерений сотни, форма дикая. Равномерные тычки тут бесполезны: почти все попадут туда, где плотность ничтожна.
Идея MCMC — Markov Chain Monte Carlo — в том, чтобы не бросать точки независимо, а пустить блуждание. Стоишь в какой-то точке, предлагаешь шаг по соседству — и решаешь, принять его или остаться. Правило приёма хитрое: если шаг ведёт туда, где плотность выше, принимаешь всегда; если ниже — принимаешь иногда, с вероятностью, равной отношению плотностей2. В среднем блуждание тянет вверх по плотности, но иногда спускается — поэтому не застревает в одном пике, а обходит всё распределение, задерживаясь в каждом месте ровно пропорционально его вероятности.
Не бросать точки в распределение, а построить блуждание, для которого это распределение — дом, куда оно всегда возвращается.
Магия в том, что такая цепь Маркова имеет стационарное распределение — то самое, которое тебе нужно1. Дай ей побродить подольше — и доля времени, проведённого в каждой области, сойдётся к её вероятности. Ты не сэмплировал из распределения, ты построил процесс, для которого оно — точка равновесия, и просто подождал. Случайное блуждание из соседнего эссе тут обретает цель: его учат стекаться куда надо.
Придумали это там же, где и Монте-Карло, — в Лос-Аламосе. Алгоритм Метрополиса (1953) вышел из той же группы физиков атомного проекта: они моделировали жидкость в равновесии и поняли, что не нужно симулировать точную физику — достаточно построить цепь с тем же равновесным распределением и дать ей сойтись3. В 1970-м Гастингс обобщил метод (отсюда «Метрополис–Гастингс»), но статистики по-настоящему распробовали MCMC только после 1990-го — когда он стал главным мотором байесовского вывода4.
Сегодня MCMC — рабочая лошадь везде, где распределение слишком сложное для формулы: байесовские модели, статистическая физика, фитирование космологических данных, вероятностное программирование. Это прямой наследник всей линии: случайность (Монте-Карло), у которой память сделана марковской (шаг зависит только от текущего места), и блуждание, которому задали правильное равновесие. Цена та же, что у всякой симуляции, — нужно дать цепи время «разогреться» и убедиться, что она действительно обошла всё, а не залипла в одном углу.
В этом изяществе вся идея: чтобы изучить недостижимое распределение, не надо его покорять формулой. Надо построить странника, для которого оно — родина, и отпустить бродить. Достаточно долго, достаточно честно — и маршрут сам нарисует карту плотности. Марков дал блужданию правила, Монте-Карло — смысл считать по нему средние; вместе они умеют то, чего не может ни формула, ни наивный случайный тык.