📊 statistics

MaxSketch: Robust Distinct Counting in Streams via Random Projections

यह शोधपत्र MaxSketch प्रस्तुत करता है, जो एक रैंडम प्रोजेक्शन-आधारित एल्गोरिदम है जो शोर वाले, उच्च-आयामी डेटा स्ट्रीम्स में विशिष्ट गणनाओं (distinct counts) का मजबूती से अनुमान लगाने के लिए सीखे गए निरूपणों (learned representations) में ज्यामितीय संरचना का लाभ उठाता है, ताकि शास्त्रीय स्केच और पूर्ववर्ती वर्स्ट-केस सीमाओं की सीमाओं को पार करते हुए निकट-इष्टतम लघुगणकीय मेमोरी जटिलता प्राप्त की जा सके।

मूल लेखक: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

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

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

CC BY 4.0

मूल लेखक: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

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

कल्पना कीजिए कि आप एक कैमरे के साथ एक व्यस्त चौराहे पर खड़े हैं, और आप यह गिनने की कोशिश कर रहे हैं कि कितने अद्वितीय (unique) लोग वहां से गुजरे।

पुराने दिनों में, कंप्यूटर साइंस में गिनती करना आसान था यदि हर कोई एक समान आईडी बैज पहनता। यदि "एलिस" वहां से गुजरती, तो उसका बैज "एलिस" कहता। यदि वह दोबारा गुजरती, तो उसका बैज अभी भी "एलिस" ही कहता। कंप्यूटर को बस यह जांचने की आवश्यकता थी कि क्या उसने पहले कभी उस सटीक बैज को देखा है। यह ऐसे ही काम करता है जैसे क्लासिक काउंटिंग टूल्स: वे सटीक मिलान (exact matches) पर निर्भर करते हैं।

लेकिन वास्तविक दुनिया में, लोग आईडी बैज नहीं पहनते। वे अलग-अलग कपड़े पहनते हैं, अलग-अलग रोशनी में खड़े होते हैं, और अलग-अलग मुद्राएं (poses) बनाते हैं। यदि एलिस लाल कोट में गुजरती है और बाद में नीली जैकेट में, तो एक साधारण कंप्यूटर सोच सकता है, "यह एक नया व्यक्ति है!" और उसे दो बार गिन सकता है। यह शोर वाले, उच्च-आयामी डेटा (noisy, high-dimensional data) की समस्या है: एक ही वस्तु हर बार अलग दिखती है।

पुराना तरीका बनाम नई समस्या

पिछले प्रयासों ने समान दिखने वाली चीजों को एक साथ समूहबद्ध करने (क्लस्टरिंग) की कोशिश की। लेकिन यह हर उस व्यक्ति की फोटो रखने जैसा है जिसे आपने कभी देखा है। यदि आप 10,000 लोगों को देखते हैं, तो आपको 10,000 फोटो याद रखने की आवश्यकता होगी। यह बहुत अधिक मेमोरी लेता है, खासकर यदि आप वास्तविक समय में डेटा के विशाल प्रवाह (stream) को प्रोसेस कर रहे हों।

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

समाधान: MaxSketch

इस शोध पत्र के लेखक MaxSketch नामक एक नई विधि पेश करते हैं। उन्होंने महसूस किया कि आधुनिक एआई (विशेष रूप से डीप लर्निंग) पहले से ही डेटा को व्यवस्थित करने में बहुत अच्छा काम करता है। जब आप किसी एआई को चेहरे या वस्तुओं को पहचानने के लिए प्रशिक्षित करते हैं, तो वह स्वाभाविक रूप से "एलिस" को एक घने क्लस्टर में और "बॉब" को दूसरे, दूर के क्लस्टर में रखता है। भले ही एलिस अपना कोट बदल ले, उसका "डिजिटल फिंगरप्रिंट" उसके मूल स्थान के करीब ही रहता है।

MaxSketch बिना हर फोटो को याद रखे, इसी प्राकृतिक क्लस्टरिंग का उपयोग करता है।

