Linear-cost Polyharmonic Spline Interpolation of Arbitrary Degree

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

इस समस्या को हल करने के लिए, वैज्ञानिक अक्सर एक "पॉलीहारमोनिक स्प्लाइन" (polyharmonic spline) का उपयोग करते हैं। इसे एक जादुई, खिंचने वाली रबर की चादर के रूप में समझें जिसे आप अपने ज्ञात डेटा बिंदुओं पर पिन कर देते हैं। वह चादर स्वाभाविक रूप से एक आकार में बैठ जाती है जो सभी बिंदुओं को सुचारू रूप से जोड़ता है। इस समस्या को हल करने के लिए गणना करना कि वह रबर की चादर वास्तव में कैसे मुड़ती है, समीकरणों के एक विशाल, उलझे हुए जाल को हल करने जैसा है। आमतौर पर, इसमें इतनी अधिक कंप्यूटर शक्ति लगती है कि यह समुद्र तट पर रेत के हर कण को हाथ से गिनने जैसा है। हालांकि, वैज्ञानिक टूलबॉक्स में दो चतुर तरीके हैं जो इसे तेज़ कर सकते हैं। पहला तरीका "फास्ट मल्टीपोल मेथड" (FMP) है, जो दूर के दोस्तों को समूह में रखने का एक अत्यंत कुशल तरीका है ताकि आपको संदेश भेजने के लिए हर व्यक्ति से व्यक्तिगत रूप से बात न करनी पड़े। दूसरा तरीका "वेचिया सन्निकटन" (Vecchia approximation) है, जो आपके निकटतम पड़ोसियों को देखकर उत्तर का अनुमान लगाने का एक तरीका है, यह मानते हुए कि दूर के लोग आपको बहुत अधिक प्रभावित नहीं करते हैं।

यह शोध पत्र एक नया, सुपर-फास्ट तरीका पेश करता है जिससे आप एक मिलियन से अधिक डेटा बिंदुओं के होने पर भी उस खिंचने वाली चादर का नक्शा बना सकते हैं। लेखक, क्रिस्टोफर जे. जियोगा और माइकल ओ'नील ने उन दोनों चतुर तरीकों को—समूह बनाने के तरीके और पड़ोसी-अनुमान लगाने के तरीके को—कुछ नए गणितीय शॉर्टकट के साथ जोड़ा है। उन्होंने पाया कि समस्या को बिजली के आवेशों (electric charges) से जुड़े एक भौतिकी पहेली की तरह मानकर और एक विशिष्ट प्रकार के "प्री-कंडीशनर" (एक गणितीय वार्म-अप अभ्यास जो कंप्यूटर को पहेली को तेज़ी से हल करने में मदद करता है) का उपयोग करके, वे लगभग तुरंत उत्तर प्राप्त कर सकते हैं। उनका तरीका इतना कुशल है कि यह एक सामान्य लैपटॉप पर एक मिलियन बिंदुओं को 15 सेकंड से कम समय में संभाल सकता है, एक ऐसा कार्य जिसे करने में आमतौर पर घंटों या दिनों का समय लगता है। उन्होंने यह भी दिखाया कि यह दृष्टिकोण अविश्वसनीय रूप से सटीक है, जो बिना किसी सेटिंग को बदले, धीमे और पूर्ण तरीकों के परिणामों से लगभग पूरी तरह मेल खाता है। यह एक घने जंगल के माध्यम से शॉर्टकट खोजने जैसा है जो आपको उसी गंतव्य तक ले जाता है जहाँ लंबा, घुमावदार रास्ता ले जाता, लेकिन बहुत कम समय में।

खिंचने वाली चादर का जादू

इस कार्य के मूल में एक ऐसी समस्या है जो सुनने में सरल लगती है लेकिन बहुत जटिल हो जाती है: आप डेटा बिंदुओं के बीच के खाली स्थानों को कैसे भरते हैं? लेखक "पॉलीहारमोनिक स्प्लाइन" (PHS) इंटरपोलेशन नामक विधि का उपयोग करते हैं। कल्पना करें कि आपके पास रबर की एक चादर है और आप उसे उन विशिष्ट स्थानों पर पिन कर देते हैं जहाँ आपको ऊंचाई का पता है। चादर उन्हें जोड़ने के लिए स्वाभाविक रूप से मुड़ जाती है। इसके पीछे के गणित में एक "कर्नेल मैट्रिक्स" (kernel matrix) शामिल है, जो केवल एक विशाल स्प्रेडशीट है जो दिखाती है कि प्रत्येक बिंदु दूसरे बिंदु से कैसे बात करता है।

समस्या यह है कि यह स्प्रेडशीट "सघन" (dense) है, जिसका अर्थ है कि इसके प्रत्येक सेल में एक नंबर है। यदि आपके पास 1,000 बिंदु हैं, तो आपको दस लाख सेल की गणना करनी होगी। यदि आपके पास एक मिलियन बिंदु हैं, तो आपको एक ट्रिलियन ट्रिलियन सेल की गणना करनी होगी। पारंपरिक कंप्यूटरों को इसे हल करने के लिए एक क्यूबिक मात्रा में काम ($O(n^3)$) करना पड़ेगा, यही कारण है कि यह विशाल डेटासेट के लिए आमतौर पर असंभव है।

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

भीड़ को समूहबद्ध करना: फास्ट मल्टीपोल मेथड

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

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

इंजन को वार्म-अप करना: प्रीकंडीशनर

इस समूह बनाने वाले तेज़ तरीके के बावजूद, कंप्यूटर को रबर की चादर का सटीक आकार खोजने के लिए समीकरणों के एक सिस्टम को हल करने की आवश्यकता होती है। यहीं पर "प्रीकंडीशनर" काम आता है। कंप्यूटर सॉल्वर को एक कार के रूप में सोचें जो एक खड़ी, घुमावदार पहाड़ी पर चढ़ने की कोशिश कर रही है। यदि पहाड़ी बहुत खड़ी या घुमावदार है, तो कार रुक सकती है या बहुत समय ले सकती है। एक प्रीकंडीशनर एक सड़क निर्माण दल की तरह है जो रास्ते को सुचारू बनाता है, जिससे पहाड़ी पर चढ़ना आसान हो जाता है ताकि कार तेज़ी से ऊपर जा सके।

लेखक "वेचिया सन्निकटन" (Vecchia approximation) पर आधारित एक नया, अविश्वसनीय रूप से तेज़ प्रीकंडीशनर प्रस्तावित करते हैं। यह विधि मानती है कि एक बिंदु मुख्य रूप से अपने निकटतम पड़ोसियों से प्रभावित होता है, न कि दुनिया के दूसरी ओर के बिंदुओं से। "मैटर्न कोवेरिएंस" (Matérn covariance) नामक एक सांख्यिकीय मॉडल का उपयोग करके (जो यह बताता है कि चीजें दूरी के साथ कैसे सुचारू होती हैं), वे एक स्पार्स मैट्रिक्स (sparse matrix) बना सकते हैं—एक ऐसी स्प्रेडशीट जहाँ अधिकांश सेल शून्य हैं। यह स्पार्स मैट्रिक्स आसानी से गणना योग्य है और सॉल्वर के लिए एक आदर्श वार्म-अप के रूप में कार्य करती है।

लेखकों ने पाया कि यह विशिष्ट संयोजन चमत्कार करता है। उनके परीक्षणों में, कंप्यूटर सॉल्वर (एक विधि जिसे 'प्रीकंडीशन्ड कंजुगेट ग्रेडिएंट' कहा जाता है) एक मिलियन से अधिक डेटा बिंदुओं के लिए भी 15 पुनरावृत्तियों (iterations) से कम में अभिसरित (converge) हो गया। इसका मतलब है कि कार ने केवल पहाड़ी नहीं चढ़ी; वह उस पर उड़ गई।

परिणाम: गति और सटीकता का मिलन

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

उन्होंने सटीकता का भी परीक्षण किया। एक प्रयोग में, उन्होंने एक जटिल फलन (function) की भविष्यवाणी करने की कोशिश की जिसमें चिकनी लहरें और एक तीखा, नुकीला उभार दोनों थे। नया तरीका "सटीक" विधि (धीमी, पूर्ण विधि) के लगभग समान त्रुटि दर के साथ परिणाम देता है, जो यह सिद्ध करता है कि शॉर्टकट ने गुणवत्ता से समझौता नहीं किया।

शायद सबसे प्रभावशाली प्रदर्शन प्रशांत महासागर के समुद्री सतह के तापमान के डेटा का उपयोग करके किया गया वास्तविक दुनिया का परीक्षण था। उनके पास लगभग 58,000 माप थे जिनमें "बादल के आवरण" (सिम्युलेटेड अंतराल) के कारण कुछ अंतराल थे। उनके तरीके का उपयोग करके, उन्होंने बहुत कम त्रुटि दर के साथ केवल 5 सेकंड में लापता डेटा को भर दिया। इसके विपरीत, उसी सांख्यिकीय मॉडल का उपयोग करने वाले पारंपरिक तरीके ने 400 सेकंड से अधिक का समय लिया और वास्तव में खराब प्रदर्शन किया। यह उनके दृष्टिकोण की एक प्रमुख विशेषता को उजागर करता है: क्योंकि पॉलीहारमोनिक स्प्लाइन "स्केल-इनवेरिएंट" (scale-invariant) है, इसे डेटा के विभिन्न आकारों के लिए ट्यून या एडजस्ट करने की आवश्यकता नहीं होती है, जो इसे एक "प्लग-एंड-प्ले" समाधान बनाता है जो बस काम करता है।

यह क्यों महत्वपूर्ण है

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

संक्षेप में, जियोगा और ओ'नील ने एक ऐसी समस्या को लिया है जो पहले अधिकांश कंप्यूटरों के लिए बहुत भारी थी और उसे एक बैकपैक में ले जाने लायक हल्का बना दिया है। दूर के बिंदुओं को समूहबद्ध करने की गति को निकटतम पड़ोसियों के आधार पर अनुमान लगाने की दक्षता के साथ जोड़कर, उन्होंने एक ऐसा उपकरण बनाया है जो एक झटके में, एक मिलियन बिंदुओं के साथ, दुनिया का नक्शा बना सकता है।