📊 statistics

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

यह शोध पत्र निरंतर डेटा के लिए एक पुनरावृत्ति कारण खोज (इटरेटिव कॉज़ल डिस्कवरी) प्रोटोकॉल प्रस्तुत करता है जो पांच गेटेड टियर्स में प्रति-एज पहचान क्षमता प्रमाणपत्र (पर-एज आइडेंटिफिएबिलिटी सर्टिफिकेट्स) और विफलता-मोड प्रश्न (फेल्योर-मोड क्वेरीज) निर्दिष्ट करता है, जो किसी भी निर्देशित अचक्रीय ग्राफ (डायरेक्टेड एसाइक्लिक ग्राफ) को पूरी तरह से पुनर्प्राप्त करने के लिए $1+K$ विशेषज्ञ इंटरैक्शन की एक सैद्धांतिक ऊपरी सीमा स्थापित करता है।

मूल लेखक: Eichi Uehara

प्रकाशित 2026-05-28

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Eichi Uehara

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य सुलझाने की कोशिश कर रहे हैं: किसने क्या किया? आपके पास सुरागों (डेटा) का एक ढेर है जो दिखा रहा है कि दो चीजें, जैसे कि "धुआं" और "आग", अक्सर एक साथ होती हैं।

अधिकांश मौजूदा जासूसी उपकरण (एल्गोरिदम) आपके सुरागों को देखेंगे और तुरंत एक नक्शा बना देंगे कि "धुआं आग का कारण बनता है।" लेकिन समस्या यह है कि वे अनुमान लगा रहे हो सकते हैं। वे केवल नक्शे को पूरा दिखाने के लिए दिशा थोप रहे हो सकते हैं, भले ही सुरागों से यह साबित न हुआ हो कि तीर किस दिशा में इशारा करता है।

यह शोध पत्र एक नया, अधिक ईमानदार जासूसी प्रोटोकॉल पेश करता है। केवल एक नक्शा बनाने के बजाय, यह नक्शे पर मौजूद हर एक संबंध के साथ एक डिजिटल "आईडी कार्ड" (ID Card) जोड़ता है।

तीन प्रकार के आईडी कार्ड

प्रत्येक संदिग्धों के जोड़े (जैसे धुआं और आग) के लिए, प्रोटोकॉल तीन प्रकार के प्रमाणपत्र जारी करता है:

"प्रमाणित" कार्ड (proven_*):
- उपमा: जासूस को एक पुख्ता सबूत (smoking gun) मिल गया है।
- इसका अर्थ है: डेटा स्वयं, एक विशिष्ट गणितीय नियम (जैसे कि "लोकेशन-स्केल नॉइज़" टेस्ट या "इंफॉर्मेशन-जियोमेट्री" टेस्ट) का उपयोग करके, बिना किसी संदेह के सिद्ध करता है कि A, B का कारण है। एल्गोरिदम ने अनुमान नहीं लगाया; गणित ने काम किया।
- परिणाम: दिशा तय हो गई है। कोई सवाल नहीं।
"भटकाने वाला सुराग" कार्ड (resolved_mediated):
- उपमा: जासूस को एहसास होता है कि धुआं और आग सीधे तौर पर जुड़े हुए नहीं हैं; उन दोनों का कारण कोई तीसरी चीज़ है, जैसे कि "माचिस"।
- इसका अर्थ है: जो प्रत्यक्ष संबंध दिख रहा था, वह वास्तव में एक बिचौलिए (middleman) के कारण था। उस सीधे लिंक को नक्शे से हटा दिया जाता है।
"मुझे मदद चाहिए" कार्ड (impossible_*):
- उपमा: जासूस एक दीवार से टकरा गया है। सुराग बहुत अस्पष्ट हैं कि यह बताने के लिए कि धुआं आग का कारण बनता है या आग धुएं का।
- इसका अर्थ है: डेटा पर्याप्त नहीं है। लेकिन केवल हार मानने या कोई मनमाना अनुमान लगाने के बजाय, यह कार्ड आपको बताता है कि विशेषज्ञ से कौन सा विशिष्ट प्रश्न पूछना है ताकि इसे हल किया जा सके।
- उदाहरण: कार्ड कह सकता है, "हम डेटा से यह नहीं बता सकते। विशेषज्ञ से पूछें: 'क्या धुएं और आग के बीच का संबंध सीधा है, या कोई छिपा हुआ कारण है?'"

"स्तरित" सुरक्षा जाल (Tiered Safety Net)

यह शोध पत्र एक "कैस्केड" (श्रृंखला) परीक्षणों का वर्णन करता है, जो सुरक्षा जांच बिंदुओं की एक श्रृंखला की तरह है।

कल्पना कीजिए कि एक क्लब का बाउंसर (डेटा) है।
पहला बाउंसर चेक करता है कि क्या डेटा "लीनियर" (सरल) दिखता है। यदि यह पास हो जाता है, तो बहुत अच्छा!
यदि यह विफल रहता है, तो डेटा अगले बाउंसर के पास जाता है, जो "नॉन-लीनियर" पैटर्न की जांच करता है।
महत्वपूर्ण नियम: यदि कोई बाउंसर सुनिश्चित नहीं है (प्रीकंडीशन विफल हो जाता है), तो वे निर्णय लेने के लिए मजबूर नहीं करते हैं। वे बस कहते हैं, "मैं इसकी पुष्टि नहीं कर सकता," और संदिग्ध को अगले स्तर पर भेज देते हैं। यदि कोई भी स्तर इसकी पुष्टि नहीं कर पाता है, तो संदिग्ध को "मुझे मदद चाहिए" कार्ड मिलता है।

यह एल्गोरिदम को खाली जगहों को भरने के लिए आत्मविश्वास से गलतियां करने से रोकता है।

"विशेषज्ञ साक्षात्कार" रणनीति

जब एल्गोरिदम एक दीवार से टकराता है (जब "मुझे मदद चाहिए" कार्ड मिलते हैं), तो उसे पूरे रहस्य को सुलझाने के लिए एक मानव विशेषज्ञ से उत्तर मांगना पड़ता है। लेकिन प्रश्न पूछना महंगा है (इसमें समय और प्रयास लगता है)। यह शोध पत्र इस बारेंे में सुझाव देता है कि पूरे रहस्य को सुलझाने के लिए न्यूनतम संभव प्रश्न कैसे पूछे जाएं।

वे दो विशेष साक्षात्कार तकनीकें पेश करते हैं:

"हब" (Hub) प्रश्न: एक बार में एक संबंध के बारे में पूछने के बजाय, विशेषज्ञ से पूछा जाता है: "इस नेटवर्क में शीर्ष K लोग कौन हैं जिनके पास सबसे अधिक बाहरी कनेक्शन (outgoing connections) हैं?" यह तुरंत नेटवर्क के "हब्स" की पहचान करता है।
"संतान" (Children) प्रश्न: एक बार हब की पहचान हो जाने के बाद, विशेषज्ञ से पूछा जाता है: "इस विशिष्ट व्यक्ति के सीधे बच्चे (direct children) कौन हैं?"

जादुई संख्या (1+K):
यह शोध पत्र सिद्ध करता है कि यदि आपके पास एक सटीक विशेषज्ञ है जो सही उत्तर देता है, तो आपको पूरे नेटवर्क को सुलझाने के लिए केवल 1 + K प्रश्नों की आवश्यकता होगी, जहाँ K उन लोगों की संख्या है जिनके बच्चे हैं (non-leaf nodes)।

उपमा: यदि आपके पास एक पारिवारिक वंशावली (family tree) है, तो आपको हर व्यक्ति के लिए यह पूछने की आवश्यकता नहीं है कि "क्या पिता, पुत्र का जनक है?" आप बस माता-पिता से पूछते हैं, "आपके बच्चे कौन हैं?" और आप एक ही बार में पूरी वंशावली संरचना प्राप्त कर लेते हैं।

उन्होंने क्या परीक्षण किया

