📊 statistics

Spectral bandits for smooth graph functions with applications in recommender systems

यह शोध पत्र स्मूथ ग्राफ फंक्शन्स के लिए स्पेक्ट्रल बैंडिट्स की अवधारणा प्रस्तुत करता है, जिसमें दो कुशल एल्गोरिदम का प्रस्ताव दिया गया है जो संचयी रिग्रेट (cumulative regret) को कम करने के लिए एक छोटे प्रभावी आयाम (effective dimension) का लाभ उठाते हैं, जैसे कि कंटेंट-आधारित अनुशंसा (content-based recommendation) जैसी ऑनलाइन लर्निंग समस्याएं, जहाँ वस्तुओं की रेटिंग ग्राफ पर उनके पड़ोसियों के समान होती है।

मूल लेखक: Tomáš Kocák, Michal Valko, Rémi Munos, Branislav Kveton, Shipra Agrawal

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

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

CC BY 4.0

मूल लेखक: Tomáš Kocák, Michal Valko, Rémi Munos, Branislav Kveton, Shipra Agrawal

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

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

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

यह वह वास्तविक दुनिया की समस्या है जिसे यह शोध पत्र हल करता है: आप एक विशाल नेटवर्क में सबसे अच्छी वस्तु (रेस्टोरेंट) कैसे खोज सकते हैं जब आप केवल कुछ ही परीक्षण कर सकते हैं, यह जानते हुए कि "पड़ोसी" समान होते हैं?

पुराना तरीका बनाम नया तरीका

पुराना तरीका (लीनियर बैंडिट्स - Linear Bandits):
कल्पना कीजिए कि आप शहर के हर एक रेस्टोरेंट के बारे में यह समझने की कोशिश कर रहे हैं कि प्रत्येक एक पूरी तरह से अद्वितीय, असंबंधित रहस्य है। आपको हर एक के बारे में जानकारी पाने के लिए हजारों जगहों पर जाना होगा। यदि शहर में 10,000 रेस्टोरेंट हैं, तो आपको निश्चित होने के लिए 10,000 बार जाने की आवश्यकता हो सकती है। यह बहुत धीमा और अक्षम है।

नया तरीका (स्पेक्ट्रल बैंडिट्स - Spectral Bandits):
लेखक एक स्मार्ट दृष्टिकोण प्रस्तावित करते हैं। हर रेस्टोरेंट को एक अद्वितीय और असंबंधित रहस्य मानने के बजाय, वे महसूस करते हैं कि शहर का "स्वाद" कुछ सरल पैटर्न (जैसे, "डाउनटाउन फैंसी है," "उपनगर साधारण हैं") द्वारा वर्णित किया जा सकता है। वे इन पैटर्नों को मैप करने के लिए ग्राफ लैपलेसियन आइजनवेक्टर्स (Graph Laplacian Eigenvectors) नामक एक गणितीय उपकरण का उपयोग करते हैं।

इन पैटर्नों को शहर के "गीत" को बनाने वाले संगीत के सुरों (musical notes) के रूप में सोचें:

"कम सुर" (छोटे आइजनवैल्यूज़) बड़े, सुचारू रुझानों (trends) का प्रतिनिधित्व करते हैं (जैसे, पूरा उत्तर भाग ट्रेंडी है)।
"उच्च सुर" (बड़े आइजनवैल्यूज़) सूक्ष्म, अराजक विवरणों का प्रतिनिधित्व करते हैं।

पेपर का तर्क है कि शहर का "स्वाद" मुख्य रूप से इन्हीं कुछ कम सुरों से बना है। यह एक सुरीला गीत है, न कि कोई अराजक शोर।

मुख्य अवधारणा: "प्रभावी आयाम" (Effective Dimension)

लेखक एक चतुर विचार पेश करते हैं जिसे प्रभावी आयाम (Effective Dimension) कहा जाता है।

कल्पना कीजिए कि आपके पास 1,000,000 किताबों वाला एक पुस्तकालय है। यदि आप केवल 5 मुख्य शैलियों (रहस्य, विज्ञान कथा, रोमांस, आदि) की परवाह करते हैं, तो आपको पुस्तकालय को समझने के लिए 1,000,000 किताबें पढ़ने की आवश्यकता नहीं है। आपको केवल उन 5 शैलियों को समझने की आवश्यकता है।

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

