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

[մինի|350px|The Proposal [probability distribution|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 

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

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

## Ծանոթագրություններ

Կատեգորիա:Ալգորիթմներ