लेखकों ने इन परीक्षणों को चार प्रसिद्ध "रहस्य मामलों" (डेटासेट जिन्हें asia, sachs, child, और alarm नाम दिया गया है) पर किया।

परिणाम: जब उन्होंने "परफेक्ट एक्सपर्ट" सिमुलेशन का उपयोग किया, तो उनकी विधि ने ठीक उसी संख्या में प्रश्नों का उपयोग करके पूरे रहस्य को सुलझा लिया जैसा कि उनके गणित ने भविष्यवाणी की थी (100% सटीकता के साथ, ठीक 1+K प्रश्नों के साथ)।
समझौता (Trade-off): यदि उन्होंने विशेषज्ञ से नहीं पूछा और केवल डेटा पर भरोसा किया, तो उन्हें कुछ कनेक्शन सही मिले लेकिन उन्हें अन्य कनेक्शनों को खाली छोड़ना पड़ा (या उन्हें "अनेहलनीय" के रूप में चिह्नित करना पड़ा) बजाय गलत अनुमान लगाने के।

सारांश

यह शोध पत्र आपको केवल एक नक्शा नहीं देता; यह आपको एक नक्शा देता है जिसमें एक संकेत सूची (legend) है।

यह आपको बताता है कि नक्शे के कौन से हिस्से डेटा द्वारा खोजे गए थे।
यह आपको बताता है कि किन हिस्सों को खारिज कर दिया गया था।
यह आपको बिल्कुल सटीक रूप से बताता है कि कौन से हिस्से गायब हैं और उन्हें भरने के लिए आपको विशेषज्ञ से क्या विशिष्ट प्रश्न पूछने की आवश्यकता है।
यह सिद्ध करता है कि यदि आप सही प्रश्न पूछते हैं, तो आप विशेषज्ञ के आश्चर्यजनक रूप से कम प्रश्नों के साथ पूरे पहेली को सुलझा सकते हैं।

तकनीकी सारांश: प्रति-एज (Per-Edge) असंभवता प्रमाणपत्रों के साथ पुनरावृत्त कारण खोज (Iterative Causal Discovery)

समस्या विवरण
वर्तमान कारण खोज (causal discovery) एल्गोरिदम आमतौर पर एक पूर्ण रूप से उन्मुख निर्देशित अचक्रीय ग्राफ (directed acyclic graph - DAG) तो लौटाते हैं, लेकिन वे डेटा द्वारा पहचाने गए किनारों की दिशाओं और आउटपुट बाधाओं को पूरा करने के लिए एल्गोरिदम द्वारा थोपी गई दिशाओं के बीच अंतर करने में विफल रहते हैं। मानक मार्कोव और निष्ठा (faithfulness) स्थितियों के तहत, अवलोकनात्मक डेटा केवल एक मार्कोव तुल्यता वर्ग (Markov equivalence class) की पहचान करता है; v-संरचनाओं (v-structures) पर न होने वाले किनारों की दिशाएं अनिश्चित होती हैं। मौजूदा विधियां या तो बिना किसी नैदानिक औचित्य के अनिश्चित दिशाओं को जबरन लागू करती हैं (जैसे NOTEARS, DAGMA), या उन्हें बिना यह निर्दिष्ट किए अनिश्चित छोड़ देती हैं (जैसे FCI) कि उन्हें हल करने के लिए विशिष्ट पूर्व सूचना की आवश्यकता है। निरंतर अनुकूलन (continuous optimization) विधियों के बारे में यह भी दिखाया गया है कि वे डेटा आर्टिफैक्ट्स (जैसे varsortability) का लाभ उठा सकती हैं जो वास्तविक पहचान की नकल करते हैं। एक सिद्धांत-आधारित प्रोटोकॉल का अभाव है जो प्रति-एज ऑडिटेबिलिटी (per-edge auditability) प्रदान कर सके, जो डेटा-संचालित पहचान क्षमता को एल्गोरिथम थोप (algorithmic imposition) से स्पष्ट रूप से अलग कर सके, और अनिश्चित किनारों को हल करने के लिए आवश्यक विशिष्ट विशेषज्ञ प्रश्नों की पहचान कर सके।

कार्यप्रणाली (Methodology)
यह शोध पत्र निरंतर डेटा पर अवलोकनात्मक कारण खोज के लिए एक नियत (deterministic), तीन-चरणीय प्रोटोकॉल प्रस्तावित करता है। यह प्रोटोकॉल डेटा-केवल कंकाल (skeleton) के प्रत्येक संभावित किनारे के लिए एक विविक्त "असंभवता प्रमाणपत्र" (impossibility certificate) जारी करता है, जो किनारे को या तो resolved (डेटा-पहचाना गया या मध्यस्थता किया गया) या impossible (डेटा-अपर्याप्त, विशेषज्ञ इनपुट की आवश्यकता) के रूप में वर्गीकृत करता है।

चरण 1: कंकाल और मध्यस्थ खोज (Skeleton and Mediator Search):
- मार्जिनली स्वतंत्र जोड़ों को हटाने के लिए FDR-नियंत्रित HSIC परीक्षणों का उपयोग करके एक कंकाल का निर्माण करता है।
- देखे गए चरों द्वारा मध्यस्थता वाले किनारों को पहचानने और हटाने के लिए एक बहु-स्तरीय मध्यस्थ खोज (multi-tier mediator search) करता है।
चरण 2: गेटेड पहचान क्षमता कैस्केड (Gated Identifiability Cascade):
- आठ-स्तरीय कैस्केड शेष किनारों का मूल्यांकन करता है। टियर्स में शास्त्रीय विधियाँ (Linear ANM $L_0$ , Nonlinear ANM $L_1$ , HOC LiNGAM $L_2$ ) और इस कार्य में पेश किए गए पांच नए टियर्स शामिल हैं: LSNM (लोकेशन-स्केल नॉइज़), IGCI (इंफॉर्मेशन-जियोमेट्रिक), Stein (स्कोर मैचिंग), MDL (एल्गोरिद्मिक मार्कोव कंडीशन), और PEIT (एन्ट्रॉपी-इंवर्जन टेस्ट)।
- गेटिंग तंत्र (Gating Mechanism): प्रत्येक टियर को सांख्यिकीय परीक्षणों (जैसे गैर-गाऊसीपन के लिए Shapiro–Wilk, हेटेरोसेडास्टिसिटी परीक्षण) द्वारा प्रीकंडीशन किया जाता है। यदि किसी टियर की प्रीकंडीशन विफल हो जाती है, तो वह दिशा थोपने के बजाय स्वयं को रोक लेता है (abstains)।
- क्रॉस-टियर सहमति (Cross-Tier Consensus): एक "असहमति गार्ड" (disagreement guard) $L_0$ के निर्णयों को तब कम स्तर पर ले आता है जब उच्च-परिशुद्धता वाले टियर्स (IGCI, Stein, MDL) दिशा का खंडन करते हैं, जिससे किनारे को impossible_l0_disagrees_with_high_tier के रूप में पुन: लेबल किया जाता है।
- जो किनारे किसी भी टियर द्वारा हल नहीं होते, उन्हें impossible_* लेबल प्राप्त होता है, जो विफलता के मोड (जैसे लेटेंट कन्फाउंडिंग, कमजोर नॉन-लीनियरिटी) और विशेषज्ञ के लिए आवश्यक प्रश्न को एनकोड करता है।
चरण 3: लक्षित ओरेकल क्वेरी (Targeted Oracle Queries):
- प्रोटोकॉल केवल impossible_* लेबल वाले किनारों पर ही डोमेन विशेषज्ञ के साथ इंटरैक्ट करता है।
- क्वेरी प्रिमिटिव्स (Query Primitives):
  - प्रति-एज क्वेरी: दिशा (FWD/BWD) या अनुपस्थिति के लिए पूछना।
  - मेटा-हब क्वेरी: आउट-डिग्री के आधार पर शीर्ष- $K$ नोड्स के बारे में पूछना।
  - नोड-चिल्ड्रन क्वेरी: किसी विशिष्ट नोड के प्रत्यक्ष बच्चों के बारे में पूछना, जिससे सभी बाहर जाने वाले किनारे एक साथ प्रतिबद्ध होते हैं।
