Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Появился способ разложить разрыв между теоретическим пределом последовательного алгоритма и его реальными затратами на отдельные потери информации. В препринте, который не рецензирован и содержит замеры самого автора, Akshay Balsubramani показывает, что для накопленного проигрыша классическая асимптотическая граница завышает требования на практическом числе шагов. Это помогает понять, нужно ли менять сам алгоритм или проблема только в слишком грубой теоретической оценке.
Работа объединяет границы для задач многоруких бандитов, последовательных тестов, поиска лучшего варианта и марковских процессов принятия решений. Обычное доказательство сначала сравнивает полные истории двух запусков, затем сжимает их до одной статистики, подставляет гарантию для всего класса алгоритмов и выбирает наиболее трудную альтернативу. Новая схема записывает каждый переход отдельно и показывает, сколько информации он отбрасывает.
При работе с естественными экспоненциальными семействами достаточно сохранить число обращений к каждому варианту и сумму полученных наград: на этом шаге информация не теряется. Остальные потери, кроме перехода к бесконечному числу шагов, можно вычислить по запускам самого алгоритма. Для гарантий на весь класс это возможно, когда гарантия задана числом — например, допустимым риском ошибки.
На задачах выбора лучшей обученной модели и в тесте Wald крупнейшей причиной разрыва обычно оказалась именно замена поведения конкретного алгоритма общей гарантией класса. В задачах накопленного проигрыша асимптотически оптимальные алгоритмы на всех проверенных горизонтах оставались ниже классического предела: он требовал больше проб, чем было нужно на практике.
Проверка охватила семь ранее опубликованных наборов и моделей: от MovieLens и точности обученных моделей до почтового маркетинга, обслуживания оборудования и замены двигателей. Для фиксированного распределения проб новая граница на малых различиях может улучшать показатель ошибки почти вдвое, но при адаптивном выборе действий выигрыш на MovieLens к 3 000 шагам составлял лишь 1,03–1,40 раза. Поэтому результат полезнее как диагностический инструмент, чем как обещание универсально более строгой границы.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
