Learning Causal Structure of Time Series using Best Order Score Search

यहाँ इरेन गेमा कैस्टिलो मान्सिला और उर्मी निनाद के शोध पत्र "Learning Causal Structure of Time Series using Best Order Score Search" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र बहुभिन्नरूपी (multivariate) टाइम सीरीज़ डेटा से कारण संरचना सीखने (causal structure learning) की चुनौती को संबोधित करता है। जबकि स्थिर (i.i.d.) डेटा के लिए कारण खोज (causal discovery) अच्छी तरह स्थापित है, टाइम सीरीज़ परिवेश महत्वपूर्ण कठिनाइयाँ पेश करता है:

• अस्थायी निर्भरता (Temporal Dependence): अवलोकन स्वतंत्र और समान रूप से वितरित (i.i.d.) नहीं होते हैं, जो कई सांख्यिकीय प्रक्रियाओं के लिए मानक मान्यताओं का उल्लंघन करते हैं।
• जटिलता: खोज स्थान (search space) समकालीन संबंधों (एक ही समय अंतराल पर चर) और लैग्ड संबंधों (पिछले समय अंतराल पर चर) दोनों को शामिल करता है।
• मौजूदा विधियों की सीमाएँ:
  • प्रतिबंध-आधारित विधियाँ (Constraint-based methods) (जैसे PCMCI+): ये सशर्त स्वतंत्रता (CI) परीक्षणों पर निर्भर करती हैं, जो मजबूत ऑटोकोरिलेशन और नमूना निर्भरता के कारण टाइम सीरीज़ में गलत अंशांकन (ill-calibrated) हो सकती हैं।
  • स्कोर-आधारित विधियाँ (Score-based methods) (जैसे GES, NOTEARS): ये स्केलेबिलिटी (scalability) में संघर्ष करती हैं या गतिशील सेटिंग के लिए विशिष्ट सैद्धांतिक गारंटी की कमी रखती हैं।

लेखक एक ऐसा स्कोर-आधारित कारण खोज तरीका विकसित करने का लक्ष्य रखते हैं जो विशेष रूप से टाइम सीरीज़ के लिए हो, जो स्केलेबिलिटी बनाए रखे, उच्च ऑटोकोरिलेशन को प्रभावी ढंग से संभाल सके, और शुद्धता के लिए सैद्धांतिक गारंटी प्रदान करे।

2. कार्यप्रणाली: TS-BOSS

लेखक TS-BOSS (Time Series - Best Order Score Search) प्रस्तावित करते हैं, जो स्थिर BOSS एल्गोरिदम (Andrews et al., 2023) का एक विस्तार है। TS-BOSS, Grow-Shrink Trees (GSTs) के माध्यम से कुशल कैशिंग (caching) के साथ क्रमपरिवर्तन-आधारित खोज (permutation-based search) को जोड़ता है।

टाइम सीरीज़ के लिए मुख्य अनुकूलन

1. विंडो कॉज़ल ग्राफ ($G_W$):

   • अनंत टाइम सीरीज़ ग्राफ को सीधे सीखने के बजाय, TS-BOSS एक विंडो कॉज़ल ग्राफ को लक्षित करता है।
   • यह एक अधिकतम समय अंतराल $\tau_{max}$ को मानता है। टाइम सीरीज़ को एक विंडो $W = [t-\tau_{max}, t]$ में "अनरोल" किया जाता है।
   • स्थिरता (Stationarity) की धारणा के तहत, इस परिमित विंडो ग्राफ की संरचना को सीखना पूरे टाइम सीरीज़ कॉज़ल ग्राफ (ts-DAG) के पुनर्निर्माण की अनुमति देता है।

2. प्रतिबंधित क्रमपरिवर्तन खोज (Restricted Permutation Search):

   • अस्थायी क्रम बाधा (Temporal Ordering Constraint): क्रमपरिवर्तन (permutations) को समय क्रम का सम्मान करना चाहिए। लैग्ड चर ($X_{t-\tau}$) को हमेशा समकालीन चरों ($X_t$) से पहले आना चाहिए।
   • खोज स्थान में कमी: क्रमपरिवर्तन खोज केवल समकालीन चरों ($X_t$) तक ही सीमित है। लैग्ड चरों को निश्चित पूर्ववर्ती (पैरेंट उम्मीदवार) माना जाता है जिन्हें वर्तमान समय स्लाइस के सापेक्ष पुनर्व्यवस्थित नहीं किया जा सकता है।

