تحديد نماذج السبب الهيكلي على شكل شجرة في وقت متعدد الحدود

تُستخدم نماذج السبب الهيكلي الخطية (SCMs) للتعبير عن العلاقات وتحليلها بين المتغيرات العشوائية. يتم تمثيل التأثيرات السببية المباشرة كحواف موجهة وعوامل التداخل كحواف ثنائية الاتجاه. تُعتبر عملية تحديد المعلمات السببية من الترابطات بين العقد بمثابة مشكلة مفتوحة في الذكاء الاصطناعي. في هذه الورقة، ندرس نماذج SCM التي تتشكل مكوناتها الموجهة على شكل شجرة. تقدم فان دير زاندر وآخرون خوارزمية من نوع PSPACE لمشكلة التعرف في هذه الحالة، وهي تحسين كبير على نهج قاعدة غروبا العامة، الذي له تعقيد زمني أسي مزدوج في عدد المعلمات الهيكلية. ومع ذلك، لم تُظهر خوارزميتهم أنها كاملة. في هذا العمل، نقدم خوارزمية عشوائية في وقت متعدّد الحدود، تحل مشكلة التعرف لنماذج SCM على شكل شجرة. بالنسبة لكل معلمة هيكلية، تقرر خوارزمياتنا ما إذا كانت قابلة للتحديد بشكل عام، أو قابلة للتحديد بشكل عام مرتين، أو غير قابلة للتحديد بشكل عام. (لا يمكن أن تحدث حالات أخرى.) في الحالتين الأوليين، توفر قدراً أو قدرين من الحدود الجذرية التربيعية النسبية لمتعددات الحدود (FASTPs) للمعلمة المقابلة، على التوالي. بشكل خاص، ليست خوارزميتنا فقط في وقت متعدد الحدود، بل هي أيضاً كاملة لنماذج SCM على شكل شجرة.