Proxy-Based Approximation of Shapley and Banzhaf Interactions

ملخص تقني: التقريب القائم على الوكيل لقيم شابلي وبانزاف التفاعلية

بيان المشكلة
تعتمد تطبيقات تعلم الآلة الحديثة بشكل متزايد على نظرية الألعاب التعاونية لتفسير سلوك النماذج، وتحديداً باستخدام قيم "شابلي" (Shapley) و"بانزاف" (Banzhaf) لنسب المساهمات إلى الميزات الفردية. ومع ذلك، فإن فهم الديناميكيات المعقدة وغير الخطية يتطلب غالباً تحليل التفاعلات من الرتب العليا (مجموعات فرعية من الميزات) بدلاً من مجرد تأثيرات العناصر المفردة. إن حساب مؤشرات التفاعل الكاردينالية-الاحتمالية الدقيقة أمر مستعصٍ حاسوبياً لعدد كبير من الميزات ($n$) بسبب النمو الأسي لفضاء التحالفات ($2^n$).

تواجه المقدرات الحالية مقايضة حرجة بين السرعة والدقة:

• الطرق القائمة على أخذ العينات (Sampling-based methods): (مثل SHAP-IQ وKernelSHAP-IQ) غالباً ما تكون دقيقة ولكنها تتطلب ميزانيات عينات غير عملية لتناسب العدد الهائل من الحدود ذات الرتب العليا، مما يؤدي إلى معاناة من تباين عالٍ يتوسع بشكل سيئ مع رتبة التفاعل.
• الطرق القائمة على الوكيل (Proxy-based methods): (مثل ProxySPEX) توفر السرعة ولكنها تعتمد على الاستخراج القائم على تحويل فوريه (Fourier) من بدائل الأشجار. يعاني هذا النهج من تعقيد أسي بالنسبة لعمق الشجرة، وغالباً ما يتطلب تقليلاً عدوانياً (truncation) يضر بالدقة. علاوة على ذلك، فإن طرق الوكيل الحالية تعيد عادةً تفاعلات "الوكيل" بدلاً من دالة القيمة الأصلية، مما يؤدي إلى حدوث انحياز.

المنهجية: ProxySHAP
يقترح المؤلفون ProxySHAF، وهو إطار عمل يوفق بين كفاءة العينة للنماذج البديلة القائمة على الأشجار وبين مسار مبدئي للاتساق عبر تصحيح البواقي (residual correction). يقوم هذا الأسلوب بتفكيك مؤشر التفاعل المستهدف $\phi^p_S(\nu)$ إلى مكونين:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{الوكيل الدقيق}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{الباقي}}$$

1. ملاءمة الوكيل (المرحلة 1): يتم تدريب نموذج قائم على الأشجار (مثل XGBoost أو LightGBM) أو نموذج خطي مع ميزات تفاعلية لتقريب دالة القيمة الأصلية $\nu$.
2. استخراج الوكيل الدقيق (المرحلة 2): على عكس الطرق السابقة التي تستخرج معاملات فوريه، يقدم ProxySHAP تعميماً متعدد الحدود لـ Interventional TreeSHAP. يسمح هذا بحساب أي مؤشر تفاعل كاردينالي-احتمالي بدقة (بما في ذلك شابلي وبانزاف) مباشرة من هيكل الشجرة.
   • تعتمد الطريقة على تمثيل موبيوس (Möbius representation) لألعاب المؤشرات المعرفة بواسطة أوراق الأشجار.
   • تتجنب التعقيد الأسي $O(4^d)$ الخاص بالاستخراج القائم على فوريه (حيث $d$ هو عمق الشجرة)، محققةً زمن تشغيل قدره $O(n_{nodes})$ لكل تفاعل.
3. تعديل البواقي: لتصحيح الانحياز الناتج عن عدم مطابقة الوكيل تماماً لـ $\nu$، يقوم الأسلوب بتقدير تفاعلات لعبة البواقي $(\nu - \hat{\nu}_T)$ باستخدام إعادة استخدام العينات القصوى (MSR).
   • يقدم البحث تحليلاً نظرياً يوضح أن تباين مُقدر MSR للتفاعلات من الرتبة $k$ يتوسع كـ $O(n^{k-1}/|T|)$.
   • بناءً على ذلك، يستنتج المؤلفون شروطاً يكون فيها تعديل MSR مفيداً: بشكل أساسي في الإعدادات منخفضة الأبعاد ($n < 30$) أو عندما تكون ميزانية أخذ العينات $|T|$ كبيرة بما يكفي بالنسبة لـ $n^{k-1}$. بالنسبة للتفاعلات عالية الرتبة في الألعاب الكبيرة، يمكن أن يفوق تباين التصحيح خفض الانحياز.

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

