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

Rinvio Multiplo con Budget

Informazioni Fondamentali

  • ID Articolo: 2510.26706
  • Titolo: Budgeted Multiple-Expert Deferral
  • Autori: Giulia DeSalvo (Google DeepMind), Clara Mohri (Harvard University), Mehryar Mohri (Google Research & Courant Institute), Yutao Zhong (Google Research)
  • Classificazione: cs.LG, stat.ML
  • Data di Pubblicazione: 30 ottobre 2025 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2510.26706

Riassunto

Imparare a rinviare le previsioni incerte a esperti costosi è una strategia potente per migliorare l'accuratezza e l'efficienza dei sistemi di apprendimento automatico. Tuttavia, le procedure standard di addestramento degli algoritmi di rinvio richiedono tipicamente di interrogare tutti gli esperti per ogni istanza di addestramento, il che diventa estremamente costoso quando le interrogazioni degli esperti comportano costi computazionali o di risorse significativi, vanificando l'obiettivo fondamentale del rinvio: limitare l'uso non necessario degli esperti. Per superare questa sfida, il presente articolo introduce il framework di rinvio con budget, progettato per addestrare algoritmi di rinvio efficaci minimizzando contemporaneamente il costo delle interrogazioni degli esperti durante l'addestramento.

Contesto di Ricerca e Motivazione

Definizione del Problema

L'apprendimento tradizionale del rinvio multiplo (Learning to Defer) affronta una contraddizione fondamentale:

  1. Obiettivo Principale: ridurre i costi rinviando selettivamente i compiti di previsione agli esperti
  2. Realtà dell'Addestramento: le procedure standard richiedono il costo di interrogare tutti gli esperti per ogni campione di addestramento, con costo totale neT (numero di esperti × numero di campioni di addestramento)
  3. Paradosso dei Costi: il processo di addestramento stesso contraddice l'intento del controllo dei costi

Importanza della Ricerca

  • Esigenze Applicative Pratiche: in scenari che coinvolgono risorse costose come modelli linguistici di grandi dimensioni ed esperti umani, i costi di addestramento possono essere estremamente elevati
  • Problemi di Scalabilità: con l'aumento del numero di esperti, il costo di addestramento cresce linearmente, limitando l'applicabilità pratica del metodo
  • Ambienti con Risorse Vincolate: in ambienti con risorse computazionali limitate, i metodi esistenti sono difficili da implementare

Limitazioni dei Metodi Esistenti

  1. Assunzione di Interrogazione Completa: i metodi esistenti presuppongono di poter ottenere senza costi le previsioni e le informazioni di costo di tutti gli esperti
  2. Divario tra Teoria e Pratica: l'analisi teorica trascura i costi di interrogazione nella fase di addestramento
  3. Scarsa Estensibilità: non riescono a gestire efficacemente insiemi di esperti su larga scala

Contributi Principali

  1. Proposta del Framework di Rinvio con Budget: primo studio sistematico del controllo dei costi di interrogazione degli esperti durante l'addestramento
  2. Progettazione di Algoritmi a Due Stadi:
    • Algoritmo di rinvio con budget a due stadi (Sezioni 3-5)
    • Algoritmo di rinvio con budget a uno stadio (Appendice E)
  3. Garanzie Teoriche:
    • Limiti di Generalizzazione: garanzie di prestazione comparabili ai metodi standard
    • Complessità di Etichettatura: ridotta da O(T) a Õ(√T) nel caso realizzabile, ulteriormente a O(log T)
  4. Verifica Sperimentale: raggiungimento di tassi di interrogazione degli esperti inferiori al 40% su più set di dati, mantenendo l'accuratezza predittiva

Dettagli del Metodo

Definizione del Compito

Impostazione a Due Stadi:

  • Spazio di Input: X, Spazio di Etichette: Y = n
  • Insieme di Esperti: {g₁, ..., gₙₑ}, ogni esperto gⱼ: X × Y → ℝ
  • Funzione di Routing: r ∈ R, seleziona l'esperto r(x) = argmax_k r(x,k)
  • Funzione di Costo: cₖ(x,y), tipicamente perdita 0-1

Obiettivo: minimizzare la perdita di rinvio a due stadi

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

Architettura dell'Algoritmo Principale

Algoritmo 1: Algoritmo di Rinvio a Due Stadi con Budget

Innovazione Chiave: decomposizione della decisione in due parti

  1. Selezione dell'Esperto: selezione dell'esperto k con probabilità qₜ,ₖ
  2. Decisione di Interrogazione: interrogazione del costo dell'esperto selezionato con probabilità pₜ,ₖ

