С ростом количества приложений для круглосуточного распространения, разработанных Chappiebot Inc., нам нужен алгоритм для тестирования многих моделей с одной и той же целью, чтобы определить, какая из них является лучшей. Традиционный метод — A/B-тест. Однако замечено, что этот старомодный способ становится неэффективным в наш век больших данных. В этом блоге я расскажу о некоторых альтернативных методах.

I. A/B-тестирование

Прежде чем углубиться в альтернативные подходы, мы представим некоторые основные моменты, касающиеся A/B-тестирования. В тесте A/B мы сравниваем две разные модели, чтобы определить, какая из них лучше. Группа пользователей A продолжает использовать старую модель, в то время как другая группа (B) использует новую. Через некоторое время, исходя из статистики, у нас будет схема «победитель получает все»: если выиграет старый, все останется на месте, ничего не изменится. В противном случае новая модель будет запущена в производство для каждого пользователя.

Этот метод очень популярен в разработке программного обеспечения. Например, иногда ваш друг рядом с вами показывает вам некоторые функции приложения Facebook, но у вас их нет, даже если вы используете одну и ту же версию.

Плюсы и минусы:

  • Как мы видим, этот метод очень интуитивно понятен и прост в реализации. Хотя он основан на статистической модели, люди, не имеющие опыта работы со статистикой, все же могут легко его понять.
  • С некоторых точек зрения это неэффективно. Нам нужно немного подождать, чтобы получить модель-победитель, и мы должны придерживаться этой модели в течение длительного времени, даже если, возможно, в какой-то момент в будущем она перестанет быть лучшей. Это не оптимально, мы стремимся найти решение, основанное на данных: мы можем изменить решение со временем.
  • Более того, когда статистика между вариантами немного отличается, сложно выбрать победителя.

II. Многорукие бандиты (MAB)

Основываясь на предыдущем наблюдении, некоторые самые яркие умы в Data Science ищут альтернативу пересмотру тестирования. И в этом процессе Многорукие бандиты демонстрируют некоторый потенциал. Название происходит от автоматов «Однорукие бандиты» в казино. В этой машине есть рычаг, с помощью которого вы можете попытать счастья, чтобы выиграть награду (на самом деле, она настроена на облегчение вашего кармана).

Представьте, что вы входите в комнату со множеством таких игровых автоматов. Стратегия победы должна заключаться в том, чтобы найти, на какой машине играть и в каком порядке. Наша цель состоит в том, чтобы максимизировать вознаграждение за последовательность нажатия на рычаг. Метод многоруких бандитов в основном состоит из:

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

A/B решит эту проблему, разделив деньги на 2 счета. Сначала он будет использовать первую учетную запись, чтобы попробовать все машины, чтобы определить, какая из них лучше, а затем будет придерживаться этой машины до конца с другой учетной записью. Для сравнения, A/B-тестирование использует короткую фазу исследования и длинную фазу эксплуатации. Они последовательные: один за другим.

Лично это не так уж и сложно. Теперь все, что осталось, — найти стратегию для определения скорости разведки и эксплуатации. Здесь есть три метода:

  1. Epsilon-Greedy: ставки для каждого фиксированы.
  2. Верхний доверительный предел: ставки динамически обновляются относительно UCB каждой руки.
  3. Выборка Томпсона: ставки корректируются с учетом всего распределения вероятностей каждой руки.

Epsilon-Greedy на сегодняшний день является самым популярным из-за своей простоты и эффективности.

Псевдокод для Epsilon-Greedy:

III. Пример:

Представьте, что мы тестируем цвет кнопки Поделиться. Есть 3 варианта: зеленый, синий, красный. В начале мы инициализируем значение для каждого цвета 1/1=100%. Это число выбрано произвольно: что бы мы ни выбрали, оно само подстроится под задачу.

Во-первых, мы выбираем вариант с наибольшей вероятностью (этап эксплуатации). Поскольку все одинаково, мы случайным образом отображаем зеленый цвет. Но пользователь говорит Нет:

Следующие последовательно говорят «нет» Синему и Красному:

Внезапно четвертый пользователь предпочел синий:

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

Рандомизация

Мы часто видим скорость 1/9 в методе Greedy-Epsilon. Это оптимально?

Скорость исследования и эксплуатации отражает компромисс между тем, чтобы попробовать что-то новое или придерживаться того, что работает. A/B-тест сначала тратит 100% своего времени на изучение, а затем полностью переключается на жадную фазу. В этом есть свой смысл. Вначале у нас не так много интуиции, поэтому мы тратим много времени на фазу исследования, но со временем скорость снижается. Это дух UCB и Thompson Sampling.

Какой лучше?

Конечно, большинство придерживается бандитского подхода. Есть еще те, кто поддерживает A/B Test. Это все еще полезно, когда не так много сбивающих с толку факторов и у нас достаточно времени для запуска теста. Лично я думаю, что A/B-тест может сыграть холодный старт для Бандита (схема «Исследуй-сначала»)

IV. Контекстные бандиты

Contextual Bandits улучшает MAB за счет включения контекстной информации при выборе модели (этап исследования). В МАБ выбор производится единообразно. Включение информации о состоянии уменьшит дисперсию модели тестирования. Это поможет нам повысить эффективность на этапе исследования, что сделает тестирование более динамичным.

В. Ссылки: