في علم الإحصاء، سلسلة ماركوف مونتي كارلو (MCMC) هي نوع من الخوارزميات المستخدمة لمحاكاة توزيع احتمالي مجهول ويتم ذلك ببناء سلسلة ماركوف التي يكون توزيعها المتوازن مطابق للتوزيع الاحتمالي المجهول المراد محاكاته. حالة السلسلة بعد عدد من الخطوات يستخدم كعينات من التوزيع الاحتمالي المراد إيجاده ودقة هذه العينات تتحسن بزيادة عدد الخطوات للسلسلة.
طرق السير العشوائي لمنتو كارلو تمثل جزء كبير من طرق سلسلة ماركوف منتوكارلو
مجالات التطبيق
- طرق MCMC تستخدم لحساب التقريبات العددية للتكاملات المتعددة الأبعاد، مثلا، في احصاء بيشان، الفيزياء الحاسوبية، علم الأحياء الحاسوبي و اللغويات الحاسوبية.[1][2]
- في احصاء بيشان، بعد التطورات الأخيرة في طرق MCMC صار بالإمكان حسابالنماذج الهرمية الكبيرة والتي عادة ما تحتاج التكامل عبر مئات أو الآلاف من المعاملات الغير معلومة.[3]
- كما أنها تستخدم لتوليد العينات التي تعبئ تدريجياً منطقة الفشل النادرة في أخذ عينات من الحالات النادرة.
التصنيف
طرق السير العشوائي لمنتوكارلو
التكاملات المتعددة الأبعاد
عندما تستخدم طرق MCMC لتقريب التكامل المتعدد الأبعاد فإن عدة من المسيرات تتحرك في المجال عشوائياً. كل نقطة داخل المسير تعتبر نقطة تُقْرب من قيمة التكامل. من الممكن أن يأخذ المسيرعدة خطوات في المنطقة باحثاً عن نقاط ذات قيمة عالية لقيمة التكامل.
طرق السير العشوائي لمونت كارلو هي نوع من المحاكاة العشوائية طريقة تكامل مونت كارلو. الفرق أنه في حين أن العينات العشوائية المستخدمة في تكامل مونت كارلو التقليدي هي مستقلة إحصائيا، تلك المستخدمة في أساليب MCMC مترابطة. يتم إنشاء سلسلة ماركوف بحيث تكون قيمة التكامل المراد حسابها تمثل التوزيع المتوازن لهذه السلسلة.
أمثلة
أمثلة على طرق السير العشوائي مونت كارلو:
- خوارزمية Metropolis–Hastings : هذه الطريقة تولد سير عشوائي باستخدام توزيع احتمالي مقترح وطريقة لرفض بعض الحركات المقترحة.
- طريقة جبس لأخذ العينات: يتطلب هذا الأسلوب أن جميع التوزيعات المشروطة للتوزيع المستهدف أن تتم أخذ العينات منها بالضبط. وهذه الطريقة لها شعبية لأنها لا تتطلب أي 'ضبط'.
- أخذ شرائح من العينات: تعتمد هذه الطريقة على المبدأ القائل بأنه يمكن للمرء أن يأخذ عينات من توزيع ما عن طريق أخذ العينات بشكل موحد من المنطقة الواقعة تحت منحنى دالة الكثافة. أخذ العينات يتم بالتناوب بين أخذ عينات موحدة رأسية وبين أخذ عينات موحدة أفقية يحددها الوضع الحالي للعينة الرأسية.
- Multiple-try Metropolis: هذا الأسلوب هو نوع من خوارزمية Metropolis–Hastings التي تسمح بعمل عدة تجارب في كل نقطة وذلك من خلال إتخاذ خطوات أكبر في كل تكرار مما يساعد في معالجة مشكلة الأبعاد.
للتقليل من الترابط بين العينات
هناك طرق أكثر تطورا تستخدم أساليب للتقليل من الترابط بين العينات الناجحة. هذه الخوارزميات قد تكون صعبة في التطبيق لكنها في نفس الوقت تكتسب القدرة على التقريب بصورة أسرع من الطرق التقليدية أي خطوات أقل لنتيجة أدق.
التقارب
عادة ليس من الصعب بناء سلسلة ماركوف بالخصائص المطلوبة لكن من الصعب تحديد كم عدد الخطوات المحتاجة للوصول إلى التوزيع المتوازن المراد تقريبه مع نسبة خطأ مقبولة[4]. تعتبر السلسلة جيدة إذا كان هناك اختلاط متكرر حول القيمة المراد إيجادها والتي يتم الوصول لها بسرعه من أي مكان في المجال. الطريقة التقليدية لمعرفة ما إذا سلسلة ما وصلت إلى التقارب المطلوب هي عن طريق تشغيل سلسلة ماركوف عدد من المرات المستقلة ثم بالتحقق أن التباين الداخلي لكل سلسلة ماركوف لكل معامل تحت الدراسة يساوي تقريباً القيمة واحد.[5] عموماً، طرق MCMC لأخذ العينات تستطيع فقط تقريب التوزيع المراد حسابه لأنه دائما تكون هناك نسبة للخطأ في عملية التقريب. هناك بعض الطرق المستحدثة التي تكون نسبة الخطأ فيها أقل لكنها تتطلب الكثير من الوقت لتشغيلها.
Software
- BUGS / WinBUGS
- JAGS
- MCSim
- R (programming language) with the packages adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, etc.
- Software for Flexible Bayesian Modeling and Markov Chain Sampling, by Radford Neal.
- Stan
روابط خارجية
- MCMC sampling and other methods in a basic overview, by Alexander Mantzaris (original link - now broken)
- Interacting Metropolis-Hastings methodologies
- MCL - a cluster algorithm for graphs, by Stijn van Dongen
- PyMC - Python module implementing Bayesian statistical models and fitting algorithms, including Markov chain Monte Carlo.
- IA2RMS is a Matlab code of the Independent Doubly Adaptive Rejection Metropolis Sampling method[6] for drawing from the full-conditional densities within a Gibbs sampler.
مراجع
- See Gill 2008.
- See Robert & Casella 2004.
- Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (الطبعة Second). CRC Press. صفحة xix. .
- Gelman, A.; Rubin, D.B. (1992). "Inference from iterative simulation using multiple sequences (with discussion)". Statistical Science. 7: 457–511.
- Cowles, M.K.; Carlin, B.P. (1996). "Markov chain Monte Carlo convergence diagnostics: a comparative review". Journal of the American Statistical Association. 91: 883–904.
- Martino, L.; Read, J.; Luengo, D. (2015-06-01). "Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling". IEEE Transactions on Signal Processing. 63 (12): 3123–3138. doi:10.1109/TSP.2015.2420537. ISSN 1053-587X. مؤرشف من الأصل في 08 ديسمبر 2019.