Metropolis--Hastings with Scalable Subsampling

إليك ملخص تقني مفصل لورقة البحث بعنوان "Metropolis–Hastings with Scalable Subsampling" (خوارزمية ميتروبوليس-هيستينغز مع أخذ عينات فرعية قابلة للتوسع) من إعداد إستيفاو برادو، كريستوفر نيميث، وكريس شيرلوك.

1. بيان المشكلة

في الاستدلال البايزي (Bayesian inference)، تعد خوارزمية ميتروبوليس-هيستينغز (MH) الطريقة القياسية لأخذ العينات من التوزيعات اللاحقة (posterior distributions). ومع ذلك، بالنسبة لمجموعات البيانات الضخمة (حيث $n$ بالملايين أو المليارات)، تصبح الخوارزمية مكلفة حاسوبياً لأنها تتطلب تقييم الاحتمالية الكاملة (جمع كافة نقاط البيانات $n$) في كل تكرار لحساب نسبة القبول.

تواجه الحلول الحالية مقايضات كبيرة:

• الطرق التقريبية: الاستدلال التبايني (Variational inference) أو تقريبات لابلاس (Laplace approximations) سريعة ولكنها تُدخل تحيزاً وليست دقيقة.
• فرق تسد (Divide-and-Conquer): تقسيم البيانات ودمج التوزيعات اللاحقة الفرعية أمر صعب التنفيذ بدقة بالنسبة للأهداف غير الغاوسية (non-Gaussian targets).
• طرق أخذ العينات الفرعية الدقيقة: تحاول خوارزميات MH السابقة التي تعتمد على أخذ عينات فرعية دقيقة (مثل SMH من كورنيش وآخرون، 2019، و TunaMH من تشانغ وآخرون، 2020) استخدام مجموعات فرعية من البيانات، لكنها تعاني من:
  • حدود فضفاضة: تعتمد هذه الطرق على حدود لفرق اللوغاريتم الاحتمالي (log-likelihood difference) تصبح فضفاضة جداً مع زيادة بُعد المعلمة ($d$)، مما يفرض استخدام عينات فرعية كبيرة.
  • خلط ضعيف (Poor Mixing): للحفاظ على معدلات قبول معقولة، تتطلب هذه الطرق غالباً تقليل حجم خطوة الاقتراح (معلمة التدرج $\lambda$) بشكل جذري، مما يؤدي إلى ارتباط ذاتي عالٍ وخلط بطيء.
  • مشكلات التباين: تستخدم طرق مثل TunaMH نسب قبول ذات تباين عالٍ تتطلب معاملات ضبط لتثبيتها، وغالباً ما يكون ذلك على حساب الكفاءة.

2. المنهجية: خوارزمية MH-SS

يقترح المؤلفون خوارزمية Metropolis–Hastings with Scalable Subsampling (MH-SS)، وهي خوارزمية دقيقة تحقق التوازن التفصيلي (detailed balance) بالنسبة للتوزيع اللاحق الحقيقي مع استخدام عينات فرعية صغيرة.

الآلية الجوهرية

تعتمد الخوارزمية على المتغيرات الضابطة (control variates) المستمدة من توسيعات تايلور (Taylor expansions) لطلبات اللوغاريتم الاحتمالي حول نمط التوزيع اللاحق التقريبي المحسوب مسبقاً ($\hat{\theta}$).

