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

Заметка об обучении ранжированию упорядочивала документы для запроса, и у каждой пары (запрос, документ) были признаки: совпадения текста, число ссылок, эмбеддинги. Рекомендательная система упорядочивает объекты (items) для человека: следующий фильм, песни плейлиста, товары для корзины, посты ленты. Запрос — это пользователь, и часто описать его нечем, кроме того, что он делал: какие объекты оценивал, покупал, слушал или пропускал. Этой записи достаточно. Люди, которые соглашались в прошлом, склонны соглашаться и в будущем, а объекты, которые нравятся одним и тем же людям, обычно нравятся вместе. Эта заметка превращает это наблюдение в модели — от соседей в матрице «пользователь — объект» до низкоранговой факторизации, выигравшей Netflix Prize, — приспосабливает его к обратной связи без негативных примеров и уделяет оценке качества столько же внимания, сколько обучению, потому что рекомендательную систему необычайно легко оценить неправильно.

Обозначения. Есть $m$ пользователей с индексом $u$ и $n$ объектов с индексом $i$. $r_{ui}$ — обратная связь пользователя $u$ на объект $i$: оценка от 1 до 5 звёзд или, для неявной обратной связи, счётчик, например число воспроизведений. $\Omega$ — множество пар $(u, i)$ с известным $r_{ui}$; $n_u$ и $n_i$ — числа известных элементов у пользователя $u$ и у объекта $i$. $R$ — матрица размера $m \times n$, в которой заполнены известные элементы. Предсказание обозначается $\hat r_{ui}$. Латентные факторы — векторы $p_u, q_i \in \mathbb R^d$, строки матриц $P$ ($m \times d$) и $Q$ ($n \times d$); $\mu$, $b_u$, $b_i$ — глобальное среднее и смещения пользователя и объекта; $\lambda$ — коэффициент регуляризации.

Матрица «пользователь — объект»#

Всё, что знает коллаборативная рекомендательная система, лежит в одной матрице: строка на пользователя, столбец на объект, элемент везде, где пользователь оставил обратную связь. Три свойства этой матрицы определяют все методы ниже.

• Она почти пуста. Данные Netflix Prize содержали более 100 миллионов оценок примерно 500 000 клиентов для более чем 17 000 фильмов (Koren, Bell and Volinsky, 2009): около 1% клеток. Синтетические данные из раздела «Код», 18 872 оценки 400 объектов от 600 пользователей, заполняют 7.9%.
• Она перекошена. Немногие объекты собирают большую часть обратной связи, а у большинства объектов её мало; в синтетических данных на 10% самых популярных объектов приходится 53% всех оценок. Любое среднее по оценкам определяется популярной головой распределения.
• Её пропуски не случайны. Пользователь оценивает фильмы, которые решил посмотреть, а решил он их посмотреть, потому что ожидал, что они ему понравятся. Поэтому пропущенный элемент — не нейтральная неизвестность, но и не низкая оценка: пуста ли клетка, зависит от показа, доступности и выбора пользователя, и одно лишь отсутствие оценки не говорит о низком предпочтении. Некоторые модели по соглашению считают пропуски слабыми отрицательными примерами, как в разделе о неявной обратной связи ниже.

Явная обратная связь (explicit feedback), например звёзды или лайки, говорит, насколько объект понравился пользователю, положительно или отрицательно, и её мало. Неявная обратная связь (implicit feedback), например воспроизведения, покупки, клики и время просмотра, обильна, но лишена негативных примеров: то, что пользователь не смотрел фильм, может означать, что фильм ему не нравится, а может — что он о нём не слышал. Первая половина заметки работает с оценками, вторая — с неявной обратной связью.

Цель редко состоит в самой оценке. Продукт показывает пользователю короткий список, поэтому задача — ранжировать объекты, которых пользователь ещё не видел, то есть задача предыдущей заметки с пользователями вместо запросов. Предсказание оценок — средство для этой цели, и оценка качества должна измерять список.

Контентная фильтрация#

Первому подходу другие пользователи матрицы вообще не нужны. Опишем каждый объект признаками — вектором жанров, эмбеддингом его описания, исполнителями песни — и обучим для каждого пользователя модель его оценок как функцию этих признаков. С линейной моделью это одна гребневая регрессия на пользователя:

$$\hat r_{ui} = w_u^\top \phi_i , \qquad w_u = \arg\min_w \sum_{i:\,(u, i) \in \Omega} (r_{ui} - w^\top \phi_i)^2 + \lambda \lVert w \rVert^2 ,$$

где $\phi_i$ — вектор признаков объекта $i$. Контентная фильтрация (content-based filtering) рекомендует новый объект в день его появления, если у него есть признаки, и может объяснить свой выбор («потому что вам понравились другие джазовые записи»). Её ограничения — это ограничения признаков. Она не может узнать, что людям, которым нравится определённый режиссёр, нравится и определённый композитор, если ни один признак этого не фиксирует, и рекомендует больше того же самого: пользователю показываются только объекты, близкие к тем, что он уже оценил. Кроме того, хорошие признаки нужно собрать или сконструировать, что для многих каталогов дорого или невозможно (Koren, Bell and Volinsky, 2009).

Коллаборативная фильтрация с соседями#

Коллаборативная фильтрация (collaborative filtering) не использует признаков объектов. Она выводит, что понравится пользователю, из того, что понравилось похожим пользователям, или из того, как пользователь оценил похожие объекты, причём само сходство вычисляется по матрице. Старейшие методы делают это с помощью ближайших соседей.

