2025-11-11T14:19:08.761279

Budgeted Multiple-Expert Deferral

DeSalvo, Mohri, Mohri et al.

Learning to defer uncertain predictions to costly experts offers a powerful strategy for improving the accuracy and efficiency of machine learning systems. However, standard training procedures for deferral algorithms typically require querying all experts for every training instance, an approach that becomes prohibitively expensive when expert queries incur significant computational or resource costs. This undermines the core goal of deferral: to limit unnecessary expert usage. To overcome this challenge, we introduce the budgeted deferral framework, which aims to train effective deferral algorithms while minimizing expert query costs during training. We propose new algorithms for both two-stage and single-stage multiple-expert deferral settings that selectively query only a subset of experts per training example. While inspired by active learning, our setting is fundamentally different: labels are already known, and the core challenge is to decide which experts to query in order to balance cost and predictive performance. We establish theoretical guarantees for both of our algorithms, including generalization bounds and label complexity analyses. Empirical results across several domains show that our algorithms substantially reduce training costs without sacrificing prediction accuracy, demonstrating the practical value of our budget-aware deferral algorithms.

academic

বাজেটকৃত মাল্টি-এক্সপার্ট ডেফারেল

মৌলিক তথ্য

পেপার আইডি: 2510.26706
শিরোনাম: Budgeted Multiple-Expert Deferral
লেখক: গিউলিয়া ডিসালভো (গুগল ডিপমাইন্ড), ক্লারা মোহরি (হার্ভার্ড বিশ্ববিদ্যালয়), মেহরিয়ার মোহরি (গুগল রিসার্চ ও কুরান্ট ইনস্টিটিউট), ইউতাও ঝং (গুগল রিসার্চ)
শ্রেণীবিভাগ: cs.LG, stat.ML
প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ৩০ (arXiv প্রাক-প্রিন্ট)
পেপার লিঙ্ক: https://arxiv.org/abs/2510.26706

সারসংক্ষেপ

অনিশ্চিত পূর্বাভাসগুলি ব্যয়বহুল বিশেষজ্ঞদের কাছে স্থগিত করতে শেখা মেশিন লার্নিং সিস্টেমের নির্ভুলতা এবং দক্ষতা উন্নত করার একটি শক্তিশালী কৌশল। তবে, মান বিলম্ব অ্যালগরিদম প্রশিক্ষণ পদ্ধতি সাধারণত প্রতিটি প্রশিক্ষণ উদাহরণের জন্য সমস্ত বিশেষজ্ঞদের অনুসন্ধান করার প্রয়োজন, যখন বিশেষজ্ঞ অনুসন্ধান উল্লেখযোগ্য গণনামূলক বা সম্পদ খরচ তৈরি করে, এই পদ্ধতিটি অত্যন্ত ব্যয়বহুল হয়ে ওঠে এবং বিলম্বের মূল লক্ষ্যকে লঙ্ঘন করে: অপ্রয়োজনীয় বিশেষজ্ঞ ব্যবহার সীমাবদ্ধ করা। এই চ্যালেঞ্জ অতিক্রম করার জন্য, এই পেপারটি বাজেটকৃত বিলম্ব কাঠামো প্রবর্তন করে, যা প্রশিক্ষণের সময় বিশেষজ্ঞ অনুসন্ধান খরচ কমিয়ে দক্ষ বিলম্ব অ্যালগরিদম প্রশিক্ষণের লক্ষ্য রাখে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

ঐতিহ্যবাহী মাল্টি-এক্সপার্ট বিলম্ব শেখা (Learning to Defer) একটি মৌলিক বৈপরীত্যের সম্মুখীন হয়:

মূল উদ্দেশ্য: পূর্বাভাস কাজগুলি নির্বাচনীভাবে বিশেষজ্ঞদের কাছে স্থগিত করে খরচ হ্রাস করা
প্রশিক্ষণ বাস্তবতা: মান প্রশিক্ষণ পদ্ধতি প্রতিটি প্রশিক্ষণ নমুনার জন্য সমস্ত বিশেষজ্ঞের খরচ অনুসন্ধান করার প্রয়োজন, মোট খরচ neT (বিশেষজ্ঞ সংখ্যা × প্রশিক্ষণ নমুনা সংখ্যা)
খরচ প্যারাডক্স: প্রশিক্ষণ প্রক্রিয়া নিজেই খরচ নিয়ন্ত্রণের উদ্দেশ্যকে লঙ্ঘন করে

