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

बजटबद्ध बहु-विशेषज्ञ स्थगन

मूल जानकारी

  • पेपर ID: 2510.26706
  • शीर्षक: Budgeted Multiple-Expert Deferral (बजटबद्ध बहु-विशेषज्ञ स्थगन)
  • लेखक: Giulia DeSalvo (Google DeepMind), Clara Mohri (Harvard University), Mehryar Mohri (Google Research & Courant Institute), Yutao Zhong (Google Research)
  • वर्गीकरण: cs.LG, stat.ML
  • प्रकाशन समय: 30 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.26706

सारांश

अनिश्चित भविष्यवाणियों को महंगे विशेषज्ञों को स्थगित करना सीखना मशीन लर्निंग प्रणालियों की सटीकता और दक्षता में सुधार का एक शक्तिशाली रणनीति है। हालांकि, मानक स्थगन एल्गोरिदम प्रशिक्षण प्रक्रिया आमतौर पर प्रत्येक प्रशिक्षण उदाहरण के लिए सभी विशेषज्ञों को क्वेरी करने की आवश्यकता होती है, जब विशेषज्ञ क्वेरी महत्वपूर्ण कम्प्यूटेशनल या संसाधन लागत उत्पन्न करते हैं, तो यह विधि अत्यंत महंगी हो जाती है, जो स्थगन के मूल उद्देश्य का उल्लंघन करती है: अनावश्यक विशेषज्ञ उपयोग को सीमित करना। इस चुनौती को दूर करने के लिए, यह पेपर बजटबद्ध स्थगन ढांचा प्रस्तुत करता है, जिसका उद्देश्य प्रशिक्षण के दौरान विशेषज्ञ क्वेरी लागत को कम करते हुए प्रभावी स्थगन एल्गोरिदम को प्रशिक्षित करना है।

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

समस्या परिभाषा

पारंपरिक बहु-विशेषज्ञ स्थगन सीखना (Learning to Defer) एक मौलिक विरोधाभास का सामना करता है:

  1. मूल उद्देश्य: भविष्यवाणी कार्यों को चुनिंदा रूप से विशेषज्ञों को स्थगित करके लागत को कम करना
  2. प्रशिक्षण वास्तविकता: मानक प्रशिक्षण प्रक्रिया प्रत्येक प्रशिक्षण नमूने के लिए सभी विशेषज्ञों को क्वेरी करने की लागत की आवश्यकता होती है, कुल लागत neT है (विशेषज्ञ संख्या × प्रशिक्षण नमूने)
  3. लागत विरोधाभास: प्रशिक्षण प्रक्रिया स्वयं लागत नियंत्रण के इरादे का उल्लंघन करती है

अनुसंधान महत्व

  • व्यावहारिक अनुप्रयोग की आवश्यकता: बड़े भाषा मॉडल, मानव विशेषज्ञ आदि महंगे संसाधनों वाले परिदृश्यों में, प्रशिक्षण लागत अत्यंत अधिक हो सकती है
  • स्केलेबिलिटी समस्या: विशेषज्ञों की संख्या बढ़ने के साथ, प्रशिक्षण लागत रैखिक रूप से बढ़ती है, जो विधि की व्यावहारिकता को सीमित करती है
  • संसाधन-बाधित वातावरण: कम्प्यूटेशनल संसाधनों से सीमित वातावरण में, मौजूदा विधियों को तैनात करना कठिन है

मौजूदा विधियों की सीमाएं

  1. पूर्ण-क्वेरी धारणा: मौजूदा विधियां मानती हैं कि सभी विशेषज्ञों की भविष्यवाणियों और लागत जानकारी को बिना लागत के प्राप्त किया जा सकता है
  2. सिद्धांत और व्यवहार का अलगाव: सैद्धांतिक विश्लेषण प्रशिक्षण चरण की क्वेरी लागत को नजरअंदाज करता है
  3. खराब विस्तारशीलता: बड़े पैमाने पर विशेषज्ञ सेट को प्रभावी ढंग से संभालने में असमर्थ