दो एल्गोरिदम (गाइड)

यह पेपर इस समस्या को हल करने के लिए दो विशिष्ट "गाइड" (एल्गोरिदम) प्रस्तावित करता है:

SpectralUCB (आशावादी खोजकर्ता - The Optimistic Explorer):
यह गाइड एक सतर्क खोजकर्ता की तरह है जो कहता है, "मुझे लगता है कि यह पड़ोस अच्छा है, लेकिन मैं 100% निश्चित नहीं हूँ। चलिए, मैं इसे एक मौका देता हूँ और इसे चेक करता हूँ।" यह अपने अनुमानों के चारों ओर एक "कॉन्फिडेंस बबल" (विश्वास का घेरा) की गणना करने के लिए गणित का उपयोग करता है। यदि कोई पड़ोस अनखोजा है लेकिन अपने पड़ोसियों के आधार पर आशाजनक दिखता है, तो गाइड वहां जाता है।

परिणाम: यह वस्तुओं को तेज़ी से पाता है और गणितीय रूप से गारंटी देता है कि यह बहुत अधिक गलतियाँ नहीं करेगा।

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

परिणाम: यह पहले गाइड की तुलना में गणना करने में बहुत अधिक तेज़ होता है। यह एक सहज अहसास की तरह है जो सांख्यिकीय रूप से ठोस है।

उन्होंने क्या पाया (परिणाम)

लेखकों ने अपने गाइडों का परीक्षण दो तरीकों से किया:

सिंथेटिक शहर (Synthetic Cities): उन्होंने एक नकली शहर (जैसे कि बाराबेसी-अल्बर्ट नेटवर्क) का अनुकरण करने के लिए नकली ग्राफ बनाए।
वास्तविक शहर (मूवीलेंस - MovieLens): उन्होंने मूवी रेटिंग का एक वास्तविक डेटासेट उपयोग किया। इस परिदृश्य में, "पड़ोस" फिल्में हैं, और "किनारे" (edges) उन फिल्मों को जोड़ते हैं जो समान हैं (जैसे, दो साइंस-फिक्शन फिल्में)।

निष्कर्ष:

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

सारांश

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

तकनीकी सारांश: स्मूथ ग्राफ फंक्शन्स के लिए स्पेक्ट्रल बैंडिट्स

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र एक मल्टी-आर्म्ड बैंडिट समस्या को संबोधित करता है जहाँ 'आर्म्स' (arms) एक ज्ञात ग्राफ $G=(V, E)$ के नोड्स के अनुरूप होते हैं, और किसी आर्म को खींचने (pulling) का अपेक्षित प्रतिफल (payoff) ग्राफ पर परिभाषित एक स्मूथ फंक्शन द्वारा निर्धारित होता है। इस सेटिंग में, रिवॉर्ड फंक्शन $f$ को ग्राफ लैपलेसियन $L$ के आइगेनवेक्टर्स (eigenvectors) के एक रैखिक संयोजन (linear combination) के रूप में माना जाता है। विशेष रूप से, यदि $Q$ में $L$ के आइगेनवेक्टर्स कॉलम के रूप में हैं, तो नोड $v$ के लिए रिवॉर्ड $f_\alpha(v) = \langle x_v, \alpha^* \rangle$ है, जहाँ $x_v$ , $Q$ की $v$ -वीं पंक्ति है और $\alpha^*$ एक अज्ञात वेट वेक्टर है।

मुख्य चुनौती तब उत्पन्न होती है जब नोड्स की संख्या $N$ (और इस प्रकार फीचर स्पेस का आयाम $D=N$ ) बहुत बड़ी होती है, जो संभावित रूप से लर्निंग प्रक्रिया के टाइम होराइजन $T$ ( $T < N$ ) से अधिक होती है। मानक लीनियर बैंडिट एल्गोरिदम, जिनका रेग्रेट (regret) आमतौर पर एम्बिएंट डायमेंशन $D$ या $K$ आर्म्स के साथ स्केल करता है, इस स्थिति में खराब प्रदर्शन करेंगे। यह शोध पत्र मानता है कि वास्तविक फंक्शन "स्मूथ" है, जिसका अर्थ है कि बड़े आइगेनवैल्यू वाले आइगेनवेक्टर्स से जुड़े गुणांक (coefficients) छोटे हैं, जबकि छोटे आइगेनवैल्यू वाले गुणांक बड़े हैं।

कार्यप्रणाली (Methodology)
लेखक दो एल्गोरिदम प्रस्तावित करते हैं जो ग्राफ के स्पेक्ट्रल गुणों का लाभ उठाकर रेगेट बाउंड्स को पूर्ण आयाम $N$ के बजाय एक "प्रभावी आयाम" (effective dimension) $d$ के साथ स्केल करते हैं।

प्रभावी आयाम (Effective Dimension - $d$ ): शोध पत्र नियमित लैपलेसियन $\Lambda = \Lambda_L + \lambda I$ के आइगेनवैल्यूज के विकास के आधार पर प्रभावी आयाम $d$ की एक औपचारिक परिभाषा प्रस्तुत करता है। $d$ को सबसे बड़े पूर्णांक के रूप में परिभाषित किया गया है कि $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$ । यह मीट्रिक समस्या में "प्रासंगिक" आयामों की संख्या को कैप्चर करता है, जो आमतौर पर वास्तविक दुनिया के ग्राफों में $N$ से बहुत कम होता है।
SpectralUCB: यह एल्गोरिदम LinUCB का एक संशोधन है। यह स्पेक्ट्रल बेसिस का उपयोग करके $\alpha^*$ के लिए एक रेगुलराइज्ड लीस्ट-स्क्वेयर्स एस्टीमेटर का उपयोग करता है। महत्वपूर्ण रूप से, यह पूर्ण आयाम $D$ के बजाय प्रभावी आयाम $d$ का उपयोग करके अनुमानित रिवॉर्ड्स के लिए कॉन्फिडेंस बाउंड्स का निर्माण करता है। एल्गोरिदम उस नोड का चयन करता है जो अपर कॉन्फिडेंस बाउंड को मैक्सिमाइज करता है: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$ , जहाँ $c_t$ , $d$ पर निर्भर करता है।
Spectral Thompson Sampling (SpectralTS): यह एल्गोरिदम एक बेयसियन दृष्टिकोण का उपयोग करता है। यह $\alpha^*$ पर एक पोस्टीरियर डिस्ट्रीब्यूशन बनाए रखता है, जिसे गौसियन $N(\hat{\alpha}_t, v^2 V_t^{-1})$ के रूप में मॉडल किया गया है। प्रायर कोवैरिएंस (prior covariance) को रेगुलराइज्ड लैपलेसियन $\Lambda$ के रूप में सेट किया गया है, जो इस धारणा को दर्शाता है कि स्मूथ फंक्शन्स (लो आइगेनवैल्यू कंपोनेंट्स) के अधिक संभावित होने की संभावना है। प्रत्येक स्टेप पर, एक पैरामीटर वेक्टर $\tilde{\alpha}$ को पोस्टीरियर से सैंपल किया जाता है, और वह नोड चुना जाता है जो $x_v^T \tilde{\alpha}$ को मैक्सिमाइज करता है।

प्रमुख योगदान और सैद्धांतिक परिणाम (Key Contributions and Theoretical Results)

नया ढांचा (Novel Framework): यह पहला कार्य है जो इस बात को औपचारिक रूप देता है कि पे-ऑफ्स ग्राफ पर स्मूथ फंक्शन्स होते हैं, जो मैनिफोल्ड लर्निंग/सेमी-सुपरवाइज्ड लर्निंग को ऑनलाइन लर्निंग के साथ जोड़ता है।
रेगेट बाउंड्स (Regret Bounds): शोध पत्र सिद्ध करता है कि SpectralUCB और SpectralTS दोनों प्रभावी आयाम $d$ $d$ के साथ स्केल होने वाले संचयी रेगेट (cumulative regret) बाउंड्स प्राप्त करते हैं:
- SpectralUCB: $O(d\sqrt{T \ln T})$ ।
- SpectralTS: $O(d\sqrt{T \ln N})$ ।
  ये बाउंड्स महत्वपूर्ण हैं क्योंकि $d$ अक्सर $N$ से बहुत छोटा होता है, जिससे ये एल्गोरिदम $T < N$ की स्थिति में भी अच्छा प्रदर्शन कर पाते हैं।
