Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

ملخص تقني: قيمة شابلي الدقيقة ذات الزمن الخطي الموزع لطرق النواة الضربيه (Product-Kernel Methods)

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

المنهجية
تقدم هذه الورقة خوارزمية PKeX-Shapley، وهي مصممة لحساب قيم شابلي الدقيقة لجميع الميزات $d$ لـ طرق النواة الضربيه (مثل آلات ناقلات الدعم SVM، وانحدار ريج ريجرسن للنواة KRR) في زمن تربيعي بالنسبة لعدد الميزات ($O(d^2)$)، أو زمن خطي موزع لكل ميزة.

تعتمد المنهجية على ثلاثة مكونات أساسية:

1. مشغل الإزالة الخالي من التوزيع (Distribution-Free Removal Operator): يركز المؤلفون على الفئة الفرعية من النماذج التي تستخدم النوى الضربيه، حيث تتفكك دالة النواة $k(x, x') = \prod_{j=1}^d k_j(x_j, x'_j)$ إلى حاصل ضرب دوال. وقد حددوا مشغل إزالة طبيعي متأصل في هذا الهيكل: إزالة الميزة $j$ تقابل استبدال عامل النواة $k_j$ بالوحدة الضربية ($1$). هذا الخيار يحافظ على البنية الضربيه، ولا يتطلب أي توزيع خلفي، ويؤدي إلى دالة قيمة خالية من المعلمات.

   • بخلاف دوال القيمة التدخلية أو الرصدية التي تتطلب أخذ عينات، يتم تعريف دالة القيمة هذه عبر التفكك الوظيفي.
   • تُعطى دالة القيمة للمجموعة $S$ كالتالي: $v_x(S) = \alpha^\top k_S(X_S, x_S) - f_\emptyset$، حيث $f_\emptyset$ هو ثابت يلغي بعضه البعض في المساهمات الهامشية. هذه الصيغة لا تتطلب أخذ عينات أو تقدير كثافة.

2. التفكك الوظيفي (Functional Decomposition): بالاستفادة من مشغل الإزالة، يمكن تفكيك النموذج $f(x)$ بشكل فريد إلى مجموع من المكونات المفهرسة بمجموعات الميزات: $f(x) = \sum_{S \subseteq D} f_S(x_S)$. ويتم اشتقاق المكونات عبر تحويل موبيوس (Möbius inversion) على شبكة المجموعات الجزئية، مما يعطي صيغة مغلقة: $f_S(x_S) = \sum_{i=1}^n \alpha_i \prod_{j \in S} (k_j(x_j, x^{(i)}_j) - 1)$.

3. الحساب المتكرر عبر كثيرات الحدود المتماثلة الأولية (ESPs):

   • يتم التعبير عن قيمة شابلي لميزة واحدة كمجموع مرجح للمساهمات الهامشية، والتي تتفكك إلى حدود تتضمن كثيرات الحدود المتماثلة الأولية (ESPs) لتقييمات النواة.
   • الحساب المباشر لـ ESPs لكل ميزة سيكون غير فعال. لذا، اشتق المؤلفون صيغة تكرارية تعتمد على متطابقات نيوتن.
   • لحساب جميع قيم شابلي $d$ بشكل مشترك، يستخدمون بناء البادئة واللاحقة (prefix–suffix construction). يقومون بتعريف كثيرات حدود مولدة للبادئة (الميزات قبل $j$) واللاحقة (الميزات بعد $j$). ومن خلال ضرب هذه كثيرات الحدود، يستعيدون الـ ESPs لمجموعة "ترك واحدة" $Z_{-j}$.
   • يسمح هذا بحساب جميع قيم شابلي في زمن $O(d^2 n)$، حيث $n$ هو عدد العينات. الخوارزمية مستقرة عددياً، وتعتمد فقط على عمليات الجمع والضرب العنصرية، متجنبة عدم الاستقرار العددي المرتبط بطرق استكمال كثيرات الحدود (مثل استكمال تشيبيشيف أو فوريه) المستخدمة في طرق أخرى دقيقة مثل TreeSHAP عند تطبيقها على أبعاد عالية.

التوسع في التباينات الإحصائية
تم توسيع الإطار ليشمل ما وراء النمذجة التنبؤية إلى التباينات الإحصائية القائمة على النواة، وتحديداً:

• التباعد المتوسط الأقصى (MMD): يُستخدم لقياس القرب التوزيعي. يوفر مشغل الإزالة دالة قيمة تخصص التباين الإجمالي بين توزيعين إلى متغيرات فردية.
• معيار هيلبرت-شميدت للاستقلال (HSIC): يُستخدم لقياس الاعتماد بين المتغيرات العشوائية. توفر الطريقة تفككاً وظيفياً لـ HSIC، مما يسمح بنسب الاعتماد إلى ميزات محددة.

النتائج
تحقق الورقة من صحة PKeX-Shapley من خلال تجارب على مجموعات بيانات اصطناعية وواقعية:

• الدقة مقابل التقريب: في التفسيرات المحلية، تتفوق PKeX-Shapley (الدقيقة) بشكل كبير على التقديرات القائمة على أخذ العينات (مثل Kernel SHAP وRKHS-SHAP). ومع زيادة الأبعاد (مثلاً $d=50$)، تتطلب الطرق القائمة على أخذ العينات أحجام مجموعات جزئية ضخمة لتحقيق خطأ منخفض، بينما توفر PKeX-Shapley نتائج دقيقة بغض النظر عن البعد.
• اختيار الميزات: في تحليل الحساسية العالمي باستخدام HSIC، تحدد PKeX-Shapley بفعالية الميزات النشطة في مهام الانحدار الاصطناعية ذات الدوال متعددة الحدود والأسية، متفوقة على أو موازية للنماذج المرجعية مثل RKHS-SHAP وGEMFIX وBiSHAP.
• الكفاءة الحوسبية: يمكن للخوارزمية التوسع لتشمل 1,000 ميزة في ثوانٍ، بينما يقتصر الحساب المباشر (brute-force) على حوالي 20 ميزة فقط. وهي أسرع باستمرار من الطرق القائمة على أخذ العينات، حتى عندما تستخدم تلك الطرق عدداً صغيراً من عينات المجموعات الجزئية.
• الاستقرار العددي: تظهر التجارب التي تقارن استراتيجيات تجميع ESP مختلفة (التكرار التربيعي مقابل FFT/استكمال تشيبيشيف) أنه بينما تكون طرق الاستكمال سريعة، فإنها تعاني من عدم استقرار عددي كارثي عند أبعاد متوسطة ($d \approx 50$). أما التكرار التربيعي المقترح فيظل مستقراً حتى $d=1000$.

الأهمية والادعاءات
تدعي الورقة أن PKeX-Shapley تعالج التحديين الرئيسيين لحساب قيمة شابلي لطرق النواة:

1. الدقة دون تقريب: توفر دالة قيمة مغلقة وخالية من المعلمات، مما يلغي الحاجة إلى أخذ العينات وتقدير الكثافة، وبالتالي يزيل خطأ التقدير.
2. القابلية للتوسع: تحقق زمناً موزعاً خطياً لكل ميزة ($O(dn)$) للحساب الدقيق، وهو تحسن كبير عن التكلفة الأسية للحساب المباشر أو التباين العالي للطرق القائمة على أخذ العينات في البيئات عالية الأبعاد.

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