📊 statistics

Linear Regression with Unknown Truncation Beyond Gaussian Features

यह शोध पत्र सब-गॉसियन (sub-Gaussian) फीचर धारणाओं के तहत अज्ञात सर्वाइवल सेट वाले ट्रंकेटेड लीनियर रिग्रेशन के लिए पहला बहुपद-समय (polynomial-time) एल्गोरिदम प्रस्तुत करता है, जो केवल धनात्मक उदाहरणों से अंतराल के संघों (unions of intervals) को सीखने के लिए एक नवीन सबरूटीन पेश करके पिछले प्रतिबंधों को दूर करता है, जिनके लिए गॉसियन फीचर्स और घातीय रनटाइम की आवश्यकता थी।

मूल लेखक: Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis, Constantine Caramanis

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

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

CC BY 4.0

मूल लेखक: Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis, Constantine Caramanis

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

कल्पना कीजिए कि आप एक रोबोट को घर के आकार, स्थान और उम्र के आधार पर उसकी कीमत का अनुमान लगाना सिखाने की कोशिश कर रहे हैं। यह एक क्लासिक "लीनियर रिग्रेशन" (linear regression) समस्या है। आमतौर पर, आप रोबोट को हजारों उदाहरण देंगे: "यह 2,000 वर्ग फुट का घर $500k में बिका," "यह 1,000 वर्ग फुट का घर$ 300k में बिका," इत्यादि।

लेकिन अब, एक मोड़ है: रोबोट को केवल वे घर देखने की अनुमति है जो $400k से कम में बिके हैं।

कोई भी घर जो $400k या उससे अधिक में बिका? रोबोट उसे कभी नहीं देख पाएगा। वे डेटा पॉइंट्स "ट्रंकेटेड" (truncated) या कटे हुए हैं। यदि आप रोबोट को केवल वे सस्ते घर खिलाते हैं जिन्हें वह देख सकता है, तो वह एक पूरी तरह से गलत नियम सीख जाएगा। उसे लग सकता है, "ओह, बड़े घर वास्तव में सस्ते होते हैं!" क्योंकि उसने बड़े, महंगे घरों को कभी देखा ही नहीं। सांख्यिकी (statistics) में, इसे ट्रंकेटेड लीनियर रिग्रेशन (Truncated Linear Regression) कहा जाता है।

समस्या: "सर्वाइवल सेट" (Survival Set) का रहस्य

वास्तविक दुनिया में, यह "कट-ऑफ" हमेशा $400k से कम जैसा एक सरल नियम नहीं होता है।

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

शोधकर्ता इस अदृश्य नियम को "सर्वाइवल सेट" ( $S^\star$ ) कहते हैं। यह उन परिणामों की विशिष्ट सीमा है जो रिकॉर्ड किए जाते हैं।

पेंच: कई वास्तविक परिदृश्यों में, हमें सर्वाइवल सेट का पता नहीं होता है। हम बस इतना जानते हैं कि हमारे पास डेटा का एक ढेर है, और हम जानते हैं कि उस ढेर में "चरम" या "अदृश्य" हिस्से गायब हैं। पुराने तरीके इसे हल कर सकते थे यदि उन्हें नियम पता हो (जैसे, "यह हमेशा $400k से कम है"), लेकिन यदि नियम एक जटिल, अज्ञात आकार है, तो पुराने एल्गोरिदम या तो पूरी तरह से विफल हो जाते थे या उन्हें गणना करने में इतना समय लगता था कि वे बेकार हो जाते थे (एक्सपोनेंशियल टाइम)।

समाधान: एक दो-चरणीय जासूसी कहानी

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

यहाँ बताया गया है कि उनका एल्गोरिदम कैसे काम करता है, एक सरल उपमा का उपयोग करते हुए:

चरण 1: अदृश्य बाड़ का मानचित्रण करना (सर्वाइवल सेट को सीखना)

कल्पना कीजिए कि आप अंधेरे खेत में एक बाड़ के आकार का पता लगाने की कोशिश कर रहे हैं, लेकिन आप केवल उन फूलों को देख सकते हैं जो बाड़ के अंदर उग रहे हैं। आप बाड़ के बाहर के फूलों को नहीं देख सकते।

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

चरण 2: रोबोट के मस्तिष्क को ठीक करना (सच्चा नियम सीखना)

