02.04.2019 08:43
chiliarchus 1 1100 Источник


Динамический ремаркетинг (dynrem) в myTarget — это технология направленной рекламы, использующая информацию о действиях пользователей на сайтах и в мобильных приложениях рекламодателей. Например, в интернет-магазине пользователь просмотрел страницы товаров или добавил их в корзину, и myTarget использует эти события для показа рекламы именно тех товаров и услуг, к которым человек уже проявлял ранее интерес. Сегодня я подробнее расскажу о механизме генерирования неперсональных, то есть item2item-рекомендаций, которые позволяют разнообразить и дополнить рекламную выдачу.

В качестве клиентов для dynrem myTarget выступают в основном интернет-магазины, у которых может быть один или несколько списков товаров. При построении рекомендаций пару «магазин — список товаров» нужно учитывать как обособленную единицу. Но для простоты дальше будем использовать просто «магазин». Если говорить о размерности задачи на входе, то рекомендации нужно строить примерно для тысячи магазинов, причем количество товаров может варьироваться от нескольких тысяч до миллионов.

Система рекомендаций для dynrem должна удовлетворять таким требованиям:

  1. Баннер содержит товары, которые максимизируют его CTR.
  2. Рекомендации строятся в оффлайн-режиме в течение заданного времени.
  3. Архитектура системы должна быть гибкой, масштабируемой, устойчивой и работать в условиях «холодного старта».

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

Раздел 2 содержит теоретические основы для построения рекомендательных систем, в разделах 3 и 4 рассматривается практическая сторона вопроса, а в разделе 5 подводится общий итог.

Основные понятия


Рассмотрим задачу построения рекомендательной системы для одного магазина и перечислим основные математические подходы.

Singular Value Decomposition (SVD)


Популярным подходом к построению рекомендательных систем является подход на основе сингулярного разложения (SVD). Матрицу рейтингов $R = (r_{ui})$ представляют в виде произведения двух матриц $P$ и $Q$ так, чтобы $R \approx P Q^T$, тогда оценка рейтинга пользователя $u$ для товара $i$ представляется в виде $\hat{r}_{ui}=<p_u,q_i>$ [1], где элементы скалярного произведения являются векторами размерности $k $(основной параметр модели). Эта формула служит основой для других SVD-моделей. Задача нахождения $P$ и $Q$ сводится к оптимизации функционала:

(2.1)

$J(P,Q) = \sum_{(u,i)}\mathcal{L}(r_{ui}, \hat{r}_{ui}) + \Lambda(P, Q) \rightarrow \min_{P,Q},$


где $L$ — функция ошибки (например, RMSE как в соревновании Netflix), $?$ — регуляризация, а суммирование идет по парам, для которых известен рейтинг. Перепишем выражение (2.1) в явном виде:

(2.2)

$J(P,Q) = \sum_{(u,i)}(r_{ui} - <p_u, q_i>)^2 + \lambda_1||p_u||^2 + \lambda_2||q_i||^2 \rightarrow \min_{P,Q},$


Здесь $?1$, $?2$ — коэффициенты L2-регуляризации для представлений пользователя $p_{u}$ и товара $q_{i}$ соответственно. Базовая модель для соревнования Netflix имела вид:

(2.3)

$\hat{r}_{ui}=\mu + b_u + b_i + <p_u,q_i>,$


(2.4)

$J(P,Q) = \sum_{(u,i)}(r_{ui} - \mu - b_u - b_i - <p_u, q_i>)^2 + \lambda_1||p_u||^2 + \lambda_2||q_i||^2 + \lambda_3 b_u^2 + \lambda_4 b_i^2 \rightarrow \min_{P,Q},$


где $µ$, $b_{u}$ и $b_{i}$ — смещения для рейтинга, пользователя и товара соответственно. Модель (2.3) — (2.4) можно улучшить, добавив в неё неявное предпочтение пользователя. На примере соревнования Netflix явным откликом является балл, поставленный пользователем фильму «по нашей просьбе», а неявным откликом выступает прочая информация о «взаимодействии пользователя с товаром» (просмотр фильма, его описания, рецензий на него; т.е. неявный отклик не даёт прямой информации о рейтинге фильма, но при этом указывает на заинтересованность). Учёт неявного отклика реализован в модели SVD++:

(2.5)

$\hat{r}_{ui}=\mu + b_u + b_i + <p_u + \frac{1}{\sqrt{\sigma_u}} \sum_{j \in S(u)} y_j,\,\,q_i>,$


где $S(u)$ — набор объектов, с которыми неявно взаимодействовал пользователь, $?_{u} = |S(u)|, y_{j}$ — представление размерности $k$ для объекта из $S(u)$.

Factorization Machines (FM)


Как видно на примерах с различными SVD-моделями, одна модель отличается от другой набором слагаемых, входящих в формулу оценки. При этом расширение модели каждый раз представляет из себя новую задачу. Мы хотим, чтобы такие изменения (например, добавление нового вида неявного отклика, учёт временных параметров) можно было легко реализовать, не меняя код реализации модели. Модели (2.1) — (2.5) можно представить в удобной универсальной форме, используя следующую параметризацию. Представим пользователя и товар в виде набора признаков:

(2.6)

$\overline{x}^U=(x_1^U, x_2^U, \dots, x_l^U) \in \mathbb{R}^l,$



(2.7)

$\overline{x}^I=(x_1^I,x_2^I,\dots,x_m^I) \in \mathbb{R}^m.$




Рис. 1: Пример матрицы признаков в случае CF.

Например, в случае коллаборативной фильтрации (CF), когда используются только данные о взаимодействии пользователей и товаров, векторы признаков имеют вид one-hot-кода (Рис. 1). Введём вектор $\overline{x}=(\overline{x}^U, \overline{x}^I)$, тогда задача рекомендации сводится к задачам регрессии с целевой переменной $r_{ui}$:

  1. Линейная модель:
    (2.8)

    $h_{lin}(\overline{x}) = w_0+\sum_{j=1}^{l+m}w_jx_j$

  2. Poly2:
    (2.9)

    $h_{poly2}(\overline{x}) = w_0+\sum_{j=1}^{l+m}w_jx_j + \sum_{i=1}^{l+m} \sum_{j=i+1}^{l+m} w_{ij} x_i x_j$

  3. FM:
    (2.10)

    $h_{FM}(\overline{x}) = w_0+\sum_{j=1}^{l+m}w_jx_j + \sum_{i=1}^{l+m} \sum_{j=i+1}^{l+m} x_i x_j <\overline{v}_i, \overline{v}_j>$


где $w_{j}$ — параметры модели, $v_{i}$ — векторы размерности $k$, представляющие признак $i$ в латентном пространстве, $l$ и $m$ — количество признаков пользователя и товара соответственно. В качестве признаков помимо one-hot-кодов могут выступать контентные признаки (Content-based, CB) (Рис. 2), например, векторизованные описания товаров и профилей пользователей.


Рис. 2: Пример расширенной матрицы признаков.

Модель FM, введенная в [2], является обобщением для (2.1) — (2.5), (2.8), (2.10). Суть FM в том, что она учитывает парное взаимодействия признаков с помощью скалярного произведения $<\overline{v}_i, \overline{v}_j>$, а не с помощью параметра $w_{ij}$. Преимущество FM относительно Poly2 состоит в существенном уменьшении количества параметров: для векторов $v_{i}$ нам потребуется $(l + m) · k$ параметров, а для $w_{ij}$ потребуется $l · m$ параметров. При $l$ и $m$ больших порядков первый подход использует значительно меньше параметров.

Обратим внимание: если в обучающей выборке отсутствует конкретная пара $(i, j)$, то соответствующее слагаемое с $w_{ij}$ в Poly2 не влияет на обучение модели, и оценка рейтинга формируется только по линейной части. Однако подход (2.10) позволяет устанавливать связи через другие признаки. Иначе говоря, данные об одном взаимодействии помогают оценить параметры признаков, не входящих в этот пример.

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

LightFM


В популярной реализации FM сделан акцент на разделение между признаками пользователя и товара. В качестве параметров модели выступают матрицы $E^U$ и $E^I$ представления пользовательских и товарных признаков:

(2.11)

$E^U= \begin{pmatrix} \overline{e}_1^U\\ \vdots \\ \overline{e}_l^U \end{pmatrix}, \,\, E^I= \begin{pmatrix} \overline{e}_1^I\\ \vdots \\ \overline{e}_m^I \end{pmatrix}, \overline{e}_i^U \in \mathbb{R}^k, \overline{e}_i^I \in \mathbb{R}^k$


