🤖 machine learning

Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies

تقدم هذه الورقة طريقة عزو مرساة بالقيود لسياسات الأمثلة التوليفية العصبية، والتي تقوم بتفكيك القرارات عبر ثنائيات الاسترخاء الخطي (LP-relaxation duals)، وتصديق الحالات المضادة باستخدام نماذج الجدوى التوليفية، وتحديد حدود أحجام التفسير الكافية باختبارات PAC المصححة بطريقة بونفيروني، مما يظهر دقة أعلى بكثير من التدرجات التقريبية عبر مجالات متعددة من المشكلات.

المؤلفون الأصليون: Sohaib Lafifi

نُشر 2026-05-26

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

CC BY 4.0

المؤلفون الأصليون: Sohaib Lafifi

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

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

تقدم هذه الورقة البحثية طريقة جديدة لفتح هذا الصندوق الأسود، تسمى الإسناد المرتبط بالقيود (CAX). فكر في الأمر كأنه مترجم يحول رياضيات الروبوت المعقدة إلى قصة حول القواعد بدلاً من مجرد الأرقام.

إليك كيف تشرح هذه الورقة هذا النظام باستخدام ثلاث أدوات رئيسية:

1. مترجم "كتاب القواعد" (Λ-attribution)

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

في هذه المشكلات، تُقاد القرارات بواسطة عائلات من القواعد (مثل "لا تتجاوز وزن الشاحنة"، "لا تصل بعد الساعة 5 مساءً"، "لا تقطع مسافة طويلة جداً").

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

2. اختبار الواقع "ماذا لو" (Feasibility-Certified Counterfactuals)

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

مشكلة الطرق القديمة: قد تقترح، "لو كان وزن الطرد -50 كجم، لذهب الروبوت إلى مكان آخر". هذا مستحيل! لا يمكنك الحصول على وزن سالب. هذه "السيناريوهات الافتراضية" صحيحة رياضياً ولكنها غير منطقية فيزيائياً.
حل CAX: تستخدم الورقة "شهادة جدوى". قبل قبول أي تفسير، تجري اختباراً صارماً (مثل مفتش السلامة) للتأكد من أن سيناريو "ماذا لو" ممكن فعلياً في العالم الحقيقي.
التشبيه: تخيل أنك تسأل، "لماذا سلكت الجسر؟" يقول ذكاء اصطناعي قديم: "لأنك لو سلكت النفق، ستتحطم". أما ذكاء CAX فيقول: "لأنك لو سلكت النفق، ستتحطم وكذلك النفق مفتوح وصالح للقيادة فعلياً". إنه يستبعد السيناريوهات المستحيلة.

3. اختبار "الحد الأدنى من الأدلة" (Bonferroni-PAC Subsets)

أحياناً، نريد أن نعرف: "ما هو أقل قدر من المعلومات الذي احتاج إليه الروبوت لاتخاذ هذا القرار؟"

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

الاختبار الكبير: هل نجح الأمر؟

اختبر المؤلفون هذا على ثلاث مشكلات مختلفة:

مسارات التوصيل (CVRPTW): شاحنات مع نوافذ زمنية وحدود للوزن.
جمع الجوائز (OP): زيارة أكبر عدد ممكن من المواقع ذات القيمة العالية دون نفاذ الوقود.
جدولة المصانع (FJSP): تخصيص المهام لآلات مختلفة.

النتائج:

في مسارات التوصيل: كانت الطريقة القديمة (النظر إلى الأرقام الخام) صحيحة بنسبة 75% فقط. أما طريقة CAX الجديدة فكانت صحيحة بنسبة 97%. لقد نجحت في رصد قاعدة "النافذة الزمنية" التي فاتتها الطريقة القديمة.
في جمع الجوائز: كانت الطريقة القديمة صحيحة بنسبة 35% فقط. بينما قفزت CAX إلى 77%.
في جدولة المصانع: اتفقت الطريقتان تماماً (100%). وهذا أكد النظرية: عندما تتماشى البيانات والقواعد بشكل جيد، تعمل الطريقة القديمة، ولكن عندما تصبح الأمور فوضوية، تكون CAX هي الوحيدة التي تنجح في ذلك.

باخت-صار

تقدم هذه الورقة طريقة لتفسير قرارات الروبوتات المعقدة من خلال:

تجميع الأسباب حسب القواعد (وليس فقط الأرقام).
التأكد من أن قصص "ماذا لو" ممكنة فيزيائياً.
إيجاد أصغر مجموعة من الحقائق اللازمة لتبرير القرار.

إنها تحول مخرجات الرياضيات المربكة إلى قصة واضحة وموثوقة حول لماذا اتخذ الروبوت هذا القرار، مما يضمن أن التفسير يرتكز على القواعد الفعلية للعبة، وليس مجرد ضجيج إحصائي.

