Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

ملخص تقني: الاكتشاف السببي التكراري مع شهادات الاستحالة لكل حافة

بيان المشكلة
عادةً ما تُرجع خوارزميات الاكتشاف السببي الحالية رسماً بيانياً موجهاً غير حلقي (DAG) موجهًا بالكامل، لكنها تفشل في التمييز بين اتجاهات الحواف التي حددها البيانات وتلك التي فرضتها الخوارزمية للوفاء بقيود المخرجات. في ظل شروط ماركوف والوفاء القياسية، تحدد البيانات الملاحظة فقط فئة التكافؤ لـ ماركوف؛ أما اتجاهات الحواف التي لا تقع ضمن هياكل v-structures فهي غير محددة بواسطة التوزيع المشترك. تفرض الطرق الحالية اتجاهات على الحواف غير القابلة للتحديد (مثل NOTEARS وDAGMA) دون مبرر تشخيصي، أو تتركها غير موجهة (مثل FCI) دون تحديد المعلومات المسبقة المحددة المطلوبة لحلها. كما ثبت أن طرق التحسين المستمر تستغل الآثار الاصطناعية للبيانات (مثل قابلية فرز المتغيرات - varsortability) التي تحاكي التحديد الحقيقي. هناك نقص في وجود بروتوكول مبدئي يوفر إمكانية التدقيق لكل حافة، ويفصل صراحةً بين القابلية للتحديد المستمدة من البيانات وبين الإملاء الخوارزمي، ويحدد الأسئلة النوعية المطلوبة من الخبراء لحل الحواف غير القابلة للتحديد.

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

1. المرحلة الأولى: البحث عن الهيكل والوسيط:

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

2. المرحلة الثانية: تسلسل القابلية للتحديد المبوّب:

   • يقيم تسلسل من ثمانية مستويات الحواف المتبقية. تتضمن المستويات طرقاً كلاسيكية (ANM الخطي $L_0$، وANM غير الخطي $L_1$، وHOC LiNGAM $L_2$) وخمسة مستويات جديدة قدمها هذا العمل: LSNM (ضجيج الموقع-المقياس)، IGCI (الهندسة المعلوماتية)، Stein (مطابقة الدرجة)، MDL (شرط ماركوف الخوارزمي)، وPEIT (اختبار عكس الإنتروبيا).
   • آلية البوابات (Gating Mechanism): يتم تهيئة كل مستوى مسبقاً باختبارات إحصائية (مثل اختبار Shapiro–Wilk لعدم التوزيع الطبيعي، واختبارات التباين غير المتجانس)؛ وإذا فشل الشرط المسبق للمستوى، فإنه يمتنع عن التحديد بدلاً من فرض اتجاه ما.
   • إجماع عبر المستويات (Cross-Tier Consensus): يقوم "حارس عدم الاتفاق" بخفض تصنيف التزامات $L_0$ إذا تعارضت مع المستويات ذات الدقة الأعلى (IGCI، Stein، MDL)، حيث يعيد تسمية الحافة بـ impossible_l0_disagrees_with_high_tier.
   • الحواف التي لا يتم حلها بواسطة أي مستوى تتلقى تسمية impossible_* ، والتي تشفر نمط الفشل المحدد (مثل وجود متغير مربك كامن، أو ضعف اللاخطية) والسؤال المقابل الذي يجب توجيهه للخبير المختص.

3. المرحلة الثالثة: استعلامات الأوراكل المستهدفة:

   • يتفاعل البروتوكول مع الخبير المختص فقط على الحواف المصنفة كـ impossible_*.
   • نماذج الاستعلام (Query Primitives):
     • استعلام لكل حافة: يطلب الاتجاه (للأمام/للخلف) أو الغياب.
     • استعلام المركز-الميتا (Meta-hub query): يطلب أعلى $K$ من العقد حسب درجة الخروج.
     • استعلام أبناء العقدة: يطلب الأبناء المباشرين لعقدة معينة، مما يؤدي لتثبيت جميع الحواف الخارجة منها في آن واحد.
   • الانتشار التلقائي (Auto-Propagation): بعد كل التزام من الأوراكل، يقوم النظام بتشغيل عمليات حل تلقائي صفرية التكلفة (فحوصات عدم الحلقية، قواعد Meek، وفصل d-separation الانتقالي) لحل الحواف الإضافية دون مزيد من الاستعلامات.

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