а также смещения $\overline{b}^U, \overline{b}^I \in \mathbb{R}^k$. Используя представления пользователя и товара:

(2.12)

$\overline{p}^U = \overline{x}^U \cdot E^U = \sum_{j=1}^l x_j^U \cdot \overline{e}_j^U,$


(2.13)

$\overline{q}^I = \overline{x}^I \cdot E^I = \sum_{j=1}^m x_j^I \cdot \overline{e}_j^I,$


получаем рейтинг пары $(u, i)$:

(2.14)

$\hat{r}_{ui} = <\overline{p}^U, \overline{q}^I> + <\overline{x}^U, \overline{b}^U> + <\overline{x}^I, \overline{b}^I>. $


Функции потерь


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

  1. Logistic представляет собой реализацию, требующую негатив, который явным образом не представлен в большинстве задач.
  2. BPR [3] заключается в максимизации разности рейтингов между позитивным и негативным примерами для конкретного пользователя. Негатив получают с помощью бутстрэп-сэмплирования. Функционал качества, используемый в алгоритме, аналогичен ROC-AUC.
  3. WARP [4] отличается от BPR методом сэмплирования негативных примеров и функцией потерь, которая тоже является ранжирующей, но при этом оптимизирует топ рекомендаций для пользователя.

Практическая реализация


Для построения рекомендаций в течение заданного времени используется параллельная реализация на Spark. Для каждого магазина запускается независимая задача, исполнение которой контролируется luigi.

Препроцессинг данных


Препроцессинг данных выполняется автоматически масштабируемыми средствами Spark SQL. Отобранные в финальную модель признаки — текстовые описания товаров и каталогов со стандартными преобразованиями.

Что нам помогало при взаимодействии со Spark:

  1. Партицирование подготовленных данных (матрицы взаимодействий пользователей и товаров, признаки для них) по магазинам. Это позволяет на этапе обучения экономить время на чтении данных из HDFS. В противном случае каждой задаче приходится считывать данные в память Spark и фильтровать их по ID магазина.
  2. Сохранение/получение данных в/из Spark мы делаем частями. Это связано с тем, что в процессе любого из этих действий данные загружаются в память JVM. Почему просто не увеличить память для JVM? Во-первых, тогда уменьшается доступная для обучения модели память, а во-вторых, не нужно хранить что-либо в JVM, она выступает в данном случае как временное хранилище.

Обучение модели


Модель для каждого магазина обучается в своем Spark-контейнере, благодаря чему можно одновременно запускать произвольное количество задач для магазинов, ограниченное только ресурсами кластера.

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

Обозначим:

$S$ — все известные нам взаимодействия между пользователями и товарами, то есть пары $(u, i)$,
$I$ — множество всех товаров $i$,
$U$ — множество всех пользователей $u$.
Для конкретного пользователя $u$ также введем $I_{u} = {i ? I : (u, i) ? S}$ — множество товаров, с которыми взаимодействовал пользователь. AUC можно вычислить следующим образом [ref]:

(3.1)

$AUC(u) = \frac{1}{|\mathcal{I}_u||\mathcal{I} \setminus \mathcal{I}_u|} \sum_{i\in \mathcal{I}_u} \sum_{j \in \mathcal{I} \setminus \mathcal{I}_u} \delta(\hat{r}_{ui} > \hat{r}_{uj}),$


(3.2)

$AUC = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} AUC(u).$


В формуле (3.1) нам нужно посчитать рейтинг для всех возможных пар $(u, i)$ ($u$ фиксировано), а также сравнить рейтинг для элементов из $\mathcal{I}_u$ с рейтингами из $\mathcal{I} \setminus \mathcal{I}_u$. Учитывая, что пользователь взаимодействует с мизерной частью ассортимента, сложность расчёта составляет $O(|\mathcal{U}||\mathcal{I}|)$. При этом одна эпоха обучения FM обходится нам в $O(|\mathcal{U}|)$.