ملخص تقني: الإسناد المرتكز على القيود للسياسات العصبية في التحسين التوافقي (CO)

بيان المشكلة

تعد السياسات العصبية للمسائل التوافقية (Combinatorial Optimization - CO) فعالة بشكل متزايد في حل مسائل التوجيه والجدولة، ومع ذلك تظل عمليات اتخاذ القرار فيها غامضة. تفشل طرق الذكاء الاصطناعي القابل للتفسير (XAI) القياسية، مثل الإسناد المعتمد على التدرج (مثل Integrated Gradients أو DeepLIFT)، في مجال التحسين التوافقي لأنها تعمل على مستوى الميزات (features) بدلاً من مستوى القيود (constraints). تُعرَّف مسائل التحسين التوافقي عبر عائلات من القيود (مثل السعة، النوافذ الزمنية، الأسبقية)، والتي غالبًا ما تمتد عبر عدة تنسيقات ميزات (feature tensors) ذات رتب متفاوتة. ونتيجة لذلك، قد تتراكم كتلة تدرج مفرطة في تنسيقات الميزات عالية الرتبة حتى عندما لا تمثل القيد الحاكم الذي يقود القرار، مما يؤدي إلى إسنادات غير متوافقة.

تعتمد أدوات التفسير الموجودة الخاصة بالتحسين التوافقي غالبًا على حالات مضادة (counterfactuals) غير مقيدة تنتهك جدوى المسألة (مثل الطلب السالب أو النوافذ الزمنية المعكوسة) أو تستهدف نماذج بديلة ثابتة بدلاً من عملية فك التشفيد التلقائي (autoregressive decoding) للسياسات العصبية. هناك نقص في الطرق التي تفكك قرارات التحسين التوافقي العصبي حسب عائلات القيود مع توفير ضمانات رسمية للجدوى.

المنهجية: الإسناد المرتكز على القيود (CAX)

يقترح البحث إطار عمل CAX، والذي يتكون من ثلاثة عناصر أولية تربط التفسيرات العصبية بالبنية التحسينية الأساسية:

1. الإسناد من نوع $\Lambda$ ( $\Lambda$ -attribution)

تقوم هذه الطريقة بتفكيك تدرج قرار السياسة حسب عائلة القيود بدلاً من الميزات الفردية. بالنسبة لقرار $a_t$ عند الخطوة $t$ ، يتم حساب الإسناد لعائلة القيد $c_k$ كما يلي:
$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$
حيث يمثل $\lambda^*_k$ مضاعف لاغرانج (القيمة المزدوجة) من استرخاء البرمجة الخطية (LP) للمسألة، مجمعًا لكل عائلة. يضمن هذا القياس أن الإسناد يعكس "ضغط الربط" (binding pressure) للقيد. يدعم الإطار ثلاثة خلفيات (backends) لتقدير $\lambda^*$ :

البرمجة الخطية (LP): القيم المزدوجة من استرخاء البرمجة الخطية.
التدرج الجزئي (Subgrad): صعود التدرج الجزئي للاغرانج على مسألة فرعية مسترخية.
الوكيل (Proxy): وزن موحد ( $\lambda_k=1$ )، وهو ما يعادل (التدرج المقسم حسب القيد $\times$ الميزة).

2. المجموعة الفرعية الكافية بنظام بونفيروني-PAC

لتحديد أصغر مجموعة فرعية من العقد المطلوبة للحفاظ على قرار الـ argmax للسياسة، تكيف الطريقة نهج Koriche et al. لمحللات (decoders) التحسين التوافقي. تسعى الطريقة لإيجال أصغر مجموعة فرعية $S$ بحيث يكون احتمال احتفاظ السياسة بقرارها تحت اضطرابات غاوسية هو $1-\epsilon$ على الأقل.

تستخدم خوارزمية جشعة (greedy algorithm) لتتبع ترتيب الإسناد لإيجاد أصغر $k$ حيث يتجاوز معدل الحفاظ التجريبي قيمة $1-\epsilon$ .
للتحكم في معدل الخطأ لكل عائلة عبر الاستعلامات التكيفية (حتى $k_{max}$ )، يتم تطبيق تصحيح بونفيروني (Bonferroni correction) على حد هوفدينغ (Hoeffding bound). ينتج عن ذلك حجم عينة $M_{bonf}$ يضمن حدًا $(1-\delta)$ -PAC على طول الترتيب الجشع.

3. الحالات المضادة الموثقة ببرمجة القيود (CSP-Certified Counterfactuals - CF)

على عكس حالات "واختر" (Wachter-style) المضادة التي تقلل معايير الاضطراب دون ضمانات للجدوى، يفرض CAX شهادة جدوى توافقية.

