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

Budgetierte Multiple-Expert-Deferral

Grundinformationen

Paper-ID: 2510.26706
Titel: Budgeted Multiple-Expert Deferral
Autoren: Giulia DeSalvo (Google DeepMind), Clara Mohri (Harvard University), Mehryar Mohri (Google Research & Courant Institute), Yutao Zhong (Google Research)
Klassifizierung: cs.LG, stat.ML
Veröffentlichungsdatum: 30. Oktober 2025 (arXiv-Preprint)
Paper-Link: https://arxiv.org/abs/2510.26706

Zusammenfassung

Das Erlernen, unsichere Vorhersagen an teure Experten zu delegieren, ist eine wirksame Strategie zur Verbesserung der Genauigkeit und Effizienz von Maschinenlern-Systemen. Allerdings erfordern Standard-Trainingsverfahren für Delegationsalgorithmen typischerweise die Abfrage aller Experten für jede Trainingsinstanz, was bei signifikanten Rechenkosten oder Ressourcenkosten extrem teuer wird und das Kernziel der Delegation – die Begrenzung unnötiger Expertennutzung – unterläuft. Um diese Herausforderung zu bewältigen, führt dieses Paper das Framework der budgetierten Delegation ein, das darauf abzielt, effektive Delegationsalgorithmen zu trainieren und gleichzeitig die Kosten für Expertenabfragen während des Trainings zu minimieren.

Forschungshintergrund und Motivation

Problemdefinition

Das traditionelle Lernen zur Delegation mit mehreren Experten (Learning to Defer) steht vor einem grundlegenden Widerspruch:

Kernziel: Kostenreduktion durch selektive Delegation von Vorhersageaufgaben an Experten
Trainingsrealität: Standard-Trainingsverfahren erfordern die Abfrage aller Experten für jede Trainingsmuster mit Gesamtkosten von neT (Anzahl der Experten × Trainingsmuster)
Kostenparadoxon: Der Trainingsprozess selbst widerspricht dem Ziel der Kostenkontrolle

Forschungsrelevanz

Praktische Anforderungen: In Szenarien mit teuren Ressourcen wie großen Sprachmodellen oder menschlichen Experten können Trainingskosten extrem hoch sein
Skalierungsprobleme: Mit zunehmender Anzahl von Experten wachsen die Trainingskosten linear, was die praktische Anwendbarkeit einschränkt
Ressourcenbeschränkte Umgebungen: In Umgebungen mit begrenzten Rechenressourcen sind bestehende Methoden schwer einsetzbar

Einschränkungen bestehender Methoden

Annahme vollständiger Abfragen: Bestehende Methoden gehen davon aus, dass Vorhersagen und Kosteninformationen aller Experten kostenfrei verfügbar sind
Theorie-Praxis-Lücke: Theoretische Analysen ignorieren Abfragekosten in der Trainingsphase
Schlechte Skalierbarkeit: Ineffektive Handhabung großer Expertenmengen

Kernbeiträge

Einführung des budgetierten Delegations-Frameworks: Erste systematische Untersuchung der Kontrolle von Expertenabfragekosten während des Trainings
Zwei-Phasen-Algorithmus-Design:
- Zwei-Phasen-Budgetierter-Delegations-Algorithmus (Abschnitte 3-5)
- Ein-Phasen-Budgetierter-Delegations-Algorithmus (Anhang E)
Theoretische Garantien:
- Generalisierungsschranken: Leistungsgarantien vergleichbar mit Standard-Methoden
- Label-Komplexität: Reduktion von O(T) auf Õ(√T) im realisierbaren Fall, weiter bis O(log T)
Experimentelle Validierung: Erreichung von Expertenabfragequoten unter 40% auf mehreren Datensätzen bei Beibehaltung der Vorhersagegenauigkeit

Methodische Details

Aufgabendefinition

Zwei-Phasen-Einstellung:

Eingaberaum: X, Labelraum: Y = n
Expertenmenge: {g₁, ..., gₙₑ}, wobei jeder Experte gⱼ: X × Y → ℝ
Routing-Funktion: r ∈ R, wählt Experte r(x) = argmax_k r(x,k)
Kostenfunktion: cₖ(x,y), typischerweise 0-1 Verlust

Ziel: Minimierung des zwei-Phasen-Delegationsverlust

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

Kern-Algorithmus-Architektur

Algorithmus 1: Budgetierter Zwei-Phasen-Delegations-Algorithmus

