company_banner

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


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

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

    Сперва немного контекста. У меня на проекте нужно было отранжировать видео-новости, которые предлагались пользователю. При этом нужно увеличить основные показатели, такие как количество просмотренных роликов или общее время пользователя, но мы заметили, что активация пользователей существенно низкая. Следовательно, увеличение 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
    Строим Интернет

    Комментарии 8

      0
      > однако обновить параметры в алгоритме бандита можно было только раз в 30 минут.

      А с чем связано такое странное ограничение, если не секрет?
        0
        Задача была встроиться в текущую архитектуру, но изначально в ней не закладывались счётчики такого типа, был только механизм обновления данных, но он тянул обновление всего. Из-за этого и возник этот лаг.
          0

          Я не очень понял, как это бьётся с утверждением


          Например, для новостей с моим объемом аудитории было достаточно задать, и если у конкретной новости меньше ста показов, то мы её считаем холодной.

          Если у вас значения конкретных счётчиков приходят раз в пол часа, то каким образом вы определяете, сколько показов было? Или идея в том, что после получения свежей статистики Томпсон работает на статичных данных и вытягивает только за счёт рандома по бэта-распределению?

            0

            Ага, именно так.

        0
        Задача о многоруких бандитах — это задача поиска руки с наибольшим мат ожиданием награды (!) при условии, что распределение награды неизвестно. Вы начали решать свою задачу, как типичный «частотник». Представьте, что вместо видеороликов вы имеете дело с продажей дорогих авто. Будете ли вы использовать алгоритм Томпсона для определения лучшей цены? Нет, вы мигом переобуетесь из «частотника» в «байесовиста» :) Сначала вы поймете, что вполне приемлемый доверительный интервал для матожидания награды в большинстве случаев может быть построен всего с 8-й попытки. А возможно ли построить доверительный интервал всего после одной попытки? Если нет, то тогда чем занимается алгоритм Томпсона? А если вам известно хотя бы название распределения, нужно ли вам использовать алгоритм Томпсона?
          0

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

          0

          Бета распределение для дорогих авто не подойдёт. Я не понимаю в чем ваше утверждение или вопрос :) В семплировании Томпсона мы предполагаем, что распределение биноминомиальное (сопряжённым к которому является бета-распределение). Вы это имели ввиду? Семплирование по Томпсону и есть байесовский метод, один из самых простых и понятных.


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

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

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

            Когда-то я потратил кучу времени, безуспешно пытаясь модифицировать алгоритм Томпсона под заданные требования. Смотрел другие статьи, в которых все получалось и шикарно работало. Потом, спустя довольно долгое время, до меня дошло, что среда в которой должен работать агент на самом деле является пространством гипотез, что иногда это пространство может быть уменьшено, а иногда все гипотезы могут быть объединены в одну «большую» гипотезу.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое