ملخص تقني: تقدير قيمة شابلي التقريبية باستخدام المعاينة بدون استبدال ومقدرات تباين بوتستراب جديدة

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

يهدف إطار عمل KernelSHAP الكلاسيكي (Lundberg and Lee, 2017) إلى تقليل التكلفة الحسابية لتقدير قيمة شابلي (Shapley value) عن طريق أخذ عينات من مجموعة فرعية من التحالفات بدلاً من تقييم دالة المساهمة لجميع المجموعات الفرعية الممكنة البالغ عددها $2^p$. ومع ذلك، فإن التنفيذات الحالية تعتمد عادةً على أخذ عينات من التحالفات مع الاستبدال. ويؤدي هذا النهج إلى تحديات إحصائية محددة:

1. عدم كفاءة المعاينة: تؤدي المعاينة مع الاستبدال إلى نسخة موزونة من "مسألة جامع الكوبونات" (Coupon Collector's Problem)، حيث يصبح الحصول على تحالفات فريدة أمراً صعباً بشكل متزايد مع نمو حجم العينة، لا سيالما بالنسبة للتحالفات ذات الأوزان المنخفضة.
2. محدودية تقدير التباين: تفترض طرق البوتستراب التقليدية أن العينات مستقلة ومتماثلة التوزيع (i.i.d.). ويتم انتهاك هذا الافتراض عند المعاينة بدون استبدال من مجتمع محدود (مجموعة كل التحالفات الممكنة). وبناءً على ذلك، قد تؤدي تقنيات البوتستراب القياسية إلى تقديرات خاطئة لتباين قيم شابلي، حيث تفشل في مراعاة قيد المجتمع المحدود الذي ينبغي أن يقترب فيه التباين نظرياً إلى الصفر إذا تم تقييم جميع التحالفات.

يعالج البحث هذه القضايا من خلال اقتراح إطار عمل يستخدم المعاينة بدون استبدال ويقدم منهجيات بوتستراب جديدة متوافقة مع نظرية المجتمع المحدود لتقدير تباين قيم شابلي المقدرة بدقة.

2. المنهجية

2.1 المعاينة بدون استبدال عبر توزيع والينيوس (Wallenius')

يقوم الخوارزمي المقترح بتعديل إجراء KernelSHAP لأخذ عينات من التحالفات بدون استبدال. وتتضمن العملية خطوتين رئيسيتين:

1. الطبقية (Stratification): يتم تجميع التحالفات حسب عدد الميزات (الحجم) التي تحتوي عليها.
2. تحديد أحجام العينات: بدلاً من أخذ عينات من التحالفات واحدة تلو الأخرى بشكل عشوائي، يقوم الخوارزمي بحساب العدد المتوقع للتحالفات المراد سحبها من كل مجموعة باستخدام توزيع والينيوس للهندسة المفرطة غير المركزية (Wallenius' noncentral hypergeometric distribution). ينمذج هذا التوزيع المعاينة المتحيزة بدون استبدال حيث تمتلك العناصر أوزاناً مختلفة.
   • يستخدم الخوارزمي القيم المتوقعة لهذا التوزيع، مع تقريبها إلى أقرب عدد صحيح، لتحديد عدد التحالفات التي يجب أخذ عينات منها من كل طبقة.
   • بمجرد تحديد الأعداد، يتم أخذ عينات من التحالفات بدون استبدال داخل كل مجموعة.
   • استراتيجية الاقتران: لتقليل التباين بشكل أكبر، تستخدم الطريقة استراتيجية اقتران (Kroese et al., 2013). فإذا تم أخذ عينة من تحالف $S$، يتم أيضاً تضمين مكمّله $S^c$ في الحساب، مما يضمن بقاء مجموع الميزات في المجموعات المزدوجة ثابتاً.

2.2 تقدير التباين عبر طرق البوتستراب

يقيم البحث ثلاثة نهج لتقدير الانحراف المعياري لقيم شابلي تحت تصميم المعاينة الجديد:

1. الطريقة الحدسية غير الصالحة: مقدر تباين هورفيتز-تومبسون (Horvitz-Thompson) القياسي المطبق مباشرة على مشكلة المربعات الصغرى الموزونة. ويوضح المؤلف أن هذه الطريقة غير صالحة لأنها تفشل في مراعاة التبعيات المحددة التي تفرضها استراتيجية الاقتران وبنية مصفوفة $Z^T W Z$ في سياق KernelSHAP.
2. بوتستراب النصف المزدوج (Antal and Tillé, 2014): طريقة معروفة للمجتمعات المحدودة حيث يتم اختيار الوحدات عبر معاينة برنولي، وتُختار الوحدات غير المختارة مرتين عشوائياً. وقد تم تنفيذ هذه الطريقة لأغراض المقارنة.
3. البوتستراب المتماثل (مساهمة جديدة): طريقة بوتستراب مبتكرة تم تطويرها خصيصاً لهذا السياق.
   • الآلية: في كل عينة بوتستراب، يمكن لكل وحدة من العينة الأصلية أن تظهر 0 أو 1 أو 2 من المرات.
   • التماثل: تضمن الطريقة أن إجمالي عدد الوحدات التي تظهر 0 مرة يساوي إجمالي عدد الوحدات التي تظهر مرتين.
   • الاحتمالات: يتم تعريف احتمالات ظهور الوحدة $k$ لعدد $S_k$ من المرات كما يلي:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • الخصائص: يضمن هذا البناء أن القيمة المتوقعة $E(S_k) = 1$ والتباين $Var(S_k) = 1 - \frac{n}{N}$، مما يحقق الشروط اللازمة لتقدير التباين الصالح في معاينة المجتمع المحدود (اتساق هورفيتز-تومبسون).
   • التعامل مع القيم غير الصحيحة: عندما يكون العدد المتوقع لظهور "0" أو "2" عدداً غير صحيح، يتم إدخال متغير عشوائي برنولي للتنقل بين القيم الصحيحة المتجاورة، مما يضمن بقاء الإجراء آلياً بالكامل.

2.3 التنفيذ الحسابي

يتم تقدير دالة المساهمة $v(S)$ باستخدام الانحدار على التحالفات المأخوذة كعينات. يعتمد التنفيذ على المصفوفات المتفرقة (sparse matrices) وتحلل تشوليسكي (Cholesky decomposition) (حزمة Matrix) للتعامل مع النماذج الخطية بكفاءة، وهو قادر على تقدير المتوسطات لأكثر من 65,000 نموذج خطي على نواة واحدة في غضون دقائق (Aanes, 2025).

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

1. إطار عمل المعاينة: دمج توزيع والينيوس للهندسة المفرطة غير المركزية في إطار عمل KernelSHAP لتمكين المعاينة بدون استبدال بكفاءة، وتجنب عدم الكفاءة المتمثلة في مسألة جامع الكوبونات المتأصلة في المعاينة مع الاستبدال.
2. البوتستراب المتماثل: تقديم طريقة بوتستراب جديدة وفعالة حسابياً مصممة خصيصاً للمعاينة بدون استبدال في المجتمعات المحدودة. وهي تلبي شروط العزوم (المتوسط والتباين) اللازمة لتقدير التباين غير المنحاز في هذا السياق.
3. تحليل تقدير التباين: مقارنة صارمة لمقدرات التباين، توضح أن البوتستراب القياسي غير صالح لهذا التصميم المحدد وأن البوتستراب المتماثل الجديد يتفوق على أو يماثل طريقة البوتستراب النصف مزدوج (Antal and Tillé, 2014).

4. النتائج

أُجريت دراستان للمحاكاة باستخدام مجموعة بيانات "Life Expectancy" من Kaggle، لمقارنة الطريقة الجديدة مع حزمة shapr البرمجية بلغة R (الإصدار 1.0.7)، والتي تأخذ عينات مع الاستبدال.

• دراسة محاكاة صغيرة (5 ميزات، 16 تحالفاً):
  • أنتجت طريقة المعاينة الجديدة تقديرات لقيم شابلي بانحرافات معيارية قابلة للمقارنة مع shapr.
  • أدى بوتستراب Antal-Tillé إلى أداء ضعيف، حيث نتج عنه تكرار مصفوفات غير كاملة الرتبة ($Z^T W Z$) وتقديرات غير دقيقة للتباين.
  • أدى البوتستراب المتماثل أداءً أفضل بكثير من Antal-Tillé، رغم أنه أنتج أحياناً انحرافات معيارية "متساهلة" (أصغر قليلاً) مقارنة بالحقيقة الأرضية (إعادة أخذ عينات من جميع التحالفات).
• دراسة محاكاة كبيرة (16 ميزة، 402 تحالفاً):
  • أنتج كل من البوتستراب المتماثل و Antal-Tillé تقديرات غير قابلة للتمييز للانحراف المعياري.
  • أدت كلتا الطريقتين الجديدتين في البوتستراب أداءً أفضل قليلاً من إجراء البوتستراب المدمج في shapr ، والذي مال إلى التقليل من قدر الانحرافات المعيارية لعدة متغيرات.
  • أدت خوارزمية المعاينة الجديدة (بدون استبدال) أداءً مشابهاً لطريقة shapr (مع الاستبدال) من حيث دقة تقديرات قيم شابلي نفسها.

5. الأهمية والخاتمة

خلصت الورقة إلى أن الخوارزمية المقترحة، التي تجمع بين المعاينة بدون استبدال عبر توزيع والينيوس مع البوتستراب المتماثل الجديد، تقدم بديلاً قوياً لتنفيذات KernelSHAP الحالية.

• الأداء: تؤدي الطريقة الجديدة أداءً "مشابهاً" لطريقة KernelSHAP المحسنة في حزمة shapr فيما يتعلق بتقديرات النقاط.
• تقدير التباين: تم تسليط الضوء على البوتستراب المتماثل كطريقة "سريعة جداً من الناحية الحسابية، وسهلة الفهم" وتعمل بشكل جيد، لا سيما في دراسات المحاكاة الكبيرة. وهي تعالج الفجوة في الأدبيات المتعلقة بوجود طريقة بوتستراب "جاهزة للاستخدام" للمعاينة العشوائية بدون استبدال في المجتمعات المحدودة.
• القيود: يشير المؤلف بتواضع إلى أنه في أصغر دراسة، أنتج البوتستراب المتماثل أحياناً انحرافات معيارية أصغر قليلاً (متساهلة) لبعض المتغيرات، رغم أنه التقط باستمرار أكبر الانحرافات المعيارية.
• القابلية للتطبيق: الطريقة مصممة للسيناريوهات التي يتم فيها تقدير دالة المساهمة عبر النماذج الخطية أو النماذج الخطية المعممة (حيث تكون التنبؤات خطية على مقياس محول)، مع الاستفادة من تقنيات الحساب السريع.

يؤسس هذا العمل على أن نظرية المجتمع المحدود يمكن تطبيقها بنجاح على تقدير قيمة شابلي لتحسين كفاءة المعاينة وتوفير تقديرات تباين صالحة، متجاوزة بذلك القيود النظرية لافتراضات البوتستراب التقليدية (i.i.d.).