उपमा: "विंड टनल" (Wind Tunnel)

कल्पना कीजिए कि आपके पास एक विशाल विंड टनल है जिसमें कई पंखे अलग-अलग दिशाओं से हवा फेंक रहे हैं।

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

यह क्यों काम करता है

यह शोध पत्र सिद्ध करता है कि यदि डेटा "व्यवस्थित" (well-behaved) है (अर्थात, एआई ने समान चीजों को सफलतापूर्वक समूहित किया है और अलग चीजों को दूर रखा है), तो यह विधि अविश्वसनीय रूप से कुशल है।

मेमोरी: आपको एक शहर के आकार के पुस्तकालय की आवश्यकता होने के बजाय, MaxSketch को केवल एक छोटी नोटबुक (लॉगारिदमिक मेमोरी) की आवश्यकता होती है। यह भीड़ को गिनने के लिए हर व्यक्ति की फोटो लेने के बजाय हवा की दिशा के कुछ त्वरित स्नैपशॉट लेने जैसा है।
सटीकता: यह बहुत उच्च सटीकता (एक बहुत ही सूक्ष्म त्रुटि मार्जिन के भीतर) के साथ अद्वितीय लोगों की संख्या का अनुमान लगा सकता है।
मजबूती (Robustness): यह तब भी काम करता है जब लाल कोट वाली "एलिस" नीली जैकेट वाली "एलिस" से थोड़ी अलग दिखती है, जब तक कि उन्हें एआई की मेमोरी के एक ही सामान्य "पड़ोस" में पहचाना जा सके।

उन्होंने क्या परीक्षण किया

शोधकर्ताओं ने इस पर परीक्षण किया:

MNIST (हस्तलिखित अंक): जहाँ "क्लस्टर" बहुत स्पष्ट हैं (एक '3' हमेशा '3' ही दिखता है)। यहाँ, MaxSketch एकदम सटीक था, यहाँ तक कि उन अनुक्रमों को गिनने में भी जो इसके प्रशिक्षण काल से बहुत लंबे थे।
CIFAR-10 (छोटी रंगीन छवियां): जहाँ चीजें अधिक अव्यवस्थित हैं। यह अभी भी अच्छा काम करता है, विशेष रूप से यदि एआई पहले से ही वस्तुओं को पहचानने के लिए प्रशिक्षित हो।
वास्तविक चेहरा डेटा (Real Face Data): वास्तविक दुनिया के लोगों की तस्वीरों का उपयोग करके। भले ही डेटा आदर्श नहीं था, MaxSketch ने हजारों तस्वीरों के प्रवाह में कितने अद्वितीय लोग थे, इसका बहुत अच्छा अनुमान लगाया, जो मैसी (messy) डेटा के लिए डिज़ाइन किए गए पिछले तरीकों से बेहतर था।

निष्कर्ष

MaxSketch एक चतुर युक्ति है जो एक कठिन गिनती की समस्या को एक सरल "अधिकतम खोजने" (maximum finding) की समस्या में बदल देती है। इस तथ्य का लाभ उठाकर कि आधुनिक एआई स्वाभाविक रूप से समान चीजों को समूहबद्ध करता है, यह बहुत कम मेमोरी का उपयोग करके एक विशाल, शोर वाले स्ट्रीम में अद्वितीय वस्तुओं को गिन सकता है। यह पुराने जमाने के काउंटिंग एल्गोरिदम और आधुनिक एआई के बीच के अंतर को पाटता है, यह दिखाते हुए कि यदि आपका डेटा अच्छी तरह से व्यवस्थित है, तो आपको यह जानने के लिए सब कुछ याद रखने की आवश्यकता नहीं है कि वहां कितने अद्वितीय तत्व मौजूद हैं।

तकनीकी सारांश: MaxSketch: रैंडम प्रोजेक्शन के माध्यम से स्ट्रीम्स में रोबस्ट डिस्टिंक्ट काउंटिंग (Robust Distinct Counting)

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