अब कि एल्गोरिदम के पास एक अच्छा अनुमान है कि बाड़ कहाँ है, यह रोबोट के मस्तिष्क को ठीक कर सकता है।

समस्या: रोबोट का मस्तिष्क (गणितीय मॉडल) पक्षपाती है क्योंकि उसने केवल "सस्ते" घर देखे हैं।
समाधान: एल्गोरिदम प्रोजेक्टेड स्टोकेस्टिक ग्रेडिएंट डिसेंट (PSGD) नामक तकनीक का उपयोग करता है। कल्पना कीजिए कि रोबोट एक हाइकर (पर्वतारोही) है जो घाटी के सबसे निचले बिंदु (सच्चे उत्तर) को खोजने की कोशिश कर रहा है।
- सामान्य रूप से, हाइकर भ्रमित हो जाता है क्योंकि गायब डेटा के कारण भूभाग विकृत हो जाता है।
- यह नया एल्गोरिदम हाइकर को एक "बायस-करेक्टेड" (bias-corrected) मानचित्र देता है। यह उसे बताता है, "हे, तुम्हें लगता है कि तुम ढलान की ओर जा रहे हो, लेकिन वास्तव में, तुम ऊपर की ओर जा रहे हो क्योंकि तुम गायब डेटा को अनदेखा कर रहे हो।"
- महत्वपूर्ण रूप से, वे हाइकर को एक सुरक्षित "प्रोजेक्शन सेट" (सुरक्षित क्षेत्र) के भीतर रहने के लिए मजबूर करते हैं ताकि वह असंभव क्षेत्र में न भटक जाए।

यह एक बड़ी बात क्यों है

यह तेज़ है: इस समस्या के लिए पिछले तरीके एक भूलभुलैया को एक-एक करके हर रास्ते की जांच करके हल करने जैसे थे (एक्सपोनेंशियल टाइम)। यह नया तरीका एक GPS की तरह है जो पॉलीनोमियल टाइम (तेज़ और स्केलेबल) में रास्ता खोज लेता है।
यह लचीला है: पुराने तरीकों के लिए आवश्यक था कि डेटा पूरी तरह से "गौसियन" (एक आदर्श बेल कर्व) हो। वास्तविक दुनिया का डेटा अव्यवस्थित होता है। यह नया तरीका तब तक काम करता है जब तक कि डेटा बहुत अधिक अजीब न हो (एक स्थिति जिसे "सब-गौसियन" कहा जाता है), जो लगभग सभी वास्तविक दुनिया के परिदृश्यों को कवर करती है।
यह पहला है: यह पहली बार है जब किसी ने यह सिद्ध किया है कि आप कुशलतापूर्वक नियम और डेटा पैटर्न को सीख सकते हैं जब "कट-ऑफ" नियम पूरी तरह से अज्ञात और जटिल हो।

सारांश

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

तकनीकी सारांश: अज्ञात ट्रंकेशन के साथ लीनियर रिग्रेशन (Linear Regression with Unknown Truncation)

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

यह शोध पत्र ट्रंकेटेड लीनियर रिग्रेशन (truncated linear regression) की समस्या को संबोधित करता है जहाँ ट्रंकेशन (या "सर्वाइवल") सेट अज्ञात होता है। इस सेटिंग में, एक शिक्षार्थी (learner) ऐसे नमूने $(x, y)$ देखता है जो निम्नानुसार उत्पन्न होते हैं:

एक फीचर वेक्टर $x \in \mathbb{R}^d$ एक अज्ञात वितरण $\mathcal{D}$ से लिया जाता है।
एक लेबल $y$ की गणना की जाती है $y = x^\top w^\star + \xi$ , जहाँ $w^\star$ एक अज्ञात रिग्रेसर है और $\xi \sim \mathcal{N}(0, 1)$ गॉसियन नॉइज़ (Gaussian noise) है।
नमूना तभी देखा जाता है यदि और केवल यदि $y \in S^\star$ हो, जहाँ $S^\star \subseteq \mathbb{R}$ एक अज्ञात "सर्वाइवल सेट" है। अन्यथा, नमूने को हटा दिया जाता है।

लक्ष्य $w^\star$ का $\varepsilon$ -सटीकता तक अनुमान लगाना है। मुख्य चुनौती यह है कि चयन पूर्वाग्रह (selection bias) के कारण मानक अनुमानक (जैसे Ordinary Least Squares) विफल हो जाते हैं, और इस समस्या के लिए पूर्ववर्ती कुशल एल्गोरिदम के लिए या तो $S^\star$ का ज्ञान आवश्यक था या फीचर वितरण पर कड़े अनुमान (विशेष रूप से, कि $\mathcal{D}$ गॉसियन है) की आवश्यकता थी।

लेखक उस व्यावहारिक रूप से प्रासंगिक मामले पर ध्यान केंद्रित करते हैं जहाँ $S^\star$ अज्ञात है और अधिकतम $k$ अंतरालों (intervals) का एक संघ (union) है। वे यह लक्ष्य प्राप्त करना चाहते हैं जहाँ फीचर वितरण $\mathcal{D}$ के लिए धारणा (assumption) कमजोर है (अर्थात, $\mathcal{D}$ स्ट्रिक्टली गॉसियन होने के बजाय सब-गॉसियन (sub-Gaussian) है)।

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

प्रस्तावित एल्गोरिदम (एल्गोरिदम 1) दो अलग-अलग चरणों में कार्य करता है:

चरण I: ट्रंकेशन सेट $S^\star$ को सीखना

चूंकि $S^\star$ अज्ञात है, इसलिए एल्गोरिदम पहले एक सन्निकटन (approximation) $\hat{S} \approx S^\star$ सीखता है।

पॉजिटिव-ओनली लर्निंग (Positive-Only Learning): $S^\star$ को सीखने की समस्या को केवल पॉजिटिव उदाहरणों (ऐसे नमूने जहाँ $y \in S^\star$ ) से एक अवधारणा (set $S^\star$ ) सीखने के रूप में फ्रेम किया गया है, जिसमें नेगेटिव उदाहरणों तक पहुँच नहीं है।
स्मूथनेस धारणा (Smoothness Assumption): इस जानकारी-सैद्धांतिक रूप से व्यवहार्य बनाने के लिए, लेखक एक "स्मूथ्ड" लर्निंग फ्रेमवर्क का उपयोग करते हैं। वे एक सहायक वितरण $\mathcal{D}$ का निर्माण करते हैं जो $y$ के वास्तविक अनट्रंकेटेड मार्जिनल वितरण (जिसे $\mathcal{D}^\star_+$ कहा जाता है) के संबंध में "स्मूथ" है।
मुख्य लेम्मा (स्मूथनेस): लेखक सिद्ध करते हैं कि यदि फीचर वितरण $\mathcal{D}$ सब-गॉसियन है, तो किसी भी पैरामीटर वेक्टर $w$ के लिए जो $w^\star$ के करीब है, $w$ द्वारा उत्पन्न $y$ का वितरण (जिसे $\mathcal{D}_y(w)$ कहा जाता है) वास्तविक $\mathcal{D}_y(w^\star)$ के संबंध में स्मूथ है। यह आवश्यक सहायक वितरण के निर्माण की अनुमति देता है जिसका उपयोग एक "वॉर्म स्टार्ट" $b_w$ ( $w^\star$ का एक प्रारंभिक अनुमान) के साथ किया जाता है।
एल्गोरिदम: वे $k$ अंतरालों के संघ को सीखने के लिए एक ग्रीडी प्रक्रिया (एल्गोरिदम 3) का उपयोग करते हैं। इसमें पॉजिटिव नमूनों को सॉर्ट करना, उनके बीच के अंतरालों की पहचान करना और उन अंतरालों को हटाना शामिल है जिनमें सहायक वितरण से सबसे अधिक नमूने आते हैं। यह एक-आयामी सेटों के लिए बहुपद समय (polynomial time) में चलता है।

चरण II: प्रोजेक्टेड स्टोकेस्टिक ग्रेडिएंट डिसेंट (PSGD) के माध्यम से पैरामीटर अनुमान

एक बार $\hat{S}$ का सन्निकटन प्राप्त हो जाने के बाद, एल्गोरिदम $w^\star$ का अनुमान लगाता है।

परटर्बड ऑब्जेक्टिव (Perturbed Objective): चूंकि $\hat{S} \neq S^\star$ , इसलिए मानक नेगेटिव लॉग-लाइक्लीहुड (NLL) सामान्य अर्थ में परिभाषित या उत्तल (convex) नहीं है। लेखक एक परटर्बड NLL ऑब्जेक्टिव, $\mathcal{L}_{\hat{S}}(w)$ , को कम करते हैं, जिसे डेटा जनरेशन के लिए अनुमानित सेट और अनुमानित सेट के बीच के प्रतिच्छेदन (intersection) का उपयोग करके परिभाषित किया गया है।
प्रोजेक्शन सेट: अभिसरण (convergence) सुनिश्चित करने के लिए, अनुकूलन को एक प्रोजेक्शन सेट $\mathcal{P}$ $P$ (वॉर्म स्टार्ट के आसपास एक स्थिर त्रिज्या वाला बॉल) तक सीमित किया गया है।
- लेखक सिद्ध करते हैं कि $w^\star$ , उच्च प्रायिकता के साथ $\mathcal{P}$ के भीतर स्थित है।
- वे स्थापित करते हैं कि यदि सेट अनुमान त्रुटि पर्याप्त रूप से छोटी है, तो $\mathcal{L}_{\hat{S}}$ , $\mathcal{P}$ के भीतर स्ट्रॉन्गली कॉनवेक्स (strongly convex) है।
बायस्ड ग्रेडिएंट सैंपलिंग (Biased Gradient Sampling): एक महत्वपूर्ण तकनीकी बाधा $\mathcal{L}_{\hat{S}}$ के लिए ग्रेडिएंट्स को सैंपल करना है। सटीक सैंपलिंग अव्यवहार्य (intractable) है। लेखक एक अनुमानित ग्रेडिएंट सैंपलर (approximate gradient sampler) डिजाइन करते हैं जो बायस्ड ग्रेडिएंट्स उत्पन्न करता है। वे सिद्ध करते हैं कि बायस (bias) सीमित है और इसे सेट अनुमान त्रुटि $\varepsilon$ को पर्याप्त रूप से छोटा बनाकर नियंत्रित किया जा सकता है।
अभिसरण (Convergence): वे इन बायस्ड ग्रेडिएंट्स के साथ PSGD का विश्लेषण करते हैं, यह दिखाते हुए कि एल्गोरिदम $\mathcal{L}_{\hat{S}}$ के मिनिमाइज़र के करीब एक बिंदु तक अभिसरित होता है, जो बदले में $w^\star$ के करीब होता है।

3. मुख्य योगदान

अज्ञात ट्रंकेशन के लिए पहला बहुपद-समय एल्गोरिदम: यह शोध पत्र पहला ऐसा एल्गोरिदम प्रस्तुत करता है जो $w^\star$ को $\text{poly}(d, k, 1/\varepsilon)$ समय में सीखता है जब सर्वाइवल सेट $S^\star$ अज्ञात हो और $k$ अंतरालों का संघ हो।
वितरण संबंधी धारणाओं का सरलीकरण: पूर्ववर्ती कार्यों (जैसे, Lee, Mehrotra, and Zampetakis [LMZ24]) के विपरीत, जिन्हें गॉसियन फीचर्स की आवश्यकता थी, यह एल्गोरिदम केवल सब-गॉसियन (sub-Gaussian) फीचर्स की आवश्यकता रखता है। यह वास्तविक दुनिया के डेटा के लिए इसकी प्रयोज्यता को काफी व्यापक बनाता है जहाँ गॉसियनिटी अक्सर एक अवास्तविक धारणा होती है।
कुशल पॉजिटिव-ओनली लर्निंग: लेखक केवल पॉजिटिव उदाहरणों से अंतरालों के संघ को PAC लर्निंग करने के लिए एक कुशल एल्गोरिदम प्रदान करते हैं, जो एक स्मूथनेस स्थिति के तहत काम करता है। यह सब-रूटीन लर्निंग थ्योरी समुदाय के लिए स्वतंत्र रुचि का विषय है।
बायस्ड ग्रेडिएंट्स को संभालना: यह कार्य ट्रंकेटेड रिग्रेशन के संदर्भ में बायस्ड ग्रेडिएंट एस्टिमेटर्स के साथ PSGD के लिए एक नवीन विश्लेषण पेश करता है, यह प्रदर्शित करते हुए कि अभिसरण संभव है भले ही सटीक ग्रेडिएंट सैंपलिंग असंभव हो।

4. परिणाम

थ्योरम 3.1 (मुख्य परिणाम): धारणा 1 (सर्वाइवल प्रोबेबिलिटी), 2 (सब-गॉसियनिटी), और 3 (आइडेंटिफिएबिलिटी) के तहत, एक ऐसा एल्गोरिदम मौजूद है जो $n = \text{poly}(d, k, 1/\varepsilon)$ नमूनों के साथ, एक अनुमान $\hat{w}$ आउटपुट करता है ताकि $1-\delta$ की प्रायिकता के साथ $\|\hat{w} - w^\star\|_2 \leq \varepsilon$ हो।
जटिलता (Complexity): सैंपल कॉम्प्लेक्सिटी और रनिंग टाइम दोनों $d$ , $k$ और $1/\varepsilon$ के बहुपद (polynomial) में स्केल करते हैं।
तुलना: गॉसियन फीचर्स के विशेष मामले में, लेखक [LMZ24] की रनिंग टाइम को $d^{\text{poly}(k/\varepsilon)}$ (जो $d$ में घातीय/exponential है) से सुधारकर $\text{poly}(d, k, 1/\varepsilon)$ कर देते हैं।
सिमुलेशन: सिंथेटिक डेटा (10-डायमेंशनल मिक्सचर ऑफ गॉसियन्स, 5 इंटरवल्स) पर प्रयोगों से पता चलता है कि प्रस्तावित एल्गोरिदम एक आदर्श एल्गोरिदम (जो $S^\star$ को पूर्व-निर्धारित रूप से जानता है) के समान दर से वास्तविक $w^\star$ की ओर अभिसरित होता है, और गलत ट्रंकेशन सेट्स वाले OLS और PSGD से काफी बेहतर प्रदर्शन करता है।

5. महत्व और दावे

यह शोध पत्र ट्रंकेटेड रिग्रेशन में एक लंबे समय से चले आ रहे खुले प्रश्न को हल करने का दावा करता है: जब ट्रंकेशन सेट अज्ञात हो, तो बिना प्रतिबंधात्मक गॉसियन फीचर्स की धारणा के कम्प्यूटेशनल दक्षता प्राप्त करना।

व्यावहारिक प्रासंगिकता: लेखक इस बात पर जोर देते हैं कि वास्तविक दुनिया के ट्रंकेशन सेट्स (जैसे खगोल विज्ञान या अर्थशास्त्र में) अक्सर अंतरालों का जटिल संघ होते हैं और शायद ही कभी स्पष्ट रूप से ज्ञात होते हैं। इसके अलावा, इन डोमेन में फीचर डिस्ट्रीब्यूशन शायद ही कभी स्ट्रिक्टली गॉसियन होते हैं।
सैद्धांतिक प्रगति: गॉसियन फीचर्स से आगे बढ़कर सब-गॉसियन फीचर्स तक पहुँचकर, यह कार्य सैद्धांतिक सुलभता और व्यावहारिक डेटा विशेषताओं के बीच के अंतर को पाटता है।
विनम्रता (Modesty): लेखक स्वीकार करते हैं कि उनका एल्गोरिदम इस धारणा पर निर्भर करता है कि $S^\star$ सीमित संख्या में अंतरालों ( $k$ ) का एक संघ है। वे नोट करते हैं कि यदि $S^\star$ ज्ञात है, तो $d$ पर घातीय निर्भरता से पूरी तरह से बचा जा सकता है, लेकिन अज्ञात मामले में $d$ पर निर्भरता (विशेष रूप से सेट लर्निंग के लिए सैंपल कॉम्प्लेक्सिटी के घातांक में) आवश्यक है, हालांकि रनटाइम बहुपद रहता है। वे यह भी उल्लेख करते हैं कि उनका दृष्टिकोण $y$ पर ट्रंकेशन के लिए विशिष्ट है, जो पिछले कार्यों से भिन्न है जो $x$ और $y$ दोनों पर उच्च-आयामी ट्रंकेशन को संभालते हैं लेकिन गॉसियनिटी की आवश्यकता रखते हैं।

यह कार्य कोवेरियेट्स (covariates) के बारे में पैरामीट्रिक धारणाओं पर निर्भर किए बिना उच्च-आयामी रिग्रेशन में व्यवस्थित चयन पूर्वाग्रहों (systematic selection biases) को संभालने की दिशा में एक मौलिक कदम के रूप में प्रस्तुत किया गया है।