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

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