📊 statistics

On Observation Time for Recovering Latent Hawkes Networks

यह शोध पत्र यह स्थापित करता है कि विरल (sparse), दुर्बल रूप से परस्पर क्रिया करने वाले स्थिर हॉक्स प्रक्रियाओं (Hawkes processes) के लिए, $d$ संस्थाओं के बीच अंतर्निहित गुप्त नेटवर्क को सटीक रूप से पुन: प्राप्त करने के लिए $\log d$ के क्रम का अवलोकन समय आवश्यक और पर्याप्त दोनों है, जिसे एक नवीन दो-चरणीय अनुमानक (two-stage estimator) और फानो की असमानता (Fano's inequality) एवं जैकोड के गिरसानोव सूत्र (Jacod's Girsanov formula) से प्राप्त निचली सीमा के माध्यम से प्राप्त किया गया है।

मूल लेखक: Jonas Linkerhägner, Michele Bortolasi, Lorenzo Baldassari, Maarten V. de Hoop, Ivan Dokmanić

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

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

CC BY 4.0

मूल लेखक: Jonas Linkerhägner, Michele Bortolasi, Lorenzo Baldassari, Maarten V. de Hoop, Ivan Dokmanić

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

कल्पना कीजिए कि आप एक जासूस हैं जो हजारों लोगों वाले एक विशाल, अराजक ग्रुप चैट में यह पता लगाने की कोशिश कर रहे हैं कि कौन किसे मैसेज भेज रहा है। आप फोन की स्क्रीन नहीं देख सकते और न ही सीधे मैसेज पढ़ सकते हैं। आप केवल एक लॉग देख सकते हैं कि लोगों ने मैसेज कब भेजे।

आपका लक्ष्य उस छिपे हुए "दोस्ती के नक्शे" (नेटवर्क) को फिर से बनाना है जो बताता है कि कौन किसे प्रभावित करता है। यदि व्यक्ति A एक मैसेज भेजता है, तो क्या इससे संभावना बढ़ जाती है कि व्यक्ति B एक सेकंड बाद मैसेज भेजेगा?

यह शोध पत्र इस रहस्य के एक बहुत ही विशिष्ट संस्करण को सुलझाता है जिसे हॉक्स प्रोसेस (Hawkes Process) नामक एक गणितीय मॉडल का उपयोग करके समझा जाता है। इसे "संक्रामक घटनाओं" का वर्णन करने के तरीके के रूप में सोचें: जैसे एक भूकंप के बाद आफ्टरशॉक्स (झटके) आते हैं, शेयर बाजार में गिरावट के बाद घबराहट में बिकवाली होती है, या एक वायरल ट्वीट रिट्वीट की बाढ़ ला देता है।

यहाँ मुख्य प्रश्न जो लेखक पूछते हैं वह यह है: इस ग्रुप चैट को समझने के लिए आपको कितना समय तक देखना होगा ताकि आप 100% निश्चित हो सकें कि आपने पूरा दोस्ती का नक्शा समझ लिया है?

बड़ी खोज: समय बनाम आकार

लेखक एक आश्चर्यजनक और सुंदर नियम सिद्ध करते हैं: आपको कितना समय देखने की आवश्यकता है, यह केवल इसलिए बहुत अधिक नहीं होना चाहिए क्योंकि समूह बड़ा हो गया है।

यदि आपके पास 10 लोग हैं, तो आपको नक्शा समझने के लिए एक निश्चित समय चाहिए।
यदि आपके पास 1,000 लोग हैं, तो आपको 100 गुना अधिक समय की आवश्यकता नहीं है। आपको केवल थोड़ा सा अधिक समय चाहिए।
यदि आपके पास 1,000,000 लोग हैं, तो भी आपको 1,000 लोगों की तुलना में बहुत कम अतिरिक्त समय चाहिए।

