Бюджетированное многоэкспертное делегирование

Основная информация

• 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. Выбор эксперта: выбор эксперта 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)
• Использование неравенства Фридмана позволяет дополнительно достичь 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) на тестовом наборе
• Эффективность запроса: кумулятивное количество запросов экспертов vs. доступное количество запросов

Детали реализации

• Класс гипотез: модель логистической регрессии (L2 регуляризация)
• Функция потерь: многоклассовая логистическая потеря
• Повторение экспериментов: 5 случайных разбиений для каждого набора данных

Результаты экспериментов

Основные результаты

Эффективность запроса:

• Наборы данных бинарной классификации: коэффициент запроса снижен до 35-40%
• Наборы данных многоклассовой классификации: коэффициент запроса снижен ниже 30%
• Эффект количества экспертов: преимущество бюджетированного метода более выражено с увеличением количества экспертов (лучший результат на наборе данных letter с 26 экспертами)

Сохранение точности:

• Точность системы на всех наборах данных сравнима со стандартным методом
• Доверительные интервалы ошибок на наборах данных бинарной классификации минимальны, что указывает на стабильность результатов
• На наборах данных многоклассовой классификации наблюдается некоторая вариативность, но общая тенденция согласуется

Ключевые выводы

1. Проверка масштабируемости: преимущества бюджетированного метода становятся более выраженными с увеличением количества экспертов
2. Анализ стабильности: "колебания" в процессе онлайн-обучения являются нормальным проявлением случайности алгоритма
3. Теоретическая проверка: экспериментальные результаты подтверждают ограниченное влияние ключевых компонентов теоретического анализа (θ, Kℓ, E*)

Связанные работы

Область обучения делегированию

• Одноэтапные методы: Mozannar & Sontag (2020), Verma & Nalisnick (2022)
• Многоэтапные методы: Mao et al. (2023a), исследования гарантий согласованности
• Теоретическое развитие: H-согласованные границы, Байесовская согласованность

Активное обучение

• Алгоритм 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): пионерская работа по бюджетированному делегированию

Общая оценка: это высококачественная статья по теории машинного обучения, решающая важную практическую проблему в обучении делегированию с предоставлением строгого теоретического анализа и убедительной экспериментальной проверки. Основной вклад работы заключается в первом систематическом исследовании контроля стоимости запросов экспертов на этапе обучения, что закладывает важную основу для практического применения методов делегирования в данной области.