مونت كارلو بسلاسل ماركوف

تُجري طريقة مونت كارلو بسلاسل ماركوف سحبًا عشوائيًا من توزيع مستهدف معقد عن طريق محاكاة سلسلة ماركوف مُصممة ليكون هذا التوزيع هو قانونها الثابت الفريد.

Definition

مونت كارلو بسلاسل ماركوف هي عائلة من الخوارزميات التي تُقدّر التوقعات في ظل توزيع احتمالي مستهدف عن طريق تشغيل سلسلة ماركوف إرغودية (ergodic Markov chain) يكون توزيعها الثابت هو التوزيع المستهدف، ومتوسط دالة على مسار السلسلة.

Scope

يغطي هذا الموضوع تصميم نواة الانتقال (transition kernels) بتوزيع ثابت محدد مسبقًا، وخوارزمية متروبوليس-هاستينغز وقاعدة القبول الخاصة بها، وأخذ العينات بطريقة غيبس (Gibbs sampler) للتحديثات الشرطية، وتشخيصات التقارب وفترة الإحماء (burn-in)، وتأثير الارتباط الذاتي (autocorrelation) على تباين المُقدِّر، والصلة بين أوقات الخلط (mixing times) والتكلفة الحسابية لأخذ العينات.

Core questions

• كيف تُبنى سلسلة ماركوف ليكون لها توزيع ثابت مرغوب؟
• لماذا تُنتج قاعدة قبول متروبوليس-هاستينغز القانون الثابت الصحيح؟
• كيف تستغل طريقة غيبس لأخذ العينات التوزيعات الشرطية؟
• ما المدة التي يجب أن تستغرقها السلسلة قبل أن تصبح عيّناتها قابلة للاستخدام، وكيف يتم تقييم ذلك؟

Key theories

بناء متروبوليس-هاستينغز

يؤدي اقتراح تحركات من نواة عشوائية وقبولها باحتمالية مبنية على نسبة الكثافة المستهدفة إلى سلسلة قابلة للعكس (reversible chain) يكون توزيعها الثابت هو التوزيع المستهدف بالضبط، ولا يتطلب ذلك سوى التوزيع المستهدف حتى ثابت التطبيع (normalising constant).

المتوسطات الإرغودية وتقدير مونت كارلو

نظرًا لأن السلسلة إرغودية مع التوزيع المستهدف كقانون ثابت لها، فإن متوسطات الوقت لدالة على طول السلسلة تتقارب بشكل شبه مؤكد مع التوقع المستهدف، مما يبرر استخدام المسارات المحاكاة كعينات.

Clinical relevance

تُعد مونت كارلو بسلاسل ماركوف حجر الزاوية في الإحصاء البايزي الحديث، والفيزياء الإحصائية، والتعلم الآلي، مما يتيح الاستدلال على التوزيعات الخلفية عالية الأبعاد، ودوال التجزئة (partition functions)، ومناظر الطاقة (energy landscapes) التي لا يمكن دمجها تحليليًا؛ وتعتمد موثوقيتها على سرعة خلط السلسلة الأساسية بشكل كافٍ.

History

نشأت سلسلة القبول-الرفض (acceptance-rejection chain) في خوارزمية متروبوليس عام 1953 للفيزياء الإحصائية، وتم تعميمها بواسطة هاستينغز في عام 1970، وأُعيد صياغتها للإحصاء من خلال طريقة غيبس لأخذ العينات (Gibbs sampler) التي قدمها جيمان وجيمان في عام 1984، والتطبيقات البايزية المؤثرة لجلفاند وسميث حوالي عام 1990، والتي أطلقت ثورة الحوسبة البايزية.

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

لماذا نستخدم سلسلة ماركوف لسحب العينات؟

بالنسبة للتوزيعات المستهدفة عالية الأبعاد أو غير المعيارية، يكون أخذ العينات المباشر غير عملي؛ تسمح لك سلسلة ماركوف التي تتقارب مع الهدف بتوليد عينات مترابطة ولكن موزعة بشكل صحيح بعد وصولها إلى التوازن.

ما هي فترة الإحماء (burn-in)؟

هي الجزء الأولي من السلسلة الذي يتم التخلص منه لأن السلسلة لم تتقارب بعد مع توزيعها الثابت، وبالتالي فإن تلك الحالات المبكرة قد تُحيز التقديرات.