Bandits for Recommender Systems

eugeneyan

Начните здесь Статьи Выступления Прототипирование О себе

Бандиты для рекомендательных систем

[ teardown recsys machinelearning ] · чтение на 14 мин

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

Бандиты решают эту проблему, моделируя неопределённость и исследование. Признавая неопределённость в данных и целенаправленно исследуя, чтобы её снизить, бандиты узнают о релевантности неисследованных объектов.

Это особенно применимо, когда набор объектов быстро меняется — например, для новостей, рекламы и твитов — или когда поток трафика мал. Если новые объекты постоянно добавляются, ожидание сбора пакета данных перед переобучением модели может оказаться слишком медленным. Бандиты хорошо подходят, поскольку они могут инкрементально обновляться на новых данных и адаптивно концентрироваться на объектах с более высокой наградой. Это снижает сожаление (regret) — упущенную выгоду от рекомендации неоптимальных объектов.

ε-greedy, UCB и Thompson Sampling

Мы кратко обсудим три основных алгоритма бандитов, прежде чем рассмотреть промышленные реализации каждого из них. Вот несколько терминов, которые я использую на протяжении статьи: (i) действие/рука (action/arm): кандидаты на рекомендацию, (ii) награда (reward): взаимодействие клиента в рамках одной попытки, например клик или покупка, (iii) ценность (value): оценочная долгосрочная награда руки за множество попыток, и (iv) политика (policy): алгоритм/агент, выбирающий действия на основе изученных ценностей.

ε-greedy — это классический алгоритм бандита. На каждой попытке он с вероятностью ε случайно выбирает действие и с вероятностью 1 - ε жадно выбирает действие с наибольшей ценностью. Мы балансируем компромисс между исследованием и эксплуатацией через параметр ε. Более высокое ε ведёт к большему исследованию, а более низкое ε — к большей эксплуатации. Однако ε-greedy может исследовать дольше, чем необходимо (хотя это можно смягчить, уменьшая ε со временем). Другой недостаток в том, что ε-greedy не подсказывает, какие объекты исследовать, и по умолчанию исследует все объекты равномерно случайно.

Upper Confidence Bound (UCB) учитывает неопределённость руки и выбирает руки с наибольшим потенциалом. Неопределённость моделируется через доверительные границы, а потенциал представлен верхней доверительной границей (отсюда и название алгоритма). Из-за принципа своей работы UCB часто называют «оптимизмом перед лицом неопределённости».

Пример UCB с часто пробуемой рукой (зелёная) и редко пробуемой рукой (красная)

На изображении выше Qₜ(a) — это оценочная ценность руки a на шаге времени t, Nₜ(a) — число раз, когда рука a была выбрана, а c — параметр уверенности (по умолчанию равен 1). Зелёная рука выбиралась часто и потому имеет более узкие доверительные границы. Напротив, красная рука выбиралась не так часто и потому имеет более широкие доверительные границы. При выборе действия, хотя зелёная рука имеет более высокую оценочную ценность, у красной руки выше UCB, и потому выбирается именно она. По мере того как красная рука выбирается чаще, её доверительные границы сужаются. Если оценочная ценность останется прежней, её UCB снизится ниже UCB зелёной руки, и будет выбрана зелёная рука.

Thompson Sampling моделирует неопределённость, строя распределение вероятностей по историческим наградам, а затем сэмплирует из этого распределения при выборе действий. В простом случае, когда награды бинарны, используется бета-распределение. Бета-распределение принимает два параметра, α и β, и среднее значение распределения равно α/α + β, что можно представить как успехи / успехи + неудачи. Чтобы выбрать действие, мы сэмплируем из бета-распределения каждой руки и выбираем руку с наибольшими сэмплированными значениями.

Бета-распределения, которые сужаются по мере роста α и β

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

Отраслевые примеры бандитов для recsys