- ऑटो-प्रोपैगेशन (Auto-Propagation): प्रत्येक ओरेकल कमिट के बाद, सिस्टम शून्य-लागत ऑटो-रिज़ॉल्यूशन पास (acyclicity चेक्स, Meek रूल्स, ट्रांसिटिव d-सेपरेशन) चलाता है ताकि बिना किसी और क्वेरी के अतिरिक्त किनारों को हल किया जा सके।

प्रमुख योगदान

प्रति-एज प्रमाणपत्र (Per-Edge Certificates): प्रोटोकॉल प्रत्येक किनारे को एक विविक्त कोड आवंटित करता है। resolved_* कोड उस विशिष्ट प्रमेय (जैसे $L_{Stein}$ ) का हवाला देता है जो दिशा को न्यायसंगत बनाता है, जबकि impossible_* कोड विफलता के मोड और आवश्यक प्रश्न को रिकॉर्ड करता है।
टियर-जागरूक त्याग (Tier-Aware Abstention): पांच नए गेटेड टियर्स (LSNM, IGCI, Stein, MDL, PEIT) का परिचय यह सुनिश्चित करता है कि दिशाएँ केवल तभी प्रतिबद्ध की जाएँ जब एक विशिष्ट पहचान प्रमेय संतुष्ट हो। यदि प्रीकंडीशन विफल हो जाता है, तो सिस्टम गलत दिशा थोपने के बजाय त्याग (abstain) करता है।
1+K इंटरैक्शन बाउंड: यह शोध पत्र किसी भी ग्राउंड-ट्रुथ DAG को रिकवर करने के लिए $1+K$ विशेषज्ञ इंटरैक्शन का एक सूचना-सैद्धांतिक ऊपरी बाउंड स्थापित करता है, जहाँ $K$ गैर-लीफ वर्टिकल की संख्या है। यह एक सिंगल मेटा-हब क्वेरी (लक्ष्यों की पहचान करने के लिए) और $K$ नोड-चिल्ड्रन क्वेरी के संयोजन से प्राप्त किया जाता है।
लक्षित निष्कर्षण (Targeted Elicitation): सक्रिय शिक्षण (active learning) विधियों के विपरीत, जो पूर्ण टोपोलॉजिकल ऑर्डर या व्यापक हस्तक्षेप मांग सकती हैं, यह प्रोटोकॉल केवल अनिश्चित किनारों को अलग करता है और आवश्यक विशिष्ट जानकारी मांगता है।

प्रायोगिक परिणाम
प्रोटोकॉल का मूल्यांकन चार मानक बेंचमार्क (Asia, Sachs, Child, Alarm) और विशिष्ट टियर्स का परीक्षण करने के लिए डिज़ाइन किए गए सिंथेटिक डेटा पर किया गया।

