तकनीकी सारांश: पदानुक्रमित सामान्यीकरण (Hierarchical Normalization) के माध्यम से सटीक और नियतात्मक पैच डिस्क्रिप्टर पुनर्प्राप्ति

समस्या विवरण

उच्च-आयामी निकटतम-पड़ोसी (nearest-neighbour - NN) खोज आधुनिक AI अनुप्रयोगों के लिए मौलिक है, जिसमें रिट्रीवल-ऑगमेंटेड जनरेशन (RAG), फेस वेरिफिकेशन और विजुअल प्लेस रिकग्निशन शामिल हैं। मानक दृष्टिकोण अक्सर उप-रैखिक (sub-linear) खोज समय प्राप्त करने के लिए HNSW या IVF-PQ जैसे एप्रोक्सीमेट नियरएस्ट नेबर (ANN) इंडेक्स पर निर्भर करते हैं। हालाँकि, ये विधियाँ दो महत्वपूर्ण सीमाएँ पेश करती हैं:

1. सन्निकटन (Approximation): वे गति के लिए सटीकता का त्याग करते हैं, जिससे संभावित रूप से वह परिणाम मिल सकता है जो वास्तविक निकटतम पड़ोसी नहीं है।
2. गैर-नियतात्मकता (Non-determinism): ग्राफ निर्माण क्रम, थ्रेड काउंट या हार्डवेयर अंतर के कारण परिणाम विभिन्न रन में भिन्न हो सकते हैं, जो A/B टेस्टिंग, परिणाम कैशिंग और सुरक्षा ऑडिटिंग के लिए समस्याग्रस्त है।

HN-Desc पदानुक्रमित सामान्यीकरण (Hierarchical Normalization) को पेश करता है जो 96.9% डिस्क्रिप्टर ऊर्जा को 8 आयामों तक सीमित करता है, जिससे अनुमानित इंडेक्स के बिना प्रमाणित सटीक निकटतम-पड़ोसी पुनर्प्राप्ति संभव होती है। मोटे-से-सूक्ष्म (coarse-to-fine) पुनर्प्राप्ति के लिए गैर-समान आयामी महत्व की अवधारणा 2020 [पेटेंट 11,797,603] से संबंधित है, जो Matryoshka Representation Learning (2022) से भी पुरानी है, जो सामान्य-उद्देश्य वाले प्रतिनिधित्व के लिए नेस्टेड इलास्टिक एम्बेडिंग पर केंद्रित है। चुनौती एक पूर्ण-शक्ति (brute-force) खोज की तुलना में महत्वपूर्ण गति वृद्धि प्राप्त करने की है, जबकि प्रमाणित सटीक और पूर्णतः नियतात्मक परिणाम बनाए रखना है।

कार्यप्रणाली: पदानुक्रमित सामान्यीकरण (HN)

मुख्य योगदान पदानुक्रमित सामान्यीकरण (Hierarchical Normalization - HN) है, जो डिस्क्रिप्टर नेटवर्क के नॉर्मलाइजेशन लेयर में एक संशोधन है जो दो-चरणीय, ब्रांच-एंड-बाउंड खोज रणनीति को सक्षम बनाता है।

1. पदानुक्रमित सामान्यीकरण योजना

मानक $L_2$ सामान्यीकरण को एक ऐसी योजना से बदल दिया जाता है जो प्री-नॉर्मलाइजेशन फीचर वेक्टर $f \in \mathbb{R}^D$ (जहाँ HardNet के लिए $D=128$ है) को दो घटकों में विभाजित करती है:

• प्रमुख घटक ($f_{major}$): पहले $K$ आयाम, जिन्हें $1-\alpha$ का वर्गाकार नॉर्म (squared norm) रखने के लिए सामान्यीकृत किया गया है।
• लघु घटक ($f_{minor}$): शेष $D-K$ आयाम, जिन्हें $\alpha$ का वर्गाकार नॉर्म रखने के लिए सामान्यीकृत किया गया है।

अदिश (scalar) $\alpha \in [0, 1)$ ऊर्जा विभाजन को नियंत्रित करता है। पूर्ण वेक्टर $[f_{major}, f_{minor}]$, यूनिट नॉर्म बनाए रखता है।

प्रशिक्षण की आवश्यकता: केवल एक प्री-ट्रेन्ड HardNet मॉडल पर इस सामान्यीकरण को पोस्ट-हॉक (post-hoc) लागू करना अपर्याप्त है क्योंकि HardNet सभी आयामों में ऊर्जा को समान रूप से वितरित करता है। शोध पत्र यह प्रदर्शित करता है कि प्रमुख प्रिफिक्स (prefix) में विभेदक ऊर्जा (discriminative energy) को स्थानांतरित करने के लिए नेटवर्क को HN के साथ फाइन-ट्यून करना आवश्यक है, जिससे पहले $K$ आयाम पूर्ण समानता के विश्वसनीय भविष्यवक्ता बन सकें।