গবেষণার গুরুত্ব

ব্যবহারিক প্রয়োগের চাহিদা: বড় ভাষা মডেল, মানব বিশেষজ্ঞ ইত্যাদি ব্যয়বহুল সম্পদ জড়িত পরিস্থিতিতে, প্রশিক্ষণ খরচ অত্যন্ত বেশি হতে পারে
স্কেলেবিলিটি সমস্যা: বিশেষজ্ঞ সংখ্যা বৃদ্ধির সাথে সাথে প্রশিক্ষণ খরচ রৈখিকভাবে বৃদ্ধি পায়, পদ্ধতির ব্যবহারিকতা সীমাবদ্ধ করে
সম্পদ-সীমাবদ্ধ পরিবেশ: গণনামূলক সম্পদ সীমাবদ্ধ পরিবেশে, বিদ্যমান পদ্ধতি স্থাপন করা কঠিন

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

সম্পূর্ণ অনুসন্ধান অনুমান: বিদ্যমান পদ্ধতি সমস্ত বিশেষজ্ঞের পূর্বাভাস এবং খরচ তথ্য বিনামূল্যে পেতে পারে বলে অনুমান করে
তত্ত্ব এবং অনুশীলনের বিচ্ছিন্নতা: তাত্ত্বিক বিশ্লেষণ প্রশিক্ষণ পর্যায়ের অনুসন্ধান খরচ উপেক্ষা করে
দুর্বল সম্প্রসারণযোগ্যতা: বড় আকারের বিশেষজ্ঞ সেট কার্যকরভাবে পরিচালনা করতে পারে না

মূল অবদান

বাজেটকৃত বিলম্ব কাঠামো প্রস্তাব: প্রশিক্ষণের সময় বিশেষজ্ঞ অনুসন্ধান খরচ নিয়ন্ত্রণ সমস্যা প্রথমবারের মতো পদ্ধতিগতভাবে অধ্যয়ন করা
দ্বি-পর্যায়ের অ্যালগরিদম ডিজাইন:
- দ্বি-পর্যায়ের বাজেটকৃত বিলম্ব অ্যালগরিদম (বিভাগ ৩-৫)
- একক-পর্যায়ের বাজেটকৃত বিলম্ব অ্যালগরিদম (পরিশিষ্ট E)
তাত্ত্বিক গ্যারান্টি:
- সাধারণীকরণ সীমানা: মান পদ্ধতির সাথে তুলনীয় কর্মক্ষমতা গ্যারান্টি
- লেবেল জটিলতা: সম্ভাব্য ক্ষেত্রে O(T) থেকে Õ(√T) এ হ্রাস, আরও O(log T) এ পৌঁছাতে পারে
পরীক্ষামূলক যাচাইকরণ: একাধিক ডেটাসেটে ৪০% এর নিচে বিশেষজ্ঞ অনুসন্ধান হার অর্জন করে, পূর্বাভাস নির্ভুলতা বজায় রেখে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

দ্বি-পর্যায়ের সেটিং:

ইনপুট স্পেস: X, লেবেল স্পেস: Y = n
বিশেষজ্ঞ সেট: {g₁, ..., gₙₑ}, প্রতিটি বিশেষজ্ঞ gⱼ: X × Y → ℝ
রুটিং ফাংশন: r ∈ R, বিশেষজ্ঞ নির্বাচন করে r(x) = argmax_k r(x,k)
খরচ ফাংশন: cₖ(x,y), সাধারণত 0-1 ক্ষতি

উদ্দেশ্য: দ্বি-পর্যায়ের বিলম্ব ক্ষতি কমানো

L_def(r,x,y,c) = Σₖ cₖ(x,y)𝟙_{r(x)=k}

মূল অ্যালগরিদম আর্কিটেকচার

অ্যালগরিদম ১: বাজেটকৃত দ্বি-পর্যায়ের বিলম্ব অ্যালগরিদম

মূল উদ্ভাবন: সিদ্ধান্তকে দুটি অংশে বিভক্ত করা

বিশেষজ্ঞ নির্বাচন: সম্ভাবনা qₜ,ₖ দিয়ে বিশেষজ্ঞ k নির্বাচন করা
অনুসন্ধান সিদ্ধান্ত: সম্ভাবনা pₜ,ₖ দিয়ে নির্বাচিত বিশেষজ্ঞের খরচ অনুসন্ধান করা

অ্যালগরিদম প্রবাহ:

t = 1 থেকে T এর জন্য:
    (xₜ, yₜ) গ্রহণ করুন
    অনুসন্ধান সম্ভাবনা ভেক্টর pₜ ← SAMPLING-PROBS(...)
    বিশেষজ্ঞ kₜ ~ q_t নির্বাচন করুন
    সম্ভাবনা pₜ,ₖₜ দিয়ে খরচ cₜ,ₖₜ অনুসন্ধান করুন
    প্রশিক্ষণ সেট Sₜ আপডেট করুন (গুরুত্ব ওজন 1/(qₜ,ₖₜpₜ,ₖₜ) সহ)
    রুটিং ফাংশন rₜ আপডেট করুন

অ্যালগরিদম ২: SAMPLING-PROBS সাব-প্রোগ্রাম

সংস্করণ স্পেস রক্ষণাবেক্ষণ:

Rₜ₊₁ = {r ∈ Rₜ : Eₜ(r) ≤ E*ₜ + Δₜ}

অনুসন্ধান সম্ভাবনা গণনা:

pₜ,ₖ = max_{r,r'∈Rₜ} {ℓ(r,xₜ,k) - ℓ(r',xₜ,k)}

ডিজাইন দর্শন: বর্তমান সংস্করণ স্পেসে সর্বাধিক মতবিরোধ সহ বিশেষজ্ঞ-উদাহরণ জোড়াগুলিকে অগ্রাধিকার দিন

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

অভিযোজিত অনুসন্ধান কৌশল: অনুমান বিরোধের উপর ভিত্তি করে গতিশীলভাবে অনুসন্ধান সম্ভাবনা সামঞ্জস্য করা
গুরুত্ব ওজন অনুমান: 1/(qₜ,ₖpₜ,ₖ) ওজনের মাধ্যমে নিরপেক্ষ অনুমান নিশ্চিত করা
সংস্করণ স্পেস প্রুনিং: ক্রমান্বয়ে উপ-সর্বোত্তম অনুমান দূর করা, উচ্চ অনিশ্চয়তা অঞ্চলে ফোকাস করা
তাত্ত্বিক সরঞ্জাম সম্প্রসারণ:
- ঢাল অসমতা (Slope Asymmetry)
- অনুমান দূরত্ব মেট্রিক
- সাধারণীকৃত বিরোধ সহগ

তাত্ত্বিক বিশ্লেষণ

সাধারণীকরণ গ্যারান্টি

উপপাদ্য ১ (দ্বি-পর্যায়ের সাধারণীকরণ সীমানা): কমপক্ষে 1-δ সম্ভাবনার সাথে, শেখা অনুমান rₜ সন্তুষ্ট করে:

E(rₜ) - E(r*) ≤ 2Δₜ₋₁

যেখানে Δₜ = √(q²·8/t·log(2t(t+1)|R|²/δ)), q = 1/q_min + 1

লেবেল জটিলতা

উপপাদ্য ৬ (লেবেল জটিলতা সীমানা): প্রত্যাশিত অনুসন্ধান সংখ্যার উপরের সীমা:

4θ·Kℓ·(E*ₜ + O((1/q_min + 1)√T log(|R|T/δ)))

মূল উন্নতি:

সম্ভাব্য ক্ষেত্র: O(neT) থেকে Õ(√T) এ হ্রাস
Freedman অসমতা ব্যবহার করে আরও O(log T) এ পৌঁছানো যায়

পরীক্ষামূলক সেটআপ

ডেটাসেট

১০টি বেঞ্চমার্ক ডেটাসেট ব্যবহার করা হয়েছে:

দ্বি-শ্রেণী: cod-rna, covtype, HIGGS, phishing, shuttle, skin
বহু-শ্রেণী: connect, dna, letter, pendigits

বিশেষজ্ঞ সেটিং

বিশেষজ্ঞ সংখ্যা: শ্রেণী সংখ্যা n এর সমান
বিশেষজ্ঞ সংজ্ঞা: বিশেষজ্ঞ gₖ k-তম শ্রেণীতে সম্পূর্ণভাবে সঠিক, অন্যান্য শ্রেণীতে এলোমেলো পূর্বাভাস দেয়
খরচ ফাংশন: 0-1 ক্ষতি cₖ(x,y) = 𝟙_{gₖ(x)≠y}

মূল্যায়ন মেট্রিক্স

সিস্টেম নির্ভুলতা: পরীক্ষা সেটে 1 - L_def(h,x,y) এর গড় মান
অনুসন্ধান দক্ষতা: সংগৃহীত বিশেষজ্ঞ অনুসন্ধান সংখ্যা বনাম উপলব্ধ অনুসন্ধান সংখ্যা

বাস্তবায়ন বিবরণ

অনুমান শ্রেণী: লজিস্টিক রিগ্রেশন মডেল (L2 নিয়মিতকরণ)
ক্ষতি ফাংশন: বহুপদী লজিস্টিক ক্ষতি
পরীক্ষা পুনরাবৃত্তি: প্রতিটি ডেটাসেটে ৫টি এলোমেলো বিভাজন

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

অনুসন্ধান দক্ষতা:

দ্বি-শ্রেণী ডেটাসেট: অনুসন্ধান হার ৩৫-৪০% এ হ্রাস
বহু-শ্রেণী ডেটাসেট: অনুসন্ধান হার ৩০% এর নিচে
বিশেষজ্ঞ সংখ্যা প্রভাব: বিশেষজ্ঞ যত বেশি, দক্ষতা উন্নতি তত বেশি (letter ডেটাসেটে ২৬টি বিশেষজ্ঞ সহ সেরা ফলাফল)

নির্ভুলতা বজায় রাখা:

সমস্ত ডেটাসেটে সিস্টেম নির্ভুলতা মান পদ্ধতির সাথে তুলনীয়
দ্বি-শ্রেণী ডেটাসেটে ত্রুটি বার অত্যন্ত ছোট, ফলাফল স্থিতিশীলতা নির্দেশ করে
বহু-শ্রেণী ডেটাসেটে কিছু ওঠানামা আছে, কিন্তু সামগ্রিক প্রবণতা সামঞ্জস্যপূর্ণ

মূল আবিষ্কার

স্কেলেবিলিটি যাচাইকরণ: বিশেষজ্ঞ সংখ্যা বৃদ্ধির সাথে সাথে বাজেট পদ্ধতির সুবিধা আরও স্পষ্ট হয়ে ওঠে
স্থিতিশীলতা বিশ্লেষণ: অনলাইন শেখার প্রক্রিয়ায় "কম্পন" অ্যালগরিদম এলোমেলোতার স্বাভাবিক প্রকাশ
তাত্ত্বিক যাচাইকরণ: পরীক্ষামূলক ফলাফল তাত্ত্বিক বিশ্লেষণে মূল উপাদান (θ, Kℓ, E*) এর সীমিত প্রভাব সমর্থন করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

সম্ভাব্যতা প্রমাণ: প্রশিক্ষণ খরচ উল্লেখযোগ্যভাবে হ্রাস করার সময় বিলম্ব অ্যালগরিদম কর্মক্ষমতা বজায় রাখা সম্ভব
তাত্ত্বিক অগ্রগতি: বাজেটকৃত বিলম্ব সমস্যার জন্য প্রথমবারের মতো কঠোর তাত্ত্বিক গ্যারান্টি প্রদান করা
ব্যবহারিক মূল্য: সম্পদ-সীমাবদ্ধ পরিবেশে বিলম্ব কৌশল আরও কার্যকর করা

সীমাবদ্ধতা

বিশেষজ্ঞ সেটিং: পরীক্ষায় বিশেষজ্ঞ সেটিং তুলনামূলকভাবে সরলীকৃত, বাস্তব প্রয়োগে বিশেষজ্ঞ আরও জটিল হতে পারে
খরচ ফাংশন: প্রধানত 0-1 ক্ষতি বিবেচনা করা হয়, অন্যান্য খরচ কাঠামো আরও যাচাইকরণ প্রয়োজন
অনুমান শ্রেণী সীমাবদ্ধতা: তাত্ত্বিক বিশ্লেষণ সীমিত অনুমান শ্রেণীর উপর ভিত্তি করে, অসীম অনুমান শ্রেণীর জন্য কভারেজ সংখ্যা বিশ্লেষণ প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

অভিযোজিত অনুসন্ধান কৌশল: প্রশিক্ষণ নমুনার মধ্যে কাঠামো তথ্য ব্যবহার করা
গতিশীল বিশেষজ্ঞ উপলব্ধতা: বিশেষজ্ঞ গতিশীলভাবে পরিবর্তনশীল পরিস্থিতি পরিচালনা করা
শক্তিশালী শেখার একীকরণ: ক্রমিক বা ইন্টারেক্টিভ সিদ্ধান্ত পরিস্থিতির জন্য

গভীর মূল্যায়ন

শক্তি

সমস্যার গুরুত্ব: বিলম্ব শেখায় একটি মৌলিক ব্যবহারিক সমস্যা সমাধান করা
তাত্ত্বিক কঠোরতা: সাধারণীকরণ সীমানা এবং লেবেল জটিলতা সহ সম্পূর্ণ তাত্ত্বিক বিশ্লেষণ কাঠামো প্রদান করা
অ্যালগরিদম উদ্ভাবন: সক্রিয় শেখার ধারণাগুলি বিলম্ব শেখার পরিস্থিতিতে চতুরভাবে অভিযোজিত করা
পরীক্ষামূলক সম্পূর্ণতা: একাধিক ডেটাসেটে পদ্ধতির কার্যকারিতা যাচাই করা

অপূর্ণতা

পরীক্ষামূলক সেটআপ সীমাবদ্ধতা: বিশেষজ্ঞ সেটিং তুলনামূলকভাবে কৃত্রিম, বাস্তব প্রয়োগ পরিস্থিতির সাথে পার্থক্য থাকতে পারে
তুলনামূলক বেসলাইন একক: প্রধানত মান বিলম্ব পদ্ধতির সাথে তুলনা, অন্যান্য বাজেট-সীমাবদ্ধ পদ্ধতির তুলনা অনুপস্থিত
গণনামূলক জটিলতা বিশ্লেষণ অপর্যাপ্ত: অ্যালগরিদমের গণনামূলক ওভারহেড বিস্তারিতভাবে বিশ্লেষণ করা হয়নি

প্রভাব

একাডেমিক অবদান: বিলম্ব শেখার ক্ষেত্রে নতুন গবেষণা দিকনির্দেশনা খোলা
ব্যবহারিক মূল্য: ব্যয়বহুল বিশেষজ্ঞ জড়িত বাস্তব প্রয়োগের জন্য গুরুত্বপূর্ণ
তাত্ত্বিক মূল্য: সক্রিয় শেখার তত্ত্ব নতুন প্রয়োগ পরিস্থিতিতে সম্প্রসারণ করা

প্রযোজ্য পরিস্থিতি

বড় ভাষা মডেল বিলম্ব: বিভিন্ন আকারের LLM এর মধ্যে খরচ-সংবেদনশীল বিলম্ব সিদ্ধান্ত
চিকিৎসা নির্ণয় সিস্টেম: বিভিন্ন বিশেষজ্ঞ চিকিৎসকদের মধ্যে নির্ণয় কাজ বরাদ্দ করা
সেন্সর নেটওয়ার্ক: বিভিন্ন ক্ষমতার সেন্সরগুলির মধ্যে ডেটা সংগ্রহ সিদ্ধান্ত

সংদর্ভ

এই পেপারটি বিলম্ব শেখা, সক্রিয় শেখা এবং মাল্টি-আর্ম ব্যান্ডিট ইত্যাদি ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, বিশেষত:

Mao et al. (2023a, 2024a): মাল্টি-এক্সপার্ট বিলম্বের তাত্ত্বিক ভিত্তি
Beygelzimer et al. (2009): IWAL অ্যালগরিদমের গুরুত্ব-ওজন ধারণা
Reid et al. (2024): বাজেট-সীমাবদ্ধ বিলম্বের অগ্রদূত কাজ

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের মেশিন লার্নিং তাত্ত্বিক পেপার যা বিলম্ব শেখায় একটি গুরুত্বপূর্ণ ব্যবহারিক সমস্যা সমাধান করে, কঠোর তাত্ত্বিক বিশ্লেষণ এবং প্রভাবশালী পরীক্ষামূলক যাচাইকরণ প্রদান করে। পেপারের প্রধান অবদান প্রশিক্ষণ পর্যায়ে বিশেষজ্ঞ অনুসন্ধান খরচ নিয়ন্ত্রণ সমস্যা প্রথমবারের মতো পদ্ধতিগতভাবে অধ্যয়ন করা, এই ক্ষেত্রের ব্যবহারিক প্রয়োগের জন্য একটি গুরুত্বপূর্ণ ভিত্তি স্থাপন করা।