🤖 machine learning

Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks

تقدم هذه الورقة خوارزمية مبتكرة تستفيد من تقنيات التحقق من الشبكات العصبية لحساب حدود دقيقة ومثبتة وقابلة للضبط بشكل تعسفي لقيم شابلي (Shapley) الدقيقة، مما يتيح حساب قيم SHAP بدقة وقابلية للتوسع للشبكات العصبية ذات مساحات البحث الأكبر بكثير من الطرق الدقيقة الحالية.

المؤلفون الأصليون: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

نُشر 2026-05-26

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أن لديك آلة معقدة للغاية، "صندوق أسود" (شبكة عصبية)، تتخذ قرارات، مثل تشخيص مرض ما أو الموافقة على قرض. أنت تريد أن تعرف بالضبط أي الميزات المدخلة (مثل العمر، أو الدخل، أو ضغط الدم) تسببت في اتخاذ هذه الآلة لقرار معين.

الطريقة القياسية للإجابة على هذا هي ما يسمى SHAP. فكر في SHAP كأنها لعبة تحاول من خلالها معرفة مقدار مساهمة كل لاعب (ميزة) في النتيجة النهائية للفريق. وللحصول على الإجابة الدقيقة تماماً، ستحتاج نظرياً إلى اختبار كل تركيبة ممكنة من اللاعبين.

المشكلة:
بالنسبة لآلة بسيطة، فإن اختبار كل التركيبات أمر سهل. ولكن بالنسبة لشبكة عصبية معقدة تحتوي على مئات الميزات، فإن عدد التركيبات ضخم جداً لدرجة أنه يشبه محاولة عد كل حبة رمل على كل شواطئ الأرض. يستغرق الأمر وقتاً طويلاً لدرجة أنه مستحيل عملياً. وبسبب ذلك، تعتمد معظم الأدوات اليوم على التخمين للوصول إلى الإجابة باستخدام طرق مختصرة. هذه التخمينات عادة ما تكون سريعة، لكنها قد تكون خاطئة، وليس لدينا طريقة لمعرفة مدى خطئها لأننا لا نستطيع حساب الإجابة "الحقيقية" للمقارنة بها.

الحل: SHAP الموثق (VERISHAP)
قام مؤلفو هذه الورقة البحثية ببناء أداة جديدة تسمى VERISHAP. هم لم يحاولوا عد كل حبة رمل، بل استخدموا حيلة ذكية مستعارة من مجال يسمى "التحقق من الشبكات العصبية" (والذي يُستخدم عادةً لإثبات أن أنظمة الذكاء الاصطناعي آمنة ومحمية).

إليك كيف تعمل VERISHAP، باستخدام تشبيه بسيط:

تشبيه "البحث في الغرفة"

تخيل أنك تبحث عن كنز محدد مخبأ في مستودع ضخم مليء بالملايين من الصناديق (مساحة البحث).

الطرق القديمة (التخمين): ترمي سهماً على الخريطة وتقول: "الكنز غالباً في هذه المنطقة العامة". إنها سريعة، لكنك قد تكون مخطئاً بمسافة ميل كامل.
الطرق الدقيقة القديمة (العد): تحاول فتح كل صندوق واحداً تلو الآخر. هذا يضمن لك العثور على الكنز، لكنك ستموت من الشيخوخة قبل أن تنتهي.
VERISHAP (البحث الذكي):
1. فرق تسد: بدلاً من فتح الصناديق واحداً تلو الآخر، تقوم بتقسيم المستودع إلى غرف كبيرة.
2. حيلة "السياج": تستخدم سياجاً رياضياً خاصاً (يسمى انتشار الحدود - bound propagation) لفحص غرفة كاملة دفعة واحدة. هذا السياج يخبرك: "الكنز الموجود في هذه الغرفة يتراوح بالتأكيد بين 10 و20 دولاراً".
3. التقريب (الزووم): إذا كان النطاق (من 10 إلى 20 دولاراً) واسعاً جداً، فإنك تقسم تلك الغرفة إلى غرف أصغر وتفحصها مرة أخرى. يصبح السياج أكثر إحكاماً: "الآن نعلم أنه بين 14 و16 دولاراً".
4. النتيجة: تستمر في تقسيم الغرف حتى يصبح السياج ضيقاً جداً بحيث يصبح النطاق فعلياً صفراً. لقد وجدت موقع الكنز بالضبط.