По пользователям (user-based). Измерим сходство $w_{uv}$ двух пользователей корреляцией их оценок на объектах, которые оценили оба, найдём пользователей, наиболее похожих на $u$ и оценивших объект $i$, и усредним их оценки, центрировав каждую по среднему её пользователя, чтобы можно было сравнивать строгого критика и щедрого:

$$\hat r_{ui} = \bar r_u + \frac{\sum_v w_{uv} (r_{vi} - \bar r_v)}{\sum_v \lvert w_{uv} \rvert} .$$

По объектам (item-based). Развернём подход: вычислим сходства между объектами по пользователям, которые оценили оба объекта, и предскажем оценку $u$ для $i$ по собственным оценкам $u$ для объектов, наиболее похожих на $i$ (Sarwar et al., 2001). Со скорректированным косинусным сходством (adjusted cosine) каждая оценка сначала центрируется по среднему её пользователя, и

$$\hat r_{ui} = \bar r_u + \frac{\sum_j s_{ij} (r_{uj} - \bar r_u)}{\sum_j \lvert s_{ij} \rvert} ,$$

где сумма идёт по объектам $j$, которые оценил $u$. Сходства объектов меняются медленно и могут вычисляться офлайн, история пользователя коротка, а рекомендация приходит с объяснением («потому что вы смотрели…»). Так был построен рекомендатель Amazon «объект — объект» (item-to-item) (Linden, Smith and York, 2003).

Разобранный пример. Пять пользователей оценили пять фильмов (· — нет оценки):

	фильм 1	фильм 2	фильм 3	фильм 4	фильм 5	среднее
Аня	5	4	·	1	·	3.333
Боря	4	5	1	·	2	3
Вика	·	4	2	1	1	2
Дима	1	·	5	4	·	3.333
Ева	2	1	4	·	5	3

Как Аня оценит фильм 3? Фильмы 3 и 1 оценили Боря, Дима и Ева. После центрирования по их средним их оценки фильма 3 равны $(-2, 1.667, 1)$, а фильма 1 — $(1, -2.333, -1)$, поэтому

$$s_{31} = \frac{-2 - 3.889 - 1}{\sqrt{7.778}\,\sqrt{7.444}} = \frac{-6.889}{7.609} = -0.905 .$$

Тот же расчёт даёт $s_{32} = -0.775$ (по Боре, Вике и Еве) и $s_{34} = +0.555$ (по Вике и Диме). Центрированные оценки Ани для фильмов 1, 2 и 4 равны $1.667$, $0.667$ и $-2.333$, поэтому

$$\hat r_{\text{Аня},3} = 3.333 + \frac{-0.905 \cdot 1.667 - 0.775 \cdot 0.667 + 0.555 \cdot (-2.333)}{0.905 + 0.775 + 0.555} = 3.333 - 1.486 = 1.85 .$$

Аня любит два фильма, которые не нравятся поклонникам фильма 3, и не любит тот, который им нравится, поэтому предсказание низкое.

Методы соседей просты и прозрачны, но испытывают трудности там, где матрица разреженнее всего. Корреляция двух пользователей, у которых всего два общих оценённых объекта, равна ровно $\pm 1$, а сходства редких объектов опираются на горстку людей. Каждое сходство оценивается отдельно, поэтому ничто не связывает их в согласованную картину вкусов; а выбор меры сходства, размера окрестности и нормализации — эвристики без целевой функции, которую можно было бы оптимизировать.

Матричная факторизация#

Модель латентных факторов (latent factor model) объясняет каждую оценку несколькими скрытыми свойствами пользователя и объекта. Каждый пользователь получает вектор $p_u \in \mathbb R^d$, каждый объект — вектор $q_i \in \mathbb R^d$, а взаимодействие пользователя и объекта — их скалярное произведение. Одна координата может начать измерять, насколько фильм является комедией и насколько пользователь любит комедии; ничто не заставляет координаты быть интерпретируемыми, но $d$ от 20 до 100 достаточно, чтобы описать значительную часть вкусов в большом каталоге (Koren, Bell and Volinsky, 2009). Ещё до взаимодействия большая часть каждой оценки объясняется тем, кто оценивает и что оценивается: некоторые пользователи ставят всему высокие оценки, некоторые фильмы все оценивают высоко. Эти эффекты получают собственные параметры — смещения (biases):

$$\hat r_{ui} = \mu + b_u + b_i + p_u^\top q_i$$

(Koren, Bell and Volinsky, 2009, формула 4). Игрушечный пример смещений: при средней оценке $\mu = 3.6$, фильме, который оценивают на $0.4$ выше среднего, и пользователе, который оценивает на $0.5$ ниже среднего, базовое предсказание равно $3.6 + 0.4 - 0.5 = 3.5$, а скалярное произведение добавляет или вычитает то, что вкус этого пользователя говорит об этом фильме.

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

$$\min_{P, Q, b} \sum_{(u, i) \in \Omega} \Big[ (r_{ui} - \mu - b_u - b_i - p_u^\top q_i)^2 + \lambda \big( \lVert p_u \rVert^2 + \lVert q_i \rVert^2 + b_u^2 + b_i^2 \big) \Big]$$

(формула 5). Без смещений, без штрафа и при всех известных элементах задача сводится к наилучшему приближению матрицы рангом $d$, которое точно даёт усечённое сингулярное разложение (SVD); штраф сохраняет те же сингулярные векторы и сжимает сингулярные значения к нулю. Это то же вычисление, которое даёт PCA в заметке о понижении размерности. При 99% пропущенных элементов SVD даже не определено, а заполнение пропусков нулями или средними научило бы модель этим выдуманным значениям. Именно штраф не даёт подгонке под известные элементы переобучиться: иначе пользователь с тремя оценками мог бы получить вектор, который воспроизводит их точно, а во всём остальном предсказывает бессмыслицу.

Рисунок

Матрица низкого ранга восстанавливается по 40% клеток

Рисунок показывает, почему модель работает, когда её предположение почти выполнено. Его истинная матрица — константа 3 плюс матрица ранга 2, обрезанная до $[1, 5]$ в 35 клетках из 600, поэтому за вычетом этой константы она имеет ранг 2 приближённо, а не точно: её сингулярные значения равны $18.3$ и $12.4$, затем $1.8$. Матрица ранга 2 задаётся $(20 + 30) \cdot 2 = 100$ числами — и даже меньшим их количеством, если убрать свободу масштабирования и поворота, — а не 600, поэтому 247 зашумлённых клеток достаточно, чтобы её определить, и факторизация заполняет оставшиеся 353 с ошибкой, близкой к уровню шума. Реальные матрицы оценок не имеют в точности низкого ранга, но главных направлений вкуса в них немного, и именно их улавливают факторы.

Стохастический градиентный спуск#

Целевая функция — сумма по известным оценкам, поэтому она подходит для стохастического градиентного спуска: обходим оценки в случайном порядке, вычисляем ошибку $e_{ui} = r_{ui} - \hat r_{ui}$ и сдвигаем каждый параметр этой оценки на шаг $\eta$ против его градиента,

$$\begin{aligned} b_u &\leftarrow b_u + \eta\,(e_{ui} - \lambda b_u), & p_u &\leftarrow p_u + \eta\,(e_{ui}\, q_i - \lambda p_u),\\ b_i &\leftarrow b_i + \eta\,(e_{ui} - \lambda b_i), & q_i &\leftarrow q_i + \eta\,(e_{ui}\, p_u - \lambda q_i) \end{aligned}$$

(множитель 2 из производной поглощается в $\eta$). Четыре обновления одновременны: каждое использует значения до шага, так что $q_i$ сдвигается со старым $p_u$, как в разделе «Код». Популярным метод сделала версия этого цикла, которую Саймон Фанк (Simon Funk) предложил во время Netflix Prize (Koren, Bell and Volinsky, 2009). Каждый шаг стоит $O(d)$, а проход по данным — $O(d\,\lvert\Omega\rvert)$.

Чередующиеся наименьшие квадраты#

Целевая функция невыпукла: $p_u^\top q_i$ — произведение неизвестных, и любое масштабирование $p_u \to c\,p_u$, $q_i \to q_i / c$ или поворот всех векторов сразу оставляет предсказания неизменными. Но при фиксированных векторах всех объектов задача для одного пользователя — задача наименьших квадратов с гребневым штрафом, у которой есть решение в замкнутом виде. Если для ясности пренебречь смещениями, то при $Q_u$ — матрице, строки которой — векторы $n_u$ объектов, оценённых $u$, — и $r_u$ — векторе этих оценок (после вычитания $\mu$ и смещений)

$$p_u = \big(Q_u^\top Q_u + \lambda n_u I\big)^{-1} Q_u^\top r_u ,$$

где множитель $n_u$ возникает из штрафа, который платится один раз на оценку. Метод чередующихся наименьших квадратов (alternating least squares, ALS) фиксирует объекты и решает задачу для каждого пользователя, затем фиксирует пользователей и решает задачу для каждого объекта, и так по кругу. Каждый полушаг решает свою подзадачу точно, поэтому целевая функция никогда не возрастает (Koren, Bell and Volinsky, 2009). Смещения входят в то же решение как дополнительная координата с регрессором, равным 1. ALS не нужен шаг обучения, его пользователи (а затем объекты) — независимые задачи, которые решаются параллельно, и он переносится на плотную целевую функцию неявной обратной связи, где SGD пришлось бы обходить каждую клетку.

Разобранный пример. Пользователь оценил два объекта с векторами $q_1 = (1, 0)$ и $q_2 = (1, 1)$; центрированные оценки равны 2 и 1. Со штрафом $0.1$ в решении

$$Q_u^\top Q_u + 0.1\, I = \begin{pmatrix} 2.1 & 1 \\ 1 & 1.1 \end{pmatrix}, \qquad Q_u^\top r_u = \begin{pmatrix} 3 \\ 1 \end{pmatrix}, \qquad p_u = \begin{pmatrix} 1.756 \\ -0.687 \end{pmatrix},$$

что даёт предсказания $1.756$ и $1.069$ для двух объектов: близко к 2 и 1, с небольшим сжатием из-за штрафа.

На синтетических оценках из раздела «Код» с разбиением по времени глобальное среднее предсказывает с корнем из среднеквадратичной ошибки (RMSE) 0.969, одни смещения — с 0.835, а факторизация с $d = 3$ — с 0.705 при ALS или 0.702 при мини-батчевом SGD на той же целевой функции: два оптимизатора, один ответ. При $d = 10$ ошибка вырастает до 0.756. Данные были сгенерированы с тремя факторами, и лишние семь подгоняются под шум; $d$ — ёмкость модели, которую выбирают на валидации, как степень многочлена.

Неявная обратная связь#

Воспроизведения, покупки и клики меняют задачу тремя способами (Hu, Koren and Volinsky, 2008, §1). Негативных примеров нет, поэтому пропущенные клетки нельзя игнорировать: модель, обученная только на наблюдаемых клетках, видела бы исключительно положительные свидетельства и везде предсказывала бы «нравится». Сигнал шумный: шоу, воспроизведённое один раз, могло идти, пока зритель спал. И значение элемента измеряет уверенность, а не предпочтение: любимый фильм, просмотренный один раз, и сериал, который смотрят каждую неделю, нравятся оба, а еженедельный счётчик говорит лишь о том, что свидетельство сильнее.

