ملخص تقني: Quadrature-TreeSHAP

بيان المشكلة

تعتمد قابلية التفسير لنماذج تجميع الأشجار (مثل XGBoost وRandom Forests) بشكل كبير على قيم شابلي (Shapley values). وبينما يعد نهج Path-Dependent SHAP هو المعيار السائد نظراً لكفاءته، إلا أن الطرق الحالية تواجه مقايضات كبيرة تتعلق بـ وقت التشغيل المرتبط بالعمق، والاستقرار العددي، ودعم التفاعلات من الرتب العليا.

تُظهر أحدث الأساليب الحالية قيوداً محددة:

• تعمل TreeSHAP و GPUTreeSHAP بتعقيد زمني قدره $O(MTLD^2)$ (حيث $M$ هي العينات، $T$ هي الأشجار، $L$ هي الأوراق، و $D$ هو العمق).
• تقوم طرق مثل FastTreeSHAP v2 و Woodelf بتقليل التعقيد إلى $O(MTLD)$، لكنها تُدخل خطوات معالجة مسبقة تتزايد أسياً مع العمق، مما يجعلها غير عملية للأشجار العميقة.
• يحقق Linear TreeSHAP تعقيد $O(MTND)$ ولكنه يعاني من عدم الاستقرار العددي بسبب العمليات في الأساس أحادي الحد (monomial basis).
• يعمل TreeGrad-Shap على تحسين الاستقرار عبر صياغات التدرج (gradient formulations)، ولكنه يقتصر على التفسيرات من الدرجة الأولى.
• يمتد TreeSHAP-IQ إلى التفاعلات من الرتب العليا، ولكن تعقيده هو $O(MTLD \binom{F-1}{s-1})$، وهو ما يتوسع بشكل سيئ مع زيادة عدد الميزات ($F$) ورتبة التفاعل ($s$).

المنهجية

يقترح المؤلفون Quadrature-TreeSHAP، وهو إعادة صياغة لـ Path-Dependent TreeSHAP بناءً على تكامل غاوس-ليجندر (Gauss–Legendre quadrature) ومتعدد حدود تفاعل بانزاف الموزون (weighted-Banzhaf interaction polynomial).

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

تستفيد الطريقة من العلاقة بين قيم شابلي وقيم بانزاف الموزونة.

• متعدد حدود بانزاف الموزون: بالنسبة لورقة شجرة القرار $v$، يتم التعبير عن قيمة تفاعل بانزاف الموزونة لـ Path-Dependent لمجموعة فرعية من الميزات $S$ عند احتمال تضمين $p$ كمتعدد حدود $B^{(S)}_{p,v}$. يتم اشتقاق هذا المتعدد الحدود من بنية مسار الورقة وأوزان الحواف.
• استعادة التكامل: يتم استعادة قيم تفاعل شابلي عن طريق تكامل هذه المتعددات الحدود لبانزاف عبر احتمال المشاركة $p \in [0, 1]$:
  $$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$$
• تقريب التربيع (Quadrature Approximation): بدلاً من التكامل الرمزي، يستخدم المؤلفون تكامل غاوس-ليجندر لتقريب هذا التكامل:
  $$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$$

2. التنفيذ الخوارزمي

• صياغة النقطة الثابتة: تقوم الخوارزمية بإجراء عملية عبور واحدة للبحث في العمق أولاً (DFS) للشجرة. أثناء العبور، يتم نشر قيم متعدد حدود المسار عند مجموعة ثابتة من عقد غاوس-ليجندر (عادةً 8 عقد) بدلاً من توسيع المتعددات الحدود رمزياً.
• تقليل التعقيد:
  • نظرياً، درجة التكامل لترتيب التفاعل $s$ هي على الأكثر $d-s$ (حيث $d$ هو أقصى عدد للميزات الفريدة في المسار).
  • عملياً، يوضح المؤلفون أن 8 نقاط تربيع ثابتة كافية للوصول إلى دقة الآلة (float32) حتى للأشجار العميقة جداً.
  • هذا يزيل الاعتماد على عمق الشجرة $d$ من الحساب الداخلي، مما يقلل التعقيد الفعلي من $O(MTN \lceil d/2 \rceil)$ إلى $O(MTN)$ للرتبة الأولى، ومن $O(MTN d^s)$ إلى $O(MTN d^{s-1})$ للتفاعلات من الرتبة $s$.
• تسريع الأجهزة: نظرًا لأن الحساب يتضمن تقييم نفس المجموعة الثابتة من النقاط لكل مسار، فإن العمليات الحسابية تكون منتظمة. وهذا يسمح بتنفيذ SIMD (تعليمات واحدة، بيانات متعددة) فعال على وحدات المعالجة المركزية (CPUs) و SIMT (تعليمات واحدة، خيوط متعددة) على وحدات معالجة الرسومات (GPUs)، مما يلغي أعباء عمليات التعبئة والجدولة المطلوبة في GPUTreeSHAP.

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

