Reinforcement Learning for Recommendations and Search

eugeneyan

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

Обучение с подкреплением для рекомендаций и поиска

[ teardown recsys deeplearning ] · 13 мин чтения

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

Во-первых, они спроектированы так, чтобы максимизировать сиюминутную награду — заставить пользователей кликнуть или совершить покупку, — и не учитывают долгосрочные награды, такие как активность пользователя. Кроме того, они склонны к жадному подходу и переоценивают популярность товаров, пренебрегая исследованием новых объектов (т. е. проблема холодного старта). Наконец, они плохо работают, когда часто добавляются новые объекты (например, новостные статьи, TikTok/YouTube и т. д.).

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

Контекстные бандиты: многорукие бандиты с контекстом

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

Контекстные бандиты идут на шаг дальше — они собирают и наблюдают контекст перед каждым действием и выбирают действия на основе контекста. Они изучают, как действия и контекст влияют на награду. В случае рекомендаций и поиска контекстом будут данные о клиенте (например, демография, устройство, указанные/исторические предпочтения) и окружении (например, день недели, время суток).

Yahoo рассказали об использовании контекстного бандита для рекомендации новостных статей. В то время как обычные бандиты обучаются только на признаках, специфичных для каждой руки (т. е. раздельные линейные модели), их подход использует признаки — такие как кросс-признаки пользователь-статья, — которые являются общими для всех рук (т. е. гибридные линейные модели). Эксперименты показали, что это позволило информации о click-through rate одной статьи быть изученной и применённой к другим статьям (т. е. трансферное обучение) — что было невозможно с раздельными линейными моделями.

В качестве признаков пользователи были представлены 1193 категориальными признаками, включая демографию (возраст, пол), географию (местоположения, штаты США) и поведение (бинарные категории, обобщающие историю потребления новостей). Новостные статьи были представлены 83 категориальными признаками, такими как категория URL (выведенная из URL) и редакторские категории (вручную размеченные редакторами-людьми).

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

Оценка была непростой, поскольку у них были только офлайн-данные, собранные с помощью другой политики (т. е. на момент сбора данных в продакшене работал другой рекомендатель, т. е. off-policy оценка). Поэтому они предположили, что отдельные события независимы и одинаково распределены, и что политика, использованная для сбора логированных данных, выбирала каждую руку равномерно случайным образом. (У них была «обучающая корзина», в которую случайным образом попадали некоторые пользователи. Пользователям в обучающей корзине статьи показывались случайным образом.)

Их оценщик политики принимает на вход обученную политику и логированную политику. Если обученная политика выбрала ту же руку, что и логированная политика, событие сохраняется и добавляется в историю, а выигрыш обновляется. Если обученная политика выбирает другую руку, то событие игнорируется, и алгоритм переходит к следующему событию без какого-либо изменения состояния.

Netflix также использовали контекстные бандиты для персонализации изображений фильмов на главной странице. Почему контекстные бандиты? Они объяснили, что пакетные подходы машинного обучения требуют времени на сбор данных, обучение модели и AB-тестирование, в течение которого участники не получают улучшенного опыта (т. е. сожаление). Чтобы снизить сожаление, они перешли к онлайн-машинному обучению и приняли контекстные бандиты, чтобы непрерывно исследовать и узнавать лучшую рекомендацию для каждого клиента.

Они начали с (неконтекстного) многорукого бандита, чтобы найти единственную лучшую обложку для всех пользователей. Затем они перешли к контекстным бандитам, чтобы персонализировать изображения для каждого пользователя. Бандит может выбирать из набора изображений для каждого шоу (т. е. действие) и наблюдать количество минут, которое пользователь смотрел шоу после показа изображения (т. е. награда). У него также есть информация об атрибутах пользователя (например, просмотренные тайтлы, просмотренные жанры, страна, языковые предпочтения), дне недели, времени суток и т. д. (т. е. контекст).

