Кіріспе
Монте-Карло алгоритмі
Статистика және статистикалық физика салаларында Метрополис-Хестингс алгоритмі – ықтималдық таралымынан тікелей үлгі алу қиын кездейсоқ үлгілер тізбегін алуға арналған Марков тізбегі Монте-Карло (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.