Hu, Koren и Volinsky разделяют эти два смысла. Предпочтение (preference) бинарно: $s_{ui} = 1$, если $r_{ui} > 0$, и 0 иначе, а уверенность (confidence) в нём растёт со счётчиком, $c_{ui} = 1 + \alpha r_{ui}$. Модель подгоняет предпочтения всех $m \cdot n$ клеток с весами уверенности:

$$\min_{P, Q} \sum_{u, i} c_{ui} \big( s_{ui} - p_u^\top q_i \big)^2 + \lambda \Big( \sum_u \lVert p_u \rVert^2 + \sum_i \lVert q_i \rVert^2 \Big)$$

(§4, формула 3). Каждая ненаблюдаемая клетка говорит «скорее нет» с минимальной уверенностью 1; каждая наблюдаемая говорит «скорее да», тем твёрже, чем чаще это случалось. В вероятностных терминах это взвешенный метод наименьших квадратов: гауссовская модель $s_{ui}$ с дисперсией $1/c_{ui}$, так что частые взаимодействия считаются точными измерениями, а отсутствующие — размытыми.

В сумме $m \cdot n$ слагаемых, на практике это миллиарды, что исключает SGD. ALS по-прежнему работает и требует времени, линейного по числу наблюдаемых клеток, благодаря одному тождеству (§4, формула 4). Решение для пользователя — $p_u = (Q^\top C^u Q + \lambda I)^{-1} Q^\top C^u s_u$, где $C^u$ — диагональная матрица уверенностей $u$, и

$$Q^\top C^u Q = Q^\top Q + Q^\top (C^u - I)\, Q .$$

$Q^\top Q$ одна и та же для всех пользователей и вычисляется один раз за проход; $C^u - I$ равна нулю везде, кроме $n_u$ объектов, с которыми взаимодействовал $u$, поэтому часть, зависящая от пользователя, стоит $O(d^2 n_u)$.

Разобранный пример. У пользователя, который воспроизвёл шоу 3 раза, при $\alpha = 2$ уверенность в предпочтении 1 равна $c = 1 + 2 \cdot 3 = 7$: подгонка заботится об этой клетке так же, как о семи невоспроизведённых шоу. При $\alpha = 40$ — значении, которое Hu, Koren и Volinsky сочли хорошим для своих телевизионных данных (§4), — та же клетка весит столько же, сколько 121 невоспроизведённое шоу.

Масштаб уверенности — гиперпараметр, взаимодействующий с $\lambda$. В симуляции из раздела «Код» те же 600 пользователей воспроизводят понравившиеся объекты по нескольку раз, а случайные — по одному разу, и для каждого пользователя один понравившийся объект отложен. Рекомендация самых популярных невоспроизведённых объектов ставит отложенный объект в первые 10 для 19.8% пользователей. Неявный ALS с $\lambda$, выбранной по отдельному валидационному объекту, достигает 32.7% при $\alpha = 0$, где каждая клетка, воспроизведённая или нет, весит одинаково, 34.8% при $\alpha = 2$ и 28.5% при $\alpha = 40$ — это значение слишком доверяет счётчикам для этих данных.

Попарные альтернативы. Вместо регрессии по всем клеткам можно обучаться на парах: для пользователя $u$ объект $i$, с которым он взаимодействовал, должен стоять выше объекта $j$, с которым он не взаимодействовал. Байесовское персонализированное ранжирование (Bayesian personalized ranking, BPR; Rendle et al., 2009, §4.1) максимизирует $\sum \log \sigma(\hat r_{ui} - \hat r_{uj})$ по всем тройкам $(u, i, j)$, где $i$ наблюдаем, а $j$ не наблюдаем для $u$, с гауссовским априорным распределением на параметры. Троек слишком много, чтобы перебирать их по очереди, поэтому сумма оптимизируется стохастическим градиентным подъёмом по случайно сэмплированным тройкам (§4.2). Максимизация этой суммы минимизирует функцию потерь RankNet из предыдущей заметки плюс штраф, с пользователем вместо запроса и ненаблюдаемыми объектами в роли менее релевантных документов. Его целевая функция для одного пользователя — сглаженная версия AUC по парам (наблюдаемый, ненаблюдаемый) (§4.1.1).

Оценка рекомендаций#

Рекомендательную систему легко оценить неправильно, и все такие ошибки делают её лучше, чем она есть.

Разбиение по времени. Случайное разбиение оценок позволяет модели обучаться на оценках, поставленных после тех, на которых её тестируют: она узнаёт, какие объекты станут популярными и что каждому пользователю понравится в будущем, — информацию, которой у неё не будет после развёртывания. Честное разбиение повторяет развёртывание: обучаемся на всём, что было до момента отсечения, тестируем на том, что произошло после. Hu, Koren и Volinsky обучали модель на четырёх неделях просмотров и тестировали на следующей неделе (§6). В синтетических данных из раздела «Код», где популярность объектов дрейфует со временем, модель ранга 3 получает 0.670 при случайном разбиении и 0.705 при разбиении по времени; случайное разбиение завышает её качество, и так происходит для каждой модели. Это разбиение по времени из заметки о валидации и утечка из заметки о данных и утечках в одной из самых распространённых форм.

Измерять список. Корень из среднеквадратичной ошибки предсказанных оценок был метрикой Netflix Prize, но пользователи видят список top-$k$. Метрики предыдущей заметки применяются для каждого пользователя: точность и полнота (precision and recall) на $k$ по отложенным объектам, доля попаданий (hit rate: есть ли среди первых $k$ хотя бы один отложенный объект), MAP, NDCG. Уже просмотренные объекты удаляются из кандидатов. Объекты, с которыми пользователь не взаимодействовал в отложенный период, не обязательно нерелевантны, поэтому точность занижает истинное значение; для неявных данных метрики типа полноты — более надёжный выбор (Hu, Koren and Volinsky, 2008, §6).

Обыграть популярность. Рекомендация самых популярных объектов — сильное базовое решение, особенно для метрик, усреднённых по взаимодействиям, в которых доминируют популярные объекты. Модель, которая не обыгрывает его с заметным отрывом, не выучила ничего персонального.

Не только качество предсказаний. Список может хорошо выглядеть по метрикам качества и при этом быть бесполезным: десять почти одинаковых объектов или одни бестселлеры, которые пользователь нашёл бы и сам. Покрытие (coverage — доля каталога, которая вообще попадает в рекомендации), разнообразие (diversity) внутри списка и новизну (novelty — насколько рекомендованные объекты незнакомы пользователю) измеряют наряду с качеством предсказаний (Shani and Gunawardana, 2011). Меняют ли рекомендации поведение, а не просто предсказывают то, что пользователи сделали бы и так, может сказать только онлайн-эксперимент: A/B-тест на времени просмотра, покупках или удержании.

Холодный старт#

У нового пользователя пустая строка, у нового объекта — пустой столбец; коллаборативной фильтрации не с чем работать. Все средства привносят информацию извне матрицы. До появления какой-либо обратной связи показывают популярные или отобранные вручную объекты либо просят нового пользователя выбрать несколько любимых. Используют признаки содержания для новых объектов и контекст (устройство, страна, время) для новых пользователей — либо через отдельную контентную модель, либо внутри факторизации: Koren, Bell и Volinsky (2009, формула 6) добавляют к вектору пользователя векторы факторов объектов, с которыми пользователь взаимодействовал неявно, — их сумму, делённую на квадратный корень из их числа, — и сумму векторов факторов его известных атрибутов, так что пользователь без оценок всё равно получает вектор. В ALS из раздела «Код» пользователи без обучающих оценок до момента отсечения получают $p_u = 0$ и $b_u = 0$ и откатываются к $\mu + b_i$ — средней оценке объекта с поправкой на пользователей, которые его оценили.

Двухбашенные модели поиска кандидатов#

Матричную факторизацию можно прочитать как два поиска по таблице и скалярное произведение: идентификатор пользователя выбирает строку $P$, идентификатор объекта — строку $Q$, а итоговое значение равно $p_u^\top q_i$. Двухбашенные модели (two-tower models) заменяют поиски по таблице нейронными сетями. Башня пользователя отображает всё, что известно о пользователе, — его историю, контекст, признаки — в вектор $u(x)$; башня объекта отображает идентификатор и признаки содержания объекта в $v(y)$; итоговое значение равно $\langle u(x), v(y)\rangle$ (Yi et al., 2019, §3). Поскольку башня объекта читает содержание, новый объект получает вектор только по своим признакам, что решает проблему холодного старта для объектов.

Обучение рассматривает рекомендацию как классификацию по каталогу: какой объект выбрал данный пользователь? Вероятность объекта $y$ — softmax по всем объектам, который, поскольку в каталоге миллионы объектов, приближается softmax по объектам мини-батча, включая выбранный объект, где остальные объекты батча служат негативными примерами (формулы 1–3). Популярные объекты попадают в батчи чаще и слишком часто штрафовались бы как негативные примеры, поэтому перед softmax из каждого логита вычитается $\log p_j$ — логарифм вероятности того, что объект $j$ попадёт в батч (§3). При применении модели векторы объектов вычисляются заранее, и приближённый поиск ближайших соседей в пространстве скалярных произведений за миллисекунды возвращает несколько сотен лучших кандидатов из миллионов (Covington, Adams and Sargin, 2016, §3). Затем ранжировщик с богатыми признаками — один из обученных ранжировщиков предыдущей заметки — упорядочивает этих кандидатов. Это снова каскад из поиска кандидатов и переранжирования, а та же архитектура — это биэнкодер из заметки о семантическом поиске, обученный с тем же softmax по батчу (in-batch softmax).

Взгляд через факторизацию простирается дальше. Векторные представления слов — это факторы матрицы «слово — контекст»: skip-gram с негативным сэмплированием неявно факторизует матрицу сдвинутой поточечной взаимной информации, причём это взвешенная факторизация, в которой частые пары весят больше (Levy and Goldberg, 2014, §3.1–3.2), а GloVe подгоняет скалярные произведения плюс два смещения к логарифмам счётчиков совместной встречаемости взвешенным методом наименьших квадратов — это модель явной обратной связи выше, в которой вместо пользователей и объектов стоят слова. Заметка о Word2Vec и заметка о GloVe разбирают обе связи подробно.

Что изменилось#

	Обучение ранжированию	Рекомендательные системы
