🤖 machine learning

PARWiS: Winner determination under shoestring budgets using active pairwise comparisons

यह अध्ययन सक्रिय युग्मवार तुलनाओं (active pairwise comparisons) के माध्यम से सीमित बजट के तहत विजेताओं को निर्धारित करने के लिए PARWiS एल्गोरिदम और इसके प्रासंगिक एवं सुदृढीकरण शिक्षण-आधारित (contextual and reinforcement learning-based) वेरिएंट्स का मूल्यांकन करता है, जो सिंथेटिक और वास्तविक दुनिया के डेटासेट पर बेसलाइन की तुलना में उनके बेहतर प्रदर्शन को प्रदर्शित करता है, विशेष रूप से तब जब शीर्ष दो वस्तुओं के बीच का अंतर महत्वपूर्ण हो।

मूल लेखक: Shailendra Bhandari

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

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

CC BY 4.0

मूल लेखक: Shailendra Bhandari

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

कल्पना कीजिए कि आप एक टैलेंट स्काउट (प्रतिभा खोजकर्ता) हैं जो 20 स्टैंड-अप कॉमेडियंस से भरे कमरे में सबसे अच्छे कॉमेडियन को खोजने की कोशिश कर रहे हैं। आपके पास बहुत ही सीमित समय और पैसा (एक "शूस्ट्रिंग बजट") है। आप सभी को पूरे एक घंटे तक नहीं देख सकते। आप केवल उन्हें जोड़ियों में, अगल-बगल बैठकर देख सकते हैं, और दर्शकों से पूछ सकते हैं: "कौन अधिक मजेदार था?"

आपका लक्ष्य कम से कम तुलनाओं का उपयोग करके पूर्ण विजेता चुनना है। यह वही समस्या है जिसे यह पेपर हल करता है, और यहाँ बताया गया है कि कैसे इसके लेखक, शैलेंद्र भंडारी ने इसे हल किया।

समस्या: "शूस्ट्रिंग" दुविधा (The "Shoestring" Dilemma)

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

समाधान: "डिसरप्टिव" डिटेक्टिव (The "Disruptive" Detective)

यह पेपर PARWiS नामक एक एल्गोरिदम पर केंद्रित है। PARWiS को एक रैंडम जज के रूप में नहीं, बल्कि एक स्मार्ट डिटेक्टिव के रूप में सोचें।

पुराना तरीका (Random): कल्पना करें कि आप दो कॉमेडियंस को रैंडम तरीके से तुलना करने के लिए चुनते हैं। आप शायद दो सबसे खराब कॉमेडियंस की तुलना कर सकते हैं। इससे आपको यह पता नहीं चलेगा कि सबसे अच्छा कौन है। यह घास के ढेर में सुई खोजने की तरह है जहाँ आप घास के दो रैंडम टुकड़ों को चुन रहे हैं।
PARWiS का तरीका: PARWiS स्पेक्ट्रल रैंकिंग (Spectral Ranking) नामक एक तकनीक का उपयोग करता है। कल्पना करें कि यह कनेक्शनों का एक विशाल जाल बना रहा है। यह केवल इस बात को नहीं देखता कि किसने किसे हराया, बल्कि यह जीत और हार के पूरे पैटर्न को देखता है।
सीक्रेट सॉस (Disruptive Pairs): PARWiS का सबसे महत्वपूर्ण हिस्सा यह चुनने की रणनीति है कि अगली तुलना किसके बीच की जाए। यह "डिसरप्टिव पेयर्स" (विघटनकारी जोड़े) की तलाश करता है।
- उपमा: कल्पना कीजिए कि आप ताश की गड्डी को छाँट रहे हैं। यदि आप 'Ace of Spades' की तुलना '2 of Clubs' से करते हैं, तो आप बहुत कुछ सीखते हैं। यदि आप '5 of Hearts' की तुलना '6 of Hearts' से करते हैं, तो आप बहुत कम सीखते हैं। PARWiS विशेष रूप से उन जोड़ों की तलाश करता है जो वर्तमान रैंकिंग में सबसे बड़ा "उथल-पुथल" पैदा करेंगे। यह पूछता है, "यदि मैं इन दोनों की तुलना करता हूँ, तो क्या यह मेरी वर्तमान रैंकिंग के बारे में मेरी राय को पूरी तरह से बदल देगा?"

