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

বহু-মডেল অনলাইন কনফরমাল প্রেডিকশন গ্রাফ-স্ট্রাকচার্ড ফিডব্যাক সহ

মৌলিক তথ্য

  • পেপার আইডি: 2506.20898
  • শিরোনাম: Multi-model Online Conformal Prediction with Graph-Structured Feedback
  • লেখক: Erfan Hajihashemi, Yanning Shen (ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়, আরভাইন)
  • শ্রেণীবিভাগ: 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. স্ব-অভিযোজিত অ-কভারেজ সম্ভাবনা আপডেট

স্কেল-মুক্ত অনলাইন গ্রেডিয়েন্ট ডিসেন্ট ব্যবহার করা: α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