📊 statistics

GraphGP: Scalable Gaussian Processes with Vecchia's Approximation

GraphGP एक स्केलेबल, GPU-त्वरित एल्गोरिदम है जो वेचिया (Vecchia) के सन्निकटन और एक नवीन बिट-रिवर्स्ड k-d ट्री ऑर्डरिंग का लाभ उठाता है ताकि लगभग एक अरब मापदंडों के लिए रैखिक समय और मेमोरी जटिलता के साथ कुशल गॉसियन प्रोसेस इन्फरेंस को सक्षम किया जा सके।

मूल लेखक: Benjamin Dodge, Philipp Frank, Susan E. Clark

प्रकाशित 2026-06-11

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

CC BY 4.0

मूल लेखक: Benjamin Dodge, Philipp Frank, Susan E. Clark

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

कल्पना कीजिए कि आप ब्रह्मांड का एक विशाल, विस्तृत भित्तिचित्र (mural) बनाने की कोशिश कर रहे हैं, लेकिन एक दीवार के बजाय, आपके पास तारों और गैस के बादलों का प्रतिनिधित्व करने वाले अरबों छोटे, बिखरे हुए बिंदु हैं। आप यह अनुमान लगाना चाहते हैं कि इन बिंदुओं के बीच का स्थान कैसा दिखता है, और खाली जगहों को एक सुचारू, निरंतर चित्र से भरना चाहते हैं। गौसियन प्रोसेस (Gaussian Processes - GPs) यही करते हैं: वे किसी भी स्थान पर किसी चीज़ का मान बताने के लिए पास के ज्ञात बिंदुओं के आधार पर अनुमान लगाने का एक गणितीय उपकरण हैं।

हालाँकि, एक बहुत बड़ी समस्या है। अरबों बिंदुओं के लिए यह गणित करना एक ऐसे पहेली को हल करने जैसा है जहाँ हर एक टुकड़ा दूसरे से जुड़ा हुआ है। कंप्यूटर अभिभूत हो जाता है, समय और मेमोरी खत्म होने लगती है, ठीक वैसे ही जैसे एक लाइब्रेरियन हर किताब को लाइब्रेरी की हर दूसरी किताब के साथ एक साथ क्रॉस-रेफरेंस करने की कोशिश करता है।

GraphGP एक नया टूल है जो इस "अभिभूत लाइब्रेरियन" की समस्या को हल करता है। यह कैसे काम करता है, इसके लिए सरल उपमाओं का उपयोग किया गया है:

1. "पड़ोसी" का शॉर्टकट (Vecchia's Approximation)

हर एक बिंदु को दूसरे बिंदु से बात करने के लिए कहने के बजाय (जो अरबों बिंदुओं के लिए असंभव है), GraphGP एक चतुर ट्रिक का उपयोग करता है जिसे Vecchia's Approximation कहा जाता है।

कल्पना कीजिए कि आप एक कहानी लिख रहे हैं। अगली पंक्ति लिखने के लिए आपको अपने द्वारा लिखी गई हर एक पंक्ति को याद रखने की आवश्यकता नहीं है, बल्कि आपको केवल पिछली कुछ पंक्तियों को याद रखने की आवश्यकता है। GraphGP कुछ ऐसा ही करता है: एक नए बिंदु पर मान का पता लगाने के लिए, यह केवल इसके निकटतम पड़ोसियों (मान लीजिए 16 सबसे करीबी बिंदुओं) को देखता है। यह बाकी सब को अनदेखा कर देता है। यह एक विशाल, असंभव गणना को एक प्रबंधनीय कार्य में बदल देता है, जैसे पूरी लाइब्रेरी को एक साथ पढ़ने के बजाय एक बार में एक किताब पढ़ना।

2. "स्मार्ट लाइन-अप" (The Ordering Problem)

यहाँ पेचीदा हिस्सा है: यदि आप बिंदुओं को किसी यादृच्छिक क्रम में, या केवल उनके निर्देशांकों (coordinates) के आधार पर प्रोसेस करते हैं, तो आप निर्भरताओं की एक लंबी श्रृंखला बना सकते हैं। कल्पना कीजिए कि लोगों की एक कतार है जहाँ व्यक्ति A को व्यक्ति B का इंतज़ार करना पड़ता है, जिसे व्यक्ति C का इंतज़ार करना पड़ता है, और इसी तरह। आप तब तक कुछ नहीं कर सकते जब तक कि पहला व्यक्ति समाप्त न हो जाए। यह धीमा है।

लेखकों ने बिंदुओं को व्यवस्थित करने का एक विशेष तरीका खोजा है, जिसे वे "Bit-Reversed k-d Tree Order" कहते हैं।

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

3. "सुपर-फास्ट फैक्ट्री" (CUDA Implementation)

पेपर ने इस टूल के लिए CUDA (एक ऐसी तकनीक जो कंप्यूटर को उनके ग्राफिक्स कार्ड, या GPUs, का भारी गणित के लिए उपयोग करने की अनुमति देती है) का उपयोग करके एक कस्टम इंजन भी बनाया है।

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

यह वास्तव में क्या कर सकता है?

पेपर के अनुसार, GraphGP निम्नलिखित के लिए बिल्डिंग ब्लॉक्स प्रदान करता है:

डेटा पॉइंट्स उत्पन्न करना (भित्तिचित्र बनाना)।
प्रक्रिया को उलटना/इनवर्ट करना (परिणाम से मूल स्थितियों का पता लगाना)।
संभाव्यता की गणना करना (हम इस भविष्यवाणी के बारे में कितने आश्वस्त हैं?)।
डेटा से सीखना (डॉट्स के साथ बेहतर तालमेल बिठाने के लिए नियमों को समायोजित करना)।

वास्तविक दुनिया का लक्ष्य

लेखक विशेष रूप से एक मुख्य लक्ष्य का उल्लेख करते हैं: इंटरस्टेलर मीडियम (Interstellar Medium) का मानचित्रण। इसका अर्थ है हमारी आकाशगंगा के बीच की गैस और धूल के 3D मानचित्र बनाना। पिछले तरीके तारों के असमान वितरण या डेटा बिंदुओं की विशाल संख्या के कारण संघर्ष कर रहे थे। GraphGP वैज्ञानिकों को बहुत कम मेमोरी के साथ और किसी भी आकार के डेटा वितरण पर उच्च-रिज़ॉल्यूशन वाले मानचित्र बनाने की अनुमति देता है।

संक्षेप में: GraphGP बड़े पैमाने पर जटिल गणित करने का एक नया तरीका है। यह डेटा को पुनर्व्यवस्थित करता है ताकि कंप्यूटर एक साथ कई चीजों पर काम कर सके, और यह स्थान बचाने के लिए ऑन-द-फ्लाई गणितीय उपकरण बनाता है। यह वैज्ञानिकों को एक ऐसे स्तर के विवरण और गति के साथ ब्रह्मांड का 3D मानचित्र बनाने की अनुमति देता है जो पहले असंभव था।

तकनीकी सारांश: GraphGP: वेकिया के सन्निकटन (Vecchia's Approximation) के साथ स्केलेबल गॉसियन प्रोसेस

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

गॉसियन प्रोसेस (GPs) स्थानिक मॉडलिंग और अनिश्चितता परिमाणन (uncertainty quantification) के लिए एक सिद्धांतवादी ढांचा प्रदान करते हैं, लेकिन उन्हें गंभीर स्केलेबिलिटी सीमाओं का सामना करना पड़ता है। मूल (Naive) कार्यान्वयन में $O(N^3)$ कम्प्यूटेशनल लागत और $O(N^2)$ मेमोरी आवश्यकताएं होती हैं, जो उन्हें लाखों या अरबों बिंदुओं वाले डेटासेट के लिए अव्यावहारिक बनाती हैं। जबकि मौजूदा विधियां आंशिक समाधान प्रदान करती हैं, उनमें महत्वपूर्ण ट्रेड-ऑफ (trade-offs) हैं:

इंड्यूसिंग-पॉइंट विधियां (Inducing-point methods): ये $O(NM^2)$ जटिलता को कम करती हैं लेकिन संघर्ष करती हैं जब इंड्यूसिंग चरों की संख्या $M$ को बड़ा रखना आवश्यक हो।
फास्ट फूरियर ट्रांसफॉर्म्स (FFTs): ये नियमित ग्रिड पर $O(N \log N)$ स्केलिंग प्राप्त करती हैं, लेकिन बड़े डायनेमिक रेंज वाले मनमाने बिंदु वितरण (arbitrary point distributions) पर इन्हें लागू करना कठिन है।
वेकिया का सन्निकटन (Vecchia's approximation): यह $O(Nk^3)$ स्केलिंग प्रदान करता है क्योंकि यह प्रत्येक बिंदु को केवल $k \ll N$ पूर्ववर्ती (preceding) बिंदुओं पर आधारित (condition) करता है, लेकिन मनमाने बिंदु वितरणों के लिए बड़े $N$ पर इसे कुशलतापूर्वक निष्पादित करना चुनौतीपूर्ण रहा है।
इटरेटिव चार्टेड रिफाइनमेंट (ICR): यह एकल GPU पर सैकड़ों मिलियन मापदंडों तक स्केल करता है, लेकिन यह बिंदुओं को एक पदानुक्रमित ग्रिड (hierarchical grid) तक सीमित रखता है, जिससे लचीलापन कम हो जाता है।

प्राथमिक चुनौती यह निर्धारित करना है कि ग्रिड-आधारित विधियों द्वारा प्राप्त स्केलेबिलिटी से समझौता किए बिना, मनमाने बिंदु वितरणों के लिए उपयुक्त कंडीशनिंग संबंधों को तेजी से कैसे निर्धारित किया जाए और परिणामी गणना को कैसे समानांतर (parallelize) किया जाए।

कार्यप्रणाली (Methodology)

GraphGP एक GPU एल्गोरिदम पेश करता है जो वेकिया के सन्निकटन के लचीलेपन को उच्च-प्रदर्शन वाले समानांतरकरण (parallelization) के साथ जोड़ता है। मुख्य कार्यप्रणाली दो मुख्य नवाचारों पर निर्भर करती है: एक नवीन बिंदु क्रम रणनीति (point ordering strategy) और एक कस्टम CUDA कार्यान्वयन।

1. वेकिया का सन्निकटन (Vecchia's Approximation)

एल्गोरिदम $N$ बिंदुओं के संयुक्त घनत्व (joint density) $p(v)$ को सशर्त संभावनाओं के उत्पाद के रूप में कारकित (factor) करता है:
$p(v) \approx \prod_{i=1}^{N} p(v_i | v_{c(i)})$
जहाँ $c(i)$ , $k$ पूर्ववर्ती कंडीशनिंग बिंदुओं का एक सेट है। सभी पिछले बिंदुओं का उपयोग करने के बजाय (जो सटीक होता लेकिन महंगा होता), GraphGP प्रत्येक बिंदु को पूर्ववर्ती बिंदुओं में से उसके $k$ निकटतम पड़ोसियों पर कंडीशन करता है। यह कंडीशनिंग मैट्रिसेस के आकार को $k \times k$ तक कम कर देता है, जिससे $O(Nk^3)$ समय और $O(Nk^2)$ मेमोरी जटिलता सक्षम होती है।

2. बिट-रिवर्स्ड $k$ -d ट्री ऑर्डरिंग (Bit-Reversed $k$ -d Tree Ordering)

वेकिया के सन्निकटन की दक्षता बिंदुओं के पीढ़ी क्रम (generation order) पर बहुत अधिक निर्भर करती है। मानक $k$ -d ट्री क्रम स्थानिक रूप से निकट बिंदुओं को समूहित करते हैं, जिससे लंबी डिपेंडेंसी चेन (dependency chains) बनती है जो समानांतरकरण में बाधा डालती हैं। GraphGP एक बिट-रिवर्स्ड ऑर्डरिंग प्रस्तावित करता है:

ट्री संरचना: बिंदुओं को एक लेफ्ट-बैलेंस्ड (left-balanced) $k$ -d ट्री में व्यवस्थित किया जाता है।
बिट-रिवर्सल परम्यूटेशन: पीढ़ी क्रम को इस तरह संशोधित किया जाता है कि प्रत्येक स्तर पर सभी लेफ्ट चिल्ड्रन (left children) को किसी भी राइट चिल्ड्रन (right children) से पहले डाला जाता है। यह प्रभावी रूप से स्थानिक रूप से निकट बिंदुओं को पीढ़ी अनुक्रम में दूर फैला देता है।
लाभ: यह ऑर्डरिंग सुनिश्चित करती है कि पीढ़ी अनुक्रम में क्रमिक बिंदु स्थानिक रूप से दूर हों, जिससे उनके सशर्त स्वतंत्र (conditionally independent) होने की संभावना बढ़ जाती है। फलस्वरूप, बिंदुओं के बड़े बैचों को समानांतर में जेनरेट किया जा सकता है।
बैच निर्माण: एल्गोरिदम पड़ोसी संबंधों द्वारा निहित निर्देशित अचक्रीय ग्राफ (directed acyclic graph - DAG) का विश्लेषण करता है ताकि प्रत्येक नोड की "डेप्थ" (रूट से सबसे लंबा पथ) की गणना की जा सके। समान डेप्थ वाले बिंदु सशर्त रूप से स्वतंत्र होते हैं और समानांतर में प्रोसेस किए जाते हैं। सटीकता सुनिश्चित करने और छोटे प्रारंभिक बैचों से बचने के लिए, पहले $n_0$ बिंदुओं को डेंस चोलेस्की फैक्टराइजेशन (dense Cholesky factorization) का उपयोग करके जेनरेट किया जाता है।

3. CUDA कार्यान्वयन और अनुकूलन (CUDA Implementation and Optimizations)

जबकि एक बेसलाइन कार्यान्वयन JAX में मौजूद है, GraphGP मेमोरी और प्रदर्शन बाधाओं को दूर करने के लिए एक कस्टम CUDA कार्यान्वयन का उपयोग करता है:

रजिस्टर-आधारित गणना (Register-Based Computation): चूंकि $k \times k$ कंडीशनिंग मैट्रिसेस छोटे ( $k \lesssim 64$ ) और अल्पकालिक होते हैं, इसलिए उन्हें ग्लोबल मेमोरी में आवंटित करने के बजाय सीधे GPU रजिस्टरों में ऑन-द-फ्लाई (on-the-fly) कंप्यूट किया जाता है। यह मेमोरी बैंडविड्थ सीमाओं से बचाता है।
इन-प्लेस ऑपरेशन्स (In-Place Operations): कार्यान्वयन इन-प्लेस मैट्रिक्स फैक्टराइजेशन और सॉल्व का उपयोग करता है, और मैट्रिसेस को लोअर-ट्राइएंगुलर फॉर्मेट में स्टोर करता है ताकि रजिस्टर के उपयोग को न्यूनतम किया जा सके।
डिफरेंशिएबिलिटी (Differentiability): बेयसियन इन्फरेंस और मॉडल फिटिंग का समर्थन करने के लिए, लेखकों ने चोलेस्की अपघटन डेरिवेटिव का उपयोग करके CUDA में फॉरवर्ड और बैकवर्ड डेरिवेटिव को लागू किया है। इन्हें कस्टम JAX प्रिमिटिव के रूप में पंजीकृत किया गया है, जिससे GraphGP बड़े डिफरेंशिएबल मॉडल्स के भीतर सहजता से कार्य कर पाता है।
समानांतर ग्राफ निर्माण: पड़ोसी खोज (neighbor search) के लिए समानांतर, सॉर्ट-आधारित GPU एल्गोरिदम का उपयोग किया जाता है जो कस्टम बिट-रिवर्स्ड ऑर्डर के लिए अनुकूलित हैं। डेप्थ अपडेट को सभी बिंदुओं पर पुनरावृत्ति (iteratively) के माध्यम से समानांतर में किया जाता है, जो कि इस अनुप्रयोग के विशिष्ट उथले (shallow) ग्राफ के लिए तेज़ है।

मुख्य योगदान (Key Contributions)

बिट-रिवर्स्ड $k$ -d ट्री ऑर्डरिंग: एक नवीन पीढ़ी क्रम जो ट्री संरचना के भीतर कुशल पड़ोसी खोज क्षमताओं को बनाए रखते हुए बैच समानांतरता (batch parallelism) को अधिकतम करता है।
डिफरेंशिएबल CUDA कार्यान्वयन: एक उच्च-प्रदर्शन, मेमोरी-कुशल कार्यान्वयन जो शुद्ध JAX बेसलाइन की तुलना में काफी तेज़ है, और इसमें कर्नेल पैरामीटर डेरिवेटिव के लिए ऑटोमैटिक डिफरेंशिएशन की सुविधा है।
लगभग एक अरब मापदंडों तक स्केलेबिलिटी: ऑर्डरिंग रणनीति और हार्डवेयर अनुकूलन का संयोजन एल्गोरिदम को रैखिक समय और मेमोरी आवश्यकताओं के साथ एकल GPU पर लगभग $10^9$ मापदंडों तक स्केल करने की अनुमति देता है।
पूर्ण इन्फरेंस बिल्डिंग ब्लॉक्स: सिस्टम फॉरवर्ड जनरेशन, इनवर्स एप्लीकेशन, लॉग-डे टर्मिनेंट गणना और कर्नेल पैरामीटर डेरिवेटिव प्रदान करता है, जो पूर्ण बेयसियन इन्फरेंस को सक्षम बनाता है।

परिणाम (Results)

प्रदर्शन: H100 GPU पर बेंचमार्क दर्शाते हैं कि CUDA कार्यान्वयन फॉरवर्ड पास के लिए JAX बेसलाइन की तुलना में दस गुना से भी अधिक तेज़ है।
स्केलिंग: फॉरवर्ड पास बिंदुओं की संख्या $N$ के संबंध में रैखिक स्केलिंग प्राप्त करता है।
मेमोरी दक्षता: मैट्रिसेस को रजिस्टरों में कंप्यूट करके, ग्लोबल मेमोरी आवंटन रणनीतियों की तुलना में मेमोरी फुटप्रिंट काफी कम हो जाता है।
सटीकता: कुलबैक-लीब्लर (Kullback–Leibler) डाइवर्जेंस का उपयोग करके मूल्यांकन से पता चलता है कि हालांकि पीढ़ी क्रम सटीकता को प्रभावित करता है, लेकिन उपयोग किए गए पड़ोसियों $k$ की संख्या की तुलना में इसका प्रभाव मामूली है। प्रस्तावित ऑर्डरिंग मानक ट्री या रैंडम ऑर्डर की तुलना में नगण्य सटीकता हानि के साथ सबसे बड़े समानांतर बैच प्राप्त करती है।
तुलना: GpGpU के विपरीत, जो केवल इनवर्स और लॉग-डे टर्मिनेंट ऑपरेशन्स को लागू करता है और जिसमें GPU पड़ोसी क्वेरीिंग की कमी है, GraphGP पूर्ण फॉरवर्ड पास और मनमाने बिंदु वितरणों का समर्थन करता है। ICR के विपरीत, इसे ग्रिड तक सीमित रहने की आवश्यकता नहीं है।

महत्व (Significance)

GraphGP इंटरस्टेलर मीडियम (interstellar medium) के त्रि-आयामी मानचित्रण और अन्य भौतिक विज्ञान क्षेत्रों के व्यावहारिक अनुप्रयोग को सक्षम बनाता है जिन्हें विषम रिज़ॉल्यूशन (inhomogeneous resolution) वाले क्षेत्रों पर इन्फरेंस की आवश्यकता होती है। ग्रिड-आधारित विधियों की बाधाओं और मूल GPs की मेमोरी बाधाओं को हटाकर, यह कम मेमोरी आवश्यकताओं के साथ उच्च-रिज़ॉल्यूशन मानचित्रों के निर्माण की अनुमति देता है। यह कार्य मनमाने बिंदुओं पर वेकिया के सन्निकटन के लचीलेपन और बड़े पैमाने पर पहले केवल संरचित ग्रिड पर ही प्राप्त की जाने वाली विशाल स्केलेबिलिटी के बीच के अंतर को पाटता है, जिससे बड़े पैमाने के स्थानिक डेटा के लिए अगली पीढ़ी के बेयसियन इन्फरेंस टूल्स का मार्ग प्रशस्त होता है।