मूल योगदान

  1. बजटबद्ध स्थगन ढांचा प्रस्तुत करना: प्रशिक्षण के दौरान विशेषज्ञ क्वेरी लागत नियंत्रण समस्या का पहली बार व्यवस्थित अध्ययन
  2. दो-चरणीय एल्गोरिदम डिजाइन:
    • दो-चरणीय बजटबद्ध स्थगन एल्गोरिदम (खंड 3-5)
    • एक-चरणीय बजटबद्ध स्थगन एल्गोरिदम (परिशिष्ट E)
  3. सैद्धांतिक गारंटियां:
    • सामान्यीकरण सीमा: मानक विधि के बराबर प्रदर्शन गारंटी
    • लेबल जटिलता: प्राप्य मामले में O(T) से Õ(√T) तक कम, आगे O(log T) तक पहुंच सकता है
  4. प्रयोगात्मक सत्यापन: कई डेटासेट पर 40% से कम विशेषज्ञ क्वेरी दर प्राप्त करते हुए भविष्यवाणी सटीकता बनाए रखना

विधि विवरण

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

दो-चरणीय सेटिंग:

  • इनपुट स्पेस: 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}

मूल एल्गोरिदम आर्किटेक्चर

एल्गोरिदम 1: बजटबद्ध दो-चरणीय स्थगन एल्गोरिदम

मुख्य नवाचार: निर्णय को दो भागों में विघटित करना

  1. विशेषज्ञ चयन: संभावना qₜ,ₖ के साथ विशेषज्ञ k चुनना
  2. क्वेरी निर्णय: संभावना pₜ,ₖ के साथ चयनित विशेषज्ञ की लागत को क्वेरी करना

एल्गोरिदम प्रवाह:

t = 1 से T के लिए:
    (xₜ, yₜ) प्राप्त करें
    क्वेरी संभावना वेक्टर pₜ ← SAMPLING-PROBS(...) की गणना करें
    विशेषज्ञ kₜ ~ q_t चुनें
    संभावना pₜ,ₖₜ के साथ लागत cₜ,ₖₜ को क्वेरी करें
    प्रशिक्षण सेट Sₜ को अपडेट करें (महत्व भार 1/(qₜ,ₖₜpₜ,ₖₜ) के साथ)
    रूटिंग फ़ंक्शन rₜ को अपडेट करें

एल्गोरिदम 2: SAMPLING-PROBS उप-प्रोग्राम

संस्करण स्पेस रखरखाव:

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

क्वेरी संभावना गणना:

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

डिजाइन दर्शन: वर्तमान संस्करण स्पेस में सबसे बड़े विसंगति वाले विशेषज्ञ-उदाहरण जोड़ी को प्राथमिकता देना

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

  1. अनुकूली क्वेरी रणनीति: परिकल्पना विसंगति के आधार पर गतिशील रूप से क्वेरी संभावना को समायोजित करना
  2. महत्व-भारित अनुमान: 1/(qₜ,ₖpₜ,ₖ) भार के माध्यम से निष्पक्ष अनुमान सुनिश्चित करना
  3. संस्करण स्पेस प्रूनिंग: क्रमिक रूप से उप-इष्टतम परिकल्पनाओं को समाप्त करना, उच्च अनिश्चितता क्षेत्रों पर ध्यान केंद्रित करना
  4. सैद्धांतिक उपकरण विस्तार:
    • ढलान असमरूपता (Slope Asymmetry)
    • परिकल्पना दूरी मेट्रिक
    • सामान्यीकृत विसंगति गुणांक

सैद्धांतिक विश्लेषण

सामान्यीकरण गारंटियां

प्रमेय 1 (दो-चरणीय सामान्यीकरण सीमा): कम से कम 1-δ की संभावना के साथ, सीखी गई परिकल्पना rₜ संतुष्ट करती है:

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

जहां Δₜ = √(q²·8/t·log(2t(t+1)|R|²/δ)), q = 1/q_min + 1

लेबल जटिलता

प्रमेय 6 (लेबल जटिलता सीमा): अपेक्षित क्वेरी संख्या की ऊपरी सीमा है:

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

मुख्य सुधार:

  • प्राप्य मामला: O(neT) से Õ(√T) तक
  • Freedman असमानता का उपयोग करके आगे O(log T) तक पहुंच सकता है

प्रयोगात्मक सेटअप

डेटासेट

10 बेंचमार्क डेटासेट का उपयोग:

  • द्विआधारी वर्गीकरण: 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 नियमितकरण)
  • हानि फ़ंक्शन: बहुपद लॉजिस्टिक हानि
  • प्रयोग दोहराव: प्रत्येक डेटासेट के लिए 5 यादृच्छिक विभाजन

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

मुख्य परिणाम

क्वेरी दक्षता:

  • द्विआधारी वर्गीकरण डेटासेट: क्वेरी दर 35-40% तक कम
  • बहु-वर्गीकरण डेटासेट: क्वेरी दर 30% से कम
  • विशेषज्ञ संख्या प्रभाव: विशेषज्ञ जितने अधिक, दक्षता सुधार उतना अधिक (letter डेटासेट 26 विशेषज्ञों के साथ सर्वश्रेष्ठ)

सटीकता संरक्षण:

  • सभी डेटासेट पर प्रणाली सटीकता मानक विधि के बराबर है
  • द्विआधारी वर्गीकरण डेटासेट पर त्रुटि पट्टियां बेहद छोटी हैं, परिणाम स्थिरता दर्शाती हैं
  • बहु-वर्गीकरण डेटासेट में कुछ उतार-चढ़ाव है, लेकिन समग्र प्रवृत्ति सुसंगत है

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

  1. स्केलेबिलिटी सत्यापन: विशेषज्ञों की संख्या बढ़ने के साथ, बजटबद्ध विधि का लाभ अधिक स्पष्ट हो जाता है
  2. स्थिरता विश्लेषण: ऑनलाइन सीखने की प्रक्रिया में "कंपन" एल्गोरिदम की यादृच्छिकता का सामान्य प्रदर्शन है
  3. सैद्धांतिक सत्यापन: प्रयोगात्मक परिणाम सैद्धांतिक विश्लेषण में मुख्य घटकों (θ, Kℓ, E*) के सीमित प्रभाव का समर्थन करते हैं

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

स्थगन सीखने का क्षेत्र

  • एक-चरणीय विधियां: Mozannar & Sontag (2020), Verma & Nalisnick (2022)
  • बहु-चरणीय विधियां: Mao et al. (2023a), सुसंगतता गारंटी अनुसंधान
  • सैद्धांतिक विकास: H-सुसंगतता सीमाएं, Bayes सुसंगतता

सक्रिय सीखना

  • IWAL एल्गोरिदम: Beygelzimer et al. (2009) की महत्व-भारित सक्रिय सीखना
  • क्षेत्र सक्रिय सीखना: Cortes et al. (2019a,b, 2020)

बजटबद्ध-बाधित सीखना

  • Reid et al. (2024): एकल विशेषज्ञ मामले में संदर्भ बैंडिट दृष्टिकोण
  • सीमाएं: बहु-विशेषज्ञ तक विस्तार करना कठिन, धारणाएं बहुत कठोर हैं

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

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

  1. व्यवहार्यता प्रमाण: प्रशिक्षण लागत में भारी कमी करते हुए स्थगन एल्गोरिदम प्रदर्शन बनाए रखना संभव है
  2. सैद्धांतिक सफलता: बजटबद्ध स्थगन समस्या के लिए पहली बार कठोर सैद्धांतिक गारंटियां प्रदान करना
  3. व्यावहारिक मूल्य: संसाधन-सीमित वातावरण में स्थगन रणनीति को अधिक व्यवहार्य बनाना

सीमाएं

  1. विशेषज्ञ सेटिंग: प्रयोगों में विशेषज्ञ सेटिंग अपेक्षाकृत सरल है, वास्तविक अनुप्रयोग में विशेषज्ञ अधिक जटिल हो सकते हैं
  2. लागत फ़ंक्शन: मुख्य रूप से 0-1 हानि पर विचार करता है, अन्य लागत संरचनाओं को आगे सत्यापन की आवश्यकता है
  3. परिकल्पना वर्ग सीमा: सैद्धांतिक विश्लेषण सीमित परिकल्पना वर्ग पर आधारित है, अनंत परिकल्पना वर्ग को कवरिंग संख्या विश्लेषण की आवश्यकता है

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

  1. अनुकूली क्वेरी रणनीति: प्रशिक्षण नमूनों के बीच संरचना जानकारी का उपयोग करना
  2. गतिशील विशेषज्ञ उपलब्धता: विशेषज्ञ गतिशील परिवर्तन के परिदृश्यों को संभालना
  3. सुदृढ़ीकरण सीखना एकीकरण: अनुक्रमिक या इंटरैक्टिव निर्णय परिदृश्यों के लिए

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

