🤖 machine learning

Sorting from Counterexamples

यह शोध पत्र $n$ वस्तुओं पर एक अज्ञात रैखिक क्रम (linear order) को सीखने के लिए $\Theta(n\log n + nk)$ की इष्टतम क्वेरी जटिलता (query complexity) स्थापित करता है, जब $k$ तक असत्य प्रति-उदाहरणों (untruthful counterexamples) की अनुमति दी जाती है, और साथ ही उन मामलों के लिए भी सीमाएँ प्रदान करता है जहाँ रैंकिंग एक निम्न-आयामी ज्यामितीय प्रतिनिधित्व (low-dimensional geometric representation) स्वीकार करती है।

मूल लेखक: Noga Alon, Shay Moran, Shlomo Moran

प्रकाशित 2026-08-25

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

CC BY 4.0

मूल लेखक: Noga Alon, Shay Moran, Shlomo Moran

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

कल्पना कीजिए कि आप एक कंप्यूटर को यह समझने के लिए सिखाने की कोशिश कर रहे हैं कि लोग चीजों को कैसे पसंद करते हैं, जैसे कि रेस्तरां को सबसे अच्छे से सबसे बुरे के क्रम में रैंक करना। वास्तविक दुनिया में, इसे सही ढंग से करना केवल एक प्रश्न पूछने का मामला नहीं होता है। इसके बजाय, आप कंप्यूटर से एक पूरी सूची का अनुमान लगाने के लिए कह सकते हैं, और फिर एक इंसान एक गलती की ओर इशारा करता है: "आपने सुशी वाले स्थान को पहले रखा है, लेकिन वास्तव में मैं फलाफेल वाले स्थान को अधिक पसंद करता हूँ।" कंप्यूटर इस एक सुधार से सीखता है और फिर से प्रयास करता है। यह आगे-पीछे की प्रक्रिया सूचना को व्यवस्थित करने के लिए मशीनों के सीखने का एक मौलिक तरीका है, लेकिन यह बहुत कठिन हो जाता है यदि फीडबैक देने वाला व्यक्ति कभी-कभी गलत हो, या शायद उसका दिन ही खराब हो। वैज्ञानिकों के लिए चुनौती यह पता लगाना है कि मशीन को सही क्रम के बारे में निश्चित होने के लिए कितने अनुमान लगाने और सुधार प्राप्त करने की आवश्यकता है, खासकर जब उन सुधारों में से कुछ झूठ हों।

यह प्रश्न कंप्यूटर विज्ञान और गणित के मिलन बिंदु पर स्थित है, विशेष रूप से लर्निंग थ्योरी (learning theory) के क्षेत्र में, जो यह अध्ययन करता है कि एल्गोरिदम डेटा के आधार पर अपने प्रदर्शन में कैसे सुधार कर सकते हैं। मुख्य कठिनाई यह है कि मशीन को हमेशा एक पूर्ण, तर्कसंगत सूची प्रस्तावित करनी होती है, न कि केवल अलग-थलग अनुमानों का एक संग्रह। यदि वह अनुमान लगाता है कि A, B से बेहतर है, और B, C से बेहतर है, तो उसे तार्किक रूप से यह निष्कर्ष निकालना चाहिए कि A, C से बेहतर है। जब फीडबैक शोरपूर्ण (noisy) या विरोधाभासी होता है, तो इस तार्किक निरंतरता को बनाए रखना एक बहुत बड़ी बाधा बन जाता है। शोधकर्ता लंबे समय से जानते हैं कि यदि प्रत्येक फीडबैक सटीक है, तो वस्तुओं की संख्या बढ़ने के साथ अनुमानों की संख्या एक अनुमानित तरीके से बढ़ती है। हालांकि, जैसे ही आप कुछ झूठों की अनुमति देते हैं, समस्या नाटकीय रूप से बदल जाती है, और अब तक, उन झूठों की सटीक लागत को पूरी तरह से समझा नहीं गया था।

एक नए अध्ययन में, शोधकर्ताओं नोग अलों, शे मौरन और श्लोमो मौरन ने इस पहेली को सामान्य मामले के लिए हल कर दिया है। उन्होंने निर्धारित किया कि एक मशीन को एक अज्ञात रैंकिंग सीखने के लिए कितने अनुमानों की आवश्यकता होती है जब उसे प्राप्त सुधारों में से कुछ संख्या तक गलत हो सकते हैं। उनका कार्य एक आश्चर्यजनक सत्य प्रकट करता है: जबकि मशीन हर कोई ईमानदार होने पर सही क्रम कुशलतापूर्वक सीख सकती है, प्रत्येक झूठ जो वह सामना करती है, उसे एक भारी कीमत चुकानी पड़ती है। विशेष रूप से, प्रत्येक असत्य सुधार के लिए, मशीन को सूची में मौजूद वस्तुओं के बराबर लगभग उतने ही अतिरिक्त अनुमान लगाने होंगे। यदि एक हजार रेस्तरां हैं और मशीन को दस झूठ मिलते हैं, तो उसे उत्तर सुनिश्चित करने के लिए हजारों अतिरिक्त अनुमान लगाने होंगे। यह निष्कर्ष सिद्ध करता है कि शोर की लागत केवल कठिनाई में एक मामूली वृद्धि नहीं है, बल्कि एक मौलिक बहुलकीकरण (multiplication) है जो समस्या के आकार के साथ सीधे तौर पर बढ़ता है।

टीम इस निष्कर्ष पर एक ज्यामितीय आकृति खोजने के अभ्यास के रूप में इस समस्या को मानकर पहुँची। उन्होंने कल्पना की कि प्रत्येक संभव रैंकिंग उच्च-आयामी स्थान (high-dimensional space) के भीतर एक विशिष्ट क्षेत्र है। जब मशीन एक अनुमान लगाती है और एक सुधार प्राप्त करती है, तो वह प्रभावी रूप से इस स्थान के एक हिस्से को काट देती है, जिससे यह सीमित हो जाता है कि वास्तविक उत्तर कहाँ छिपा हो सकता है। एक आदर्श दुनिया में, एक एकल सुधार शेष संभावनाओं का आधा हिस्सा काट देगा, जिससे मशीन तेजी से उत्तर पा सकेगी। शोधकर्ताओं ने दिखाया कि भले ही झूठ मौजूद हों, वे एक ऐसी रणनीति बना सकते हैं जो संभावनाओं के एक स्थिर अंश को काटती रहती है, लेकिन एक झूठ इस प्रक्रिया को काफी धीमा कर देता है। उन्होंने एक शक्तिशाली गणितीय उपकरण का उपयोग किया, जो उत्तल आकृतियों (convex shapes) के गुरुत्वाकर्षण केंद्र के बारे में एक प्रमेय है, यह सिद्ध करने के लिए कि उनकी रणनीति काम करती है। इस दृष्टिकोण ने उन्हें एक ऐसा एल्गोरिदम बनाने की अनुमति दी जिसे यह जानने की आवश्यकता नहीं है कि कितने झूठ बोले जाएंगे; यह बस चलते समय शोर के अनुकूल हो जाता है, यह सुनिश्चित करता है कि यह विरोधाभासों के चक्र में फंसे बिना अंततः सत्य को खोज ले।

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

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

तकनीकी सारांश: प्रति-उदाहरणों (Counterexamples) से सॉर्टिंग

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

यह शोध पत्र एक अज्ञात रैखिक क्रम (रैंकिंग) $\pi^*$ को सीखने की समस्या की जांच करता है, जो $n$ वस्तुओं पर आधारित है और एक संवादात्मक प्रश्न प्रक्रिया (interactive query process) के माध्यम से प्राप्त किया जाता है। प्रत्येक दौर में, एक शिक्षार्थी (learner) एक पूर्ण रैखिक क्रम $\pi$ प्रस्तावित करता है। ओरेकल (oracle) दो में से एक तरीके से प्रतिक्रिया देता है:

पुष्टि (Confirmation): घोषित करता है कि $\pi = \pi^*$ , जिससे संवाद समाप्त हो जाता है।
प्रति-उदाहरण (Counterexample): वस्तुओं का एक जोड़ा $\{i, j\}$ लौटाता है जो यह दर्शाता है कि $\pi$ में उनका सापेक्ष क्रम गलत है।

मुख्य चुनौती असत्य प्रति-उदाहरणों (untruthful counterexamples) की उपस्थिति है। लौटाए गए जोड़े $\{i, j\}$ को सत्य (truthful) तब कहा जाता है जब प्रस्तावित क्रम $\pi$ और लक्ष्य क्रम $\pi^*$ के बीच $i$ और $j$ का सापेक्ष क्रम भिन्न हो। इसके विपरीत, एक प्रति-उदाहरण असत्य (untruthful) है यदि $\pi$ और $\pi^*$ वास्तव में $i$ और $j$ के सापेक्ष क्रम पर सहमत हैं। मॉडल यह मानता है कि लौटाए गए प्रति-उदाहरणों में से अधिकतम $k$ असत्य (झूठ) हैं, लेकिन शिक्षार्थी को पहले से $k$ के मान का पता नहीं होता है। लक्ष्य न्यूनतम प्रश्नों (दौरों) का उपयोग करके लक्ष्य रैंकिंग $\pi^*$ की पहचान करना है।

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

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

लेखक क्रमपरिवर्तनों (permutations) के ज्यामितीय निरूपण, उत्तल ज्यामिति (convex geometry), और संयोजन संबंधी निचली सीमा निर्माण (combinatorial lower-bound constructions) के संयोजन का उपयोग करते हैं।

1. ज्यामितीय निरूपण और ग्रुनबाम का प्रमेय (अप्रतिबंधित रैंकिंग)

सामान्य मामले के लिए जहाँ लक्ष्य कोई भी $n!$ रैंकिंग हो सकती है, लेखक एक ज्यामितीय निरूपण का उपयोग करते हैं जहाँ प्रत्येक रैंकिंग हाइपरक्यूब $[0, 1]^n$ में एक सेल (cell) के अनुरूप होती है। एक बिंदु $x \in [0, 1]^n$ उसके निर्देशांकों के सॉर्ट किए गए क्रम के आधार पर एक रैंकिंग प्रेरित करता है।

सत्य मामला (Truthful Case): जब सभी प्रति-उदाहरण सत्य होते हैं, तो सुसंगत बिंदुओं का सेट एक उत्तल पिंड (convex body) बनाता है। शिक्षार्थी इस पिंड के केंद्रक (centroid) द्वारा प्रेरित रैंकिंग को क्वेरी करता है। ग्रुनबाम का प्रमेय (Grünbaum's Theorem) गारंटी देता है कि किसी उत्तल पिंड के केंद्रक को समाहित करने वाला कोई भी हाफस्पेस (halfspace) उस पिंड के आयतन के कम से कम $1/e$ भाग को समाहित करता है। इस प्रकार, एक गलत अनुमान शेष आयतन के एक स्थिर अंश को समाप्त कर देता है, जिससे $O(n \log n)$ जटिलता प्राप्त होती है।
शोर वाला मामला (Noisy Case): लक्ष्य को स्थायी रूप से त्यागने के बजाय असत्य प्रति-उदाहरणों को संभालने के लिए, लेखक 'हार्ड एलिमिनेशन' के स्थान पर एक स्मूथ वेटेड अपडेट (smooth weighted update) का उपयोग करते हैं। वे हाइपरक्यूब पर एक डिस्क्रीट वेट के बजाय एक लॉग-कॉन्केव घनत्व (log-concave density) बनाए रखते हैं। अपडेट नियम एक सरोगेट लॉस फंक्शन का उपयोग करता है जिसे लॉग-कॉन्केविटी को बनाए रखने के लिए डिज़ाइन किया गया है। यह लॉग-कॉन्केव संस्करण के ग्रुनबाम प्रमेय को लागू करने की अनुमति देता है। अपडेट नियम उन रैंकिंग्स को दंडित करता है जो प्रति-उदाहरण के साथ असंगत हैं, लेकिन वास्तविक लक्ष्य के पास के भार को धीरे-धीरे कम करता है (केवल $n$ से संबंधित कारक द्वारा), जबकि कुल द्रव्यमान हर दौर में एक स्थिर कारक से कम हो जाता है।

2. ज्यामितीय वर्गों के लिए स्ट्रॉन्ग मेजॉरिटी (Strong Majority)

कम-आयामी ज्यामितीय संरचना वाले रैंकिंग वर्गों के लिए (जहाँ वस्तुएं वेक्टर $v_i \in \mathbb{R}^d$ हैं और रैंकिंग एक दिशा $w$ पर प्रोजेक्शन द्वारा प्रेरित होती हैं), लेखक वेटेड मेजॉरिटी एल्गोरिदम को अनुकूलित करते हैं।

साधारण युग्मवार मेजॉरिटी (जो चक्र बना सकती है) के बजाय, वे एक स्ट्रॉंग-मेजॉरिटी संबंध (strong-majority relation) को परिभाषित करते हैं: एक किनारा $i \to j$ तभी मौजूद होता है जब वर्तमान भार का एक अंश $1 - O(1/d)$ इसका समर्थन करता है।
कैराथियोडोरी के प्रमेय (Carathéodory's Theorem) का उपयोग करते हुए, वे सिद्ध करते हैं कि $d$ -आयामी ज्यामितीय वर्गों में, यह स्ट्रॉंग-मेजॉरिटी संबंध अचक्रीय (acyclic) है और इसे एक वैध रैखिक क्रम में विस्तारित किया जा सकता है।
यह शिक्षार्थी को एक वैध क्रम क्वेरी करने की अनुमति देता है जबकि यह सुनिश्चित करता है कि कोई भी प्रति-उदाहरण कुल भार के एक महत्वपूर्ण अंश ( $\Omega(1/d)$ ) को समाप्त कर देता है।

3. निचली सीमा निर्माण (Lower Bound Constructions)

निचली सीमाएँ दो अलग-अलग प्रतिकूल रणनीतियों से प्राप्त की गई हैं:

सॉर्टिंग तर्क ( $\Omega(n \log n)$ ): तुलना-आधारित सॉर्टिंग (जैसे मर्जसॉर्ट) से अनुकूलित, एक प्रतिकूल (adversary) शिक्षार्थी को एक संतुलित तुलना वृक्ष (balanced comparison tree) को पार करने के लिए मजबूर करता है, जिसके लिए शोर रहित सेटिंग में भी $\Omega(n \log n)$ प्रश्नों की आवश्यकता होती है।
कॉन्डोरसेट चक्र (Condorcet Cycle) ( $\Omega(nk)$ ): प्रतिकूल $n$ वस्तुओं के निर्देशित चक्र के आधार पर उम्मीदवार रैंकिंग का एक सेट बनाता है। चक्र के किनारों को प्रति-उदाहरण के रूप में लौटाकर, प्रतिकूल शिक्षार्थी को $n$ उम्मीदवारों के बीच अंतर करने के लिए मजबूर कर सकता है, जहाँ प्रत्येक उम्मीदवार तब तक व्यवहार्य रहता है जब तक कि उसका विशिष्ट "वर्जित" किनारा $k+1$ बार वापस न मिल जाए। इससे $\Omega(nk)$ का खर्च आता है।
ज्यामितीय निचली सीमाएं: $d$ -आयामी वर्गों के लिए, लेखक टर्निंग पॉइंट्स को पहचानने के लिए बहुपद रैंकिंग (moment curve पर वस्तुएं) का उपयोग करते हैं, जो चक्र निर्माण से $\Omega(dk)$ लागत के साथ मिलकर $\Omega(d \log n)$ प्रश्नों की आवश्यकता को दर्शाता है।

मुख्य परिणाम

1. अप्रतिबंधित रैंकिंग (Unrestricted Rankings)

$n$ वस्तुओं पर अधिकतम $k$ असत्य प्रति-उदाहरणों के साथ एक मनमाने लक्ष्य रैंकिंग के लिए:

इष्टतम क्वेरी जटिलता: $\Theta(n \log n + nk)$ ।
ऊपरी सीमा (Upper Bound): एक नियतक (deterministic) शिक्षार्थी द्वारा प्राप्त किया जाता है जिसे $k$ के इनपुट की आवश्यकता नहीं होती है। एल्गोरिदम एक लॉग-कॉन्केव घनत्व अपडेट का उपयोग करता है और केंद्रक-प्रेरित रैंकिंग को क्वेरी करता है।
निचली सीमा (Lower Bound): स्थिरांक कारकों तक ऊपरी सीमा से मेल खाती है। $\Omega(n \log n)$ पद सॉर्टिंग से उत्पन्न होता है, और $\Omega(nk)$ पद कॉन्डोरसेट चक्र निर्माण से उत्पन्न होता है।
निहितार्थ: जबकि शोर रहित सॉर्टिंग $O(n \log n)$ है, प्रत्येक असत्य प्रति-उदाहरण $O(n)$ का अतिरिक्त खर्च लाता है, जो मानक वेटेड-मेजॉरिटी लर्निंग की तुलना में एक महत्वपूर्ण वृद्धि है जहाँ लागत $O(k)$ होती है।

2. ज्यामितीय रैंकिंग वर्ग

$\mathbb{R}^d$ में वेक्टर्स द्वारा प्रेरित रैंकिंग वर्गों के लिए:

ऊपरी सीमा: $O(d^2 \log n + dk)$ ।
निचली सीमा: $\Omega(d \log n + dk)$ ।
अंतराल (Gap): शोर रहित पद में $d$ का एक कारक अंतराल बना हुआ है ( $d^2 \log n$ बनाम $d \log n$ )। ऊपरी सीमा स्ट्रॉंग-मेजॉरिटी ग्राफ के लीनियर एक्सटेंशन या सेंटरपॉइंट दृष्टिकोण को क्वेरी करके प्राप्त की जाती है।
उचितता (Properness): शिक्षार्थी को ऐसे रैंकिंग आउटपुट करने के लिए सीमित किया जा सकता है जो स्वयं ज्यामितीय रूप से साकार योग्य (दिशा $\mathbb{R}^d$ द्वारा प्रेरित) हों।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह सीमित शोर के तहत प्रति-उदाहरणों से रैंकिंग सीखने के लिए क्वेरी जटिलता का एक सटीक चित्रण प्रदान करता है, जो उचितता (वैध रैखिक क्रम आउटपुट करने) को बनाए रखने के विशिष्ट खर्च को उजागर करता है।

उचितता की लागत (The Cost of Properness): लेखक इस बात पर जोर देते हैं कि शिक्षार्थी को एक रैखिक क्रम आउटपुट करने के लिए मजबूर करना (arbitrary pairwise predictions के बजाय) शोर की उपस्थिति में जटिलता को मौलिक रूप से बदल देता है। मानक वेटेड-मेजॉरिटी में, एक असत्य प्रति-उदाहरण की लागत $O(1)$ होती है; यहाँ, यह $O(n)$ है क्योंकि शिक्षार्थी को एक वैध क्रम बनाने के लिए संभावित चक्रों (Condorcet phenomena) को हल करना पड़ता है।
ज्यामितीय अंतर्दृष्टि: यह कार्य प्रदर्शित करता है कि कैसे उत्तल ज्यामिति (ग्रुनबाम प्रमेय) और लॉग-कॉन्केव माप का उपयोग शोर के प्रति मजबूत, उचित शिक्षण एल्गोरिदम डिजाइन करने के लिए किया जा सकता है, जो आंशिक सूचना के तहत सॉर्टिंग के लिए उपयोग की जाने वाली तकनीकों का विस्तार करता है।
पैरामीटर-मुक्त लर्निंग: प्रस्तावित एल्गोरिदम को $k$ के ज्ञान की आवश्यकता नहीं होती है, जिससे वे विभिन्न शोर स्तरों के प्रति मजबूत बनते हैं।
खुले प्रश्न: लेखक नोट करते हैं कि जबकि $k$ पर निर्भरता सटीक है, ज्यामितीय शोर रहित पद में $d$ पर निर्भरता ( $O(d^2 \log n)$ बनाम $O(d \log n)$ ) अभी भी एक खुला प्रश्न है। वे सामान्य-उद्देश्य वाले सैंपलिंग से बचने के लिए कुशल संयोजन संबंधी कार्यान्वयन के विकास को भी भविष्य के कार्य के रूप में छोड़ देते हैं।

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