A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

तकनीकी सारांश: ऑफलाइन मूल्यांकन विधियों का उपयोग करके A/B टेस्टिंग के माध्यम से एक अधिक सटीक एल्गोरिदम तुलना

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

अनुशंसक प्रणालियों (recommender systems) और खोज इंजन (search engines) जैसी ऑनलाइन सेवाओं के विकास में, श्रेष्ठ एल्गोरिदम का चयन करना महत्वपूर्ण है। जबकि A/B टेस्टिंग को एल्गोरिदम चयन के लिए "स्वर्ण मानक" (gold standard) माना जाता है क्योंकि यह रैंडमाइजेशन के माध्यम से कन्फाउंडिंग कारकों (confounding factors) को समाप्त करने की क्षमता रखती है, लेकिन यह अक्सर महंगा होता है और यदि कोई खराब एल्गोरिदम तैनात किया जाता है, तो उपयोगकर्ता अनुभव या राजस्व में गिरावट का जोखिम भी उठाता है। इसके विपरीत, ऑफलाइन मूल्यांकन (ऐतिहासिक लॉग डेटा का उपयोग करना) सुरक्षित है लेकिन पारंपरिक रूप से उच्च अनुमान विचरण (estimation variance) और संभावित पूर्वाग्रह (bias) के कारण कम सटीक माना जाता है।

लेखक एक प्रति-सहज घटना (counterintuitive phenomenon) की पहचान करते हैं: कुछ परिदृश्यों में, A/B टेस्टिंग में उपयोग किया जाने वाला मानक एवरेज (AVG) एस्टिमेटर, इनवर्स प्रोपेंसिटी स्कोरिंग (IPS) जैसी ऑफलाइन मूल्यांकन विधियों की तुलना में उच्च एल्गोरिदम चयन त्रुटि दर (algorithm selection error rate) देता है। मुख्य मुद्दा एस्टिमेटर्स के सांख्यिकीय गुणों में निहित है:

• AVG एस्टिमेटर: एल्गोरिदम A और एल्गोरिदम B के लिए स्वतंत्र डेटा का उपयोग करता है। फलस्वरूप, प्रदर्शन अनुमान आपस में असंबद्ध (uncorrelated) होते हैं। अंतर एस्टिमेटर का विचरण (variance) केवल व्यक्तिगत विचलनों का योग ($Var(\hat{V}_A) + Var(\hat{V}_B)$) होता है, जो सहसंबंध (correlation) के माध्यम से विचरण को कम करने का कोई तंत्र प्रदान नहीं करता है।
• ऑफलाइन एस्टिमेटर्स (जैसे IPS): कई एल्गोरिदम के प्रदर्शन का अनुमान लगाने के लिए साझा ऐतिहासिक डेटा का उपयोग करते हैं। यह अनजाने में एस्टिमेटर्स के बीच एक सकारात्मक सहसंबंध (positive correlation) उत्पन्न करता है। विचरण अपघटन सूत्र ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$) के अनुसार, यह सकारात्मक सहप्रसरण (covariance) अंतर एस्टिमेटर के कुल विचरण को कम करता है, जिससे महत्वपूर्ण चयन त्रुटियों (श्रेष्ठ एल्गोरिदम को कम आंकना या निम्नतर एल्गोरिदम को अधिक आंकना) की संभावना कम हो जाती है।

यह शोध पत्र तर्क देता है कि A/B टेस्टिंग इस लाभकारी सहसंबंध का लाभ उठाने में विफल रहती है, जिससे विशिष्ट प्री-प्रयोगों (pre-experiments) में ऑफलाइन विधियों की तुलना में उप-इष्टतम चयन सटीकता प्राप्त होती है।

2. कार्यप्रणाली: मिडिल-इन-डिफरेंस (MID) एस्टिमेटर

A/B टेस्टिंग में सहसंबंध की कमी को दूर करने के लिए, लेखक मिडिल-इन-डिफरेंस (MID) नामक एक नया एस्टिमेटर प्रस्तावित करते हैं। मूल विचार एक काल्पनिक मिडल एल्गोरिदम (middle algorithm) ($\pi_M$) को पेश करके A/B टेस्टिंग फ्रेमवर्क के भीतर जानबूझकर सकारात्मक सहसंबंध उत्पन्न करना है।

चरणवार अनुमान प्रक्रिया (Stepwise Estimation Process):
एल्गोरिदम A ($\pi_A$) और एल्गोरिदम B ($\pi_B$) की सीधे तुलना करने के बजाय, MID प्रदर्शन अंतर को दो चरणों में विभाजित करता है:

1. $\pi_A$ से एकत्र किए गए लॉग डेटा ($D_A$) का उपयोग करके $\pi_A$ और $\pi_M$ के बीच के अंतर का अनुमान लगाएं।
2. $\pi_B$ से एकत्र किए गए लॉग डेटा ($D_B$) का उपयोग करके $\pi_M$ और $\pi_B$ के बीच के अंतर का अनुमान लगाएं।

अंतिम एस्टिमेटर इन दोनों अंतरों का योग है:
$$\Delta \hat{V}_{MID} = (\hat{V}_{IPS}(\pi_A; D_A) - \hat{V}_{IPS}(\pi_M; D_A)) + (\hat{V}_{IPS}(\pi_M; D_B) - \hat{V}_{IPS}(\pi_B; D_B))$$

विचरण न्यूनीकरण का तंत्र (Mechanism of Variance Reduction):

• प्रेरित सहसंबंध (Induced Correlation): क्योंकि पहला पद $\pi_A$ और $\pi_M$ दोनों के अनुमान के लिए साझा डेटा $D_A$ का उपयोग करता है, और दूसरा पद $\pi_M$ और $\pi_B$ के लिए साझा $D_B$ का उपयोग करता है, इसलिए प्रत्येक चरण के भीतर सकारात्मक सहसंबंध प्रेरित होता है। यह व्यक्तिगत अंतर पदों के विचरण को कम करता है।
• इष्टतम मिडल एल्गोरिदम (Optimal Middle Algorithm): लेखक एक इष्टतम मिडल एल्गोरिदम $\pi_M^*$ का प्रतिपादन करते हैं जो एस्टिमेटर के विचरण को न्यूनतम करता है। इष्टतम पॉलिसी को लॉगिंग पॉलिसी के हार्मोनिक मीन (harmonic mean) के रूप में परिभाषित किया गया है:
  $$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$$
  यह डिज़ाइन सुनिश्चित करता है कि $\pi_M$ दोनों $\pi_A$ और $\pi_B$ के अत्यधिक समान बना रहे, जिससे "विचरण विस्फोट" (variance explosion) कम होता है जो अक्सर असमान एल्गोरिदम की तुलना करने पर मानक IPS में देखा जाता है।

सैद्धांतिक गुण (Theoretical Properties):

• निर्विरोधता (Unbiasedness): लेखक सिद्ध करते हैं कि यदि मिडल एल्गोरिदम इस शर्त को पूरा करता है कि वह केवल उन क्रियाओं (actions) का चयन करता है जहाँ मूल एल्गोरिदम में से कम से कम एक की प्रायिकता गैर-शून्य है, तो एस्टिमेटर निर्विरोध (unbiased) रहता है।
• विचरण तुलना (Variance Comparison): सैद्धांतिक विश्लेषण दर्शाता है कि MID का रिवॉर्ड टर्म, मानक AVG एस्टिमेटर के रिवॉर्ड टर्म से कड़ाई से कम या उसके बराबर है। इसके अलावा, मानक IPS के विपरीत, MID $1/\pi_A$ विचरण विस्फोट से बचता है क्योंकि मध्यवर्ती तुलनाओं में समान पॉलिसियाँ शामिल होती हैं।

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

1. सांख्यिकीय अंतर्दृष्टि: यह शोध पत्र स्पष्ट करता है कि मानक AVG एस्टिमेटर एल्गोरिदम चयन के लिए आवश्यक रूप से इष्टतम नहीं है क्योंकि यह एस्टिमेटर्स के बीच सकारात्मक सहसंबंध के लाभों का लाभ उठाने में विफल रहता है।
2. नया एस्टिमेटर (MID): लेखक MID एस्टिमेटर प्रस्तावित करते हैं, जो एक काल्पनिक मिडल एल्गोरिदम और स्टेपवाइज एस्टिमेशन के माध्यम से जानबूझकर सकारात्मक सहसंबंध प्रेरित करता है, जिससे मानक A/B टेस्टिंग (AVG) और ऑफलाइन मूल्यांकन (IPS) दोनों की तुलना में कम चयन त्रुटि दर प्राप्त होती है।
3. सैद्धांतिक व्युत्पत्ति: शोध पत्र विचरण को न्यूनतम करने के लिए इष्टतम मिडल एल्गोरिदम को व्युत्पन्न करता है और एक बायस-वेरिएंस विश्लेषण प्रदान करता है जो दिखाता है कि MID मौजूदा विधियों से बेहतर क्यों है।
4. अनुभवजन्य सत्यापन (Empirical Validation): वास्तविक वीडियो अनुशंसा डेटा (KuaiRec) का उपयोग करते हुए, लेखक प्रदर्शित करते हैं कि MID विभिन्न सेटिंग्स में लगातार कम चयन त्रुटि दर प्राप्त करता है।

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