कंप्यूटेशनल दक्षता (Computational Efficiency): लेखक SpectralTS के लिए एक कंप्यूटेशनल लाभ पर प्रकाश डालते हैं। जबकि SpectralUCB को सभी $N$ आर्म्स के लिए कॉन्फिडेंस बाउंड्स की गणना करने की आवश्यकता होती है (जिससे सबसे खराब स्थिति में $D=N$ के लिए $O(N^3)$ जटिलता होती है), SpectralTS को केवल एक पैरामीटर वेक्टर को सैंपल करने और मैक्सिमम खोजने की आवश्यकता होती है, जिसे $O(N^2)$ प्रति स्टेप अधिक कुशलता से किया जा सकता है।

प्रायोगिक परिणाम (Experimental Results)
लेखकों ने सिंथेटिक और वास्तविक दुनिया के डेटासेट दोनों पर एल्गोरिदम का मूल्यांकन किया:

सिंथेटिक डेटा: Barabási-Albert ग्राफ्स ( $N=250$ ) का उपयोग करते हुए जहाँ वास्तविक रिवॉर्ड फंक्शन पहले 3 स्मूथ आइगेनवेक्टर्स का एक लीनियर कॉम्बिनेशन था। $T < N$ के शासन में, दोनों SpectralUCB और SpectralTS ने अपने लीनियर समकक्षों (LinUCB और LinearTS) की तुलना में संचयी रेगेट के मामले में काफी बेहतर प्रदर्शन किया। SpectralTS ने तेज़ कंप्यूटेशनल समय भी प्रदर्शित किया।
वास्तविक दुनिया का डेटा: मूवीलेंस (MovieLens) डेटासेट ( $N=2019$ फिल्में) का उपयोग करते हुए, जहाँ यूजर प्रेफरेंसेस को मूवी रेटिंग्स से निर्मित सिमिलरिटी ग्राफ पर एक स्मूथ फंक्शन के रूप में मॉडल किया गया। परिणामों ने सिंथेटिक निष्कर्षों को दोहराया: स्पेक्ट्रल एल्गोरिदम ने लीनियर बैंडिट बेसलाइन्स की तुलना में कम संचयी रेगेट हासिल किया। शोध पत्र नोट करता है कि हजारों आइटम्स के लिए यूजर प्रेफरेंसेस के अच्छे एस्टीमेटर को केवल दर्जनों नोड इवैल्यूएशन से सीखा जा सकता है।

महत्व और दावे (Significance and Claims)
शोध पत्र का दावा है कि स्पेक्ट्रल डीकंपोजिशन के माध्यम से ग्राफ पर फंक्शन्स की स्मूथनेस का लाभ उठाकर, यह संभव है कि बहुत अधिक संख्या में आर्म्स वाली ऑनलाइन लर्निंग समस्याओं को हल किया जाए, जहाँ रेगेट नोड्स की संख्या के साथ खराब तरीके से स्केल नहीं होता है। प्रभावी आयाम $d$ का परिचय एल्गोरिदम को ग्राफ की अंतर्निहित जटिलता के अनुकूल होने की अनुमति देता है। यह कार्य कंटेंट-आधारित रिकमेंडेशन और सोशल नेटवर्क में लक्षित विज्ञापन (targeted advertising) जैसे अनुप्रयोगों के लिए प्रासंगिक है, जहाँ यूजर प्रेफरेंसेस या इंटरेस्ट्स जुड़े हुए नोड्स के बीच सुचारू रूप से (smoothly) बदलते रहते हैं। लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण विशेष रूप से उन परिदृश्यों के लिए प्रासंगिक है जहाँ उपलब्ध इंटरैक्शन की संख्या ( $T$ ), उपलब्ध आइटम्स की संख्या ( $N$ ) की तुलना में कम होती है।

पुराना तरीका बनाम नया तरीका

मुख्य अवधारणा: "प्रभावी आयाम" (Effective Dimension)

दो एल्गोरिदम (गाइड)

उन्होंने क्या पाया (परिणाम)

सारांश

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