डेटा स्ट्रीम में विशिष्ट तत्वों (distinct elements) की संख्या का अनुमान लगाने की शास्त्रीय समस्या अच्छी तरह से समझी जा चुकी है जब एक ही तत्व की बार-बार होने वाली उपस्थिति को समान कुंजियों (जैसे, सटीक स्ट्रिंग मिलान) द्वारा दर्शाया जाता है (उदाहरण के लिए, HyperLogLog)। ये एल्गोरिदम सुसंगत हैश मानों (consistent hash values) पर भरोसा करके लॉगरिदमिक मेमोरी के साथ इसे प्राप्त करते हैं। हालाँकि, आधुनिक डेटा मोडैलिटीज (जैसे, कंप्यूटर विज़न, नेचुरल लैंग्वेज) में, अवलोकन उच्च-आयामी (high-dimensional) और शोरयुक्त (noisy) होते हैं। एक ही वस्तु के विभिन्न उदाहरण (जैसे, एक ही व्यक्ति की अलग-अलग छवियां) केवल लगभग समान (approximately similar) होते हैं, सटीक रूप से समान नहीं।

इस "रोबस्ट डिस्टिंक्ट काउंटिंग" शासन (regime) में, शास्त्रीय स्केच विफल हो जाते हैं क्योंकि वे एक नए ऑब्जेक्ट और मौजूदा ऑब्जेक्ट के शोरयुक्त संस्करण के बीच अंतर नहीं कर सकते हैं। सामान्य मीट्रिक स्पेस में हालिया कार्यों ने रोबस्ट काउंटिंग के लिए $\tilde{\Omega}(\sqrt{n})$ का वर्स्ट-केस मेमोरी लोअर बाउंड स्थापित किया है, जो सटीक सेटिंग में प्राप्त $\tilde{O}(\log n)$ की तुलना में घातीय रूप से खराब है। यह शोध पत्र जिस केंद्रीय प्रश्न को संबोधित करता है वह यह है कि क्या आधुनिक सीखे गए रिप्रजेंटेशन (learned representations) में पाई जाने वाली विशिष्ट ज्यामितीय संरचना—जहाँ एक ही वस्तु के अवलोकन घने क्लस्टर बनाते हैं और अलग-अलग वस्तुएं अच्छी तरह से अलग दिशाओं के रूप में होती हैं—इस $\sqrt{n}$ बाधा को पार कर सकती है।

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

लेखक MaxSketch पेश करते हैं, जो एक सरल, मैक्स-लीनियर स्ट्रीमिंग स्केच है जिसे सीखे गए एम्बेडिंग्स की ज्यामितीय संरचना का लाभ उठाने के लिए डिज़ाइन किया गया है।

मुख्य तंत्र (Core Mechanism)

योग (summing) या औसत (averaging) करने के बजाय (जो फ्रीक्वेंसी के साथ स्केल करते हैं और विशिष्टता को बहुलता के साथ भ्रमित करते हैं), MaxSketch अवलोकनों को मैक्सिमम (maximum) ऑपरेशन्स के माध्यम से एकत्रित करता है।

रैंडम प्रोजेक्शंस (Random Projections): यूनिट वेक्टर्स $X = \langle \tilde{x}_1, \dots, \tilde{x}_n \rangle \subset S^{d-1}$ की एक स्ट्रीम दी गई है, एल्गोरिदम $m$ स्वतंत्र रैंडम गॉसियन वेक्टर्स $w_1, \dots, w_m \sim \mathcal{N}(0, I_d)$ को फिक्स करता है।
मैक्स-एग्रीगेशन (Max-Aggregation): प्रत्येक प्रोजेक्शन $w_j$ के लिए, यह स्ट्रीम में किसी भी अवलोकन के साथ अधिकतम आंतरिक उत्पाद (maximum inner product) की गणना करता है:
$M_j(X) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle$
सांख्यिकी (Statistic): अंतिम स्केच इन मैक्सिमा का औसत है:
$S(X) = \frac{1}{m} \sum_{j=1}^m M_j(X)$

