🤖 AI

Probabilistic Kernel Function for Fast Angle Testing

यह शोध पत्र उच्च-आयामी स्थानों में तेज़ कोण परीक्षण के लिए नियतात्मक, प्रोजेक्शन-आधारित संभाव्य कर्नेल फलनों को प्रस्तुत करता है जो स्पर्शोन्मुखी धारणाओं को समाप्त करते हैं और अनुमानित निकटतम पड़ोसी खोज में HNSW की तुलना में 2.5x–3x उच्च क्वेरी थ्रूपुट प्राप्त करते हैं।

मूल लेखक: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa

प्रकाशित 2026-03-03

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

CC BY 4.0

मूल लेखक: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa

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

कल्पना कीजिए कि आप अरबों किताबों वाली एक विशाल लाइब्रेरी चला रहे हैं, लेकिन शीर्षकों के बजाय, हर किताब को एक जटिल, बहु-आयामी "फिंगरप्रिंट" (एक वेक्टर) द्वारा दर्शाया गया है। आपके पास एक 'क्वेरी बुक' (खोज वाली किताब) है, और आप पूरी लाइब्रेरी में सबसे समान 10 किताबें ढूंढना चाहते हैं। यह एप्रोक्सीमेट निएरेस्ट नेबर सर्च (ANNS) की समस्या है।

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

यह पेपर एक नया, स्मार्ट स्पीड फ़िल्टर पेश करता है जिसे KS (स्पीड के लिए कर्नल फंक्शन) कहा जाता है, जो इन समान किताबों को खोजने की प्रक्रिया को वर्तमान सर्वोत्तम तरीकों की तुलना में 2.5 से 3 गुना तेज़ बनाता है।

यह कैसे काम करता है, इसका विवरण सरल उपमाओं (analogies) का उपयोग करके यहाँ दिया गया है:

1. पुराना तरीका: "गौसियन गेस" (The Gaussian Guess)

लंबे समय से, फ़िल्टर करने का सबसे अच्छा तरीका CEOs (कन्कोमिटेंट्स ऑफ एक्सट्रीम ऑर्डर स्टैटिस्टिक्स) था।

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

2. नया तरीका: "स्ट्रक्चर्ड कंपास" (The Structured Compass)

लेखकों ने महसूस किया कि "रुई जैसा पदार्थ" (गौसियन डिस्ट्रीब्यूशन) असली रहस्य नहीं था। असली रहस्य किताब और धागे के बीच का कोण (angle) था।

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

3. दो महाशक्तियाँ (Two Superpowers)

पेपर दो अलग-अलग कार्यों के लिए दो विशिष्ट उपकरण (कर्नल फंक्शन्स) प्रस्तावित करता है:

टूल 1 (KS1): "बेहतर कंपैरेटर"
- काम: "क्या किताब A, किताब B की तुलना में क्वेरी के अधिक समान है?"
- यह कैसे मदद करता है: यह "मैक्सिमम इनर प्रोडक्ट" (जैसे उपयोगकर्ता के लिए सबसे प्रासंगिक विज्ञापन ढूंढना) जैसे कार्यों में पुराने "गौसियन" तरीके को बदल देता है।
- परिणाम: यह पुराने तरीके की तुलना में थोड़ा अधिक सटीक है, जिसका अर्थ है कि आप कम गलतियों के साथ सही किताबें ढूंढ लेते हैं।
टूल 2 (KS2): "सुपर फास्ट गेटकीपर"
- काम: "क्या किताब A इतनी समान है कि उसकी जांच करने की ज़रूरत है?"
- यह कैसे मदद करता है: यह बड़ा विजेता है। इसका उपयोग ग्राफ-आधारित खोज (जैसे लोकप्रिय HNSW एल्गोरिदम) में किया जाता है। एक भूलभुलैया की कल्पना करें जहाँ आप बाहर निकलने का रास्ता ढूंढ रहे हैं। पुराने गेटकीपर (PEOs) हर चौराहे पर यह तय करने के लिए कि कौन सा रास्ता लेना है, बहुत देर तक सोचते रहते थे।
- KS2 का जादू: नया गेटकीपर बिजली की तरह तेज़ है। यह चौराहे को देखता है और तुरंत कहता है, "नहीं, यह रास्ता बंद गली है," या "हाँ, इस तरफ जाओ!" बिना किसी भारी गणित के।
- परिणाम: क्योंकि यह बहुत तेज़ी से इतने सारे डेड एंड्स (बंद रास्तों) को छोड़ देता है, इसलिए पूरी खोज प्रक्रिया 2.5 से 3 गुना तेज़ (Queries Per Second में मापा गया) हो जाती है और फिर भी सही किताबें ढूंढ लेती है।