Они рассказали о нескольких моделях бандитов, таких как жадная политика (через регрессионную модель с учителем), epsilon-greedy, LinUCB и сэмплирование Томпсона, но не уточнили, какая использовалась в продакшене (вероятно, ансамбль или что-то, что часто обновляется). Подход к оценке был похож на подход Yahoo — я писал об этом подробнее здесь.

Value-based: изучение ценности для каждой пары состояние-действие

В обучении с подкреплением value-based методы изучают оптимальную функцию ценности. Это либо функция состояния (отображающая состояние в ценность), либо функция состояния-действия (отображающая состояние-действие в ценность). Используя функцию ценности, агент действует, выбирая действие с наивысшей ценностью в каждом состоянии

JD рассказали об использовании глубоких Q-сетей (DQN) и негативной обратной связи для рекомендаций в e-commerce. Они отметили, что объекты, которые пользователи пропускают (т. е. не кликают), несут полезный сигнал о предпочтениях пользователя и также должны учитываться в рекомендательных системах — система, работающая только с позитивными объектами, не изменит своё состояние и не обновит стратегию, когда пользователи пропускают рекомендованные объекты.

Поэтому они определили состояние своего марковского процесса принятия решений (MDP) так, чтобы включить негативные объекты. Их MDP имеет два отдельных состояния: State+ (предыдущие N объектов, которые пользователи кликнули или купили) и State- (предыдущие N объектов, которые пользователи пропустили). Что касается перехода, если пользователи кликают/покупают рекомендованный объект, обновляется State+, но не State-; если пользователи пропускают объект, обновляется State-, но не State+.

В качестве входа для DQN управляемые рекуррентные блоки (GRU) кодируют последовательность позитивных и негативных событий в эмбеддинги S+ и S-. Затем эти эмбеддинги конкатенируются с кандидатом-объектом (a). Первые несколько скрытых слоёв (для S+ и S-) разделены; интуиция в том, что мы хотим рекомендовать объекты, похожие на кликнутые/купленные, но отличающиеся от пропущенных. Таким образом, разделение первых скрытых слоёв помогает уловить различный вклад позитивной и негативной обратной связи.

DQN от JD для рекомендации объектов на основе позитивных и негативных событий (источник)

Чтобы снизить вычислительные затраты, у них есть предварительный шаг отбора кандидатов, который сокращает пространство поиска. Кандидаты выбираются путём поиска N наиболее похожих объектов для последних M объектов, которые пользователи кликнули и купили. Затем эти кандидаты передаются в DQN как потенциальные действия для ранжирования.

Microsoft также приняли DQN для рекомендаций новостей. В качестве признаков у них были:

Признаки новостей: 417 one-hot признаков, таких как провайдер, ранжирование, имя сущности, категория, тематическая категория и историческое число кликов. Признаки пользователя: атрибуты признаков, на которые пользователи кликали за последний 1 час, 6 часов, 24 часа, 1 неделю и 1 год, в сумме 413 x 5 = 2065 признаков. Признаки пользователь-новость: 25 признаков, описывающих взаимодействие между пользователем и конкретной новостью (например, частота сущности, категории, темы, провайдера). Контекстные признаки: 32 признака, такие как время, день, свежесть новости (время между рекомендацией и публикацией новости)

DQN различает четыре типа признаков. Признаки пользователя и контекста считаются признаками состояния, тогда как все признаки считаются признаками действия. Интуиция в том, что награда за совершение действия связана со всеми признаками, тогда как награда, относящаяся к атрибутам пользователя, зависит только от признаков пользователя и контекста. Таким образом, Q-функция делится на функцию ценности (только признаки состояния) и функцию преимущества (все признаки).

DQN от Microsoft для рекомендаций новостей (источник)

Что касается награды, они объединили (сиюминутную) награду на основе кликов и (долгосрочную) награду за активность пользователя. Они рассудили, что метрики кликов — лишь часть обратной связи пользователя, и что рекомендательные системы также должны учитывать, вернётся ли пользователь в приложение. Активность пользователя моделировалась с помощью моделей выживаемости и объединялась с наградой за клики для получения суммарной награды. Тем не менее награда за активность пользователя имела низкий вес 0.05.

