С ростом количества приложений для круглосуточного распространения, разработанных Chappiebot Inc., нам нужен алгоритм для тестирования многих моделей с одной и той же целью, чтобы определить, какая из них является лучшей. Традиционный метод — A/B-тест. Однако замечено, что этот старомодный способ становится неэффективным в наш век больших данных. В этом блоге я расскажу о некоторых альтернативных методах.
I. A/B-тестирование
Прежде чем углубиться в альтернативные подходы, мы представим некоторые основные моменты, касающиеся A/B-тестирования. В тесте A/B мы сравниваем две разные модели, чтобы определить, какая из них лучше. Группа пользователей A продолжает использовать старую модель, в то время как другая группа (B) использует новую. Через некоторое время, исходя из статистики, у нас будет схема «победитель получает все»: если выиграет старый, все останется на месте, ничего не изменится. В противном случае новая модель будет запущена в производство для каждого пользователя.
Этот метод очень популярен в разработке программного обеспечения. Например, иногда ваш друг рядом с вами показывает вам некоторые функции приложения Facebook, но у вас их нет, даже если вы используете одну и ту же версию.
Плюсы и минусы:
- Как мы видим, этот метод очень интуитивно понятен и прост в реализации. Хотя он основан на статистической модели, люди, не имеющие опыта работы со статистикой, все же могут легко его понять.
- С некоторых точек зрения это неэффективно. Нам нужно немного подождать, чтобы получить модель-победитель, и мы должны придерживаться этой модели в течение длительного времени, даже если, возможно, в какой-то момент в будущем она перестанет быть лучшей. Это не оптимально, мы стремимся найти решение, основанное на данных: мы можем изменить решение со временем.
- Более того, когда статистика между вариантами немного отличается, сложно выбрать победителя.
II. Многорукие бандиты (MAB)
Основываясь на предыдущем наблюдении, некоторые самые яркие умы в Data Science ищут альтернативу пересмотру тестирования. И в этом процессе Многорукие бандиты демонстрируют некоторый потенциал. Название происходит от автоматов «Однорукие бандиты» в казино. В этой машине есть рычаг, с помощью которого вы можете попытать счастья, чтобы выиграть награду (на самом деле, она настроена на облегчение вашего кармана).
Представьте, что вы входите в комнату со множеством таких игровых автоматов. Стратегия победы должна заключаться в том, чтобы найти, на какой машине играть и в каком порядке. Наша цель состоит в том, чтобы максимизировать вознаграждение за последовательность нажатия на рычаг. Метод многоруких бандитов в основном состоит из:
- Фаза исследования: вы пощадите в равной степени все машины за долю вашего времени.
- Этап эксплуатации: вы будете придерживаться машины с лучшими характеристиками, полученными на этапе исследования.
A/B решит эту проблему, разделив деньги на 2 счета. Сначала он будет использовать первую учетную запись, чтобы попробовать все машины, чтобы определить, какая из них лучше, а затем будет придерживаться этой машины до конца с другой учетной записью. Для сравнения, A/B-тестирование использует короткую фазу исследования и длинную фазу эксплуатации. Они последовательные: один за другим.
Лично это не так уж и сложно. Теперь все, что осталось, — найти стратегию для определения скорости разведки и эксплуатации. Здесь есть три метода:
- Epsilon-Greedy: ставки для каждого фиксированы.
- Верхний доверительный предел: ставки динамически обновляются относительно UCB каждой руки.
- Выборка Томпсона: ставки корректируются с учетом всего распределения вероятностей каждой руки.
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 за счет включения контекстной информации при выборе модели (этап исследования). В МАБ выбор производится единообразно. Включение информации о состоянии уменьшит дисперсию модели тестирования. Это поможет нам повысить эффективность на этапе исследования, что сделает тестирование более динамичным.
В. Ссылки:
- https://www.searchenginepeople.com/blog/16072-multi-armed-bandits-ab-testing-makes-money.html
- http://stevehanov.ca/blog/index.php?id=132
- https://towardsdatascience.com/solving-the-multi-armed-bandit-problem-b72de40db97c
- https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-1-5-contextual-bandits-bff01d1aad9c