लेखकों ने KuaiRec डेटासेट का उपयोग करके प्रयोग किए, जो एक पूर्णतः प्रेक्षित (fully-observed) वीडियो अनुशंसा डेटासेट है जो ग्राउंड-ट्रुथ एल्गोरिदम प्रदर्शन की गणना करने की अनुमति देता है। उन्होंने विभिन्न सैंपल साइज और एल्गोरिदम समानता के साथ एक A/B टेस्टिंग वातावरण का अनुकरण किया।

• नमूना दक्षता (Sample Efficiency): MID ने मौजूदा विधियों (AVG और IPS) के समान चयन त्रुटि दर प्राप्त करने के लिए केवल आधे से एक-चौथाई A/B टेस्टिंग सैंपल साइज का उपयोग किया। उदाहरण के लिए, जहाँ AVG को 5% त्रुटि दर तक पहुँचने के लिए 350-400 नमूनों की आवश्यकता थी, वहीं MID ने 100-200 नमूनों के साथ वही उपलब्धि हासिल की।
• समानता के प्रति मजबूती (Robustness to Similarity):
  • उच्च-समानता (High-similarity) परिदृश्यों में, MID ने IPS (जो आमतौर पर ऑफलाइन सेटिंग्स में विचरण के साथ संघर्ष करता है) और AVG दोनों को पछाड़ दिया।
  • निम्न-समानता (Low-similarity) परिदृश्यों में, जहाँ महत्व भारण (importance weighting) के कारण IPS विचरण विस्फोट से ग्रस्त होता है, MID स्थिर रहा और IPS एवं AVG दोनों से बेहतर प्रदर्शन किया।
• तंत्र सत्यापन (Mechanism Verification): एस्टिमेट्स के स्कैटर प्लॉट्स ने पुष्टि की कि MID सफलतापूर्वक स्टेपवाइज एस्टिमेटर्स के बीच सकारात्मक सहसंबंध प्रेरित करता है, जिसके परिणामस्वरूप AVG के गोलाकार (असंबद्ध) वितरण की तुलना में अंतिम अंतर अनुमान का अधिक संकीर्ण (tighter) वितरण प्राप्त होता है। यह संकीर्ण प्रसार सीधे तौर पर महत्वपूर्ण चयन त्रुटियों में कमी से संबंधित है।

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

शोध पत्र का दावा है कि प्रस्तावित MID एस्टिमेटर एल्गोरिदम चयन के लिए A/B टेस्टिंग की दक्षता और सटीकता में मौलिक सुधार करता है। ऑफलाइन मूल्यांकन के सांख्यिकीय तंत्र (साझा डेटा द्वारा प्रेरित सहसंबंध) को उधार लेकर और इसे एक काल्पनिक मिडल एल्गोरिदम के माध्यम से A/B टेस्टिंग फ्रेमवर्क के भीतर लागू करके, MID पारंपरिक A/B टेस्टिंग (स्वतंत्रता के कारण उच्च विचरण) और ऑफलाइन मूल्यांकन (कम समानता या नए डेटा की कमी के कारण अस्थिरता) दोनों की सीमाओं को पार करता है।

लेखक इस बात पर जोर देते हैं कि यह दृष्टिकोण संगठनों को बहुत कम उपयोगकर्ताओं या कम प्रयोग अवधि के साथ अधिक सटीक एल्गोरिदम चयन निर्णय लेने की अनुमति देता है, जिससे ऑनलाइन प्रयोगों से जुड़े लागत और जोखिम को कम किया जा सकता है। यह कार्य सुझाव देता है कि A/B टेस्टिंग के "स्वर्ण मानक" को छोड़ने के बजाय, इसे उन सांख्यिकीय सहसंबंधों का लाभ उठाने के लिए परिष्कृत करके बढ़ाया जा सकता है जिनका पहले ऑनलाइन सेटिंग्स में उपयोग नहीं किया गया था।