ملخص تقني: مُقدِّر غريب لقيم شابلي (OddSHAP)

بيان المشكلة

تُعد قيمة شابلي (Shapley value) الإطار المعياري للعزو (attribution) في تعلم الآلة، حيث تُستخدم لأهمية الميزات، وتقييم البيانات، والاستدلال السببي. ومع ذلك، فإن حسابها الدقيق يكون غير قابل للحل عادةً بسبب العدد الأسي للتحالفات ($2^d$) المطلوبة للتقييم. وبينما توجد طرق تقريبية، فإن أكثر المُقدِّرات فعالية تعتمد غالباً على "أخذ العينات المزدوجة" (sampling a coalition $S$ and its complement $S^c$)، وهو نهج استدلالي يحسن الدقة تجريبياً ولكنه يفتقر إلى تبرير نظري صارم لسبب نجاحه، لا سيما فيما يتعلق بالتفاعلات من الرتب العليا. علاوة على ذلك، تواجه طرق الانحدار متعدد الحدود الحالية ذات الرتب العليا (مثل PolySHAP) عقبة في القابلية للتوسع، حيث تنمو التكلفة الحسابية تربيعياً مع قاعدة متعدد الحدود، مما يحد من تطبيقها في البيئات عالية الأبعاد.

المنهجية

يقترح المؤلفون OddSHAP، وهو مُقدِّر جديد يستفيد من خاصية هيكلية جوهرية لقيمة شابلي: وهي أنها تعتمد حصرياً على المكون الفردي (odd component) لدالة القيمة $f$.

الأساس النظري

1. التفكيك الفردي-الزوجي (Odd-Even Decomposition): يمكن تفكيك أي دالة مجموعة $f$ بشكل فريد إلى مكون فردي ($f_{odd}$) ومكون زوجي ($f_{even}$)، حيث $f_{odd}(S) = -f_{odd}(S^c)$ و $f_{even}(S) = f_{even}(S^c)$.
2. خاصية قيمة شابلي: يثبت المؤلفون أن $\phi_i(f) = \phi_i(f_{odd})$ لجميع اللاعبين $i$. حيث يساهم المكون الزوجي بصفر في قيمة شابلي.
3. آلية أخذ العينات المزدوجة: تقدم الورقة أول تبرير نظري عام لأخذ العينات المزدوجة. فمن خلال أخذ عينات من أزواج $(S, S^c)$ بأوزان متماثلة، تعمل مشكلة المربعات الصغرى الموزونة على تعامد (orthogonalization) (أي فصل) مشكلة التحسين إلى مشكلات مستقلة للمكونين الفردي والزوجي. وبما أن المكون الزوجي ليس ذا صلة، فإن أخذ العينات المزدوجة يعزل فعلياً الإشارة المطلوبة لقيم شابلي. وهذا يحل تخميناً مفاده أن أخذ العينات المزدوجة باستخدام ملاءمة من الرتبة $k$ (حيث $k$ فردي) يكافئ ملاءمة من الرتبة $k+1$.

تصميم الخوارزمية: OddSHAP

لاستغلال هذه الرؤية مع تجنب الانفجار التوليفي لجميع الحدود ذات الرتب العليا، يعمل OddSHAP في قاعدة فورييه (Fourier basis) بدلاً من قاعدة الإجماع (unanimity basis).

• ميزة قاعدة فورييه: في قاعدة فورييه، تكون دالة القاعدة $\chi_T$ فردية إذا وفقط إذا كان عدد عناصرها $|T|$ فردياً. وهذا يسمح بفصل واضح بين الحدود الفردية والزوجية، على عكس قاعدة الإجماع.
• عملية من مرحلتين:
  1. فحص التفاعل (Interaction Screening): يتم ملاءمة نموذج بديل يعتمد على الأشجار المعززة بالتدريج (GBT) للتحالفات التي تم أخذ عينات منها. وباستخدام طريقة مثل ProxySPEX، تستخرج الخوارزمية مجموعة متفرقة من معاملات فورييه ذات التأثير العالي والفردية الرتبة. وهذا يتجنب الحاجة لملاءمة جميع التفاعلات الممكنة.
  2. الانحدار الفردي (Odd Regression): يتم إجراء انحدار المربعات الصغرى الموزونة حصرياً على حدود فورييه الفردية المختارة (بالإضافة إلى الحدود الخطية)، مع الالتزام بمطابقة دالة القيمة عند المجموعات الفارغة والكاملة.