Schlüsselinnovation: Zerlegung der Entscheidung in zwei Teile

Expertenauswahl: Wähle Experte k mit Wahrscheinlichkeit qₜ,ₖ
Abfrage-Entscheidung: Frage Kosten des ausgewählten Experten mit Wahrscheinlichkeit pₜ,ₖ ab

Algorithmus-Ablauf:

für t = 1 bis T:
    Empfange (xₜ, yₜ)
    Berechne Abfrage-Wahrscheinlichkeitsvektor pₜ ← SAMPLING-PROBS(...)
    Wähle Experte kₜ ~ q_t
    Frage Kosten cₜ,ₖₜ mit Wahrscheinlichkeit pₜ,ₖₜ ab
    Aktualisiere Trainingsmenge Sₜ (mit Wichtungsgewicht 1/(qₜ,ₖₜpₜ,ₖₜ))
    Aktualisiere Routing-Funktion rₜ

Algorithmus 2: SAMPLING-PROBS Unterprogramm

Versionraum-Verwaltung:

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

Abfrage-Wahrscheinlichkeitsberechnung:

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

Designphilosophie: Priorisierung der Abfrage von Experten-Instanz-Paaren mit maximaler Uneinigkeit im aktuellen Versionraum

Technische Innovationen

Adaptive Abfragestrategie: Dynamische Anpassung der Abfragewahrscheinlichkeiten basierend auf Hypothesen-Uneinigkeit
Wichtungsgewichtete Schätzung: Sicherung unverzerrter Schätzungen durch Gewicht 1/(qₜ,ₖpₜ,ₖ)
Versionraum-Beschneidung: Progressive Eliminierung suboptimaler Hypothesen, Fokussierung auf hochunsichere Regionen
Erweiterung theoretischer Werkzeuge:
- Asymmetrie der Steigung (Slope Asymmetry)
- Hypothesen-Distanzmetriken
- Verallgemeinerter Uneinigkeitskoeffizient

Theoretische Analyse

Generalisierungsgarantien

Theorem 1 (Zwei-Phasen-Generalisierungsschranke): Mit Wahrscheinlichkeit mindestens 1-δ erfüllt die gelernte Hypothese rₜ:

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

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

Label-Komplexität

Theorem 6 (Label-Komplexitätsschranke): Obere Schranke für erwartete Abfragezahl:

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

Schlüsselverbesserungen:

Realisierbarer Fall: Reduktion von O(neT) auf Õ(√T)
Mit Freedman-Ungleichung weiter erreichbar bis O(log T)

Experimentelle Einrichtung

Datensätze

Verwendung von 10 Benchmark-Datensätzen:

Binärklassifikation: cod-rna, covtype, HIGGS, phishing, shuttle, skin
Mehrklassen-Klassifikation: connect, dna, letter, pendigits

Experten-Einrichtung

Anzahl der Experten: Gleich der Anzahl der Klassen n
Experten-Definition: Experte gₖ ist auf Klasse k vollkommen korrekt, auf anderen Klassen zufällig
Kostenfunktion: 0-1 Verlust cₖ(x,y) = 𝟙_{gₖ(x)≠y}

Bewertungsmetriken

System-Genauigkeit: Durchschnittswert von 1 - L_def(h,x,y) auf Testsatz
Abfrage-Effizienz: Kumulierte Expertenabfragen vs. verfügbare Abfragen

Implementierungsdetails

Hypothesenklasse: Logistische-Regressions-Modelle (L2-Regularisierung)
Verlustfunktion: Multinomiale logistische Verlustfunktion
Experimentwiederholungen: 5 zufällige Aufteilungen pro Datensatz

Experimentelle Ergebnisse

Hauptergebnisse

Abfrage-Effizienz:

Binärklassifikations-Datensätze: Abfragequote auf 35-40% reduziert
Mehrklassen-Datensätze: Abfragequote unter 30%
Effekt der Expertenanzahl: Je mehr Experten, desto signifikanter die Effizienzverbesserung (beste Ergebnisse beim letter-Datensatz mit 26 Experten)

Genauigkeitsbeibehaltung:

System-Genauigkeit auf allen Datensätzen vergleichbar mit Standard-Methoden
Binärklassifikations-Datensätze zeigen minimale Fehlerbalken, was auf stabile Ergebnisse hindeutet
Mehrklassen-Datensätze zeigen gewisse Schwankungen, aber konsistente Gesamttrends

Schlüsselfunde

Skalierbarkeitsvalidierung: Mit zunehmender Expertenanzahl werden Vorteile der budgetierten Methode deutlicher
Stabilitätsanalyse: "Zittern" während des Online-Lernens ist normales Verhalten der Algorithmus-Zufälligkeit
Theoretische Validierung: Experimentelle Ergebnisse unterstützen begrenzte Auswirkungen von Schlüsselkomponenten (θ, Kℓ, E*) in der theoretischen Analyse

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

Machbarkeitsbeweis: Erhebliche Reduktion der Trainingskosten bei Beibehaltung der Delegationsalgorithmus-Leistung ist möglich
Theoretischer Durchbruch: Erste strenge theoretische Garantien für das budgetierte Delegationsproblem
Praktischer Wert: Macht Delegationsstrategien in ressourcenbeschränkten Umgebungen praktischer

Einschränkungen

Experten-Einrichtung: Experimentelle Experten-Einrichtung ist relativ vereinfacht; reale Anwendungen könnten komplexere Experten haben
Kostenfunktionen: Hauptsächlich 0-1 Verlust berücksichtigt; andere Kostenstrukturen benötigen weitere Validierung
Hypothesenklassen-Einschränkungen: Theoretische Analyse basiert auf endlichen Hypothesenklassen; unendliche Klassen benötigen Überdeckungsanalyse

Zukünftige Richtungen

Adaptive Abfragestrategien: Nutzung von Strukturinformationen zwischen Trainingsmuster
Dynamische Experten-Verfügbarkeit: Handhabung von Szenarien mit sich ändernden Experten
Verstärkungslern-Integration: Für sequenzielle oder interaktive Entscheidungsszenarien

Tiefgreifende Bewertung

Stärken

Problemrelevanz: Löst ein grundlegendes praktisches Problem im Delegationslernbereich
Theoretische Strenge: Bietet vollständiges theoretisches Analysegerüst einschließlich Generalisierungsschranken und Label-Komplexität
Algorithmus-Innovation: Geschickte Anpassung von Ideen des aktiven Lernens auf Delegationslern-Szenarien
Experimentelle Vollständigkeit: Validierung der Methodeneffektivität auf mehreren Datensätzen

Schwächen

Experimentelle Einrichtungs-Einschränkungen: Experten-Einrichtung ist relativ künstlich; mögliche Diskrepanzen zu realen Anwendungsszenarien
Begrenzte Vergleichsbaselines: Hauptsächlich Vergleich mit Standard-Delegationsmethoden; Vergleich mit anderen budgetbeschränkten Methoden fehlt
Unzureichende Rechenaufwands-Analyse: Fehlende detaillierte Analyse der Rechenkosten des Algorithmus

Einflussfaktor

Akademischer Beitrag: Eröffnet neue Forschungsrichtung im Delegationslernbereich
Praktischer Wert: Bedeutsam für reale Anwendungen mit teuren Experten
Theoretischer Wert: Erweitert aktive Lerntheorie auf neue Anwendungsszenarien

Anwendungsszenarien

Große-Sprachmodell-Delegation: Kostenempfindliche Delegationsentscheidungen zwischen verschiedenen LLM-Größen
Medizinische Diagnosesysteme: Aufgabenverteilung zwischen verschiedenen Fachärzte
Sensornetzwerke: Datenerfassungsentscheidungen zwischen Sensoren unterschiedlicher Kapazität

Literaturverzeichnis

Dieses Paper zitiert wichtige Literatur aus den Bereichen Delegationslernens, aktives Lernen und Multi-Armed Bandits, insbesondere:

Mao et al. (2023a, 2024a): Theoretische Grundlagen der Mehrexperten-Delegation
Beygelzimer et al. (2009): Wichtungsgewichtete Ideen des aktiven Lernens
Reid et al. (2024): Pionierarbeit bei budgetierter Delegation

Gesamtbewertung: Dies ist ein hochqualitatives Maschinenlern-Theorie-Paper, das ein wichtiges praktisches Problem im Delegationslernbereich löst und strenge theoretische Analysen sowie überzeugende experimentelle Validierung bietet. Der Hauptbeitrag liegt in der ersten systematischen Untersuchung der Kontrolle von Expertenabfragekosten in der Trainingsphase und legt damit eine wichtige Grundlage für praktische Anwendungen in diesem Bereich.