⚡ electrical engineering

Conformal Predictive Programming for Chance Constrained Optimization

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

मूल लेखक: Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

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

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

CC BY 4.0

मूल लेखक: Yiqi Zhao, Xinyi Yu, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann

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

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

यह चांस कांस्ट्रेंड ऑप्टिमाइज़ेशन (Chance Constrained Optimization) की समस्या है। यह एक रास्ता खोजने जैसा है जबकि आप यह कह रहे हों, "मुझे 90% यकीन है कि मैं दीवार से नहीं टकराऊंगा," बिना यह जाने कि भूलभुलैया के सटीक नियम क्या हैं।

पुराना तरीका: परिदृश्यों (Scenarios) के साथ अनुमान लगाना

पारंपरिक रूप से, इंजीनियरों ने "सिनारियो अप्रोच" (Scenario Approach) नामक एक विधि का उपयोग किया है। कल्पना कीजिए कि आप दोस्तों के एक समूह से अनुमान लगाने के लिए कहते हैं कि दीवारें कहां हो सकती हैं। फिर आप एक ऐसा रास्ता बनाते हैं जो आपके दोस्तों द्वारा अनुमानित हर दीवार से बचता है। यदि आप पर्याप्त दोस्तों से पूछते हैं, तो आप एक सुरक्षित रास्ता खोजने में सफल हो सकते हैं।

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

नया विचार: कॉन्फॉर्मल प्रेडिक्टिव प्रोग्रामिंग (CPP)

इस शोध पत्र के लेखक कॉन्फॉर्मल प्रेडिक्टिव प्रोग्रामिंग (CPP) नामक एक नया टूल प्रस्तावित करते हैं। CPP को एक दो-चरणीय "परीक्षण और प्रमाणित" (test and certify) प्रक्रिया के रूप में समझें जो तब भी काम करती है जब आपको खेल के सटीक नियम नहीं पता होते।

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

चरण 2: सुरक्षा जांच (कैलिब्रेशन)
यहीं पर CPP चतुर हो जाता है। केवल अभ्यास सत्र पर भरोसा करने के बजाय, रोबोट डेटा का एक दूसरा, पूरी तरह से अलग सेट (अन्य 200 रन) लेता है जो एक 'रेफरी' के रूप में कार्य करेगा। यह चरण 1 में खोजे गए पथ की इस नए रेफरी डेटा के विरुद्ध जांच करता है।

"क्वांटाइल लेम्मा" (Quantile Lemma) नामक एक सांख्यिकीय ट्रिक का उपयोग करते हुए, CPP एक सुरक्षा मार्जिन की गणना करता है। यह पूछता है: "रेफरी डेटा में यह पथ कितनी बार विफल हुआ?" यदि यह बहुत बार विफल हुआ, तो पथ को खारिज कर दिया जाता है। यदि यह पर्याप्त बार पास हुआ, तो सिस्टम एक "प्रमाणपत्र" देता है कि, "हमें 90% यकीन है कि यह रास्ता सुरक्षित है।"

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

यह पेपर CPP की तीन मुख्य महाशक्तियों को उजागर करता है:

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

आंकड़े क्या कहते हैं

लेखकों ने केवल सिद्धांत नहीं दिया; उन्होंने यह साबित करने के लिए सिमुलेशन चलाए कि यह काम करता है।

एक कॉन्वेक्स (चिकने) परीक्षण मामले में, उन्होंने 300 प्रयोग चलाए। नई विधि ने सफलतापूर्वक रोबोट को लगभग 91% बार सुरक्षित रखा (उनके 90% सुरक्षा लक्ष्य से मेल खाता है), जबकि पुराने "डिस्कार्ड" (discard) तरीके ने केवल 87% ही हासिल किया।
एक नॉन-कॉन्वेक्स (टेढ़े-मेढ़े) परीक्षण मामले में, जो बहुत कठिन है, नई विधि ने अभी भी 90% और 89% सुरक्षा दर हासिल की।
उन्होंने एक "स्टोकेस्टिक ऑप्टिमल कंट्रोल" (Stochastic Optimal Control) परिदृश्य का परीक्षण किया (एक 2D स्पेस में चलते रोबोट)। जब उन्होंने एक "डिस्ट्रीब्यूशन शिफ्ट" (वैरिएंस को 0.012 से 0.013 में बदलकर) पेश किया, तो मानक विधि सुरक्षा लक्ष्य को पूरा करने में विफल रही (केवल 80%), लेकिन नया "रोबस्ट CPP" विधि 96% तक पहुँच गया।

वे क्या दावा नहीं करते हैं

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

निष्कर्ष

पेपर सुझाव देता है कि समस्या को "प्लानिंग" चरण और "कैलिब्रेशन" चरण में विभाजित करके, हम अधिक सुरक्षित और विश्वसनीय रोबोट और सिस्टम बना सकते हैं, भले ही दुनिया अस्त-व्यस्त और अप्रत्याशित हो। यह यह कहने का एक तरीका है कि, "हमें आज एक सुरक्षित योजना बनाने के लिए भविष्य के बारे में सब कुछ जानने की आवश्यकता नहीं है; हमें बस अपने काम की जांच करने का एक अच्छा तरीका चाहिए।"

तकनीकी सारांश: चांस कांस्ट्रेंड ऑप्टिमाइज़ेशन के लिए कॉन्फॉर्मल प्रेडिक्टिव प्रोग्रामिंग

समस्या विवरण (Problem Statement)
यह शोध पत्र चांस कांस्ट्रेंड ऑप्टिमाइज़ेशन (CCO) समस्याओं को संबोधित करता है, जिनमें एक रैंडम वेक्टर $Y$ पर उच्च संभावना ( $1-\delta$ ) के साथ बाधाओं (constraints) को पूरा करते हुए एक लागत फलन (cost function) $J(x)$ को न्यूनतम करना शामिल है। औपचारिक रूप से, समस्या है:
$\min_{x \in X} J(x) \quad \text{s.t.} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$
जहाँ $f$ एक बोरेल मेजरेबल (Borel measurable) फलन है और $Y$ एक अज्ञात वितरण $P_Y$ का अनुसरण करता है। CCO को हल करने में प्राथमिक चुनौती यह है कि $P_Y$ आमतौर पर अज्ञात होता है, और यदि ज्ञात भी हो, तो संभाव्यता बाधा (probability constraint) का मूल्यांकन करने के लिए जटिल, अक्सर अगम्य (intractable) समाकलों (integrals) को हल करने की आवश्यकता होती है। मौजूदा सैंपलिंग-आधारित दृष्टिकोण, जैसे कि सिनारियो अप्रोच (Scenario Approach - SA) और सैंपल एवरेज एप्रोक्सिमेशन (Sample Average Approximation - SAA), अक्सर मजबूत संरचनात्मक धारणाओं (जैसे $J$ , $f$ , और $X$ की उत्तलता/convexity) पर निर्भर करते हैं ताकि ए प्राइori (a priori) गारंटी प्रदान की जा सके। जब ये धारणाएं लागू नहीं होती हैं, या जब ए प्राइori गारंटी बहुत अधिक रूढ़िवादी (conservative) या गणनात्मक रूप से महंगी होती है (जैसे कि सपोर्ट बाधाओं की पहचान करने की आवश्यकता), तो मौजूदा विधियाँ विश्वसनीय ए पोस्टेरियोरी (a posteriori) व्यवहार्यता गारंटी प्रदान करने में संघर्ष करती हैं।

कार्यप्रणाली: कॉन्फॉर्मल प्रेडिक्टिव प्रोग्रामिंग (CPP)
लेखक कॉन्फॉर्मल प्रेडिक्टिव प्रोग्रामिंग (CPP) का प्रस्ताव करते हैं, जो एक ढांचा है जो कॉन्फॉर्मल प्रेडिक्शन (CP) का उपयोग करके स्टोकेस्टिक CCO समस्या को एक नियतात्मक (deterministic) अनुकूलन समस्या में बदल देता है। CPP दो विशिष्ट चरणों में कार्य करता है:

अनुकूलन चरण (क्वांटाइल रिफॉर्मुलेशन):
सीधे चांस कंस्ट्रेंट के बजाय, CPP एक क्वांटाइल बाधा का उपयोग करता है जो एक अनुकूलन डेटासेट $\{Y^{(1)}, \dots, Y^{(K)}\}$ पर आधारित है। इसे इस प्रकार पुनर्गठित किया जाता है:
$\min_{x \in X} J(x) \quad \text{s.t.} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$
यहाँ, $\hat{Q}_{\alpha(K)}$ एक विशिष्ट कॉन्फिडेंस लेवल $\alpha(K)$ पर एम्पिरिकल क्वांटाइल है। लेखक यह प्रदर्शित करते हैं कि यह रिफॉर्मुलेशन SAA का एक उदाहरण है, जिससे CPP विशिष्ट समस्या वर्गों (जैसे, सेपरेबल कंस्ट्रेंट्स) के लिए SAA साहित्य से ए प्राइओरी गारंटी प्राप्त कर सकता है।
कैलिब्रेशन चरण (ए पोस्टेरियोरी गारंटी):
संरचनात्मक धारणाओं (जैसे उत्तलता) पर निर्भर रहे बिना कठोर ए पोस्टेरियोरी व्यवहार्यता गारंटी प्रदान करने के लिए, CPP एक दूसरे, स्वतंत्र कैलिब्रेशन डेटासेट $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$ का उपयोग करता है।

मार्जनल गारंटी (Marginal Guarantees): CP के क्वांटाइल लेम्मा का उपयोग करते हुए, CPP कैलिब्रेशन डेटा पर एक क्वांटाइल $C_m$ की गणना करता है। प्रमेय 3.4 स्थापित करता है कि समाधान $x^*(K)$ डेटा के प्रोडक्ट मेजर के संबंध में $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ को संतुष्ट करता है।
कंडीशनल गारंटी (Conditional Guarantees): क्वांटाइल गणना के दौरान एक कड़ा (tightened) कॉन्फिडेंस लेवल का उपयोग करके, CPP ऐसी गारंटी प्रदान करता है जो कैलिब्रेशन डेटासेट पर उच्च विश्वास ( $1-\beta$ ) के साथ बनी रहती है।
क्वांटाइल शिफ्ट (Quantile Shift): उन मामलों को संबोधित करने के लिए जहाँ गणना किया गया बाउंड $C$ धनात्मक है, लेखक एक "क्वांटाइल शिफ्ट" विधि (प्रमेय 3.6) प्रस्तावित करते हैं। यह कैलिब्रेशन सेट में संतुष्ट बाधाओं की संख्या के आधार पर एक समायोजित विफलता संभावना $\delta^*$ की गणना करता है, जो सुनिश्चित करता है कि $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ उच्च विश्वास के साथ।

प्रमुख योगदान

नया ढांचा: CCO समस्याओं के लिए एक सैंपलिंग-आधारित दृष्टिकोण के रूप में CPP का परिचय, जिसके लिए सीमित संरचनात्मक धारणाओं की आवश्यकता होती है।
सांख्यिकीय गारंटी: दोनों कंडीशनल और मार्जनल ए पोस्टेरियोरी व्यवहार्यता गारंटी प्रदान करना। मानक SA के विपरीत, ये गारंटी निर्णय चर (decision variable) के आयाम $n$ पर निर्भर नहीं करती हैं, जिससे उच्च-आयामी समस्याओं के लिए रूढ़िवादिता कम हो जाती है।
मॉड्यूलरिटी और बहुमुखी प्रतिभा: यह ढांचा विभिन्न कॉन्फॉर्मल प्रेडिक्शन वेरिएंट्स को आसानी से शामिल करने के लिए डिज़ाइन किया गया है। लेखक CPP को निम्नलिखित में विस्तारित करके इसे प्रदर्शित करते हैं:
- रोबस्ट CPP (RCPP): रोबस्ट कॉन्फॉर्मल प्रेडिक्शन और एम्बिग्युटी सेट्स का उपयोग करके वितरण बदलाव (जैसे सिम-टू-रियल गैप) को संभालता है।
- मोंड्रियन CPP (MCPP): क्लास-कंडीशनल चांस कंस्ट्रेंट्स (MCCO) को संबोधित करता है, यह सुनिश्चित करता है कि सुरक्षा गारंटी रैंडम वेरिएबल के विशिष्ट उपसमूहों (subgroups) के लिए बनी रहे।
मौजूदा सिद्धांत से जुड़ाव: यह शोध पत्र स्थापित करता है कि CPP, SAA से ए प्राइओरी गारंटी विरासत में प्राप्त करता है और इसके कंडीशनल ए पोस्टेरियोरी गारंटी एसिम्प्टोटिक रूप से चेरनोफ बाउंड्स (Chernoff bounds) में बदल जाते हैं।

परिणाम और केस स्टडीज
लेखक वक्रीय (convex) और गैर-वक्रीय (nonconvex) दोनों समस्याओं और एक स्टोकेस्टिक ऑप्टिमल कंट्रोल कार्य सहित संख्यात्मक केस स्टडीज के माध्यम से CPP को मान्य करते हैं।

वक्रता और गैर-वक्रता अनुकूलन: गैर-वक्रता समस्याओं के लिए CPP की तुलना सिनारियो अप्रोच (SA) से करने वाले प्रयोगों में, CPP ने प्रतिस्पर्धी प्रदर्शन दिखाया। विशेष रूप से, जबकि गैर-वक्रता SA विधियों (जैसे, [18, 26]) को ए पोस्टेरियोरी गारंटी के लिए महंगे कम्प्यूटेशनल स्टेप्स की आवश्यकता होती है (अध्ययन में ~10 सेकंड), CPP का क्वांटाइल शिफ्ट कैलकुलेशन काफी तेज़ (लीनियर टाइम) है।
एम्पिरिकल कवरेज: प्रयोगों ने पुष्टि की कि समाधानों का एम्पिरिकल कवरेज सैद्धांतिक बाउंड्स ( $1-\delta$ या $1-\delta^*$ ) की ओर अभिसरित (converge) होता है। शून्य के पास केंद्रित गणना किए गए बाउंड्स के हिस्टोग्राम दर्शाते हैं कि क्वांटाइल रिफॉर्मुलेशन मूल चांस कंस्ट्रेंट का प्रभावी ढंग से अनुमान लगाता है।
रोबस्ट और मोंड्रियन विस्तार: एक स्टोकेस्टिक ऑप्टिमल कंट्रोल समस्या (रोबोट नेविगेशन) में, RCPP ने वितरण बदलाव (शोर भिन्नता में परिवर्तन का अनुकरण) को सफलतापूर्वक संभाला, जिससे मानक CPP बेसलाइन (0.80) की तुलना में उच्च एम्पिरिकल कवरेज (0.96) प्राप्त हुआ। इसी तरह, मोंड्रियन CPP ने विशिष्ट डिस्टर्बेंस मैग्नीट्यूड समूहों के लिए कवरेज गारंटी बनाए रखने में सफलता प्राप्त की जहाँ मानक CPP विफल रहा था।

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