नए अपग्रेड (The New Upgrades)

लेखक ने केवल मूल PARWiS की नकल नहीं की है; उन्होंने इसे दो नई "सुपरपावर्स" दी हैं:

कॉन्टेक्स्टुअल PARWiS (द "रेज़्यूमे" रीडर):
- विचार: क्या होगा यदि आप कॉमेडियंस की पृष्ठभूमि जानते हों? (जैसे, "यह एक अनुभवी है, वह एक नौसिखिया है")।
- परिणाम: एल्गोरिदम ने इन अतिरिक्त विवरणों (फीचर्स) का उपयोग यह अनुमान लगाने के लिए करने की कोशिश की कि कौन जीतेगा, इससे पहले कि उन्हें देखा जाए।
- चुनौती: वास्तविक दुनिया के परीक्षणों (Jokes और Movies) में, डेटा में ये "रेज़्यूमे" नहीं थे। इसलिए, इस संस्करण ने मूल की तरह ही काम किया। यह एक आशाजनक विचार है, लेकिन इसे चमकने के लिए बेहतर डेटा की आवश्यकता है।
RL PARWiS (द "वीडियो गेम" प्लेयर):
- विचार: यह संस्करण रीइन्फोर्समेंट लर्निंग (Reinforcement Learning) (जैसे कुत्ते को प्रशिक्षित करना या किसी AI को वीडियो गेम में प्रशिक्षित करना) का उपयोग करता है। यह प्रयास और त्रुटि (trial and error) से सीखता है। हर बार जब यह एक जोड़ा चुनता है और परिणाम प्राप्त करता है, तो इसे एक "रिवॉर्ड" (पुरस्कार) या "पनिशमेंट" (दंड) मिलता है। हजारों खेलों के माध्यम से, यह जोड़े चुनने की सही रणनीति सीख जाता है।
- परिणाम: इसने मूल PARWiS के लगभग समान प्रदर्शन किया, जिससे सिद्ध हुआ कि AI भी एक बेहतरीन टैलेंट स्काउट बनने के लिए सीख सकता है।

बड़ा टेस्ट: जोक्स बनाम मूवीज़ (The Big Test: Jokes vs. Movies)

लेखक ने इन एल्गोरिदम का परीक्षण तीन अलग-अलग "क्षेत्रों" में किया:

सिंथेटिक डेटा (The Practice Field): बनावटी डेटा जहाँ नियम स्पष्ट हैं।
जेस्टर (The Joke Dataset): चुटकुलों का एक संग्रह। यहाँ, सबसे मजेदार चुटकुले और दूसरे सबसे मजेदार चुटकुले के बीच का अंतर स्पष्ट था।
- परिणाम: PARWiS और RL PARWiS ने प्रतियोगिता को पछाड़ दिया। उन्होंने आसानी से सबसे अच्छा चुटकुला ढूंढ लिया।
मूवी लेंस (The Movie Dataset): फिल्मों की रेटिंग का एक विशाल संग्रह। यहाँ, शीर्ष फिल्में गुणवत्ता में इतनी समान थीं कि उन्हें पहचानना अविश्वसनीय रूप से कठिन था।
- परिणाम: सभी संघर्ष कर रहे थे। सबसे अच्छी और दूसरी सबसे अच्छी फिल्म के बीच का अंतर इतना सूक्ष्म था कि सबसे स्मार्ट एल्गोरिदम को भी कठिनाई हुई। लेकिन, PARWiS अभी भी अन्य लोगों की तुलना में थोड़ा बेहतर प्रदर्शन करने में सफल रहा।

निष्कर्ष (The Verdict)

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

संक्षेप में: यदि आपको यह तय करने के लिए बहुत कम समय है कि सबसे अच्छा कौन है, तो अंदाज़ा न लगाएं। एक ऐसी प्रणाली का उपयोग करें जो पूरी तस्वीर को देखती है और विशेष रूप से वर्तमान लीडर्स को चुनौती देती है। यही वह चीज़ है जो PARWiS करता है, और यह तब जादू की तरह काम करता है जब प्रतिस्पर्धा स्पष्ट होती है, और जब मुकाबला बराबरी का होता है, तब भी यह सबसे अच्छा विकल्प बना रहता है।

यहाँ शैलेंद्र भंडारी के शोध पत्र "PARWiS: Winner determination under shoestring budgets using active pairwise comparisons" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा

यह शोध पत्र वरीयता-आधारित शिक्षण (विशेष रूप से ड्युलिंग बैंडिट्स - Dueling Bandits) में शूस्ट्रिंग बजट (अत्यंत सीमित बजट) के तहत विजेता निर्धारण समस्या (winner determination problem) को संबोधित करता है।

संदर्भ: कई वास्तविक दुनिया के अनुप्रयोगों (अनुशंसक प्रणालियों, सामाजिक चयन) में, प्रत्यक्ष संख्यात्मक फीडबैक उपलब्ध नहीं होता है; इसके बजाय, वरीयताओं का अनुमान युग्म तुलनाओं (जैसे, "वस्तु A को वस्तु B से बेहतर माना जाता है") के माध्यम से लगाया जाता है।
प्रतिबंध: अनुमत तुलनाओं की संख्या ( $B$ ) गंभीर रूप से सीमित है ("शूस्ट्रिंग बजट"), जिसे आमतौर पर $k$ वस्तुओं के लिए $B = 2k, 3k, \text{ या } 4k$ के रूप में परिभाषित किया गया है।
लक्ष्य: ब्रैडली-टेरी-ल्यूस (BTL) मॉडल का उपयोग करके उच्चतम अंतर्निहित स्कोर वाली वस्तु (जिसे "विजेता" कहा जाता है) की पहचान करना, जबकि तुलनाओं की संख्या को न्यूनतम रखना। यहाँ वस्तु $i$ के वस्तु $j$ को हराने की संभावना $P_{i,j} = w_i / (w_i + w_j)$ है।
चुनौती: मानक एल्गोरिदम (जैसे RUCB या स्पार्स बोर्डा) को अभिसरण (converge) करने के लिए बहुत अधिक तुलनाओं की आवश्यकता होती है, जिससे वे सीमित बजट के लिए अनुपयुक्त हो जाते हैं। इसके अलावा, समस्या की कठिनाई शीर्ष दो वस्तुओं के बीच के अंतर ( $\Delta_{1,2}$ ) पर निर्भर करती है।

2. कार्यप्रणाली

लेखक PARWiS (Pairwise Active Recovery of Winner under a Shoestring budget) एल्गोरिदम को लागू करते हैं और इसे दो नवीन वेरिएंट्स के साथ विस्तारित करते हैं:

A. मुख्य एल्गोरिदम: PARWiS

तंत्र: वस्तुओं के स्कोर का अनुमान लगाने के लिए युग्म परिणामों से स्पेक्ट्रल रैंकिंग (रैंक सेंट्रैलिटी) का उपयोग करता है।
रणनीति:
1. आरंभीकरण (Initialization): एक प्रारंभिक रैंकिंग बनाने के लिए $k-1$ तुलनाएँ करता है।
2. सक्रिय चयन (Active Selection): सबसे "विघटनकारी युग्मों" (disruptive pairs) का चयन करता है—ऐसे युग्म जिनकी तुलना से स्पेक्ट्रल रैंकिंग में अधिकतम परिवर्तन होने की अपेक्षा की जाती है। यह विजेता को तेजी से परिष्कृत करने के लिए अनिश्चित क्षेत्रों पर ध्यान केंद्रित करता है।

B. प्रस्तावित विस्तार

कॉन्टेक्स्टुअल (Contextual) PARWiS:
- वस्तुओं की विशेषताओं (जब उपलब्ध हों) को शामिल करने के लिए लॉजिस्टिक्स रिग्रेशन का उपयोग करता है ताकि तुलना के परिणामों की भविष्यवाणी की जा सके।
- सीमा: वास्तविक दुनिया के डेटासेट में, जहाँ स्पष्ट विशेषताएं मौजूद नहीं हैं, यह नॉन-कॉन्टेक्स्टुअल व्यवहार पर वापस आ जाता है।
RL PARWiS:
- एक सुदृढीकरण शिक्षण (Reinforcement Learning - Q-learning) आधारित दृष्टिकोण।
- अवस्था (State): वर्तमान रैंकिंग और तुलना गणना।
- क्रिया (Action): एक युग्म का चयन जिसे तुलना किया जाना है।
- पुरस्कार (Reward): प्रति चरण रिग्रेट (regret) में कमी और विजेता की पहचान करने के लिए अंतिम पुरस्कार का संयोजन।

