Մետրոպոլիս-Հաստինգսի ալգորիթմ

The Proposal distribution Q proposes the next point that the random walk might move to.

Մետրոպոլիս-Հաստինգսի ալգորիթմը, սեմպլիրացման ալգորիթմ է , որն հիմնականում օգտագործվում է բաշխման բարդ ֆունկցիաների համար:Այն մասամբ նման է շեղումներով ընտրության ալգորիթմին, սակայն այստեղ բաշխման օժանդակ ֆունկցիան փոխվում է ժամանակի ընթացքում է:Առաջին անգամ ալգորիթմը լույս է տեսել Նիկոլաս Մետրոպոլիսի կողմից 1953 թվին, և հետո ընդհանրացվել Հաստինգսի կողմից 1970 թվին. սեմպլիրացում ըստ Գիբբսի հանդիսանում է Մետրոպոլիս-Հաստինգսի ալգորիթմի մասնավոր դեպք,և ավելի հայտնի է իր պարզությամբ և արագությամբ, չնայած առավել հազվադեպ է կիրառվում:

Մետրոպոլիս-Գաստինգի ալգորիթմը թույլ է տալիս սեմպլիրացնել ցանկացած բաշխման ֆունկցիա:Այն հիմնված է Մարկովի շղթայի ստեղծման վրա, այսինքն ալգորիթմի յուրաքանչյուր քայլին նոր ընտրված $x^{t+1}$-ի իմաստը կախված է նախորդ $x^{t}$-ից.Ալգորիթմն օգտագործում է $Q(x'|x^{t})$ բաշխման օժանդակ ֆունկցիան, որը կախված է $x^{t}$-ից,և որի համար գեներացիան выборку հեշտ է (օրինակ, նորմալ բաշխումը). Այս ֆունկցիայի համար ամեն քայլին գեներացվում է $x'$-ի պատահական իմաստ:Հետո հավանականությամբ`

$u={\frac {P(x')Q(x^{t}|x')}{P(x^{t})Q(x'|x^{t})}}$

( կամ 1 հավանականությամբ եթե $u>1$), ընտրված իմաստը ընդունվում է որպես նոր` $x^{t+1}=x'$, հակառակ դեպքում մնում է նույնը` $x^{t+1}=x^{t}$.

Օրինակ, եթե ընդունենք բաշխման նորմալ ֆունկցիան որպես օժանդակ, ապա

$Q(x'|x^{t})\sim N(x^{t},\sigma ^{2}I)\,\!$ .

Այսպիսի ֆունկցիան տալիս է նոր նշանակություն`կախված նախկին քայլում ստացված նշանակությունից: Ի սկզբանե Մետրոպոլիսի ալգորիթմը պահանջում էր, որ օժանդակ ֆունկցիան լիներ սիմետրիկ` $Q(x',x^{t})=Q(x^{t},x')$, սակայն Գաստինգսի ընդհանրացումը այս սահմանափակումը վերացնում է :

Ալգորիթմ

Ենթադրենք մենք արդեն ընտրել ենք $x^{t}$ նշանակությունը: Մյուս նշանակության ընտրության համար սկզբում $x'$ ֆունկցիայի համար պետք է ստանանք $Q(x'|x^{t})$ պատահական նշանակությունը: Հետո գտնենք $a=a_{1}a_{2}$ ածանցյալը, որտեղ

$a_{1}={\frac {P(x')}{P(x^{t})}}$

հանդիսանում է միջանկյալ և նախկին նշանակությունների միջև հավանականությունների հարաբերակցություն, իսկ

$a_{2}={\frac {Q(x^{t}|x')}{Q(x'|x^{t})}}$ սա հարաբերություն է հավանականությունների միջև ` անցնելով $x'$ -ից $x^{t}$ կամ հակառակը. Եթե $Q$ սիմետրիկ է, ապա երկրորդ բազմապատկիչը հավասար է 1. Պատահական նշանակությունը նոր քայլում ընտրվում է կանոններին համապտասխան`

${\begin{matrix}{\mbox{If }}a\geq 1:&\\&x^{t+1}=x',\end{matrix}}$

${\begin{matrix}{\mbox{and if }}a<1:&\\&x^{t+1}=\left\{{\begin{matrix}x'{\mbox{ with probability }}a\\x^{t}{\mbox{ with probability }}1-a.\end{matrix}}\right.\end{matrix}}$

Ալգորիթմը ծագում է $x^{0}$–ի պատահական նշանակությունից, և սկզբում մի քանի քայլ գործում է միայնակ, որպեսզի մոռացվի սկզբնական նշանակությունը:

Ամենալավը ալգորիթմը գործում է այն ժամանակ, երբ օժանդակ ֆունկցիայի ձևը մոտ է նպատակայինին $P$ ֆունկցիայի ձևին. : Սակայն այս չճշտվածությանը հասնելը մասամբ անհնար է: Խնդրի լուծման համար օժանդակ ֆունկցիան հարմարեցնում են ալգորիթմի աշխատանքի նախապատրաստական փուլի ընթացքում: Օրինակ, նորմալ բաշխման համար $\sigma ^{2}$ պարամետրը ընտրում են այնպես , որ ընդունած պատահական նշանակությունների բաժինը (այսինքն նրանց, որոնց համար $x^{t+1}=x'$)-ը մոտ լինի 60%. Եթե $\sigma ^{2}$ -ը չափազանց փոքր է, ապա նշանակությունները կստացվեն շատ մոտ և ընդունվածների բաժինը կլինի բարձր: Եթե $\sigma ^{2}$ չափազանց մեծ է, ապա մեծ հավանականությամբ նոր նշանակությունները փոքր $P$ հավանականության զոնայից դուրս կմնան, որից ընդունված նշանակությունների բաժինը փոքր կլինի: