📊 statistics

Improving TensorSketch Using Complex Random Variables

यह शोध पत्र TensorSketch एल्गोरिदम के एक नवीन संस्करण को प्रस्तुत करता है जो उच्च-आयामी बहुपद कर्नेल (polynomial kernels) के लिए $2^p/D$ का बेहतर विचरण सीमा (variance bound) प्राप्त करने के लिए जटिल यादृच्छिक चरों (complex random variables) का लाभ उठाता है, जबकि मूल पद्धति के कुशल इनपुट-विरलता (input-sparsity) रनिंग टाइम को बनाए रखता है।

मूल लेखक: Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

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

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

CC BY 4.0

मूल लेखक: Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang

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

कल्पना कीजिए कि आप एक विशाल जिग्सॉ पहेली (jigsaw puzzle) को हल करने की कोशिश कर रहे हैं, लेकिन टुकड़ों के बजाय, आपके पास डेटा पॉइंट्स के रूप में लाखों संख्याएँ हैं। मशीन लर्निंग की दुनिया में, कंप्यूटर अक्सर इन संख्याओं की तुलना करके पैटर्न खोजने की कोशिश करते हैं। कभी-कभी, पैटर्न सरल होते हैं, जैसे एक सीधी रेखा। लेकिन अक्सर, दुनिया अव्यवज़त और घुमावदार होती है, इसलिए कंप्यूटर "कर्नेल" (kernels) का उपयोग करते हैं—गणितीय जादू के नुस्खे जो उन्हें डेटा पॉइंट्स के बीच जटिल, घुमावदार संबंधों को देखने में सक्षम बनाते हैं। एक लोकप्रिय तरीका "पॉलीनोमियल कर्नेल" (polynomial kernel) है, जो यह देखता है कि जब विशेषताओं (features) को कई बार आपस में गुणा किया जाता है, तो वे कैसे परस्पर क्रिया करती हैं।

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

हाल ही में, शोधकर्ताओं के एक दल ने एक जिज्ञासु प्रश्न पूछा: क्या होगा यदि हम केवल नियमित संख्याओं का उपयोग करना बंद कर दें और "कॉम्प्लेक्स" (complex) संख्याओं का उपयोग करना शुरू कर दें—संख्याएँ जिनमें एक काल्पनिक भाग (imaginary part) शामिल होता है, जैसे कि ऋण एक का वर्गमूल? उन्होंने सोचा कि क्या यह काल्पनिक मोड़ थंबनेल को अधिक स्पष्ट बना सकता है। एक पिछले अध्ययन ने दिखाया था कि एक प्रकार के स्केचिंग के लिए, कॉम्प्लेक्स नंबरों का उपयोग करने से चित्र अधिक स्पष्ट हो गया (धुंधलेपन को कम कर दिया)। हालांकि, वह विधि धीमी और बोझिल थी, जैसे दौड़ते समय एक भारी बैकपैक ले जाना। शोधकर्ता यह जानना चाहते थे: क्या हम उस सुपर-शार्प, कॉम्प्लेक्स-नंबर क्लैरिटी को बिना उस भारी बैकपैक के प्राप्त कर सकते हैं? क्या हम तेज़, हल्के टेन्सरस्केच तरीके को उस धीमी, भारी विधि जितना अच्छा बना सकते हैं?

पेपर, जिसका शीर्षक "Improving TensorSketch Using Complex Random Variables" है, कहता है कि हाँ। लेखकों ने, अमित शर्मा, मोहम्मद अज़हर खान, रामेश्वर प्रताप और कीगन कांग ने एक नया टेन्सरस्केच बनाया है जो इन कॉम्प्लेक्स नंबरों का उपयोग करता है लेकिन मूल विधि की गति को बनाए रखता है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने इसे गणित के साथ सिद्ध किया और वास्तविक डेटा के साथ परीक्षण किया।

यहाँ बताया गया है कि उन्होंने यह कैसे किया। मूल टेन्सरस्केच आपके डेटा को लेता है, उसे यादृच्छिक संकेतों (random signs) के साथ मिलाता है (जैसे कि यह तय करने के लिए सिक्का उछालना कि संख्या धनात्मक है या ऋणात्मक), और फिर उसे सिकोड़ देता है। नया तरीका, जिसे वे "कॉम्प्लेक्स-टू-रियल टेन्सरस्केच" (या CtR TensorSketch) कहते हैं, सिक्के के उछाल को बदल देता है। केवल चित या पट (1 या -1) के बजाय, वे एक चार-तरफा पासे का उपयोग करते हैं जो 1, -1, या दो काल्पनिक संख्याओं (i और -i) पर गिरता है। यह सुनने में ऐसा लग सकता है कि इसका परिणाम एक अजीब, काल्पनिक गड़बड़ी होगी, लेकिन उनके पास एक चतुर तरकीब है। वे परिणाम लेते हैं, जो एक कॉम्प्लेक्स नंबर है, और इसे दो भागों में विभाजित करते हैं: "वास्तविक" (real) भाग और "काल्पनिक" (imaginary) भाग। फिर, वे इन दोनों भागों को अगल-बगल रखकर एक नया, वास्तविक-दुनिया का वेक्टर बनाते हैं।

जादू इस बात में है कि ये काल्पनिक संख्याएँ कैसे परस्पर क्रिया करती हैं। जब शोधकर्ताओं ने संख्याओं की गणना की, तो उन्होंने पाया कि उनके नए तरीके की "धुंधलापन" (या वेरिएंस) पुराने तरीके की तुलना में बहुत धीमी गति से बढ़ता है। पुराने तरीके में, त्रुटि $3^p$ (जहाँ $p$ पहेली की जटिलता है) की तरह बढ़ती है। उनके नए तरीके में, त्रुटि केवल $2^p$ की तरह बढ़ती है। यह सुनने में एक छोटे अंतर जैसा लग सकता है, लेकिन घातांकीय वृद्धि (exponential growth) की दुनिया में, यह एक विशाल सुधार है। इसका मतलब है कि जटिल पहेलियों के लिए, उनका नया स्केच काफी अधिक सटीक है।

महत्वपूर्ण रूप से, उन्होंने यह भी सिद्ध किया कि यह नया तरीका अभी भी पुराने वाले के समान ही तेज़ है। जबकि कॉम्प्लेक्स नंबरों का उपयोग करने वाले अन्य तरीकों के लिए कंप्यूटर को भारी, धीमी गणनाएँ करने की आवश्यकता होती है (जो डेटा के पूर्ण आकार के समान समय लेती हैं), उनका तरीका "इनपुट-स्पार्स" (input-sparse) रहता है। इसका मतलब है कि यह केवल डेटा के उन हिस्सों पर समय खर्च करता है जो वास्तव में मौजूद हैं, शून्य (zeros) को अनदेखा करता है। उन्होंने दिखाया कि उनके एल्गोरिदम को चलाने में लगने वाला समय $O(p(nnz(x) + D \log D))$ है, जो मूल टेन्सरस्केच की गति के समान है।

यह सुनिश्चित करने के लिए कि यह केवल कागज पर काम करने वाला एक गणितीय चमत्कार नहीं था, उन्होंने प्रयोग चलाए। उन्होंने अपने तरीके का परीक्षण सिंथेटिक डेटा (बनाए गए नंबर) और वास्तविक दुनिया के डेटासेट जैसे कि MAGIC गामा टेलीस्कोप डेटा और COD-RNA पर किया। उन्होंने अपने CtR टेन्सरस्केच की तुलना मानक टेन्सरस्केच और अन्य कॉम्प्लेक्स विधियों से की। परिणाम स्पष्ट थे: उनके नए तरीके ने बहुत अधिक सटीक सन्निकटन (approximations) उत्पन्न किए (जिसे KL डाइवर्जेंस द्वारा मापा जाता है, जो यह जाँचता है कि स्केच मूल के कितने समान है) जबकि इसे कंप्यूट करने में समान समय लगा। वास्तव में, कुछ परीक्षणों में, उनका तरीका अन्य कॉम्प्लेक्स विधियों की तुलना में तेज़ भी था क्योंकि उसे भारी काम नहीं करना पड़ा।

पेपर एक संभावित भ्रम को भी संबोधित करता है। उन्होंने दिखाया कि केवल एक अलग प्रकार के स्केच (जिसे काउंटस्केच कहा जाता है) में कॉम्प्लेक्स नंबरों का उपयोग करने से यह स्वतः बेहतर नहीं हो जाता है। सुधार केवल उस विशिष्ट तरीके से आता है जिससे उन्होंने कॉम्प्लेक्स नंबरों को टेन्सरस्केच संरचना के साथ जोड़ा। यह सिद्ध करता है कि उनका परिणाम कोई इत्तेफाक नहीं है; यह एक विशिष्ट, गैर-तुच्छ (non-trivial) सुधार है जो इस बात से आता है कि गणित कैसे कुछ त्रुटि पदों (error terms) को रद्द करता है।

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

तकनीकी सारांश: जटिल यादृच्छिक चरों (Complex Random Variables) का उपयोग करके TensorSketch में सुधार

समस्या विवरण
पॉलीनोमियल कर्नेल (Polynomial kernels), जिन्हें $k(x, y) = \langle x, y \rangle^p$ के रूप में परिभाषित किया गया है, उच्च-क्रम के गैर-रेखीय अंतःक्रियाओं (higher-order non-linear interactions) को मॉडल करने के लिए आवश्यक हैं। हालाँकि, $p$ -फोल्ड क्रोनेकर उत्पाद (Kronecker product) $x^{\otimes p} \in \mathbb{R}^{d^p}$ के आंतरिक उत्पाद (inner product) की गणना करना घातीय आयामी वृद्धि (exponential dimension growth) के कारण कम्प्यूटेशनल रूप से असंभव है। रैंडमाइज्ड स्केचिंग तकनीकें, जैसे कि TensorSketch (Pham और Pagh [2013]) और JL-प्रकार के रैंडम फीचर मैप्स (Kar और Karnick [2012]), इन कर्नेल्स का कुशलतापूर्वक अनुमान लगाती हैं। जबकि TensorSketch $O(p(\text{nnz}(x) + D \log D))$ का इनपुट-स्पैरसिटी रनिंग टाइम प्रदान करता है जो उच्च-आयामी विरल (sparse) डेटा के लिए उपयुक्त है, TensorSketch और JL-प्रकार की दोनों विधियाँ ऐसे वेरिएंस (variance) से ग्रस्त हैं जो पॉलीनोमियल डिग्री $p$ के साथ $3^p/D$ के रूप में तेजी से बढ़ता है।

हालिया कार्य द्वारा Wacker et al. [2023] ने प्रदर्शित किया कि JL-प्रकार के प्रोजेक्शन में जटिल-मान वाले यादृच्छिक चरों (complex-valued random variables) का उपयोग करने से इस वेरिएंस निर्भरता को $2^p/D$ तक कम किया जा सकता है। हालाँकि, उनकी विधि $O(pDd)$ लागत वाली सघन मैट्रिक्स गुणन (dense matrix multiplications) पर निर्भर करती है, जो उच्च-आयामी विरल इनपुट के लिए अक्षम है। इसके अलावा, उनका दृष्टिकोण हैशिंग-आधारित TensorSketch फ्रेमवर्क तक विस्तारित नहीं हुआ।

कार्यप्रणाली (Methodology)
यह शोध पत्र एक कॉम्प्लेक्स-टू-रियल (Complex-to-Real - CtR) वेरिएंट ऑफ TensorSketch प्रस्तुत करता है जो वेरिएंस रिडक्शन और कम्प्यूटेशनल दक्षता के बीच के अंतर को पाटता है। मुख्य कार्यप्रणाली में तीन प्रमुख घटक शामिल हैं:

कॉम्प्लेक्स काउंटस्केच (Complex CountSketch): लेखक एक कॉम्प्लेक्स काउंटस्केच मैपिंग को परिभाषित करते हैं जहाँ रैंडम साइन फंक्शन $s: [d] \to \{1, \omega, \omega^2, \omega^3\}$ मानक रियल रेडमेकर साइन्स $\{-1, 1\}$ के बजाय चौथी घात के रूट्स ऑफ यूनिटी (fourth roots of unity, $\omega = i$ ) से मानों को समान रूप से चुनता है।
कॉम्प्लेक्स टेंसरस्केच निर्माण: वे $p$ स्वतंत्र कॉम्प्लेक्स काउंटस्केच मैपिंग का निर्माण करके और FFT-आधारित कन्वोल्यूशन (convolution) के माध्यम से उन्हें संयोजित करके इसे डिग्री- $p$ कर्नेल्स तक विस्तारित करते हैं। यह पूर्ण टेंसर बनाए बिना $x^{\otimes p}$ के स्केच की गणना करने की अनुमति देता है, जिससे इनपुट-स्पैरसिटी टाइम कॉम्प्लेक्सिटी बनी रहती है।
कॉम्प्लेक्स-टू-रियल (CtR) रूपांतरण: यह सुनिश्चित करने के लिए कि आउटपुट मानक रियल-वैल्यूड मशीन लर्निंग एल्गोरिदम के अनुकूल हो, लेखक एक CtR रूपांतरण लागू करते हैं। इसमें कॉम्प्लेक्स स्केच वेक्टर $\Phi_C(x^{\otimes p}) \in \mathbb{C}^{D/2}$ के रियल और इमेजिनरी भागों को जोड़कर एक रियल-वैल्यूड वेक्टर $\Phi_{CtR}(x^{\otimes p}) \in \mathbb{R}^D$ बनाना शामिल है।