Пример ε-greedy — это recplanations у Spotify (рекомендация объяснений к музыкальным рекомендациям). Они выбрали ε-greedy за простоту реализации в продакшене и propensity scoring. Чтобы ограничить негативное влияние исследования на пользовательский опыт, они заранее отбирают 100 наиболее релевантных объектов для исследования. Эти 100 объектов отбираются отдельной моделью на основе эмбеддингов, которая улавливает предпочтения пользователя, аналогично этапу отбора кандидатов из статьи YouTube.

Другой пример — ранжировщик на многоруких бандитах от Schibsted, который переранжирует объекты-кандидаты от нескольких субрекомендателей. К каждому переранжируемому входу добавляется 5% случайных объектов, чтобы избежать локальных минимумов во время обучения.

Классический пример UCB — это LinUCB от Yahoo для рекомендации новостей. Гребневая регрессия (ridge regression) обучается оценивать награду линейно по признакам руки. Затем UCB выводится сложением предсказанной награды и стандартного отклонения гребневой регрессии. Гибридная версия LinUCB также использует признаки, общие для всех рук (например, категорию новости), и эксперименты показали, что общие признаки позволяли извлекать и эксплуатировать информацию о CTR сразу по нескольким новостным статьям.

Другой пример — LinUCB от Alibaba для рекомендации объектов, где они применили модель просмотра пользователем, чтобы добавить позиционные веса. Цель состояла в устранении позиционного смещения (position bias), которое сильно влияет на вовлечённость пользователя, особенно на мобильных поверхностях. Позиционные веса моделировали вероятность рассмотрения, и награды для каждой руки обновляются с учётом как признаков руки, так и вероятности рассмотрения. Аналогично применяется гребневая регрессия, а стандартное отклонение используется для вычисления UCB.

Пример Thompson Sampling — это бандиты от Doordash для рекомендации кухонь. Предпочтения пользователя к кухне моделируются через Beta(α=число заказов этой кухни, β=число заказов других кухонь). При выборе набора фильтров кухонь для показа на странице исследования значение для каждой кухни сэмплируется из её бета-распределения. Затем эти значения сортируются по убыванию, чтобы отобрать топовые кухни для показа.

Другой пример — бандит на Thompson Sampling от Yahoo для рекомендации рекламы и новостей. Чтобы предсказать награду (то есть CTR) рекламы или новостной статьи, они обучили регуляризованную модель логистической регрессии. Затем, чтобы смоделировать неопределённость, апостериорное распределение весов модели представляется гауссовыми распределениями. На каждой попытке каждый вес независимо извлекается из своего гауссова апостериорного распределения перед тем, как использоваться для предсказания награды действия.

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

Неопределённость можно также моделировать методами глубокого обучения. Бандит на глубоком обучении от Twitter для рекомендации рекламы рассматривал два подхода: бутстрэппинг и дропаут.

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

Дропаут моделирует неопределённость, заставляя сеть предсказывать ценность действия через множество прямых проходов с разными dropout-юнитами. Это сродни сэмплированию из апостериорного распределения. Слой дропаута выступает в роли голов многоголовой сети.

Байесовский бандит от Twitter, который моделирует неопределённость через предпоследний слой дропаута

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

Уроки применения бандитов в индустрии

Во-первых, UCB и Thompson Sampling превосходят ε-greedy. По умолчанию ε-greedy не направлен и выбирает действия равномерно случайно. Напротив, UCB и Thompson Sampling направляются доверительными границами и распределениями вероятностей, которые сужаются по мере того, как действие пробуется чаще. В результате, поскольку UCB и Thompson Sampling разумно исследуют руки с большей неопределённостью, у них ниже сожаление (regret).

Во-вторых, при отложенной обратной связи Thompson Sampling превосходит UCB. Отложенная обратная связь, когда взаимодействия пользователя с объектами обрабатываются не сразу, характерна для большинства реальных систем из-за ограничений по ресурсам и времени выполнения. В этой ситуации, поскольку UCB выбирает руки детерминированно, он выбирает одно и то же действие, пока не будет учтена новая обратная связь. Напротив, поскольку Thompson Sampling выбирает действия стохастически, сэмплируя из апостериорного распределения, он рандомизирует выбор действий даже без обновлённых наград. Оценка Thompson Sampling от Yahoo и музыкальный бандит Deezer отметили, что это приводило к более широкому исследованию и, как следствие, к лучшим результатам.

Чтобы дополнительно изучить влияние отложенных наград, Yahoo смоделировали разные задержки обновления — 10, 30 и 60 минут. Thompson Sampling был конкурентоспособен при всех задержках. С другой стороны, хотя UCB превосходил Thompson Sampling при короткой задержке (10 минут), он показывал себя хуже Thompson Sampling, когда задержка возрастала до 30 и 60 минут. В целом это говорит о том, что стохастические политики более устойчивы к задержке, поскольку продолжают исследование даже без обновлённых наград.

В-третьих, способ инициализации бандита имеет значение. Deezer обнаружили, что пессимистичная инициализация работает лучше наивной. Для Thompson Sampling они экспериментировали с наивной инициализацией, где априорным распределением было Beta(1, 1), и пессимистичной инициализацией, где априорным распределением было Beta(1, 99). Аналогичная наивная и пессимистичная инициализация была применена для UCB. Они обнаружили, что пессимистичная инициализация работает лучше из-за более низких априорных вероятностей, которые точнее отражали реальную награду.

Исследование новых объектов — два варианта

Те немногие статьи, что обсуждали исследование, применяли два основных подхода: (i) обширное исследование на ограниченном наборе пользователей против (ii) небольшого исследования на всех пользователях.

Для первого Yahoo использует бакет исследования, в который пользователи отбираются случайным образом. Пользователям в бакете исследования затем показываются новостные статьи равномерно случайно. Аналогично, у Twitter есть политика случайной рекламы, обслуживающая 1% продакшен-трафика.

Для второго Netflix тестирует новые обложки на всех пользователях («… сожаление от исследования обычно очень мало и амортизируется по всей нашей огромной базе участников, при этом каждый участник неявно помогает давать обратную связь по обложкам для небольшой части каталога»). Аналогично, Schibsted добавляет 5% случайных объектов к каждому входу своего ранжировщика на бандитах.

Борьба с проклятием размерности

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

Yahoo решили это, применив PCA для снижения размерности перед обучением политики через LinUCB. Они начали с 1,2 тыс. пользовательских признаков (например, демография, геолокация и поведение). У них также было 83 признака статей на основе категорий URL и редакторских категорий. Для сокращения признаков они спроецировали пользовательские признаки на признаки статей, а затем кластеризовали пользователей на пять групп, где пользователи в каждой группе имели схожие предпочтения. Это сократило 1,2 тыс. пользовательских признаков до пяти признаков. Признаки статей были сокращены аналогичным образом.

Deezer сравнили представление пользователей в виде кластеров (полуперсонализация) против пользовательских признаков (полная персонализация). Для полуперсонализации пользователи были кластеризованы на 100 групп методом k-means по прошлому поведению. Это дало кластеры пользователей со схожими музыкальными вкусами. Затем они обучили отдельного бандита для каждого кластера. Для полной персонализации пользователи представлялись через 97-мерный вектор, который обобщает предпочтения пользователя по жанрам, настроениям, странам и т. д. Вектор был получен факторизацией матрицы взаимодействий пользователь-песня. Затем они обучили контекстного бандита на этих пользовательских признаках.

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

«Тёплый старт» бандитов для лучшего пользовательского опыта

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

Doordash рассказали, как они выполняют тёплый старт своих бандитов по кухням через данные более высокого регионального уровня. Для каждой кухни они изучают политику бандита на нескольких уровнях (то есть региональном, субрегиональном, пользовательском). Бандит верхнего уровня инициализируется как Beta(α=1, β=1). Затем для каждого бандита более низкого уровня они обновляют α, прибавляя среднее число заказов этой кухни (на данном уровне), и обновляют β, прибавляя среднее число заказов других кухонь (на данном уровне). Наконец, для бандита пользовательского уровня α и β обновляются данными о заказах самого пользователя. В результате бандит по кухням для нового пользователя получает тёплый старт на данных маркетплейса более высокого уровня, прежде чем каждый новый заказ обновит бандита его персональными предпочтениями.

Другой подход — выполнить тёплый старт пользовательских предпочтений на данных, собранных через случайную политику. Yahoo изучили CTR-оценки, специфичные для пользователя (на случайных данных), которые затем добавлялись к контекстно-независимым CTR-оценкам для рекомендации новостей. Они обнаружили, что бандиты с тёплым стартом на данных о предпочтениях пользователей смогли обойти контекстно-независимых бандитов.

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

Данные, собранные через жадную политику, также могут быть полезны для тёплого старта. Twitter выполнил тёплый старт своего бандита на данных, собранных жадной политикой, и обнаружил, что тёплый старт на большем числе эпох (500 против 100) приводил к улучшению метрик на тестовом наборе.

Оценка бандитов через off-policy evaluation

Несколько реализаций бандитов (например, Netflix, Yahoo) ссылаются на метод replay от Li et al. для оценки вне политики (off-policy evaluation). Replay предполагает, что (i) отдельные события независимы и одинаково распределены и (ii) логирующая политика выбирала каждую руку равномерно случайно. Далее в статье говорится, что второе предположение можно ослабить, так что может использоваться любая рандомизированная политика — не только равномерно случайная. (Насколько я понимаю, случайность необходима для достаточного покрытия (support), и потому равномерная случайность строго не обязательна.)

Во время оценки replay принимает на вход новую политику (которую нужно оценить) и события залогированной политики. Если новая политика выбирает то же действие, что и залогированная политика, событие добавляется в историю и награда обновляется. Если нет, событие игнорируется без обновления награды. (Контрфактическая оценка через Inverse Propensity Scoring — ещё одна альтернатива.)

Как off-policy оценка бандитов соотносится с типичной оценкой обучения с учителем на залогированных данных? Статья Twitter даёт некоторое понимание. Они вычислили два набора метрик: (i) PR-AUC на стандартном тестовом наборе и (ii) улучшения CTR против случайной политики. Между PR-AUC и CTR наблюдался компромисс.

Хотя жадная политика показала хорошие результаты по PR-AUC, по CTR она показала себя относительно плохо. И наоборот, политики бандитов, такие как UCB и Thompson Sampling, показали себя хуже по PR-AUC, но превзошли жадную политику по CTR. Это демонстрирует расхождение, при котором обучение с учителем, которое хорошо оценивается на смещённых залогированных данных по традиционным метрикам, может на деле работать плохо по тем метрикам, которые нас действительно волнуют (например, CTR, конверсия).

• • •

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

Знаете ли вы другие промышленные реализации рекомендательных систем на основе бандитов? Пожалуйста, поделитесь ими в комментариях ниже!

Ссылки

Artwork Personalization at Netflix Personalized Cuisine Filter A Contextual-Bandit Approach to Personalized News Article Learning from Logged Implicit Exploration Data Explore, Exploit, and Explain: Personalizing Explainable Recommendations Bandit based Optimization of Multiple Objectives on a Music Streaming Platform Carousel Personalization in Music Streaming Apps with Contextual Bandits Contextual User Browsing Bandits for Mobile Recommendations An Efficient Bandit Algorithm for Realtime Multivariate Optimization Deep Bayesian Bandits: Exploring in Online Personalized Recommendations Deep Neural Network Marketplace Recommenders in Online Experiments An Empirical Evaluation of Thompson Sampling Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms

Если вы нашли это полезным, пожалуйста, цитируйте эту статью так:

Yan, Ziyou. (Май 2022). Bandits for Recommender Systems. eugeneyan.com. https://eugeneyan.com/writing/bandits/.

или

@article{yan2022bandit, title = {Bandits for Recommender Systems}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2022}, month = {May}, url = {https://eugeneyan.com/writing/bandits/} }

Присоединяйтесь к 11 800+ читателям, получающим обновления о машинном обучении, RecSys, LLM и инженерии.