Шпаргалка по рекомендательным системам11.02.2024 23:30

Цель рекомендаций — порекомендовать пользователю что-то новое. Например, на маркетплейсах, в музыкальных или видео-стриминговых сервисах.

На деле вы всегда работаете с так называемой матрицей взаимодействий (user-item matrix), на каждой строке которой стоят пользователи (users), а каждому столбцу соответствует товар (items). На пересечении пользователя и товара записано какое-то их взаимодействие (feedback).

Feedback между пользователем и товаром может быть:

явным (explicit): оценки, лайки;
неявным (implicit): клики, скипы;

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

При этом, и описание пользователя можно представить по-разному:

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

Здесь будут рассмотрены 1 и 2 пункты.

Основные подходы при решении таких задач:

Коллаборативная фильтрация (collaborative filtering, CF);
Матричные факторизации (matrix factorization, MF), SVD-разложение;
Нейросетевые подходы:

1. Коллаборативная фильтрация

Разделяется на Item2Item (основан на похожести между товарами) и User2User (основан на похожести между пользователями) подходы.

Ниже приведены рассуждения для Item2Item, но, с точностью до замен переменных, они верны для User2User.

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

В зависимости от имеющегося фидбека, похожесть будет считаться по-разному: в случае explicit фидбека это может быть корреляция, а в случае implicit — мера Жаккара.

Посчитав все похожести товаров, предсказание можно взять как усреднение ТОПа самых похожих, что, в каком-то смысле, похоже на KNN.

2. Матричные факторизации

Этот подход основан на методе главных компонент (PCA) и матричном разложении (SVD).

Матрица взаимодействий очень большая и очень разряженная.

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

Геометрический смысл SVD

Формульно:

$R = U \Sigma V^T\\ U U^T = U^T U = I_M\\ V V^T = V^T V = I_N$

и — матрицы поворота, $\Sigma$ — это диагональная матрица с неотрицательными сингулярными числами, которые расположены в порядке неубывания. Они говорят о мере дисперсии (разброса) точек: чем больше это число, тем больше разброс. Если мы будем умножать вектор на SVD-разложение, то сначала мы вектор повернем, потом растянем и еще раз повернем.

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

меньшее (часто меньше 100) количество главных (первых) компонент из матрицы $\Sigma$ , просто отбросив «хвост». Такая манипуляция, с одной стороны, позволяет значительно сократить объемы памяти, с другой стороны, дает наилучшее приближение к R по норме Фробениуса.

Сделав замену $P = U \Sigma$ , Q = V^T матрицу взаимодействий представляют как R = P Q и говорят, что строка — это представление i-го пользователя, а столбец — представление j-го товара. Тогда, их взаимодействие считается как скалярное произведение: $\hat R_{ij} = \big( P_i , Q_j \big)$ .

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

$\sum \big( R_{ij} - \hat R_ij \big) ^2 = \sum \big( R_{ij} - (P_i , Q_j) \big)^2 → min$

Причем, мы не можем просто применить SVD разложение: поскольку матрица содержит большое количество нулей, то и решение всегда будет близко к нулю. Идея Funk SVD в том, что мы восстанавливаем матрицу R только по заданным элементам. Такая задача оптимизации решается градиентным спуском и довольно хорошо сходится.

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

Модификации функционала:

3. Нейросетевые подходы

SLIM: Sparse Linear Methods for Top-N Recommender Systems

Пусть имеется матрица взаимодействий (implicit feedback). Задача — предсказать какие взаимодействия в будущем наиболее вероятны. Решается — с помощью взвешенной суммы событий из прошлого:

$\hat r_{ui} = \sum_{j = 1}{w_{ij} r_{ui}}$

Причем на матрицу весов наложены следующие ограничения: $w_{ij} ≥ 0$ (так модель будет учитывать учитывает только похожие товары) и $w_{ii} = 0$ (чтобы избежать элементарного решения). По-сути, ищется взаимодействие пользователя и товара через сумму взвешенных взаимодействий с другими товарами.

Обучается MSE-loss с Elastic Net регуляризацией (L1 и L2):

$\frac{1}{2} \sum_{u, i} \left( r_{ui} - \sum_{j} w_{ij} r_{uj} \right)^2+ \lambda \sum_{i, j} |w_{ij}| + \frac{\beta}{2} \sum_{i, j} (w_{ij})^2 \rightarrow \min_{W}$

причем основная роль отводится именно L1 регуляризации, потому что вектор весов мы стараемся максимально занулить (отсюда название метода).

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

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

Для предсказания для i-го пользователя и j-го товара перемножаются вектор взаимодействий пользователя и j-ый столбец матрицы весов W.

Такая модель хорошо работает для top-N предсказаний. Для двухстадийных рекомендательных систем SLIM выгоднее использовать в первом этапе, при генерации кандидатов. При этом, во втором этапе (ранжирование и генерирование признаков) удобнее использовать матричную факторизацию.

Factorization Machines (FM)

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

1) Преобразуем матрицу взаимодействий в матрицу , состоящую из ohe-hot векторов, где стоит на месте соответствующего пользователя и товара (, ).

2) Рассмотрим регрессионную модель $r(x) = w_0 + \sum_{i=1}^{n} w_i x_i$ , где — какая-то one-hot user-a или one-hot item-а фича.

3) Добавим взаимодействия второго порядка. Это позволит учитывать более сложные соотношения между признаками:

$r(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij} x_i x_j$

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

Однако, матрица будет слишком большого размера:

4) Факторизуем матрицу весов . Вместо веса $w_{ij}$ будет учить скалярное произведение векторов и (embedding-и i-ой фичи и j-ой фичи):

$r(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j$

где — bias (смещение) всей системы, $\sum_{i=1}^{n} w_i x_i$ — bias пользователей и bias товаров, $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j$ — попарные взаимодействия. Таким образом, можно обучать гораздо меньшее количество параметров. Такая модель и называется Factorization Machines.

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

Если добавить в матрицу дополнительные one-hot item-ы из прошлого пользователя, образуя хвостик из товаров с которыми пользователь взаимодействовал в прошлом, тогда модель будет дополнительно изучать последовательности взаимодействий. Фактически это будет факторизация марковских цепей.

Идея FFM — Field-aware Factorization Machines: разбить признаки из матрицы на группы :

Тогда модель FFM выглядит как:

В остальном, все как в FM.

Two-tower network

Изначально это все пошло из поска, где обучались DSSM (Deep Structured Semantic Models) модели (классические модели поиска и ранжирования) для запросов и документов. Хотелось бы, чтобы вектор запроса был похож на вектор документа, который релевантен и который подходит пользователю.

Представляем текстовый документи запрос в виде Bag of words как x_D, x_Q (~100k). С помощью нейросетей, переводим их в embedding-и небольшого размера (~300). Между ними считается функция близости: косинус, скалярное произведение или др. По значению близости ранжируются документы.

Поиск релевантных товаров можно представить как задачу ранжирования, где в качестве запроса — пользователь, его история и фичи.

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

В качетсве признаков можно использовать: стандартные статистики документа: количество лайков, кликов, подписок; признаки автора: количество подписчиков, жанр; неструктурированные данные: текст документа (можно использовать BOW формат, а можно воспользоваться предобученными эмбеддингами), видео и картинки (предварительно представив их в виде эмбеддинга).

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

Two-tower архитектура (в частности DSSM) имеет ряд преимуществ: большое пространство для творчества при конструировании признаков; быстрый интерфейс, так как эмбеддинги товаров можно считать оффлайн; возможность построить оффлайн (и даже онлайн) отбор кандидатов на обученных эмбеддингаx.