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

Մետրոպոլիս-Հաստինգսի ալգորիթմը, սեմպլիրացման ալգորիթմ է, որն հիմնականում օգտագործվում է բաշխման բարդ ֆունկցիաների համար։ Այն մասամբ նման է շեղումներով ընտրության ալգորիթմին, սակայն այստեղ բաշխման օժանդակ ֆունկցիան փոխվում է ժամանակի ընթացքում է։ Առաջին անգամ ալգորիթմը լույս է տեսել Նիկոլաս Մետրոպոլիսի կողմից 1953 թվին, և հետո ընդհանրացվել Հաստինգսի կողմից 1970 թվին. սեմպլիրացում ըստ Գիբբսի հանդիսանում է Մետրոպոլիս-Հաստինգսի ալգորիթմի մասնավոր դեպք, և ավելի հայտնի է իր պարզությամբ և արագությամբ, չնայած առավել հազվադեպ է կիրառվում։
Մետրոպոլիս-Գաստինգի ալգորիթմը թույլ է տալիս սեմպլիրացնել ցանկացած բաշխման ֆունկցիա։ Այն հիմնված է Մարկովի շղթայի ստեղծման վրա, այսինքն ալգորիթմի յուրաքանչյուր քայլին նոր ընտրված 
  
    
      
        
          x
          
            t
            +
            1
          
        
      
    
    {\displaystyle x^{t+1}}
  -ի իմաստը կախված է նախորդ 
  
    
      
        
          x
          
            t
          
        
      
    
    {\displaystyle x^{t}}
  -ից.Ալգորիթմն օգտագործում է 
  
    
      
        Q
        (
        
          x
          ′
        
        
          |
        
        
          x
          
            t
          
        
        )
      
    
    {\displaystyle Q(x'|x^{t})}
   բաշխման օժանդակ ֆունկցիան, որը կախված է 
  
    
      
        
          x
          
            t
          
        
      
    
    {\displaystyle x^{t}}
  -ից, և որի համար գեներացիան выборку հեշտ է (օրինակ, նորմալ բաշխումը). Այս ֆունկցիայի համար ամեն քայլին գեներացվում է 
  
    
      
        
          x
          ′
        
      
    
    {\displaystyle x'}
  -ի պատահական իմաստ։ Հետո հավանականությամբ՝

  
    
      
        u
        =
        
          
            
              P
              (
              
                x
                ′
              
              )
              Q
              (
              
                x
                
                  t
                
              
              
                |
              
              
                x
                ′
              
              )
            
            
              P
              (
              
                x
                
                  t
                
              
              )
              Q
              (
              
                x
                ′
              
              
                |
              
              
                x
                
                  t
                
              
              )
            
          
        
      
    
    {\displaystyle u={\frac {P(x')Q(x^{t}|x')}{P(x^{t})Q(x'|x^{t})}}}
  
( կամ 1 հավանականությամբ եթե 
  
    
      
        u
        >
        1
      
    
    {\displaystyle u>1}
  ), ընտրված իմաստը ընդունվում է որպես նոր՝ 
  
    
      
        
          x
          
            t
            +
            1
          
        
        =
        
          x
          ′
        
      
    
    {\displaystyle x^{t+1}=x'}
  , հակառակ դեպքում մնում է նույնը՝ 
  
    
      
        
          x
          
            t
            +
            1
          
        
        =
        
          x
          
            t
          
        
      
    
    {\displaystyle x^{t+1}=x^{t}}
  .
Օրինակ, եթե ընդունենք բաշխման նորմալ ֆունկցիան որպես օժանդակ, ապա

  
    
      
        Q
        (
        
          x
          ′
        
        
          |
        
        
          x
          
            t
          
        
        )
        ∼
        N
        (
        
          x
          
            t
          
        
        ,
        
          σ
          
            2
          
        
        I
        )
        
        
      
    
    {\displaystyle Q(x'|x^{t})\sim N(x^{t},\sigma ^{2}I)\,\!}
  
.
Այսպիսի ֆունկցիան տալիս է նոր նշանակություն՝կախված նախկին քայլում ստացված նշանակությունից։ Ի սկզբանե Մետրոպոլիսի ալգորիթմը պահանջում էր, որ օժանդակ ֆունկցիան լիներ սիմետրիկ՝ 
  
    
      
        Q
        (
        
          x
          ′
        
        ,
        
          x
          
            t
          
        
        )
        =
        Q
        (
        
          x
          
            t
          
        
        ,
        
          x
          ′
        
        )
      
    
    {\displaystyle Q(x',x^{t})=Q(x^{t},x')}
  , սակայն Գաստինգսի ընդհանրացումը այս սահմանափակումը վերացնում է։


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

  
    
      
        
          a
          
            1
          
        
        =
        
          
            
              P
              (
              
                x
                ′
              
              )
            
            
              P
              (
              
                x
                
                  t
                
              
              )
            
          
        
      
    
    {\displaystyle a_{1}={\frac {P(x')}{P(x^{t})}}}
  
հանդիսանում է միջանկյալ և նախկին նշանակությունների միջև հավանականությունների հարաբերակցություն, իսկ

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

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

  
    
      
        
          
            
              
                
                  
                    and if 
                  
                
                a
                <
                1
                :
              
              
            
            
              
              
                
                  x
                  
                    t
                    +
                    1
                  
                
                =
                
                  {
                  
                    
                      
                        
                          
                            x
                            ′
                          
                          
                            
                               with probability 
                            
                          
                          a
                        
                      
                      
                        
                          
                            x
                            
                              t
                            
                          
                          
                            
                               with probability 
                            
                          
                          1
                          −
                          a
                          .
                        
                      
                    
                  
                  
                
              
            
          
        
      
    
    {\displaystyle {\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
          
        
      
    
    {\displaystyle x^{0}}
  –ի պատահական նշանակությունից, և սկզբում մի քանի քայլ գործում է միայնակ, որպեսզի մոռացվի սկզբնական նշանակությունը։
Ամենալավը ալգորիթմը գործում է այն ժամանակ, երբ օժանդակ ֆունկցիայի ձևը մոտ է նպատակայինին 
  
    
      
        P
      
    
    {\displaystyle P}
   ֆունկցիայի ձևին. ։ Սակայն այս չճշտվածությանը հասնելը մասամբ անհնար է։ Խնդրի լուծման համար օժանդակ ֆունկցիան հարմարեցնում են ալգորիթմի աշխատանքի նախապատրաստական փուլի ընթացքում։ Օրինակ, նորմալ բաշխման համար 
  
    
      
        
          σ
          
            2
          
        
      
    
    {\displaystyle \sigma ^{2}}
   պարամետրը ընտրում են այնպես, որ ընդունած պատահական նշանակությունների բաժինը (այսինքն նրանց, որոնց համար 
  
    
      
        
          x
          
            t
            +
            1
          
        
        =
        
          x
          ′
        
      
    
    {\displaystyle x^{t+1}=x'}
  )-ը մոտ լինի 60%. Եթե 
  
    
      
        
          σ
          
            2
          
        
      
    
    {\displaystyle \sigma ^{2}}
  -ը չափազանց փոքր է, ապա նշանակությունները կստացվեն շատ մոտ և ընդունվածների բաժինը կլինի բարձր։ Եթե 
  
    
      
        
          σ
          
            2
          
        
      
    
    {\displaystyle \sigma ^{2}}
   չափազանց մեծ է, ապա մեծ հավանականությամբ նոր նշանակությունները փոքր 
  
    
      
        P
      
    
    {\displaystyle P}
   հավանականության զոնայից դուրս կմնան, որից ընդունված նշանակությունների բաժինը փոքր կլինի։


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