4. "क्रॉस-पॉलीटोप" का गुप्त नुस्खा (The Cross-Polytope Secret Sauce)

उन्होंने इस परफेक्ट कंपास को कैसे बनाया?

उपमा: बोर्ड पर रैंडम तरीके से डार्ट्स फेंकने (गौसियन) के बजाय, उन्होंने उन्हें एक क्रॉस-पॉलीटोप (सोचें एक 3D स्टार या अष्टफलक/octahedron) नामक विशिष्ट ज्यामितीय आकार में व्यवस्थित किया।
यह क्यों काम करता है: यह आकार स्थान (space) को बहुत अधिक समान रूप से कवर करता है। यह सुनिश्चित करता है कि आपकी "क्वेरी बुक" कहीं भी हो, वहां हमेशा एक "सुई" बहुत करीब मौजूद हो। यह "रेफरेंस एंगल" (दूरी) को कम करता है, जिससे भविष्यवाणी अविश्वसनीय रूप से सटीक हो जाती है।

सारांश: आपको इसकी परवाह क्यों करनी चाहिए?

यदि आप अनुशंसा (recommendations), खोज इंजन, या इमेज रिकग्निशन के लिए AI का उपयोग करते हैं, तो यह पेपर आपको सटीकता खोए बिना अपने सिस्टम को काफी तेज़ और सस्ता बनाने का एक तरीका प्रदान करता है।

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

लेखकों ने अपने कोड को ओपन-सोर्स भी कर दिया है, ताकि डेवलपर्स आज ही अपने स्वयं के AI अनुप्रयोगों को गति देने के लिए इस "सुपर-कंपास" का उपयोग करना शुरू कर सकें।

यहाँ शोध पत्र "Probabilistic Kernel Function for Fast Angle Testing" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र उच्च-आयामी यूक्लिडियन स्पेस (high-dimensional Euclidean spaces) में समानता खोज (similarity search) की चुनौती को संबोधित करता है, विशेष रूप से एंगल टेस्टिंग (angle testing) पर ध्यान केंद्रित करता है। जबकि सटीक कोण गणना (कोसाइन सिमिलरिटी) की लागत $O(d)$ होती है, जो उच्च आयामों के लिए अत्यधिक महंगी है, कई अनुप्रयोगों में केवल संभाव्य निर्णयों (probabilistic decisions) की आवश्यकता होती है न कि सटीक मानों की। लेखक दो मुख्य समस्याओं को परिभाषित करते हैं:

एंगल कंपैरिजन (समस्या 1.1): एक क्वेरी $q$ और दो डेटा वेक्टर्स $v_1, v_2$ दिए जाने पर, उच्च संभाव्यता के साथ यह निर्धारित करना कि $\langle q, v_1 \rangle > \langle q, v_2 \rangle$ है या नहीं, जिसमें $o(d)$ कंप्यूटेशनल लागत वाला एक कर्नेल फंक्शन उपयोग किया जाता है।
एंगल थ्रेशोल्डिंग (समस्या 1.2): एक थ्रेशोल्ड $\theta$ दिए जाने पर, यह निर्धारित करना कि $q$ और $v$ के बीच का कोण $\theta$ से कम है या नहीं (अर्थात $\langle q, v \rangle > \cos \theta$ ), फिर से $o(d)$ लागत के साथ।

मौजूदा दृष्टिकोणों की सीमाएँ:
वर्तमान अत्याधुनिक विधियाँ, जैसे कि CEOs (Concomitants of Extreme Order Statistics) और PEOs (जो HNSW जैसे ग्राफ-आधारित ANNS में उपयोग किए जाते हैं), गाऊसी वितरण (Gaussian distribution) से प्राप्त रैंडम प्रोजेक्शन वेक्टर्स पर निर्भर करती हैं। ये विधियाँ एक सैद्धांतिक लेम्मा (लेम्मा 1.3) पर निर्भर करती हैं जो यह मानती है कि प्रोजेक्शन वेक्टर्स की संख्या $m \to \infty$ है। व्यवहार में, $m$ परिमित (finite) होता है, जिससे सैद्धांतिक अंतराल और उप-इष्टतम प्रदर्शन होता है क्योंकि गाऊसी वितरण "रेफरेंस एंगल" (क्वेरी और सबसे अच्छी तरह से मेल खाने वाले प्रोजेक्शन वेक्टर के बीच का कोण) को न्यूनतम करने की गारंटी नहीं देता है।

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

लेखक प्रोबेबिलिस्टिक कर्नेल फंक्शन्स (Probabilistic Kernel Functions) पर आधारित एक नया ढांचा प्रस्तावित करते हैं जो एसिम्प्टोटिक धारणाओं ( $m \to \infty$ ) की आवश्यकता को समाप्त करता है और प्रोजेक्शन वेक्टर्स के लिए एक नियत (deterministic) संरचना का लाभ उठाता है।

A. मुख्य अवधारणा: रेफरेंस एंगल्स (Reference Angles)

गाऊसी रैंडमनेस पर निर्भर रहने के बजाय, लेखक एक रेफरेंस एंगल $\psi$ पेश करते हैं, जिसे क्वेरी वेक्टर $q$ और उसके "रेफरेंस वेक्टर" $Z_S(q)$ (सेट $S$ में वह प्रोजेक्शन वेक्टर जिसका $q$ के साथ अधिकतम इनर प्रोडक्ट है) के बीच के कोण के रूप में परिभाषित किया गया है।

मुख्य अंतर्दृष्टि: कोण अनुमान की सटीकता मुख्य रूप से इस रेफरेंस एंगल $\psi$ के परिमाण पर निर्भर करती है। $\psi$ जितना छोटा होगा, सटीकता उतनी ही अधिक होगी।
नियतिवादी संरचना (Deterministic Structure): लेखक प्रोजेक्शन वेक्टर्स के सेट $S$ को इस तरह डिजाइन करते हैं कि अपेक्षित रेफरेंस एंगल को कम किया जा सके, न कि रैंडम गाऊसी सैंपलिंग पर निर्भर रहें।

B. प्रस्तावित कर्नेल फंक्शन्स (Proposed Kernel Functions)

दो समस्याओं के लिए दो कर्नेल फंक्शन परिभाषित किए गए हैं:

$K^1_S(q, v)$ (कंपैरिजन के लिए): $K^1_S(q, v) = \langle v, Z_{HS}(q) \rangle$ $K_{S}^{1} (q, v) = ⟨ v, Z_{H S} (q)⟩$ ।
- यहाँ, $H$ एक रैंडम रोटेशन मैट्रिक्स है, और $Z_{HS}(q)$ रोटेटेड सेट $HS $में$ q$ के सबसे निकटतम प्रोजेक्शन वेक्टर है।
$K^2_S(q, v)$ (थ्रेशोल्डिंग के लिए): $K^2_S(q, v) = \langle Hq, Z_S(Hv) \rangle / A_S(Hv)$ $K_{S}^{2} (q, v) = ⟨ H q, Z_{S} (H v)⟩ / A_{S} (H v)$ ।
- यह अनुमान को सामान्य (normalize) करने के लिए रेफरेंस एंगल जानकारी $A_S(\cdot)$ (रेफरेंस वेक्टर के साथ इनर प्रोडक्ट) को शामिल करता है, जिससे सटीक थ्रेशोल्डिंग संभव होती है।

C. प्रोजेक्शन वेक्टर्स का विन्यास ( $S$ )

रेफरेंस एंगल को कम करने के लिए, लेखक सेट $S$ के लिए दो विशिष्ट संरचनाएं प्रस्तावित करते हैं (जो रैंडम गाऊसी वेक्टर्स का स्थान लेती हैं):

एंटीपोडल प्रोजेक्शंस ( $S_{sym}$ ): एंटीपोडल बिंदुओं के जोड़े के रूप में स्फीयर (sphere) पर बिंदु उत्पन्न करता है। यह समरूपता सुनिश्चित करता है और तेज़ गणना (मूल्यांकन समय को आधा करना) की अनुमति देता है।
मल्टीपल क्रॉस-पॉलीटोप्स ( $S_{pol}$ ): रोटेटेड क्रॉस-पॉलीटोप्स (सामान्यीकृत अष्टफलक/octahedrons) का उपयोग करके $S$ का निर्माण करता है। चूंकि क्रॉस-पॉलीटोप के शीर्ष $m=2d$ के लिए इष्टतम कवरेज प्रदान करते हैं, इसलिए कई ऐसी संरचनाओं को रोटेट और संयोजित करने से स्फीयर का एक अत्यधिक कुशल कवरेज बनता है, जो वर्स्ट-केस रेफरेंस एंगल को न्यूनतम करता है।

D. अनुप्रयोग (Applications)

$KS_1$ : मैक्सिमम इनर प्रोडक्ट सर्च (MIPS) के लिए CEOs को बेहतर बनाने हेतु $K^1_S$ पर आधारित एक प्रोजेक्शन तकनीक।
$KS_2$ टेस्ट: समानता ग्राफ (जैसे HNSW) के लिए एक नया प्रोबेबिलिस्टिक रूटिंग टेस्ट। यह PEOs टेस्ट को बदल देता है, जो उन पड़ोसियों के लिए सटीक दूरी गणना को छोड़ने के लिए $K^2_S$ से प्राप्त असमानता का उपयोग करता है जो निकटतम पड़ोसी होने की संभावना कम रखते हैं।

3. प्रमुख योगदान (Key Contributions)

सैद्धांतिक प्रगति: यह शोध पत्र गैर-एसिम्प्टोटिक (non-asymptotic) सैद्धांतिक गारंटी प्रदान करता है। पिछली कार्यप्रणालियों के विपरीत जिन्हें $m \to \infty$ की आवश्यकता थी, प्रस्तावित कर्नेल फंक्शन परिमित $m$ के लिए संभाव्यता गारंटी को संतुष्ट करते हैं, जो रेफरेंस एंगल और प्रोजेक्शन मान के बीच एक नियतिवादी संबंध (लेम्मा 4.2 और 4.3) पर आधारित है।
इष्टतम प्रोजेक्शन संरचनाएं: लेखक प्रदर्शित करते हैं कि प्रोजेक्शन वेक्टर्स के लिए गाऊसी वितरण उप-इष्टतम है। वे $S_{sym}$ और $S_{pol}$ प्रस्तावित करते हैं, जो छोटे रेफरेंस एंगल और उच्च अनुमान सटीकता प्राप्त करते हैं।
नया रूटिंग टेस्ट ( $KS_2$ ): ग्राफ-आधारित ANNS के लिए एक सरल और अधिक सटीक रूटिंग टेस्ट, जिसे PEOs की तुलना में कम संग्रहीत स्थिरांक (constants) की आवश्यकता होती है, जिससे इंडेक्स का आकार छोटा हो जाता है।
व्यापक विश्लेषण: यह शोध पत्र उत्पाद-क्वांटाइजेशन जैसी संरचना में स्तरों ( $L$ ) की संख्या और रेफरेंस एंगल के बीच संबंध स्थापित करता है, यह दिखाते हुए कि $L$ को बढ़ाने से सटीकता में काफी सुधार होता है।

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

