📊 statistics

Realizable Bayes-Consistency for General Metric Losses

यह शोध पत्र सामान्य मीट्रिक लॉस के साथ रियलाइजेबल सेटिंग में स्ट्रॉन्ग यूनिवर्सल बेयस-कंसिस्टेंसी के लिए आवश्यक और पर्याप्त स्थितियाँ स्थापित करके लर्निंग थ्योरी की एक खुली समस्या को हल करता है, जो परिकल्पना वर्ग (हाइपोथीसिस क्लास) को एक अनंत गैर-बढ़ते $(\gamma_k)$ -लिट्लस्टोन ट्री की अनुपस्थिति के माध्यम से अभिलक्षणित करता है।

मूल लेखक: Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich

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

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

CC BY 4.0

मूल लेखक: Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich

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

मुख्य विचार: बिना सुरक्षा जाल के सीखना

कल्पना कीजिए कि आप एक रोबट को भविष्य की भविष्यवाणी करना सिखा रहे हैं। कई मानक मशीन लर्निंग समस्याओं में, रोबट गलतियाँ करता है, लेकिन गलती की "लागत" (cost) सीमित होती है। यदि वह गलत रंग का अनुमान लगाता है, तो वह 1 अंक खोता है। यदि वह गलत संख्या का अनुमान लगाता है, तो वह 1 अंक खोता है। सबसे खराब स्थिति हमेशा ज्ञात और प्रबंधनीय होती है।

हालाँकि, यह शोध पत्र एक बहुत अधिक डरावनी स्थिति से निपटता है: अनबाउंडेड मेट्रिक लॉस (Unbounded Metric Loss)।

इसे इस तरह सोचें जैसे रोबट किसी स्थान की भविष्यवाणी करने का खेल खेल रहा हो।

यदि वह कुछ इंच की चूक करता है, तो दंड छोटा होता है।
यदि वह कुछ मील की चूक करता है, तो दंड बड़ा होता है।
यदि वह हज़ार मील की चूक करता है, तो दंड खगोलीय (astronomical) होता है।

इस दुनिया में, गलत होने की "लागत" सीमित नहीं है। यह अनंत (infinity) तक जा सकती है। यह शोध पत्र एक मौलिक प्रश्न पूछता है: किन परिस्थितियों में एक लर्निंग एल्गोरिदम यह गारंटी दे सकता है कि वह अंततः पूरी तरह से सीख जाएगा, भले ही एक दुर्लभ गलती की लागत अनंत हो सकती हो?

लेखक "रियलाइज़ेबल" (Realizable) सेटिंग पर ध्यान केंद्रित करते हैं। इसका अर्थ है कि हम यह मान रहे हैं कि ब्रह्मांड में एक आदर्श नियम मौजूद है जिसे रोबट खोजने की कोशिश कर रहा है। डेटा शोर (noisy) नहीं है; बस रोबट ने अभी तक पर्याप्त डेटा नहीं देखा है।

मुख्य समस्या: "छिपा हुआ जाल"

लेखकों ने पाया कि भले ही एक आदर्श नियम मौजूद हो, फिर भी एक रोबट विनाशकारी रूप से विफल हो सकता है। क्यों?

कल्पना कीजिए कि रोबट "संख्या पहचानने" का खेल खेल रहा है।

ब्रह्मांड का एक नियम है: "यदि मैं तुम्हें लाल कार्ड दिखाता हूँ, तो उत्तर 0 है। यदि मैं तुम्हें नीला कार्ड दिखाता हूँ, तो उत्तर 1,000,000 है।"
रोबट 1,000 लाल कार्ड देखता है। वह सीख जाता है "लाल = 0"।
फिर, ब्रह्मांड रोबट को एक नीला कार्ड दिखाता है। रोबट 0 का अनुमान लगाता है।
दंड 1,000,000 है।

मानक लर्निंग में, यह ठीक है क्योंकि दंड सीमित है। लेकिन इस शोध पत्र की सेटिंग में, ब्रह्मांड एक धोखेबाज हो सकता है। यह ऐसे "नीले कार्डों" का क्रम छिपा सकता है जो कम होते जा रहे हैं (दुर्लभ घटनाएँ), लेकिन हर बार जब वे दिखाई देते हैं, तो दंड घातांकीय रूप से (exponentially) बड़ा होता जाता है।