1. شهادات لكل حافة: يخصص البروتوكول رمزاً منفصلاً لكل حافة. رموز resolved_* تشير إلى النظرية المحددة (مثل $L_{Stein}$) التي تبرر الاتجاه، بينما تسجل رموز impossible_* نمط الفشل والسؤال المطلوب لحله.
2. الامتناع الواعي بالمستويات: يضمن تقديم المستويات الجديدة المبوّبة (LSNM, IGCI, Stein, MDL, PEIT) أن الاتجاهات لا يتم الالتزام بها إلا عندما يتحقق شرط نظرية محددة. إذا فشل الشرط المسبق، يمتنع النظام بدلاً من فرض اتجاه قد يكون زائداً.
3. حد التفاعل $1+K$: يضع البحث حداً معلوماتياً نظرياً للتفاعل مع الخبير يبلغ $1+K$ لاستعادة أي DAG حقيقي، حيث $K$ هو عدد العقد غير الورقية. ويتحقق ذلك من خلال الجمع بين استعلام مركز-ميتا واحد (لتحديد الأهداف) و $K$ من استعلامات أبناء العقد.
4. الاستخلاص المستهدف: على عكس طرق التعلم النشط التي قد تطلب ترتيبات طوبولوجية كاملة أو تدخلات واسعة، يعزل هذا البروتوكول فقط الحواف غير القابلة للتحديد ويطلب المعلومات المحددة اللازمة لحلها.

النتائج التجريبية
تم تقييم البروتوكول على أربعة معايير قياسية (Asia, Sachs, Child, Alarm) وبيانات اصطناعية مصممة لاختبار مستويات محددة.

• أداء الأوراكل المثالي: تحت افتراض وجود أوراكل مثالي، استعاد البروتوكول الـ DAG الحقيقي بدقة (Precision) واستدعاء (Recall) وF1 تساوي 1.000 في جميع المعايير الأربعة باستخدام بالضبط $1+K$ من التفاعلات.
  • Alarm (V=37): تم استعادة 46 حافة في 27 تفاعلاً.
  • Sachs (V=11): تم استعادة 17 حافة في 8 تفاعلات.
• فعالية التسلسل: في مجموعة بيانات Sachs، قام التسلسل وحده بحل 5 من أصل 19 حافة حقيقية من البيانات وحدها. إضافة المستويات الآمنة الجديدة حسنت دقة الاتجاه من 61.5% (القاعدة L0-L2) إلى 66.7% عند تفعيل حارس عدم الاتفاق.
• خصوصية المستويات: أكدت اختبارات الإجهاد الاصطناعية أن كل مستوى جديد يتمتع بدقة إيجابية في نطاقه الأصلي (مثل LLSNM في ضجيج الموقع-المقياس، وLIGCI في البيانات القريبة من الحتمية) ويمتنع (يعطي 0/40) في البيانات خارج النطاق، مما يمنع النتائج الإيجابية الكاذبة.
• جبهة باريتو (Pareto Frontier): في Sachs، أظهر البروتوكول مقايضة بين عدد الاستعلامات ودرجة F1. حقق نهج "الآمن فقط" (التسلسل بدون أوراكل) F1=0.571 مع 5 استعلامات، بينما حقق البروتوكول الكامل F1=1.000 باستخدام 13 استعلاماً (باستخدام التسلسل لتقليل عبء الأوراكل).

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

• المساهمة النظرية: يمثل حد $1+K$ الجانب المقابل لجانب الاستخلاص في حدود ميزانية التدخل في الاكتشاف السبابي النشط، مما يحدد الحد الأدنى من المعلومات المطلوبة لحل DAG عند توفر معرفة الخبير.
• الفائدة العملية: يسمح البروتوكول للممارسين بتركيز جهد الخبير حصرياً على الحواف غير القابلة للتحديد، مما يقلل العبء المعرفي عبر تقديم أسئلة محددة وواعية بالنطاق بدلاً من مج-رد اتجاهات الحواف الخام.
• القيود: يشير المؤلفون صراحةً إلى أن النطاق الحالي يقتصر على المتغيرات المستمرة؛ حيث تُعامل الشبكات البايزية المنفصلة فقط كفحص لمتانة طبقة الأوراكل. يفترض البروتوكول وجود أوراكل مثالي؛ وقد تم تحديد التعامل مع استجابات الخبراء الضوضائية أو الاحتمالية كعمل مستقبلي. كما أن مرحلة بناء الهيكل تفرض حداً للاستدعاء، حيث إن الحواف التي يتم حذفها بواسطة اختبار HSIC الأولي لا يمكن استعادتها.

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