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

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