В соавторстве с Шубха Шедтикере и Шьям Сандер.

1. Введение

Платформа Swiggy Ads поддерживает рекламу партнеров-ресторанов и различных партнеров-брендов FMCG/не FMCG в разных сферах бизнеса (еда, Instamart, мясо). С миллионами клиентов, взаимодействующих с приложением каждый день по всей Индии, оно дает возможность нашим рекламным партнерам охватить широкую аудиторию в разных регионах. Системы рекомендаций Ads основаны на алгоритмах релевантности и ранжирования, основанных на науке о данных, и предоставляют персонализированные рекомендации. Это помогает клиентам находить подходящие рестораны/бренды и, наоборот, помогает рекламным партнерам ориентироваться на соответствующую аудиторию. Эти алгоритмы ранжирования, как правило, представляют собой модели машинного обучения, которые обучаются на исторических данных о взаимодействии с клиентами/транзакциях и оптимизируются с учетом рейтинга кликов.

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

С другой стороны, алгоритмы Multi-Armed Bandit (MAB), также известные как алгоритмы K-Armed Bandit, обеспечивают принципиальный способ компромисса между исследованием (понимание пользовательских предпочтений с помощью новых рекомендаций) и эксплуатацией (рекомендации на основе исторических предпочтений). . Проще говоря, алгоритму MAB предоставляется K различных вариантов (также известных как руки) на выбор, и каждый вариант связан с наградой, которая неизвестна алгоритму и раскрывается алгоритму после выбор руки. В частности, в нашем случае рекомендатель на основе MAB будет рекомендовать конкретного рекламного партнера данному клиенту. Как только впечатление произведено, алгоритм наблюдает за вознаграждением, возможно, получение клика будет вознаграждением. Предположим, что клиент нажимает на показ, а затем, когда клиент войдет в приложение в следующий раз, должен ли алгоритм выбрать того же рекламного партнера, потому что клиент нажал ранее (эксплуатация), или должен ли алгоритм попробовать нового рекламного партнера (исследовать) для получить новую информацию? Алгоритмы MAB делают этот компромисс таким образом, что пытаются изучить (почти) лучший выбор, тратя минимум попыток на изучение вариантов.

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

В этой работе мы обсуждаем, как мы включили контекстные MAB для рекомендации рекламы партнеров по рекламе ресторанов. Эта схема применима и к другим рекомендациям.

Ниже приведены некоторые из основных проблем, связанных с внедрением контекстных бандитских алгоритмов в производство:

  • Оценка в режиме реального времени. Когда клиент входит в приложение, алгоритм ранжирования предоставляет «оценку релевантности» для каждого из рекламных партнеров, которые могут быть полезны клиенту. Эти оценки релевантности затем используются для ранжирования ресторанов. Если бы оценки релевантности вычислялись путем пакетного вывода для всех пар «клиент-ресторан» и передавались в систему рекомендаций посредством поиска в таблице, то многие из готовых библиотек бандитских алгоритмов, такие как Vowpal Wabbit, можно было использовать. Но проблема здесь в том, что с миллионами клиентов и десятками тысяч ресторанов-партнеров, размещающих рекламу каждый день (что приводит к подсчету сотен исправных партнеров на одного клиента), количество пар «клиент-ресторан», которые необходимо оценить, резко возрастает, что приводит к большие затраты на хранение. Чтобы преодолеть это, нам нужна система, способная делать выводы в реальном времени. В отличие от моделей машинного обучения, которые после обучения и развертывания будут использоваться для вывода, MAB представляют собой модели онлайн-обучения, которые постоянно обновляют параметры модели в зависимости от полученных вознаграждений. Следовательно, настройка инструментария для MAB в производстве для оценки в реальном времени не настолько проста. Кроме того, рекомендации по рекламе являются системой с малой задержкой, поэтому нам необходимо спроектировать наше решение таким образом, чтобы мы могли выполнять оценку в реальном времени с использованием алгоритмов MAB, соблюдая эти ограничения задержки.
  • Потребность в новых настраиваемых преобразователях данных.Преобразователи данных, например связанные с матричными операциями, которые необходимы для поддержки оценки в реальном времени с использованием алгоритмов MAB и соответствуют с нашей нынешней производственной системой не существовало. Следовательно, нам нужно было создать новые преобразователи данных для поддержки матричных операций.

В оставшейся части блога мы даем краткий обзор контекстных MAB и алгоритма LinUCB, а затем глубоко погружаемся в то, как мы разработали решение, создали пользовательские преобразователи данных и настроили инфраструктуру LinUCB в производственной среде, которая способна выполнять реальные задачи. вывод времени по шкале Swiggy.

2. Контекстная настройка MAB

Как указывалось во введении, алгоритмы Contextual MAB используют дополнительную информацию или контекст, доступные для выбора наилучшего действия/руки в каждом испытании. Вознаграждение в каждом испытании «t» зависит от контекста и выбранной руки. Цель алгоритма — максимизировать ожидаемое совокупное вознаграждение за T раундов/испытаний.

В одной из более простых версий контекстной настройки мы предполагаем линейную зависимость между ожидаемым значением вознаграждения и контекстом. Такие контекстные бандиты называются Linear Bandits.

В нашем случае мы формулируем рекомендацию рекламного ресторана на странице «Еда» в приложении Swiggy как задачу «Линейный бандит». Контекст — это информация о пользователе: его ранее заказанные рестораны на платформе, предпочтения в кухне, вегетарианская/невегетарианская близость, информация об устройстве, средняя стоимость заказа и т. д. Действие — это выбор полезного рекламного ресторана-партнера для отображения. Отзывы пользователей с точки зрения кликов/отсутствий кликов служат наградой. Для этого варианта использования мы рассматриваем бинарное вознаграждение: 0, если клика нет, 1, если клик есть. Цель здесь состоит в том, чтобы максимизировать общее количество кликов, полученных за испытания.

Мы формально определяем настройку Contextual MAB для нашего варианта использования, как показано ниже:

  1. Пробная версия. Каждый сеанс пользователя в приложении, в ходе которого пользователь видит рекламу ресторана, является пробной версией.
  2. Arm: в каждой пробной версии у нас есть набор подходящих ресторанов-партнеров по рекламе, которые нужно выбрать и отобразить. Каждый исправный ресторан-партнер по рекламе является Arm
  3. Контекст:в каждой пробной версии (сеансе клиента) для каждой ветви (ресторана) определяется вектор контекста, который обобщает информацию как отпользователя, так и от руки.
  4. Действие: выбор показа ресторана (руки) пользователю
  5. Вознаграждение. Мы определяем вознаграждение на основе отзывов пользователей; Вознаграждение определяется как +1, когда пользователь нажимает на ресторан, и 0, если ресторан произвел впечатление и не получил клика.
  6. Цель: максимизировать общее количество кликов в долгосрочнойсделке.

2.1 Алгоритм LinUCB

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

  1. Эмпирическая оценка среднего вознаграждения (подвига) и
  2. Термин, который обратно пропорционален количеству раз, когда рука была сыграна (исследование).

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

  1. как каждая рука оценивается в испытании и
  2. как параметры модели обновляются на основе отзывов клиентов (вознаграждения)

Полную информацию об алгоритме LinUCB можно найти в статье Контекстно-бандитский подход к рекомендации персонализированных новостных статей.

2.1.1 Подсчет очков

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

уравнение 1 показан этот показатель, который представлен суммой -

  1. Средняя оценка вознаграждения каждой руки (красный прямоугольник) и
  2. Соответствующее стандартное отклонение (синяя рамка), где α — гиперпараметр.

Чем выше α, тем шире становятся доверительные границы (стандартное отклонение). Таким образом, это приводит к тому, что больше внимания уделяется разведке, а не эксплуатации.

где
x (вектор) — контекст,
θ (вектор) и A (матрица) — параметры модели, изученные для каждой руки,
α (скаляр) — гиперпараметр, который управляет уровень разведки

2.1.2 Обновление параметров модели

После каждого испытания мы получаем отзывы о каждом ресторане, который произвел впечатление. Обратная связь (вознаграждение), как определено ранее, составляет +1 для ресторана, на который кликнули, и 0 для остальных.

LinUCB обновляет параметры модели — θ и A для каждого плеча в соответствии с приведенными ниже уравнениями —

Где x — контекст, а r — вознаграждение (1 или 0). Обновленные параметры модели, θ и A, теперь используются для оценки ресторанов в последующих испытаниях.

3. Настройка производства

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

3.1 Архитектура системы рекомендаций по рекламе

Ключевые компоненты рекомендательной системы Ads в Swiggy приведены ниже:

Рекламная платформа. Рекламная платформа включает в себя возможности для непрерывной поддержки жизненного цикла рекламы. Его уровень предварительного обслуживанияпозволяет создавать кампании и хранить сведения о кампании. Уровень показа объявлений лежит в основе системы рекомендаций по рекламе. Во время каждого клиентского сеанса он извлекает список обслуживаемых ресторанов, в которых проводится активная кампания, и дополняет этот список некоторыми сигналами в реальном времени, такими как предполагаемое время доставки заказа и т. д. Затем он вызывает механизм логического вывода в Data Science. Платформа (DSP) для получения оценки рейтинга (или релевантности) для каждого из ресторанов для данного клиента. Уровень показа рекламы возвращает отсортированный список ресторанов на основе оценки релевантности на уровень представления, который отображает эти показы рекламы в приложении. Платформа Ads также позволяет регистрировать эти показы объявлений и клики, которые затем могут обрабатываться на пост-обслуживающем уровне для целей выставления счетов. Эти зарегистрированные события также используются для построения функций и обучения моделей ранжирования.

Платформа обработки данных (DSP): Платформа обработки данных — это одна из основных возможностей Swiggy, обеспечивающая развертывание моделей и получение логических выводов в реальном времени в масштабе. Модели машинного обучения обучаются в среде Spark, а конвейеры моделей сериализуются в требуемый формат. Сериализованные конвейеры (обычно ZIP-файлы) загружаются и регистрируются в DSP через удобный для специалистов по данным интерфейс. Чтобы быть совместимым с нашим тяжелым стеком машинного обучения Spark, DSP поддерживает формат сериализации/десериализации MLeap. Затем эти модели машинного обучения развертываются в соответствующих производственных кластерах, где они десериализуются в объекты MLeap, которые запускаются в среде выполнения MLeap во время логического вывода. Всякий раз, когда от клиента (в данном случае уровня обслуживания рекламы) через конечную точку модели делается запрос логического вывода к DSP, механизм выполнения DSP извлекает необходимые функции из хранилища функций и предоставляет эти функции в качестве входных данных для конвейера модели MLeap. запускает модель и возвращает результат вызывающей стороне.

Магазин функций. Функции, необходимые для вывода моделей машинного обучения в режиме реального времени, обрабатываются с помощью заданий cron (обычно заданий Pyspark) и передаются в базы данных с быстрым доступом, такие как Redis/DynamoDB. Эти функции включают в себя различные атрибуты клиентов, атрибуты ресторана и атрибуты отношений между клиентом и рестораном, которые подготавливаются на основе журналов взаимодействия с клиентом и данных транзакций. Во время вывода эти функции извлекаются из хранилища функций с помощью службы DSP Feature Fetch и вводятся в объект модели MLeap.

3.2 Включение LinUCB в производство

Как обсуждалось в предыдущем разделе, во время каждого испытания «t» (сеанс пользователя) политика/алгоритм выбора ветви представлена ​​набором ветвей (рестораны) и соответствующими векторами контекста. Для каждой руки мы вычисляем оценку LinUCB (которая указана в приведенном ниже уравнении) и ранжируем руки на основе этой оценки. Другими словами, для каждого из обслуживаемых рекламных партнеров, когда рекламная платформа вызывает конечную точку модели LinUCB в DSP, модель по существу должна иметь возможность вычислить оценку LinUCB и вернуть ее рекламной платформе. Слой обслуживания рекламы в Ads Platform сортирует рестораны на основе этой оценки и возвращает отсортированный список на уровень представления для рендеринга.

Чтобы обеспечить вычисление оценки LinUCB в указанной выше производственной среде, нам необходимо следующее:

  • Извлечение параметров моделивозможность сделать параметры модели доступными во время оценки.
  • Извлечение векторов контекставозможность сделать векторы контекста, которые могут быть комбинацией исторических признаков и сигналов реального времени, доступными для оценки.
  • Вычисление оценки LinUCB: конвейер MLeap для вычисления оценки LinUCB в реальном времени.
  • Обновление параметров модели. Механизм обновления параметров каждого из рычагов в зависимости от вознаграждения.

3.2.1. Выборка параметров модели

Параметры модели θ и A inverse для каждого ресторана-партнера по рекламе обновляются с помощью задания Spark Cron и сохраняются в хранилище функций. Во время вывода эти параметры модели извлекаются с помощью службы выборки Fetch DSP. Обратите внимание, что это отличается от случая с обученной и сериализованной моделью ML, где параметры модели были бы частью объекта MLeap, развернутого в кластере. В случае MAB, которые постоянно адаптируют стратегию подсчета очков на основе вознаграждений, параметры модели постоянно обновляются (частота которых обсуждается в следующем разделе) и сохраняются в хранилище функций.

3.2.2 Выборка контекстного вектора

Вектор контекста x суммирует информацию как о пользователе, так и о руке. Этот вектор включает в себя сигналы, основанные на исторических взаимодействиях/транзакциях с клиентами, таких как предпочтения клиентов в кухне, вегетарианская/невегетарианская близость, стоимость заказа и т. д. Вектор контекста также может включать сигналы в реальном времени, такие как ожидаемое время доставки из ресторана и т. д.

Исторические сигналы для каждого из клиентов и ресторанов вычисляются и сохраняются в Feature Store. Сигналы в реальном времени передаются в DSP с рекламной платформы. Во время вывода исторические функции извлекаются из хранилища функций, а затем объединяются с сигналами в реальном времени для получения окончательного вектора контекста.

3.2.3 MLeap Pipeline для вычисления оценки LinUCB

Вычисление оценки LinUCB по существу включает матричное умножение, скалярное произведение, операцию квадратного корня, скалярное умножение и сложение. Библиотека MLeap имеет несколько преобразований данных и может поддерживать все необходимые операции для вычисления оценки LinUCB, кроме матричного умножения. Поэтому мы создали специальный преобразователь MLeap Matrix Multiplication, который получает две матрицы на вход и возвращает их произведение на выходе. Созданный пользовательский преобразователь может быть сериализован вместе с другими преобразователями в конвейере и, таким образом, может использоваться в выводе в реальном времени во время выполнения после его десериализации. Более подробную информацию о подключении новых трансформеров к MLEAP можно найти по адресу — Custom Transformers — combust/mleap-docs · GitHub

Мы также разместим исходный код разработанного преобразователя в репозитории MLEAP.

Имея все необходимые преобразователи/операторы MLeap, мы построили конвейер MLeap LinUCB, который делает следующее:

  1. Соберите вектор контекста. Как обсуждалось выше, исторические сигналы и сигналы реального времени, которые составляют вектор контекста, должны быть объединены и нормализованы для получения окончательного вектора контекста. Конвейер MLeap включает преобразователи для объединения и сборки вектора контекста.
  2. Вычисление оценки LinUCB:Включив умножение матриц в MLeap, мы можем сгенерировать оценку, используя контекст, θ и обратное и возвращают то же самое на рекламную платформу.

3.2.4 Обновление параметров модели

Параметры модели θ и A обновляются ежедневно в соответствии с уравнением (2) на основе отзывов, полученных в ходе взаимодействия между клиентом и рестораном накануне. Обратите внимание, что в отличие от теоретической настройки MAB, при которой параметры обновляются после каждого испытания, мы делаем пакетное обновление, при котором параметры обновляются после агрегирования вознаграждений за день. Частота этого обновления может быть изменена в соответствии с вариантом использования. Обновление после каждой пробной версии (сеанса пользователя) или чаще было неприемлемо или невыполнимо для нашего варианта использования, учитывая, что у нас ежедневно происходят миллионы пользовательских сеансов.

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

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

Ниже мы суммируем шаги, связанные с процессом обновления параметров, который выполняется в (ежедневном) хроне Spark:

  1. Получите последний вектор θ и матрицу A для каждого ресторана из Hive. Если ресторан никогда не производил впечатления, θ инициализируется как нулевой вектор, а A — как единичная матрица.
  2. Получить все взаимодействия клиентов с рестораном в предыдущий день и их соответствующие векторы контекста + вознаграждения
  3. Использование каждого обновления взаимодействия клиента и ресторана θ и A для ресторана с использованием уравнений обновления LinUCB, упомянутых ранее (уравнение 2).
  4. Сохраните окончательные обновленные параметры в Feature Store (DynamoDB), которые будут использоваться для оценки ресторанов в режиме реального времени для сеансов на следующий день, и в Hive, который будет использоваться для обновлений параметров.

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

4. Заключение

В этом посте мы обсудили архитектуру системы, новые преобразователи Mleap, которые мы создали, и конвейеры, которые мы настроили для включения контекстных MAB с использованием алгоритма LinUCB для рекомендаций партнеров по рекламе ресторанов. Это решение согласовано с нашей текущей производственной системой и способно предоставлять логические выводы в реальном времени, гарантируя, что оно соответствует требуемым профилям задержки. Имея этот инструментарий, мы теперь изучаем, как мы можем включить другие модели онлайн-обучения, которые могут обеспечить лучшее открытие и разнообразие в наших рекомендациях. В качестве ближайших следующих шагов мы также предоставим преобразователи матричного умножения Mleap с открытым исходным кодом.

5. Соответствующие ресурсы

  1. Многорукие бандиты в Свигги: Часть 1
  2. Многорукие бандиты в Свигги: Часть 2
  3. Платформа Swiggy Data Science
  4. Контекстно-бандитский подход к рекомендации персонализированных новостных статей (документ LinUCB) — https://arxiv.org/pdf/1003.0146.pdf
  5. Сообщение в блоге о Disjoint LinUCB — https://kfoofw.github.io/contextual-bandits-linear-ucb-disjoint/