SVD в рекомендательных системах

Материал из MachineLearning.

Версия от 21:22, 4 июля 2026; Nikita Saveliuk (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM Claude Opus 4.8 и проверена участником Nikita Saveliuk 01:22, 5 июля 2026 (MSD)

Содержание

1 Историческая справка
2 Постановка задачи
3 Метод
4 Свойства
- 4.1 Преимущества
- 4.2 Ограничения
5 Применение
6 См. также
7 Ссылки
8 Литература

Приближение матрицы «пользователь–объект» произведением матриц низкого ранга — один из центральных подходов коллаборативной фильтрации, известный в рекомендательных системах под названием SVD (от англ. Singular Value Decomposition). Идея состоит в том, чтобы описать каждого пользователя и каждый объект вектором из небольшого числа скрытых факторов так, чтобы оценка пользователя объекту приближалась скалярным произведением их векторов. Подход получил широкую известность в ходе конкурса Netflix Prize (2006–2009), где модели этого семейства превзошли классические методы на основе ближайших соседей (Koren et al., 2009).

Важная терминологическая тонкость: то, что в рекомендациях называют «SVD», в общем случае не является сингулярным разложением в смысле линейной алгебры. Классический SVD определён для полностью заданной матрицы и через теорему Эккарта–Янга даёт наилучшее низкоранговое приближение. Матрица же оценок почти всегда разрежена — большинство её элементов неизвестны, — поэтому классическое разложение к ней неприменимо напрямую. Метод, унаследовавший название «SVD», оптимизирует приближение только по наблюдённым оценкам и отказывается от ортогональности факторов; по сути это регуляризованная матричная факторизация.

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

Историческая справка

Сингулярное разложение как объект линейной алгебры известно с работ Бельтрами и Жордана 1870-х годов. Ключевой для приложений результат — теорема Эккарта–Янга (1936) — утверждает, что усечённое сингулярное разложение даёт наилучшее приближение матрицы матрицей меньшего ранга по норме Фробениуса. На этом основано применение SVD для снижения размерности, в частности латентно-семантический анализ текстов (Deerwester et al., 1990).

Перенос идеи на рекомендательные системы столкнулся с разреженностью матрицы оценок. Ранние работы (Sarwar et al., 2000) заполняли пропуски усреднёнными значениями и затем применяли классический SVD, однако заполнение искажало данные и было вычислительно дорогим. Перелом произошёл во время Netflix Prize: в 2006 году Саймон Функ в открытом блоге описал приём, позднее названный Funk SVD, — обучать факторизацию градиентным спуском только по известным оценкам, с регуляризацией. Развитие этих идей Йегудой Кореном и соавторами (смещения, SVD++, учёт времени) и модель для неявной обратной связи (Hu et al., 2008) сформировали современный облик метода. Итог обобщён в обзорной работе Koren, Bell, Volinsky (2009), ставшей канонической ссылкой.

Постановка задачи

Пусть имеется $m$ пользователей и $n$ объектов. Известные оценки образуют разреженную матрицу $R \in \mathbb{R}^{m \times n}$ , где элемент $r_{ui}$ — оценка, поставленная пользователем $u$ объекту $i$ . Заданы лишь оценки из наблюдённого множества пар $\mathcal{K}$ ; подавляющее большинство элементов $R$ отсутствует. Задача — предсказать неизвестные оценки $r_{ui}$ для пар $(u, i) \notin \mathcal{K}$ и на их основе ранжировать объекты для пользователя.

Специфика задачи — именно в неполноте $R$ . Классическое сингулярное разложение требует полностью заданной матрицы: сумма квадратов отклонений в теореме Эккарта–Янга берётся по всем элементам. Для разреженной $R$ это выражение не определено. Заполнение пропусков возвращает задачу в область применимости SVD, но вносит систематическое смещение (заполняющее значение становится «целью» для ненаблюдённых пар) и уничтожает разреженность, делая разложение неподъёмным по памяти. Поэтому в рекомендательных системах оптимизируют иную, определённую только на наблюдённой части величину.

Метод

Классический SVD и теорема Эккарта–Янга

Любая матрица $R \in \mathbb{R}^{m \times n}$ раскладывается в произведение:

$R = U \Sigma V^{\top}$ ,

где $U$ и $V$ — ортогональные матрицы левых и правых сингулярных векторов, а $\Sigma$ — диагональная матрица неотрицательных сингулярных чисел. Оставив $k$ наибольших сингулярных чисел и соответствующие векторы, получаем усечённое разложение $R_k = U_k \Sigma_k V_k^{\top}$ ранга $k$ . По теореме Эккарта–Янга оно оптимально:

$\| R - R_k \|_F = \min_{\mathrm{rank}(B) \le k} \| R - B \|_F$ ,

то есть среди всех матриц ранга не выше $k$ усечённый SVD ближе всего к $R$ по норме Фробениуса. Именно этот результат делает SVD инструментом снижения размерности. Существенно, что оптимизируемая норма берётся по всем элементам матрицы — что и требует её полной заданности.

Матричная факторизация как «SVD» в рекомендациях

В рекомендательной постановке каждому пользователю сопоставляется вектор скрытых факторов $p_u \in \mathbb{R}^{k}$ , каждому объекту — вектор $q_i \in \mathbb{R}^{k}$ , а оценка приближается их скалярным произведением:

$\hat{r}_{ui} = p_u^{\top} q_i$ ,

Векторы факторов ищутся минимизацией регуляризованной квадратичной ошибки только по наблюдённым оценкам:

$\min_{P,\, Q} \sum_{(u,i) \in \mathcal{K}} \bigl( r_{ui} - p_u^{\top} q_i \bigr)^{2} + \lambda \bigl( \| p_u \|^{2} + \| q_i \|^{2} \bigr)$ ,

Здесь $P$ и $Q$ — матрицы факторов пользователей и объектов, $\lambda$ — коэффициент $L_2$ -регуляризации, сдерживающий переобучение на пользователях и объектах с малым числом оценок.

Ключевое, но часто упускаемое обстоятельство: решение этой задачи в общем случае не совпадает с усечённым сингулярным разложением какой-либо матрицы. Во-первых, ортогональность $U$ и $V$ здесь не накладывается — $p_u$ и $q_i$ произвольны. Во-вторых, сумма берётся не по всей матрице, а лишь по $\mathcal{K}$ , поэтому гарантия оптимальности Эккарта–Янга неприменима. В-третьих, в отличие от полного SVD, имеющего замкнутое решение, эта задача невыпукла по паре $(P, Q)$ и решается итеративно, с риском попасть в локальный минимум. Классический SVD оказывается частным случаем: если бы $R$ была полностью наблюдаема, а $\lambda = 0$ , минимизация той же ошибки по всем элементам восстановила бы усечённое разложение с точностью до вращения факторов. Название «SVD» удержалось по историческим причинам (Funk, Netflix Prize), обозначая регуляризованную матричную факторизацию.

Обучение через стохастический градиентный спуск

Для каждой наблюдённой оценки вычисляется ошибка предсказания:

$e_{ui} = r_{ui} - \hat{r}_{ui}$ ,

Дифференцируя слагаемое целевой функции по $p_u$ и $q_i$ , получаем шаги стохастического градиентного спуска, обновляющие факторы навстречу антиградиенту:

$p_u \leftarrow p_u + \gamma\bigl( e_{ui}\, q_i - \lambda\, p_u \bigr)$ ,

$q_i \leftarrow q_i + \gamma\bigl( e_{ui}\, p_u - \lambda\, q_i \bigr)$ ,

где $\gamma$ — скорость обучения. Каждое обновление затрагивает только факторы, участвующие в данной оценке, поэтому одна эпоха стоит порядка $|\mathcal{K}|$ операций и линейна по числу известных оценок — это и обеспечивает масштабируемость на разреженных данных.

Учёт смещений

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

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

где $\mu$ — глобальное среднее, $b_u$ и $b_i$ — смещения пользователя и объекта. Смещения обучаются теми же шагами SGD:

$b_u \leftarrow b_u + \gamma\bigl( e_{ui} - \lambda\, b_u \bigr), \qquad b_i \leftarrow b_i + \gamma\bigl( e_{ui} - \lambda\, b_i \bigr)$ ,

Учёт смещений заметно повышает точность и позволяет скалярному произведению $p_u^{\top} q_i$ моделировать именно отклонение от базового уровня, а не общий сдвиг.

SVD++ и неявная обратная связь

Даже без явной оценки сам факт взаимодействия (просмотр, клик, покупка) несёт информацию о предпочтениях. Модель SVD++ добавляет к вектору пользователя вклад объектов, с которыми он взаимодействовал:

$\hat{r}_{ui} = \mu + b_u + b_i + q_i^{\top}\Bigl( p_u + |N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_j \Bigr)$ ,

где $N(u)$ — множество объектов с неявной обратной связью пользователя $u$ , $y_j$ — обучаемые векторы этих объектов, а нормировка $|N(u)|^{-\frac{1}{2}}$ уравнивает вклад пользователей с разной активностью. SVD++ был одним из сильнейших одиночных предикторов в решениях Netflix Prize.

ALS как альтернатива обучению

Целевая функция невыпукла по паре $(P, Q)$ , но выпукла по каждой матрице при фиксированной другой. Это основа метода попеременных наименьших квадратов (ALS): при фиксированных факторах объектов оптимальные факторы каждого пользователя находятся в замкнутом виде как решение гребневой регрессии:

$p_u = \bigl( Q_{(u)}^{\top} Q_{(u)} + \lambda I \bigr)^{-1} Q_{(u)}^{\top} r_{(u)}$ ,

где $Q_{(u)}$ — матрица факторов объектов, оценённых пользователем $u$ , а $r_{(u)}$ — вектор его оценок. Затем факторы объектов пересчитываются симметрично, и шаги чередуются. ALS легко распараллеливается по пользователям и объектам и особенно удобен для неявной обратной связи, где сумма идёт по всем парам с весами-уверенностями (Hu et al., 2008), что делает поэлементный SGD неэффективным.

Свойства

Преимущества

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

Ограничения

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

Применение

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

См. также

Ссылки

Литература

Koren Y., Bell R., Volinsky C. Matrix Factorization Techniques for Recommender Systems // Computer (IEEE). — 2009. — Т. 42. — № 8. — С. 30–37.

Hu Y., Koren Y., Volinsky C. Collaborative Filtering for Implicit Feedback Datasets // Proceedings of the 8th IEEE International Conference on Data Mining (ICDM). — 2008. — С. 263–272.

Sarwar B., Karypis G., Konstan J., Riedl J. Application of Dimensionality Reduction in Recommender System — A Case Study // WebKDD Workshop. — 2000.

Eckart C., Young G. The approximation of one matrix by another of lower rank // Psychometrika. — 1936. — Т. 1. — № 3. — С. 211–218.

Funk S. Netflix Update: Try This at Home2006.

Источник — «http://machinelearning.ru/wiki/index.php?title=SVD_%D0%B2_%D1%80%D0%B5%D0%BA%D0%BE%D0%BC%D0%B5%D0%BD%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0%D1%85»