तकनीकी सारांश: अनुक्रमिक निर्णय-निर्माण (Sequential Decision-Making) के माध्यम से चयन हेतु डेटा मानों का एकीकरण और अनुकूलन

समस्या विवरण

डेटा चयन (Data Selection), डेटा मूल्यांकन (Data Valuation) का एक महत्वपूर्ण डाउनस्ट्रीम अनुप्रयोग है, जिसका लक्ष्य मॉडल के प्रदर्शन को अधिकतम करने के लिए प्रशिक्षण डेटा के इष्टतम उपसमुच्चयों (optimal subsets) की पहचान करना है। जबकि मौजूदा डेटा मूल्यांकन विधियाँ (जैसे कि डेटा शैपली, बान्ज़ाफ, बीटा शैपली) सहयोगात्मक गेम थ्योरी के आधार पर नमूनों के योगदान को मापने के सिद्धांतवादी तरीके प्रदान करती हैं, 'चयन' (selection) के लिए उनके सैद्धांतिक आधार अभी भी कम खोजे गए हैं। विशेष रूप से, ये विधियाँ चयन के उद्देश्य के लिए स्पष्ट रूप से अनुकूलित नहीं हैं, जिसके लिए सभी संभावित उपसमुच्चय आकारों (selection curves) में संचयी प्रदर्शन को अधिकतम करने की आवश्यकता होती है। यह शोध पत्र चयन अनुक्रमों की सैद्धांतिक इष्टतमता और वर्तमान मूल्यांकन विधियों के व्यावहारिक प्रदर्शन के बीच के अंतर की पहचान करता है, विशेष रूप से उच्च डेटा अतिरेक (redundancy) या घटते प्रतिफल (submodularity) वाले परिदृश्यों में।

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

लेखक डेटा चयन को एक अनुक्रमिक निर्णय-निर्माण समस्या के रूप में पुनर्गठित करते हैं जिसे एक नियतात्मक मार्कोव निर्णय प्रक्रिया (Deterministic Markov Decision Process - DMDP) के रूप में मॉडल किया गया है।

1. अनुक्रमिक सूत्रीकरण (Sequential Formulation):

   • अवस्था (State): अब तक चयनित डेटा बिंदुओं का सेट ($s_t \subseteq D$)।
   • क्रिया (Action): अगला डेटा बिंदु जिसे जोड़ा जाना है ($a_t \in D \setminus s_t$)।
   • पुरस्कार (Reward): परिणामी उपसमुच्चय की उपयोगिता, $U(s_t \cup \{a_t\})$।
   • उद्देश्य: सभी प्रीफिक्स आकारों में अपेक्षित संचयी उपयोगिता (Expected Cumulative Utility) को अधिकतम करना (जो कि 'एरिया अंडर द सिलेक्शन कर्व' - AUSC के बराबर है)।

2. डायनेमिक प्रोग्रामिंग (DP) के माध्यम से सटीक समाधान:

   • इष्टतम चयन अनुक्रम को बेलमैन इष्टतमता समीकरण (Bellman optimality equation) का उपयोग करके प्राप्त किया जाता है। यह एक सटीक समाधान प्रदान करता है जहाँ इष्टतम नीति तत्काल पुरस्कारों और भविष्य के मूल्य (फुल लुकअहेड) दोनों पर विचार करती है।
   • सीमा: स्टेट स्पेस तेजी से बढ़ता है ($O(n \cdot 2^n)$), जिससे बड़े डेटासेट के लिए सटीक DP गणनात्मक रूप से अव्यवहार्य हो जाता है।