Flusso dell'Algoritmo:

per t = 1 a T:
    ricevi (xₜ, yₜ)
    calcola il vettore di probabilità di interrogazione pₜ ← SAMPLING-PROBS(...)
    seleziona l'esperto kₜ ~ q_t
    interroga il costo cₜ,ₖₜ con probabilità pₜ,ₖₜ
    aggiorna l'insieme di addestramento Sₜ (con pesi di importanza 1/(qₜ,ₖₜpₜ,ₖₜ))
    aggiorna la funzione di routing rₜ

Algoritmo 2: Sottoprogramma SAMPLING-PROBS

Mantenimento dello Spazio delle Versioni:

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

Calcolo della Probabilità di Interrogazione:

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

Filosofia di Progettazione: dare priorità all'interrogazione delle coppie esperto-istanza con il massimo disaccordo nello spazio delle versioni corrente

Punti di Innovazione Tecnica

  1. Strategia di Interrogazione Adattiva: regolazione dinamica delle probabilità di interrogazione basata sul disaccordo delle ipotesi
  2. Stima con Ponderazione di Importanza: garanzia di stima imparziale attraverso il peso 1/(qₜ,ₖpₜ,ₖ)
  3. Potatura dello Spazio delle Versioni: eliminazione progressiva di ipotesi subottimali, focalizzazione su aree ad alta incertezza
  4. Estensione degli Strumenti Teorici:
    • Asimmetria della Pendenza (Slope Asymmetry)
    • Metrica della Distanza di Ipotesi
    • Coefficiente di Disaccordo Generalizzato

Analisi Teorica

Garanzie di Generalizzazione

Teorema 1 (Limite di Generalizzazione a Due Stadi): Con probabilità almeno 1-δ, l'ipotesi appresa rₜ soddisfa:

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

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

Complessità di Etichettatura

Teorema 6 (Limite di Complessità di Etichettatura): Il limite superiore del numero di interrogazioni attese è:

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

Miglioramenti Chiave:

  • Caso realizzabile: riduzione da O(neT) a Õ(√T)
  • Utilizzo della disuguaglianza di Freedman consente ulteriore riduzione a O(log T)

Configurazione Sperimentale

Set di Dati

Utilizzo di 10 set di dati di riferimento:

  • Classificazione Binaria: cod-rna, covtype, HIGGS, phishing, shuttle, skin
  • Classificazione Multiclasse: connect, dna, letter, pendigits

Configurazione degli Esperti

  • Numero di Esperti: pari al numero di classi n
  • Definizione dell'Esperto: l'esperto gₖ è completamente corretto sulla classe k, predice casualmente su altre classi
  • Funzione di Costo: perdita 0-1 cₖ(x,y) = 𝟙_{gₖ(x)≠y}

Metriche di Valutazione

  • Accuratezza del Sistema: valore medio di 1 - L_def(h,x,y) sul set di test
  • Efficienza di Interrogazione: numero cumulativo di interrogazioni degli esperti vs. numero di interrogazioni disponibili

Dettagli di Implementazione

  • Classe di Ipotesi: modello di regressione logistica (regolarizzazione L2)
  • Funzione di Perdita: perdita logistica multinomiale
  • Ripetizioni Sperimentali: 5 divisioni casuali per ogni set di dati

Risultati Sperimentali

Risultati Principali

Efficienza di Interrogazione:

  • Set di Dati Binari: tasso di interrogazione ridotto al 35-40%
  • Set di Dati Multiclasse: tasso di interrogazione ridotto al di sotto del 30%
  • Effetto del Numero di Esperti: maggiore è il numero di esperti, più evidente è il miglioramento dell'efficienza (migliori risultati nel set di dati letter con 26 esperti)

Mantenimento dell'Accuratezza:

  • Accuratezza del sistema comparabile ai metodi standard su tutti i set di dati
  • Intervalli di errore estremamente ridotti nei set di dati binari, indicando risultati stabili
  • Alcune fluttuazioni nei set di dati multiclasse, ma tendenza complessiva coerente

Scoperte Chiave

  1. Verifica della Scalabilità: il vantaggio del metodo con budget diventa più evidente con l'aumento del numero di esperti
  2. Analisi di Stabilità: le "oscillazioni" durante il processo di apprendimento online sono manifestazioni normali della casualità dell'algoritmo
  3. Verifica Teorica: i risultati sperimentali supportano l'influenza limitata dei componenti chiave nell'analisi teorica (θ, Kℓ, E*)

Lavori Correlati

