🤖 machine learning

TriOpt: A Scalable Algorithm for Linear Causal Discovery

TriOpt एक स्केलेबल एल्गोरिदम है जो लीनियर कॉज़ल डिस्कवरी (linear causal discovery) के लिए है, जो पहले शेर्मन-मोरिसन अपडेट्स (Sherman-Morrison updates) के माध्यम से कुशलतापूर्वक टोपोलॉजिकल ऑर्डरिंग को रिकवर करके और फिर बिना एसाइक्लिसिटी बाधाओं (acyclicity constraints) के एक कॉन्वेक्स स्ट्रक्चर लर्निंग समस्या को हल करके, उच्च सटीकता बनाए रखते हुए अत्याधुनिक तरीकों की तुलना में महत्वपूर्ण गति प्राप्त करता है।

मूल लेखक: Rafat Ashraf Joy, Elena Zheleva

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

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

CC BY 4.0

मूल लेखक: Rafat Ashraf Joy, Elena Zheleva

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

कल्पना कीजिए कि आप लोगों के एक बड़े समूह का पारिवारिक वंश (family tree) पता लगाने की कोशिश कर रहे हैं, लेकिन आपके पास केवल उनकी आपस में बातचीत करते हुए फोटो एल्बम है, न कि जन्म प्रमाण पत्र। आपको यह अनुमान लगाना है कि किसका माता-पिता कौन है, उनके दिखने और व्यवहार के आधार पर। डेटा साइंस की दुनिया में, इसे Causal Discovery कहा जाता है: अवलोकन संबंधी डेटा (observational data) से कारण-और-प्रभाव (cause-and-effect) के संबंधों को समझना।

समस्या यह है कि जैसे-जैसे लोगों (चरों/variables) की संख्या बढ़ती है, संभावित पारिवारिक वंशों की संख्या बहुत तेजी से विस्फोट की तरह बढ़ती है। यह एक भूलभुलैया में एक सही रास्ता खोजने जैसा है जो हर नए मोड़ के साथ तेजी से जटिल होता जाता है।

यह शोध पत्र एक नया टूल पेश करता है जिसे TriOpt (Three-Fold Optimization) कहा जाता है, ताकि इस भूलभुलैया को पिछले तरीकों की तुलना में बहुत तेज़ी से और अधिक सटीकता से हल किया जा सके, विशेष रूप से विशाल डेटासेट के मामले में।

TriOpt कैसे काम करता है, यहाँ सरल चरणों और उपमाओं में दिया गया है:

पुराने तरीकों के साथ समस्या

TriOpt से पहले, शोधकर्ता दो मुख्य रणनीतियों का उपयोग करते थे, जिनमें से दोनों में एक बड़ी खामी थी:

"ऑर्डर-फर्स्ट" (क्रम-प्रथम) विधि: कल्पना कीजिए कि आप पीढ़ियों के क्रम (दादा-दादी, फिर माता-पिता, फिर बच्चे) का पहले अनुमान लगाकर और फिर रेखाएं खींचकर एक पारिवारिक वंश बनाने की कोशिश कर रहे हैं।
- खामी: जब भी वे किसी "लीफ" (वह व्यक्ति जिसका कोई बच्चा नहीं है) का अनुमान लगाते और अगले व्यक्ति की जांच करने के लिए उन्हें सूची से हटाते, तो उन्हें एक विशाल गणितीय चार्ट (kernel matrix) को फिर से शुरू से कैलकुलेट करना पड़ता था। यह हर बार एक वाक्य से एक शब्द हटाने पर पूरी विश्वकोश (encyclopedia) को फिर से पढ़ने जैसा है। बड़े समूहों के लिए यह अविश्वसनीय रूप से धीमा था।
"कंटीन्यूअस ऑप्टिमाइज़ेशन" (सतत अनुकूलन) विधि: यह दृष्टिकोण पूरे पेड़ को एक साथ बनाने की कोशिश करता है, एक स्लाइडर को तब तक खिसकाते हुए जब तक कि तस्वीर सही न दिखने लगे।
- खामी: यह सुनिश्चित करने के लिए कि पेड़ में लूप (जैसे कि एक बच्चा खुद ही अपना दादा बन जाए) न हों, कंप्यूटर को हर एक स्टेप पर एक बहुत ही भारी, जटिल गणना (matrix exponential) करनी पड़ती है। यह कार चलाने और लगातार इंजन की जांच करने जैसा है कि क्या वह अभी भी चल रहा है, इसके लिए इंजन को खोलकर फिर से जोड़ने की आवश्यकता पड़ती है। यह सटीक है लेकिन कष्टदायक रूप से धीमा है।

TriOpt समाधान: एक तीन-चरणीय शॉर्टकट

TriOpt दोनों विधियों के सबसे अच्छे हिस्सों को जोड़ता है और इसे तेज़ बनाने के लिए एक "जादुई ट्रिक" जोड़ता है।

चरण 1: "मैजिक इरेज़र" (तेज़ क्रम)

TriOpt अभी भी पीढ़ियों के क्रम का अनुमान लगाकर शुरू करता है। हालाँकि, हर बार किसी व्यक्ति को हटाने पर विशाल गणितीय चार्ट को शुरू से फिर से कैलकुलेट करने के बजाय, यह Sherman-Morrison downdate नामक एक गणितीय ट्रिक का उपयोग करता है।

उपमा: कल्पना कीजिए कि आपके पास एक विशाल स्प्रेडशीट है। जब आप एक पंक्ति (row) को हटाते हैं, तो पूरी शीट को फिर से टाइप करने के बजाय, आप मौजूदा नंबरों में बस एक छोटा, विशिष्ट समायोजन करते हैं। TriOpt गणितीय रूप से ऐसा ही करता है। यह समझता है कि क्योंकि संबंध "रैखिक" (linear) हैं, इसलिए एक वेरिएबल को हटाना एक सरल, कम प्रयास वाला अपडेट है।
परिणाम: यह एक ऐसे कार्य को जो घंटों लेता था, मिनटों में बदल देता है, यहाँ तक कि हजारों वेरिएबल्स के लिए भी।

चरण 2: "वन-वे स्ट्रीट" (Convex Optimization)

एक बार जब TriOpt के पास सही क्रम (जैसे, दादा-दादी $\to$ माता-पिता $\to$ बच्चे) होता है, तो उसे सड़क के नियम पता होते हैं: माता-पिता केवल उन बच्चों को प्रभावित कर सकते हैं जो सूची में उनके बाद आते हैं।

उपमा: पुराने तरीकों में, कंप्यूटर को लगातार चेक करना पड़ता था, "क्या इसमें कोई लूप है? क्या यह एक डेड एंड है?" TriOpt बस एक कागज पर नक्शा बनाता है जहाँ केवल आगे की ओर बढ़ना ही संभव है। यह कंप्यूटर को केवल डेटा के "अपर ट्रायंगल" (ऊपरी त्रिकोण) को देखने के लिए मजबूर करता है।
परिणाम: क्योंकि कंप्यूटर को अब लूप्स की जांच करने की आवश्यकता नहीं है, इसलिए गणितीय समस्या "convex" हो जाती है। सरल शब्दों में, इसका मतलब है कि परिदृश्य एक ऊबड़-खाबड़ पहाड़ के बजाय एक चिकने कटोरे जैसा है। कंप्यूटर बिना कहीं फंसे सीधे नीचे (परफेक्ट उत्तर) तक फिसल सकता है।

चरण 3: "नो-लूप गारंटी"

चूंकि कंप्यूटर को केवल आगे देखने के लिए मजबूर किया जाता है (चरण 1 में पाए गए क्रम के आधार पर), इसलिए लूप बनाना गणितीय रूप से असंभव है।

