📊 statistics

Coordinate Descent Algorithm for Least Absolute Deviations Regression

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

मूल लेखक: Zehaan Naik, Debasis Kundu

प्रकाशित 2026-03-23

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

CC BY 4.0

मूल लेखक: Zehaan Naik, Debasis Kundu

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

कल्पना कीजिए कि आप भविष्य की भविष्यवाणी करने के लिए कागज पर बिखरे हुए बिंदुओं (dots) के बीच से एक सीधी रेखा खींचने की कोशिश कर रहे हैं। सांख्यिकीविद (statisticians) इसे लीनियर रिग्रेशन (Linear Regression) कहते हैं।

आमतौर पर, इस रेखा को खींचने का सबसे लोकप्रिय तरीका ऑर्डिनरी लीस्ट स्क्वायर्स (OLS) कहलाता है। OLS को एक ऐसे "परफेक्शनिस्ट" के रूप में सोचें जिसे तब बहुत गुस्सा आता है जब कोई एक बिंदु भी रेखा से दूर होता है। क्योंकि OLS हर गलती (error) के वर्ग (square) को देखता है, इसलिए एक अकेला अजीबोगरीब आउटलायर (वह बिंदु जो चार्ट से बहुत दूर हो) पूरी रेखा को अपनी ओर खींच सकता है, जिससे बाकी सबके लिए भविष्यवाणी खराब हो जाती है।

इसे ठीक करने के लिए, सांख्यिकीविदों ने लीस्ट एब्सोल्यूट डेविएशन (LAD) का आविष्कार किया। गलतियों का वर्ग करने के बजाय, LAD एक "व्यावहारिक वार्ताकार" (pragmatic negotiator) की तरह है। यह बस सीधी-रेखा की दूरियों को जोड़ देता है। यदि एक बिंदु बहुत दूर है, तो यह चिल्लाता नहीं है; यह बस कुल योग में थोड़ा सा योगदान देता है। यह इस रेखा को बहुत अधिक रोबस्ट (robust) बनाता है—यह अजीबोगरीब आउटलेर्स को अनदेखा करता है और "वास्तविक" मध्य (median) को खोज लेता है।

समस्या: पुराना तरीका बहुत धीमा है

दशकों से, इस "व्यावहारिक" LAD रेखा को खोजना एक विशाल जिग्सॉ पहेली (jigsaw puzzle) को हल करने जैसा था, जिसमें आपको हर बार एक टुकड़े को हिलाने पर पूरी पहेली को फिर से खोलकर नए सिरे से बनाना पड़ता था।

पुराना तरीका (लिनियर प्रोग्रामिंग): यह पूरी तरह से काम करता था, लेकिन गणनात्मक रूप से बहुत भारी था। यह जटिल "मैट्रिक्स इनवर्जन" (गणितीय कलाबाजी) पर निर्भर था जो तब असंभव हो जाता था जब आपके पास हजारों चर (variables/predictors) और पर्याप्त डेटा पॉइंट्स नहीं होते थे। यह ऐसा था जैसे किसी फॉर्मूला 1 कार को कीचड़ भरे दलदल से चलाने की कोशिश करना; वह बस फंस जाती थी।

समाधान: "कोऑर्डिनेट डिसेंट" एल्गोरिदम

इस शोध पत्र के लेखक, ज़ेहान नाइक और देबासिस कुंडू ने उस रेखा को खोजने का एक नया, बहुत स्मार्ट तरीका प्रस्तावित किया है। वे इसे कोऑर्डिनेट डिसेंट (Coordinate Descent) कहते हैं।

यहाँ इसकी उपमा (analogy) दी गई है:
कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी (सबसे अच्छी संभव रेखा) में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं।