1. المتغيرات الضابطة:
   بالنسبة للفرق في اللوغاريتم الاحتملي بين الحالة المقترحة $\theta'$ والحالة الحالية $\theta$، يقرب المؤلفون الحد $\ell_i(\theta') - \ell_i(\theta)$ باستخدام:

   • الدرجة الأولى (CV1): توسيع تايلور الخطي.
   • الدرجة الثانية (CV2): توسيع تايلور التربيعي الذي يتضمن المصفوفة الهيسية (Hessian).

   خطأ التقريب محكوم بدالة حتمية:
   $$|\ell_i(\theta') - \ell_i(\theta) - r_i(\theta, \theta'; \hat{\theta})| \leq c_i M(\theta, \theta')$$
   حيث تعتمد $c_i$ على البيانات وتعتمد $M(\theta, \theta')$ على حجم خطوة الاقتراح.

2. التخفيف بـ "بواسون" وأخذ العينات الفرعية (Poisson Thinning & Subsampling):
   بدلاً من تقييم جميع الحدود $n$، تستخدم الخوارزمية التخفيف بـ "بواسون" (Poisson thinning) لاختيار مجموعة فرعية عشوائية من فهارس البيانات $I$.

   • تحدد الخوارزمية دوال مساعدة $\phi_i$ و $\phi'_i$ بناءً على حدود الخطأ والفرق في المتغير الضابط ($\Delta_i$).
   • يتم أخذ عينات من نقاط البيانات باحتمالات تتناسب مع هذه الدوال.
   • يتم بناء نسبة القبول باستخدام مُقدّر غير منحاز يتضمن المجموعة المختارة، مما يضمن أن السلسلة تستهدف التوزيع اللاحق الدقيق.

3. القبول المتأخر (Delayed Acceptance - DA):
   تستخدم الخوارزمية عملية قبول ذات مرحلتين:

   • المرحلة 1: خطوة فحص مسبق رخيصة باستخدام تقريب المتغير الضابط (لا تتطلب أخذ عينات فرعية من البيانات) لرفض الاقتراحات السيئة بوضوح.
   • المرحلة 2: إذا تم اجتياز المرحلة الأولى، يتم تطبيق تصحيح قائم على العينة الفرعية. إذا تجاوز حجم العينة المطلوبة $n$، تعود الخوارزمية إلى استخدام الاحتمالية الكاملة للبيانات.

4. الضبط الأمثل:
   استنتج المؤلفون أن الكفاءة تبلغ ذروتها عندما يتم ضبط المعامل $\gamma$ (الذي يتحكم في شكل دالة التحديد) عند القيمة 0. علاوة على ذلك، أثبتوا أن معدل القبول الأمثل لـ MH-SS هو حوالي 45.2%، وهو أعلى بكثير من نسبة 23.4% الخاصة بـ Random Walk Metropolis (RWM)، مما يسمح بخطوات أكبر وخلط أفضل.

3. المساهمات الرئيسية

• حدود نظرية أكثر إحكاماً: اشتق الورقة حدوداً جديدة أكثر إحكاماً بشكل كبير لطلبات فرق اللوغاريتم الاحتملي للنماذج اللوجستية (logistic)، والبروبيت (probit)، والبوواسون (Poisson)، ونماذج الانحدار القوية (robust regression). هذه الحدود تتفوق على الطرق السابقة (مثل SMH) بمقدار $O(d^{1/2})$ في الأبعاد المتوسطة إلى العالية، مما يقلل بشكل كبير من حجم العينة الفرعية المطلوبة.
• مثالية المتغيرات الضابطة: أثبت المؤلفون أن ضبط $\gamma=0$ في بناء احتمالية القبول يزيد من معدل القبول إلى أقصى حد، وبالتالي يزيد من حجم العينة الفعالة (ESS) لكل ثانية.
• التعقيد الحسابي:
  • أظهر أن تكلفة التكرار الواحد لـ MH-SS مستقلة عن $n$ (تحديداً $O(d^{3/2})$ لـ CV1 و $O(d^3/\sqrt{n})$ لـ CV2).
  • في المق المقابل، فإن تكلفة الطرق السابقة مثل SMH تتدهور بسرعة أكبر مع البعد $d$.
• التوسع متعدد الأنماط (Multimodal Extension): تقدم الورقة امتداداً نظرياً لـ MH-SS للتعامل مع التوزيعات اللاحقة متعددة الأنماط (مثل نماذج الخليط/mixture models) عبر اختيار متغيرات ضابطة بناءً على نقطة المنتصف بين الحالة الحالية والمقترحة، مما يضمن الحفاظ على التوازن التفصيلي.

4. النتائج

تحقق المؤلفون من صحة MH-SS من خلال محاكاة واسعة النطاق وتطبيقات واقعية (Hepmass، حوادث الطرق في المملكة المتحدة، تعداد الولايات المتحدة، مستشعرات الغاز).

• مكاسب الكفاءة:
  • مقابل RWM: تعتبر MH-SS أكثر كفاءة بعدة مراتب عشرية (من حيث حجم العينة الفعالة لكل ثانية) من RWM القياسي، خاصة مع زيادة $n$ و $d$.
  • مقابل SMH: تتطلب MH-SS عينات فرعية أصغر بكثير. على سبيل المثال، في الانحدار اللوجستي مع $d=50$، غالباً ما تتطلب SMH تقييم كافة نقاط البيانات $n$، بينما تستخدم MH-SS جزءاً ضئيلاً جداً.
  • مقابل TunaMH: بينما تستخدم TunaMH عينات فرعية صغيرة، إلا أنها تعاني من خلط ضعيف بسبب الحاجة إلى خطوات متناهية الصغر للحفاظ على معدلات القبول. تحقق MH-SS معدلات قبول عالية بخطوات أكبر، مما ينتج عنه ESS أعلى بكثير.
• الأداء في العالم الحقيقي:
  • في مجموعة بيانات Hepmass ($n=10^6, d=26$)، حققت MH-SS-2 (الدرجة الثانية) مقدار ESS لكل ثانية بلغ حوالي 69.2، مقارنة بـ 0.002 لـ Tuna و 0.016 لـ SMH-1.
  • كانت MH-SS-2 هي الخوارزمية الأكثر كفاءة باستمرار عبر جميع نماذج الانحدار المختبرة (Logistic, Probit, Poisson).
• سلوك التوسع (Scaling Behavior): تؤكد النتائج التجريبية التنبؤ النظري بأن MH-SS تتوسع بشكل أفضل مع البعد $d$ مقارنة بـ SMH. إن "فضاوة" حدود SMH تجبرها على تقييم المزيد من البيانات مع نمو $d$، بينما تظل حدود MH-SS محكمة.

5. الأهمية

تمثل هذه الورقة تقدماً كبيراً في الاستدلال البايزي القابل للتوسع:

1. الدقة: توفر طريقة ممكنة حاسوبياً لمجموعات البيانات الضخمة مع الحفاظ على الدقة (على عكس الاستدلال التبايني).
2. العملية: من خلال اشتقاق حدود أكثر إحكاماً ومعاملات ضبط مثالية، جعل المؤلفون الخوارزمية قوية وسهلة التنفيذ لنماذج الانحدار القياسية دون الحاجة إلى حدود معقدة خاصة بكل مشكلة كما تتطلب طرق مثل Firefly Monte Carlo.
3. الكفاءة: القدرة على تحقيق معدلات قبول عالية (45%) مع عينات فرعية صغيرة تسمح لسلسلة ماركوف باستكشاف الفضاء اللاحق بشكل أسرع بكثير من طرق أخذ العينات الفرعية الدقيقة الموجودة، مما يجعلها خياراً متفوقاً لتحليلات "البيانات الضخمة" البايزية.

باختصار، تحل MH-SS مشكلة "لعنة الأبعاد" في MCMC لأخذ العينات الفرعية عبر الاستفيد من حدود المتغيرات الضابطة الأكثر إحكاماً واستراتيجيات القبول المثلى، مما يوفر حلاً عملياً ودقيقاً وعالي الكفاءة للاستدلال البايزي واسع النطاق.