لماذا يعد هذا أمراً مهماً؟

تدعي الورقة تحقيق ثلاث انتصارات رئيسية:

إنها تتوسع (Scale Up): الطرق السابقة التي حاولت إيجاد الإجابة الدقيقة كانت تتعطل أو تنفد ذاكرتها إذا أصبح المشكل كبيراً جداً. تستطيع VERISHAP التعامل مع مساحات بحث أكبر بعدة مراتب عشرية (فكر في المليارات أو التريليونات من المرات) مما كان ممكناً في السابق.
تعطيك إجابات "جيدة بما يكفي" بسرعة: ليس عليك دائماً الانتظار حتى ينتهي البحث بنسبة 100%. إذا أصبح "السياج" ضيقاً بما يكفي (على سبيل المثال: "الإجابة بين 14.9 و15.1")، يمكنك التوقف مبكراً والقول: "نحن متأكدون بنسبة 99.9% أن الإجابة هي 15". هذا يمنحك رؤى موثوقة بشكل أسرع بكثير من الانتظار للحصول على الإجابة المثالية.
تخلق "معياراً ذهبياً" للاختبار: نظرًا لأن VERISHAP يمكنها حساب الإجابة الحقيقية للمشاكل الأكبر، فإنها تعمل كـ "آلة الحقيقة". يمكن للباحثين الآن استخدامها لاختبار أدوات التخمين تلك (مثل KERNELSHAP) لمعرفة مدى دقتها حقاً على الشبكات العصبية المعقدة والواقعية. قبل ذلك، لم يكن بإمكاننا اختبار أدوات التخمين إلا على أمثلة صغيرة وبسيطة لا تعكس الواقع.

ما تقوله الورقة فعلياً (وما لا تقوله)

هي تقول: لقد نجحوا في حساب قيم SHAP الدقيقة والحدود الضيقة للشبكات العصبية على البيانات الجدولية (مثل الجداول البيانات) وبيانات الصور (مثل أرقام MNIST). كما أظهروا أنها تعمل على أنواع مختلفة من بنيات الشبكات (مثل ResNets) ووظائف تنشيط مختلفة (مثل ReLU و Tanh).
هي تقول: هي حالياً أبطأ من طرق "التخمين"، لكنها الطريقة الوحيدة للحصول على إجابة دقيقة ومثبتة رياضياً للشبكات الكبيرة.
هي لا تقول: الورقة لا تدعي أن هذه الأداة جاهزة للاستخدام السريري الفوري في المستشفيات أو أنها تحل جميع مشكلات التحيز في الذكاء الاصطناعي. هي تركز حصرياً على القدرة الرياضية لحساب هذه القيم والتحقق منها. وهي تقر بأنه بينما يعد هذا خطوة هائلة للأمام، إلا أن الرياضيات الأساسية لا تزال صعبة للغاية، وبالنسبة لبعض الشبكات المحددة والمعقدة جداً، قد تستغرق وقتاً طويلاً أيضاً.

باختتام الكلام:
VERISHAP تشبه الترقية من بوصلة تشير "تقريباً نحو الشمال" إلى نظام GPS يمكنه تحديد موقعك بدقة، حتى في غابة شاسعة وغير مرسومة على الخريطة. إنها تثبت أننا يمكننا الحصول على الحقيقة المطلقة للقرارات المعقدة للذكاء الاصطناعي، وهي تمنحنا مسطرة لقياس مدى جودة أدواتنا الأخرى الأسرع.

ملخص تقني: SHAP الموثق (VERISHAP)

بيان المشكلة

تُعد قيم شابلي الإضافية (SHAP) طريقة قياسية للتفسير البعدي (post-hoc) لنسب تنبؤات نماذج تعلم الآلة إلى الميزات المدخلة. ومع ذلك، يُعتبر حساب قيم SHAP الدقيقة للشبكات العصبية عملية غير قابلة للحل حسابياً بشكل واسع بسبب فضاء البحث الأسي عبر مجموعات الميزات ( $2^n$ ). وبينما يكون الحساب الدقيق ممكناً للنماذج القائمة على الأشجار والنماذج الجمعية، فإنه يُصنف ضمن المسائل من فئة #P-hard بالنسبة للشبكات العصبية العامة. وبناءً على ذلك، تعتمد الأدبيات على المقدرات الإحصائية (مثل KERNELSHAP وFASTSHAP وLEVERAGESHAP). وتواجه هذه المقدرات قصوراً جوهرياً يتمثل في:

عدم الدقة: فهي تقدم تقريبات قد تكون غير موثوقة في النماذج عالية غير الخطية أو السيناريوهات التي تتسم بتفاعلات قوية بين الميزات.
غياب الحقيقة الأرضية (Ground Truth): نظراً لأن حساب قيم SHAP الدقيقة مكلف للغاية للشبكات العصبية، فإن المقدرات تُقيّم عادةً على نماذج صغيرة جداً (toy-sized) حيث يكون الحساب الدقيق ممكناً. وغالباً ما تفشل هذه الإعدادات في التعميم على الشبكات العصبية الواقعية عالية الأبعاد.

المنهجية: SHAP الموثق (VERISHAP)

تقدم الورقة البحثية VERISHAP، وهي أول خوارزمية تستفيد من التطورات الأخيرة في التحقق من الشبكات العصبية (neural network verification) لحساب قيم SHAP الدقيقة والحدود المثبتة للشبكات العصبية. وتعمل هذه الطريقة على تكييف تقنيات التحقق القائمة على "التفريع والتقييد" (branch-and-bound) مع الطبيعة المنفصلة، والاحتمالية، والكثيفة في عمليات الجمع الخاصة بـ SHAP.

الخوارزمية الأساسية

تستخدم VERISHAP استراتيجية "التفريع والتقييد" التدريجية لتقسيم فضاء الميزات (مجموعة كل التحالفات $S_i$ للميزة $i$ ) بشكل متكرر.

التقسيم: تُعرف الخوارزمية الفروع $B$ بناءً على مجموعات الميزات المضمنة ( $I$ ) والمستبعدة ( $E$ ). يمثل كل فرع مجموعة فرعية من التحالفات حيث تكون الميزات في $I$ موجودة والميزات في $E$ غائبة.
التقييد عبر الانتشار: لكل فرع، تقوم الخوارزمية بحساب الحدود الدنيا والعليا للمساهمة الهامشية $\Delta_i(S) = v(S \cup \{i\}) - v(S)$ $Δ_{i} (S) = v (S \cup {i}) - v (S)$ .
- لتطبيق انتشار الحدود المستمر (مثل CROWN وIBP) على المجموعات المنفصلة، تقوم الخوارزمية بتبسيط أقنعة الميزات البوليانية $m \in \{0, 1\}^n$ إلى المجال المستمر $[0, 1]^n$ .
- تستخدم انتشار الحدود الخطي (LBP) (تحديداً CROWN-IBP) لاستخلاص حدود ضيقة على دالة القيمة $v(S)$ عبر المجال المبسط.
التجميع: يتم حساب حدود قيم SHAP الإجمالية عن طريق جمع الحدود الموزونة لجميع الفروع:
$\phi_i^{(t)} = \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B \leq \phi_i \leq \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B = \bar{\phi}_i^{(t)}$
حيث $\Lambda_B$ هو المجموع ذو الصيغة المغلقة لأوزان شابلي للتحالفات في الفرع $B$ ، والمستمد تركيبياً.
التحسين: تختار الخوارزمية فروعاً لتقسيمها بشكل متكرر (باستخدام استراتيجيات مثل MAXDIAM) وميزات للتقسيم عليها (باستخدام استراتيجيات مثل SMEARS)، مما يؤدي إلى تحسين الحدود حتى تتقارب مع القيمة الدقيقة أو مستوى الدقة المطلوب.

الخصائص النظرية الرئيسية

الإنهاء: تضمن الخوارما لإنهاء العمل بعد عدد محدد من التكرارات (على الأكثر $2^{n-1}$ )، حيث يعزل التقسيم في النهاية التحالفات الفردية.
الإنهاء المبكر للنماذج الخطية: بالنسبة للنماذج الخطية، تنتهي الخوارزمية في التكرار الأول لأن المساهمة الهامشية ثابتة، ولا يسبب LBP أي خطأ تقريبي في التركيبات الخطية.
esta الخطية الجزئية (Piecewise-Linearity): بالنسبة للشبكات ذات تنشيط ReLU، يمكن للخوارزمية الإنهاء مبكراً إذا كان التقسيم يقيد البحث في المناطق التي تسلك فيها الشبكة سلوكاً خطياً.

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

