ملخص تقني: QuadraSHAP

بيان المشكلة

تُعد قيم شابلي (Shapley values) أداة أساسية لتفسير تنبؤات تعلم الآلة، حيث تقدم إسنادات للميزات (feature attributions) قائمة على نظرية الألعاب التعاونية. ومع ذلك، فإن الحساب الدقيق لهذه القيم غير قابل للحل عمليًا بشكل عام، مما يتطلب تقييم عدد هائل من تحالفات الميزات ($2^{d-1}$). وبينما تستغل الطرق الخاصة بنماذج معينة (مثل TreeSHAP وRKHS-SHAP) الخصائص الهيكلية لتحقيق وقت حسابي حدودي (polynomial time)، إلا أنها غالبًا ما تواجه مقايضة مستمرة بين الاستقرار العددي والكفاءة الحسابية.

على وجه التحديد، تعاني الطرق التي تعتمد على الاستيفاء متعدد الحدود (مثل Linear TreeSHAP) من عدم استقرار عددي سريع مع زيادة درجة متعدد الحدود (التي يحكمها عمق الشجرة أو عدد الميزات) بسبب سوء حالة معكوسات "فاندرموند" (Vandermonde inverses). وفي المقابل، توفر طرق التكرار الجبري (مثل تلك المستخدمة لنماذج النواة الضربيه/product-kernel) استقرارًا، لكنها تتكبد تكاليف حسابية أعلى بكثير. تعالج هذه الورقة الحاجة إلى طريقة تكون في آن واحد دقيقة (أو شبه دقيقة)، ومستقرة عددياً، وفعالة حسابياً لمجموعة واسعة من النماذج التي تظهر بنية ضربية (multiplicative structure).

المنهجية

تقدم الورقة QuadraSHAP، وهي طريقة لحساب قيم شابلي لـ الألعاب الضربية (product games)—وهي ألعاب تعاونية يكون فيها قيمة التحالف عبارة عن حاصل ضرب حدود لكل لاعب ($v(S) = \prod_{j \in S} u_j$). هذه البنية تظهر بشكل طبيعي في النماذج القائمة على الأشجار وطرق النواة ذات النواة الضربية.

1. التمثيل التكاملي

المساهمة النظرية الجوهرية هي إعادة صياغة قيمة شابلي للعبة ضربية من مجموع مرجح عبر $2^{d-1}$ من المجموعات الفرعية إلى تكامل أحادي البعد دقيق. من خلال استخدام تمثيل دالة "بيتا" (Beta-function) لأوزان شابلي، استنتج المؤلفون ما يلي:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
هذا التحويل يلغي الحاجة إلى تعداد المجموعات الفرعية أو استعادة المعاملات القائمة على الاستيفاء.

2. تربيع غاوس-ليجندر (Gauss–Legendre Quadrature)

يتم تقييم التكامل باستخدام تربيع غاوس-ليجندر.

• الدقة: إذا كان عدد عقد التربيع $m_q$ يحقق $m_q \ge \lceil d/2 \rceil$، فإن الطريقة تستعيد قيمة شابلي الدقيقة.
• التقريب: إذا كان $m_q < \lceil d/2 \rceil$، فإن الطريقة توفر تقريبًا شبه دقيق. وقد ثبت أن الخطأ يتناقص هندسياً بالنسبة لـ $m_q$، وتحديداً بحدود $O(\rho^{-2m_q})$ لمعلمة ناقص برنوي (Bernstein ellipse) حيث $\rho > 1$. تجريبياً، يكفي بضع مئات من العقد للحصول على تقديرات عالية الدقة حتى مع آلاف الميزات، وهو أقل بكثير من عتبة الدقة النظرية.

3. تنفيذ مستقر عددياً وفعال

لمعالجة التحديات الحسابية العملية، يقترح المؤلفون تحسينات خوارزمية محددة:

• التقييم في الفضاء اللوغاريتمي: لمنع تجاوز السعة (overflow) أو نقصها (underflow) في الأبعاد العالية، يتم تقييم الحواصل في الفضاء اللوغاريتمي مع تتبع صريح للإشارة. يتم حساب المقدر كالتالي:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  حيث $P_q$ هو حاصل الضرب الكامل للحدود و $T_{q,i}$ هو الحد الخاص بالميزة $i$.
• الحساب المشترك: بدلاً من إعادة حساب حاصل الضرب "المتروك خارج المجموعة" (leave-one-out) لكل ميزة، يتم حساب حاصل الضرب الكامل مرة واحدة، ثم يتم قسمة العامل المحدد للميزة $i$. هذا يقلل التعقيد من $O(d^2 m_q)$ إلى $O(d m_q)$.
• التوازي: تستخدم عملية الحساب عمليات المسح الترابطي (associative scan primitives) (مثل الجمع التراكمي المسبق) لحساب الاختزال في الفضاء اللوغاريتمي في زمن قدره $O(\log d)$ بالتوازي.

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