लेखकों ने छह उच्च-आयामी वास्तविक दुनिया के डेटासेट्स (Word, GloVe, SIFT, Tiny, GIST) पर अपनी विधियों का मूल्यांकन किया।

CEOs के साथ तुलना ( $KS_1$ बनाम CEOs):
- $KS_1$ ने विभिन्न डेटासेट्स और प्रोब सेटिंग्स में मानक CEOs की तुलना में रिकॉल दरों में मामूली लेकिन निरंतर सुधार (0.8% तक) प्राप्त किया।
- $S_{pol}$ कॉन्फ़िगरेशन ने आम तौर पर $S_{sym}$ से बेहतर प्रदर्शन किया, जो क्रॉस-पॉलीटोप संरचनाओं के लाभ की पुष्टि करता है।
ANNS प्रदर्शन ( $HNSW + KS_2$ ):
- थ्रूपुट (Throughput): $HNSW + KS_2$ ने मानक HNSW की तुलना में 2.5× से 3× अधिक क्वेरी-पर-सेकंड (QPS) प्राप्त किया।
- स्टेट-ऑफ-द-आर्ट तुलना: इसने रिकॉल को बनाए रखते हुए या सुधारते हुए, पिछले सर्वश्रेष्ठ ग्राफ-आधारित दृष्टिकोण, HNSW+PEOs की तुलना में QPS में 10% से 30% बेहतर प्रदर्शन किया।
- इंडेक्स आकार: $KS_2$ टेस्ट को PEOs की तुलना में कम स्कैलर्स को स्टोर करने की आवश्यकता थी, जिसके परिणामस्वरूप इंडेक्स आकार में 5% की कमी आई।
- मजबूती (Robustness): विधि ने विभिन्न रिकॉल स्तरों पर बेहतर प्रदर्शन दिखाया, विशेष रूप से 0.75–0.85 रिकॉल रेंज में जहाँ रूटिंग दक्षता महत्वपूर्ण होती है।

5. महत्व (Significance)

यह शोध पत्र उच्च-आयामी समानता खोज के क्षेत्र में एक महत्वपूर्ण योगदान देता है:

सिद्धांत और व्यवहार के बीच सेतु बनाना: यह एक नियत, रेफरेंस-एंगल-आधारित ढांचे को पेश करके मौजूदा रैंडम प्रोजेक्शन विधियों की सैद्धांतिक सीमा ( $m \to \infty$ पर निर्भरता) को हल करता है।
ग्राफ खोज को अनुकूलित करना: एक तेज़ और अधिक सटीक रूटिंग टेस्ट ( $KS_2$ ) प्रदान करके, यह सबसे लोकप्रिय श्रेणी के ANNS एल्गोरिदम (HNSW) को महत्वपूर्ण रूप से तेज करता है, जिससे बड़े पैमाने पर वेक्टर खोज अधिक कुशल हो जाती है बिना सटीकता से समझौता किए।
प्रोजेक्शन रणनीतियों को पुनर्परिभाषित करना: यह प्रोजेक्शन वेक्टर्स के लिए गाऊसी वितरण पर लंबे समय से चले आ रहे भरोसे को चुनौती देता है, यह सिद्ध करते हुए कि संरचित, ज्यामितीय रूप से अनुकूलित सेट (जैसे क्रॉस-पॉलीटोप्स) एंगल टेस्टिंग कार्यों के लिए बेहतर परिणाम देते हैं।

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