1. خوارزمية لأي رتبة تفاعل: يقدم البحث خوارزمية لحساب قيم تفاعل شابلي لأي رتبة تحسن من تعقيد TreeSHAP-IQ من $O(MTLD \binom{F-1}{s-1})$ إلى $O(MTN d^s)$. وهذا يحقق مكاسب كبيرة عندما يتجاوز عدد الميزات عمق الشجرة ($F > D \ge d$).
2. إعادة الصياغة القائمة على التربيع: يقدم المؤلفون تحليلاً نظرياً وتجريبياً يوضح أن 8 نقاط غاوس-ليجندر كافية للوصول إلى دقة الآلة لقيم شابلي والتفاعلات، مما يفصل فعلياً بين وقت التشغيل وعمق الشجرة في الممارسة العملية.
3. الاستقرار العددي: من خلال تقييم المتعدد الحد الملخص عند عقد موجبة ومحدودة بدلاً من توسيع المعاملات في أساس أحادي الحد، تتجنب الطريقة الإلغاء الكارثي. ويدعي المؤلفون أن Quadrature-TreeSHAP أكثر استقراراً عددياً من TreeSHAP، خاصة للأشجار العميقة.
4. تنفيذ فعال للأجهزة: تم تنفيذ الطريقة بلغة C++ للمعالجات المركزية ودمجها في XGBoost لمعالجات الرسومات. وهي تستغل التوجيه الشعاعي (vectorization) (4 نقاط للمعالج المركزي و32 للرسومات) لتحقيق تسريع كبير مقارنة بالتنفيذات الحالية.
5. التكامل في المصادر المفتوحة: تم دمج التنفيذ في مكتبة XGBoost (ليحل محل خلفية TreeSHAP)، وهو متاح عبر استدعاءات API القياسية (pred_contribs=True و pred_interactions=True).

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

قيم المؤلفون Quadrature-TreeSHAP على 12 مجموعة اختبار من XGBoost (Adult, CalHousing, CovType, Fashion-MNIST) عبر أنظمة صغيرة وكبيرة ومتفرقة.

• الرتبة الأولى (قيم شابلي):
  • المعالج المركزي (CPU): أسرع من TreeSHAP بمقدار 1.06× إلى 10.59× (بمتوسط 3.84×).
  • معالج الرسومات (GPU): أسرع من GPUTreeSHAP بمقدار 1.84× إلى 6.95×.
• الرتبة الثانية (التفاعلات الزوجية):
  • المعالج المركزي (CPU): أسرع من TreeSHAP بمقدار 3.80× إلى 58.11× (بمتوسط 12.86×).
  • معالج الرسومات (GPU): أسرع من GPUTreeSHAP بمقدار يصل إلى 6.65× (رغم أن GPUTreeSHAP ظل منافساً في مهام معينة ذات العمق الصغير).
• التفاعلات من الرتب العليا (اختبارات بايثون):
  • مقارنة بـ TreeSHAP-IQ في التفاعلات من الدرجة الثالثة، كان Quadrature-TreeSHAP أسرع بمقدار 18.73× إلى 26.49×.
  • في مجموعة بيانات CovType-sparse، زاد التسريع مقارنة بـ TreeSHAP-IQ مع زيادة رتبة التفاعل، ليصل إلى 1209.37× عند الرتبة 6.
• الاستقرار العددي:
  • في اختبار Fashion-MNIST-sparse مع زيادة عمق الشجرة، أصبح TreeSHAP غير مستقر بعد العمق 32. بينما ظل Quadrature-TreeSHAP مستقراً، حيث حققت 6-8 نقاط دقة عالية.

الأهمية

يدعي البحث أن Quadrature-TreeSHAP يوفر إعادة صياغة لـ Path-Dependent SHAP تتميز بـ الاستقرار العددي، والكفاءة في التعامل مع الأجهزة، والوعي بالتفاعلات. من خلال الانتقال من الحساب الرمزي للمتعددات الحدود إلى التربيع ذو النقاط الثابتة، تحل الطريقة المقايضة بين الاعتماد على العمق والاستقرار العددي. إنها تتيح الحساب الفعال للتفاعلات عالية الرتبة على الأشجار العميقة، وهي مهمة كانت تعيقها سابقاً التعقيدات الأسية أو عدم الاستقرار في الطرق السابقة. ويضمن دمجها في XGBoost فائدة عملية فورية لمستخدمي المكتبة وحزمة shap بشكل عام.