सैद्धांतिक गारंटी (Theoretical Guarantees)
यह शोध पत्र यह सिद्ध करने के लिए कठोर सैद्धांतिक विश्लेषण प्रदान करता है कि प्रस्तावित एस्टीमेटर (estimator) पॉलीनोमियल कर्नेल $\langle x, y \rangle^p$ के लिए निष्पक्ष (unbiased) है। महत्वपूर्ण रूप से, वेरिएंस विश्लेषण कॉम्प्लेक्स वेरिएबल्स के लिए अनुकूलित खिंचिन-प्रकार (Khintchine-type) की असमानताओं और कॉम्प्लेक्स चरों के गुणों का लाभ उठाता है। लेखक सिद्ध करते हैं कि CtR TensorSketch एस्टीमेटर का वेरिएंस निम्नलिखित है:
$\text{Var}(\hat{k}_{CtR}(x, y)) \leq \frac{2^{p+1} - 2}{D} \|x\|_2^{2p} \|y\|_2^{2p}$
यह क्लासिकल TensorSketch वेरिएंस बाउंड $\frac{3^p - 1}{D} \|x\|_2^{2p} \|y\|_2^{2p}$ की तुलना में एक महत्वपूर्ण सुधार है, जो घातीय आधार (exponential base) को $3 $से घटाकर$ 2 $कर देता है। टाइम कॉम्प्लेक्सिटी$ O(p(\text{nnz}(x) + D \log D))$ बनी रहती है, जो मूल रियल-वैल्यूड TensorSketch की दक्षता से मेल खाती है।

प्रायोगिक परिणाम (Experimental Results)
लेखक अपने तरीके को मानक TensorSketch, JL-प्रकार के स्केच (Gaussian और Rademacher), और उनके CtR वेरिएंट के विरुद्ध सिंथेटिक और वास्तविक दुनिया के डेटासेट (MAGIC Gamma Telescope, COD-RNA) पर सत्यापित करते हैं।

सटीकता (Accuracy): सटीक कर्नेल और स्केच-आधारित सन्निकटन (approximation) के बीच KL डाइवर्जेंस के माध्यम से मापी गई, CtR TensorSketch विभिन्न पॉलीनोमियल डिग्री ( $p$ ) और स्केच आयामों ( $D$ ) के लिए लगातार निम्नतम त्रुटि प्राप्त करती है।
दक्षता (Efficiency): वॉल-क्लॉक कंस्ट्रक्शन टाइम के संदर्भ में, प्रस्तावित विधि इनपुट-स्पैरसिटी लाभ को बनाए रखती है, जो वास्तविक TensorSketch के तुलनीय प्रदर्शन करती है और $O(pDd)$ के साथ स्केल करने वाले सघन JL-प्रकार के तरीकों की तुलना में काफी तेज़ है।
डाउनस्ट्रीम टास्क: लीनियर SVMs का उपयोग करके बाइनरी क्लासिफिकेशन पर प्रयोगों से पता चलता है कि CtR TensorSketch, वास्तविक TensorSketch और सघन JL वेरिएंट की तुलना में उच्च सटीकता प्राप्त करता है, जबकि सबसे तेज़ कुल निष्पादन समय (कंप्रेशन + ट्रेनिंग) बनाए रखता है।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि यह कार्य हैशिंग-आधारित CountSketch/TensorSketch प्रतिमान में कॉम्प्लेक्स-टू-रियल फ्रेमवर्क को सफलतापूर्वक अनुकूलित करने वाला पहला प्रयास है। पूर्ववर्ती जटिल-मान वाले दृष्टिकोणों के विपरीत, जो सघन प्रोजेक्शन तक सीमित थे, यह विधि महत्वपूर्ण इनपुट-स्पैरसिटी रनिंग टाइम को बरकरार रखते हुए बेहतर वेरिएंस बाउंड्स ( $2^p$ बनाम $3^p$ ) प्राप्त करती है।

लेखक नोट करते हैं कि वेरिएंस रिडक्शन गैर-तुच्छ (non-trivial) है; विशिष्ट CtR कंस्ट्रक्शन और क्रॉस-टर्म्स के विश्लेषण के बिना केवल CountSketch पर कॉम्प्लेक्स वेरिएबल्स लागू करने से वेरिएंस में कमी नहीं आती है। सुधार चौथे घात के रूट्स ऑफ यूनिटी के गुणों के कारण वेरिएंस विश्लेषण में विशिष्ट क्रॉस-टर्म्स के शून्य होने से आता है।

शोध पत्र दो खुले दिशाओं (open directions) की पहचान करते हुए समाप्त होता है: यह जांचना कि क्या उच्च-क्रम के रूट्स ऑफ यूनिटी और भी कड़े सन्निकटन गारंटी दे सकते हैं, और अन्य कर्नेल परिवारों (पॉलीनोमियल कर्नेल्स के परे) तक CtR कंस्ट्रक्शन के विस्तार की खोज करना। यह कार्य CtR TensorSketch को लीनियर SVM ट्रेनिंग, डीप लर्निंग स्केलेबिलिटी और फाइन-ग्रेन्ड विजुअल रिकग्निशन सहित कुशल पॉलीनोमियल कर्नेल एप्रोक्सिमेशन के लिए एक आशाजनक विकल्प के रूप में स्थापित करता है।

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