पुराना तरीका: आप एक साथ पूरी घाटी के ढलान (slope) की गणना करने की कोशिश करते हैं ताकि तय किया जा सके कि कहाँ चलना है। यदि घाटी बहुत जटिल (high-dimensional) है, तो आपका कैलकुलेटर टूट जाता है।
नया तरीका (कोऑर्डिनेट डिसेंट): आप एक बहुत ही विशिष्ट, सरल तरीके से चलने का निर्णय लेते हैं। आप केवल उत्तर-दक्षिण (North-South) देखते हैं। आप उत्तर या दक्षिण की ओर तब तक चलते हैं जब तक कि आप उस विशिष्ट दिशा में सबसे निचले बिंदु तक न पहुँच जाएँ। फिर, आप रुक जाते हैं। इसके बाद, आप पूर्व-पश्चिम (East-West) देखते हैं। आप पूर्व या पश्चिम की ओर तब तक चलते हैं जब तक कि आप उस दिशा में सबसे निचले बिंदु तक न पहुँच जाएँ। फिर, आप रुक जाते हैं। आप ज़िग-ज़ैग (उत्तर-दक्षिण, पूर्व-पश्चिम, उत्तर-दक्षिण...) करते रहते हैं जब तक कि आप और नीचे न जा सकें।

यह क्यों जीनियस है?

यह सरल है: हर बार जब आप एक कदम उठाते हैं (एक वेरिएबल अपडेट करते हैं), तो गणित अविश्वसनीय रूप से आसान हो जाता है। आपको बस संख्याओं की एक छोटी सूची का मीडियन (Median) निकालना होता है। कोई जटिल कैलकुलस नहीं, कोई मैट्रिक्स इनवर्जन नहीं।
यह "अजीब" डेटा को संभालता है: क्योंकि यह मीडियन का उपयोग करता है, यह स्वाभाविक रूप से आउटलेर्स को अनदेखा कर देता है।
यह "असंभव" क्षेत्र में काम करता है: यह शोध पत्र दिखाता है कि यह तरीका तब भी काम करता है जब आपके पास डेटा पॉइंट्स से अधिक वेरिएबल्स हों (उदाहरण के लिए, 2,000 फीचर्स का उपयोग करके घर की कीमत बताने की कोशिश करना लेकिन आपके पास केवल 1,000 घर हों)। पुराने तरीके यहाँ क्रैश हो जाते हैं; यह चलता रहता है।

गुप्त मंत्र: "इन्क्रीमेंटल अपडेट्स"

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

इसे एक टेंट को एडजस्ट करने की तरह समझें।

नाइव (Naive) दृष्टिकोण: हर बार जब आप एक पोल (खंभा) हिलाते हैं, तो आप पूरा टेंट हटा देते हैं, जमीन को फिर से मापते हैं और उसे फिर से खड़ा करते हैं। (बहुत धीमा)।
अनुकूलित (Optimized) दृष्टिकोण: आप बस उस एक पोल के लिए रस्सी को एडजस्ट करते हैं और तनाव (tension) को अपडेट करते हैं। आप पूरा टेंट दोबारा नहीं बनाते; आप बस उस हिस्से को ठीक करते हैं जिसे आपने बदला है।

इस छोटे से बदलाव ने एल्गोरिदम को, विशेष रूप से बड़े डेटासेट के लिए, बेहद तेज़ बना दिया।

उन्होंने क्या सिद्ध किया?

उन्होंने इस नए तरीके का परीक्षण किया:

नकली डेटा (Fake Data): उन्होंने बहुत अधिक शोर (noise) और आउटलेर्स वाले परिदृश्य बनाए। नए तरीके ने शोर को अनदेखा करते हुए हर बार सटीक रेखा खोजी।
वास्तविक डेटा (Real Data): उन्होंने बोस्टन हाउसिंग (घर की कीमतों की भविष्यवाणी करना) और एयर क्वालिटी (ओजोन स्तर की भविष्यवाणी करना) जैसे प्रसिद्ध डेटासेट्स का उपयोग किया।
- परिणाम: नया तरीका पुराने, धीमे और जटिल तरीकों जितना ही सटीक था।
- बोनस: हाई-डायमेंशनल परिदृश्यों में (जहाँ पुराने तरीके पूरी तरह विफल हो गए थे), नया तरीका काम करता रहा और यहाँ तक कि जब उन्होंने इसे "वार्म स्टार्ट" (रिज रिग्रेशन नामक एक सरल गणितीय ट्रिक का उपयोग करके शुरुआत देना) दिया, तो इसमें सुधार भी हुआ।

मुख्य निष्कर्ष (The Takeaway)

यह शोध पत्र हमें डेटा साइंस के लिए एक नया, हल्का और मजबूत उपकरण प्रदान करता है।

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

संक्षेप में: उन्होंने एक कठिन सांख्यिकीय समस्या को छोटे, आसान चरणों में तोड़कर इसे हल करने का एक तरीका खोजा है, जिससे रोबस्ट रिग्रेशन सबसे जटिल, बिखरे हुए और हाई-डायमेंशनल डेटा समस्याओं के लिए भी सुलभ हो गया है।

यहाँ ज़ेहान नाइक और देबासिस कुंडू के शोध पत्र "Coordinate Descent Algorithm for Least Absolute Deviations Regression" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र लीस्ट एब्सोल्यूट डेविएशन (LAD) रिग्रेशन की कम्प्यूटेशनल सीमाओं को संबोधित करता है, जो लीस्ट स्क्वायर्स (OLS) का एक मजबूत (robust) विकल्प है। LAD, स्क्वेर्ड रेसिडुअल्स के बजाय एब्सोल्यूट रेसिडुअल्स के योग को कम करता है।

चुनौती: जबकि LAD आउटलेयर्स (outliers) और हेवी-टेल्ड नॉइज़ के प्रति मजबूत है, पारंपरिक सॉल्वर लीनियर प्रोग्रामिंग (LP) फॉर्मुलेशन (जैसे सिम्प्लेक्स या इंटीरियर-पॉइंट मेथड्स) पर निर्भर करते हैं। ये विधियाँ उन उच्च-आयामी सेटिंग्स (high-dimensional settings) में अत्यधिक कम्प्यूटेशनल रूप से महंगी, संख्यात्मक रूप से अस्थिर हो जाती हैं, या पूरी तरह विफल हो जाती हैं जहाँ प्रेडिक्टर्स ( $p$ ) की संख्या अवलोकनों ( $n$ ) के बराबर या उससे अधिक होती है।
अंतराल (The Gap): स्केलेबल, मैट्रिक्स-इनवर्जन-मुक्त एल्गोरिदम की कमी है जो LAD ऑब्जेक्टिव फंक्शन की नॉन-डिफरेंशिएबल प्रकृति को कुशलतापूर्वक संभाल सके, विशेष रूप से जब $p \ge n$ हो।

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

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

A. मुख्य गणितीय अंतर्दृष्टि (Core Mathematical Insight)

LAD ऑब्जेक्टिव फंक्शन है:
$L(\beta) = \sum_{i=1}^n |y_i - x_i^T \beta|$
जब सभी गुणांकों (coefficients) को $\beta_j$ को छोड़कर स्थिर कर दिया जाता है, तो समस्या एक यूनिवेरिएट मिनिमाइजेशन में बदल जाती है:
$\beta_j = \arg\min_{t} \sum_{i=1}^n |r_i^{(j)} - x_{ij}t|$
जहाँ $r_i^{(j)}$ एक पार्शियल रेसिड्यूल (partial residual) है।

क्लोज्ड-फॉर्म समाधान: यह सब-प्रॉब्लम अनुपातों $r_i^{(j)}/x_{ij}$ (वेट्स $|x_{ij}|$ के साथ) के वेटेड मीडियन (weighted median) द्वारा एक सटीक समाधान प्रदान करता है। यदि $x_{ij}=1$ (इंटरसेप्ट) है, तो यह मानक मीडियन है।
अभिसरण (Convergence): चूंकि ऑब्जेक्टिव फंक्शन कॉनवेक्स है और प्रत्येक कोऑर्डिनेट अपडेट एक सटीक मिनिमाइजेशन है, इसलिए एल्गोरिदम एक ग्लोबल मिनिमाइज़र तक पहुँचने की गारंटी देता है।

B. एल्गोरिद्मिक अनुकूलन (Algorithmic Optimization)

नेइव (naive) कोऑर्डिनेट डिसेंट की अक्षमता को दूर करने के लिए (जिसमें बार-बार रेसिड्यूल रीकंप्यूटेशन के कारण $O(np^2)$ जटिलता होती है), लेखक एक इन्क्रीमेंटल रेसिड्यूल अपडेट (Incremental Residual Update) रणनीति पेश करते हैं:

ग्लोबल रेसिड्यूल बनाए रखें: एक एकल रेसिड्यूल वेक्टर $res = y - X\beta$ रखें।
अपडेट स्टेप्स:
- रिस्टोर (Restore): वर्तमान $\beta_j$ के योगदान को अस्थायी रूप से जोड़कर पार्शियल रेसिड्यूल प्राप्त करें ( $O(n)$ )।
- सॉल्व (Solve): वेटेड मीडियन के माध्यम से नया $\beta_j$ कंप्यूट करें ( $O(n \log n)$ )।
- अपडेट (Update): $\beta_j$ में परिवर्तन द्वारा ग्लोबल रेसिड्यूल को एडजस्ट करें ( $O(n)$ )।

जटिलता: यह प्रति-इटरेशन जटिलता को $O(np^2)$ से घटाकर $O(np \log n)$ कर देता है, जो इसे बड़े $p$ के लिए अत्यधिक स्केलेबल बनाता है।

C. इनिशियलाइजेशन रणनीतियाँ (Initialization Strategies)

यह पहचानते हुए कि CD का प्रदर्शन इनिशियलाइजेशन पर निर्भर करता है, विशेष रूप से अंडरडिटरमिन्ड (underdetermined) शासन में ( $p \ge n$ ), शोध पत्र निम्नलिखित का मूल्यांकन करता है:

रिज रिग्रेशन वार्म-स्टार्ट (Ridge Regression Warm-start): पहले एक पेनलाइज्ड लीस्ट स्क्वायर्स समस्या को हल करना। यह एक स्थिर, डिटर्मिनिस्टिक शुरुआती बिंदु प्रदान करता है जो गुणांकों को सिकोड़ता है, जिससे रैंक डेफिशिएंसी को प्रभावी ढंग से संभाला जा सकता है।
जेनेटिक एल्गोरिदम (GA): अत्यधिक नॉन-कॉन्वेक्स या जटिल लैंडस्केप के लिए एक ग्लोबल सर्च इनिशियलाइज़र के रूप में उपयोग किया जाता है, हालांकि यह कम्प्यूटेशनल रूप से भारी है।
रैंडम मल्टी-स्टार्ट (Random Multi-start): रैंडमनेस के प्रति मजबूती सुनिश्चित करने के लिए कई रैंडम सीड्स से एल्गोरिदम चलाना।

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

एल्गोरिदम डिज़ाइन: LAD के लिए एक नवीन कोऑर्डिनेट डिसेंट एल्गोरिदम जो मैट्रिक्स इनवर्जन से बचता है और वेटेड मीडियंस के माध्यम से नॉन-डिफरेंशिएबल ऑब्जेक्टिव को संभालता है।
स्केलेबिलिटी: $O(np \log n)$ जटिलता के साथ एक अनुकूलित कार्यान्वयन, जो उच्च-आयामी सेटिंग्स ( $p \ge n$ ) में LAD रिग्रेशन को सक्षम बनाता है जहाँ LP सॉल्वर विफल हो जाते हैं।
सैद्धांतिक गारंटी: LAD ऑब्जेक्टिव की कॉनवेक्सिटी और कोऑर्डिनेट अपडेट की सटीकता के आधार पर ग्लोबल कन्वर्जेंस का प्रमाण।
हाइब्रिड फ्रेमवर्क: यह प्रदर्शन करना कि रिज रिग्रेशन (स्थिरता के लिए) को LAD-CD (मजबूती के लिए) के साथ मिलाने से कंटैमिनेटेड और उच्च-आयामी डेटा में बेहतर प्रेडिक्टिव प्रदर्शन मिलता है।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने सिंथेटिक डेटा और वास्तविक दुनिया के बेंचमार्क (Boston Housing, Air Quality, Concrete Compressive Strength) पर अपने तरीके का मूल्यांकन किया।

अभिसरण और स्थिरता (Convergence & Stability):
- एल्गोरिदम 20–50 इटरेशन के भीतर मोनोटोनिक रूप से अभिसरित होता है।
- सिंथेटिक डेटा पर 1,000 पुनरावृत्तियों (replications) में, अंतिम मीन एब्सोल्यूट एरर (MAE) अत्यधिक केंद्रित था (SD $\approx 6 \times 10^{-4}$ ), जो रैंडम इनिशियलाइजेशन के बावजूद स्थिरता को सिद्ध करता है।
आउटलेयर्स के प्रति मजबूती (Robustness to Outliers):
- 20% आउटलेयर कंटैमिनेशन वाले डेटासेट में, LAD-CD ने OLS से काफी बेहतर प्रदर्शन किया और LP-आधारित सॉल्वर (QuantReg) की सटीकता के बराबर रहा।
- रिज-इनिशियलाइज्ड LAD-CD ने प्रारंभिक रिज फिट की तुलना में प्रेडिक्शन MAE को 32.5% और GA-इनिशियलाइज्ड फिट की तुलना में 44% कम कर दिया।
उच्च-आयामी प्रदर्शन ( $p \ge n$ ):
- LP सॉल्वर्स: $p > n$ होने पर समाधान देने में विफल रहे या $p=n$ होने पर ट्रिवियल ओवरफिटिंग उत्पन्न की।
- LAD-CD: स्थिर और सुपरिभाषित बना रहा।
- रिज इनिशियलाइजेशन: उच्च आयामों में अनरेगुलराइज्ड तरीकों और GA-आधारित स्टार्ट की तुलना में लगातार बेहतर रहा, सबसे कम प्रेडिक्शन एरर प्राप्त किया।
वास्तविक दुनिया के बेंचमार्क:
- Boston Housing, Air Quality, और Concrete डेटासेट पर, LAD-CD ने स्थापित quantreg (LP-आधारित) पैकेज के समान प्रेडिक्टिव सटीकता (MAE) प्राप्त की।
- हालांकि छोटे डेटासेट पर LP सॉल्वर तेज़ थे, LAD-CD एक मैट्रिक्स-इनवर्जन-मुक्त विकल्प प्रदान करता है जो प्रभावी ढंग से स्केल करता है।

5. महत्व और निहितार्थ (Significance and Implications)

व्यावहारिक उपयोगिता: यह तरीका मजबूत रिग्रेशन के लिए एक "सॉल्वर-फ्री" टूल प्रदान करता है जिसे विशेष LP सॉफ्टवेयर के बिना लागू करना आसान है।
उच्च-आयामी मजबूती: यह आधुनिक जीनोमिक्स और फाइनेंस में सामान्य परिदृश्य, जहाँ $p \ge n$ होता है, में रोबस्ट मीडियन रिग्रेशन को सक्षम करके सांख्यिकीय पद्धति में एक महत्वपूर्ण अंतर को भरता है।
कम्प्यूटेशनल दक्षता: प्रति स्वीप (sweep) में जटिलता को क्वाड्रेटिक से घटाकर $n$ के लगभग लीनियर तक लाकर, यह LAD रिग्रेशन को बड़े पैमाने के डेटासेट के लिए व्यवहार्य बनाता है।
भविष्य की दिशाएं: शोध पत्र कोऑर्डिनेट अपडेट को पैरेललाइज करने, सीधे CD स्टेप्स में स्पष्ट रेगुलराइजेशन (Lasso/Ridge) को शामिल करने, और न्यूनतम वितरण धारणाओं के तहत फाइनाइट-सैंपल गारंटी स्थापित करने पर भविष्य के कार्य का सुझाव देता है।

निष्कर्षतः, प्रस्तावित LAD-CD एल्गोरिदम पारंपरिक LP-आधारित सॉल्वर्स के लिए एक स्केलेबल, स्थिर और सैद्धांतिक रूप से सुदृढ़ विकल्प प्रदान करता है, जो विशेष रूप से उच्च-आयामी और आउटलेयर-कंटैमिनेटेड वातावरण में उत्कृष्ट है।