الـ computational Bayesian methods | STAT-101

لما الجبر يخلص من الإطار

الدرسين اللي فاتوا بنوا الماكينة البايزية ووروها شغّالة باليد. كل posterior بيتناسب مع الـ prior مضروب في الـ likelihood، ومع زوج conjugate الـ posterior بيقع في عيلة معروفة، فالتحديث بيبقى حساب بصيغة مقفولة. والمشكلة إن الأزواج الـ conjugate هي الاستثناء. اكتب الـ posterior كامل والمقام هيبقى integral على فضاء الـ parameters كله:

الـ posterior، كامل

p(\theta \mid D) = \dfrac{p(D \mid \theta)\,p(\theta)}{\int p(D \mid \theta)\,p(\theta)\,d\theta}

البسط سهل: لأي θ مرشّحة نقدر نحسب الـ prior والـ likelihood. أما المقام — الـ marginal likelihood P(D) — فهو الـ integral ده، وبرّه الـ models الـ conjugate مالوش صيغة مقفولة.

لـ parameter أو اتنين ممكن تطحن الـ integral بالأرقام على grid. بس الـ models الحقيقية فيها عشرات أو مئات أو آلاف الـ parameters، وgrid بالعدد ده من الأبعاد فيه خلايا أكتر من اللي وقت الكمبيوتر يستحمله. ده الحيطة اللي خلّت الاستدلال البايزي مش عملي معظم القرن العشرين، وهي بالظبط الحيطة اللي الـ Markov chain Monte Carlo (سلسلة ماركوف مونت كارلو) أو MCMC بتلف حواليها.

فكرة الـ MCMC

بدل ما تحسب الـ posterior، الـ MCMC بتاخد samples منه. والاسم فكرتين لازقين في بعض. Monte Carlo: لو تقدر تسحب samples من distribution، تقدر تقدّر أي خاصية ليه — الـ mean بتاعه، أو فترة 95%، أو احتمال ديل — بإنك بس تحسب الخاصية دي على الـ samples وتاخد متوسطها. Markov chain: تسلسل حالات كل واحدة معتمدة على اللي قبلها بس.

الحيلة إنك تبني Markov chain يكون الـ stationary distribution (التوزيع المستقر) بتاعها هو الـ posterior نفسه. ابدأها من أي حتة، وسيبها تشتغل، وبعد شوية الحالات اللي بتلف فيها بتبقى samples من P(θ∣D) — مش samples مستقلة، بس samples برضه. والميزة الحاسمة إن الـ chain عمرها ما بتحتاج غير إنها تقارن الـ posterior عند نقطتين، فبتشتغل بـ نسب الـ posterior. وفي النسبة المقام الصعب بيتشال: هو نفس الثابت فوق وتحت. فالـ MCMC عمرها ما بتضطر تحسب الحاجة اللي كان مستحيل تتحسب.

الـ Metropolis–Hastings

أقدم وأعم وصفة للـ chain دي هي الـ Metropolis–Hastings. من الحالة الحالية x بتقترح مرشّح x′ من proposal distribution q، وبعدين تقرر تنقل له ولا تفضل، باستخدام احتمال قبول:

الـ acceptance probability

اسحب رقم uniform على (0, 1)؛ لو أقل من α انقل لـ x′، غير كده افضل عند x وسجّل x تاني. وخد بالك إن p بيظهر بس كنسبة، فكفاية تعرفه لحد ثابت — وده بيت القصيد.

لما الـ proposal يبقى symmetric (متماثل) — احتمال إنك تقترح خطوة من x لـ x′ زي احتمال العكس، ودي حال أي Gaussian متمركز على النقطة الحالية — نسبة q بتساوي واحد والقاعدة بتتحوّل لصيغة Metropolis الأصلية:

الحالة المتماثلة

أي خطوة لفوق (x′ احتمالها أكبر) بتتقبل دايمًا؛ والخطوة لتحت بتتقبل باحتمال بيساوي احتمالها نزل قد إيه. والاستعداد المظبوط ده إنها تنزل هو اللي بيخلّي الـ chain تستكشف بدل ما تطلع للـ mode وبس.

ليه ده بيقع على الـ posterior؟ قاعدة القبول متصممة عشان تحقق الـ detailed balance (التوازن التفصيلي): إن احتمال إنك تمسك الـ chain وهي بتخطي من x لـ x′ يساوي احتمالها من x′ راجعة لـ x، لما x تتسحب من الـ posterior. والـ chain اللي بتمشي على الـ detailed balance بالنسبة لـ distribution، الـ distribution ده بيبقى الـ stationary distribution بتاعها. شغّلها وقت كفاية وهتنسى بدأت منين وتستقر على سحب samples من الـ posterior.

الضبط: القبول قصاد الـ mixing

الـ Metropolis–Hastings ليه مقبض واحد بيقرر هيشتغل كويس ولا بالعافية يشتغل: عرض الـ proposal، يعني الحجم المعتاد للخطوة اللي بيقترحها. وده بيعمل trade-off مباشر بين القبول بيحصل قد إيه والـ chain بتعمل mixing كويس قد إيه — يعني بتتنقل في الـ posterior بسرعة قد إيه.

صغير أوي — تقريبًا كل خطوة صغيرة بتتقبل، بس الـ chain بتلف حوالين نفسها. الـ samples المتتالية تقريبًا زي بعض، فهي autocorrelated جامد وشايلة معلومة مستقلة قليلة.
كبير أوي — تقريبًا كل خطوة بتقع في حتة احتمالها أقل بكتير فبتترفض، فالـ chain بتقعد واقفة فترات طويلة، وبتسجّل نفس القيمة تاني وتالت.
نطاق صحي بينهم — خطوات كبيرة كفاية إنها تتنقل، وبتتقبل كفاية إنها تفضل ماشية. هنا الـ sampler بيستكشف بجد.

قاعدة تقريبية

لـ random-walk Metropolis sampler في الأبعاد العالية فيه هدف مشهور: acceptance rate قريب من 0.234 قريب من الأمثل (Roberts, Gelman & Gilks, 1997). اعتبره تشخيص مش قانون — لو بتقبل 95% من الـ proposals يبقى خطواتك خجولة زيادة عن اللزوم، ولو بتقبل 2% يبقى جريئة زيادة عن اللزوم. والإجابة الصح لمسألة ليها بعد واحد أعلى، حوالي 0.44.

الـ Gibbs sampling

الـ Metropolis–Hastings عام بس مبذّر: بيرمي كل proposal بيترفض. ولما الـ model يبقى فيه تركيبة أكتر، الـ Gibbs sampling بيستغلها. الفكرة إنك تحدّث parameter واحد كل مرة بإنك تسحبه من الـ full conditional distribution (التوزيع الشرطي الكامل) بتاعه — توزيعه بالنظر للقيم الحالية لكل الـ parameters التانية. ولو كل full conditional distribution تقدر تسحب منه على طول، عمرك ما هترفض حاجة.

المثال النضيف هو الـ bivariate normal المرتبط. لو (x₁, x₂) bivariate normal بـ correlation ρ وvariance واحد، يبقى الـ full conditional لكل إحداثي هو نفسه normal distribution عادي:

full conditional distribution

x_1 \mid x_2 \sim \mathcal{N}(\rho x_2,\; 1 - \rho^2)

ثبّت x₂ يبقى x₁ normal متمركز على ρx₂ والـ variance بتاعه 1−ρ²؛ وبالتماثل نفس الكلام لو بدّلت الأدوار. اسحب x₁ من ده، وبعدين x₂ من الـ conditional بتاعه، وكرّر — كل sample بتتقبل.

الـ Gibbs sampling بيعمل mixing كويس ومش محتاج ضبط لما ينفع يتستخدم، وعشان كده شغّل أول جيل من البرامج البايزية العملية. وحدّه هو بالظبط شرطه: مينفعش تستخدمه إلا لما الـ full conditionals تبقى distributions معروفة تقدر تسحب منها. ولما متبقاش كده، بترجع للـ Metropolis–Hastings، أو لـ hybrid بيستخدم Gibbs في الحتت اللي ينفع فيها وخطوات Metropolis في الباقي.

التشخيصات: الـ chain اتقاربت؟

الـ MCMC بتدّيك samples سواء الـ chain وصلت للـ posterior فعلًا ولا لأ، فمينفعش تثق في ناتجها وإنت مغمّض. وشوية تشخيصات بيقولولك تصدّقه ولا لأ:

الـ trace plots. ارسم كل parameter قصاد رقم الـ iteration. الـ chain اللي اتقاربت وبتعمل mixing كويس بتبان زي شريط أفقي منكوش — «دودة مشعّرة». أما الحتت المفرودة الطويلة، أو الانزلاق البطيء، أو chain عمرها ما بتستقر، فكلها علامات إنذار.
الـ burn-in (الإحماء). الـ chain بتبدأ في المكان اللي حطيتها فيه، وده ممكن يبقى بعيد عن معظم الـ posterior. ارمي الـ iterations الأولانية — الـ burn-in — عشان التقديرات متتشدّش ناحية نقطة البداية الاعتباطية.
الـ autocorrelation والـ effective sample size. الـ samples المتتالية مرتبطة ببعض، فـ 10,000 sample من الـ MCMC قيمتها أقل من 10,000 sample مستقلة. والـ effective sample size (حجم العيّنة الفعّال) أو ESS بيقول بيعادلوا كام sample مستقلة؛ والـ ESS الصغير معناه autocorrelation عالي وتقديرات مهزوزة.
الـ R-hat بين الـ chains. شغّل كذا chain من نقط بداية متفرقة. لو اتقاربت لازم كلها تستكشف نفس المنطقة، فالـ variance بين الـ chains يطابق الـ variance جواها. وإحصاءة Gelman–Rubin R̂ بتقيس ده، والقيمة القريبة من 1 هي إشارة إن الـ chains متفقة.

إنت مش هتكتب دول بإيدك

عمليًا محدش بيبرمج sampler من الصفر. لغات الـ probabilistic programming — Stan وPyMC وغيرهم — بتخلّيك توصف الـ model (الـ priors والـ likelihood) في سطور قليلة وتحوّله لـ sampler كفؤ أوتوماتيك، عادةً طريقة حديثة مبنية على الـ gradient بدل الـ random-walk Metropolis البسيط. والمفاهيم اللي في الدرس ده هي اللي الأدوات دي بتعمله تحت الكبوت، وهي اللي التشخيصات اللي فوق بتطلب منك تفحصها برضه.

جرّبها

الـ MCMC sampler التفاعلي اللي مع الدرس بيشغّل Metropolis–Hastings chain حقيقية وGibbs sampler حقيقي في الـ browser. حرّك عرض الـ proposal وشوف trade-off القبول والـ mixing في الـ trace plot — الخطوات الصغيرة بتزحف، والكبيرة بتعلق، واللي في النص بتستكشف. ودي أسرع طريقة تحس بيها يعني إيه «mixing».

أهم النقط

ثابت الـ normalization بتاع الـ posterior هو integral مستحيل برّه الـ models الـ conjugate، فعادةً مينفعش تحسب الـ posterior على طول.
الـ MCMC بتاخد samples من الـ posterior بدل ما تحسبه: ابني Markov chain الـ stationary distribution بتاعها هو الـ posterior، وقدّر أي كمية بمتوسط على الـ samples بتاعتها. ومحتاج بس نسب الـ posterior، فالثابت الناقص بيتشال.
الـ Metropolis–Hastings بيقترح نقلة ويقبلها باحتمال α = min(1, …)؛ ومع proposal symmetric بيبقى min(1, p(x′)/p(x)). والـ detailed balance هو اللي بيخلّي الـ posterior هو الـ stationary.
عرض الـ proposal بيبدّل القبول بالـ mixing: الصغير أوي بيزحف، والكبير أوي بيعلق. وacceptance rate حوالي 0.234 في الأبعاد العالية قاعدة تقريبية مفيدة.
الـ Gibbs sampling بيسحب كل parameter من الـ full conditional بتاعه ويقبل كل sample — ممتاز لما الـ conditionals تبقى معروفة، ومش متاح لما متبقاش.
شخّص دايمًا: الـ trace plots، والـ burn-in، والـ autocorrelation والـ ESS، والـ R̂ على كذا chain. وأدوات الـ probabilistic programming (Stan وPyMC) بتبنيلك الـ sampler بس مش بتعفيك من الفحوص.