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

Մետրոպոլիս-Հաստինգսի ալգորիթմ
Տեսակ	ալգորիթմ
Հայտնաբերող	Nicholas Metropolis?, Marshall Rosenbluth?, Էդվարդ Թելեր, W. K. Hastings?, Էնրիկո Ֆերմի և Ստանիսլավ Ուլամ
Անվանված է	Nicholas Metropolis? և W. K. Hastings?

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$ հավանականության զոնայից դուրս կմնան, որից ընդունված նշանակությունների բաժինը փոքր կլինի։