परिणाम: महंगी "लूप-चेकिंग" गणित को पूरी तरह से हटा दिया जाता है। कंप्यूटर बस एक मानक, तेज़ समीकरण को हल करता है।

यह क्यों मायने रखता है (शोध पत्र के अनुसार)

लेखकों ने सिंथेटिक डेटा (बनाए गए परिदृश्य), सेमी-सिंथेटिक डेटा (वास्तविक जीन नेटवर्क), और वास्तविक दुनिया के डेटा (मानव कोशिकाओं में प्रोटीन सिग्नलिंग) पर TriOpt का परीक्षण किया।

गति: TriOpt वर्तमान सर्वोत्तम तरीकों की तुलना में कई गुना तेज़ है। 1,000 वेरिएबल्स वाले कुछ परीक्षणों में, यह अपने प्रतिस्पर्धियों की तुलना में 95% से 97% तक तेज़ था।
सटीकता: इतनी तेज़ होने के बावजूद, यह उतना ही सटीक है, और कभी-कभी धीमे तरीकों से भी अधिक सटीक है।
स्केलेबिलिटी: जबकि अन्य तरीके बड़े डेटासेट (high-dimensional) आने पर क्रैश हो जाते हैं या बहुत समय लेते हैं, TriOpt सुचारू रूप से ऊपर बढ़ता है।

एक छोटी सी कमी

शोध पत्र एक छोटी सी सीमा का उल्लेख करता है: "मैजिक इरेज़र" ट्रिक (Sherman-Morrison) अधिकांश डेटा के लिए पूरी तरह से काम करती है, लेकिन यदि डेटा में बहुत विशिष्ट, अजीब शोर पैटर्न (जैसे Exponential या Gumbel वितरण) हों, तो यह थोड़ी अस्थिर हो सकती है। हालाँकि, लेखकों ने इसे ठीक करने के लिए कोड में एक सुरक्षा जाल (safety net) बनाया है।

संक्षेप में: TriOpt एक ऐसी कार में अपग्रेड करने जैसा है जिसे हर चौराहे पर रुककर मैप चेक करना पड़ता है, बजाय एक हाई-स्पीड ट्रेन के जिसे पता है कि ट्रैक एकतरफा है। यह आपको गंतव्य (सही कॉज़ल ग्राफ) तक बहुत तेज़ी से पहुँचाता है बिना रास्ता भटके।

तकनीकी सारांश: TriOpt – एक रैखिक कारण खोज (Linear Causal Discovery) के लिए स्केलेबल एल्गोरिदम

समस्या की परिभाषा

कारण खोज (Causal discovery) का लक्ष्य अवलोकन संबंधी डेटा (observational data) से कारण-और-प्रभाव संबंधों को दर्शाने वाले निर्देशित अचक्रीय ग्राफ़ (Directed Acyclic Graphs - DAGs) सीखना है। जबकि यादृच्छिक नियंत्रित परीक्षण (randomized controlled trials) स्वर्ण मानक हैं, वे लागत या नैतिक बाधाओं के कारण अक्सर अव्यवहार्य होते हैं। फलस्वरूप, अवलोकन संबंधी डेटा से कारण संरचनाओं को सीखना एक मौलिक चुनौती है।

इस क्षेत्र में प्राथमिक बाधा चरों की संख्या ( $d$ ) के साथ ग्राफ़ खोज स्थान का सुपर-एक्सपोनेंशियल (super-exponential) विकास है। मौजूदा दृष्टिकोण आम तौर पर दो प्रतिमानों (paradigms) में आते हैं, जो दोनों ही उच्च-आयामी (high-dimensional) सेटिंग्स में महत्वपूर्ण स्केलेबिलिटी सीमाओं का सामना करते हैं:

क्रम-आधारित विधियाँ (Ordering-based methods) (जैसे, SCORE, CaPS, DiffAN): ये पहले एक टोपोलॉजिकल व्यवस्था (topological ordering) की पहचान करती हैं और फिर अवांछित किनारों (spurious edges) को हटा देती हैं। हालांकि ये प्रभावी हैं, लेकिन ये अक्सर कर्नल स्टाइन विसंगति (kernelized Stein discrepancy) पर निर्भर करती हैं, जिसके लिए प्रत्येक चर को हटाने के चरण में कर्नल मैट्रिसेस का पुनर्गणना और व्युत्क्रमण (inversion) आवश्यक होता है ( $O(d^2n^2)$ और $O(dn^3)$ )। इसके अलावा, पोस्ट-प्रोसेसिंग प्रूनिंग चरण (जैसे, CAM) उच्च आयामों में अत्यधिक धीमा हो सकता है।
सतत अनुकूलन विधियाँ (Continuous optimization methods) (जैसे, NOTEARS, GOLEM, DAGMA): ये DAG लर्निंग को एक अचक्रीयता बाधा (acyclicity constraint) के साथ एक विभेद्य उद्देश्य (differentiable objective) के रूप में प्रस्तुत करती हैं। हालांकि ये GPU त्वरण का लाभ उठाती हैं, अचकलीयता बाधा को लागू करने में आमतौर पर महंगी मैट्रिक्स एक्सपोनेंशियल ( $O(d^3)$ ) शामिल होती है और यह गैर-कन्वेक्सिटी (non-convexity) पेश करती है, जिससे ग्रेडिएंट लुप्त (vanishing gradients) हो जाते हैं और स्थानीय इष्टतम (local optima) के प्रति संवेदनशीलता बढ़ जाती है।

कार्यप्रणाली: TriOpt फ्रेमवर्क

यह शोध पत्र TriOpt (थ्री-फोल्ड ऑप्टिमाइज़ेशन) पेश करता है, जो एक फ्रेमवर्क है जो सटीकता से समझौता किए बिना स्केलेबिलिटी प्राप्त करने के लिए क्रम-आधारित और सतत अनुकूलन प्रतिमानों को एकीकृत करता है। TriOpt रैखिक कारण खोज को दो कुशल चरणों में विभाजित करता है:

चरण 1: लीनियर कर्नल के माध्यम से तीव्र पूर्वज व्यवस्था (Fast Ancestral Ordering)

मानक रेडियल बेसिस फंक्शन (RBF) कर्नल, जिसे महंगे पुनर्गणना की आवश्यकता होती है, के बजाय TriOpt स्कोर मिलिंग के लिए एक लीनियर कर्नल का उपयोग करता है।

योगात्मकता और शेरमन-मोरिसन (Additivity and Sherman-Morrison): लीनियर कर्नल एल्गोरिदम को कर्नल मैट्रिक्स की योगात्मक संरचना का लाभ उठाने की अनुमति देता है। जब एक लीफ नोड (leaf node) की पहचान कर ली जाती है और उसे हटा दिया जाता है, तो कर्नल मैट्रिक्स एक रैंक-1 संशोधन (rank-1 modification) से गुजरता है। TriOpt कर्नल इनवर्स को कुशलतापूर्वक अपडेट करने के लिए शेरमन-मोरिसन रैंक-1 डाउनडेट फॉर्मूला का उपयोग करता है।
जटिलता में कमी: यह दृष्टिकोण कर्नल मैट्रिक्स और इनवर्स गणना की कम्प्यूटेशनल लागत को $O(d^2n^2)$ और $O(dn^3)$ से घटाकर $O(dkn^2)$ और $O(dn^2 + kn^3)$ कर देता है (जहाँ $k \ll d$ संख्यात्मक स्थिरता के लिए पुन: व्युत्क्रमण की आवृत्ति है)।
लीफ पहचान: एल्गोरिदम CaPS में स्थापित पहचान मानदंडों (identifiability criteria) के अनुरूप, स्टाइन स्कोर एस्टीमेटर से प्राप्त हेसियन प्रॉक्सी (Hessian proxy) के अनुभवजन्य माध्य (empirical mean) को अधिकतम करके लीफ नोड्स की पुनरावृत्ति से पहचान करता है।