1. صياغة التكامل الدقيق: تثبت الورقة أن قيم شابلي للألعاب الضربية تقبل تمثيلاً تكاملياً دقيقاً، مما يسمح باستخدام تربيع غاوس-ليجندر.
2. الاستقرار والكفاءة: تحل QuadraSHAP المقايضة بين الاستقرار والكفاءة. فهي تتجنب عدم الاستقرار العددي للطرق القائمة على الاستيفاء (مثل Linear TreeSHAP) بينما تكون أسرع بكثير من طرق التكرار الجبري لنماذج النواة الضربيه.
3. الضمانات النظرية: توفر الطريقة ضمانات دقة مثبتة عندما يكون $m_q \ge \lceil d/2 \rceil$ وحدود تقارب هندسي في حالات التقريب.
4. خوارزميات قابلة للتوسع: يستنتج المؤلفون خوارزميات بجهد تسلسلي قدره $O(d m_q)$ وزمن موازٍ قدره $O(\log d)$، مما يجعل الطريقة قابلة للتوسع للمشكلات ذات الأبعاد العالية (آلاف الميزات).

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

يقيم المؤلفون QuadraSHApp مقابل أفضل الطرق المرجعية (Baselines) مثل (TreeSHAP، Linear TreeSHAP، FastTreeSHAP، shapiq، وPKeX-Shapley) على مجموعات بيانات اصطناعية وواقعية.

• مجموعات الأشجار (Tree Ensembles):
  • السرعة: تعد QuadraSHAP أسرع طريقة مستقرة عددياً عبر جميع الإعدادات المختبرة. في المجموعات الكبيرة ($10^5$ ورقة)، تتفوق على TreeSHA بمعدل 3-5 أضعاف، وعلى FastTreeSHAP بمعدل 2-2.7 ضعف.
  • الاستقرار: في سيناريوهات الأشجار العميقة (عمق يصل إلى 100)، تظهر المنافسة مثل Linear TreeSHAP وTreeSHAP انتهاكات كارثية لمبدأ كفاءة شابلي (تصل الأخطاء إلى $10^{186}$ أو أعلى). تحافظ QuadraSHAP على الدقة عند مستوى حدود الفاصلة العائمة ($\sim 10^{-13}$).
• طرق النواة الضربيه (Product-Kernel Methods):
  • القابلية للتوسع: بالنسبة لانحدار ريجرسون النواة (Kernel Ridge Regression) مع النواوات الضربيه، تعد QuadraSHAP أسرع بمراحل من المرجع الدقيق الحالي (PKeX-Shapley).
  • الأبعاد العالية: بينما تنتهي مدة تنفيذ PKeX-Shapley (بحد أقصى 300 ثانية) عندما يكون بعد الميزات $d \ge 2000$، تنجز QuadraSHAP التفسيرات في ثوانٍ (مثلاً 7.6 ثانية لـ $d=5000$).
• جودة التقريب: تؤكد التجارب أن خطأ التقريب يتناقص هندسياً مع عدد العقد $m_q$. بالنسبة لـ $d=5000$، استخدام 400 عقدة فقط (أقل بكثير من عتبة الدقة $2500$) يعطي دقة تقترب من دقة الآلة.

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

تدعي الورقة أن QuadraSHAP توفر إطاراً موحداً وقوياً لتفسير النماذج ذات البنى الضربيه. ومن خلال الاستفيد من التمثيل التكاملي وتربيع غاوس-ليجندر، تحقق:

• المتانة العددية: تظل مستقرة في بيئات الأشجار العميقة والأبعاد العالية حيث تفشل الطرق القائمة على الاستيفاء.
• التفوق الحسابي: تضاهي أو تتجاوز سرعة أسرع الطرق الموجودة مع الحفاظ على الدقة أو التقريب المنضبط.
• الشمولية: توحد مجموعات الأشجار وطرق النواة الضربيه تحت نموذج حسابي واحد.

يضع المؤلفون QuadraSHAP كأسرع طريقة مستقرة عددياً لهذه الفئات المحددة من النماذج، مما يوفر حلاً عملياً للقابلية للتفسير في أنظمة تعلم الآلة المعقدة وعالية الأبعاد.