Току-що сте се сдобили с хубав набор от данни, например цени на недвижими имоти с характеристиките на домовете. Въпрос, който можете да си зададете е: Как да предвидя цената на къща въз основа на нейните характеристики?

Първият модел, който идва на ум, би бил линеен модел, който приема характеристиките като входни данни. Да кажем, че имаме достъп до следните характеристики:

  • Квадратура на къщата
  • Брой спални
  • Локализация
  • Година на построяване

Проблемът с прогнозирането на цените на жилищата с такива набори от данни е интензивно изследван (https://www.kaggle.com/c/house-prices-advanced-regression-techniques) и е възможно да се получи точен модел. Използвам тази рамка като модел играчка, за да подчертая колко лесно параметрите могат да бъдат свързани в модел. Размерът на къщата и броят на спалните са свързани, но нито една от тях не може наистина да се използва, за да замени другата в оценката, поради което оценката на параметрите на модела може да бъде затруднена. По-специално, методите за вземане на проби като вериги на Марков Монте-Карло могат да бъдат неефективни, когато целевото разпределение на параметрите е неизвестно. Ако това е проблем, който може да не възникне при изчисляване на цените на жилищата, следователно е необходимо да го имате предвид, когато монтирате по-сложни модели.

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

Верига Марков Монте-Карло

MCMC е метод за вземане на проби, който е широко използван в байесовската статистика, особено когато се оценяват постериорни предишни стойности. С едно изречение MCMC може да се счита за процес на произволно ходене, използван за оценка на целево разпределение (разпределението на параметрите). Metropolis-Hastings е най-използваният алгоритъм в класа 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 и Bayesian алгоритмите са наистина ефективни при монтиране на параметри за голямо разнообразие от модели, високата размерност и корелацията могат да доведат до безкрайно време за изчисление. Точно тогава еволюционните алгоритми идват на помощ. Използвайки алгоритъма MCMC за диференциална еволюция, различните вериги могат да се информират взаимно за корелацията на параметрите, като по този начин правят конвергенцията на алгоритъма по-бърза. Така че следващия път, когато имате корелация между параметрите на вашия модел, опитайте да добавите DE-MCMC към вашия набор от байесови инструменти.

Препратки

[1] Неделман, Дж. Р. Рецензия на книгата: „Байесов анализ на данни,“ второ издание от А. Гелман, Дж. Б. Карлин, Х. С. Стърн и Д.Б. Rubin Chapman & Hall/CRC, 2004. Изчислителна статистика 20, 655–657 (2005). https://doi.org/10.1007/BF02741321

[2] Braak, Cajo J. F.. „Версия на Марковска верига Монте Карло на генетичния алгоритъм Differential Evolution: easy Bayesian computing for real parameter spaces.“ Статистика и изчисления 16 (2006): 239–249.