चरण 2: कॉनवेक्स सतत अनुकूलन (Convex Continuous Optimization)

एक बार टोपोलॉजिकल व्यवस्था प्राप्त हो जाने के बाद, खोज स्थान को सख्ती से ऊपरी-त्रिकोणीय (strictly upper-triangular) मैट्रिसेस तक सीमित कर दिया जाता है (यह मानते हुए कि व्यवस्था सही है)।

अचकलीयता बाधा का निष्कासन: NOTEARS या DAGMA के विपरीत, TriOpt को वैश्विक अचकलीयता बाधा को लागू करने की आवश्यकता नहीं है क्योंकि हार्ड अपर-ट्रायंगुलर बाधा (जो बाइनरी मास्क के माध्यम से लागू की जाती है) सही व्यवस्था होने पर स्वाभाविक रूप से अचकलीयता सुनिश्चित करती है।
कन्वेक्सिटी (Convexity): अचकलीयता बाधा को हटाने से, अनुकूलन समस्या कॉनवेक्स (convex) बन जाती है। ऑब्जेक्टिव फंक्शन में स्पर्सिटी (sparsity) के लिए एक स्मूथ $\ell_1$ (Charbonnier) रेगुलाइजेशन के साथ एक लीस्ट-स्क्वायर्स लॉस शामिल है।
सैद्धांतिक गारंटी: लेखक सिद्ध करते हैं कि सही व्यवस्था और लीनियर स्ट्रक्चरल इक्वेशन मॉडल (SEM) धारणाओं के तहत, यह कॉनवेक्स ऑब्जेक्टिव पॉपुलेशन सेटिंग में वास्तविक DAG को सफलतापूर्वक रिकवर करता है। अद्वितीय ग्लोबल मिनिमाइज़र वास्तविक एडजेसेंसी मैट्रिक्स के ट्रांसपोज़ के अनुरूप होता है।

मुख्य योगदान

नवीन सूत्रीकरण (Novel Formulation): TriOpt, क्रम-आधारित और सतत अनुकूलन विधियों को बारीकी से एकीकृत करता है, जिससे दोनों की स्केलेबिलिटी संबंधी बाधाओं को दूर किया जा सके।
कुशल व्यवस्था (Efficient Ordering): लीनियर कर्नल और शेरमन-मोरिसन डाउनडेट का लाभ उठाकर, TriOpt व्यवस्था चरण के रनटाइम को नाटकीय रूप से कम करता है, जिससे पिछले स्टाइन ऑर्डरिंग विधियों की $O(dn^3)$ बाधा से बचा जा सकता है।
कॉनवेक्स ऑप्टिमाइज़ेशन: फ्रेमवर्क ने रिकवर की गई व्यवस्था का उपयोग करके हार्ड अपर-ट्रायंगुलर बाधा लागू करके संरचना सीखने को एक कॉनवेक्स समस्या के रूप में पुनर्गठित किया है, जिससे महंगी अचकलीयता बाधाओं की आवश्यकता समाप्त हो गई है और ग्लोबल मिनिमम तक अभिसरण (convergence) सुनिश्चित हुआ है।
सैद्धांतिक गारंटी: पेपर यह प्रमाण प्रदान करता है कि TriOpt पॉपुलेशन सेटिंग में सही व्यवस्था के तहत सटीक रूप से अंतर्निहित लीनियर DAG को रिकवर करता है।

प्रयोगात्मक परिणाम

TriOpt का मूल्यांकन सिंथेटिक, सेमी-सिंथेटिक और वास्तविक दुनिया के डेटासेट्स पर अत्याधुनिक बेसलाइन्स (NOTEARS, GOLEM, DAGMA, और CaPS) के विरुद्ध किया गया।