العملية: يقوم جامع عينات بتوليد اضطرابات لقلب قرار الـ argmax. تخضع المرشحات أولاً لفحوصات حسابية (مثل حدود المجال).
التوثيق: يتم التحقق من أفضل مرشح مقابل نموذج قرار-جدوى لبرمجة القيود (CP) (يتم تنفيذه عبر CP-SAT).
إشارة التحكيم: العائلة التي تحمل أكبر كتلة $L_1$ في اضطراب القلب الموثق بـ CSP تعمل كإشارة للحساسية المحلية للسياسة. هذه الإشارة ثابتة بالنسبة لمعايير الاضطراب ( $L_1, L_2, L_\infty$ ) وتطبيع الأبعاد.

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

التفكيك على مستوى القيد: يعد CAX أول طريقة تفكك قرارات سياسة التحسين التوافي العصبي حسب عائلات القيود باستخدام مضاعفات استرخاء LP، مما يصحح مشكلات سوء الترتيب المتأصلة في الإسناد على مستوى الميزات.
الحالات المضادة الموثقة بالجدوى: يقدم عملية توليد حالات مضادة تلتزم بصرامة بقيود المسألة عبر نماذج قرار-جدوى لبرمجة القيود (CSP)، مما يميزه عن طرق XAI غير المقيدة.
المجموعات الفرعية الكافية بنظام PAC: يوفر حدًا محكومًا بتصحيح بونفيروني وحد هوفدينغ لحجم المجموعات الفرعية الكافية للسياسات التوافقية العصبية.
التحكيم التجريبي: يستخدم الإطار الإشارة المستمدة من CF للتحقق من صحة خلفيات الإسناد، مما يثبت أن مضاعفات LP تستعيد دقة الإسناد عندما تكون رتب الميزات وعائلات القيود الحاكمة غير متوافقة.

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

تم تقييم الإطار على ثلاث مسائل توافقية متميزة: مسألة توجيه المركبات ذات السعة مع النوافذ الزمنية (CVRPTW)، مسألة التوجيه (OP)، ومسألة جدولة ورشة العمل المرنة (FJSP).

الاتفاق مع إشارة CF:
- CVRPTW: طابق الإسناد $\Lambda$ المرتكز على LP إشارة CF في 96.5% من الحالات ( $n_{cert}=344$ )، متفوقًا بشكل كبير على الوكيل (Proxy) (75.0%). كان الفرق (+0.215) ذا دلالة إحصائية (McNemar $p \le 10^{-14}$ ).
- OP: حقق الإسناد المرتكز على LP اتفاقًا بنسبة 77.2% ( $n_{cert}=281$ ) مقابل 35.2% للوكيل (فرق +0.420، $p \le 10^{-14}$ ).
- FJSP: في هذا النظام "المتراصف الرتب" حيث تتطابق التنسيقات عالية الكتلة مع العائلات الحاكمة، حقق كل من LP والوكيد اتفاقًا بنسبة 100% في جميع حالات القلب الموثقة الـ 59، مما يؤكد التنبؤ النظري بأن مضاعفات LP لا تضيف معلومات إضافية عندما تتراصف الرتب.
معدلات الجدوى: حافظت الحالات المضادة الموثقة بـ CSP على جدوى عالية. اجتازت الفلترة الحسابية وحدها 100% من الفائزين، بينما اجتاز خط الأساس غير المقيد 19.3% فقط من المرشحات.
مجموعات PAC: بلغ متوسط المجموعات الفرعية لـ PAC المصححة ببونفيروني في CVRPTW حوالي 5.0 عقدة لكل خطوة ( $M=70, \epsilon=\delta=0.2$ ).

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

يزعم البحث أن CAX يوفر نهجًا صارمًا ومستندًا إلى القيود لتفسير سياسات التحسين التوافقي العصبية. تكمن أهميته الأساسية في إثبات أن مضاعفات LP ضرورية للإسناد الدقيق فقط عندما تكون رتب تنسيقات الميزات غير متوافقة مع عائلة القيد الحاكمة. عندما تتوافق الرتب، تكفي الطرق الأبسط؛ وعندما لا تتوافق، تفشل طرق مستوى الميزات، وتستعيد الطرق المرتكزة على LP الإشارة الصحيحة على مستوى القيد.

الإطار متواضع في نطاقه: فهو يتطلب فقط نموذج جدوى (تم تنفيذه هنا كـ CSP) ويعمل كأداة تحليل لاحقة (post-hoc). هو لا يدعي حل تحسين شبكة المجموعات الفرعية الكاملة (لا تزال المجموعات المثلى لـ PAC مسألة مفتوحة)، ولكنه يوفر حدًا محافظًا وموثقًا عبر الترتيب الجشع. يضع هذا العمل معيارًا جديدًا لتقييم XAI في التحسين التوافقي باستخدام الحالات المضادة الموثقة بـ CSP كإشارة تحكيم، متجاوزًا أهمية الميزات الاستدلالية نحو الصلاحية القائمة على القيود.