Поэтому мы модифицировали расчет AUC. Во-первых, следует разбить выборку на тренировочную $\mathcal{S}^{train} \subset \mathcal{S}$ и валидационную $\mathcal{S}^{val} \subset \mathcal{S}$, причем $\mathcal{S}^{val} = \mathcal{S} \setminus \mathcal{S}^{train}$. Далее мы с помощью сэмплирования формируем множество пользователей для валидации $\mathcal{U}^{val} \subset \{u\in \mathcal{U}: (u, i) \in \mathcal{S}^{val}\}$. Для пользователя $u$ из $\mathcal{U}^{val}$ элементами позитивного класса будем считать множество $\mathcal{I}_u^{+} = \{i\in \mathcal{I}: (u, i) \in \mathcal{S}^{val}\}$, аналогичное $\mathcal{I}_u$. В качестве элементов негативного класса возьмем подвыборку $\mathcal{I}_u^{-} \subset \mathcal{I}$ так, чтобы в неё не попали элементы из $\mathcal{I}_u$. Размер подвыборки можно брать пропорциональным размеру $\mathcal{I}_u^{+}$, то есть $|\mathcal{I}_u^{-}| = c\cdot |\mathcal{I}_u^{+}|$. Тогда формулы (3.1), (3.2) для расчета AUC изменятся:

(3.3)

$AUC(u) = \frac{1}{|\mathcal{I}_u^{+}|| \mathcal{I}_u^{-}|} \sum_{i\in \mathcal{I}_u^{+} } \sum_{j \in \mathcal{I}_u^{-} } \delta(\hat{r}_{ui} > \hat{r}_{uj}),$


(3.4)

$AUC = \frac{1}{|\mathcal{U}^{val}|} \sum_{u \in \mathcal{U}^{val}} AUC(u).$


В итоге получаем константное время на расчет AUC, так как берём только фиксированную часть пользователей, и множества $\mathcal{I}_u^{+}$ и $\mathcal{I}_u^{-}$ имеют небольшой размер. Процесс обучения для магазина останавливается после того, как AUC (3.4) перестает улучшаться.

Поиск похожих объектов


В рамках задачи item2item необходимо выбрать для каждого товара $n$ (или максимально похожих на него товаров) такие, которые максимизируют кликабельность баннера. Наше допущение: кандидатов для баннера нужно считать из top-$k$ ближайших в пространстве эмбеддингов. Мы протестировали следующие методы расчёта «ближайших соседей»: Scala + Spark, ANNOY, SCANNs, HNSW.


У связки Scala + Spark для магазина с 500 тыс. объектов подсчёт честной косинусной метрики занял 15 минут и значительный объём ресурсов кластера, в связи с чем мы протестировали аппроксимальные методы поиска ближайших соседей. При исследовании метода SCANNs варьировались следующие параметры: bucketLimit, shouldSampleBuckets, NumHashes и setSignatureLength, но результаты получились неудовлетворительными по сравнению с остальными методами (в бакеты попадали сильно различающиеся объекты). Алгоритмы ANNOY и HNSW показали результаты, сравнимые с честным косинусом, но отработали значительно быстрее.

200к товаров 500к товаров 2.2м товаров
Алгоритм ANNOY HNSW ANNOY HNSW ANNOY HNSW
время построения
индекса (сек)		 59.45 8.64 258.02 25.44 1190.81 90.45
общее время (сек) 141.23 14.01 527.76 43.38 2081.57 150.92


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

Заключение


Напомним: WARP мы используем для обучения модели, AUC — для ранней остановки, а финальная оценка качества проводится с помощью А/Б-теста на живом трафике.

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

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

Спасибо за внимание!

Литература


[ 1 ] Ricci F., Rokach L., Shapira B. Introduction to recommender systems handbook
//Recommender systems handbook. — Springer, Boston, MA, 2011. — С. 147160.

[ 2 ] Rendle S. Factorization machines //2010 IEEE International Conference on Data Mining. — IEEE, 2010. — С. 995-1000.

[ 3 ] Rendle S. et al. BPR: Bayesian personalized ranking from implicit feedback
//Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence.
— AUAI Press, 2009. — С. 452-461.

[ 4 ] Weston J., Bengio S., Usunier N. Wsabie: Scaling up to large vocabulary image annotation //Twenty-Second International Joint Conference on Artificial Intelligence. — 2011.

Комментарии (1)


  1. FreakII
    02.04.2019 13:41
    #19973886
    -2

    Какой мощный матан на входе, и какие тупые нерелевантные рекламные баннеры на выходе