ملخص تقني: تقريب قيمة شابلي بناءً على الألعاب ذات الإضافة k (k-Additive Games)

بيان المشكلة

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

المنهجية: SVAkADD

يقترح المؤلفون طريقة SVAkADD (تقريب قيمة شابلي تحت شرط الإضافة k)، وهي طريقة مبتكرة تقرب قيم شابلي عن طريق ملاءمة لعبة بديلة ذات بنية "إضافة k" (k-additive surrogate game) لمجموعة عينة من قيم التحالفات.

المفهوم الجوهري: الإضافة k (k-Additivity)

بدلاً من تقدير قيمة شابلي مباشرة عبر أخذ عينات مونت كارلو للمساهمات الهامشية، تفترض SVAkADD أن اللعبة الأساسية يمكن تقريبها بواسطة لعبة إضافة k. في مثل هذه اللعبة، يُفترض أن مؤشرات التفاعل (تفاعلات شابلي) للتحالفات التي يزيد حجمها عن $k$ هي صفر.

• التمثيل: يتم التعبير عن دالة القيمة $\nu_k$ للعبة البديلة كتحويل خطي لمؤشرات تفاعل شابلي $I(B)$ لجميع التحالفات $B$ حيث $|B| \leq k$.
• تقليل المعلمات: يقلل هذا الافتراض بشكل كبير من عدد المعلمات المطلوبة لتعريف اللعبة من $2^n$ إلى عدد حدودي (على سبيل المثال، $O(n^k)$)، مما يجعل عملية التحسين قابلة للتنفيذ.

إطار التحسين

تصيغ الطريقة التقريب كمسألة أقل مربعات موزونة مقيدة (constrained weighted least squares problem):

1. الهدف: تقليل الخطأ المربع الموزون بين قيم التحالف المرصودة $\nu(A)$ من اللعبة الأصلية والقيم المتوقعة من بديل الإضافة k وهو $\nu_k(A)$.
2. القيود: يفرض التحسين "بديهية الكفاءة" (efficiency axiom)، مما يضمن أن مجموع قيم شابلي للبديل يساوي الفرق بين قيمة التحالف الأكبر وقيمة المجموعة الفارغة ($\nu(N) - \nu(\emptyset)$).
3. التوزين: اشتق المؤلفون تحليلياً أوزاناً محددة $w^*_A = \binom{n-2}{|A|-1}^{-1}$ لمسألة أقل المربعات الموزونة. وقد أثبتوا أنه إذا تم رصد جميع التحالفات، فإن حل عملية التحسين المحددة هذه يعطي قيم شابلي الدقيقة، بغض النظر عما إذا كانت اللعبة الأصلية هي حقاً "إضافة k" أم لا.

الخوارمية

تسير خوارزمية SVAkADD وفق الخطوات التالية:

1. أخذ العينات: تقوم بتقييم المجموعة الفارغة $\emptyset$ والتحالف الأكبر $N$ بشكل حتمي. ثم تأخذ عينات لـ $T-2$ من التحالفات الإضافية من مجموعة القوى (باستثناء $\emptyset$ و $N$) بناءً على توزيع احتمالي يتناسب مع الأوزان المستمدة $w^*_A$.
2. الملاءمة: تقوم بحل مسألة أقل المربعات الموزونة المقيدة باستخدام البيانات المأخوذة لتقدير مؤشرات التفاعل $I(B)$ لـ $|B| \leq k$.
3. الاستخراج: يتم الحصول على قيم شابلي للعبة البديلة مباشرة كأوزان التفاعل الأحادية ($I(\{i\})$)، والتي تعمل كتقديرات للعبة الأصلية.

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

1. طريقة تقريب مبتكرة: تقديم SVAkADD، التي تطابق لعبة بديلة ذات إضافة k مع البيانات المأخوذة، مما يوفر بديلاً مهيكلاً لأخذ عينات المساهمة الهامشية المباشرة.
2. الرصانة النظرية: إثبات تحليلي أنه بالنسبة لـ $k=1, 2, 3$، فإن تحسين أقل المربعات الموزونة المقترح يعطي قيم شابلي الدقيقة عند رصد مجموعة التحالفات الكاملة. وهذا يثبت أن "الإضافة k" هي أداة للتقريب وليست افتراضاً مقيداً لبنية اللعبة.
3. الاستقلالية عن النموذج والمجال: لا تتطلب الطة خصائص هيكلية محددة لدالة القيمة، مما يجعلها قابلة للتطبيق على أي لعبة تعاونية، بما في ذلك تفسيرات الميزات المحلية والعالمية في تعلم الآلة.
4. التقييم التجريبي: مقارنة شاملة مع أفضل المعايير المرجعية (KernelSHAP, Stratified SVARM, Stratified sampling) عبر مختلف مجموعات البيانات وأنواع التفسير (عالمي، محلي، غير مُشرف عليه).

النتائج التجريبية

قيم المؤلفون أداء SVAkADD على مجموعات بيانات تتراوح من 9 إلى 14 ميزة عبر مهام عالمية، محلية، وغير مُشرفة عليها.

• التقارب: تظهر الطريقة أداءً تنافسياً. وبينما قد تظهر خطأً أعلى عند ميزانيات عينات منخفضة جداً مقارنة ببعض المعايير المرجعية، إلا أنها تتقارب بشكل أسرع نحو قيم شابلي الدقيقة مع زيادة الميزانية، خاصة لمهام الإسناد المحلي في مجموعات بيانات Adult و ImageNet.
• اختيار $k$: تسلط التجارب الضوء على المقايضة بين المرونة وسرعة التقارب.
  • $k$ المنخفض (1 أو 2) غالباً ما يتقارب ببطء بسبب عدم كفاية المرونة لنمذجة تفاعلات الميزات المعقدة.
  • $k$ الأعلى (3 أو 4) يتقارب عموماً بشكل أسرع بكثير ويتفوق على النماذج ذات الرتب الأدنى بعد بضع عينات.
  • يقترح المؤلفون $k=3$ كخيار افتلي مفضل، حيث يوفر توازناً جيداً بين تقليل الخطأ وعدد المعلمات المطلوبة.
• المقارنة: تنافس SVAkADD باستمرار أو تتفوق على KernelSHAP و Stratified SVARM، لا سيما في السيناريوهات التي تتطلب دقة عالية مع ميزانيات عينات متوسطة.

الأهمية والادعاءات

يزعم البحث أن SVAkADD توفر نهجاً راسخاً نظرياً وفعالاً عملياً لتقريب قيمة شابلي. ومن خلال الاستفادة من بنية ألعاب الإضافة k، تحول الطريقة مسألة التقدير إلى عملية تحسين ذات زمن حدودي تضمن الاستعادة الدقيقة تحت شروط توزين محددة.

يؤكد المؤلفون أن نهجهم مستقل عن النموذج ومستقل عن المجال، وقادر على التعامل مع أي صيغة للعبة تعاونية. وخلصوا إلى أنه بينما لا يهيمن منهج تقريب واحد على جميع السيناريوهات (اعتماداً على مجموعة البيانات، المهمة، والميزانية)، فإن SVAkADD تقدم بديلاً قوياً يستفيد من الخصائص النظرية لتفاعلات شابلي لتحقيق دقة عالية. كما تشير الورقة إلى أن الطريقة توفر بشكل طبيعي تقديرات لتأثيرات التفاعل (التكرار أو التكامل) عندما تكون $k \geq 2$، مما يوفر قابلية تفسير إضافية تتجاوز أهمية الميزات الفردية.