• الكفاءة: من خلال قصر الانحدار على الفضاء الفردي واستخدام نموذج بديل لاختيار الحدود، تحقق طريقة OddSHAP تعقيداً زمنياً حدودياً بالنسبة لميزانية أخذ العينات، متجاوزة بذلك مقياس $O(d^k)$ الذي تفرضه طرق متعددات الحدود ذات الرتب الثابتة.

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

1. التوحيد النظري لأخذ العينات المزدوجة: تثبت الورقة أن أخذ العينات المزدوجة يفصل ضمنياً هدف الانحدار إلى مكونات فردية وزوجية، مما يوفر تفسيراً صارماً لنجاحه التجريبي ويعمم النتائج السابقة التي كانت مقتصرة على التفاعلات منخفضة الرتب.
2. مُقدِّر OddSHAP: مُقدِّر متسق يقوم بعمل انحدار متعدد الحدود فقط على مجموعة متفرقة مختارة من دالات قاعدة فورييه ذات الرتب الفردية. وهو يقوم بتصفية المكونات الزوجية غير ذات الصلة ويحدد التفاعلات عالية التأثير عبر نموذج بديل.
3. الأداء المتميز (State-of-the-Art): تظهر الاختبارات المرجعية المكثفة أن OddSHAP يحقق دقة تقدير متفوقة مقارنة بالطرق الموجودة (بما في ذلك RegressionMSR و LeverageSHAP و PolySHAP) تحت ميزانيات أخذ عينات أكبر، لا سيما في البيئات عالية الأبعاد.

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

قيم المؤلفون أداء OddSHAP على ثماني دالات قيمة تتراوح من $d=14$ (DistilBERT) إلى $d=101$ (مجموعة بيانات الجريمة)، لتشمل مجالات التعلم العميق (الصور والنصوص) والبيانات الجدولية.

• الدقة: حققت OddSHAP باستمرار أدنى متوسط خطأ تربيعي (MSE) وأفضل متوسط ترتيب عبر الاختبارات المرجعية، خاصة عندما تكون ميزانية أخذ العينات $m$ كافية لاكتشاف التفاعلات ($m > \eta \cdot d$).
• المقارنة مع FFD: تفوقت OddSHAP على تصميم العوامل الكسرية ذي الميزانية الثابتة (FFD-RD) في بنيات التعلم العميق (ViT, DistilBERT)، حيث تكون التفاعلات عالية الرتبة ذات أهمية كبيرة. وعلى العكس من ذلك، قدم FFD-RD أداءً أفضل قليلاً في مجموعات البيانات الجدولية القائمة على الأشجار حيث تتلاشى التفاعلات عالية الرتب بسرعة، مما يؤكد المقايضات الخاصة بكل مجال.
• دراسات الاستئصال (Ablation Studies):
  • المزدوج مقابل غير المزدوج: تفوق أخذ العينات المزدوج باستمرار على أخذ العينات غير المزدوج.
  • الفردي مقابل جميع التفاعلات: تحت أخذ العينات المزدوج، لم يوفر تضمين التفاعلات الزوجية أي فائدة بل أدى إلى تراجع طفيف في الأداء من خلال استهلاك ميزانية التفاعل بحدود تلغي بعضها رياضياً.
  • التشتت (Sparsity): أدى إدراج عدد معتدل من التفاعلات الفردية (يتم التحكم فيه عبر عامل متغير الانحدار $\eta$) إلى تقليل الخطأ بشكل كبير مقارنة بالنماذج الخطية، رغم حدوث فرط في التخصيص (overfitting) عند زيادة عدد التفاعلات بشكل كبير.

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

تدعي الورقة أن OddSHAP توفر إطار عمل مرن الميزانية يتكيف بقوة عبر هياكل التفاعل المتنوعة. وتكمن أهميتها الأساسية في:

1. حل تخمين مفتوح: توفر الآلية النظرية الأساسية التي تفسر سبب نجاح أخذ العينات المزدوج، منتقلة من مجرد الملاحظة التجريبية إلى البرهان الهيكلي.
2. القابلية للتوسع: تحافظ على القدرة التعبيرية للتقريبات عالية الرتب دون تحمل تكاليفها التوليفية الباهظة من خلال قصر النموذج على الفضاء الفردي.
3. المتانة: على عكس الطرق التي تعتمد على افتراضات قطع صارمة (مثل FFD)، تظل OddSHAP فعالة في مجالات التعلم العميق المعقدة حيث لا يمكن إهمال التفاعلات عالية الرتب، مع الحفاظ على التنافسية في المجالات الجدولية المتفرقة.

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