3. अनुमानित डायनेमिक प्रोग्रामिंग (ADP) के माध्यम से मौजूदा विधियों की पुनर्व्याख्या:

   • यह शोध पत्र प्रदर्शित करता है कि मौजूदा गेम-थ्योरेटिक डेटा मान (शैपली, बान्ज़ाफ, बीटा शैपली) ADP ढांचे के भीतर मायोपिक लीनियर एप्रोक्सिमेशन (myopic linear approximations) के रूप में संगत हैं।
   • ये विधियाँ अप्रत्यक्ष रूप से एक लीनियर सरोगेट उपयोगिता फलन $\hat{U}(S) = \hat{b} + \sum_{i \in S} \theta_i$ को फिट करती हैं और एक मायोपिक नीति (तत्काल मार्जिनल गेन $\theta_i$ पर आधारित ग्रीडी चयन) अपनाती हैं।
   • सैद्धांतिक विश्लेषण से पता चलता है कि इन अनुमानों की प्रभावशीलता उपयोगिता फलन की वक्रता ($c$) पर निर्भर करती है। लीनियर उपयोगिताओं ($c=0$) के लिए, ये विधियाँ इष्टतम हैं। हालाँकि, जैसे-जैसे वक्रता बढ़ती है (जो घटते प्रतिफल/सबमॉड्यूलरिटी को दर्शाती है), प्रदर्शन की गारंटी $(1-c)^2$ के रूप में तेजी से गिरती है।

4. प्रस्तावित समाधान: बाइपार्टाइट ग्राफ-आधारित सरोगेट (Bipartite Graph-Based Surrogate):

   • सैद्धांतिक इष्टतमता और गणनात्मक दक्षता के बीच के अंतर को पाटने के लिए, लेखक प्रशिक्षण और सत्यापन सेटों के बीच एक बाइपार्टाइट ग्राफ का उपयोग करके एक नवीन अनुमान योजना प्रस्तावित करते हैं।
   • उपयोगिता मॉडलिंग: सरोगेट उपयोगिता को चयनित प्रशिक्षण बिंदुओं द्वारा सत्यापन बिंदुओं के "कवरेज" (coverage) के रूप में परिभाषित किया गया है। इस कवरेज फलन को नॉर्मलाइज्ड, मोनोटोन और सबमॉड्यूलर सिद्ध किया गया है।
   • चयन नीति: इस सरोगेट पर एक ग्रीडी चयन एल्गोरिदम लागू किया जाता है।
   • सैद्धांतिक गारंटी: "सैंडविच" स्थितियों के तहत जहाँ सरोगेट वास्तविक उपयोगिता का समान रूप से अनुमान लगाता है, यह विधि $(1-\epsilon)(1-1/e)$ का एंड-टू-एंड अनुमान गारंटी प्रदान करती है।

मुख्य योगदान

• सैद्धांतिक एकीकरण: यह शोध पत्र डेटा मूल्यांकन को अनुक्रमिक निर्णय-निर्माण के साथ एकीकृत करने वाला एक ढांचा स्थापित करता है, जिससे यह पता चलता है कि लोकप्रिय सेमी-वैल्यू विधियाँ ADP में विशिष्ट मायोपिक लीनियर एप्रोक्सिमेशन के उदाहरण हैं।
• इष्टतमता विश्लेषण: यह नई सैद्धांतिक अंतर्दृष्टि प्रदान करता है जो यह बताती है कि मौजूदा विधियाँ कब और क्यों विफल होती हैं, विशेष रूप से उपयोगिता फलन की वक्रता (curvature) को इससे जोड़कर।
• कुशल एल्गोरिदम: लेखक एक बाइपार्टाइट ग्राफ-आधारित सरोगेट विकसित करते हैं जो सबमॉड्यूलर संरचना को बनाए रखता है, जिससे प्रमाणित सैद्धांतिक गारंटी के साथ स्केलेबल ग्रीडी चयन संभव होता है।
• प्रायोगिक सत्यापन: व्यापक प्रयोगों से पता चलता है कि मौजूदा विधियाँ इष्टतम अनुक्रमिक चयन की तुलना में लगातार कम प्रदर्शन करती हैं, जबकि प्रस्तावित बाइपार्टाइट दृष्टिकोण इस अंतर को काफी हद तक कम कर देता है।

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

लेखकों ने आठ शास्त्रीय ML बेंचमार्क और एक बड़े पैमाने के LLM फाइन-ट्यूनिंग कार्य पर नौ बेसलाइनों (डेटा शैपली, बीटा शैपली, बान्ज़ाफ, इन्फ्लुएंस फंक्शन्स और लर्निंग-आधारित विधियों सहित) के विरुद्ध अपने तरीके का मूल्यांकन किया।

• इष्टतमता से अंतर (Gap to Optimality): मौजूदा विधियों ने संचयी चयन प्रदर्शन में इष्टतम डायनेमिक प्रोग्रामिंग समाधान की तुलना में 8.39% से 23.76% कम प्रदर्शन किया। सबसे बड़े अंतर उन संरचित डेटासेट में देखे गए जिनमें उच्च रेडंडेंसी थी।
• वक्रता का प्रभाव: डेटा प्रतिस्थापनीयता (substitutability) को (वक्रता के प्रॉक्सी के रूप में) हेरफेर करने वाले प्रयोगों ने पुष्टि की कि जैसे-जैसे प्रतिस्थापनीयता बढ़ती है, गेम-थ्योरेटिक विधियों का प्रदर्शन गिरता है और अभिसरित (converge) होता है, जो $(1-c)^2$ के सैद्धांतिक बाउंड के अनुरूप है।
• बाइपार्टाइट प्रदर्शन: प्रस्तावित बाइपार्टाइट विधि ने उच्चतम औसत सटीकता प्राप्त की।
  • bbc-embeddings डेटासेट पर, इसने सर्वश्रेष्ठ बेसलाइन के 0.809 के मुकाबले 0.878 सटीकता प्राप्त की।
  • digits डेटासेट पर, इसने अगले सर्वश्रेष्ठ के 0.680 के मुकाबले 0.764 सटीकता प्राप्त की।
  • बड़े पैमाने के LLM फाइन-ट्यूनिंग (DATE-LM बेंचमार्क) में, विधि (BipCov) ने 63.89% औसत सटीकता प्राप्त की, जो मजबूत बेसलाइनों जैसे RDS+ (62.88%) और रैंडम (62.82%) से बेहतर है।
• उपयोगिता अनुमान: बाइपार्टाइट सरोगेट ने लीनियर रिग्रेशन बेसलाइनों (MSE: 0.089) की तुलना में काफी कम अनुमान त्रुटि (MSE: 0.019) प्रदर्शित की, जो अंतर्निहित उपयोगिता संबंधों को पकड़ने की इसकी क्षमता को प्रमाणित करती है।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह डेटा मूल्यांकन को अनुक्रमिक निर्णय-निर्माण के साथ एकीकृत करने वाला एक सैद्धांतिक ढांचा प्रदान करता है, जो वर्तमान गेम-थ्योरेटिक विधियों की सीमाओं के लिए एक कठोर स्पष्टीकरण देता है। डेटा मानों को डायनेमिक प्रोग्रामिंग से प्राप्त इष्टतम चयन अनुक्रम के एनकोडिंग के रूप में पुनर्गठित करके, लेखक तर्क देते हैं कि मौजूदा विधियाँ मौलिक रूप से उनकी मायोपिक और लीनियर प्रकृति द्वारा सीमित हैं।

इस कार्य का महत्व निम्नलिखित में निहित है:

1. विफलता का निदान: एक सिद्धांतवादी स्पष्टीकरण (वक्रता) प्रदान करना कि डेटा मूल्यांकन विधियाँ रेडंडेंट डेटासेट पर संघर्ष क्यों करती हैं।
2. व्यावहारिक सुधार: एक गणनात्मक रूप से कुशल विधि (बाइपार्टाइट ग्राफ सरोगेट) प्रदान करना जो मौजूदा अत्याधुनिक चयन रणनीतियों से काफी बेहतर प्रदर्शन करते हुए सैद्धांतिक गारंटी बनाए रखती है।
3. स्केलेबिलिटी: यह प्रदर्शित करना कि सिद्धांतवादी डेटा चयन को अत्यधिक लागत वाले सटीक डायनेमिक प्रोग्रामिंग के बिना बड़े डेटासेट और LLM फाइन-ट्यूनिंग कार्यों तक स्केल किया जा सकता है।

लेखक अपने सैद्धांतिक बाउंड्स के संबंध में विनम्र बने हुए हैं, यह नोट करते हुए कि $(1-c)^2$ गारंटी एक 'वर्स्ट-केस लोअर बाउंड' है जो विफलताओं को समझाने के लिए उपयोगी है न कि विशिष्ट सफलता की भविष्यवाणी करने के लिए, और उनके प्रायोगिक परिणाम अक्सर इन रूढ़िवादी बाउंड्स से बेहतर प्रदर्शन दिखाते हैं।