3. दो-चरणीय एल्गोरिदम:

   • चरण 1 (क्रमपरिवर्तन खोज और Grow-Shrink):
     • समकालीन चरों के सर्वोत्तम क्रमपरिवर्तन को पुनरावृत्ति से खोजता है।
     • जब चरों को पैरेंट सेटों में जोड़ा या हटाया जाता है, तो गणना को दोहराने से बचने के लिए Grow-Shrink Trees (GSTs) का उपयोग करके मध्यवर्ती स्कोर गणना को कैश करता है।
     • इष्टतम क्रमपरिवर्तन के आधार पर एक TS-DAG (Time Series Directed Acyclic Graph) का निर्माण करता है।
   • चरण 2 (TS-BES - Backward Equivalence Search):
     • यह उन किनारों (edges) को हटाने के लिए एक बैकवर्ड खोज लागू करता है जो स्कोर में सुधार नहीं करते हैं, जिससे यह सुनिश्चित होता है कि परिणामी ग्राफ डेटा का सबसे न्यूनतम प्रतिनिधित्व (Markov Equivalent Class) है।

4. स्कोरिंग (Scoring):

   • यह मॉडल की उपयुक्तता (goodness-of-fit) और मॉडल जटिलता के बीच संतुलन बनाने के लिए बेयसियन सूचना मानदंड (BIC) का उपयोग करता है।

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

सैद्धांतिक योगदान

• शुद्धता गारंटी (Soundness Guarantees): लेखक यह स्थापित करने के लिए सैद्धांतिक प्रमाण (Theorems 5, 6, और 7) प्रदान करते हैं कि TS-BOSS बड़े नमूना सीमा (large sample limit) में सुदृढ़ (sound) है।
  • वे सिद्ध करते हैं कि क्रमपरिवर्तन-प्रेरित विंडो ग्राफ विंडो मार्कोव प्रॉपर्टी और विंडो सबग्राफ मिनिमल को संतुष्ट करता है।
  • वे स्पारसेस्ट क्रमपरिवर्तन (sparsest permutations) के संबंध में शास्त्रीय परिणामों (Verma & Pearl, 1990; Raskutti & Uhler, 2018) को गतिशील (टाइम सीरीज़) सेटिंग में विस्तारित करते हैं।
• मान्यताएँ (Assumptions): यह विधि मानक मान्यताओं पर निर्भर करती है: टाइम सीरीज़ लोकल मार्कोव प्रॉपर्टी, फेथफुलनेस (Faithfulness), कॉज़ल सफिशिएंसी (कोई अज्ञात कन्फाउंडर नहीं), स्थिरता (Stationarity), और एक ज्ञात परिमित अधिकतम समय अंतराल।

एल्गोरिथमिक योगदान

• TS-BOSS एल्गोरिदम: एक नवीन अनुकूलन जो दक्षता के लिए GSTs का लाभ उठाते हुए क्रमपरिवर्तन-आधारित खोज के भीतर अस्थायी बाधाओं को लागू करता है।
• ऑटोकोरिलेशन को संभालना: इसे विशेष रूप से उच्च-ऑटोकोरिलेशन वाले शासन (regimes) में प्रभावी रहने के लिए डिज़ाइन किया गया है जहाँ प्रतिबंध-आधारित विधियाँ अक्सर विफल हो जाती हैं क्योंकि वहां सशर्त स्वतंत्रता परीक्षणों का अंशांकन कठिन होता है।

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

लेखकों ने बहुभिन्नरूपी रैखिक टाइम-सीरीज़ SCMs से उत्पन्न सिंथेटिक डेटा पर TS-BOSS का मूल्यांकन किया, और इसकी तुलना निम्नलिखित से की:

1. TS-BOSS (i.i.d.): एक बेसलाइन जहाँ एल्गोरिदम के मूल तर्क का परीक्षण करने के लिए डेटा को स्वतंत्र रूप से सैंपल किया जाता है ताकि अस्थायी निर्भरता का प्रभाव न हो।
2. PCMCI+: टाइम सीरीज़ के लिए एक अत्याधुनिक प्रतिबंध-आधारित विधि।

मुख्य निष्कर्ष:

• उच्च ऑटोकोरिलेशन शासन (High Autocorrelation Regime): उच्च ऑटोकोरिलेशन होने पर TS-BOSS, एडजसेंसी रिकॉल (Adjacency Recall) के मामले में PCMCI+ से काफी बेहतर प्रदर्शन करता है। PCMCI+ इन शासनों में किनारों (edges) का पता लगाने में संघर्ष करता है, जबकि TS-BOSS स्थिर रहता है।
• परिशुद्धता बनाम रिकॉल (Precision vs. Recall): जबकि PCMCI+ अक्सर थोड़ी उच्च परिशुद्धता (कम फाल्स पॉजिटिव) प्राप्त करता है, TS-BOSS तुलनीय परिशुद्धता स्तरों पर लगातार उच्च रिकॉल (कम फाल्स नेगेटिव) प्राप्त करता है।
• स्केलेबिलिटी (Scalability): TS-BOSS, PCMCI+ की तुलना में काफी तेज़ है, विशेष रूप से जैसे-जैसे नोड्स ($N$) की संख्या और ग्राफ घनत्व बढ़ता है। क्रमपरिवर्तन खोज, प्रतिबंध-आधारित विधियों द्वारा आवश्यक सशर्त स्वतंत्रता परीक्षणों की घातीय वृद्धि की तुलना में अधिक अनुकूल रूप से स्केल करती है।
• नमूना आकार (Sample Size): प्रदर्शन बड़े नमूना आकारों ($T$) के साथ बेहतर होता है, लेकिन TS-BOSS मध्यम नमूना आकारों के साथ भी रिकॉल में अपना लाभ बनाए रखता है।

5. महत्व और प्रभाव

• सिद्धांत और व्यवहार के बीच सेतु: यह शोध पत्र स्थिर सेटिंग्स से गतिशील टाइम सीरीज़ तक स्पार्सिटी-आधारित, क्रमपरिवर्तन-संचालित कारण शिक्षण सिद्धांत को विस्तारित करने के लिए एक व्यवस्थित सेतु प्रदान करता है।
• CI परीक्षणों का विकल्प: यह प्रदर्शित करता है कि क्रमपरिवर्तन-आधारित स्कोर खोज, टाइम सीरीज़ के लिए एक व्यवहार्य और अक्सर बेहतर विकल्प है (जो CI परीक्षणों पर निर्भर हैं), विशेष रूप से जब डेटा में मजबूत अस्थायी निर्भरता होती है।
• स्केलेबिलिटी: Grow-Shrink पेड़ों का उपयोग करके और क्रमपरिवर्तन स्थान को समकालीन चरों तक सीमित करके, TS-BOSS उच्च-आयामी टाइम सीरीज़ कारण खोज के लिए एक स्केलेबल समाधान प्रदान करता है, जो न्यूरोसाइंस, अर्थशास्त्र और अर्थ प्रणाली विज्ञान जैसे क्षेत्रों में एक महत्वपूर्ण आवश्यकता है।
• भविष्य की दिशाएँ: यह कार्य स्लाइडिंग-विंडो सेटिंग्स (गैर-i.i.d. डेटा) में स्कोर निरंतरता (score consistency) के संबंध में और अधिक सैद्धांतिक गारंटी की आवश्यकता को रेखांकित करता है और सुझाव देता है कि क्रमपरिवर्तन-आधारित विधियाँ बड़े पैमाने की प्रणालियों के लिए बेहतर समानांतरकरण (parallelization) के अवसर प्रदान कर सकती हैं।

संक्षेप में, TS-BOSS टाइम सीरीज़ कारण खोज में एक महत्वपूर्ण प्रगति का प्रतिनिधित्व करता है, जो एक मजबूत, स्केलेबल और सैद्धांतिक रूप से सुदृढ़ दृष्टिकोण प्रदान करता है जो उन उच्च-ऑटोकोरिलेशन वातावरणों में उत्कृष्ट है जहाँ पारंपरिक विधियाँ विफल हो जाती हैं।