Для исследования они применили dueling bandit gradient descent. Используются две сети для создания рекомендаций: текущая сеть Q и сеть исследования Q’. Веса Q’ получаются добавлением некоторого шума к весам Q. Рекомендации от Q и Q’ затем чередуются перед показом пользователям. Если объекты, рекомендованные Q’, получают лучшую обратную связь, агент обновляет Q в сторону Q’. В противном случае Q остаётся неизменной.

Исследование через Dueling Bandit Gradient Descent (источник)

В качестве последнего примера рассмотрим использование ByteDance отдельных DQN для рекомендаций и рекламы. Они использовали двухуровневую структуру для совместной оптимизации рекомендаций и рекламы. Первый уровень генерирует список рекомендаций для оптимизации пользовательского опыта в долгосрочной перспективе. Второй уровень вставляет рекламу в список рекомендаций, чтобы сбалансировать сиюминутный рекламный доход и негативное влияние рекламы на долгосрочный пользовательский опыт.

Их рекомендательный DQN рассматривает историю просмотров объектов и рекламы по отдельности. Эти последовательности объектов и рекламы проходят через два GRU, чтобы закодировать предпочтения по рекомендациям и рекламе (подобно подходу JD), прежде чем конкатенироваться с контекстом (например, версия приложения, операционная система, тип ленты) — это представляет состояние. Потенциальные действия (т. е. рекомендации объектов) представлены через эмбеддинги. Получив состояние и список возможных действий, DQN выдаёт Q-значение каждой пары состояние-действие.

Каскадный DQN от ByteDance для рекомендаций (источник)

Рекламный DQN сложнее. Он должен вернуть три выхода: включать ли рекламу, какую рекламу вставить и в какую позицию её вставить. Однако эти выходы взаимозависимы, и традиционный DQN не сработал бы. Поэтому они разработали новый DQN, который выдаёт Q-значение, специфичное для рекламы, для всех возможных позиций. Они также добавили ещё один элемент в финальном слое (index=0), чтобы представить Q-значение невставки рекламы. Такая конструкция позволяет DQN учитывать состояние и действие и возвращать все три выхода за один проход.

DQN от ByteDance для рекламы (источник)

Рекламный DQN использует тот же метод, что и рекомендательный DQN, для получения состояния (через GRU на последовательностях объектов и рекламы). Выход рекомендательного DQN также включается в состояние (рекламного DQN). Потенциальная реклама представлена через эмбеддинги.

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

Policy-based: прямое изучение действий для каждого состояния

По сравнению с value-based методами, policy-based методы изучают функцию политики, которая напрямую отображает состояние в действие, без необходимости изучать Q-значения. В результате они работают лучше в непрерывных и стохастических средах (т. е. без дискретных состояний или действий) и обычно более стабильны при достаточно малой скорости обучения.

Google рассказали об использовании REINFORCE для рекомендаций YouTube. Входом служит последовательность исторических взаимодействий пользователя, а выход предсказывает следующее действие (т. е. какое видео рекомендовать).

Для основной политики (π) входная последовательность эмбеддится через RNN. Они пробовали разные RNN (например, LSTM, GRU) и в итоге использовали Chaos Free RNN из-за её стабильности и вычислительной эффективности. RNN принимает последовательность событий пользователя вплоть до шага t и кодирует её в состояние пользователя для следующего шага (t+1). Затем это конкатенируется с контекстом шага t+1.

Финальный слой softmax предсказывает вероятность каждого действия (т. е. видео для рекомендации) — это похоже на предыдущую реализацию, в которой также был выходной слой softmax. Учитывая, что softmax содержит миллионы возможных действий, во время обучения они применяют sampled softmax. Во время обслуживания применяется приближённый поиск ближайших соседей (ANN) для извлечения топ-действий.

Основная политика REINFORCE от Google с отдельной головой поведенческой политики (источник)

Они также оценивают поведенческую политику (β). Они указывают на трудность прямого логирования поведенческой политики, поскольку в их системе несколько агентов. Поэтому для каждой пары состояние-действие поведенческая голова оценивает вероятность того, что смесь поведенческих политик выберет это действие, используя ещё один softmax. Как видно из рисунка выше, они переиспользуют состояние пользователя и моделируют поведенческую политику с помощью отдельной головы. Чтобы поведенческая голова не вмешивалась в состояние пользователя основной политики π, они блокируют обратное распространение градиента в RNN.

Для минимизации негативного влияния на пользовательский опыт использовалось исследование по Больцману. Они отметили, что грубое исследование (например, e-greedy) было неприменимо, так как могло привести к неуместным рекомендациям и плохому пользовательскому опыту. После извлечения топ-M кандидатов через ANN логиты (немасштабированные расстояния?) подаются в меньший softmax для нормализации вероятностей перед сэмплированием из распределения. Исследование и эксплуатация балансируются путём рекомендации топ-K наиболее вероятных объектов и сэмплирования остальных из оставшихся M - K объектов.

Actor-Critic: объединение value-based и policy-based

Actor-critic объединяет лучшее из value-based и policy-based методов, разделяя модель на две: одну для вычисления действия на основе состояния, и другую для получения Q-значения состояния-действия. (Policy-based) актор принимает состояние на вход и выдаёт лучшее действие, изучая оптимальную политику и управляя тем, как ведёт себя агент. (Value-based) критик затем оценивает действие, вычисляя функцию ценности и предоставляя актору обратную связь о том, насколько хорошо действие.

Мне встретилось несколько примеров использования actor-critic в рекомендациях и поиске. Мы не будем обсуждать их в этой статье, и я рекомендую вам ознакомиться с ними по мере необходимости.

Использование Alibaba actor-critic для выбора лучшей функции ранжирования для поискового запроса. Использование Baidu двух акторов — одного для рекомендаций на главной странице и одного для рекомендаций на странице деталей. Использование JD actor-critic для постраничных рекомендаций

Заключение

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

Тем не менее, независимо от того, какой подход вы выберете, уделите особое внимание тому, как выполняется off-policy оценка — наличие правильной системы оценки значит больше половины успеха. Вот хороший туториал по counterfactual-оценке. Также см. эту статью о парадоксе Симпсона в офлайн-оценке для рекомендаций.

Я что-то упустил? Пожалуйста, напишите мне!

У традиционных RecSys есть недостатки, такие как:• Максимизация краткосрочной (клики) награды в ущерб долгосрочной• Переоценка популярности объектов и отсутствие исследования• Неспособность угнаться за частым появлением новых объектов (новости, TikTok)Давайте разберём, как может помочь обучение с подкреплением.https://t.co/DfZamMhOfd— Eugene Yan (@eugeneyan) 8 сентября 2021

Ссылки

A Contextual-Bandit Approach to Personalized News Article Recommendation Selecting the best artwork for videos through A/B testing Artwork Personalization at Netflix Recommendations with Negative Feedback via Deep Reinforcement Learning DRN: A Deep Reinforcement Learning Framework for News Recommendation Jointly Learning to Recommend and Advertise Top-K Off-Policy Correction for a REINFORCE Recommender System A recurrent neural network without chaos Deep Neural Networks for YouTube Recommendations Reinforcement Learning to Rank in E-Commerce Search Engine Whole-Chain Recommendations Deep Reinforcement Learning for Page-wise Recommendations SIGIR 2016 Tutorial on Counterfactual Evaluation and Learning The Simpson’s Paradox in the Offline Evaluation of Recommendation Systems

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

Yan, Ziyou. (Sep 2021). Reinforcement Learning for Recommendations and Search. eugeneyan.com. https://eugeneyan.com/writing/reinforcement-learning-for-recsys-and-search/.

или

@article{yan2021reinforcement, title = {Reinforcement Learning for Recommendations and Search}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2021}, month = {Sep}, url = {https://eugeneyan.com/writing/reinforcement-learning-for-recsys-and-search/} }

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