Рекомендательные системы

Рекомендательные системы с использованием LinUCB: контекстный подход многорукого бандита

Анализ контекстного подхода многорукого бандита к рекомендательным системам с использованием непересекающегося алгоритма LinUCB для максимального взаимодействия с пользователем

Что такое проблема многоруких бандитов?

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

Владелец бизнеса запускает алгоритм для первых 1000 пользователей, чтобы выбрать лучшую рекламу из 10 доступных рекламных объявлений, и после завершения пробного запуска решает показать лучшую рекламу остальным пользователям. Алгоритм оценивает лучшую рекламу на основе ее эффективности в пробном прогоне (первые 1000 пользователей)

Вот где мы начинаем думать. Достаточно ли ОДНОЙ рекламы для удовлетворения широкой и разнообразной аудитории?

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

Разведка VS Эксплуатация

Дилемма выбора между исследованием и эксплуатацией существует в различных аспектах жизни.

Допустим, вы идете в кафе-мороженое за углом и получаете свой любимый аромат - c шоколад. Вы не пробуете другие вкусы, потому что боитесь, что они могут вам не понравиться. Но есть также небольшая вероятность, что если вы попробуете новый аромат, скажем, бархатный, он вам может понравиться даже больше, чем шоколад. Важно найти баланс между опробованием новых вкусов (e xploration) и постоянным приобретением любимого (e xploitation).

Алгоритмы MAB должны найти точный компромисс между выбором случайной руки (которая может оказаться оптимальной рукой) или использованием ее истории для выбора того, что, по его мнению, является лучшей рукой (которая может быть просто неоптимальной рукой, потому что оптимальная рука, возможно, еще недостаточно изучена)

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

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

Алгоритм UCB

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

Алгоритм UCB выходит за рамки этого подхода и находит баланс между разведкой и эксплуатацией. Вот как это работает.

Алгоритм UCB отслеживает среднее вознаграждение для каждой руки до настоящего испытания, а также вычисляет верхнюю доверительную границу для каждой руки. Верхняя граница указывает на неопределенность нашей оценки потенциала руки.

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

Рассмотрим работающий алгоритм UCB с его текущими границами достоверности (пунктирные линии), как показано на рисунке ниже.

Несмотря на то, что зарегистрированное среднее вознаграждение, полученное для группы 3, выше, алгоритм выбирает группу 2 из-за неопределенности ее потенциала и обновляет ее доверительную границу для будущих испытаний.

Алгоритм UCB не принимает во внимание функции u ser и контента (контекст), которые могут включать исторические действия пользователя на агрегированном уровне, а также заявленную демографическую информацию.

LinUCB

Проблема эксплуатации / исследования для контекстных проблем MAB формализуется следующим образом:

Предполагается, что ожидаемый выигрыш руки линейен по его d-мерному вектору признаков X с некоторым неизвестным вектором коэффициентов theta.

Эта модель называется непересекающейся, поскольку параметры не являются общими для разных плеч. Чтобы найти вектор коэффициентов theta в приведенном выше уравнении, к обучающим данным применяется гребенчатая регрессия.

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

Цель алгоритма - максимизировать общее вознаграждение (общее количество кликов пользователей в долгосрочной перспективе).

Алгоритм формализован его авторами следующим образом:

Мы не останавливаемся на математике алгоритма, но сосредоточимся на результатах, которых я добился, моделируя алгоритм на стандартном наборе данных.

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

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

Алгоритм LinUCB отлично справляется с выбором руки в каждом испытании, и график ниже отражает то же самое. Он сравнивает максимально возможное достижимое вознаграждение для каждой руки с фактически полученным вознаграждением для каждой руки. Результаты показывают, что мы можем использовать каждую руку до 90% ее потенциала.

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

Алгоритмы CMAB сочетаются с различными методами фильтрации, основанными на предпочтениях пользователя, для получения еще более персонализированных рекомендаций.

РЕЗЮМЕ

Алгоритм LinUCB позволяет нам получить около 90% от общего возможного вознаграждения, что намного выше, чем у других алгоритмов MAB. Рекомендательные системы - это чрезвычайно важный пример использования, в котором вознаграждение обычно приводит к более высокому доходу, что является конечной целью бизнеса.

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА