При работе с алгоритмами есть две реальности: как это написано в учебнике и как это получается у тебя. Второе ближе к телу, и хочется, чтобы оно получалось. Главное, понимать, что ты работаешь не с оригинальной модельной задачей; в твоём проде есть особенности, которые могут мешать тебе достичь результата. И я хочу рассказать о нескольких нюансах в запуске многоруких бандитов.
Поскольку цель как можно проще объяснить почему мог не завестись выбранный алгоритм бандитов, я предполагаю, что ты уже вкурсе что это такое и какими методами их решают. Например, можно посмотреть здесь, ну или заглянуть на вики.
Сперва немного контекста. У меня на проекте нужно было отранжировать видео-новости которые предлагались пользователю. При этом нужно увеличить основные показатели, такие как количество просмотренных роликов или общее время пользователя, но мы заметили, что активация пользователей существенно низкая. Следовательно, увеличение CTR могло бы поднять нужные нам метрики. Здесь и было принято решение, что нам нужно поработать с многоруким бандитами.
Бандиты могут применяться не только в задаче ранжирования потока видео-новостей. Ты можешь выбирать статьи, товары, оптимизировать рекламу и много чего еще, поэтому я постараюсь давать описания без привязки к своей задаче, но для некоторых примеров это будет просто удобно.
Итак, как только определился с метрикой и понимаешь, что улучшать ее, скорее всего, будешь через многоруких бандитов. Здесь есть три стратегии:
Большинство разработчиков останавливаются на 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. Я опишу только один из методов, на мой взгляд, менее затратный с точки зрения реализации.
Суть в том, чтобы использовать биас при сэмплировании рангов для документов. Мы пользуемся формулой:
Здесь
То есть суть модификации только в биасе, а если наложить несколько ограничений, то мы сможем даже его вычислить напрямую.
Во-первых, нам надо разделить весь контент на свежий (холодный), который к нам пришел, и тот, который мы уже знаем и по которому есть статистика (прогретый). Поясню: холодным для нас будет любой контент, по которому мы знаем менее
Во-вторых, биас будем вычислять только для холодного контента, то есть для прогретого с
Обозначим как
Биас для холодных документов вычисляется по формуле:
Как выводится эта формула. В случае
Итак, конечная модификация алгоритма такая:
Как видишь, мы остаемся в рамках Thompson sampling, однако с помощью небольшой модификации создаём трамплин для новых документов. В алгоритме появились два новых параметра
Apple возобновила переговоры с OpenAI о возможности внедрения ИИ-технологий в iOS 18, на основе данной операционной системы будут работать новые…
Конкурсный управляющий российской «дочки» Google подготовил 23 иска к участникам рекламного рынка. Общая сумма исков составляет 16 млрд рублей –…
Google завершил обновление основного алгоритма March 2024 Core Update. Раскатка обновлений была завершена 19 апреля, но сообщил об этом поисковик…
У частных продавцов на Авито появилась возможность составлять текст объявлений с помощью нейросети. Новый функционал доступен в категории «Обувь, одежда,…
24 апреля 2024 года в Москве состоялась церемония вручения наград международного конкурса Workspace Digital Awards. В этом году участниками стали…
27 июня Яндекс проведет гик-фестиваль Young Con для студентов и молодых специалистов, которые интересуются технологиями и хотят работать в IT.…