მეტროპოლისის ალგორითმი

Metropolis Algorithm

სურათი უჩვენებს მეტროპოლისის ალგორითმის მიერ ლოკალური კვლევის პროცესში გავლილი დზის ტრაექტორიას

        მეტროპოლისის მეთოდი გვეხმარება მოვახდინოთ მნიშვნელოვნობით შერჩევა უცნობ განაწილებაში და მივიღოთ სასურველი განაწილების პროპორციული განაწილება ისე, რომ ამავდროულად დავრჩეთ მიუკერძოებელი. მეთოდის სახელი უკავშირდება ბერძნული წარმოშობის ამერიკელი მეცნიერის ნიკოლას მეტროპოლისის გვარს, რომელიც 50-იან წლებში მეთაურობდა მკვლევარების ჯგუფს, რომლებმაც ამ პერიოდში შეიმუშავეს მონტე კარლოს ინტეგრირების გამოთვლითი მეთოდი. მეტროპოლისი მეორე მსოფლიო ომის შემდგომ ასევე ხელმძღვანელობდა ჯგუფს რომელიც ახდენდა MANIAC I-ისთეორიულ დამუშავებას.
        მეტროპოლისის მეთოდი წარმოადგენს შერჩევის მეთოდს რომელიც დაფუძნებულია მარკოვის ჯაჭვებზე. მარკოვის ჯაჭვი არის შერჩევების მიმდევრობა რომელშიც თითოეული შერჩევა დამოკიდებულია მის წინა შერჩევაზე(და არა მთელ მიმდევრობაზე). მეტროპოლისის მეთოდის დახმარებით ჩვენ ვქმნით შერჩევების ასეთ კორელაციურ მიმდევრობას და ამავდროულად შერჩევას ვახდეთ მნიშვნელოვნობით, რაც საბოლოოდ გვეხმარება რომ სასურველ შედეგთან მივიდეთ უფრო მალე. მეტროპოლისის მეთოდი გვეხმარება მივიღოთ სასურველი განაწილების პროპორციული განაწილება(რჩება მხოლოდ დავადგინოთ ნორმალიზების კოეფიციენტი რომელზე გამრავლებითაც მივიღებთ სასურველ განაწილებას, რომლის პოვნაც რეალურად დამატებით პრობლემას წარმოადგენს).
        განვმარტოთ მეთოდი უფრო დეტალურად: ვთქვათ არსებობს რაიმე განაწილება P(x) რომლის საერთო სახეც ჩვენთვის უცნობია და დავუშვათ რომ არსებობს ასევე F(x) განაწილება რომელიც არის P(x)-ის პროპორციული. მთავარი პირობა რომელსაც P(x) განაწილება უნდა აკმაყოფილებდეს არის ის, რომ უნდა იყოს არანოლოვანი ნებისმიერ წერტილში. 

1. ინიციალიზაცია - შევარჩიოთ შემთხვევითი წერტილი x0 და ის იყოს პირველი შერჩევა. ასევე შევარჩიოთ ალბათობის სიმკვრივის ფუნქცია Q(x|y) რომელიც გვთავაზობს შერჩევის ახალ მნიშვნელობა x-ს, შერჩევის წინა მნიშვნელობის y-ის საფუძველზე. იმ დაშვებით რომ Q არის სიმეტრიული რაც იმას ნიშნავს რომ ალბათობა x-დან y-ში მოხვედრის იგივეა რაც y-დან x-ში. ამ პირობების გათვალისწინებით Q შეიძლება იყოს ნებისმიერი თუმცა ხშირად იღებენ ხოლმე გაუსის განაწილებას რომელის ცენტრიც არის y-ზე და შესაბამისად y-თან ახლოს მდებარე წერტილები უფრო მეტი ალბათობით აიღება. Q ფუნქციის საშუალებით ჩვენ ვახდეთ ახალი პოზიციის განსაზღვრას და დავხტივართ განაწილებაში პოზიციიდან პოზიციაზე ამიტომ Q განაწილებას ხტომის განაწილებასაც ეძახიან.
2. იტერაციის თითოეულ ეტაპზე:
• შევარჩიოთ კანდიდატი x', რომელსაც ვიღებთ Q(x'|xt)-დან.
• გამოვთვალოთ α = F(x')/F(xt) ფარდობა, რომლის საფუძველზეც ჩვენ უნდა მივიღოთ ან უარი ვთქვათ შემოთავაზებულ კანდიდატზე. რადგან მიმდინარე F განაწილება ყოველთვის პროპორციულია Q-სი α = f(x')/f(xt) = Q(x')/Q(xt).
• თუ α > 1, მაშინ ვიღებთ შემოთავაზებას და ვაფიქსირებთ, რომ xt+1 = x'. წინააღმდეგ შემთხვევაში შემოთავაზებას ვიღებთ α ალბათობით. თუ კანდიდატზე უარი ითქვა ვაფიქსირებთ რომ xt+1 = xt, რაც იმას ნიშნავს რომ ვრჩებით იგივე ადგილზე.

        სხვა სიტყვებით რომ ვთქვათ ალგორითმი იწყებს მოძრაობას შემთხვევითი პოზიციიდან და ახდენს გადასვლას რაღაც ახლო მიდამოში შემთხვევითად(ხან გადადის ხან არა) და ასე იკვლევს ლოკალურად გარემოს, რის საფუძველზეც F განაწილების სახით იღებს Q-ს პროპორციულ განაწილებას.

        მოცემულ ვიდეოში ნაჩვენებია მეტროპოლისის მეთოდი მუშაობის პროცესში. სასურველი განაწილება მოცემულია შავთეთრი სურათის სახით, ნაჩვენებია პოზიციის მუტაციები 4, 8 და 16 პიქსელის სიახლოვეში. მუტაციის მიდამოს გაზრდით ჩვენ ფაქტიურად ვამცირებთ მნიშვნელოვნობით შერჩევის ეფექტს თუმცა ძალიან შემცირების შემთხვევაში კონკრეტული მცირე მიდამოს ლოკალური კვლევის პროცესი იწვევს ლოკალურ კორელაციას რაც საბოლოო ჯამში გაზრდის გლობალური მიახლოების დროს. მეტროპოლისის მეთოდი არის მე-20 საუკუნის 10 საუკეთესი მეთოდს შორის რაც ხაზს უსვამს მის განსაკუთრებულობას.