Metropolis--Hastings with Scalable Subsampling

यहाँ एस्तेवाओ प्राडो, क्रिस्टोफर नेमेथ और क्रिस शेरलॉक के शोध पत्र "Metropolis–Hastings with Scalable Subsampling" का विस्तृत तकनीकी सारांश दिया गया है।

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

बेशियन अनुमान (Bayesian inference) में, मेट्रोपोलिस-हैस्टिंग्स (MH) एल्गोरिदम पोस्टीरियर वितरणों से नमूने लेने के लिए एक मानक विधि है। हालाँकि, बड़े डेटासेट (जहाँ $n$ लाखों या अरबों में हो) के लिए, यह एल्गोरिदम कम्प्यूटेशनल रूप से अत्यधिक कठिन हो जाता है क्योंकि स्वीकृति अनुपात (acceptance ratio) की गणना करने के लिए प्रत्येक पुनरावृत्ति (iteration) पर पूर्ण लाइकलीहुड (full likelihood) (सभी $n$ डेटा बिंदुओं का योग) का मूल्यांकन करना आवश्यक होता है।

मौजूदा समाधान महत्वपूर्ण समझौते (trade-offs) का सामना करते हैं:

• अनुमानित विधियाँ (Approximate Methods): वेरिएशनल इन्फरेंस या लैपलेस सन्निकटन (Laplace approximations) तेज़ हैं लेकिन वे पूर्वाग्रह (bias) पेश करते हैं और सटीक नहीं हैं।
• डिवाइड-एंड-कन्कर (Divide-and-Conquer): डेटा को विभाजित करना और सब-पोस्टीरियर को संयोजित करना गैर-गौसियन लक्ष्यों (non-Gaussian targets) के लिए सटीक रूप से करना कठिन है।
• सटीक सबसैंपलिंग विधियाँ (Exact Subsampling Methods): पिछले सटीक सबसैंपलिंग MH एल्गोरिदम (जैसे कॉर्निश एट अल., 2019 द्वारा Scalable MH (SMH), और झांग एट अल., 2020 द्वारा TunaMH) डेटा के उपसमुच्चयों (subsets) का उपयोग करने का प्रयास करते हैं, लेकिन वे निम्नलिखित समस्याओं से ग्रस्त हैं:
  • ढीले अंतराल (Loose Bounds): वे लॉग-लाइकलीहुड अंतर के लिए बाउंड्स (bounds) पर निर्भर करते हैं जो पैरामीटर आयाम ($d$) बढ़ने पर बहुत ढीले हो जाते हैं, जिससे बड़े सबसैंपल्स का उपयोग करने के लिए मजबूर होना पड़ता है।
  • खराब मिक्सिंग (Poor Mixing): उचित स्वीकृति दर बनाए रखने के लिए, इन विधियों को अक्सर प्रस्ताव स्टेप साइज (प्रस्तावित चरण आकार) $\lambda$ को काफी कम करने की आवश्यकता होती है, जिससे उच्च ऑटोकोरिलेशन और धीमी मिक्सिंग होती है।
  • वैरिएंस संबंधी मुद्दे (Variance Issues): TunaMH जैसी विधियाँ उच्च-वैरिएंस वाले स्वीकृति अनुपातों का उपयोग करती हैं जिन्हें स्थिर करने के लिए ट्यूनिंग मापदंडों की आवश्यकता होती है, जो अक्सर दक्षता की कीमत पर होता है।

2. कार्यप्रणाली: MH-SS एल्गोरिदम (Methodology: The MH-SS Algorithm)

लेखक Metropolis–Hastings with Scalable Subsampling (MH-SS) प्रस्तावित करते हैं, जो एक सटीक एल्गोरिदम है जो एक पूर्व-निर्धारित अनुमानित पोस्टीरियर मोड ($\hat{\theta}$) के आसपास लॉग-लाइकलीहुड पदों के टेलर एक्सपेंशन (Taylor expansions) से प्राप्त कंट्रोल वेरिएट्स (control variates) का उपयोग करते हुए, वास्तविक पोस्टीरियर के संबंध में विस्तृत संतुलन (detailed balance) को संतुष्ट करता है।

मुख्य तंत्र (Core Mechanism)

एल्गोरिदम वर्तमान स्थिति $\theta$ और प्रस्तावित स्थिति $\theta'$ के बीच लॉग-लाइकलीहुड अंतर के लिए कंट्रोल वेरिएट्स का उपयोग करता है:

1. कंट्रोल वेरिएट्स (Control Variates):
   $\theta'$ और $\theta$ के बीच लॉग-लाइकलीहुड अंतर के लिए, लेखक $\ell_i(\theta') - \ell_i(\theta)$ को निम्नलिखित का उपयोग करके अनुमानित करते हैं:

   • प्रथम-क्रम (CV1): रैखिक टेलर एक्सपेंशन।
   • द्वितीय-क्रम (CV2): हेसियन (Hessian) के साथ द्विघात (quadratic) टेलर एक्सपेंशन।

   अनुमान त्रुटि को एक नियतक फलन (deterministic function) द्वारा सीमित किया गया है:
   $$|\ell_i(\theta') - \ell_i(\theta) - r_i(\theta, \theta'; \hat{\theta})| \leq c_i M(\theta, \theta')$$
   जहाँ $c_i$ डेटा पर निर्भर करता है और $M(\theta, \theta')$ प्रस्ताव स्टेप साइज पर निर्भर करता है।

2. पॉइसन थिनिंग और सबसैंपलिंग (Poisson Thinning & Subsampling):
   सभी $n$ पदों का मूल्यांकन करने के बजाय, एल्गोरिदम डेटा इंडेक्स के एक यादृच्छिक उपसमुच्चय $I$ को चुनने के लिए पॉइसन थिनिंग का उपयोग करता है।

   • यह त्रुटि बाउंड्स और कंट्रोल वेरिएंट अंतर ($\Delta_i$) के आधार पर सहायक फलन $\phi_i$ और $\phi'_i$ को परिभाषित करता है।
   • डेटा बिंदुओं को इन फलनों के आनुपातिक संभावनाओं के साथ सैंपल किया जाता है।
   • स्वीकृति अनुपात का निर्माण एक निष्पक्ष अनुमानक (unbiased estimator) का उपयोग करके किया जाता है जिसमें सैंपल किए गए उपसमुच्चय का उपयोग होता है, जिससे यह सुनिश्चित होता है कि चेन सटीक (exact) पोस्टीरियर को लक्षित करती है।

3. डिलेड एक्सेप्टेंस (Delayed Acceptance - DA):
   एल्गोरिदम दो-चरणीय स्वीकृति प्रक्रिया का उपयोग करता है:

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

4. इष्टतम ट्यूनिंग (Optimal Tuning):
   लेखक यह स्थापित करते हैं कि दक्षता तब अधिकतम होती है जब पैरामीटर $\gamma$ (जो बाउंडिंग फंक्शन के आकार को नियंत्रित करता है) को 0 पर सेट किया जाता है। इसके अलावा, वे स्थापित करते हैं कि MH-SS के लिए इष्टतम स्वीकृति दर लगभग 45.2% है, जो रैंडम वॉक मेट्रोपोलिस (RWM) के लिए मानक 23.4% से काफी अधिक है, जिससे बड़े स्टेप साइज और बेहतर मिक्सिंग की अनुमति मिलती है।

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

• टाइट थ्योरेटिकल बाउंड्स (Tighter Theoretical Bounds): यह शोध पत्र लॉजिस्टिक, प्रोबिट, पॉइसन और रोबस्ट रिग्रेशन मॉडल के लिए लॉग-लाइकलीहुड अंतर शेष पदों के लिए नए, काफी टाइट बाउंड्स निकालता है। ये बाउंड्स मध्यम-से-उच्च आयामों में पिछले तरीकों (SMH) की तुलना में $O(d^{1/2})$ बेहतर स्केल करते हैं, जिससे आवश्यक सबसैंपल का आकार नाटकीय रूप से कम हो जाता है।
• कंट्रोल वेरिएट्स की इष्टतमता (Optimality of Control Variates): लेखक सिद्ध करते हैं कि स्वीकृति संभाव्यता के निर्माण में $\gamma=0$ सेट करने से स्वीकृति दर अधिकतम होती है, और फलस्वरूप, प्रति सेकंड प्रभावी नमूना आकार (effective sample size) अधिकतम होता है।
• कम्प्यूटेशनल जटिलता (Computational Complexity):
  • MH-SS की प्रति-पुनरावृत्ति लागत $n$ से स्वतंत्र ($O(d^{3/2})$ CV1 के लिए और $O(d^3/\sqrt{n})$ CV2 के लिए) दिखाई गई है।
  • इसके विपरीत, SMH जैसे पिछले तरीकों की लागत आयाम $d$ के साथ तेजी से घटती है।
• मल्टीमॉडल विस्तार (Multimodal Extension): यह शोध पत्र मल्टीमॉडल पोस्टीरियस (जैसे मिश्रण मॉडल) को संभालने के लिए MH-SS का एक सैद्धांतिक विस्तार प्रदान करता है, जो वर्तमान और प्रस्तावित अवस्था के मध्य बिंदु के आधार पर कंट्रोल वेरिएट्स का चयन करता है, जिससे विस्तृत संतुलन बनाए रखना सुनिश्चित होता है।

4. परिणाम (Results)

लेखक व्यापक सिमुलेशन और वास्तविक दुनिया के अनुप्रयोगों (Hepmass, UK Road Casualties, US Census, Gas Sensors) के माध्यम से MH-SS को सत्यापित करते हैं।

• दक्षता लाभ (Efficiency Gains):
  • RWM के विरुद्ध: MH-SS, मानक RWM की तुलना में लगातार क्रमों का अंतर (orders of magnitude) अधिक कुशल (प्रति सेकंड प्रभावी नमूना आकार के मामले में) है, विशेष रूप से जैसे-जैसे $n$ और $d$ बढ़ते हैं।
  • SMH के विरुद्ध: MH-SS को काफी छोटे सबसैंपल्स की आवश्यकता होती है। उदाहरण के लिए, $d=50$ के साथ लॉजिस्टिक रिग्रेशन में, SMH अक्सर सभी $n$ डेटा बिंदुओं का मूल्यांकन करने की आवश्यकता महसूस करता है, जबकि MH-SS एक बहुत ही छोटे अंश का उपयोग करता है।
  • TunaMH के विरुद्ध: हालांकि TunaMH छोटे सबसैंपल्स का उपयोग करता है, यह स्वीकृति दरों को बनाए रखने के लिए बहुत छोटे स्टेप साइज की आवश्यकता के कारण खराब मिक्सिंग से ग्रस्त है। MH-SS बड़े स्टेप्स के साथ उच्च स्वीकृति दर प्राप्त करता है, जिसके परिणामस्वरूप बहुत अधिक ESS होता है।
• वास्तविक दुनिया का प्रदर्शन (Real-World Performance):
  • Hepmass डेटासेट ($n=10^6, d=26$) पर, MH-SS-2 (द्वितीय-क्रम) ने लगभग 69.2 का ESS प्रति सेकंड प्राप्त किया, जबकि Tuna के लिए यह 0.002 और SMH-1 के लिए 0.016 था।
  • परीक्षण किए गए सभी रिग्रेशन मॉडल (Logistic, Probit, Poisson) में MH-SS-2 लगातार सबसे कुशल एल्गोरिदम रहा।
• स्केलिंग व्यवहार (Scaling Behavior): अनुभवजन्य परिणाम इस सैद्धांतिक भविष्यवाणी की पुष्टि करते हैं कि MH-SS, SMH की तुलना में आयाम $d$ के साथ बेहतर स्केल करता है। SMH के बाउंड्स की "ढीलापन" इसे $d$ बढ़ने के साथ अधिक डेटा का मूल्यांकन करने के लिए मजबूर करती है, जबकि MH-SS के बाउंड्स टाइट रहते हैं।

5. महत्व (Significance)

यह शोध पत्र स्केलेबल बेशियन अनुमान (scalable Bayesian inference) में एक प्रमुख प्रगति का प्रतिनिधित्व करता है।

1. सटीकता (Exactness): यह एक ऐसा तरीका प्रदान करता है जो विशाल डेटासेट के लिए कम्प्यूटेशनल रूप से व्यवहार्य है जबकि सटीकता बनाए रखता है (वेरिएशनल इन्फरेंस के विपरीत)।
2. व्यावहारिकता (Practicality): टाइट बाउंड्स और इष्टतम ट्यूनिंग मापदंडों को व्युत्पन्न करके, लेखक एल्गोरिदम को मानक रिग्रेशन मॉडल के लिए मजबूत और लागू करने में आसान बनाते हैं, जिसमें फायरफ्लाई मोंटे कार्लो जैसे तरीकों के लिए आवश्यक जटिल, समस्या-विशिष्ट लोअर बाउंड्स की आवश्यकता नहीं होती है।
3. दक्षता (Efficiency): छोटे सबसैंपल्स के साथ उच्च स्वीकृति दर (45%) प्राप्त करने की क्षमता चैन को पोस्टीरियर स्पेस को बहुत तेज़ी से एक्सप्लोर करने की अनुमति देती है, जो इसे मौजूदा सटीक सबसैंपलिंग विधियों की तुलना में एक बेहतर विकल्प बनाती है, जिससे यह "बिग डेटा" बेशियन विश्लेषण के लिए एक उत्कृष्ट विकल्प बन जाता है।

संक्षेप में, MH-SS टाइट कंट्रोल वेरिएंट बाउंड्स और इष्टतम स्वीकृति रणनीतियों का लाभ उठाकर सबसैंपलिंग MCMC में "डायमेंशनलिटी के अभिशाप" (curse of dimensionality) को हल करता है, जो बड़े पैमाने के बेशियन अनुमान के लिए एक व्यावहारिक, सटीक और अत्यधिक कुशल समाधान प्रदान करता है।