📊 statistics

The windowEM algorithm

यह शोध पत्र windowEM एल्गोरिदम का प्रस्ताव करता है, जो EM पद्धति का एक स्टोकेस्टिक संस्करण है जो अनुक्रमिक अपडेट और रोलिंग विंडो स्मूथिंग के माध्यम से अनुमानों की एक जनसंख्या उत्पन्न करने के लिए डेटा को एक वृत्त पर व्यवस्थित ब्लॉकों में विभाजित करता है, जिससे अभिसरण गारंटी और संभावित ओवर-फिटिंग रोकथाम प्राप्त होती है।

मूल लेखक: Carsten Wiuf, Malthe Sebro Rasmussen

प्रकाशित 2026-07-07

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

CC BY 4.0

मूल लेखक: Carsten Wiuf, Malthe Sebro Rasmussen

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

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

यह windowEM एल्गोरिदम के पीछे का मूल विचार है जिसका वर्णन कार्सटेन विउफ (Carsten Wiuf) और माल्थे सेब्रो रासमुसेन (Malthe Sebro Rasmussen) के शोध पत्र में किया गया है। यह जटिल सांख्यिकीय समस्याओं (विशेष रूप से जिसे "EM एल्गोरिदम" कहा जाता है) को हल करने का एक नया तरीका है, जब आपके पास संभालने के लिए बहुत अधिक डेटा हो।

यह कैसे काम करता है, इसे सरल अवधारणाओं में यहाँ दिया गया है:

1. समस्या: बहुत अधिक डेटा, बहुत अधिक शोर (Noise)

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

इसलिए, वैज्ञानिकों ने डेटा को छोटे हिस्सों या "ब्लॉक्स" (blocks) में विभाजित करना शुरू किया, और एक बार में केवल एक ब्लॉक को देखना शुरू किया। यह तेज़ है, लेकिन इसमें एक समस्या है: यह शोर भरा (noisy) है।

उपमा (Analogy): कल्पना कीजिए कि आप केवल एक व्यक्ति को शहर के सभी लोगों की औसत ऊंचाई का अनुमान लगाने के लिए कहते हैं। वे सड़क पर किसी बास्केटबॉल खिलाड़ी या किसी छोटे बच्चे को चुन सकते हैं। उनका अनुमान "रफ" और अविश्वसनीय होगा। यदि आप हर बार अलग-अलग यादृच्छिक (random) लोगों के साथ ऐसा करते हैं, तो आपका अंतिम उत्तर अस्थिर होगा।

2. समाधान: "रोलिंग विंडो" (The Rolling Window)

लेखकों ने एक चतुर ट्रिक प्रस्तावित की है जिसे windowEM कहा जाता है। केवल एक ब्लॉक को देखने और आगे बढ़ने के बजाय, वे सभी डेटा ब्लॉक्स को एक घेरे (circle) में व्यवस्थित करते हैं।

यहाँ प्रक्रिया दी गई है:

घेरा (The Circle): कल्पना कीजिए कि आपके सभी डेटा ब्लॉक्स एक गोल मेज के चारों ओर रखी सीटों की तरह हैं।
पास करना (The Pass): आप एक सीट से शुरू करते हैं, उस ब्लॉक के आधार पर एक त्वरित अनुमान लगाते हैं, और घेरे में अगले व्यक्ति को "बैटन" (आपका वर्तमान अनुमान) पास करते हैं।
विंडो (The Window): केवल वर्तमान व्यक्ति के अनुमान का उपयोग करने के बजाय, आप पिछले $w$ लोगों के अनुमानों को देखते हैं। आप अपने नए निर्णय को लेने के लिए उनके अनुमानों का औसत (average) लेते हैं।
स्मूथिंग (The Smoothing): यह "विंडो" एक स्मूथिंग फिल्टर के रूप में कार्य करती है। यदि कोई व्यक्ति एक अजीब, शोर भरा अनुमान देता है (जैसे किसी बच्चे की ऊंचाई मापना), तो अगले कुछ लोगों के अधिक तर्कसंगत अनुमान औसत को सत्य की ओर वापस खींच लेंगे। यह शोर को रद्द कर देता है।

3. दो परिदृश्य: परिमित बनाम अनंत (Finite vs. Infinite)

शोध पत्र देखता है कि यह घेरा दो तरीकों से काम कर सकता है:

परिदृश्य A: परिमित घेरा (B परिमित है)
आपके पास ब्लॉक्स की एक निश्चित संख्या है (मान लीजिए 50)। आप घेरे के चारों ओर जाते हैं, फिर से चक्कर लगाते हैं, और फिर से।
- परिणाम: आपको केवल एक अंतिम उत्तर नहीं मिलता है। आपको एक उत्तरों की जनसंख्या (population of answers) मिलती है (प्रत्येक ब्लॉक के लिए एक)।
- लाभ: यदि आप अंत में इन सभी उत्तरों का औसत निकालते हैं, तो आपको एक बहुत ही स्थिर परिणाम प्राप्त होता है। शोध पत्र गणितीय रूप से सिद्ध करता है कि यदि आप घेरे के चारों ओर घूमते रहते हैं, तो ये उत्तर अंततः स्थिर हो जाएंगे और बदलना बंद कर देंगे।
परिदृश्य B: अनंत प्रवाह (B अनंत है)
कल्पना कीजिए कि डेटा इतना विशाल है कि आप कभी भी एक ही ब्लॉक को दोबारा नहीं देखते। आप बस एक अंतहीन सड़क पर चल रहे हैं।
- परिणाम: आप चलते समय अपने अनुमान को अपडेट करते रहते हैं। शोध पत्र दिखाता है कि इस अंतहीन प्रवाह में भी, यदि आप अपने हालिया कदमों का औसत (विंडो) निकालते रहते हैं, तो आपका अनुमान अंततः स्थिर हो जाएगा और सही उत्तर की ओर अग्रसर होगा।

4. "एवरेजिंग" (Averaging) "परफेक्टिंग" (Perfecting) से बेहतर क्यों है

इस शोध पत्र की एक सबसे दिलचस्प खोज ओवर-फिटिंग (over-fitting) के बारे में है।

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

5. वास्तविक दुनिया के उदाहरण

लेखकों ने इसे दो उदाहरणों के साथ परखा:

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

सारांश

windowEM एल्गोरिदम डेटा के विशाल मात्रा को संसाधित करने का एक स्मार्ट तरीका है:

डेटा को ब्लॉक्स में तोड़कर।
एक घेरे में अनुमानों को पास करके।
शोर को कम करने के लिए हालिया अनुमानों का औसत (average) निकालकर।

यह एक एकल "परफेक्ट" अनुमान के विचार के बजाय स्थिर, औसत अनुमानों की एक जनसंख्या के लिए व्यापार करता है, जो बड़े, अव्यवस्थित डेटासेट के साथ काम करते समय अक्सर अधिक सटीक और त्रुटियों के प्रति कम संवेदनशील होता है।

"The windowEM एल्गोरिदम" का तकनीकी सारांश

समस्या विवरण (Problem Statement)
एक्सपेक्टेशन-मैक्सिमाइजेशन (EM) एल्गोरिदम लेटेंट वेरिएबल्स (latent variables) वाले मॉडलों में मैक्सिमम लाइक्लीहुड एस्टीमेशन के लिए एक मानक विधि है। हालांकि, बड़े पैमाने के डेटासेट (जैसे कि अरबों बिंदुओं वाले जीनोमिक डेटा) के संदर्भ में, मानक EM एल्गोरिदम गणनात्मक रूप से अव्यवहारिक हो जाता है क्योंकि इसे प्रत्येक पुनरावृत्ति (iteration) में पूरे डेटासेट को प्रोसेस करने की आवश्यकता होती है। जबकि कन्वर्जेंस को तेज करने के लिए स्टोकेस्टिक EM (मिनी-बैच का उपयोग करके) के संस्करण प्रस्तावित किए गए हैं, वे अक्सर खुरदरे या शोर वाले पैरामीटर अनुमान (parameter estimates) उत्पन्न करते हैं, विशेष रूप से तब जब पैरामीटर स्पेस जटिल हो या जब कुछ लेटेंट वेरिएबल्स डेटा में विरल (sparsely represented) हों। यह शोर आर्टिफैक्ट्स (artifacts) पैदा कर सकता है, जैसे कि अनुमानित डिस्ट्रीब्यूशन (जैसे साइट फ्रीक्वेंसी स्पेक्ट्रा - SFS) में कृत्रिम "बम्प्स" (bumps), और यह ओवर-फिटिंग में भी योगदान दे सकता है।

कार्यप्रणाली (Methodology): The windowEM एल्गोरिदम
लेखक windowEM का प्रस्ताव करते हैं, जो EM एल्गोरिदम का एक स्टोकेस्टिक संस्करण है जो डेटा को $B$ ब्लॉक्स में विभाजित करता है और इन ब्लॉक्स को एक वृत्त (circle) पर व्यवस्थित करता है। एल्गोरिदम निम्नलिखित तंत्र के माध्यम से कार्य करता है:

ब्लॉक विभाजन (Block Partitioning): डेटा को $B$ ब्लॉक्स ( $x_1, \dots, x_B$ ) में विभाजित किया जाता है। ब्लॉक्स के आकार और वितरण भिन्न हो सकते हैं और यह माना नहीं गया है कि वे स्वतंत्र हैं।
अनुक्रमिक अपडेट (Sequential Updates): एल्गोरिदम अपडेट की एक श्रृंखला करता है जहाँ वर्तमान ब्लॉक $k$ के लिए अनुमान पिछले ब्लॉक $k-1$ से प्राप्त अनुमान का उपयोग करके निकाला जाता है। विशेष रूप से, एक प्रारंभिक अनुमान $\psi_{t+1}$ प्राप्त किया जाता है, जो वर्तमान पैरामीटर अनुमान $\theta_t$ का उपयोग करके ब्लॉक $b(t+1)$ पर मानक EM एल्गोरिदम का एक इटरेशन करके प्राप्त होता है:
$\psi_{t+1} = f_{b(t+1)}(\theta_t) = \arg\max_{\theta'} Q_{b(t+1)}(\theta' | \theta_t)$
रोलिंग विंडो एवरेजिंग (Rolling Window Averaging): सिंगल-ब्लॉक अपडेट में निहित शोर का मुकाबला करने के लिए, एल्गोरिदम अनुमानों की एक "जनसंख्या" (population) बनाए रखता है। एक दिए गए चरण के लिए अंतिम अनुमान $\theta_t$ , $w$ के आकार की रोलिंग विंडो के भीतर $w$ सबसे हालिया प्रारंभिक अनुमानों का औसत होता है:
$\theta_t = \frac{1}{w} \sum_{i=t-w+1}^{t} \psi_i$
चक्रीय पुनरावृत्ति (Circular Iteration): ब्लॉक्स को चक्रीय रूप से व्यवस्थित किया जाता है। यदि $B$ परिमित (finite) है, तो एल्गोरिदम ब्लॉक्स को बार-बार दोहराता है (epochs)। यदि $B = \infty$ है, तो एल्गोरिदम अद्वितीय ब्लॉक्स के अनंत अनुक्रम के माध्यम से आगे बढ़ता है।
अंतिम अनुमान (Final Estimation): $B$ अनुमानों की जनसंख्या का औसत निकालकर एक एकल पॉइंट एस्टीमेट तैयार किया जा सकता है।

लेखक नोट करते हैं कि हालांकि windowEM से पॉलीक-रुपर्ट एवरेजिंग (Polyak-Ruppert averaging) प्रेरित है, यह इससे भिन्न है क्योंकि यह ग्रेडिएंट्स या मानक स्टोकेस्टिक ग्रेडिएंट डिसेंट के तरीके में अपडेट के औसत के बजाय, एक गोलाकार व्यवस्था में क्रमिक EM चरणों पर उत्पन्न अनुमानों पर औसत लागू करता है।

प्रमुख सैद्धांतिक योगदान (Key Theoretical Contributions)
पेपर दो परिदृश्यों के तहत windowEM के कन्वर्जेंस गुणों की जांच करता है: परिमित $B$ और अनंत $B$ ।

परिमित $B$ (Finite $B$ ): लेखक कॉन्ट्रैक्शन थ्योरी (contraction theory) का उपयोग करते हैं। वे स्थापित करते हैं कि यदि अपडेट फंक्शन एक कॉन्ट्रैक्शन है, तो ब्लॉक्स का अनुक्रम अभिसरण (converge) करता है। एक प्रमुख निष्कर्ष यह है कि यदि एक ब्लॉक के लिए फिक्स्ड पॉइंट मौजूद है, तो सभी ब्लॉक्स के लिए फिक्स्ड पॉइंट मौजूद होता है। इन ब्लॉक अनुमानों का वितरण विंडो साइज $w$ पर निर्भर करता है; अनुभवजन्य रूप से, बड़े विंडो साइज ब्लॉक्स के अनुमानों के बीच कम वेरिएंस (variance) का परिणाम देते हैं।
अनंत $B$ (Infinite $B$ ): $B = \infty$ के मामले के लिए (या पर्याप्त बड़ा जहाँ ब्लॉक्स कभी दोहराए नहीं जाते), लेखक डिपेंडेंट डेटा के लिए रैंडम इटरेशन थ्योरी को लागू करते हैं। वे ऐसी स्थितियाँ प्रदान करते हैं जिनके तहत बड़े ब्लॉक इंडेक्स के लिए अनुमान एक फिक्स्ड पॉइंट की ओर अभिसरित होते हैं। इसके अलावा, वे ऐसी स्थितियाँ स्थापित करते हैं जो $B \to \infty$ होने पर ब्लॉक अनुमानों के एर्गोडिक एवरेज (ergodic average) के कन्वर्जेंस की गारंटी देती हैं।
एक्सपोनेंशियल फैमिली (Exponential Families): विश्लेषण विशेष रूप से एक्सपोनेंशियल फैमिली के लिए कठोर है। लेखक प्रदर्शित करते हैं कि मीन वैल्यू पैरामीट्राइजेशन के लिए, अपडेट फंक्शन अक्सर पर्याप्त सांख्यिकी (sufficient statistics) का एक रैखिक फंक्शन होता है। मिश्रण (mixtures) के मामले में, अपडेट फंक्शन ऑब्जर्व्ड स्टैटिस्टिक्स में रैखिक रहता है, जो अनुमानित क्लास प्रोबेबिलिटीज द्वारा भारित (weighted) होता है।
विशेष मामले (Special Cases): पेपर विशिष्ट कॉन्फ़िगरेशन का विश्लेषण करता है, जैसे $w=1$ (जो बिना एवरेजिंग के एक क्रमिक EM में बदल जाता है) और $w=B$ (जहाँ अपडेट सभी ब्लॉक्स पर एक औसत बन जाता है, जो रैखिकता धारणाओं के तहत मानक EM समाधान के समकक्ष एक फिक्स्ड पॉइंट दे सकता है)।

अनुभवजन्य परिणाम (Empirical Results)
पेपर दो प्राथमिक उदाहरणों का उपयोग करके एल्गोरिदम को मान्य करता है:

इलस्ट्रेटिव बिनोमियल उदाहरण (Illustrative Binomial Example): एक जीन फ्रीक्वेंसी एस्टीमेशन समस्या। परिणाम दिखाते हैं कि windowEM तेजी से मैक्सिमम लाइक्लीहुड एस्टीमेट (MLE) की ओर अभिसरित होता है। अनुमानों का वेरिएंस $w$ बढ़ने के साथ घटता है, हालांकि बड़े $w$ के साथ कन्वर्जेंस की गति थोड़ी धीमी हो सकती है।
यूनिवेरिएट गौसियन मिक्सचर (Univariate Gaussian Mixtures): एल्गोरिदम का परीक्षण गौसियन डिस्ट्रीब्यूशन के मिश्रण पर किया गया है।
- $n=10^5$ डेटा पॉइंट्स और $B=10$ ब्लॉक्स के साथ एक सिमुलेशन में, windowEM ने मानक EM की तुलना में काफी तेजी से पूर्ण-डेटा MLE के करीब लॉग-लाइक्लीहुड प्राप्त किया।
- उल्लेखनीय रूप से, जबकि मानक EM ने अंततः windowEM की तुलना में उच्च लॉग-लाइक्लीहुड प्राप्त किया, इसने पूर्ण-डेटा MLE को भी पार कर लिया, जो ओवर-फिटिंग का सुझाव देता है। windowEM का अनुमान, जो अनुमानों की जनसंख्या का औसत है, एक रेगुलराइज़र (regularizer) के रूप में कार्य करता हुआ प्रतीत हुआ, जो पूर्ण-डेटा MLE के करीब रहा बिना उस "ओवरशूट" के जो मानक EM में देखा गया था।
- समान रुझान छोटे ( $n=10^4$ ) और बड़े ( $n=10^6$ ) डेटासेट में भी देखे गए, जहाँ windowEM ने मानक EM की तुलना में मानक EM से अधिक तेजी से और स्थिर रूप से पूर्ण-डेटा MLE के करीब स्थिर होकर प्रदर्शन किया।

महत्व और दावे (Significance and Claims)
लेखक दावा करते हैं कि windowEM उन बड़े पैमाने के इन्फरेंस के लिए एक व्यावहारिक समाधान प्रदान करता है जहाँ मानक EM अव्यवहारिक है और मानक स्टोकेस्टिक EM बहुत शोर वाला है। प्राथमिक महत्व एक रोलिंग विंडो में अनुमानों की जनसंख्या को औसत करने से उत्पन्न रेगुलराइजेशन प्रभाव (regularization effect) में निहित है।

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