पार्श्विक समय में वृक्ष-आकृत संरचनात्मक कारणात्मक मॉडलों की पहचान

रेखीय संरचनात्मक कारणात्मक मॉडल (SCMs) का उपयोग रैंडम वेरिएबल्स के बीच संबंधों को व्यक्त करने और विश्लेषण करने के लिए किया जाता है। सीधे कारणात्मक प्रभावों का प्रतिनिधित्व निर्दिष्ट किनारों के रूप में किया जाता है और भ्रमित करने वाले कारकों का प्रतिनिधित्व द्विदिशीय किनारों के रूप में किया जाता है। नोड्स के बीच के सहसंबंधों से कारणात्मक पैरामीटर्स की पहचान करना कृत्रिम बुद्धिमत्ता में एक खुला प्रश्न है। इस पत्र में, हम SCMs का अध्ययन करते हैं जिनका निर्दिष्ट घटक एक वृक्ष बनाता है। वान डेर ज़ैंडर और अन्य ने इस मामले में पहचान समस्या के लिए एक PSPACE-एल्गोरिदम दिया, जो सामान्य ग्रोबनर आधार दृष्टिकोण पर एक महत्वपूर्ण सुधार है, जिसमें संरचनात्मक पैरामीटर्स की संख्या में डबल-एक्सपोनेंशियल समय जटिलता होती है। हालाँकि, वे यह नहीं दिखाते कि उनका एल्गोरिदम पूर्ण है। इस काम में, हम एक यादृच्छिक बहुपद-समय एल्गोरिदम प्रस्तुत करते हैं, जो वृक्ष-आकृत SCMs के लिए पहचान समस्या को हल करता है। प्रत्येक संरचनात्मक पैरामीटर के लिए, हमारे एल्गोरिदम यह तय करते हैं कि क्या यह सामान्य रूप से पहचान योग्य है, सामान्य रूप से 2-पहचान योग्य है, या सामान्य रूप से अनजान है। (कोई अन्य मामलों का होने की संभावना नहीं है।) पहले दो मामलों में, यह संबंधित पैरामीटर के लिए एक या दो अंशात्मक आसन्न वर्गमूल टर्म प्रदान करता है। विशेष रूप से, हमारा एल्गोरिदम न केवल बहुपद समय है, बल्कि वृक्ष-आकृत SCMs के लिए पूर्ण भी है.