2. स्वीकार्य ऊपरी सीमा (Admissible Upper Bound)

यह विधि पूर्ण आंतरिक उत्पाद (inner product) समानता पर एक सटीक ऊपरी सीमा स्थापित करने के लिए कॉची-श्वार्ज़ (Cauchy–Schwarz) असमानता पर निर्भर करती है। एक क्वेरी $q$ और डेटाबेस प्रविष्टि $x$ के लिए:
$$\langle q, x \rangle = \langle q_{major}, x_{major} \rangle + \langle q_{minor}, x_{minor} \rangle$$
चूँकि $\|q_{minor}\| = \|x_{minor}\| = \sqrt{\alpha}$, लघु आंतरिक उत्पाद $\alpha$ द्वारा सीमित है:
$$\langle q, x \rangle \leq \text{dot}_K(q, x) + \alpha$$
यहाँ, $\text{dot}_K(q, x)$ केवल $K$-आयामी प्रमुख घटकों का आंतरिक उत्पाद है।

3. दो-चरणीय सटीक खोज एल्गोरिदम

पुनर्प्राप्ति प्रक्रिया (एल्गोरिदम 1) इस प्रकार चलती है:

1. चरण 1 (प्रमुख स्कैन): डेटाबेस के सभी $N$ प्रविष्टियों के लिए $K$-आयामी डॉट उत्पाद की गणना करें। उच्चतम स्कोर $s_b$ वाले उम्मीदवार $b$ की पहचान करें।
2. आरंभीकरण (Initialization): $b$ के लिए पूर्ण 128-आयामी आंतरिक उत्पाद की गणना करें ताकि वर्तमान सर्वोत्तम स्कोर $s_{best}$ स्थापित किया जा सके।
3. चरण 2 (स्वीकार्य छंटनी/Pruning): शेष प्रविष्टियों के माध्यम से पुनरावृत्ति करें। प्रत्येक प्रविष्टि $i$ के लिए:
   • ऊपरी सीमा की गणना करें: $s_i + \alpha$।
   • छंटनी (Prune): यदि $s_i + \alpha \leq s_{best}$, तो पूर्ण मूल्यांकन को छोड़ दें (वह प्रविष्टि निकटतम पड़ोसी नहीं हो सकती)।
   • मूल्यांकन: यदि सीमा पार हो जाती है, तो पूर्ण 128-आयामी डॉट उत्पाद की गणना करें। यदि यह $s_{best}$ से अधिक हो जाता है, तो $s_{best}$ और सर्वश्रेष्ठ इंडेक्स को अपडेट करें।

4. नियतात्मकता और दक्षता

• नियतात्मकता (Determinism): एक निश्चित डेटाबेस क्रम के लिए एल्गोरिदम नियतात्मक है। प्रमुख स्कोर में होने वाले 'टाई' (ties) को इंडेक्स क्रम द्वारा तोड़ा जाता है। चूँकि फ्लोटिंग-पॉइंट डिस्क्रिप्टर शायद ही कभी सटीक आंतरिक-उत्पाद टाई उत्पन्न करते हैं, इसलिए आउटपुट डेटाबेस क्रमिंग के प्रति प्रभावी रूप से स्वतंत्र है।
• मेमोरी लेआउट: गति को अधिकतम करने के लिए, लेखक स्ट्रक्चर-ऑफ-एरेज़ (SOA) लेआउट का उपयोग करते हैं। यह प्रमुख और लघु घटकों को अलग-अलग निरंतर सरणियों (contiguous arrays) में संग्रहीत करता है, जिससे चरण 1 केवल कॉम्पैक्ट मेजर सरणी (जैसे, $K=8, N=500k$ के लिए 16 MB) को स्कैन कर पाता है, जिससे पूर्ण 256 MB डिस्क्रिप्टर बैंक को लोड किए बिना मेमोरी बैंडविड्थ का उपयोग कम होता है और कैश उपयोगिता में सुधार होता है।

मुख्य योगदान

1. सटीक पुनर्प्राप्ति (प्रमेय 1): शोध पत्र सिद्ध करता है कि HN-आधारित दो-चरणीय खोज वही इंडेक्स लौटाती है जो एक व्यापक (exhaustive) पूर्ण-वेक्टर खोज द्वारा प्राप्त होता है। गति वृद्धि में शून्य पुनर्प्राप्ति त्रुटि होती है।
2. नियतात्मकता (प्रमेय 2): यदि डेटाबेस क्रम स्थिर है, तो विधि रन, इंडेक्स बिल्ड और थ्रेड काउंट के बीच पुनरुत्पादनीय (reproducible) है। यह HNSW और IVF-PQ के विपरीत है, जो गैर-नियतात्मक हैं।
3. दक्षता: स्वीकार्य सीमा और SOA लेआउट का लाभ उठाकर, यह विधि केवल डेटाबेस के एक बहुत छोटे हिस्से का पूर्ण मूल्यांकन करके महत्वपूर्ण वॉल-क्लॉक स्पीड-अप प्राप्त करती है।