C. बेसलाइन (Baselines)

प्रस्तावित विधियों की तुलना निम्नलिखित से की जाती है:

डबल थॉमसन सैंपलिंग (Double Thompson Sampling): बीटा प्रायर्स (Beta priors) का उपयोग करने वाला एक मानक ड्युलिंग बैंडिट एल्गोरिदम।
रैंडम सिलेक्शन (Random Selection): एक समान यादृच्छिक युग्म चयन रणनीति।

D. डेटासेट और मेट्रिक्स

डेटासेट:
- सिंथेटिक (Synthetic): BTL मॉडल द्वारा उत्पन्न ( $k=20$ )।
- जेस्टर (Jester): जेस्टर डेटासेट से चुने गए 20 चुटकुले (सघन रेटिंग, $\Delta_{1,2} \approx 0.0946$ )।
- मूवीलेंस 20M (MovieLens 20M): चुने गए 20 मूवीज़ (विरल रेटिंग, $\Delta_{1,2} \approx 0.0008$ , जो एक बहुत कठिन समस्या का प्रतिनिधित्व करता है)।
बजट: $B \in \{40, 60, 80\}$ तुलनाएँ।
मेट्रिक्स:
- रिकवरी फ्रैक्शन (Recovery Fraction): वास्तविक विजेता की सिफारिश करने की संभावना।
- रिपोर्ट किए गए विजेता की वास्तविक रैंक: सिफारिश की गई वस्तु और वास्तविक विजेता के बीच की निकटता।
- संचयी रिग्रेट (Cumulative Regret): गैर-इष्टतम वस्तुओं को चुनने से होने वाला कुल नुकसान।
- $\Delta_{1,2}$ : समस्या की कठिनाई दर्शाने वाला पृथक्करण मीट्रिक।

3. मुख्य परिणाम

प्रत्येक कॉन्फ़िगरेशन के लिए 30 रन के ऊपर प्रयोग किए गए।

आसान समस्याओं पर प्रदर्शन (सिंथेटिक और जेस्टर):
- PARWiS और RL PARWiS ने बेसलाइन्स को लगातार पछाड़ा।
- जेस्टर डेटासेट ( $\Delta_{1,2} = 0.0946$ ) पर, PARWiS और RL PARWiS ने सभी बजटों में ~0.467 का रिकवरी फ्रैक्शन प्राप्त किया, जो रैंडम (~0.03–0.06) से काफी अधिक है और अक्सर डबल TS से भी अधिक है।
- संचयी रिग्रेट: PARWiS ने सबसे धीमी गति से रिग्रेट संचित किया, जो आरंभीकरण चरण के बाद जल्दी स्थिर हो गया।
- सांख्यिकीय सार्थकता: टी-टेस्ट (T-tests) ने पुष्टि की कि PARWiS, सिंथेटिक और जेस्टर डेटासेट पर डबल TS से काफी बेहतर है (p < 0.05)।
कठिन समस्याओं पर प्रदर्शन (मूवीलेंस):
- अत्यंत छोटा पृथक्करण ( $\Delta_{1,2} = 0.0008$ ) सभी एजेंटों के लिए विजेता निर्धारण को कठिन बना देता है।
- सभी एल्गोरिदम के लिए रिकवरी फ्रैक्शन गिरकर 0.100–0.167 हो गया।
- हालांकि PARWiS और RL PARWiS ने रिग्रेट और रिकवरी में मामूली बढ़त बनाए रखी, लेकिन आसान डेटासेट की तुलना में प्रदर्शन का अंतर काफी कम हो गया।
वेरिएंट विश्लेषण:
- कॉन्टेक्स्टुअल PARWiS: मानक PARWiS के तुलनीय प्रदर्शन करता है। वास्तविक डेटा पर, यह लापता विशेषताओं के कारण नॉन-कॉन्टेक्स्टुअल व्यवहार पर चला गया। सिंथेटिक डेटा के साथ, इसने कोई महत्वपूर्ण सुधार नहीं दिखाया, जिससे पता चलता कि यादृच्छिक विशेषताएं पर्याप्त सूचनात्मक नहीं थीं।
- RL PARWiS: जेस्टर/सिंथेटिक पर प्रतिस्पर्धी प्रदर्शन दिखाता है, जो PARWiS के बराबर है। हालांकि, इसने मूवीलेंस पर थोड़ा अधिक रिग्रेट और "वास्तविक विजेता की रिपोर्ट की गई रैंक" में अधिक अंतर प्रदर्शित किया, जो दर्शाता कि इसे बेहतर स्टेट रिप्रेजेंटेशन या ट्रेनिंग की आवश्यकता है।