Запрос	текст с признаками	пользователь, часто известный только по истории
Описание объекта	признаки пары запрос–документ	необязательно; коллаборативная фильтрация обходится без него
Сигнал	многоуровневые метки или клики для пары (запрос, документ)	разреженная матрица «пользователь — объект»: оценки или счётчики неявной обратной связи
Модель	функция оценки от признаков	соседи в матрице; низкоранговые факторы $\mu + b_u + b_i + p_u^\top q_i$; две башни
Обучение	поточечные, попарные или списочные функции потерь	регуляризованные наименьшие квадраты через ALS или SGD; для неявных данных — с весами уверенности по всем клеткам
Новые объекты	сразу оцениваются по признакам	холодный старт: нужны признаки содержания или запасной вариант
Оценка качества	разбиение по запросам	разбиение по времени; метрики ранжирования в сравнении с базовым решением по популярности

Ограничения#

• Петли обратной связи. Рекомендательная система учится на взаимодействиях с объектами, которые сама решила показать, поэтому подкрепляет собственные прошлые решения, и популярные объекты становятся ещё популярнее. Поправка на показы требует идей вероятности просмотра из предыдущей заметки или рандомизированного исследования (exploration).
• Низкий ранг — это приближение. У вкуса длинный хвост индивидуальных особенностей, которые несколько факторов не вмещают; промышленные системы сочетают факторизацию с соседями, признаками и бустинговыми ранжировщиками.
• Оценки — не цели. Модель, предсказывающая звёзды или клики, оптимизирует именно их, а это может расходиться с тем, что ценят пользователи: кликбейт собирает клики. Выбор целевой переменной — часть проектирования.
• Холодный старт и разреженность никуда не деваются. Новые пользователи и объекты, а также длинный хвост редких объектов — именно там коллаборативные сигналы слабее всего.
• Офлайн-метрики — суррогаты. Качество на отложенной истории измеряет, насколько хорошо модель предсказывает, что пользователи делали при старой системе, а не то, как они отреагируют на новую; ответить на это могут только онлайн-эксперименты.

Что нужно запомнить#

• Матрица «пользователь — объект» разрежена, перекошена в сторону популярных объектов, и её пропуски не случайны; продукту нужен ранжированный список ещё не просмотренных объектов.
• Контентная фильтрация регрессирует оценки каждого пользователя на признаки объектов; коллаборативная фильтрация использует только матрицу — через соседей (по пользователям или по объектам, с центрированными сходствами) или латентные факторы.
• Матричная факторизация: $\hat r_{ui} = \mu + b_u + b_i + p_u^\top q_i$, обученная на известных элементах со штрафом $\ell_2$, что соответствует MAP-оценке при гауссовском шуме и гауссовских априорных распределениях.
• SGD обновляет параметры одной оценки за раз; ALS чередует гребневые регрессии в замкнутом виде для пользователей и объектов, никогда не увеличивает целевую функцию и распараллеливается.
• Неявная обратная связь: бинарное предпочтение $s_{ui}$, уверенность $c_{ui} = 1 + \alpha r_{ui}$, взвешенная подгонка всех клеток; ALS остаётся линейным по наблюдаемым клеткам благодаря $Q^\top C^u Q = Q^\top Q + Q^\top(C^u - I)Q$.
• Оценивать — с разбиением по времени, метриками ранжирования и базовым решением по популярности; холодный старт решать с помощью содержания, контекста или популярности.
• Двухбашенные модели обобщают факторизацию на признаки, обучаются с softmax по батчу и находят кандидатов для ранжировщика поиском ближайших соседей.

Код#

Соседи по объектам и шаг ALS на игрушечных числах, матричная факторизация на синтетических оценках при случайном разбиении и разбиении по времени и неявный ALS на синтетических воспроизведениях:

import numpy as np

# соседи по объектам на игрушечной матрице: пять пользователей, пять фильмов, nan = нет оценки
R = np.array([[5, 4, np.nan, 1, np.nan], [4, 5, 1, np.nan, 2], [np.nan, 4, 2, 1, 1],
              [1, np.nan, 5, 4, np.nan], [2, 1, 4, np.nan, 5]])
seen = ~np.isnan(R)
C = np.where(seen, R - np.nanmean(R, 1, keepdims=True), 0)            # центрируем оценки каждого пользователя
def sim(i, j):                                                         # скорректированный косинус по пользователям, оценившим оба объекта
    both = seen[:, i] & seen[:, j]
    a, b = C[both, i], C[both, j]
    return a @ b / np.sqrt((a @ a) * (b @ b))
s = np.array([sim(2, j) for j in (0, 1, 3)])
print(s.round(3), (np.nanmean(R[0]) + s @ C[0, [0, 1, 3]] / np.abs(s).sum()).round(2))   # [-0.905 -0.775  0.555] 1.85

# один шаг ALS для одного пользователя: гребневая регрессия на векторах оценённых им объектов
Qu, ru = np.array([[1.0, 0.0], [1.0, 1.0]]), np.array([2.0, 1.0])
pu = np.linalg.solve(Qu.T @ Qu + 0.1 * np.eye(2), Qu.T @ ru)
print(pu.round(3), (Qu @ pu).round(3))                                 # [ 1.756 -0.687] [1.756 1.069]