Campo dell'Apprendimento del Rinvio

  • Metodi a Uno Stadio: Mozannar & Sontag (2020), Verma & Nalisnick (2022)
  • Metodi a Più Stadi: Mao et al. (2023a), ricerca su garanzie di coerenza
  • Sviluppo Teorico: limiti di coerenza H, coerenza Bayes

Apprendimento Attivo

  • Algoritmo IWAL: apprendimento attivo con ponderazione di importanza di Beygelzimer et al. (2009)
  • Apprendimento Attivo Regionale: Cortes et al. (2019a,b, 2020)

Apprendimento con Vincoli di Budget

  • Reid et al. (2024): approccio di gioco d'azzardo contestuale nel caso di un singolo esperto
  • Limitazioni: difficile estensione a più esperti, ipotesi eccessivamente ristrittive

Conclusioni e Discussione

Conclusioni Principali

  1. Prova di Fattibilità: è possibile mantenere le prestazioni degli algoritmi di rinvio riducendo drasticamente i costi di addestramento
  2. Avanzamento Teorico: prime garanzie teoriche rigorose per il problema del rinvio con budget
  3. Valore Pratico: rende le strategie di rinvio più fattibili in ambienti con risorse limitate

Limitazioni

  1. Configurazione degli Esperti: la configurazione degli esperti negli esperimenti è relativamente semplificata; gli esperti nelle applicazioni reali potrebbero essere più complessi
  2. Funzione di Costo: principalmente considerata la perdita 0-1; altre strutture di costo richiedono ulteriore verifica
  3. Limitazioni della Classe di Ipotesi: l'analisi teorica si basa su classi di ipotesi finite; le classi di ipotesi infinite richiedono analisi del numero di copertura

Direzioni Future

  1. Strategie di Interrogazione Adattive: utilizzo delle informazioni strutturali tra campioni di addestramento
  2. Disponibilità Dinamica degli Esperti: gestione di scenari con esperti che cambiano dinamicamente
  3. Integrazione dell'Apprendimento per Rinforzo: applicazione a scenari di decisione sequenziale o interattiva

Valutazione Approfondita

Punti di Forza

  1. Importanza del Problema: risolve un problema pratico fondamentale nell'apprendimento del rinvio
  2. Rigore Teorico: fornisce un framework di analisi teorica completo, inclusi limiti di generalizzazione e complessità di etichettatura
  3. Innovazione Algoritmica: adattamento intelligente delle idee dell'apprendimento attivo allo scenario del rinvio
  4. Completezza Sperimentale: verifica dell'efficacia del metodo su più set di dati

Insufficienze

  1. Limitazioni della Configurazione Sperimentale: la configurazione degli esperti è relativamente artificiale e potrebbe differire dagli scenari di applicazione reale
  2. Singolarità delle Linee di Base di Confronto: principalmente confronto con metodi standard di rinvio, mancanza di confronto con altri metodi con vincoli di budget
  3. Analisi Insufficiente della Complessità Computazionale: mancanza di analisi dettagliata dei costi computazionali dell'algoritmo

Impatto

  1. Contributo Accademico: apre una nuova direzione di ricerca nel campo dell'apprendimento del rinvio
  2. Valore Pratico: significativo per applicazioni pratiche che coinvolgono esperti costosi
  3. Valore Teorico: estende la teoria dell'apprendimento attivo a nuovi scenari di applicazione

Scenari Applicabili

  1. Rinvio di Modelli Linguistici di Grandi Dimensioni: decisioni di rinvio sensibili ai costi tra LLM di diverse dimensioni
  2. Sistemi di Diagnosi Medica: allocazione di compiti diagnostici tra medici di diverse specialità
  3. Reti di Sensori: decisioni di raccolta dati tra sensori con diverse capacità

Bibliografia

Il presente articolo cita importanti letteratura nei campi dell'apprendimento del rinvio, dell'apprendimento attivo e dei giochi d'azzardo multi-braccio, in particolare:

  • Mao et al. (2023a, 2024a): fondamenti teorici del rinvio multiplo
  • Beygelzimer et al. (2009): idea della ponderazione di importanza nell'algoritmo IWAL
  • Reid et al. (2024): lavoro pionieristico nel rinvio con vincoli di budget

Valutazione Complessiva: questo è un articolo di alta qualità nel campo dell'apprendimento automatico teorico che risolve un importante problema pratico nell'apprendimento del rinvio, fornendo analisi teorica rigorosa e verifica sperimentale convincente. Il principale contributo dell'articolo risiede nel primo studio sistematico del controllo dei costi di interrogazione degli esperti nella fase di addestramento, gettando una base importante per le applicazioni pratiche in questo campo.