पहली दुर्लभ घटना: दंड = 10।
दूसरी दुर्लभ घटना: दंड = 100।
100वीं दुर्लभ घटना: दंड = 1,000,000,000।

भले ही रोबट 99.9% सही हो, वे कुछ दुर्लभ, विशाल दंड औसत स्कोर (रिस्क) को अनंत बना सकते हैं। शोध पत्र पूछता है: हमें कैसे पता चलेगा कि कोई लर्निंग समस्या इन "अनंत जाल" वाले परिदृश्यों से सुरक्षित है?

समाधान: "इनफिनिट गैप ट्री" (Infinite Gap Tree)

लेखक यह निर्धारित करने के लिए कि क्या कोई लर्निंग समस्या हल करने योग्य है, एक सटीक "हाँ/नहीं" परीक्षण प्रदान करते हैं। वे एक अवधारणा पेश करते हैं जिसे "इनफिनिट नॉन-डिक्रीजिंग लिटिलस्टोन ट्री" (Infinite Non-Decreasing Littlestone Tree) कहा जाता है।

उपमा: अंतहीन भूलभुलैया
एक निर्णय वृक्ष (डिसीजन ट्री, जैसे फ्लोचार्ट) की कल्पना करें जहाँ:

हर कदम पर, ब्रह्मांड एक स्थिति प्रस्तुत करता है (एक नोड)।
ब्रह्मांड दो संभावित उत्तर (लेबल) प्रदान करता है।
जैसे-जैसे आप ट्री में गहराई में जाते हैं, इन दोनों उत्तरों के बीच की दूरी (दंड) बढ़ती जाती है।
- स्तर 1: उत्तर 1 इकाई दूर हैं।
- स्तर 10: उत्तर 1,000 इकाइयों दूर हैं।
- स्तर 1,000: उत्तर 1,000,000 इकाइयों दूर हैं।
महत्वपूर्ण रूप से, इस ट्री के माध्यम से जाने वाला प्रत्येक पथ उन नियमों के अनुसार एक वैध संभावना होना चाहिए जिन्हें रोबट सीखने की कोशिश कर रहा है।

फैसला:

यदि यह "इनफिनिट गैप ट्री" मौजूद है: तो लर्निंग समस्या असंभव है। चाहे एल्गोरिदम कितना भी स्मार्ट क्यों न हो, एक विरोधी (ब्रह्मांड) एक ऐसी स्थिति बना सकता है जहाँ रोबट को दो ऐसे उत्तरों के बीच चयन करने के लिए मजबूर किया जाए जो उस पथ पर एक दूसरे से अनंत दूरी पर हैं जिसे उसने अभी तक नहीं देखा है। रोबट अंततः इतनी महंगी गलती करेगा कि उसका औसत स्कोर अनंत हो जाएगा।
यदि यह ट्री मौजूद नहीं है: तो लर्निंग समस्या हल करने योग्य है। लेखक सिद्ध करते हैं कि यदि यह विशिष्ट "जाल" वाली संरचना मौजूद नहीं है, तो एक ऐसा लर्निंग एल्गोरिदम बनाने का तरीका है जो अंततः पूर्ण नियम सीख लेगा, और उसका रिस्क शून्य हो जाएगा।

जीतने वाला एल्गोरिदम कैसे काम करता है (द गेम स्ट्रैटेजी)

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

खेल: कल्पना कीजिए कि रोबट एक विरोधी के खिलाफ खेल खेल रहा है। विरोधी रोबट को ऐसी स्थिति में फँसाने की कोशिश करता है जहाँ उसे दो बहुत अलग उत्तरों के बीच चयन करना पड़े।
रणनीति: रोबट के पास एक "जीतने वाली रणनीति" (नियमों का एक सेट) है जो यह गारंटी देती है कि वह अंततः विरोधी को इन बड़े उछालों को करने से रोकने में सक्षम होगा।
स्थिरीकरण (Stabilization): जैसे-जैसे रोबट अधिक डेटा देखता है, उसे एहसास होता है कि विरोधी इन विशाल अंतराल को हमेशा बनाए नहीं रख सकता। रोबट की सही उत्तर के बारे में "अनिश्चितता" एक छोटे, प्रबंधनीय दायरे में सिमट जाती है।
विभाजन (Partition): रोबट दुनिया को छोटे "पड़ोस" (neighborhoods) में विभाजित करता है। प्रत्येक पड़ोस में, संभावित उत्तर एक-दूसरे के करीब (सीमित) होते हैं।
स्थानीय लर्निंग (Local Learning): एक बार जब समस्या को इन छोटे, सुरक्षित पड़ोसों में तोड़ दिया जाता है, तो रोबट सही उत्तर पाने के लिए मानक, सिद्ध लर्निंग तकनीकों का उपयोग कर सकता है।

निष्कर्षों का सारांश

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

संक्षेप में, यह शोध पत्र एक स्पष्ट रेखा खींचता है: यदि आपकी लर्निंग समस्या में "इनफिनिट गैप ट्री" शामिल है, तो आप विफल हो जाएंगे। यदि यह नहीं है, तो आप हमेशा सफल हो सकते हैं।

तकनीकी सारांश: सामान्य मीट्रिक लॉस के लिए रियलाइज़ेबल बेयज़-कंसिस्टेंसी (Realizable Bayes-Consistency)

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

यह शोध पत्र सामान्य मीट्रिक लॉस (general metric losses) के लिए रियलाइज़ेबल सेटिंग में स्ट्रॉन्ग यूनिवर्सल बेयज़-कंसिस्टेंसी (strong universal Bayes-consistency) की समस्या को संबोधित करता है। इस सेटिंग में शामिल हैं:

एक इंस्टेंस स्पेस $(X, \rho)$ और एक लेबल स्पेस $(Y, \ell)$ , जहाँ $\ell$ एक मीट्रिक है जो अनबाउंडेड (unbounded) हो सकता है।
एक हाइपोथीसिस क्लास $\mathcal{H} \subseteq Y^X$ ।
एक डेटा-जनरेटिंग डिस्ट्रीब्यूशन $\bar{\mu}$ जो $X \times Y$ पर रियलाइज़ेबल है, जिसका अर्थ है कि इष्टतम रिस्क शून्य है ( $\inf_{h \in \mathcal{H}} R_{\bar{\mu}}(h) = 0$ )।

लक्ष्य यह निर्धारित करना है कि $\mathcal{H}$ पर क्या आवश्यक और पर्याप्त शर्तें हैं जिससे एक डिस्ट्रीब्यूशन-फ्री लर्निंग रूल (distribution-free learning rule) का अस्तित्व हो, जिसका रिस्क प्रत्येक रियलाइज़ेबल डिस्ट्रीब्यूशन $\bar{\mu}$ के लिए लगभग निश्चित रूप से (almost surely) शून्य की ओर अग्रसर हो।

लेखक बाउंडेड (bounded) और अनबाउंडेड (unbounded) लॉस के बीच एक महत्वपूर्ण अंतर पर प्रकाश डालते हैं। बाउंडेड सेटिंग्स में, त्रुटि की संभावना को नियंत्रित करना रिस्क को नियंत्रित करने के समतुल्य होता है। अनबाउंडेड मीट्रिक सेटिंग्स में, एक लर्नर उन घटनाओं पर गलतियाँ कर सकता है जिनकी प्रायिकता लुप्त होती जा रही है, फिर भी इन त्रुटियों का परिमाण इतनी तेज़ी से बढ़ सकता है कि अपेक्षित रिस्क अनंत हो जाता है या शून्य की ओर अभिसरित (converge) होने में विफल रहता है। यह शोध पत्र यह खोजने का प्रयास करता है कि ऐसी "विनाशकारी दुर्लभ-घटना विफलताओं" (catastrophic rare-event failures) से कैसे बचा जा सकता है।

2. कार्यप्रणाली और सैद्धांतिक ढांचा (Methodology and Theoretical Framework)

यह शोध पत्र इनफिनिट गेम थ्योरी (infinite game theory) और ट्री ऑब्स्ट्रक्शंस (tree obstructions) में निहित एक कॉम्बिनेटोरियल दृष्टिकोण का उपयोग करता है, जो पहले 0-1 क्लासिफिकेशन और बाउंडेड रिग्रेशन के लिए विकसित ढांचों का विस्तार करता है।

मुख्य परिभाषाएँ:

इनफिनिट नॉन-डिक्रीजिंग $(\gamma_k)$ -लिट्लस्टोन ट्री (Infinite Non-Decreasing $(\gamma_k)$ -Littlestone Tree): एक पूर्ण बाइनरी ट्री जहाँ डेप्थ $k$ पर इंटरनल नोड्स $x_{k,i}$ हैं, और आउटगोइंग एडजेस $y_{k,i,1}, y_{k,i,2} \in Y$ के साथ लेबल किए गए हैं ताकि मीट्रिक डिस्टेंस $\ell(y_{k,i,1}, y_{k,i,2}) \ge \gamma_k$ हो। अनुक्रम $(\gamma_k)$ नॉन-डिक्रीजिंग है और $\gamma_k \to \infty$ की ओर अग्रसर है। ट्री "रियलाइज़ेबल" है यदि प्रत्येक परिमित रूट-टू-लीफ पाथ $\mathcal{H}$ के किसी हाइपोथीसिस के साथ सुसंगत (consistent) है।
रियलाइज़ेबिलिटी धारणा (Realizability Assumption): लेखक एक "कॉम्पैक्ट-पैरामीट्रिज़ेशन" स्थिति (लेम्मा 4.3) मानते हैं: $\mathcal{H}$ एक कॉम्पैक्ट स्पेस $\Theta$ द्वारा पैरामीट्राइज़ किया गया है जिसमें एक निरंतर इवैल्यूएशन मैप है। इस हल्के अनुमान के तहत, परिमित-प्रिफिक्स रियलाइज़ेबिलिटी का अर्थ है कि प्रत्येक अनंत पाथ एक ही हाइपोथीसिस द्वारा रियलाइज़ किया जाता है।

प्रूफ आर्किटेक्चर (Proof Architecture):
मुख्य परिणाम को एक लोअर बाउंड (आवश्यकता) और एक अपर बाउंड (पर्याप्तता) के माध्यम से स्थापित किया गया है।

लोअर बाउंड (असंभवता): यदि $\mathcal{H}$ में एक अनंत नॉन-डिक्रीजिंग $(\gamma_k)$ -लिट्लस्टोन ट्री शामिल है, तो लेखक एक ऐसा रियलाइज़ेबल डिस्ट्रीब्यूशन निर्मित करते हैं जहाँ विरोधी (adversary) तेजी से घटते प्रायिकता द्रव्यमान (probability masses) के पीछे तेजी से अलग होते लेबल विकल्पों को छिपाता है। एक बोरेल-कैन्टेली (Borel-Cantelli) तर्क का उपयोग करते हुए, वे दिखाते हैं कि किसी भी लर्निंग एल्गोरिदम के लिए, अपेक्षित रिस्क प्रत्येक सैंपल साइज $n$ के लिए अनंत है। लर्नर को अनदेखे नोड्स पर $\gamma_k$ से अलग लेबल के बीच अनुमान लगाने के लिए मजबूर किया जाता है, जिससे रिस्क डाइवर्जेंट हो जाता है।
अपर बाउंड (रचनात्मक एल्गोरिदम): यदि ऐसा ट्री ऑब्स्ट्रक्शन मौजूद नहीं है, तो लेखक एक डिस्ट्रीब्यूशन-फ्री लर्निंग रूल का निर्माण करते हैं। प्रमाण चार चरणों में आगे बढ़ता है:
1. गेम-थ्योरेटिक एनकोडिंग: ट्री ऑब्स्ट्रक्शन की अनुपस्थिति का अर्थ है कि लर्नर के पास एक विशिष्ट इनफिनिट गेल-स्टुअर्ट गेम (Gale-Stewart game) के विरुद्ध एक विरोधी के खिलाफ जीतने की रणनीति है।
2. स्टेबिलाइज़ेशन (Stabilization): एक i.i.d. सैंपल पर इस गेम को सिम्युलेट करके, प्रक्रिया कुछ राउंड के बाद लगभग निश्चित रूप से स्थिर हो जाती है। यह प्रत्येक $x$ के लिए, एक सीमित व्यास (diameter) वाले "एडमिसेबल" लेबल का एक सेट $H_K(x)$ उत्पन्न करता है।
3. पार्टिशनिंग (Partitioning): $Y$ के एक डेंस सबसेट के आधार पर इंस्टेंस स्पेस $X$ को गणनीय सेल्स (countably many cells) में विभाजित किया जाता है। प्रत्येक सेल के भीतर, एडमिसेबल लेबल सेट का व्यास सीमित होता है।
4. रिडक्शन (Reduction): समस्या को बाउंडेड लॉस वाले गणनीय उप-समस्याओं में बदल दिया जाता है। लेखक मौजूदा मेडनेट (MedNet) एल्गोरिदम (त्सिर कोहेन और कोंटोरकोविच, 2022) को प्रत्येक सेल पर लागू करते हैं, जो बाउंडेड मीट्रिक लॉस के लिए स्ट्रॉन्गली यूनिवर्सली बेयज़-कंसिस्टेंट है, और परिणामों को एकत्रित करते हैं।

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

शार्प कैरेक्टराइजेशन (Sharp Characterization): यह शोध पत्र सामान्य (संभवतः अनबाउंडेड) मीट्रिक लॉस के तहत रियलाइज़ेबल स्ट्रॉन्ग यूनिवर्सल बेयज़-कंसिस्टेंसी के लिए एक आवश्यक और पर्याप्त स्थिति प्रदान करता है। शर्त हाइपोथीसिस क्लास में अनंत नॉन-डिक्रीजिंग $(\gamma_k)$ -लिट्लस्टोन ट्री का अस्तित्व न होना है।
एक ओपन प्रॉब्लम का समाधान: यह कार्य त्सिर कोहेन और कोंटोरकोविच (2022) द्वारा प्रस्तुत एक ओपन प्रॉब्लम के रियलाइज़ेबल केस को हल करता है। यह प्रदर्शित करता है कि प्राकृतिक फाइनाइटनेस-टाइप स्थितियाँ, जैसे कि बेयज़ रिस्क की परिमितता ( $R^* < \infty$ ) या लेबल स्पेस पर "बाउंडेड-इन-एक्सपेक्टेशन" (BIE) स्थिति, अनबाउंडेड सेटिंग में कंसिस्टेंसी सुनिश्चित करने के लिए अपर्याप्त हैं।
रचनात्मक लर्निंग रूल (Constructive Learning Rule): ट्री ऑब्स्ट्रक्शन की अनुपस्थिति में, यह शोध पत्र एक स्पष्ट लर्निंग रूल प्रस्तुत करता है (मेडनेट एल्गोरिदम और गेम-थ्योरेटिक स्टेबिलाइज़ेशन पर आधारित) जो स्ट्रॉन्ग यूनिवर्सल बेयज़-कंसिस्टेंसी प्राप्त करता है।
काउंटर-एग्जांपल निर्माण: लेखक एक ठोस काउंटर-एग्जांपल (सेक्शन 3) प्रदान करते हैं जो दिखाता है कि भले ही $R^* < \infty$ हो, यदि हाइपोथीसिस क्लास में विशिष्ट अनबाउंडेड-गैप ट्री संरचना है, तो कोई डिस्ट्रीब्यूशन-फ्री कंसिस्टेंट लर्नर मौजूद नहीं हो सकता है।

4. परिणाम और महत्व (Results and Significance)

केंद्रीय प्रमेय (थ्योरम 4.5) बताता है कि पॉलिश स्पेस $(X, \rho)$ और $(Y, \ell)$ और एक हाइपोथीसिस क्लास $\mathcal{H}$ के लिए जो हल्के मेजरेबिलिटी और कॉम्पैक्टनेस की शर्तों को पूरा करती है, निम्नलिखित समकक्ष हैं:

एक डिस्ट्रीब्यूशन-फ्री लर्निंग रूल का अस्तित्व है जो प्रत्येक रियलाइज़ेबल डिस्ट्रीब्यूशन के लिए स्ट्रॉन्गली यूनिवर्सली बेयज़-कंसिस्टेंट है।
$\mathcal{H}$ में एक अनंत नॉन-डिक्रीजिंग $(\gamma_k)$ -लिट्लस्टोन ट्री ( $\gamma_k \to \infty$ के साथ) शामिल नहीं है।

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

लेखक उल्लेख करते हैं कि इस कैरेक्टराइजेशन को एग्नोस्टिक सेटिंग (जहाँ डिस्ट्रीब्यूशन अनिवार्य रूप से रियलाइज़ेबल नहीं है) तक विस्तारित करना एक खुला विषय बना हुआ है, जिसके लिए उनके परिशिष्ट (Appendix) में चर्चा की गई बाधाओं का हवाला दिया गया है।