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
  • العنوان: الإحالة المتعددة للخبراء ذات الميزانية
  • المؤلفون: جوليا ديسالفو (Google DeepMind)، كلارا موهري (جامعة هارفارد)، مهريار موهري (Google Research & معهد كورانت)، يوتاو تشونج (Google Research)
  • التصنيف: cs.LG, stat.ML
  • تاريخ النشر: 30 أكتوبر 2025 (نسخة أولية على arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.26706

الملخص

يعتبر تعلم إحالة التنبؤات غير المؤكدة للخبراء المتخصصين المكلفين استراتيجية قوية لتحسين دقة وكفاءة أنظمة التعلم الآلي. ومع ذلك، فإن إجراءات التدريب القياسية للخوارزميات المعروفة عادة ما تتطلب الاستعلام عن جميع الخبراء لكل عينة تدريب، مما يصبح مكلفاً للغاية عندما تنتج استعلامات الخبراء تكاليف حسابية أو موارد كبيرة، مما يتعارض مع الهدف الأساسي للإحالة: تحديد استخدام الخبراء غير الضروري. للتغلب على هذا التحدي، تقدم هذه الورقة إطار عمل الإحالة ذات الميزانية، الذي يهدف إلى تدريب خوارزميات إحالة فعالة مع تقليل تكاليف استعلام الخبراء أثناء التدريب.

الخلفية البحثية والدافع

تعريف المشكلة

يواجه التعلم التقليدي للإحالة المتعددة للخبراء تناقضاً أساسياً:

  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. اختيار الخبير: اختيار الخبير k باحتمالية qₜ,ₖ
  2. قرار الاستعلام: الاستعلام عن تكلفة الخبير المختار باحتمالية pₜ,ₖ

تدفق الخوارزمية:

لـ t = 1 إلى T:
    استقبال (xₜ, yₜ)
    حساب متجه احتمالية الاستعلام pₜ ← SAMPLING-PROBS(...)
    اختيار الخبير kₜ ~ q_t
    الاستعلام عن التكلفة cₜ,ₖₜ باحتمالية pₜ,ₖₜ
    تحديث مجموعة التدريب 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. إحالة نموذج اللغة الكبيرة: اتخاذ قرارات إحالة حساسة للتكلفة بين نماذج لغة بأحجام مختلفة
  2. أنظمة التشخيص الطبي: توزيع مهام التشخيص بين أطباء متخصصين مختلفين
  3. شبكات الاستشعار: اتخاذ قرارات جمع البيانات بين أجهزة استشعار بقدرات مختلفة

المراجع

تستشهد هذه الورقة بأدبيات مهمة في مجالات التعلم بالإحالة والتعلم النشط وآلات القمار متعددة الأذرع، خاصة:

  • Mao et al. (2023a, 2024a): الأساس النظري للإحالة المتعددة للخبراء
  • Beygelzimer et al. (2009): فكرة الأهمية المرجحة في خوارزمية IWAL
  • Reid et al. (2024): العمل الرائد في الإحالة المقيدة بالميزانية

التقييم الشامل: هذه ورقة عالية الجودة في التعلم الآلي النظري، تحل مشكلة عملية مهمة في التعلم بالإحالة، وتوفر تحليلاً نظرياً صارماً والتحقق التجريبي المقنع. تكمن المساهمة الرئيسية للورقة في أول دراسة منهجية لمشكلة التحكم في تكاليف استعلام الخبراء أثناء التدريب، مما يضع أساساً مهماً للتطبيقات العملية في هذا المجال.