Вы только что получили себе хороший набор данных, например, цены на недвижимость с характеристиками домов. Вы можете задать себе вопрос: как мне предсказать цену дома на основе его характеристик?

Первой моделью, которая приходит на ум, будет линейная модель, использующая характеристики в качестве входных данных. Допустим, у нас есть доступ к следующим характеристикам:

  • Площадь дома
  • Количество спален
  • Локализация
  • Год постройки

Проблема прогнозирования цен на жилье с такими наборами данных интенсивно изучается (https://www.kaggle.com/c/house-prices-advanced-regression-techniques), и можно получить точную модель. Я использую этот фреймворк в качестве игрушечной модели, чтобы показать, насколько легко можно сопоставить параметры в модели. Размер дома и количество спален коррелируют, но ни один из них не может реально использоваться для замены другого в оценке, поэтому оценка параметров модели может оказаться сложной. В частности, методы выборки, такие как Цепи Маркова Монте-Карло, могут быть неэффективными, если целевое распределение параметров неизвестно. Если это проблема, которая может не возникнуть при оценке цен на жилье, ее необходимо иметь в виду при подборе более сложных моделей.

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

Цепь Маркова Монте-Карло

MCMC — это метод выборки, который широко используется в байесовской статистике, особенно при оценке апостериорных априорных значений. Одним предложением MCMC можно рассматривать как процесс случайного блуждания, используемый для оценки целевого распределения (распределения параметров). Алгоритм Метрополиса-Гастингса является наиболее часто используемым алгоритмом в классе MCMC [1].

Пусть P = (p1, p2,…) вектор параметров нашей модели. Затем алгоритм выбирает начальное значение P1 для параметров и выбирает возможное значение P*, используя предлагаемое распределение P =* K(P1). Типичное распределение предложений обычно представляет собой распределение Гаусса с центром вокруг P1. После этого кандидат P* принимается с вероятностью:

Разложим эту формулу. M(P*) представляет целевое распределение. Например, в случае подбора модели целевое распределение может быть экспоненциальной функцией ошибки. Использование экспоненциальной функции позволяет перейти от функции ошибок к распределению вероятностей. q(Pt|P*) представляет собой плотность распределения предложений, оцененную в Pt с параметрами П*. Другими словами, он показывает, насколько вероятно, что будет выбран Pt, если мы будем выбирать из P*. Этот член необходим для стационарности алгоритма.

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

Ниже приведен пример кода Python с использованием пакета mc3 (модифицированного из их руководства) для моделирования алгоритма MCMC для соответствия параметрам квадратичной модели:

Теперь, если мы вернемся к случаю, когда некоторые наши параметры коррелированы. Если распределение предложений явно не учитывает корреляции между параметрами, то многие значения-кандидаты не будут лежать в целевом распределении. Например, на рисунке ниже серое облако представляет собой вымышленное распределение двух параметров. Круг представляет распределение предложения. Большая часть круга лежит за пределами серого распределения.

Это приведет к значительному количеству отказов, а MCMC займет очень много времени. Таким образом, не всегда может быть уместно использовать эту байесовскую технику для соответствия вашей модели. Хорошая новость заключается в том, что существует класс алгоритмов, которые могут решать многомерные задачи с высокой степенью корреляции: MCMC на основе популяции.

Диффузионная эволюция Цепи Маркова Монте-Карло

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

Объединение значений осуществляется следующим образом. P_k представляет текущее состояние цепочки k. Затем значение-кандидат, P*, генерируется с использованием различий между состояниями двух цепочек, выбранных случайным образом, P_m и P_n. Вкратце процесс выглядит следующим образом:

Где коэффициент ɣ представляет скорость прыжка. Скорость принятия нового кандидата аналогична алгоритму MCMC, использующему, например, правило Метрополиса-Гастингса. Эмпирическое правило использования скорости прыжка:

с d количество размерностей параметров. Алгоритм DE-MCMC представлен на рисунке ниже:

Почему DE-MCMC эффективен при выборке по коррелирующим параметрам?

Различные цепочки MCMC используются для информирования состояний в одной цепочке. Таким образом, корреляции между цепочками (следовательно, корреляции между выборками) напрямую используются для информирования о состояниях цепочек. Использование разницы между цепочками для создания новых значений-кандидатов позволяет естественным образом учитывать корреляции между параметрами. Кроме того, значения по умолчанию для параметров цепочки хорошо работают для множества задач, что делает его хорошим алгоритмом для многомерных задач.

Алгоритм DE-MCMC можно реализовать с помощью пакета MC3 с примером кода, аналогичным предыдущему, указав demc в качестве алгоритма выборки MCMC. Это приводит к следующей подгонке предыдущей квадратичной модели:

Используя предыдущий пакет для выполнения алгоритма MCMC, можно получить легкий доступ к апостериорным распределениям параметров, парным корреляциям и дополнительной информации. Если вы хотите углубиться в это, вы можете прочитать их руководство по адресу https://mc3.readthedocs.io/en/latest/mcmc_tutorial.html#sampler-algorithm.

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

Рекомендации

[1] Недельман, Дж. Р. Рецензия на книгу: Байесовский анализ данных, второе издание А. Гельмана, Дж. Б. Карлин, Х.С. Стерн и Д.Б. Рубин Чепмен и Холл/CRC, 2004. Вычислительная статистика 20, 655–657 (2005). https://doi.org/10.1007/BF02741321

[2] Браак, Кахо Дж. Ф.. «Версия Монте-Карло цепи Маркова генетического алгоритма дифференциальной эволюции: простые байесовские вычисления для пространств с реальными параметрами». Статистика и вычисления 16 (2006): 239–249.