शक्तियां

  1. समस्या महत्व: स्थगन सीखने में एक मौलिक व्यावहारिक समस्या को हल करना
  2. सैद्धांतिक कठोरता: सामान्यीकरण सीमा और लेबल जटिलता सहित पूर्ण सैद्धांतिक विश्लेषण ढांचा प्रदान करना
  3. एल्गोरिदम नवाचार: सक्रिय सीखने के विचारों को चतुराई से स्थगन सीखने के परिदृश्य में अनुकूलित करना
  4. प्रयोगात्मक पूर्णता: कई डेटासेट पर विधि की प्रभावशीलता को सत्यापित करना

कमियां

  1. प्रयोगात्मक सेटअप सीमा: विशेषज्ञ सेटिंग अपेक्षाकृत कृत्रिम है, वास्तविक अनुप्रयोग परिदृश्य से भिन्न हो सकता है
  2. तुलनात्मक आधार एकल: मुख्य रूप से मानक स्थगन विधि के साथ तुलना, अन्य बजटबद्ध-बाधित विधियों की तुलना की कमी
  3. कम्प्यूटेशनल जटिलता विश्लेषण अपर्याप्त: एल्गोरिदम की कम्प्यूटेशनल ओवरहेड का विस्तार से विश्लेषण नहीं किया गया

प्रभाव

  1. शैक्षणिक योगदान: स्थगन सीखने के क्षेत्र में नई अनुसंधान दिशा खोलना
  2. व्यावहारिक मूल्य: महंगे विशेषज्ञों वाले वास्तविक अनुप्रयोगों के लिए महत्वपूर्ण महत्व
  3. सैद्धांतिक मूल्य: सक्रिय सीखने के सिद्धांत को नए अनुप्रयोग परिदृश्य तक विस्तारित करना

लागू परिदृश्य

  1. बड़े भाषा मॉडल स्थगन: विभिन्न आकार के LLM के बीच लागत-संवेदनशील स्थगन निर्णय
  2. चिकित्सा निदान प्रणाली: विभिन्न विशेषज्ञ डॉक्टरों के बीच निदान कार्य आवंटन
  3. सेंसर नेटवर्क: विभिन्न क्षमता वाले सेंसर के बीच डेटा संग्रह निर्णय

संदर्भ

यह पेपर स्थगन सीखना, सक्रिय सीखना और बहु-सशस्त्र दस्यु आदि क्षेत्रों के महत्वपूर्ण साहित्य का हवाला देता है, विशेष रूप से:

  • Mao et al. (2023a, 2024a): बहु-विशेषज्ञ स्थगन का सैद्धांतिक आधार
  • Beygelzimer et al. (2009): IWAL एल्गोरिदम के महत्व-भारित विचार
  • Reid et al. (2024): बजटबद्ध-बाधित स्थगन का अग्रदूत कार्य

समग्र मूल्यांकन: यह मशीन लर्निंग सिद्धांत का एक उच्च-गुणवत्ता वाला पेपर है जो स्थगन सीखने में एक महत्वपूर्ण व्यावहारिक समस्या को हल करता है, कठोर सैद्धांतिक विश्लेषण और प्रेरक प्रयोगात्मक सत्यापन प्रदान करता है। पेपर का मुख्य योगदान प्रशिक्षण चरण के दौरान विशेषज्ञ क्वेरी लागत नियंत्रण समस्या का पहली बार व्यवस्थित अध्ययन करना है, जो इस क्षेत्र के व्यावहारिक अनुप्रयोग के लिए एक महत्वपूर्ण आधार स्थापित करता है।