1. إطار عمل ProxySHAP: استراتيجية تقدير مبتكرة تجمع بين الوكيل البديل القائم على الأشجار وتصحيح البواقي، مما يتيح التقريب الفعال والدقيق للتفاعلات من الرتب العليا.
2. التقدم النظري:
   • اشتقاق خوارزمية ذات زمن تشغيل متعدد الحدود لاستخراج مؤشرات التفاعل الكاردينالية-الاحتمالية الدقيقة من مجموعات الأشجار، متجاوزةً بذلك الاعتماد الأسي على العمق الذي تعاني منه طرق فوريه السابقة.
   • توصيف رسمي لنمو التباين لـ MSR للتفاعلات من الرتب العليا، مما يضع شروطاً صريحة (من حيث $n$، والميزانية، ورتبة التفاعل $k$) متى كان تعديل البواقي يحسن الأداء أو يقلله.
3. الأداء التجريبي: أظهرت الاختبارات المرجعية المكثفة عبر 47 مجموعة بيانات (جداول، رؤية، لغة، رسوم بيانية، ورؤية-لغة) أن ProxySHAP يضع معياراً جديداً للأداء الأفضل (state-of-the-art). فقد حقق أدنى خطأ في كل من أنظمة الميزانية الصغيرة (حيث يتفوق على ProxySPEX) والأنظمة ذات الميزانية الكبيرة (حيث يتفوق على KernelSHAP-IQ).

النتائج

• الدقة: يتفوق ProxySHAP باستمرار على النماذج المرجعية (KernelSHAP-IQ، ProxySPEX، SHAP-IQ) من حيث متوسط مربع الخطأ النسبي (MSE). وفي التطبيقات واسعة النطاق مع آلاف الميزات (مثل Bioresponse مع $n=1776$)، يظل ProxySHAP فعالاً في حين تصبح الطرق الأخرى غير مجدية حاسوبياً أو غير دقيقة.
• الكفاءة: توفر خوارزمية الاستخراج ذات الزمن متعدد الحدود تسريعاً بمقدار عدة مراتب عشرية (من 10 إلى 1000 ضعف) مقارنة بالاستخراج القائم على فوريه، لا سيما مع زيادة عمق الشجرة.
• المهام اللاحقة: في تطبيق محدد لشرح نموذج الرؤية واللغة SigLIP-2 (لعبة FIxLIP)، أظهر ProxySHAP دقة فائقة (مقاسة بمنحنى الإدراج والحذف - AUC) مقارنة بنماذج الانحدار الخطي وProxySPEX.
• الحساسية للمعلمات الفائقة: تسلط الدراسة الضوء على أن جودة الوكيل أمر بالغ الأهمية. حيث أدى تحسين المعلمات الفائقة (HPO) إلى تحسين الأداء بشكل ملحوظ، واقتُرح تكوين افتراضي "مدعوم بـ HPO" (باستخدام العديد من الأشجار الضحلة) للموازنة بين التكلفة والدقة.

الأهمية والادعاءات
يزعم البحث أن ProxySHAP يحل المقايضة طويلة الأمد بين السرعة والدقة في تقدير التفاعل. ومن خلال توفير آلية استخراج دقيقة للوكلاء القائمين على الأشجار واستراتيجية قائمة على أسس نظرية لتصحيح البواقي، فإنه يتيح القياس الكمي القابل للتوسع للاعتمادات المعقدة في أنظمة الذكاء الاصطناعي الحديثة. ويؤكد المؤلفون أن طريقتهم ذات قيمة خاصة لـ:

• التطبيقات واسعة النطاق: التعامل مع مجموعات البيانات التي تحتوي على آلاف الميزات حيث يكون الحساب الدقيق مستحيلاً.
• التفاعلات عالية الرتبة: توفير تقديرات موثوقة للتفاعلات التي تتجاوز التأثيرات الثنائية، والتي تعد ضرورية لفهم التبعيات عبر الوسائط (مثل نماذج الرؤية واللغة) والتآزرات المعقدة للميزات.
• النشر العملي: تقديم مُقدر "الأفضل في فئته" (state-of-the-art) يتسم بالمتانة عبر قيود الميزانية وأنواع النماذج المختلفة، مدعوماً بتنفيذ بلغة C++ قابل للتوسع.

يشير المؤلفون بتواضع إلى وجود قيود، وتحديداً أن جودة التقريب تعتمد على الوكيل الملائم (مما يتطلب ضبطاً دقيقاً للمعلمات الفائقة)، وأن تباين تصحيح البواقي يحد من فائدته في الإعدادات عالية الأبعاد جداً للتفاعلات من الرتب العليا. ويُقترح في العمل المستقبلي استكشاف فئات بديلة للوكلاء ومقدرات للبواقي تتوسع بشكل أكثر سلاسة.