आदर्श ओरेकल प्रदर्शन: एक पूर्ण ओरेकल की धारणा के तहत, प्रोटोकॉल ने ठीक $1+K$ इंटरैक्शन का उपयोग करके सभी चार बेंचमार्क पर ग्राउंड-ट्रुथ DAG को Precision = Recall = F1 = 1.000 के साथ रिकवर किया।
- Alarm (V=37): 27 इंटरैक्शन में 46 किनारे रिकवर किए गए।
- Sachs (V=11): 8 इंटरैक्शन में 17 किनारे रिकवर किए गए।
कैस्केड प्रभावकारिता: Sachs डेटासेट पर, कैस्केड ने अकेले डेटा से 19 वास्तविक किनारों में से 5 को हल किया। असहमति गार्ड सक्रिय होने पर नए सुरक्षित टियर्स के जुड़ने से दिशा परिशुद्धता (direction precision) $L_0$ - $L_2$ के 61.5% से बढ़कर 66.7% हो गई।
टियर विशिष्टता: सिंथेटिक स्ट्रेस टेस्ट ने पुष्टि की कि प्रत्येक नया टियर अपने नेटिव रिजीम (जैसे LLSNM के लिए लोकेशन-स्केल नॉइज़, LIGCI के लिए निकट-नियत डेटा) पर परिशुद्धता-सकारात्मक है और ऑफ-रिजीम डेटा पर त्याग (abstain) करता है, जिससे गलत सकारात्मक (false positives) को रोका जा सके।
पारेटो फ्रंटियर (Pareto Frontier): Sachs पर, प्रोटोकॉल ने क्वेरी संख्या और F1 स्कोर के बीच एक ट्रेड-ऑफ प्रदर्शित किया। एक "SAFE-only" दृष्टिकोण (कैस्केड बिना ओरेकल के) 5 क्वेरी के साथ F1=0.571 प्राप्त करता है, जबकि पूर्ण प्रोटोकॉल 13 क्वेरी के साथ F1=1.000 प्राप्त करता है (ओरेकल बोझ को कम करने के लिए कैस्केड का उपयोग करके)।

महत्व और दावे
शोध पत्र एक मौलिक अंतर को संबोधित करने का दावा करता है: वर्तमान विधियों की दिशाओं को डेटा-पहचाने गए बनाम एल्गोरिदम-थोपे गए के बीच अंतर करने में अक्षमता। प्रत्येक किनारे के साथ "प्रमाणपत्र" संलग्न करके, प्रोटोकॉल एक पारदर्शी ऑडिट ट्रेल प्रदान करता है।

सैद्धांतिक योगदान: $1+K$ बाउंड सक्रिय कारण खोज (active causal discovery) के हस्तक्षेप-बजट बाउंड्स के सूचना-पक्ष का समकक्ष है, जो मात्रा निर्धारित करता है कि विशेषज्ञ ज्ञान उपलब्ध होने पर DAG को हल करने के लिए न्यूनतम सूचना की आवश्यकता है।
व्यावहारिक उपयोगिता: प्रोटोकॉल चिकित्सकों को केवल अनिश्चित किनारों पर अपना विशेषज्ञ प्रयास केंद्रित करने की अनुमति देता है, जो कच्चे किनारे की दिशाओं के बजाय विशिष्ट, रिजीम-जागरूक प्रश्न प्रस्तुत करके संज्ञानात्मक भार को कम करता है।
सीमाएँ: लेखक स्पष्ट रूप से उल्लेख करते हैं कि वर्तमान दायरा निरंतर चरों तक सीमित है; डिस्क्रीट बेयसियन नेटवर्क को केवल ओरेकल लेयर के लिए एक मजबूती जांच (robustness check) के रूप में माना गया है। प्रोटोकॉल एक पूर्ण ओरेकल मानता है; शोर वाले या संभाव्य विशेषज्ञ प्रतिक्रियाओं को संभालना भविष्य के कार्य के रूप में पहचाना गया है। कंकाल निर्माण चरण एक रिकॉल सीमा लागू करता है, क्योंकि प्रारंभिक HSIC टेस्ट द्वारा हटाए गए किनारों को रिकवर नहीं किया जा सकता है।

यह कार्य खुद को निरंतर अनुकूलन या बाधा-आधारित विधियों के विकल्प के रूप में नहीं, बल्कि एक ऑर्थोगोनल दृष्टिकोण के रूप में स्थापित करता है जो प्रति-एज ऑडिटेबिलिटी को प्राथमिकता देता है और लक्षित, प्रमाण-संचालित क्वेरी के माध्यम से विशेषज्ञ निष्कर्षण की लागत को कम करता है।

तीन प्रकार के आईडी कार्ड

"स्तरित" सुरक्षा जाल (Tiered Safety Net)

"विशेषज्ञ साक्षात्कार" रणनीति

उन्होंने क्या परीक्षण किया

सारांश

इसी तरह के और पेपर