# синтетические оценки: смещения + модель вкуса ранга 3 + шум; популярность объектов дрейфует со временем
rng = np.random.default_rng(0)
m, n = 600, 400
P0, Q0 = rng.normal(0, 0.6, (m, 3)), rng.normal(0, 0.6, (n, 3))
bu0, bi0, drift = rng.normal(0, 0.4, m), rng.normal(0, 0.5, n), rng.normal(0, 0.6, n)
pop = rng.zipf(1.6, n).clip(max=60).astype(float); pop /= pop.sum()    # длинный хвост популярности
U = np.concatenate([np.full(k, u) for u, k in enumerate(rng.integers(5, 60, m))])
I = np.concatenate([rng.choice(n, (U == u).sum(), replace=False, p=pop) for u in range(m)])
T = rng.random(len(U))                                                  # время каждой оценки, в [0, 1]
r = 3.6 + bu0[U] + bi0[I] + drift[I] * (T - 0.5) + (P0[U] * Q0[I]).sum(1) + rng.normal(0, 0.5, len(U))
r = np.clip(np.round(r), 1, 5)
print(len(r), round(len(r) / (m * n), 3), (np.sort(np.bincount(I, minlength=n))[::-1][:n // 10].sum() / len(r)).round(3))
# 18872 0.079 0.527

def als(u, i, r, d, lam=0.05, iters=10):     # чередуем гребневые регрессии; столбец 0 матриц P и Q хранит смещения
    mu, P, Q = r.mean(), np.zeros((m, d + 1)), rng.normal(0, 0.1, (n, d + 1))
    for _ in range(iters):
        for A, B, a_idx, b_idx in ((P, Q, u, i), (Q, P, i, u)):
            Z_all = B.copy(); Z_all[:, 0] = 1                           # регрессоры: 1 для смещения, затем факторы другой стороны
            res = r - mu - B[b_idx, 0]
            order = np.argsort(a_idx); cuts = np.searchsorted(a_idx[order], np.arange(len(A) + 1))
            for a in range(len(A)):
                k = order[cuts[a]:cuts[a + 1]]
                Z = Z_all[b_idx[k]]
                A[a] = np.linalg.solve(Z.T @ Z + lam * max(len(k), 1) * np.eye(d + 1), Z.T @ res[k])
    return lambda uu, ii: mu + P[uu, 0] + Q[ii, 0] + (P[uu, 1:] * Q[ii, 1:]).sum(1)

def sgd(u, i, r, d=3, lam=0.05, lr=0.02, epochs=40, batch=64):       # та же целевая функция, по одному мини-батчу за шаг
    mu, bu, bi = r.mean(), np.zeros(m), np.zeros(n)
    P, Q = rng.normal(0, 0.1, (m, d)), rng.normal(0, 0.1, (n, d))
    for _ in range(epochs):
        for k in np.array_split(rng.permutation(len(r)), len(r) // batch):
            e = r[k] - mu - bu[u[k]] - bi[i[k]] - (P[u[k]] * Q[i[k]]).sum(1)
            gP, gQ = e[:, None] * Q[i[k]] - lam * P[u[k]], e[:, None] * P[u[k]] - lam * Q[i[k]]
            np.add.at(bu, u[k], lr * (e - lam * bu[u[k]])); np.add.at(bi, i[k], lr * (e - lam * bi[i[k]]))
            np.add.at(P, u[k], lr * gP); np.add.at(Q, i[k], lr * gQ)
    return lambda uu, ii: mu + bu[uu] + bi[ii] + (P[uu] * Q[ii]).sum(1)

rmse = lambda f, k: np.sqrt(np.mean((f(U[k], I[k]) - r[k]) ** 2)).round(3)
for name, test in (('random split', rng.random(len(r)) < 0.2), ('time split', T > 0.8)):
    tr = ~test
    print(name, np.sqrt(np.mean((r[tr].mean() - r[test]) ** 2)).round(3),       # глобальное среднее
          *[rmse(als(U[tr], I[tr], r[tr], d), test) for d in (0, 3, 10)])     # только смещения, ранг 3, ранг 10
print('SGD, rank 3, time split', rmse(sgd(U[tr], I[tr], r[tr]), test))
# random split 0.966 0.8 0.67 0.732 | time split 0.969 0.835 0.705 0.756 | SGD, rank 3, time split 0.702

# неявная обратная связь: те же пользователи и объекты, видимые через воспроизведения. Понравившиеся объекты
# воспроизводятся снова и снова, случайные — по разу. У каждого пользователя отложены два понравившихся: для валидации и для теста.
taste = np.exp(np.log(pop) + 2 * P0 @ Q0.T); taste /= taste.sum(1, keepdims=True)
plays, held = np.zeros((m, n)), np.zeros((m, 2), int)
for u in range(m):
    liked = rng.choice(n, rng.integers(5, 30), replace=False, p=taste[u])
    plays[u, liked] = 1 + rng.poisson(3, len(liked))
    noise = rng.integers(0, n, rng.integers(5, 30))
    plays[u, noise] = np.maximum(plays[u, noise], 1)
    held[u] = rng.choice(liked, 2, replace=False); plays[u, held[u]] = 0
def hit_rate(S, col):                                                   # входит ли отложенный объект в первые 10 невоспроизведённых?
    top = np.argsort(np.where(plays > 0, np.inf, -S), 1)[:, :10]
    return (top == held[:, [col]]).any(1).mean().round(3)
def ials(alpha, lam, d=8, iters=8):                                     # веса 1 + alpha * plays на каждой клетке, включая нули
    s, c = (plays > 0).astype(float), 1 + alpha * plays
    X, Y = rng.normal(0, 0.1, (m, d)), rng.normal(0, 0.1, (n, d))
    for _ in range(iters):
        for A, B, cA, sA in ((X, Y, c, s), (Y, X, c.T, s.T)):
            BtB = B.T @ B                                               # вычисляется один раз за проход, общая для всех строк
            for a in range(len(A)):
                k = np.flatnonzero(sA[a]); Bk = B[k]
                A[a] = np.linalg.solve(BtB + Bk.T @ ((cA[a, k] - 1)[:, None] * Bk) + lam * np.eye(d), Bk.T @ cA[a, k])
    return X @ Y.T
print('popularity', hit_rate(np.tile((plays > 0).sum(0), (m, 1)).astype(float), 1))   # popularity 0.198
for alpha in (0, 2, 40):
    fits = {lam: ials(alpha, lam) for lam in (10, 50, 200)}
    best = max(fits, key=lambda lam: hit_rate(fits[lam], 0))            # выбираем lambda по валидационному объекту
    print('alpha', alpha, 'lambda', best, 'validation', hit_rate(fits[best], 0), 'test', hit_rate(fits[best], 1))
# alpha 0 lambda 10 validation 0.347 test 0.327 | alpha 2 lambda 50 validation 0.363 test 0.348
# alpha 40 lambda 200 validation 0.315 test 0.285

Курс в одном абзаце#

Курс начался с обещания и опасности: программа может выучить правило по примерам, а правило, идеально подогнанное под примеры, всё равно может ошибиться на следующем, поэтому валидация появилась раньше любой модели. Дальше каждый метод отвечал на ограничение предыдущего, пока последние разделы не сменили задачу. Ближайшие соседи теряли смысл в высокой размерности, и метод наименьших квадратов дал глобальную структуру, прочитанную как максимальное правдоподобие при гауссовском шуме; градиентный спуск обучал то, у чего нет решения в замкнутом виде, а регуляризация, прочитанная как априорное распределение, не давала подгонке гнаться за шумом. Для классов логистическая регрессия заменила квадратичную ошибку правдоподобием Бернулли, метрики считали те ошибки, которые важны, а отступы (margins) и ядра изгибали границу. Деревья выражали взаимодействия, разложение на смещение и разброс объяснило, почему помогают усреднение и бустинг, а нейронные сети выучивали сами признаки через обратное распространение ошибки. Без разметки кластеризация, EM-алгоритм, понижение размерности и поиск аномалий находили структуру, а две последние заметки превратили числовые оценки в порядки. Под всем этим лежала вероятность: многие функции потерь — это отрицательные логарифмы правдоподобия (кусочно-линейная функция потерь SVM — нет), штрафы — априорные распределения, цель регрессии — условное математическое ожидание, а значение метрики на валидации — это среднее: закон больших чисел делает его состоятельным, центральная предельная теорема даёт приближённо нормальную ошибку, а неравенства концентрации дают явные границы при своих предположениях. Те же элементы переходят в следующие курсы: логистическая регрессия на признаках мешка слов, softmax и кросс-энтропия в языковых моделях, обратное распространение через рекуррентные сети, эмбеддинги как факторизованные совместные встречаемости и поиск с переранжированием в RAG; а в генеративном моделировании PCA вырастает в автоэнкодеры, EM — в VAE, ядра — в максимальное расхождение средних (maximum mean discrepancy) из Kernel Inception Distance, а оценки аномальности — в модели, основанные на энергии.

Литература#

• Y. Koren, R. Bell, C. Volinsky. Matrix Factorization Techniques for Recommender Systems. IEEE Computer, 42(8), 2009. Контентная и коллаборативная фильтрация, базовая модель и её целевая функция (формулы 1–2), SGD и ALS, смещения (формулы 3–5), дополнительные входы для холодного старта (формула 6), веса уверенности (формула 8), Netflix Prize.
• Y. Hu, Y. Koren, C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets. ICDM, 2008. Свойства неявной обратной связи (§1), предпочтение и уверенность, целевая функция (§4, формула 3), обновление ALS и его ускорение (формула 4), оценка качества на следующей неделе (§6).
• R. Salakhutdinov, A. Mnih. Probabilistic Matrix Factorization. NeurIPS, 2008. Гауссовское правдоподобие и априорные распределения, регуляризованная целевая функция (§2, формулы 1–4).
• B. Sarwar, G. Karypis, J. Konstan, J. Riedl. Item-Based Collaborative Filtering Recommendation Algorithms. WWW, 2001. Скорректированное косинусное сходство (§3.1.3), предсказание взвешенной суммой (§3.2.1).
• G. Linden, B. Smith, J. York. Amazon.com Recommendations: Item-to-Item Collaborative Filtering. IEEE Internet Computing, 7(1), 2003.
• S. Rendle, C. Freudenthaler, Z. Gantner, L. Schmidt-Thieme. BPR: Bayesian Personalized Ranking from Implicit Feedback. UAI, 2009. Критерий BPR (§4.1), его связь с AUC (§4.1.1) и его оптимизация с помощью SGD по сэмплированным тройкам (§4.2).
• G. Shani, A. Gunawardana. Evaluating Recommendation Systems. В книге Recommender Systems Handbook, Springer, 2011. Качество предсказаний, покрытие, новизна и разнообразие.
• P. Covington, J. Adams, E. Sargin. Deep Neural Networks for YouTube Recommendations. RecSys, 2016. Генерация кандидатов как экстремальная многоклассовая классификация, применяемая через поиск ближайших соседей (§3).
• X. Yi, J. Yang, L. Hong, D. Z. Cheng, L. Heldt, A. Kumthekar, Z. Zhao, L. Wei, E. Chi. Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations. RecSys, 2019. Двухбашенная модель, softmax по батчу и поправка на логарифм вероятности (§3, формулы 1–4).
• O. Levy, Y. Goldberg. Neural Word Embedding as Implicit Matrix Factorization. NeurIPS, 2014. SGNS как факторизация матрицы сдвинутой PMI (§3.1) и как взвешенная матричная факторизация (§3.2).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 19: рекомендательные системы и лекция 20: рекомендательные системы, оценка качества, 2019.