📊 statistics

Majority-of-Three is Optimal

यह शोध पत्र एक संक्षिप्त प्रमाण प्रदान करता है जो यह दर्शाता है कि तीन स्वतंत्र सुसंगत क्लासिफायर (classifiers) का बहुमत मत (majority vote) रियलाइजेबल (realizable) PAC सेटिंग के भीतर एक इष्टतम शिक्षार्थी (optimal learner) बनता है, जिससे पिछले वोटिंग-आधारित शिक्षण एल्गोरिदम का विश्लेषण सरल हो जाता है।

मूल लेखक: Divit Rawal, Nikita Zhivotovskiy

प्रकाशित 2026-06-12

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

CC BY 4.0

मूल लेखक: Divit Rawal, Nikita Zhivotovskiy

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

यहाँ "Majority-of-Three is Optimal" शोध पत्र का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

बड़ी तस्वीर: मशीन लर्निंग के "तीन बुद्धिमान पुरुष" (Three Wise Men)

कल्पना कीजिए कि आप एक कंप्यूटर को तस्वीरों में बिल्लियों को पहचानना सिखाने की कोशिश कर रहे हैं। आपके पास तस्वीरों का एक बहुत बड़ा ढेर (डेटा) है, और आप जानते हैं कि आपके संभावित नियमों की सूची में कहीं न कहीं एक सटीक "बिल्ली का नियम" (cat rule) मौजूद है (इसे realizable setting कहा जाता है)।

इस क्षेत्र का बड़ा सवाल यह रहा है: कंप्यूटर को नियम पूरी तरह से सिखाने के लिए, उच्च आत्मविश्वास (high confidence) के साथ, आपको उसे कितनी तस्वीरें दिखानी होंगी?

दशकों तक, इसका उत्तर बहुत जटिल था। सबसे प्रसिद्ध विधि के लिए एक बहुत ही जटिल एल्गोरिदम की आवश्यकता होती थी (जैसे कि 50 औजारों वाला एक स्विस आर्मी नाइफ) ताकि गणितीय रूप से सटीक उत्तर प्राप्त किया जा सके। इस शोध पत्र के लेखक कहते हैं: "वास्तव में, आपको स्विस आर्मी नाइफ की आवश्यकता नहीं है। आपको बस तीन सरल औजारों की आवश्यकता है।"

मुख्य विचार: "तीन न्यायाधीशों" का उदाहरण

यह शोध पत्र सिद्ध करता है कि सबसे सरल संभव वोटिंग सिस्टम वास्तव में सबसे अच्छा संभव सिस्टम है।

कल्पना कीजिए कि आपके सामने एक कठिन गणित की समस्या है। एक जीनियस से इसे हल करने के लिए कहने के बजाय, आप समस्या को तीन छोटे, स्वतंत्र भागों में विभाजित करते हैं।

आप भाग A न्यायाधीश 1 को देते हैं।
आप भाग B न्यायाधीश 2 को देते हैं।
आप भाग C न्यायाधीश 3 को देते हैं।

प्रत्यनीक न्यायाधीश अपने हिस्से का अध्ययन करता है और एक ऐसा समाधान निकालता है जो उनके द्वारा देखे गए डेटा के साथ पूरी तरह फिट बैठता है।

न्यायाधीश 1 किसी पेचीदा मामले (edge case) में गलती कर सकता है।
न्यायाधीश 2 एक अलग गलती कर सकता है।
न्यायाधीश 3 तीसरी गलती कर सकता है।

हालाँकि, यदि आप अंतिम उत्तर पर वोट करने के लिए तीनों से पूछते हैं, और आप उस विकल्प को चुनते हैं जिस पर वे तीनों में से कम से कम दो सहमत हैं (Majority Vote), तो अंतिम परिणाम अविश्वसनीय रूप से विश्वसनीय होता है।

शोध पत्र का दावा:
लेखक सिद्ध करते हैं कि यदि आप तीन स्वतंत्र "शिक्षकों" (learners/judges) को लेते हैं और उन्हें वोट करने देते हैं, तो परिणामी "मेजोरिटी-ऑफ-थ्री" (Majority-of-Three) शिक्षार्थी इष्टतम (optimal) है। इसका अर्थ है कि यह दक्षता की पूर्ण सैद्धांतिक सीमा को प्राप्त करता है। आप इससे बेहतर नहीं कर सकते, चाहे आपका एल्गोरिदम कितना भी जटिल क्यों न हो।

इसे सिद्ध करना कठिन क्यों था?

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

पिछले प्रमाणों के लिए आवश्यक था:

नेस्टेड सैंपल्स (Nested Samples): जैसे किसी छात्र को पहले अध्याय 1 पढ़ने के लिए कहना, फिर अध्याय 1 और 2, फिर अध्याय 1, 2 और 3। यह एक जटिल निर्भरता श्रृंखला (dependency chain) बनाता है।
जटिल गणित: इसका विश्लेषण ऊन के गोले को सुई से सुलझाने जैसा था।

इस शोध पत्र के लेखकों ने यह सिद्ध करके प्रमाण को सरल बना दिया कि आपको "नेस्टेड" दृष्टिकोण की आवश्यकता नहीं है। आप बस डेटा के तीन स्वतंत्र समूहों (जैसे तीन अलग-अलग कक्षाएं) को ले सकते हैं और प्रत्येक में एक छात्र को प्रशिक्षित कर सकते हैं।

गुप्त सूत्र: "ओवरलैप" (Overlap) की समस्या

इसे सिद्ध करने के लिए, लेखकों को एक विशिष्ट गणितीय पहेली को हल करना था: दो अलग-अलग छात्र कितनी बार बिल्कुल एक ही गलती करते हैं?

यदि छात्र A और छात्र B दोनों एक ही प्रश्न का गलत उत्तर देते हैं, तो यह एक "खराब ओवरलैप" (bad overlap) है।
यदि वे अलग-अलग गलतियाँ करते हैं, तो मेजोरिटी वोट काम आता है (क्योंकि तीसरा छात्र सही होने की संभावना रखता है)।

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

"AI" का मोड़

दिलचस्प बात यह है कि शोध पत्र में इसे लिखने के बारे में एक अनूठा परिशिष्ट (appendix) शामिल है।

लेखकों के पास पहले एक लंबा, जटिल प्रमाण था।
फिर उन्होंने इसे सरल बनाने के लिए एक AI (Large Language Model) की मदद ली।
उन्होंने AI को समस्या और कुछ संकेत दिए, और पूछा कि क्या वह गणित को समझाने का एक छोटा तरीका ढूंढ सकता है।
AI ने एक "रिकर्सिव" (recursive/चरण-दर-चरण) संरचना का सुझाव दिया जो उनके मूल संस्करण की तुलना में बहुत अधिक स्पष्ट थी।
लेखकों ने हर चरण को सत्यापित किया और अंतिम शोध पत्र स्वयं लिखा।

यह शीर्ष स्तर के गणितीय शोध पत्रों के दुर्लभ उदाहरणों में से एक है जो गणित उत्पन्न करने के लिए नहीं, बल्कि प्रमाण को सरल बनाने के लिए AI को स्पष्ट रूप से श्रेय देता है।

एक वाक्य में सारांश

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

तकनीकी सारांश: मेजॉरिटी-ऑफ-थ्री (Majority-of-Three) इष्टतम है

समस्या विवरण
यह शोध पत्र रियलाइजेबल सेटिंग (realizable setting) में PAC लर्निंग के लिए इष्टतम सैंपल कॉम्प्लेक्सिटी (sample complexity) निर्धारित करने की केंद्रीय समस्या को संबोधित करता है। जबकि हनेके (Hanneke [Han16]) द्वारा इष्टतम लर्नर्स के अस्तित्व को स्थापित किया गया था (साइमन [Sim15] के कार्य पर आधारित), परिणामी एल्गोरिदम और उनके संभावabilistic विश्लेषण जटिल हैं। एक विशिष्ट, सरल उम्मीदवार एक इष्टतम लर्नर के रूप में "मेजॉरिटी-ऑफ-थ्री" (majority-of-three) नियम है: एक प्रशिक्षण नमूने (training sample) को तीन स्वतंत्र ब्लॉकों में विभाजित करना, प्रत्येक ब्लॉक पर एक कंसिस्टेंट क्लासिफायर (consistent classifier) प्रशिक्षित करना, और बहुमत (majority vote) को आउटपुट के रूप में देना। पिछले कार्य [AAHLZ24] ने सिद्ध किया कि यह नियम अपेक्षा (expectation) में एक इष्टतम बाउंड प्राप्त करता है और एक निकट-इष्टतम (near-optimal) PAC बाउंड प्राप्त करता है (डबली लॉगरिदमिक कारक, $\log \log(\min\{n/d, 1/\delta\})$ तक)। [AAHLZ24] के लेखकों ने अनुमान लगाया था कि मेजॉरिटी-ऑफ-थ्री नियम इन अतिरिक्त कारकों के बिना इष्टतम PAC बाउंड प्राप्त करता है। यह शोध पत्र उस अनुमान को सिद्ध करने के लिए एक प्रमाण प्रदान करता है।

कार्यप्रणाली
प्रमाण मेजॉरिटी-ऑफ-थ्री क्लासिफायर, $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$ , की त्रुटि (error) पर एक उच्च-संभाव्यता (high-probability) ऊपरी बाउंड स्थापित करता है, जहाँ प्रत्येक $\hat{f}_i$ आकार $m = n/3$ के एक स्वतंत्र ब्लॉक $S_i$ पर प्रशिक्षित एक कंसिस्टेंट क्लासिफायर है।

ओवरलैप मोमेंट्स (Overlap Moments) में न्यूनीकरण:
बहुमत मत (majority vote) की त्रुटि केवल तभी होती है जब तीन में से कम से कम दो क्लासिफायर किसी बिंदु $x$ को गलत वर्गीकृत करते हैं। यदि $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ $i$ -वें क्लासिफायर का एरर सेट है, तो कुल त्रुटि युग्मवार इंटरसेक्शन (pairwise intersections) के योग द्वारा सीमित होती है:
$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_ 3) + P(E_1 \cap E_3).$
प्रमाण इन इंटरसेक्शन प्रोबेबिलिटीज के $L_q$ मोमेंट्स, विशेष रूप से $\|P(E_1 \cap E_2)\|_{L_q}$ , को बाउंड करने पर केंद्रित है।
मुख्य तकनीकी उपकरण: प्रपोजिशन 2.2 (Proposition 2.2):
तर्क का मुख्य हिस्सा प्रपोजिशन 2.2 है, जो आकार $m$ के दो स्वतंत्र नमूनों $S$ और $T$ के एरर सेट्स के ओवरलैप के लिए एक मोमेंट बाउंड प्रदान करता है। एक VC क्लास $\mathcal{C}$ (VC dimension $d$ के साथ) और एक डिटरमिनिस्टिक कंसिस्टेंट सिलेक्टर $A$ (जहाँ $A(S) \cap S = \emptyset$ ) के लिए, प्रपोजिशन कहता है:
$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$
यह परिणाम साइमन [Sim15] के ओवरलैप अनुमान के समान है लेकिन नेस्टेड (nested) नमूनों के बजाय स्वतंत्र नमूनों पर लागू होता है। नेस्टेड संरचनाओं के पिछले विश्लेषणों में मौजूद डबली लॉगरिदमिक कारकों से बचने के लिए स्वतंत्रता (independence) अत्यंत महत्वपूर्ण है।
रिकर्सिव डिकम्पोजिशन और कंडीशनल प्रोबेबिलिटीज:
प्रपोजिशन 2.2 को सिद्ध करने के लिए, लेखक $q$ स्वतंत्र टेस्ट पॉइंट्स $X = (X_1, \dots, X_q)$ को पेश करके ओवरलैप के $q$ -वें मोमेंट का विश्लेषण करते हैं। मोमेंट को $\mathbb{E}_X [p_q(X)^2]$ के रूप में पुनर्गठित किया जाता है, जहाँ $p_q(X) = P(X \subseteq A(S))$ है।
चेन-रूल डिकम्पोजिशन का उपयोग करते हुए, $p_q(X)$ को कंडीशनल इंक्लूजन प्रोबेबिलिटीज के उत्पाद के रूप में व्यक्त किया जाता है:
$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{जहाँ } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$
प्रमाण लेम्मा 3.1 पर निर्भर करता है, जो इन कंडीशनल प्रोबेबिलिटीज के लिए एक टेल बाउंड (tail bound) है। यह दिखाता है कि एक कंडीशनिंग इवेंट $E_z$ (जिसकी प्रोबेबिलिटी $p_z$ है) के लिए, कंडीशनल इंक्लूजन प्रोबेबिलिटी $\alpha_z(X)$ के एक थ्रेशोल्ड $a$ से अधिक होने की संभावना इस प्रकार सीमित है:
$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$
यह बाउंड VC डायमेंशन टर्म को बढ़ाए बिना कंडीशनिंग इवेंट की "दुर्लभता" (rarity) को नियंत्रित करता है।
रिकर्सिव तर्क (Recursive Argument):
लेखक एक भारित फंक्शनल (weighted functional) $M_k$ को परिभाषित करते हैं जिसमें स्क्वेर्ड कंडीशनल प्रोबेबिलिटीज और एक लॉगरिदमिक टर्म शामिल है। वे एक रिकर्सन $M_k \leq \frac{960}{m} M_{k-1}$ स्थापित करते हैं। $k=1$ से $q$ तक इस रिकर्सन को दोहराने से वांछित $q$ -वें मोमेंट के लिए बाउंड प्राप्त होता है, जिसे फिर $q = \lceil \log(1/\delta) \rceil$ के साथ मार्कोव की असमानता (Markov's inequality) का उपयोग करके एक उच्च-संभाव्यता बाउंड में परिवर्तित किया जाता है।

मुख्य योगदान और परिणाम

इष्टतमता का प्रमाण (Optimality Proof): यह शोध पत्र सिद्ध करता है कि मेजॉरिटी-ऑफ-थ्री लर्नर रियलाइजेबल PAC सेटिंग में इष्टतम सैंपल कॉम्प्लेक्सिटी प्राप्त करता है। विशेष रूप से, किसी भी वितरण $P$ , टार्गेट $f^\star$ , और कॉन्फिडेंस $\delta$ के लिए:
$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$
यह क्लासिक लोअर बाउंड [EHKV89] के बराबर है (एक यूनिवर्सल कांस्टेंट तक)।
विश्लेषण का सरलीकरण: यह प्रमाण पिछले इष्टतम लर्नर्स (जैसे हनेके [Han16] और लार्सन [Lar23] का बैगिंग विश्लेषण) की एल्गोरिद्मिक संरचना और संभावabilistic विश्लेषण को सरल बनाता है। यह जटिल नेस्टेड सैंपल संरचनाओं और परिणामस्वरूप होने वाले डबली लॉगरिदमिक कारकों की आवश्यकता को समाप्त करता है।
नेस्टिंग के ऊपर स्वतंत्रता (Independence over Nesting): यह कार्य प्रदर्शित करता है कि नेस्टेड नमूनों (के बजाय) के रूप में स्वतंत्र ब्लॉक्स का उपयोग करने से एक स्वच्छ विश्लेषण संभव होता है जो उन डबली लॉगरिदमिक कारकों से बचता है जिन्हें पहले सरल वोटिंग स्कीमों के लिए आवश्यक माना जाता था।

महत्व और दावे
लेखक दावा करते हैं कि यह परिणाम [AAHLZ24] के उस अनुमान को हल करता है जो मेजॉरिटी-ऑफ-थ्री नियम की इष्टतमता के संबंध में था। यह शोध पत्र इस परिणाम को PAC लर्निंग के सिद्धांत में एक महत्वपूर्ण सरलीकरण के रूप में प्रस्तुत करता है, जो कि "सरलतम वोटिंग स्कीम" प्रदान करता है जो प्रमाणित रूप से इष्टतम है। प्रमाण को संक्षिप्त और स्व-निहित (self-contained) बताया गया है, जो पूर्ववर्ती अधिक जटिल रचनाओं के बजाय कंडीशनल इंक्लूजन प्रोबेबिलिटीज के एक नवीन रिकर्सिव डिकम्पोजिशन पर आधारित है।

शोध पत्र में एक परिशिष्ट (appendix) भी शामिल है जो प्रमाण को सरल बनाने के लिए लार्ज लैंग्वेज मॉडल्स (LLMs) के उपयोग का विवरण देता है। लेखक नोट करते हैं कि प्रारंभिक प्रमाण लंबा था और पहले लेखक द्वारा व्युत्पन्न किया गया था, लेकिन वैकल्पिक तर्कों को खोजने के लिए LLM सहायता का उपयोग किया गया था, जिससे अंतिम पांडुलिपि में प्रस्तुत संक्षिप्त रिकर्सिव रूप प्राप्त हुआ। गणितीय दावों को लेखकों द्वारा सत्यापित और लिखा गया है।