أول SHAP دقيق للشبكات العصبية: تعد VERISHAP أول خوارزمية تحسب قيم SHAP الدقيقة للشبكات العصبية العامة، وتتوسع لتشمل فضاءات بحث أكبر بعدة مراتب من الطرق الدقيقة السابقة.
حدود مثبتة: توفر الطريقة حدوداً دنيا وعليا ضيقة للغاية على قيم SHAP، مما يتيح رؤى تفسيرية موثوقة حتى قبل الوصول إلى التقارب الكامل.
خط أساس للحقيقة الأرضية: تؤسس إطاراً منهجياً لتقييم مقدرات SHAK الإحصائية على فضاءات بحث أكبر وأكثر واقعية حيث كان الوصول إلى الحقيقة الأرضية مستحيلاً سابقاً.
الكفاءة عبر التحقق: من خلال استغلال تفكيك الشبكات العصبية إلى مناطق شبه خطية، تتجنب الخوارزمية تعداد جميع التحالفات $2^n$ في كثير من الحالات العملية.

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

قيم المؤلفون أداء VERISHAP على مجموعات بيانات الجداول (UCI datasets) والرؤية (MNIST, FashionMNIST, CIFEST10, GTSRB).

القابلية للتوسع مقابل EXACTSHAP: تتفوق VERISHAP بشكل كبير على أحدث طريقة دقيقة (EXACTSHAP). فبينما تستهلك EXACTSHAP ذاكرة وحدة معالجة الرسومات (GPU) بالكامل لفضاءات البحث الأكبر من $2^{20}$ ، تقوم VERISHAP بحساب القيم الدقيقة لحالات تصل إلى $2^{25}$ ( $\approx 3 \times 10^7$ تحالفاً) وتوفر حدوداً ضيقة لفضاءات تصل إلى $2^{60}$ ( $\approx 10^{18}$ تحالفاً).
المقارنة بالمقدرات: عند مقارنتها بالمقدرات الإحصائية (KERNELSHAP, TREEMSR, LEVERAGESHAP)، تُظهر VERISHAP أن المقدرات غالباً ما تفشل في تحقيق نفس الدقة ضمن قيود الذاكرة. علاوة على ذلك، تكشف VERISHAP أن أداء المقدرات يختلف بشكل كبير عبر مجموعات البيانات (على سبيل المثال، يُظهر TREEMSR أداءً متقلباً على الشبكات العصبية مقارنة بالنماذج القائمة على الأشجار).
تنوع البنية: نجحت الخوارزمية في حساب قيم SHAP الدقيقة لمختلف البنى، بما في ذلك الشبكات كاملة الاتصال (fully connected) مع تنشيطات ReLU وtanh وSwish، بالإضافة إلى شبكات ResNet.
التقارب: في التجارب (مثل MNIST)، تصبح الحدود معلوماتية (تكشف عن أنماط الإسناد) قبل وقت طويل من حساب القيمة الدقيقة، غالباً في غضض ثوانٍ، بينما قد يستغرق الحساب الدقيق عشرات الثواني.

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

تضع الورقة البحثية VERISHAP كـ خطوة أولى نحو توسيع نطاق حساب SHAP الدقيق للشبكات العصبية. وتكمن أهميتها في ثلاثة مجالات:

القابلية للتوسع: إنها تسد الفجوة بين عدم القدرة الحسابية النظرية لـ SHAP الدقيق والتطبيق العملي من خلال الاستفادة من التحقق من الشبكات العصبية.
الموثوقية: توفر طريقة للحصول على تفسيرات "الحقيقة الأرضية" مع ضمانات مثبتة، مما يعالج عدم اليقين المتأصل في التقريبات الإحصائية.
إطار التقييم: توفر معياراً صارماً لتقييم وتحسين مقدرات SHAP على فضاءات بحث أكبر، متجاوزة بذلك النماذج التجريبية الصغيرة.

يقر المؤلفون بأن حساب SHAP الدقيق لا يزال من فئة #P-hard وأن VERISHAP قد تظل بطيئة لبعض الشبكات المعقدة. ومع ذلك، يجادلون بأن القدرة على حساب الحدود المثبتة وإمكانية التحسين المستمر للتحقق من الشبكات العصبية تجعل منها تقدماً تأسيسياً في مجال قابلية التفسير للذكاء الاصطناğu الموثوق.