Монте-Карло әдісі (MCMC): ықтималдық таралымдарынан үлгі алу алгоритмі. Күрделі мәселелерді шешуге, сандық модельдеуге көмектеседі. Metropolis-Hastings алгоритмі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Тәуелді үлгі алу алгоритмдерінің класы
Class of dependent sampling algorithms
Статистикада Марков тізбегі Монте-Карло (MCMC) – ықтималдық таралымынан үлгілер алуға қолданылатын алгоритмдер класы. Ықтималдық таралымы берілген жағдайда, оның элементтерінің таралымы оны жуықтайтын Марков тізбегін құруға болады, яғни Марков тізбегінің тепе-теңдік таралымы мақсатты таралыммен сәйкес келеді. Қадамдардың саны артық болған сайын, үлгінің таралымы нақты қажетті таралымға соғұрлым жақын болады. Марков тізбегі Монте-Карло әдістері тек аналитикалық тәсілдермен зерттеуге тым күрделі немесе тым жоғары өлшемді ықтималдық таралымдарын зерттеу үшін қолданылады. Мұндай Марков тізбектерін құру үшін әртүрлі алгоритмдер бар, оның ішінде Метрополис-Хестингс алгоритмі де бар.
In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that is, the Markov chain's equilibrium distribution matches the target distribution. The more steps that are included, the more closely the distribution of the sample matches the actual desired distribution. Markov chain Monte Carlo methods are used to study probability distributions that are too complex or too highly dimensional to study with analytic techniques alone. Various algorithms exist for constructing such Markov chains, including the Metropolis–Hastings algorithm.
Қолданбалар
MCMC әдістері негізінен көп өлшемді интегралдардың сандық жуықтамаларын есептеу үшін қолданылады, мысалы, Байес статистикасында, есептеу физикасында, есептеу биологиясында және есептеу лингвистикасында. Байес статистикасында Марков тізбегі Монте-Карло әдістері әдетте кейінірек ықтималдық үлестірімдерінің моменттері мен сенімді интервалдарын есептеу үшін қолданылады. MCMC әдістерін қолдану жүздеген немесе мыңдаған белгісіз параметрлер бойынша интегралдауды талап ететін үлкен иерархиялық модельдерді есептеуге мүмкіндік береді. Сирек кездесетін оқиғаларды үлгілеуде олар сирек болатын сәтсіздік аймағын кезең-кезеңімен толтыратын үлгілерді жасау үшін де қолданылады.
MCMC methods are primarily used for calculating numerical approximations of multi dimensional integrals, for example in Bayesian statistics, computational physics, computational biology and computational linguistics. In Bayesian statistics, Markov chain Monte Carlo methods are typically used to calculate moments and credible intervals of posterior probability distributions. The use of MCMC methods makes it possible to compute large hierarchical models that require integrations over hundreds to thousands of unknown parameters. In rare event sampling, they are also used for generating samples that gradually populate the rare failure region.
Жалпы түсініктеме
Марков тізбегі Монте-Карло әдістері белгілі бір функцияға пропорционалды ықтималдық тығыздығы бар үздіксіз кездейсоқ айнымалыдан үлгілер құрайды. Бұл үлгілерді сол айнымалы бойынша интегралды, оның күтілетін мәнін немесе дисперсиясын бағалау үшін қолдануға болады. Іс жүзінде, әдетте бір-бірінен жеткілікті қашықтықта таңдалған нүктелер жиынтығынан басталатын тізбектердің жиынтығы жасалады. Бұл тізбектер – "саяхашылардың" стохастикалық процестері болып табылады, олар интегралға үлкен үлес қосатын жерлерді іздеп, келесі қадамға өтуге мүмкіндік беретін алгоритм бойынша кездейсоқ қозғалады, оларға жоғары ықтималдықтар тағайындайды. Кездейсоқ жүріс Монте-Карло әдістері – кездейсоқ симуляцияның немесе Монте-Карло әдісінің бір түрі. Дегенмен, дәстүрлі Монте-Карло интеграциясында қолданылатын интегралдың кездейсоқ үлгілері статистикалық түрде тәуелсіз болса, MCMC-де қолданылатын үлгілер автокорреляциялық болады. Үлгілердің корреляциясы орташа мәндердің қатесін бағалау кезінде Марков тізбегінің орталық шектеу теоремасын қолдану қажеттілігін тудырады. Бұл алгоритмдер Марков тізбектерін құрады, олардың тепе-теңдік үлестірімі берілген функцияға пропорционалды болады.
Markov chain Monte Carlo methods create samples from a continuous random variable, with probability density proportional to a known function. These samples can be used to evaluate an integral over that variable, as its expected value or variance. Practically, an ensemble of chains is generally developed, starting from a set of points arbitrarily chosen and sufficiently distant from each other. These chains are stochastic processes of "walkers" which move around randomly according to an algorithm that looks for places with a reasonably high contribution to the integral to move into next, assigning them higher probabilities. Random walk Monte Carlo methods are a kind of random simulation or Monte Carlo method. However, whereas the random samples of the integrand used in a conventional Monte Carlo integration are statistically independent, those used in MCMC are autocorrelated. Correlations of samples introduces the need to use the Markov chain central limit theorem when estimating the error of mean values. These algorithms create Markov chains such that they have an equilibrium distribution which is proportional to the function given.
Сәйкестікті азайту
MCMC әдістері көп өлшемді проблемаларды жалпы Монте-Карло алгоритмдерінен жақсы шешу үшін жасалғанмен, өлшемдер саны артқанда олар да өлшемдік қарғысқа ұшырайды: жоғары ықтималдығы бар аймақтар созылып, интегралға аз үлес қосатын кеңістіктің көлемі ұлғайып, олардың арасында жоғалып кетеді. Бұл мәселені шешудің бір жолы – жүргіншінің қадамдарын қысқарту, осылайша ол ең жоғары ықтималдық аймағынан үнемі шығуға тырыспайды, алайда бұл жағдайда процесс жоғары автокорреляциялы және қымбатқа соғады (яғни, дәл нәтиже алу үшін көп қадамдар қажет болады). Гамильтондық Монте-Карло және Ван мен Ландау алгоритмі сияқты күрделі әдістер осы автокорреляцияны азайтудың түрлі жолдарын пайдаланады, сонымен бірге процесті интегралға үлкен үлес қосатын аймақтарда ұстап тұруға тырысады. Бұл алгоритмдер көбінесе күрделі теорияға негізделген және іске асыруы қиын, бірақ олар әдетте жылдамырақ конвергенциялайды.
While MCMC methods were created to address multi dimensional problems better than generic Monte Carlo algorithms, when the number of dimensions rises they too tend to suffer the curse of dimensionality: regions of higher probability tend to stretch and get lost in an increasing volume of space that contributes little to the integral. One way to address this problem could be shortening the steps of the walker, so that it does not continuously try to exit the highest probability region, though this way the process would be highly autocorrelated and expensive (i. e. many steps would be required for an accurate result). More sophisticated methods such as Hamiltonian Monte Carlo and the Wang and Landau algorithm use various ways of reducing this autocorrelation, while managing to keep the process in the regions that give a higher contribution to the integral. These algorithms usually rely on a more complicated theory and are harder to implement, but they usually converge faster.
Кездейсоқ жүру
Метрополис–Хестингс алгоритмі: Бұл әдіс жаңа қадамдар үшін ұсыныстың тығыздығын пайдаланып және ұсынылған кейбір қадамдарды қабылдамау әдісін қолдана отырып, Марков тізбегін жасайды. Бұл, шын мәнінде, ең алғашқы және қарапайым MCMC (Метрополис алгоритмі) және төменде тізілген көптеген жаңа баламаларды қамтитын жалпы құрылым. Гиббс үлгілеуі: Мақсатты үлестірім көп өлшемді болғанда, Гиббс үлгілеу алгоритмі басқа координаттар белгілі болғанда әрбір координатаны толық шартты үлестірімінен жаңартады. Гиббс үлгілеуін Метрополис–Хестингс алгоритмінің ерекше жағдайы ретінде қарастыруға болады, онда қабылдау деңгейі біркелкі түрде 1-ге тең. Толық шартты үлестірімдерден үлгі алу оңай болмаған жағдайда, Гиббс ішіндегі басқа үлгілеушілер қолданылады (мысалы, қараңыз). Гиббс үлгілеуінің танымал болуының бір себебі – ол ешқандай «реттеу» қажет етпейді. Гиббс үлгілеу алгоритмінің құрылымы координаталық өрлеудің вариациялық қорытындысына өте ұқсас, себебі екі алгоритм де жаңарту процедурасында толық шартты үлестірімдерді пайдаланады. Метрополис реттелген Лангевин алгоритмі және лог-мақсатты тығыздықтың градиентіне (немесе екінші туындысына) сүйенетін және жоғары ықтималдық тығыздығына қарай қадамдарды ұсынуға арналған басқа әдістер. Гамильтондық (немесе гибридтік) Монте-Карло (HMC): Кездейсоқ серуендеуден аулақ болу үшін қосалқы импульс векторын енгізеді және Гамильтондық динамиканы іске асырады, сондықтан потенциалдық энергия функциясы мақсатты тығыздық болып табылады. Импульс үлгілерінен кейін құтылады. Гибридтік Монте-Карлоның нәтижесі – ұсыныстар үлгі кеңістігінде үлкен қадамдармен жылжиды; сондықтан олар аз корреляцияланған және мақсатты үлестірімге жылдамрақ жақындайды. Псевдомаргиналды Метрополис–Хестингс: Бұл әдіс мақсатты үлестірімнің тығыздығын бағалауды бейтарап бағалаумен алмастырады және мақсатты тығыздық аналитикалық түрде қолжетімді болмаған кезде пайдалы, мысалы, жасырын айнымалы модельдерде. Кесінді үлгілеуі: Бұл әдіс оның тығыздық функциясының графигі астындағы аймақтан біркелкі үлгі алу арқылы үлестірімнен үлгі алу принципіне негізделген. Ол тік бағытта біркелкі үлгі алуді және ағымдағы тік жағдаймен анықталған көлденең «кесіндіден» біркелкі үлгі алуді ауыстырады. Көп реттегі Метрополис: Бұл әдіс – әр нүктеде бірнеше рет сынақ жасауға мүмкіндік беретін Метрополис–Хестингс алгоритмінің нұсқасы. Әр итерацияда үлкен қадамдар жасауға мүмкіндік беру арқылы, ол өлшемділік қарғысын жеңілдетуге көмектеседі. Кері секіру: Бұл әдіс – кеңістіктің өлшемділігін өзгертетін ұсыныстарға мүмкіндік беретін Метрополис–Хестингс алгоритмінің түрі. Өлшемділігін өзгертетін Марков тізбегі Монте-Карло әдістері статистикалық физикадағы кейбір мәселелерде ұзақ уақыттан бері қолданылып келеді, онда кейбір мәселелер үшін үлестірім үлкен канондық жиынтық болып табылады (мысалы, қораптағы молекулалардың саны өзгермелі болғанда). Бірақ кері секіру нұсқасы Марков тізбегі Монте-Карло немесе Гиббс үлгілеуін Дирихле процесін немесе қытай мейрамханасы процесін қамтитын бейестік емес модельдерде қолдану кезінде пайдалы, онда араласу компоненттерінің/кластерлерінің/т.б. саны деректерден автоматты түрде анықталады.
Metropolis–Hastings algorithm: This method generates a Markov chain using a proposal density for new steps and a method for rejecting some of the proposed moves. It is actually a general framework which includes as special cases the very first and simpler MCMC (Metropolis algorithm) and many more recent alternatives listed below. Gibbs sampling: When target distribution is multi dimensional, Gibbs sampling algorithm updates each coordinate from its full conditional distribution given other coordinates. Gibbs sampling can be viewed as a special case of Metropolis–Hastings algorithm with acceptance rate uniformly equal to 1. When drawing from the full conditional distributions is not straightforward other samplers within Gibbs are used (e. g., see ). Gibbs sampling is popular partly because it does not require any 'tuning'. Algorithm structure of the Gibbs sampling highly resembles that of the coordinate ascent variational inference in that both algorithms utilize the full conditional distributions in the updating procedure. Metropolis adjusted Langevin algorithm and other methods that rely on the gradient (and possibly second derivative) of the log target density to propose steps that are more likely to be in the direction of higher probability density. Hamiltonian (or hybrid) Monte Carlo (HMC): Tries to avoid random walk behaviour by introducing an auxiliary momentum vector and implementing Hamiltonian dynamics, so the potential energy function is the target density. The momentum samples are discarded after sampling. The result of hybrid Monte Carlo is that proposals move across the sample space in larger steps; they are therefore less correlated and converge to the target distribution more rapidly. Pseudo marginal Metropolis–Hastings: This method replaces the evaluation of the density of the target distribution with an unbiased estimate and is useful when the target density is not available analytically, e. g. latent variable models. Slice sampling: This method depends on the principle that one can sample from a distribution by sampling uniformly from the region under the plot of its density function. It alternates uniform sampling in the vertical direction with uniform sampling from the horizontal 'slice' defined by the current vertical position. Multiple try Metropolis: This method is a variation of the Metropolis–Hastings algorithm that allows multiple trials at each point. By making it possible to take larger steps at each iteration, it helps address the curse of dimensionality. Reversible jump: This method is a variant of the Metropolis–Hastings algorithm that allows proposals that change the dimensionality of the space. Markov chain Monte Carlo methods that change dimensionality have long been used in statistical physics applications, where for some problems a distribution that is a grand canonical ensemble is used (e. g., when the number of molecules in a box is variable). But the reversible jump variant is useful when doing Markov chain Monte Carlo or Gibbs sampling over nonparametric Bayesian models such as those involving the Dirichlet process or Chinese restaurant process, where the number of mixing components/clusters/etc. is automatically inferred from the data.
Бір-бірімен әрекеттесетін бөлшектер әдістері
Өзара әсерлесетін МККМ әдістері – бұл орташа өрістегі бөлшектер әдістерінің бір класы, олар іріктеудің күрделілігі артатын ықтималдық үлестірілімдерінің тізбегінен кездейсоқ үлгілер алуға арналған. Бұл ықтималдық модельдерге уақыт горизонты ұлғаятын жол кеңістігінің күй модельдері, жартылай байқаулар тізбегіне қатысты артқы үлестірімдер, шартты үлестірімдер үшін шектеу деңгейлерінің жиынтығын арттыру, кейбір Болцманн-Гиббс үлестірімдерімен байланысты температураның төмендеу кестелері және тағы да басқалары кіреді. Принцип бойынша, кез келген Марков тізбегі Монте-Карло сынамалаушысын өзара әсерлесетін Марков тізбегі Монте-Карло сынамалаушысына айналдыруға болады. Бұл өзара әсерлесетін Марков тізбегі Монте-Карло сынамалаушыларын Марков тізбегі Монте-Карло сынамалаушыларының тізбесін параллель түрде іске қосудың бір жолы ретінде қарастыруға болады. Мысалы, өзара әсерлесетін симуляцияланған оттыру алгоритмдері тәуелсіз Метрополис-Хестингс қимылдарына негізделген, олар тізбектеп өзара әрекеттеседі және таңдауды қайта үлгілеу механизмімен жұмыс істейді. Традициялық Марков тізбегі Монте-Карло әдістерінен айырмашылығы, осы кластағы өзара әсерлесетін Марков тізбегі Монте-Карло сынамалаушыларының дәлдік параметрі тек өзара әсерлесетін Марков тізбегі Монте-Карло сынамалаушыларының санына байланысты. Бұл жетілдірілген бөлшектер әдістемелері Фейнман-Как бөлшектер модельдері класына жатады, сонымен қатар Байестік қорытынды және сигналды өңдеу қауымдастықтарында ретті Монте-Карло немесе бөлшектер сүзгісі әдістері деп те аталады. Өзара әсерлесетін Марков тізбегі Монте-Карло әдістерін Марков тізбегі Монте-Карло мутациялары бар мутациялық таңдау генетикалық бөлшектер алгоритмі ретінде де қарастыруға болады.
Interacting MCMC methodologies are a class of mean field particle methods for obtaining random samples from a sequence of probability distributions with an increasing level of sampling complexity. These probabilistic models include path space state models with increasing time horizon, posterior distributions w. r. t. sequence of partial observations, increasing constraint level sets for conditional distributions, decreasing temperature schedules associated with some Boltzmann–Gibbs distributions, and many others. In principle, any Markov chain Monte Carlo sampler can be turned into an interacting Markov chain Monte Carlo sampler. These interacting Markov chain Monte Carlo samplers can be interpreted as a way to run in parallel a sequence of Markov chain Monte Carlo samplers. For instance, interacting simulated annealing algorithms are based on independent Metropolis–Hastings moves interacting sequentially with a selection resampling type mechanism. In contrast to traditional Markov chain Monte Carlo methods, the precision parameter of this class of interacting Markov chain Monte Carlo samplers is only related to the number of interacting Markov chain Monte Carlo samplers. These advanced particle methodologies belong to the class of Feynman–Kac particle models, also called Sequential Monte Carlo or particle filter methods in Bayesian inference and signal processing communities. Interacting Markov chain Monte Carlo methods can also be interpreted as a mutation selection genetic particle algorithm with Markov chain Monte Carlo mutations.
Квази-Монте-Карло
Квази Монте-Карло әдісі – кездейсоқ сандардың орнына төмен сәйкессіздік тізбектерін пайдаланатын, қалыпты Монте-Карло әдісінің аналогы. Koksma–Hlawka теңсіздігімен сандық түрде көрсетілгендей, бұл нақты кездейсоқ үлгі алудан гөрі жылдам төмендейтін интеграция қатесін береді. Тәжірибе жүзінде бұл бағалау қатесін және конвергенция уақытын бірнеше есеге азайтуға мүмкіндік береді. Марков тізбегі квази Монте-Карло әдістері, мысалы, Array–RQMC әдісі, квази-Монте-Карло және Марков тізбегінің модельдеуін біріктіреді, тізбектерді бір уақытта модельдеу арқылы тізбектің нақты таралуын қарапайым MCMC-ге қарағанда жақсырақ жақындастырады. Тәжірибелік эксперименттерде, күйдің функциясының орташа мәнінің дисперсиясы Монте-Карло жылдамдығының орнына кейде одан да жылдам немесе тіпті одан да жылдам конвергенцияланады.
The quasi Monte Carlo method is an analog to the normal Monte Carlo method that uses low discrepancy sequences instead of random numbers. It yields an integration error that decays faster than that of true random sampling, as quantified by the Koksma–Hlawka inequality. Empirically it allows the reduction of both estimation error and convergence time by an order of magnitude. Markov chain quasi Monte Carlo methods such as the Array–RQMC method combine randomized quasi–Monte Carlo and Markov chain simulation by simulating chains simultaneously in a way that better approximates the true distribution of the chain than with ordinary MCMC. In empirical experiments, the variance of the average of a function of the state sometimes converges at rate or even faster, instead of the Monte Carlo rate.
Ынтымақтастық
Көбінесе қажетті қасиеттері бар Марков тізбегін құру қиын емес. Ең қиын мәселе – қабылдау қателігінің шегінде стационарлық үлестірілімге жету үшін қанша қадам қажет екенін анықтау. Жақсы тізбек жылдам араласады: стационарлық таралу кез келген бастапқы нүктеден тез жетеді. Конвергенцияны бағалаудың стандартты эмпирикалық әдісі – бірнеше тәуелсіз симуляцияланған Марков тізбегін іске қосып, барлық іріктемеленген параметрлер үшін тізбек ішіндегі және тізбектер арасындағы дисперсиялардың қатынасы 1-ге жақын екенін тексеру. Әдетте, Марков тізбегі Монте-Карло үлгілеуі тек мақсатты үлестірілімді жуықтап ғана бере алады, себебі бастапқы нүктенің әрқашан қалдық әсері болады. Марков тізбегіне негізделген күрделі алгоритмдер, мысалы, өткенмен байланыстыру (coupling from the past), қосымша есептеулер мен шексіз (бірақ күту бойынша шекті) жұмыс уақытының есебінен нақты үлгілерді жасауға мүмкіндік береді. Көптеген кездейсоқ серуен Монте-Карло әдістері тепе-теңдік үлестірілімінде салыстырмалы түрде кішкентай қадамдармен қозғалады, қадамдардың бір бағытта жасалуына ешқандай бейімділік жоқ. Бұл әдістерді іске асыру және талдау оңай, бірақ өкінішке орай, серуеншінің барлық кеңістікті зерттеуіне көп уақыт қажет болуы мүмкін. Серуенші көбінесе кері қайтып, бұрын басып өткен жерді қайтадан қарастырады. Конвергенцияны одан әрі қарастыру Марков тізбегінің орталық шек теоремасында қарастырылады. Метрополис-Хестингс алгоритмінің конвергенциясы және стационарлығына қатысты теорияны қараңыз.
Usually it is not hard to construct a Markov chain with the desired properties. The more difficult problem is to determine how many steps are needed to converge to the stationary distribution within an acceptable error. A good chain will have rapid mixing: the stationary distribution is reached quickly starting from an arbitrary position. A standard empirical method to assess convergence is to run several independent simulated Markov chains and check that the ratio of inter chain to intra chain variances for all the parameters sampled is close to 1. Typically, Markov chain Monte Carlo sampling can only approximate the target distribution, as there is always some residual effect of the starting position. More sophisticated Markov chain Monte Carlo based algorithms such as coupling from the past can produce exact samples, at the cost of additional computation and an unbounded (though finite in expectation) running time. Many random walk Monte Carlo methods move around the equilibrium distribution in relatively small steps, with no tendency for the steps to proceed in the same direction. These methods are easy to implement and analyze, but unfortunately it can take a long time for the walker to explore all of the space. The walker will often double back and cover ground already covered. Further consideration of convergence is at Markov chain central limit theorem. See for a discussion of the theory related to convergence and stationarity of the Metropolis–Hastings algorithm.