गणितीय रूप से, वे सिद्ध करते हैं कि आवश्यक अवलोकन समय (observation time) लोगों की संख्या के साथ लॉगारिदमिक (logarithmically) रूप से बढ़ता है। सरल शब्दों में: समय $\approx$ नेटवर्क के आकार का लॉग (Logarithm)।

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

उन्होंने इसे कैसे हल किया (दो चरणों वाला जासूसी कार्य)

यह पेपर केवल यह नहीं कहता कि "यह संभव है"; वे इसे करने के लिए एक विशिष्ट विधि बनाते हैं। वे इसे टू-स्टेज एस्टीमेटर (two-stage estimator) कहते हैं।

चरण 1: "स्क्रीनिंग" (एक कच्चा मसौदा)
कल्पना कीजिए कि आपके पास 1,000 संदिग्धों की सूची है। आप तुरंत उन सभी का गहराई से इंटरव्यू नहीं ले सकते। इसलिए, आप एक त्वरित स्कैन करते हैं।

आप देखते हैं कि किसी व्यक्ति द्वारा मैसेज भेजने के ठीक पहले कौन सक्रिय था।
आप पूछते हैं: "इस घटना से ठीक पहले और कौन सक्रिय था?"
आप शीर्ष 10 लोगों को रखते हैं जो सबसे अधिक संभावित कारण लगते हैं और बाकी 990 को हटा देते हैं।
ट्रिक: लेखक दिखाते हैं कि भले ही आप डेटा को काट दें (अत्यधिक शोर वाले संदेशों को अनदेखा करना) और उसे बिन (chunks में बांटना) कर दें, यह त्वरित स्कैन इतना स्मार्ट है कि वास्तविक दोषियों को सूची में बनाए रखता है। यह एक छलनी की तरह है जो सोने को पकड़ लेती है लेकिन रेत को नीचे गिरने देती है।

चरण 2: "रिफाइनमेंट" (गहन जांच)
अब आपके पास केवल 10 संदिग्ध बचे हैं। अब आप इस छोटे समूह पर गहन, विस्तृत विश्लेषण कर सकते हैं।

आप इस छोटे समूह पर एक सटीक सांख्यिकीय परीक्षण (Least Squares) चलाते हैं।
आप संख्याओं की जांच करते हैं कि वास्तव में किसने किसे प्रभावित किया।
क्योंकि समूह बहुत छोटा है, आप परिणाम के बारे में गणितीय रूप से निश्चित हो सकते हैं।

यह कठिन क्यों है?

लेखक बताते हैं कि यह जितना दिखता है उससे कहीं अधिक कठिन है क्योंकि इसमें "अप्रत्यक्ष प्रतिध्वनि" (Indirect Echoes) का प्रभाव होता है।

कल्पना कीजिए कि व्यक्ति A, व्यक्ति B को टेक्स्ट करता है, और व्यक्ति B, व्यक्ति C को टेक्स्ट करता है।

प्रत्यक्ष लिंक: A $\to$ B.
प्रत्यक्ष लिंक: B $\to$ C.
भ्रम (Illusion): A अप्रत्यक्ष रूप से C को भी प्रभावित करता हुआ प्रतीत होता है, भले ही उन्होंने सीधे बात न की हो। A के मैसेज ने B को कार्य करने के लिए प्रेरित किया, जिससे C ने कार्य किया।

एक शोर भरे, व्यस्त नेटवर्क में, ये "प्रतिध्वनियाँ" आपको यह सोचने के लिए धोखा दे सकती हैं कि A और C दोस्त हैं, जबकि वे वास्तव में नहीं हैं। लेखक सिद्ध करते हैं कि यदि इंटरैक्शन कमजोर (लोग एक मैसेज से बहुत अधिक उत्तेजित नहीं होते) और विरल (sparse) (हर कोई केवल कुछ ही लोगों से बात करता है) हैं, तो आप वास्तविक प्रत्यक्ष मित्रों को नकली अप्रत्यक्ष मित्रों से अलग कर सकते हैं।

"असंभव" सीमा

यह पेपर दूसरे पक्ष को भी सिद्ध करता है: आप इसे इससे तेज़ नहीं कर सकते।

उन्होंने फानो की असमानता (Fano's Inequality) नामक एक गणितीय उपकरण का उपयोग किया (इसे "न्यूनतम सूचना" नियम के रूप में सोचें) यह दिखाने के लिए कि यदि आप ग्रुप चैट को बहुत जल्दी देखना बंद कर देते हैं, तो डेटा में पर्याप्त संकेत नहीं होते हैं। चाहे आपका कंप्यूटर कितना भी स्मार्ट हो या आपका एल्गोरिदम कितना भी शानदार, यदि आपने पर्याप्त समय तक नहीं देखा है, तो विभिन्न संभावित दोस्ती के नक्शे सांख्यिकीय रूप से एक जैसे ही दिखेंगे। आप अंधेरे में अनुमान लगा रहे होंगे।

निष्कर्ष

यह शोध पत्र नेटवर्क रिकवरी के लिए एक सैद्धांतिक "स्पीड लिमिट" प्रदान करता है।

अच्छी खबर: आपको किसी नेटवर्क को समझने के लिए वर्षों तक देखने की आवश्यकता नहीं है। एक अपेक्षाकृत छोटा अवलोकन समय (जो आकार के लॉग के साथ स्केल होता है) पर्याप्त है।
बुरी खबर: यदि आप उस समय से कम समय में ऐसा करने की कोशिश करते हैं, तो सही होना गणितीय रूप से असंभव है।

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

समस्या विवरण
यह शोध पत्र बहुभिन्नरूपी हॉक्स प्रक्रिया (multivariate Hawkes process) के घटना-आधारित अवलोकनों से उसके अंतर्निहित अंतःक्रिया नेटवर्क (latent interaction network) के अनुमान लगाने की मौलिक सांख्यिकीय समस्या को संबोधित करता है। विशेष रूप से, यह अंतःक्रिया मैट्रिक्स $\Theta$ की सटीक सपोर्ट रिकवरी (exact support recovery) प्राप्त करने के लिए आवश्यक अवलोकन समय $T$ और अंतःक्रिया करने वाली संस्थाओं (नोड्स) की संख्या $d$ के बीच स्केलिंग संबंध की जांच करता है। लेखक एक ऐसे परिदृश्य पर ध्यान केंद्रित करते हैं जहाँ नेटवर्क विरल (sparse) है (प्रत्येक नोड के पास अधिकतम $k \ll d$ पैरेंट हैं) और अंतःक्रियाएं कमजोर हैं, जो भूकंप के बाद के झटकों (aftershocks), उच्च-आवृत्ति व्यापार (high-frequency trading), न्यूरोनल स्पाइक ट्रेनों, और महामारी प्रसार जैसी घटनाओं के लिए प्रासंगिक है।

कार्यप्रणाली
लेखक एक ज्ञात क्षय दर (decay rate) $\beta$ वाले $d$ -आयामी एक्सपोनेंशियल हॉक्स प्रक्रिया का उपयोग करके एक सैद्धांतिक ढांचा स्थापित करते हैं। अंतःक्रिया मैट्रिक्स को $\Theta = \alpha B$ के रूप में मॉडल किया गया है, जहाँ $B$ एक विरल गैर-ऋणात्मक मैट्रिक्स है जिसके प्रविष्टियाँ (entries) सीमित हैं, और $\alpha$ कपलिंग स्ट्रेंथ (coupling strength) को नियंत्रित करता है। विश्लेषण एक स्थिर अवलोकन विंडो $[0, T]$ को मानता है और $X(0)$ को अवलोकन योग्य (एक मानक इनिशियलाइजेशन धारणा) मानता है।

परिणामों को प्राप्त करने के लिए, शोध पत्र दो अलग-अलग कार्यप्रणाली दृष्टिकोणों का उपयोग करता है:

ऊपरी सीमा (उपलब्धता/Achievability): लेखक नेटवर्क को रिकवर करने के लिए एक दो-चरणीय एस्टिमेटर (estimator) का निर्माण करते हैं।
- स्क्रीनिंग चरण (Screening Stage): एस्टिमेटर क्लिप्ड और बिन्ड (clipped and binned) घटना डेटा का उपयोग करके, उम्मीदवार पैरेंट नोड्स और लक्षित नोड की भविष्य की घटनाओं के बीच अनुभवजन्य सहप्रसरण स्कोर (empirical covariance scores) की गणना करता है। यह चरण $d$ संभावित पैरेंट्स को $m \geq k$ आकार के एक उम्मीदवार सेट तक फ़िल्टर करता है, यह सुनिश्चित करते हुए कि वास्तविक सपोर्ट इस सेट के भीतर है (sure screening)।
- रिफाइनमेंट चरण (Refinement Stage): स्क्रीन किए गए उम्मीदवार सेट पर एक स्थानीय ऑर्डिनरी लीस्ट स्क्वायर्स (OLS) रिग्रेशन किया जाता है। अनुमानित गुणांकों को अप्रत्यक्ष उत्तेजना कैस्केड (indirect excitation cascades) के कारण होने वाले स्प्यूरियस कोरिलेशन (spurious correlations) से वास्तविक किनारों (edges) को अलग करने के लिए थ्रेशोल्ड किया जाता है।
- विश्लेषण: प्रमाण हॉक्स प्रक्रियाओं के पॉइसन क्लस्टर प्रतिनिधित्व (Poisson cluster representation) पर निर्भर करता है ताकि एस्टिमेटर में उपयोग किए जाने वाले डिपेंडेंट ब्लॉक एवरेज के लिए कंसंट्रेशन बाउंड्स (concentration bounds) प्राप्त किए जा सकें। यह लेखकों को यह दिखाने की अनुमति देता है कि अनुभवजन्य सांख्यिकी उच्च प्रायिकता के साथ अपने सैद्धांतिक मानों के आसपास केंद्रित होती है।
निचली सीमा (असंभवता/Impossibility): लेखक एक सूचना-सैद्धांतिक निचली सीमा (information-theoretic lower bound) स्थापित करके यह सिद्ध करते हैं कि लॉगरिदमिक स्केलिंग इष्टतम है।
- वे समस्या को नेटवर्कों के एक विशिष्ट उपवर्ग तक सीमित करते हैं जहाँ केवल एक लक्षित नोड के $k$ अज्ञात पैरेंट हैं, जबकि अन्य सभी नोड्स स्वतंत्र हैं।
- फानो की असमानता (Fano's inequality) का उपयोग करते हुए, वे किसी भी एस्टिमेटर की त्रुटि प्रायिकता को अज्ञात सपोर्ट और अवलोकनों के बीच म्यूचुअल इंफॉर्मेशन (mutual information) से जोड़ते हैं।
- म्यूचुअल इंफॉर्मेशन को एक विशिष्ट सपोर्ट के तहत देखे गए प्रोसेस के कानून और बिना किसी अंतःक्रिया वाले संदर्भ कानून के बीच कुलबैक-लीब्लर (KL) डाइवर्जेंस का उपयोग करके बाउंड किया जाता है। यह गणना पॉइंट प्रोसेस के लिए जैकोड के गिरसनोव फॉर्मूला (Jacod's Girsanov formula) का उपयोग करती है ताकि मेजर के परिवर्तन (change of measure) को संभाला जा सके।

प्रमुख परिणाम
शोध पत्र सिद्ध करता है कि विरल, कमजोर अंतःक्रियाओं वाले स्थिर हॉक्स प्रक्रियाओं के एक वर्ग के लिए, सटीक नेटवर्क रिकवरी के लिए आवश्यक अवलोकन समय $T$ इस प्रकार स्केल करता है:
$T \asymp \log d$
विशेष रूप से:

प्रमेय 3.1 (ऊपरी सीमा): एक दो-चरणीय एस्टिमेटर मौजूद है जिससे यदि $T \geq C^* \log d$ , तो सटीक सपोर्ट रिकवरी की प्रायिकता कम से कम $1 - d^{-c^*}$ है। एस्टिमेटर वास्तविक पैरेंट्स को गैर-पैरेंट्स से एक "स्क्रीनिंग गैप" के माध्यम से अलग करके सफल होता है, जो क्लिपिंग और बिनिंग के तहत संरक्षित रहता है।
प्रमेय 4.1 (निचली सीमा): किसी भी एस्टिमेटर के लिए, यदि $T \leq c \log d$ (पर्याप्त छोटे स्थिरांक $c$ के लिए), तो त्रुटि की प्रायिकता शून्य से दूर (bounded away from zero) रहती है। इसका तात्पर्य है कि कोई भी एल्गोरिदम, चाहे उसकी कम्प्यूटेशनल लागत कुछ भी हो, सब-लॉगारिदमिक समय में उच्च प्रायिकता के साथ सटीक रिकवरी प्राप्त नहीं कर सकता है।

महत्व और दावे
शोध पत्र यह दावा करता है कि यह हॉक्स प्रक्रियाओं में सटीक नेटवर्क रिकवरी (समय के संदर्भ में) के लिए सैंपल कॉम्प्लेक्सिटी (sample complexity) को चरित्रित करने वाला पहला सैद्धांतिक परिणाम प्रदान करता है। लेखक इस बात पर जोर देते हैं कि $d$ पर लॉगरिदमिक निर्भरता समस्या के लिए आंतरिक है, जो $d$ उम्मीदवारों के बीच एक विरल पैरेंट सेट की पहचान करने की कॉम्बिनेटोरियल लागत से प्रेरित है।

इस परिणाम को सक्षम करने वाले प्रमुख कारक शामिल हैं:

एक्सपोनेंशियल कर्नेल द्वारा प्रदान किया गया मार्कोव स्टेट रिप्रेजेंटेशन, जो तीव्रता की गतिशीलता (intensity dynamics) को सरल बनाता है।
स्टेट वेरिएबल के सापेक्ष तीव्रता की रैखिकता (linearity)।
कमजोर अंतःक्रिया की स्थिति (weak interaction condition), जो यह सुनिश्चित करती है कि अप्रत्यक्ष उत्तेजना कैस्केड प्रत्यक्ष पैरेंट्स से मिलने वाले सिग्नल को दबा न दें, जिससे वास्तविक और गलत किनारों के बीच अलगाव संभव हो पाता है।
स्थिरता (Stationarity), जो अवलोकन विंडो पर समान वितरण नियंत्रण प्रदान करती है।

लेखक उल्लेख करते हैं कि जबकि अनुभवजन्य कार्यों ने नेटवर्क इन्फरेंस के लिए लंबे समय से हॉक्स प्रक्रियाओं का उपयोग किया है, यह कार्य ऐसे सफल परिणामों को एक सैद्धांतिक आधार प्रदान करता है, यह प्रदर्शित करते हुए कि जब अवलोकन विंडो आयाम के साथ लॉगरिदमिक रूप से स्केल करती है, तो बड़े नेटवर्क आकार स्वाभाविक रूप से सटीक रिकवरी को बाधित नहीं करते हैं। शोध पत्र भविष्य की दिशाओं का सुझाव देते हुए समाप्त होता है, जैसे कि हस्ताक्षरित या निरोधात्मक (inhibitory) अंतःक्रियाओं, अज्ञात क्षय दरों, या स्थानिक रूप से संरचित नेटवर्कों तक सिद्धांत का विस्तार करना, लेकिन यह दावा नहीं करता है कि ये विस्तार वर्तमान में हल किए गए हैं।

बड़ी खोज: समय बनाम आकार

उन्होंने इसे कैसे हल किया (दो चरणों वाला जासूसी कार्य)

यह कठिन क्यों है?

"असंभव" सीमा

निष्कर्ष

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