प्रयोगात्मक परिणाम

विधि का मूल्यांकन UBC पैच डेटासेट (Notredame ट्रेनिंग, Trevi और Halfdome टेस्टिंग) पर एक HardNet बैकबोन के साथ किया गया जिसे HN के साथ फाइन-ट्यून किया गया था।

गुणवत्ता-गति ट्रेड-ऑफ

• कॉन्फ़िगरेशन $K=16, \alpha=1/8$:
  • स्पीड-अप: ब्रूट-फोर्स की तुलना में Trevi पर $7.2\times$ और Halfdome पर $5.8\times$।
  • गुणवत्ता: Trevi पर FPR@95 प्रीट्रेन्ड बेसलाइन (0.0062) से केवल मामूली रूप से बढ़कर 0.0064 हुआ।
  • छंटनी (Pruning): 98.8% प्रविष्टियों को पूर्ण मूल्यांकन से बचा लिया गया।
• कॉन्फ़िगरेशन $K=8, \alpha=1/32$:
  • स्पीड-अप: Trevi पर $13.7\times$ और Halfdome पर $12.7\times$।
  • गुणवत्ता: Trevi पर FPR@95 0.0397 था ($K=16$ की तुलना में अधिक लेकिन फिर भी प्रतिस्पर्धी)।
  • छंटनी (Pruning): केवल 0.4% प्रविष्टियों को पूर्ण मूल्यांकन की आवश्यकता पड़ी।

HNSW के साथ तुलना

• छोटे डेटासेट ($N=1,000$): HN ($K=16$) ने 100% सटीक रिकॉल के साथ $9.5\times$ स्पीड-अप प्राप्त किया। HNSW कॉन्फ़िगरेशन या तो ब्रूट-फोर्स से धीमे थे या कम रिकॉल प्रदान कर रहे थे।
• बड़े डेटासेट ($N=99,000$): HNSW ($ef=50$) ने उच्च थ्रूपुट ($111.9\times$) प्राप्त किया लेकिन अनिश्चित रिकॉल के साथ (सिंथेटिक डेटा पर ~94% तक गिर गया)। HN ने $12.5\times$ स्पीड-अप के साथ 100% सटीक रिकॉल बनाए रखा।
• स्केलेबिलिटी: HN का स्पीड-अप काफी हद तक $N$ से स्वतंत्र है (मेमोरी बैंडविड्थ द्वारा सीमित), जबकि HNSW का लाभ $N$ के साथ बढ़ता है क्योंकि इसकी जटिलता उप-रैखिक (sub-linear) है।

महत्व और दावे

शोध पत्र इस कार्य को उच्च-आयामी पुनर्प्राप्ति के "सटीकता बनाम गति" दुविधा के समाधान के रूप में प्रस्तुत करता है।

• सुरक्षा और विश्वसनीयता: लेखक जोर देते हैं कि सुरक्षा-महत्वपूर्ण अनुप्रयोगों (जैसे, फोरेंसिक पहचान, स्वायत्त नेविगेशन) के लिए, ANN विधियों की "साइलेंट एरर्स" (silent errors) अस्वीकार्य हैं। HN एक गणितीय शुद्धता प्रमाण (प्रमेय 1) प्रदान करता है।
• पुनरुत्पादनीयता: HN की नियतात्मक प्रकृति को रिग्रेशन ट्रैकिंग, A/B टेस्टिंग और परिणाम कैशिंग के लिए आवश्यक बताया गया है, जो वे क्षेत्र हैं जहाँ HNSW और MRL पाइपलाइन रन-टू-रन वेरिएंस के कारण विफल होते हैं।
• प्रशिक्षण अंतर्दृष्टि: यह कार्य दर्शाता है कि डिस्क्रिप्टर की गुणवत्ता को संपीड़न के दौरान कैसे संरक्षित किया जा सकता है—पोस्ट-हॉक आयामी कमी (जैसे PCA) पर भरोसा करने के बजाय, जो HardNet डिस्क्रिप्टर के लिए विफल हो जाता है—एक सक्रिय नेटवर्क प्रशिक्षण के माध्यम से जो विभेदक जानकारी को एक प्रिफिक्स में केंद्रित करता है।

लेखक निष्कर्ष निकालते हैं कि अभ्यासकर्ता बिना सटीकता या नियतात्मकता से समझौता किए ( $K$ और $\alpha$ को ट्यून करके) गुणवत्ता-गति पारेटो फ्रंट (Pareto frontier) पर किसी भी बिंदु को चुन सकते हैं, जो उन परिदृश्यों के लिए एक मजबूत विकल्प प्रदान करता है जहाँ पुनरुत्पादनीयता और शुद्धता सर्वोतम है।