स्केलेबिलिटी: उच्च-आयामी शासन ( $d=1000$ ) में, TriOpt ऑर्डर्स-ऑफ-मैग्निट्यूड स्पीडअप प्राप्त करता है। विशेष रूप से, शेरमन-मोरिसन के साथ TriOpt, NOTEARS की तुलना में लगभग 97% तेज़, GOLEM की तुलना में 96% तेज़ और DAGMA की तुलना में 93% तेज़ है।
सटीकता: TriOpt विभिन्न ग्राफ प्रकारों (Erdős–Rényi, Scale-Free) और शोर वितरण (Gaussian, Gumbel, Exponential) में तुलनीय या बेहतर सटीकता (Normalized SHD, F1 Score, और AID द्वारा मापा गया) बनाए रखता है।
मजबूती (Robustness):
- जब रैखिकता की धारणा का उल्लंघन होता है (नॉन-लीनियर डेटा के साथ मिसस्पेसिफाइड रिजीम), तब भी TriOpt मजबूत रहता है और नॉन-लीनियर सेटिंग्स में लीनियर बेसलाइन्स से बेहतर प्रदर्शन करता है।
- विधि व्यवस्था त्रुटियों (जैसे, एडजसेंट स्वैप्स, ब्लॉक रिवर्सल्स) के प्रति अत्यधिक मजबूत है, लेकिन संरचनात्मक रूप से महत्वपूर्ण त्रुटियों (जैसे, एंसेस्टर स्वैप्स, हब स्वैप्स) के साथ इसका प्रदर्शन गिर जाता है, जो सैद्धांतिक अपेक्षाओं के अनुरूप है।
एब्लेशन अध्ययन (Ablation Studies):
- लीनियर कर्नल और शेरमन-मोरिसन डाउनडेट का उपयोग CaPS की तुलना में मेमोरी उपयोग और रनटाइम को काफी कम करता है, जिससे TriOpt उन आयामों पर चल पाता है जहाँ CaPS आउट-ऑफ-मेमोरी एरर के कारण विफल हो जाता है।
- अपर-ट्रायंगुलर ऑप्टिमाइज़ेशन चरण CAM प्रूनिंग की तुलना में काफी तेज़ (50 नोड्स पर 664 गुना तक) और अधिक सटीक है।

महत्व और दावे

पेपर का दावा है कि TriOpt उच्च-आयामी सेटिंग्स के लिए Causal Discovery को नाटकीय रूप से अधिक स्केलेबल बनाने की दिशा में एक महत्वपूर्ण कदम है। कर्नल पुनर्गणना के कम्प्यूटेशनल ओवरहेड और अचकलीयता बाधाओं की गैर-कन्वेक्सिटी को हटाकर, TriOpt उन समस्याओं के लिए कॉज़ल डिस्कवरी के अनुप्रयोग को सक्षम बनाता है जिन्हें पहले कम्प्यूटेशनल रूप से अव्यवहार्य माना जाता था।

लेखक उल्लेख करते हैं कि हालांकि फ्रेमवर्क रैखिक संबंधों को मानता है, यह कई वास्तविक दुनिया की सेटिंग्स में अच्छा अनुमान प्रदान करता है और नॉन-लिनियैरिटी की उपस्थिति में भी मजबूत रहता है। एक स्वीकार की गई सीमा विशिष्ट स्क्यूड नॉइज़ डिस्ट्रीब्यूशंस (Exponential, Gumbel) के तहत शेरमन-मोरिसन डाउनडेट की संभावित संख्यात्मक अस्थिरता (numerical instability) है, जिसे आवधिक पुन: व्युत्क्रमण रणनीतियों (periodic re-inversion strategies) द्वारा कम किया जाता है। यह कार्य सुझाव देता है कि TriOpt रैखिक कारण खोज के लिए एक व्यावहारिक, स्केलेबल समाधान प्रदान करता है जो कम्प्यूटेशनल दक्षता और सैद्धांतिक कठोरता एवं अनुभवजन्य सटीकता के बीच संतुलन बनाता है।