827,55
Рейтинг
Mail.ru Group
Строим Интернет

Многорукие бандиты: особенности использования алгоритмов ранжирования

Блог компании Mail.ru GroupАлгоритмыМатематика

При работе с алгоритмами есть две реальности: как это написано в учебнике и как это получается у тебя. Второе ближе к телу, и хочется, чтобы оно получалось. Главное, понимать, что ты работаешь не с оригинальной модельной задачей; в твоём проде есть особенности, которые могут мешать тебе достичь результата. И я хочу рассказать о нескольких нюансах в запуске многоруких бандитов.

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

Сперва немного контекста. У меня на проекте нужно было отранжировать видео-новости, которые предлагались пользователю. При этом нужно увеличить основные показатели, такие как количество просмотренных роликов или общее время пользователя, но мы заметили, что активация пользователей существенно низкая. Следовательно, увеличение CTR могло бы поднять нужные нам метрики. Здесь и было принято решение, что нам нужно поработать с многоруким бандитами.

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

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

  • epsilon-greedy;
  • UCB1;
  • Thompson sampling.

Большинство разработчиков останавливаются на epsilon-greedy, хотя все тесты показывают, что UCB1 и Thompson sampling эффективнее, то есть быстрее сходятся. Дело в том, что обычно в проде есть две особенности, которые не дают корректно использовать оба этих алгоритма. Проблемы вызывают отложенность обратной связи и новый контент.

Отложенность обратной связи


Часто это упускают из виду, но всё-таки бандиты относятся к классу online задач. Предполагается, что вы сразу же получаете от среды отклик на своё действие и можете тут же использовать обновленный опыт. Отклик среды и есть та обратная связь, которая позволяет быстро подстраиваться.

Отложенная обратная связь — это не время, через которое вы получаете отклик, а количество событий, через которые вы эту связь учитываете. Тем не менее, при объяснении эффектов я буду использовать задержку по времени, так проще для понимания.

Например, в моем случае, особенность архитектуры была такой, что я мог узнать реакцию пользователя за несколько секунд, однако обновить параметры в алгоритме бандита можно было только раз в 30 минут. Обратная связь откладывается, а за это время происходит несколько десятков тысяч событий. Замечу, кстати, что 30-минутная задержка была бы не такой страшной, если бы за это время у меня было только 1-2 события, но когда их тысячи — это целая вечность.

Есть проблема, но задачу решать надо. Сразу скажу, что отложенная обратная связь препятствует использованию UCB1, и вот почему. В этом алгоритме ранги для документов вычисляются строго исходя из наблюдаемых значений активации и показов. А поскольку отклик приходит с опозданием, на величину дельты этого опоздания параметры твоей системы не меняются. Как результат, ты получаешь фиксированную выдачу на время задержки. Поэтому сильно страдает exploration (исследование нового контента).

Проблеме отложенной обратной связи меньше подвержены методы с вшитой случайностью: epsilon-greedy и Thompson sampling. Однако и эти алгоритмы не совсем гладко справляются с этой проблемой, но всё-таки с меньшими потерями. Самой главной трудностью для них будет то состояние, в котором зафиксирована система, но эти алгоритмы всё равно попытаются провести некоторое исследование (exploration), и к следующему обновлению у тебя будет больше шансов использовать результаты случайности и вытянуть что-то стоящее.

Новый контент


В реальном продукте мы постоянно пополняем нашу базу чем-то новым. Для epsilon-greedy совершенно безразлично, сколько нового контента он получил. Понемногу он будет отдавать предпочтение новому, и через какое-то время мы узнаем реальные ранги. У алгоритмов UCB1 и Thompson sampling поведение отличается. Они постараются показывать сперва новый контент, и с каждой новой итерацией добавленный контент будет тонуть в топах до тех пор, пока не зафиксируется на какой-то стабильно позиции (в некоторых случаях, если CTR достаточно высоки, контент может повышать позицию в топе). В любом случае, важно, что процесс exploration запустится на свежем контенте.

Если у нас честный online learning, то исследование нового не займет много времени. И, в зависимости от объема аудитории и количества свежего контента, мы можем даже не заметить, что алгоритмы переходили в exploration-фазу.

