2025-11-16T14:37:12.620917

Multi-model Online Conformal Prediction with Graph-Structured Feedback

Hajihashemi, Shen
Online conformal prediction has demonstrated its capability to construct a prediction set for each incoming data point that covers the true label with a predetermined probability. To cope with potential distribution shift, multi-model online conformal prediction has been introduced to select and leverage different models from a preselected candidate set. Along with the improved flexibility, the choice of the preselected set also brings challenges. A candidate set that includes a large number of models may increase the computational complexity. In addition, the inclusion of irrelevant models with poor performance may negatively impact the performance and lead to unnecessarily large prediction sets. To address these challenges, we propose a novel multi-model online conformal prediction algorithm that identifies a subset of effective models at each time step by collecting feedback from a bipartite graph, which is refined upon receiving new data. A model is then selected from this subset to construct the prediction set, resulting in reduced computational complexity and smaller prediction sets. Additionally, we demonstrate that using prediction set size as feedback, alongside model loss, can significantly improve efficiency by constructing smaller prediction sets while still satisfying the required coverage guarantee. The proposed algorithms are proven to ensure valid coverage and achieve sublinear regret. Experiments on real and synthetic datasets validate that the proposed methods construct smaller prediction sets and outperform existing multi-model online conformal prediction approaches.
academic

बहु-मॉडल ऑनलाइन कनफॉर्मल प्रेडिक्शन ग्राफ-संरचित प्रतिक्रिया के साथ

मूल जानकारी

  • पेपर ID: 2506.20898
  • शीर्षक: Multi-model Online Conformal Prediction with Graph-Structured Feedback
  • लेखक: Erfan Hajihashemi, Yanning Shen (University of California, Irvine)
  • वर्गीकरण: cs.LG
  • प्रकाशन समय/सम्मेलन: Transactions on Machine Learning Research (10/2025)
  • पेपर लिंक: https://arxiv.org/abs/2506.20898

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

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

मुख्य योगदान

  1. GMOCP एल्गोरिदम प्रस्तावित किया: ग्राफ-संरचित प्रतिक्रिया के आधार पर बहु-मॉडल ऑनलाइन कनफॉर्मल प्रेडिक्शन एल्गोरिदम डिज़ाइन किया, द्विपक्षीय ग्राफ के माध्यम से प्रभावी मॉडल के सबसेट की गतिशील पहचान
  2. स्व-अनुकूल ग्राफ जनरेशन फ्रेमवर्क का निर्माण: मॉडल के ऑनलाइन चयन को सक्षम करते हुए, मॉडल के ऐतिहासिक प्रदर्शन के आधार पर द्विपक्षीय ग्राफ को गतिशील रूप से निर्माण और अपडेट करना
  3. EGMOCP विस्तार एल्गोरिदम विकसित किया: प्रेडिक्शन सेट आकार को अतिरिक्त प्रतिक्रिया संकेत के रूप में उपयोग करना, प्रेडिक्शन दक्षता को और बढ़ाना
  4. सैद्धांतिक गारंटी प्रदान की: एल्गोरिदम की वैध कवरेज दर और उप-रैखिक खेद सीमा सिद्ध की
  5. कई डेटासेट पर प्रभावशीलता सत्यापित की: CIFAR-10C, CIFAR-100C आदि डेटासेट पर छोटे प्रेडिक्शन सेट और कम कम्प्यूटेशनल जटिलता प्राप्त की

विधि विवरण

कार्य परिभाषा

ऐतिहासिक डेटा {(Xτ,Yτtrue)}τ=1t−1\{(X_τ, Y^{true}_τ)\}^{t-1}_{τ=1} और नई इनपुट XtX_t दी गई है, प्रेडिक्शन सेट Cαm(Xt)⊆YC^m_α(X_t) ⊆ Y का निर्माण करें ताकि सही लेबल YttrueY^{true}_t संभावना 1−α1-α के साथ प्रेडिक्शन सेट में समाहित हो, जहाँ αα गलत कवरेज संभावना है।

मॉडल आर्किटेक्चर

1. द्विपक्षीय ग्राफ संरचना डिज़ाइन

  • मॉडल नोड्स: {v1(l),...,vM(l)}\{v^{(l)}_1, ..., v^{(l)}_M\} M उम्मीदवार मॉडल का प्रतिनिधित्व करते हैं
  • चयन नोड्स: {v1(s),...,vJ(s)}\{v^{(s)}_1, ..., v^{(s)}_J\} J चयन नोड्स का प्रतिनिधित्व करते हैं
  • कनेक्शन बाधा: प्रत्येक चयन नोड अधिकतम N मॉडल नोड्स से जुड़ा हो सकता है

2. ग्राफ जनरेशन एल्गोरिदम

मॉडल नोड कनेक्शन संभावना: ptm=(1−ηe)wtm∑mˉ=1Mwtmˉ+ηeMp^m_t = (1 - η_e) \frac{w^m_t}{\sum^M_{\bar{m}=1} w^{\bar{m}}_t} + \frac{η_e}{M}

जहाँ ηeη_e अन्वेषण गुणांक है, wtmw^m_t मॉडल वजन है।

3. मॉडल वजन अपडेट

महत्व नमूनाकरण हानि अनुमान का उपयोग: wt+1m=wtmexp⁡(−εltm/2b)w^m_{t+1} = w^m_t \exp(-ε l^m_t / 2^b)

जहाँ हानि फ़ंक्शन है: ltm=L(αˉtm,αtm)qtmI{m∈St}l^m_t = \frac{L(\bar{α}^m_t, α^m_t)}{q^m_t} I\{m ∈ S_t\}

4. अनुकूली गलत कवरेज संभावना अपडेट

Scale-Free ऑनलाइन ग्रेडिएंट डिसेंट का उपयोग: αt+1m=αtm−η∇αtmL(αˉtm,αtm)∑τ=1t∥∇ατmL(αˉτm,ατm)∥22α^m_{t+1} = α^m_t - η \frac{∇_{α^m_t} L(\bar{α}^m_t, α^m_t)}{\sqrt{\sum^t_{τ=1} \|∇_{α^m_τ} L(\bar{α}^m_τ, α^m_τ)\|^2_2}}

तकनीकी नवाचार बिंदु

  1. ग्राफ संरचना प्रतिक्रिया तंत्र: द्विपक्षीय ग्राफ के माध्यम से मॉडल के सबसेट का गतिशील चयन, सभी मॉडल के अपडेट से बचना
  2. दोहरी प्रतिक्रिया डिज़ाइन: EGMOCP प्रेडिक्शन हानि और प्रेडिक्शन सेट आकार दोनों को प्रतिक्रिया संकेत के रूप में विचार करता है
  3. अनुकूली अन्वेषण-शोषण संतुलन: विभिन्न अन्वेषण गुणांकों के माध्यम से बहु-स्तरीय अन्वेषण रणनीति का कार्यान्वयन

प्रयोग सेटअप

डेटासेट

  1. CIFAR-10C/CIFAR-100C: 15 प्रकार की भ्रष्टता, 5 गंभीरता स्तर
  2. TinyImageNet-C: 200 वर्गों का भ्रष्ट संस्करण डेटासेट
  3. सिंथेटिक डेटासेट: 3000 नमूने, 20 वर्ग, वितरण बदलाव का अनुकरण

मूल्यांकन मेट्रिक्स

  • कवरेज: प्रेडिक्शन सेट में सही लेबल शामिल होने का प्रतिशत
  • औसत चौड़ाई: प्रेडिक्शन सेट का औसत आकार
  • रन टाइम: एल्गोरिदम का चलने का समय
  • एकल चौड़ाई: आकार 1 और सही कवरेज वाले प्रेडिक्शन सेट का प्रतिशत

तुलनात्मक विधियाँ

  • MOCP: बहु-मॉडल ऑनलाइन कनफॉर्मल प्रेडिक्शन आधार विधि
  • COMA: कनफॉर्मल ऑनलाइन मॉडल एकीकरण विधि
  • एकल-मॉडल विधियाँ: ACI, FACI, DECAY, SAOCP

कार्यान्वयन विवरण

  • लक्ष्य कवरेज दर: 90% (α = 0.1)
  • हाइपरपैरामीटर: ε = 0.5, η = 0.05, β = 0.05
  • समय चरण: T = 6000
  • बैच आकार: 500 नमूने

प्रयोग परिणाम

मुख्य परिणाम

CIFAR-100C डेटासेट पर अचानक वितरण बदलाव प्रयोग में:

  • GMOCP MOCP की तुलना में तेजी से रन टाइम (लगभग 50% सुधार) और समान प्रेडिक्शन सेट आकार प्राप्त करता है
  • EGMOCP प्रेडिक्शन सेट आकार को काफी कम करता है, MOCP के 12.63 से 6.18 तक, 90% लक्ष्य कवरेज दर बनाए रखते हुए
  • एकल चौड़ाई अनुपात 22.43% से 29.91% तक बढ़ता है

विलोपन प्रयोग

  1. ग्राफ पैरामीटर प्रभाव: N (मॉडल नोड्स संख्या) और J (चयन नोड्स संख्या) के विभिन्न संयोजन का परीक्षण
  2. अन्वेषण रणनीति: विभिन्न अन्वेषण गुणांक सेटिंग के प्रभाव की तुलना
  3. प्रतिक्रिया तंत्र: प्रेडिक्शन सेट आकार प्रतिक्रिया की प्रभावशीलता सत्यापित करना

केस विश्लेषण

DenseNet121 के तीन प्रशिक्षण कॉन्फ़िगरेशन (120D, 10R, 1R) के माध्यम से प्रदर्शन:

  • उच्च प्रदर्शन मॉडल (120D) सर्वोच्च वजन और चयन संभावना प्राप्त करते हैं
  • EGMOCP प्रभावी रूप से बेहतर प्रदर्शन वाले मॉडल की पहचान कर सकता है और उनका चयन कर सकता है
  • प्रेडिक्शन सेट आकार मॉडल प्रदर्शन के साथ नकारात्मक रूप से संबंधित है

प्रयोग निष्कर्ष

  1. कम्प्यूटेशनल दक्षता सुधार: GMOCP की प्रति-चरण जटिलता O(Nt + JMN) है, जो N << M होने पर MOCP के O(Mt) की तुलना में काफी कम है
  2. प्रेडिक्शन गुणवत्ता सुधार: EGMOCP दोहरी प्रतिक्रिया तंत्र के माध्यम से छोटे प्रेडिक्शन सेट प्राप्त करता है
  3. मजबूती सत्यापन: विभिन्न वितरण बदलाव परिदृश्यों में स्थिर प्रदर्शन बनाए रखता है

संबंधित कार्य

  1. कनफॉर्मल प्रेडिक्शन आधार: Vovk आदि के शास्त्रीय ढांचे पर आधारित, ऑनलाइन वातावरण में विस्तारित
  2. अनुकूली कनफॉर्मल प्रेडिक्शन: Gibbs & Candès की समय-परिवर्तनशील गलत कवरेज संभावना विधि
  3. बहु-मॉडल विधियाँ: Hajihashemi & Shen, Gasparin & Ramdas के कार्य के साथ तुलना
  4. ऑनलाइन लर्निंग सिद्धांत: विशेषज्ञ लर्निंग और बहु-सशस्त्र दस्यु के विचारों से उधार

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. ग्राफ संरचना प्रतिक्रिया तंत्र कम्प्यूटेशनल जटिलता को प्रभावी रूप से कम कर सकता है और प्रेडिक्शन दक्षता में सुधार कर सकता है
  2. प्रेडिक्शन सेट आकार को प्रतिक्रिया संकेत के रूप में उपयोग करना एल्गोरिदम प्रदर्शन में काफी सुधार करता है
  3. सैद्धांतिक गारंटी और प्रयोग परिणाम सुसंगत हैं, विधि की प्रभावशीलता सत्यापित करते हैं

सीमाएँ

  1. ग्राफ निर्माण को अतिरिक्त हाइपरपैरामीटर ट्यूनिंग की आवश्यकता होती है
  2. जब उम्मीदवार मॉडल की गुणवत्ता समान हो तो सुधार सीमित है
  3. सैद्धांतिक विश्लेषण विशिष्ट हानि फ़ंक्शन धारणा पर आधारित है

भविष्य की दिशाएँ

  1. अधिक जटिल ग्राफ संरचना और अपडेट रणनीति का अन्वेषण
  2. प्रतिगमन कार्यों और अन्य अनिश्चितता परिमाणीकरण विधियों तक विस्तार
  3. मजबूत वितरण बदलाव के तहत अनुकूलन का अनुसंधान

गहन मूल्यांकन

शक्तियाँ

  1. विधि नवाचार मजबूत: ग्राफ संरचना प्रतिक्रिया तंत्र बहु-मॉडल चयन के लिए नई सोच प्रदान करता है
  2. सैद्धांतिक आधार ठोस: कवरेज दर और खेद सीमा के कठोर प्रमाण प्रदान करता है
  3. प्रयोग डिज़ाइन व्यापक: कई डेटासेट और वितरण बदलाव परिदृश्य शामिल करता है
  4. व्यावहारिक मूल्य उच्च: कम्प्यूटेशनल जटिलता को काफी कम करते हुए प्रेडिक्शन गुणवत्ता में सुधार करता है

कमियाँ

  1. हाइपरपैरामीटर संवेदनशीलता: कई ग्राफ-संबंधित पैरामीटर को समायोजित करने की आवश्यकता
  2. अनुप्रयोग परिदृश्य सीमा: जब मॉडल गुणवत्ता में अंतर बड़ा न हो तो लाभ स्पष्ट नहीं
  3. सैद्धांतिक विश्लेषण जटिल: प्रमाण प्रक्रिया जटिल है, व्यावहारिक प्रयोज्यता सत्यापन की प्रतीक्षा में है

प्रभाव

  1. शैक्षणिक योगदान: ऑनलाइन अनिश्चितता परिमाणीकरण क्षेत्र के लिए नई तकनीकी दिशा प्रदान करता है
  2. अनुप्रयोग संभावना: वास्तविक समय निर्णय की आवश्यकता वाली सुरक्षा-महत्वपूर्ण प्रणालियों में महत्वपूर्ण मूल्य
  3. पुनरुत्पादनीयता: एल्गोरिदम विवरण विस्तृत है, प्रयोग सेटअप स्पष्ट है

अनुप्रयोग परिदृश्य

  1. वास्तविक समय अनिश्चितता परिमाणीकरण की आवश्यकता वाली ऑनलाइन लर्निंग प्रणालियाँ
  2. वितरण बदलाव का सामना करने वाले गतिशील वातावरण
  3. कम्प्यूटेशनल संसाधन सीमित लेकिन बहु-मॉडल संलयन की आवश्यकता वाले परिदृश्य
  4. सुरक्षा-महत्वपूर्ण अनुप्रयोगों में विश्वसनीय प्रेडिक्शन आवश्यकता

संदर्भ

  1. Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world
  2. Gibbs, I., & Candès, E. J. (2021). Adaptive conformal inference under distribution shift
  3. Hajihashemi, E., & Shen, Y. (2024). Multi-model ensemble conformal prediction in dynamic environments
  4. Gasparin, M., & Ramdas, A. (2024). Conformal online model aggregation