🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

यह शोध पत्र एक कोटिएंट-DAG फ्रेमवर्क और फॉरवर्ड-DP एल्गोरिदम पेश करता है ताकि ऑटोरिग्रेसिव रिकमेंडेशन सिस्टम्स में कुशल ऑफ-पॉलिसी इवैल्यूएशन के लिए न्यूसेंस वेरिएंस को समाप्त किया जा सके और अनऑर्डर्ड स्लेट प्रोपेंसिटीज की सटीक गणना सक्षम की जा सके।

मूल लेखक: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

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

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

CC BY 4.0

मूल लेखक: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

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

कल्पना कीजिए कि आप एक शेफ हैं जो यह आंकना चाहते हैं कि एक नई रेसिपी (Target Policy) कितनी अच्छी होगी, लेकिन आप इसे अपने खुद के किचन में वास्तव में बना नहीं सकते क्योंकि यह बहुत महंगा या जोखिम भरा है। इसके बजाय, आपके पास एक नोटबुक है जिसमें एक दूसरे शेफ (Behavior Policy) द्वारा पहले बनाई गई रेसिपीज़ का विवरण है। आपका लक्ष्य केवल उस पुरानी नोटबुक का उपयोग करके यह अनुमान लगाना है कि वह नई रेसिपी कितनी स्वादिष्ट होगी। यही Off-Policy Evaluation (OPE) की मूल समस्या है।

समस्या: गलत चीजों को गिनना

आमतौर पर, नई रेसिपी का आकलन करने के लिए, आप पुराने शेफ द्वारा उठाए गए हर एक कदम को देखते हैं। आप कहते हैं, "ठीक है, उन्होंने नमक डाला, फिर काली मिर्च, फिर लहसुन।" आप उस सटीक क्रम के आधार पर एक स्कोर की गणना करते हैं।

लेकिन यहाँ एक पेंच है: कभी-कभी सामग्री डालने का क्रम वास्तव में अंतिम व्यंजन के स्वाद को नहीं बदलता है।

परिदृश्य: कल्पना करें कि वस्तुओं की एक "स्लेट" (जैसे 5 गानों की प्लेलिस्ट या 5 ऐपेटाइज़र की ट्रे) है। ग्राहक केवल इस बात की परवाह करता है कि ट्रे पर कौन से 5 आइटम हैं, न कि इस बात की कि शेफ ने उन्हें किस क्रम में रखा।
गलती: पुराना नोटबुक क्रम को रिकॉर्ड करता है (गाना A, फिर B, फिर C...)। यदि आप अपने स्कोर की गणना उस विशिष्ट क्रम के आधार पर करते हैं, तो आप "क्रम" को महत्वपूर्ण मान रहे हैं। लेकिन चूंकि ग्राहक इसकी परवाह नहीं करता, इसलिए आप अपनी गणना में "शोर" (noise) जोड़ रहे हैं।
परिणाम: यह शोर बहुत अधिक भ्रम (variance) पैदा करता है। यह ऐसा है जैसे आप हर एक मोज़े को अलग-अलग तौलकर सूटकेस का वजन बताने की कोशिश कर रहे हों, बजाय इसके कि आप पूरे सूटकेस को एक साथ तौलें। आप कितने मोज़ों को कैसे गिना, इस पर निर्भर करते हुए आपको बहुत अलग-अलग उत्तर मिलेंगे।

इसके अलावा, वस्तुओं के एक विशिष्ट समूह (क्रम को अनदेखा करते हुए) को प्राप्त करने की "वास्तविक" प्रायिकता (probability) की गणना करना एक गणितीय दुःस्वप्न है। यदि आपके पास 5 आइटम हैं, तो उन्हें चुनने के 120 अलग-अलग तरीके (5 factorial) हो सकते हैं। आपकी नोटबुक के हर एक एंट्री के लिए यह गणित करना कम्प्यूटेशनल रूप से असंभव है।

समाधान: "Quotient DAG" (ग्रुपिंग मैप)

लेखक डेटा को देखने का एक चतुर नया तरीका प्रस्तावित करते हैं। हर उस पथ (path) को देखने के बजाय जो एक ही परिणाम की ओर ले जाता है, वे सुझाव देते हैं कि उन सभी पथों को समूहित (grouping) किया जाए जो एक ही परिणाम तक पहुँचते हैं।

उपमा: एक विशाल पेड़ की कल्पना करें जहाँ प्रत्येक शाखा सामग्री डालने के एक अलग क्रम का प्रतिनिधित्व करती है।
- पुराना तरीका: आप हर एक शाखा पर चलते हैं, वजन मापते हैं, और उनका औसत निकालने की कोशिश करते हैं।
- नया तरीका (Quotient DAG): आप महसूस करते हैं कि वे सभी शाखाएं जो अंततः सामग्री के एक ही सेट पर समाप्त होती हैं, वास्तव में आपके मानचित्र में एक ही "नोड" हैं। आप उन सभी शाखाओं को एक एकल बिंदु में समेट देते हैं।
- मैप: यह एक "Directed Acyclic Graph" (DAG) बनाता है—एक ऐसा मानचित्र जहाँ आप केवल चुने गए वस्तुओं के सेट पर ध्यान केंद्रित करते हैं, उनके क्रम पर नहीं।

जादुई ट्रिक: Forward-Flow Importance Sampling

एक बार जब आपके पास यह सरल मानचित्र हो जाता है, तो आपको यह जानने की आवश्यकता है कि नया शेफ एक विशिष्ट "सेट" तक पहुँचने की कितनी संभावना रखता है।

पुराना तरीका: आपको उत्तर प्राप्त करने के लिए सभी 120 अलग-अलग क्रमों की प्रायिकता को जोड़ना होगा।
नया तरीका (Forward-DP): लेखकों ने Forward-DP (डायनेमिक प्रोग्रामिंग) नामक एक विधि विकसित की है। इसे एक स्मार्ट कैलकुलेटर के रूप में सोचें जो उत्तर को चरण-दर-चरण बनाता है।
- यह एक खाली ट्रे (प्रायिकता 1) से शुरू होता है।
- यह पूछता है: "यदि मेरे पास 1 आइटम है, तो दूसरा जोड़ने की क्या संभावना है?"
- यह पूछता है: "यदि मेरे पास 2 आइटम हैं, तो तीसरा जोड़ने की क्या संभावना है?"
- यह बिना कभी भी सभी 120 क्रमों को सूचीबद्ध किए, पूरे सेट की प्रायिकता का निर्माण करता रहता है।

यह विधि सटीक (exact) है (यह अनुमान नहीं लगाती) और तेज़ है। वर्षों तक गणना करने के बजाय (factorial time), यह एक प्रबंधनीय समय में होता है (ट्रे के आकार के संदर्भ में exponential, लेकिन मेनू के आकार के संदर्भ में polynomial)।

यह क्यों महत्वपूर्ण है

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

सारांश

यह पेपर "कैसे" (कार्यों का क्रम) का अत्यधिक विश्लेषण करने के बजाय "क्या" (वस्तुओं का अंतिम सेट) पर ध्यान केंद्रित करने का एक तरीका पेश करता है। समान पथों को एक साथ समूहित करके और एक स्मार्ट, चरण-दर-चरण गणना विधि (Forward-DP) का उपयोग करके, वे नए रणनीतियों का बहुत अधिक सटीकता और दक्षता के साथ मूल्यांकन कर सकते हैं, विशेष रूप से स्वास्थ्य सेवा और अनुशंसा इंजन जैसे क्षेत्रों में जहाँ वास्तविक जीवन में नए विचारों का परीक्षण करना बहुत खतरनाक या महंगा है।

तकनीकी सारांश: ऑफ-पॉलिसी इवैल्यूएशन के लिए कोटिएंट DAGs (Quotient DAGs)

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

ऑफ-पॉलिसी इवैल्यूएशन (OPE), एक व्यवहार नीति (behavior policy) $\beta$ द्वारा एकत्र किए गए डेटा का उपयोग करके एक लक्षित नीति (target policy) $\pi$ के प्रदर्शन का अनुमान लगाता है। मानक इम्पोर्टेंस सैंपलिंग (IS) लॉग की गई ट्रैजेक्टरीज को लक्ष्य-से-व्यवहार क्रिया-प्रायिकता अनुपातों (action-probability ratios) के गुणनफल द्वारा पुन: भारित (reweight) करती है। हालाँकि, यह दृष्टिकोण अक्सर जनरेशन प्रक्रिया के उन विवरणों को भी सार्थक मान लेता है जिन्हें मूल्यांकन लक्ष्य अनदेखा कर देता है।

इस समस्या का एक प्राथमिक उदाहरण स्लेट अनुशंसा (slate recommendation) में मिलता है, जहाँ आधुनिक जनरेटर अक्सर क्रमवार (autoregressively) स्लेट्स (वस्तुओं के सेट) का निर्माण करते हैं, जिससे एक विशिष्ट क्रम के साथ प्रति-चरण प्रायिकताएं (per-step probabilities) उजागर होती हैं। फिर भी, रिवॉर्ड और डाउनस्ट्रीम एस्टिमेटर्स केवल अक्रमित स्लेट (unordered slate) पर निर्भर करते हैं। मानक ट्रैजेक्टरी IS एक विशिष्ट क्रमित पथ (ordered path) को एक संभावना अनुपात (likelihood ratio) प्रदान करता है, जो एक "संयुक्त-प्रोपेंसिटी गैप" (joint-propensity gap) बनाता है: लॉगर एक क्रमित क्रम की प्रायिकता को उजागर करता है, जबकि एस्टिमेटर को अक्रमित स्लेट की कुल प्रायिकता की आवश्यकता होती है। इस सटीक अक्रमित प्रोपेंसिटी की गणना करने के लिए $K!$ जनरेशन ऑर्डर्स पर योग करना आवश्यक होता है, जो मध्यम आकार की स्लेट्स के लिए कम्प्यूटेशनल रूप से अव्यवहार्य (intractable) है। इसके अतिरिक्त, यदि रिवॉर्ड जनरेशन ऑर्डर के प्रति अपरिवर्तनीय (invariant) है, तो ऑर्डरिंग को महत्वपूर्ण मानना 'न्युसेंस वेरिएंस' (nuisance variance) उत्पन्न करता है।

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

यह शोध पत्र इन समस्याओं के समाधान के लिए एक कोटिएंट-DAG (Quotient-DAG) दृश्य प्रस्तुत करता है। मुख्य विचार मूल्यांकन लक्ष्य के लिए पर्याप्त एक समतुल्यता संबंध (equivalence relation) द्वारा रोलआउट ट्री के हिस्ट्री प्रिफिक्सेस (history prefixes) को कोटिएंट करना है।

कोटिएंट DAG और फॉरवर्ड फ्लो (Forward Flow):
- रोलआउट ट्री को उन हिस्ट्री प्रिफिक्सेस को मर्ज करके संकुचित किया जाता है जो मूल्यांकन लक्ष्य के लिए समान हैं (उदाहरण के लिए, वे प्रिफिक्स जिनमें चुनी गई वस्तुओं का एक ही सेट है, चाहे उनका क्रम कुछ भी हो)।
- यह एक स्तरित निर्देशित अचक्रीय ग्राफ (layered Directed Acyclic Graph - DAG) बनाता है जहाँ नोड्स समतुल्यता वर्गों (equivalence classes या quotient states) का प्रतिनिधित्व करते हैं।
- एकल realized पथ के अनुपात के बजाय, यह विधि फॉरवर्ड-फ्लो अनुपात $F_\pi(z)/F_\beta(z)$ का उपयोग करके भार आवंटित करती है, जहाँ $F_\mu(z)$ नीति $\mu$ के तहत नोड $z$ तक पहुँचने वाला प्रायिकता द्रव्यमान (probability mass) है।
- यह दृष्टिकोण मौजूदा विधियों का सामान्यीकरण करता है: पर-डिसीजन IS, मार्जिनलाइज्ड IS, और ज्ञात-एब्स्ट्रैक्शन MIS, विभिन्न समतुल्यता संबंधों के चयन के आधार पर इसके विशेष मामले हैं।
फॉरवर्ड-फ्लो इम्पोर्टेंस सैंपलिंग (FF-IS):
- सामान्य परिमित-क्षितिज (finite-horizon) OPE के लिए, यह एस्टिमेटर पर-डिसीजन IS (PDIS) में सैंपल किए गए प्रिफिक्स अनुपात को कोटिएंट लाइकलीहुड रेशियो से बदल देता है।
- सैद्धांतिक विश्लेषण से पता चलता है कि टर्मिनल कोटिएंट-मेज़रेबल रिटर्न्स के लिए, यह वेटिंग "विदिन-क्लास" (within-class) लक्ष्य-व्यवहार बेमेल को हटा देती है, जो एक सटीक वेरिएंस गैप अभिव्यक्ति प्रदान करती है जो न्युसस वेरिएंस (nuisance variance) की कमी को स्पष्ट करती है।
स्लेट OPE के लिए फॉरवर्ड-DP (Forward-DP):
- यह शोध पत्र इस ढांचे को एक सेट-सफिशिएंट (set-sufficient) इंटरफ़ेस (परिभाषा 1) के तहत ऑटोरेग्रेसिव स्लेट जनरेशन के लिए विशेष रूप से लागू करता है। एक नीति तब 'सेट-सफिशिएंट' कहलाती है यदि अगली वस्तु चुनने की प्रायिकता संदर्भ (context) और पहले से चुनी गई वस्तुओं के सेट पर निर्भर करती है, न कि उनके क्रम पर।
- सेट-सफिशिएंसी के तहत, परम्यूटेशन कोटिएंट एक सबसेट DAG (subset DAG) के अनुरूप होता है, जहाँ नोड्स कैटलॉग के सबसेट्स होते हैं और किनारे (edges) बिना चुनी गई वस्तुओं को जोड़ते हैं।
- फॉरवर्ड-DP एल्गोरिदम: यह डायनेमिक प्रोग्रामिंग एल्गोरिदम सबसेट्स पर योग करके सटीक अक्रमित स्लेट प्रोपेंसिटी $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ की गणना करता है।
  - जटिलता (Complexity): $O((M + K) \cdot 2^K)$ , जहाँ $M$ कैटलॉग का आकार है और $K$ स्लेट का आकार है। यह $K!$ एन्यूमरेशन (enumeration) से बचता है।
  - इष्टतमता (Optimality): शोध पत्र सिद्ध करता है कि सेट-सफिशिएंट पॉलिसियों के लिए सटीक अक्रमित प्रोपेंसिटी की गणना करने वाला कोई भी नियतात्मक (deterministic) एल्गोरिदम, वर्स्ट केस में स्लेट के प्रत्येक उचित उपसमुच्चय (proper subset) को क्वेरी करेगा, जो स्थापित करता है कि फॉरवर्ड-DP स्थिर कारकों (constant factors) तक क्वेरी-ऑप्टिमल है।

मुख्य योगदान (Key Contributions)

सैद्धांतिक ढांचा: OPE के लिए एक एकीकृत कोटिएंट-DAG दृश्य जो एक मोटे सैंपल स्पेस (coarser sample space) पर फॉरवर्ड-फ्लो रेशियो के रूप में सटीक लाइकलीहुड रेशियो प्राप्त करता है।
एल्गोरिद्मिक नवाचार: फॉरवर्ड-DP एल्गोरिदम, जो संदर्भ-निर्भर, सेट-सफिशिएंट ऑटोरेग्रेसिव लॉगर के लिए सटीक अक्रमित स्लेट प्रोपेंसी को कैटलॉग के आकार के बहुपद (polynomial) और स्लेट के आकार $K$ के चरघातांकीय (exponential) समय में कंप्यूट करता है (जो $K$ के लिए फिक्स्ड-पैरामीटर ट्रेक्टेबल है)।
वेरिएंस रिडक्शन: एक औपचारिक प्रमाण कि कोटिएंट वेटिंग अप्रासंगिक जनरेशन ऑर्डर्स (जैसे स्लेट अनुशंसा में ऑर्डरिंग-न्युसेंस वेरिएंस) से उत्पन्न होने वाले वेरिएंस घटक को हटा देती है, विशेष रूपकर जब रिवॉर्ड्स स्लेट के जनरेशन सीक्वेंस के प्रति अपरिवर्तनीय होते हैं।
स्लेट OPE के लिए प्रिमिटिव्स: फिक्स्ड-स्कोर प्लैकेट-ल्यूस (Plackett-Luce) फॉर्मूला जहाँ लागू नहीं होते, वहां संदर्भ-निर्भर ऑटोरेग्रेसिव ट्रांसफॉर्मर रिकमेंडर्स के लिए सटीक प्रोपेंसिटी-आधारित मूल्यांकन और मॉडल सिलेक्शन को सक्षम करने वाले एक प्रिमिटिव के रूप में फॉरवर्ड-DP का परिचय।

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

लेखक अपने मेथड का मूल्यांकन परिमित-क्षितिज MDP बेंचमार्क और स्लेट अनुशंसा कार्यों पर करते हैं:

परिमित-क्षितज़ MDPs (Sepsis & ICU-Sepsis):
- फॉरवर्ड-फ्लो IS (FF-IS), स्टैंडर्ड ट्रैजेक्टरी IS और अन्य बेसलाइन्स (जैसे DualDICE, GenDICE) की तुलना में RMSE को काफी कम कर देता है।
- सेप्सिस बेंचमार्क पर, FF-WIS ने RMSE को 0.291 (WIS) से घटाकर 0.0568 कर दिया।
- ये लाभ केवल लॉग की गई ट्रैजेक्टरीज का उपयोग करके प्राप्त किए गए, बिना किसी ट्रांजिशन मॉडल को फिट किए।
KuaiRec स्लेट प्रयोग:
- कम्प्यूटेशनल दक्षता: फॉरवर्ड-DP, $K!$ एन्यूमरेशन की तुलना में कई गुना तेजी से सटीक प्रोपेंसिटी कंप्यूट करता है। $K=8$ के लिए, एन्यूमरेशन में ~97,108 सेकंड लगे, जबकि फॉरवर्ड-DP ने ~8.94 सेकंड लिए। $K=12$ के लिए, एन्यूमरेशन असंभव है, जबकि फॉरवर्ड-DP ~13.7 सेकंड में पूरा हो जाता है।
- डाउनस्ट्रीम OPE: फॉरवर्ड-DP वेट्स (FF-OI, FF-DR) का उपयोग करने वाले एस्टिमेटर्स ने सभी स्लेट आकारों ( $K \in \{4, 6, 8\}$ ) में ट्रैजेक्टरी-वेटेड समकक्षों (OIS, DR) की तुलना में सभी RMSE के मामले में लगातार बेहतर प्रदर्शन किया।
- मॉडल सिलेक्शन: ऑटोरेग्रेसिव ट्रांसफॉर्मर रिकमेंडर्स के बीच ऑफ-पॉलिसी मॉडल सिलेक्शन में, फॉरवर्ड-DP (जैसे, Tree-DR, DP-OPCB-DR) का उपयोग करने वाले एस्टिमेटर्स ने ट्रैजेक्टरी-आधारित तरीकों की तुलना में बेहतर Top-1 सटीकता, स्पियरमैन सहसंबंध (Spearman correlation) और कम रिग्रेट (regret) प्राप्त किया।

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

शोध पत्र का दावा है कि प्रस्तावित ढांचा पर-डिसीजन IS का राव-ब्लैकलाइज़ेशन (Rao–Blackwellization) प्रदान करता है। पर्याप्त समतुल्यता संबंधों के तहत रोलआउट ट्री को कोटिएंट करके, यह विधि अप्रासंगिक हिस्ट्री विवरणों (जैसे स्लेट अनुशंसा में जनरेशन ऑर्डर) से जुड़े न्युसेंस वेरिएंस को समाप्त करती है।

विशेष रूप से स्लेट अनुशंसा के लिए, शोध पत्र का तर्क है कि फॉरवर्ड-DP, संदर्भ-निर्भर ऑटोरेग्रेसिव लॉगर के लिए लुप्त OPE प्रिमिटिव की आपूर्ति करता है। उन पिछले तरीकों के विपरीत जो फिक्स्ड-स्कोर धारणाओं (जहाँ आइटम स्कोर आंशिक स्लेट के साथ नहीं बदलते) या मोंटे कार्लो सन्निकटन (approximations) पर निर्भर करते हैं, फॉरवर्ड-DP उन मामलों को संभालता है जहाँ अगला-आइटम सॉफ्टमैक्स (softmax) आंशिक स्लेट पर निर्भर करता है, और $K!$ एन्यूमरेशन के बिना सटीक संयुक्त प्रोपेंसिटी की गणना करता है। यह आधुनिक ट्रांसफॉर्मर-आधारित रिकमेंडर्स के लिए व्यावहारिक, सटीक प्रोपेंसिटी-आधारित मूल्यांकन और मॉडल सिलेक्शन को सक्षम बनाता है।

लेखक सीमाओं को भी नोट करते हैं, जिसमें सेट-सफिशिएंसी धारणा की आवश्यकता (जिसके लिए डिप्लॉयमेंट में चुने गए सेट को कैनोनिकल बनाना पड़ सकता है) और स्लेट आकार $K$ के साथ चरघातांकीय स्केलिंग शामिल है, हालांकि वे तर्क देते हैं कि यह विशिष्ट स्लेट आकारों ( $K \le 10$ ) के लिए व्यावहारिक है जहाँ $K!$ अव्यवहार्य है।