И всё же здесь есть маленький нюанс. Когда в нашем продукте мы наблюдаем одновременно и отложенность обратной связи и новый контент, «ломается» Thompson sampling. Что же происходит? Поясню на примере своего случая. В текущие полчаса ко мне пришли несколько единиц нового контента, а следовательно, до следующего обновления Thompson sampling отдает предпочтение в основном свежему контенту. И если у вас достаточно низкий CTR и пришло что-то новенькое, то, скорее всего, в следующие полчаса ты будешь случайным образом показывать только свежий контент. Если это происходит один раз в сутки, то не страшно, потому что всё остальное время мы работаем почти эффективно. Однако проблемы начинаются, когда у тебя есть какой-то новый контент в каждую итерацию учета обратной связи. В этом случае Thompson sampling будет стараться показывать только новый контент, который пришел за последнее время, потому что для этого контента алгоритм находится в режиме exploration и не знает о нем совершенно ничего. В моем случае каждые полчаса приходило около 20 новостей и выдача в топах превращалась в показ только свежего контента.

В результате самая неэффективная стратегия epsilon-greedy оказывается самой устойчивой к внешним особенностям.

Исправляем Томпсона


Существует несколько способов смешивания стратегий Thompson sampling и epsilon-greedy. Я опишу только один из методов, на мой взгляд, менее затратный с точки зрения реализации.

Суть в том, чтобы использовать биас при сэмплировании рангов для документов. Мы пользуемся формулой:

$r(x) = Beta(positive_x, negative_x) + bias_x \,$


Здесь $x$ — документ для которого вычисляем ранг, $positve_x$ и $negative_x$ — количество положительных и отрицательных событий для документа $x$, $Beta(\cdot,\cdot)$ — бета-распределение, $bias_x$ — смещение для документа $x$.

То есть суть модификации только в биасе, а если наложить несколько ограничений, то мы сможем даже его вычислить напрямую.

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

Во-вторых, биас будем вычислять только для холодного контента, то есть для прогретого с $bias_x = 0$. Более того, холодный контент я буду показывать рандомно и равновероятно. Это заклинание означает, что внутри холодного контента я не расставляю приоритеты по показам. Кстати, отсюда следует, что в этом случае $bias = const$. Равновероятность при сэмплировании по beta-распределению можно получить, только когда $positve = negative = 1$. Следовательно, для холодных документов мы не учитываем накопленную статистику, даже если у нас обновились данные. Единственное, что мы должны учитывать, это $positive + negative < c$, то есть когда документ еще холодный.

Обозначим как $p_{max}$ максимальный CTR на прогретой части, $n$ — количество холодных документов на текущей итерации и $\epsilon$ — долю аудитории, которой вы готовы показывать холодные документы.

Биас для холодных документов вычисляется по формуле:

$bias = (1-\epsilon)^\frac1n - p_{max}$


Как выводится эта формула. В случае $positive=negative=1$, обозначим через $\lambda$ вероятность того, что для холодного документа сгенерированный ранг будет выше ранга любого прогретого документа. Её можно вычислить как геометрическую вероятность: $\lambda = 1 — (bias + p_{max})$. Поскольку у нас имеется $n$ холодных документов и мы хотим, чтобы в $(1-\epsilon)$ случаях в верху топа показывались прогретые документы, можем связать всё одной формулой $C_n^0 \lambda^0 (1 - \lambda)^n = 1 - \epsilon$, и после должных сокращений получим $bias = (1-\epsilon)^\frac1n - p_{max}$.

Итак, конечная модификация алгоритма такая:

  1. Фиксируем два параметра $c$ и $\epsilon$.
  2. Разделяем все документы на холодные и прогретые.
  3. Вычисляем количество холодных документов $n$.
  4. Вычисляем $p_{max}$ на прогретой части.
  5. Для холодных собираем $positive=negative=1$ и $bias = (1-\epsilon)^\frac1n - p_{max}$.
  6. Для прогретых собираем $positive$ и $negative$ исходя из текущей известной информации.
  7. Для всех документов семплируем ранги по формуле $r(x) = Beta(positive_x, negative_x) + bias_x$.

Как видишь, мы остаемся в рамках Thompson sampling, однако с помощью небольшой модификации создаём трамплин для новых документов. В алгоритме появились два новых параметра $\epsilon$ и $c$, которые отвечают за то, сколько будет прогреваться новый контент. Могу дать только одну рекомендацию по поводу параметра $c$: он должен быть в 2-3 раза больше, чем $1/mean(CTR)$. Отсюда уже можно вычислить и $\epsilon$, но всё-таки лучше его зафиксировать.
Теги:многорукие бандиты
Хабы: Блог компании Mail.ru Group Алгоритмы Математика
+29
2,4k 43
Комментарии 8

Лучшие публикации за сутки

Информация

Дата основания
Местоположение
Россия
Сайт
team.mail.ru
Численность
5 001–10 000 человек
Дата регистрации

Блог на Хабре