सैद्धांतिक आधार (Theoretical Foundation)

यह विधि इस धारणा पर निर्भर करती है कि स्ट्रीम $(\eta, \rho)$ -क्लस्टर करने योग्य (clusterable) है। इसका अर्थ है:

इंट्रा-क्लस्टर अलाइनमेंट (Within-cluster alignment): एक ही वस्तु के अवलोकन एक लेटेंट सेंटर (latent center) के दिशात्मक रूप से करीब होते हैं (जिसे $\eta$ द्वारा नियंत्रित किया जाता है)।
क्रॉस-क्लस्टर सेपरेशन (Cross-cluster separation): अलग-अलग वस्तुओं के लेटेंट सेंटर्स के बीच आंतरिक उत्पाद कम होता है (जिसे $\rho$ द्वारा नियंत्रित किया जाता है)।

इस धारणा के तहत, वेक्टर्स के सेट का अधिकतम प्रोजेक्शन स्वतंत्र गॉसियनों के अधिकतम (maximum of independent Gaussians) की तरह व्यवहार करता है। $k$ और $(1+\epsilon)$ क्लस्टर्स के बीच अपेक्षित मैक्सिमा में अंतर, उच्च प्रायिकता के साथ उन्हें अलग करने के लिए पर्याप्त होता है। गॉसियन प्रोसेस के एक्सट्रीम-वैल्यू स्टैटिस्टिक्स (Slepian's inequality और Lipschitz functions के अभिसरण का उपयोग करते हुए) का विश्लेषण करके, लेखक सिद्ध करते हैं कि $k$ और $(1+\epsilon)k$ क्लस्टर्स के बीच अपेक्षित मैक्सिमा का अंतर उन्हें उच्च प्रायिकता के साथ अलग करने के लिए पर्याप्त है।

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

Max-Sketch एल्गोरिदम: एक परम्यूटेशन-इनवेरिएंट (permutation-invariant), स्ट्रीमिंग-संगत स्केच जो निरंतर एम्बेडिंग्स पर सीधे कार्य करता है। यह निर्माण द्वारा बहुलता (multiplicity) को हटा देता है, क्योंकि एक ही वस्तु की अतिरिक्त पुनरावृत्ति क्लस्टर के "पीक" तक पहुँचने के बाद अधिकतम प्रोजेक्शन मान को नहीं बढ़ाती है।
बेहतर मेमोरी गारंटी: पेपर यह सिद्ध करता है कि प्राकृतिक क्लस्टर करने योग्य धारणा के तहत, MaxSketch $\tilde{O}(\log n / \epsilon^2)$ मेमोरी का उपयोग करके डिस्टिंक्ट काउंट का $(1+\epsilon)$ -मल्टीप्लिकेटिव एप्रोक्सिमेशन प्राप्त करता है। यह बिना ऐसी संरचना वाले सामान्य मीट्रिक स्पेस के लिए ज्ञात $\tilde{\Omega}(\sqrt{n})$ लोअर बाउंड की तुलना में एक महत्वपूर्ण सुधार है।
लर्निंग रिडक्शन (Learning Reduction): लेखक दिखाते हैं कि एक बार रैंडम प्रोजेक्शन फिक्स हो जाने के बाद, स्केच की इनपुट पर निर्भरता एक एकल स्केलर सांख्यिकी $S(X)$ में सिमट जाती है जो वास्तविक काउंट के प्रति मोनोटोन (monotone) है। फलस्वरूप, काउंट की भविष्यवाणी करना सीखने के लिए एक एक-आयामी मोनोटोन फंक्शन (रीडआउट) को फिट करना होता है, जो सैंपल-एफिशिएंट और वेल-कंडीशन्ड है।
फिक्स्ड स्केच अस्तित्व (Fixed Sketch Existence): जबकि सैद्धांतिक गारंटी शुरू में प्रत्येक स्ट्रीम के लिए ताज़ा रैंडम प्रोजेक्शन मानती है, पेपर यह सिद्ध करता है कि क्लस्टर करने योग्य स्ट्रीम के वितरण के लिए उच्च प्रायिकता के साथ एक ही फिक्स्ड रैंडम प्रोजेक्शन सेट पर्याप्त है।

प्रयोगात्मक परिणाम (Experimental Results)

लेखक तीन मोर्चों पर MaxSketch का सत्यापन करते हैं:

MNIST: कम इंट्रा-क्लास वेरिएबिलिटी वाले सेटिंग में, Max-Sketch (केवल काउंट सुपरविजन के साथ एंड-टू-एंड प्रशिक्षित) लगभग पूर्ण सटीकता प्राप्त करता है और प्रशिक्षण के दौरान देखे गए अनुक्रमों की लंबाई से काफी अधिक तक एक्सट्रपलेशन (extrapolate) करता है। यह पुष्टि करता है कि जब एम्बेडिंग्स अच्छी तरह से क्लस्टर की गई होती हैं, तो एग्रीगेशन मैकेनिज्म मजबूत होता है।
CIFAR-10: उच्च इंट्रा-क्लास वेरिएबिलिटी वाले सेटिंग में, केवल काउंट सुपरविजन से एंड-टू-एंड प्रशिक्षण प्रीट्रेन्ड फीचर्स का उपयोग करने की तुलना में कम सटीकता देता है। हालाँकि, मॉडल अभी भी काउंट्स के सही क्रम को कैप्चर करता है, जो यह सुझाव देता है कि कठिनाई क्लस्टर करने योग्य ज्यामिति को सीखने में है, न कि काउंटिंग मैकेनिज्म में।
रियल-वर्ल्ड फेस स्ट्रीम्स: फिक्स्ड प्रीट्रेन्ड एम्बेडिंग्स (DeepFace) का उपयोग करके मर्ज किए गए फेस डेटासेट्स (LFW, CelebA, Multi-PIE) पर Max-Sketch की तुलना सामान्य मीट्रिक स्पेस में रोबस्ट डिस्टिंक्ट काउंटिंग के लिए झांग (Zhang) के एल्गोरिदम से की गई है। Max-Sketch बेहतर मजबूती प्रदर्शित करता है, जो व्यापक रेंज (5,100 तक के डिस्टिंक्ट काउंट तक) में उच्च सटीकता (जैसे, $\pm 50$ एरर के भीतर $\ge 60\%$ ) बनाए रखता है, जबकि बेसलाइन एल्गोरिदम दूरी वितरण (distance distributions) के ओवरलैप के कारण विफल हो जाता है जो इसकी सख्त ज्यामितीय धारणाओं का उल्लंघन करता है।

महत्व और दावे (Significance and Claims)

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

लेखक तर्क देते हैं कि रोबस्ट काउंटिंग के लिए $\sqrt{n}$ लोअर बाउंड ऐसी संरचनाहीन वर्स्ट-केस मीट्रिक स्पेस का एक आर्टिफैक्ट (artifact) है। आधुनिक डीप लर्निंग के शासन में, जहाँ "न्यूरल कोलैप्स" (neural collapse) घने इंट्रा-क्लास क्लस्टर और अच्छी तरह से अलग-थも दिशाओं को प्रेरित करता है, यह समस्या पॉलीलॉग-मेमोरी (polylogarithmic memory) के साथ हल करने योग्य हो जाती है। Max-Sketch इस संरचना का लाभ उठाने वाला एक सैद्धांतिक रूप से ठोस, विश्लेषणात्मक रूप से सुलभ समाधान है, जो बिना किसी स्पष्ट क्लस्टरिंग या आइडेंटिटी सुपरविजन के, शोरयुक्त, उच्च-आयामी डेटा स्ट्रीम्स में कुशल डिस्टिंक्ट काउंटिंग के लिए एक मार्ग प्रदान करता है।