4. मुख्य योगदान

कार्यान्वयन और विस्तार: PARWiS को सफलतापूर्वक लागू किया गया और फीचर एकीकरण तथा अनुकूलन नीति सीखने (adaptive policy learning) का पता लगाने के लिए दो वेरिएंट्स पेश किए गए।
व्यापक मूल्यांकन: विभिन्न कठिनाई स्तरों ( $\Delta_{1,2}$ ) वाले सिंथेटिक और दो अलग-अलग वास्तविक डेटासेट (जेस्टर और मूवीलेंस) के माध्यम से इसका कठोर मूल्यांकन किया गया।
अनुभवजन्य सत्यापन (Empirical Validation): यह सिद्ध हुआ कि सीमित बजट के तहत विजेता की पहचान करने के लिए स्पेक्ट्रल रैंकिंग के साथ विघटनकारी युग्म चयन (disruptive pair selection) अत्यधिक प्रभावी है, जो मानक थॉमसन सैंपलिंग और रैंडम रणनीतियों से बेहतर है।
ओपन सोर्स टूलकिट: पुनरुत्पादकता (reproducibility) को सुगम बनाने के लिए सभी एल्गोरिदम, डेटासेट और मूल्यांकन स्क्रिप्ट के कार्यान्वयन के साथ एक पायथन पैकेज (dueling-bandit) जारी किया गया।

5. महत्व और निष्कर्ष

यह शोध पत्र पुष्टि करता है कि जब तुलना बजट अत्यंत सीमित हो, तो PARWiS विजेता निर्धारण के लिए एक मजबूत समाधान है।

व्यावहारिक प्रभाव: यह एल्गोरिदम उन अनुप्रयोगों के लिए विशेष रूप से मूल्यवान है जहाँ उपयोगकर्ता इंटरैक्शन महंगा या सीमित होता है (जैसे, प्रारंभिक अनुशंसा चरण, कम भागीदारी के साथ क्राउडसोर्सिंग)।
कठिनाई पर अंतर्दृष्टि: अध्ययन इस बात पर प्रकाश डालता है कि एल्गोरिदम का प्रदर्शन पृथक्करण मीट्रिक ( $\Delta_{1,2}$ ) पर बहुत अधिक निर्भर करता है। जबकि PARWiS तब उत्कृष्ट प्रदर्शन करता है जब शीर्ष वस्तुएं पहचानने योग्य होती हैं, जब शीर्ष वस्तुएं लगभग अविभाज्य होती हैं, तो सभी विधियाँ संघर्ष करती हैं।
भविष्य की दिशाएं: लेखक सुझाव देते हैं कि यद्यपि RL PARWiS आशाजनक है, इसे अधिक परिष्कृत स्टेट रिप्रेजेंटेशन की आवश्यकता है। इसके अतिरिक्त, वास्तविक दुनिया के डेटा (जैसे मूवी टैग्स) से सार्थक विशेषताएं निकालना कॉन्टेक्स्टुअल PARWiS की क्षमता को अनलॉक कर सकता है।

संक्षेप में, यह कार्य इस बात को प्रमाणित करता है कि सख्त बजट प्रतिबंधों के तहत विजेता की पहचान करने के लिए विघटनकारी युग्मों (disruptive pairs) और स्पेक्ट्रल रैंकिंग पर ध्यान केंद्रित करने वाली सक्रिय शिक्षण रणनीतियाँ, निष्क्रिय या यादृच्छिक रणनीतियों की तुलना में श्रेष्ठ हैं।