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

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

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

Содержание

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

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

За семейством закрепилось имя «SVD», хотя в рекомендательном контексте оно употребляется в расширенном смысле. Точное сингулярное разложение определено лишь для полностью заполненной матрицы, тогда как матрица оценок огромна (миллионы пользователей и объектов) и заполнена на доли процента, а предсказывать нужно именно пропуски. Поэтому реальные алгоритмы — Funk SVD, SVD++, ALS, NMF — приближают наблюдаемые ячейки латентными факторами, обучаемыми оптимизацией, и связаны с классическим разложением скорее идейно, чем алгебраически. Низкоранговая структура формализует интуицию о том, что предпочтения определяются небольшим числом скрытых факторов — жанром, ценовым сегментом, настроением, — общих для пользователей и объектов.

Эти методы занимают промежуточное положение между соседскими (memory-based) подходами, опирающимися на явные меры похожести, и современными нейросетевыми моделями коллаборативной фильтрации. Прорыв 2006–2009 годов в рамках конкурса Netflix Prize сделал их де-факто стандартом: латентные модели оказались точнее, компактнее и масштабируемее соседских, а их обобщения — учёт смещений, неявной обратной связи, времени — задали словарь, на котором до сих пор описывают рекомендательные системы.

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

Первое прямое применение сингулярного разложения к рекомендациям предложили Сарвар, Карипис, Констан и Ридл (Sarwar et al., 2000): пропуски в матрице оценок заполнялись средними значениями, после чего к полученной плотной матрице применялось усечённое SVD. Подход страдал двумя пороками — заполнение средними вносило систематическое смещение, а разложение матрицы размером в миллионы строк было вычислительно неподъёмным.

Перелом наступил во время конкурса Netflix Prize (2006–2009, приз в 1 млн долларов за улучшение точности на 10 %). В декабре 2006 года участник под псевдонимом Simon Funk (Брэндин Уэбб) опубликовал в блоге метод, который вошёл в обиход как «Funk SVD». Его ключевая идея — отказаться от восстановления полной матрицы и обучать латентные векторы стохастическим градиентным спуском, минимизируя ошибку только на известных оценках. Это превратило неподъёмное разложение в задачу, линейную по числу наблюдений.

Развитие шло стремительно. Корен, Белл и Волински систематизировали подход и ввели смещения пользователей и объектов; Корен предложил модель SVD++ (Koren, 2008), включающую неявную обратную связь (сам факт оценивания объекта несёт информацию), и temporal-расширение timeSVD++, учитывающее дрейф предпочтений во времени. Параллельно развивались альтернативные схемы оптимизации и ограничения на знак факторов — попеременные наименьшие квадраты (ALS) и неотрицательное матричное разложение (NMF). Победившая в конкурсе модель BellKor's Pragmatic Chaos была ансамблем, ядром которого служили именно факторизационные методы.

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

Пусть имеется множество из $m$ пользователей и $n$ объектов. Взаимодействия задаются частично наблюдаемой матрицей оценок $R \in \mathbb{R}^{m \times n}$ , в которой известна лишь малая доля ячеек. Обозначим через $\Omega$ множество наблюдаемых пар $(u,i)$ — тех, для которых оценка $r_{ui}$ известна. Типичная плотность $|\Omega|/(mn)$ составляет 1 % и ниже.

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

Качество измеряют среднеквадратичной ошибкой на отложенной части наблюдений:

$\mathrm{RMSE} = \sqrt{\frac{1}{|\mathcal{T}|} \sum_{(u,i) \in \mathcal{T}} \bigl(r_{ui} - \hat{r}_{ui}\bigr)^{2}}$

Здесь $\mathcal{T}$ — тестовое множество пар, $r_{ui}$ — истинная оценка, $\hat{r}_{ui}$ — предсказание модели. Именно по RMSE оценивались решения Netflix Prize. В задачах с неявной обратной связью (клики, просмотры) вместо RMSE используют ранжирующие метрики (Recall@k, NDCG), что меняет и формулировку функции потерь.

Метод

Классическое сингулярное разложение и связь с PCA

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

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

где $U \in \mathbb{R}^{m \times m}$ и $V \in \mathbb{R}^{n \times n}$ ортогональны, а $\Sigma$ диагональна с неотрицательными сингулярными числами $\sigma_1 \ge \sigma_2 \ge \ldots \ge 0$ на диагонали. Усечение до $k$ старших компонент даёт приближение $R_k = U_k \Sigma_k V_k^{\top}$ .

Теорема Эккарта–Янга утверждает, что $R_k$ — наилучшее приближение ранга $k$ в норме Фробениуса и в спектральной норме:

$R_k = \arg\min_{\mathrm{rank}(\tilde{R}) \le k} \, \|R - \tilde{R}\|_{F}$

Это и есть мост к методу главных компонент. Если предварительно вычесть из $R$ средние по столбцам, то правые сингулярные векторы (столбцы $V$ ) совпадают с главными компонентами, а квадраты сингулярных чисел $\sigma_i^{2}$ равны собственным значениям матрицы рассеяния $R^{\top} R$ и измеряют долю дисперсии, объяснённую вдоль $i$ -й латентной оси. Геометрически SVD поворачивает систему координат к ортогональным направлениям максимальной вариативности, а сингулярные числа задают «полуоси» эллипсоида данных; усечение отбрасывает направления с наименьшей дисперсией.

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

Funk SVD: латентные факторы по наблюдаемым ячейкам

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

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

Координаты $p_u$ интерпретируются как сила интереса пользователя к скрытому фактору, координаты $q_i$ — как выраженность этого фактора в объекте. Факторы оцениваются минимизацией регуляризованной ошибки только на $\Omega$ :

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

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

Что на самом деле регуляризует L2-штраф

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

$\|X\|_{*} = \min_{X = P Q^{\top}} \frac{1}{2}\bigl(\|P\|_{F}^{2} + \|Q\|_{F}^{2}\bigr)$

где $\|\cdot\|_{*}$ — ядерная (следовая) норма, $\|\cdot\|_{F}$ — норма Фробениуса, а минимум берётся по всем разложениям. Иными словами, L2-штраф на факторы — это в точности ядерная норма произведения $P Q^{\top}$ , а ядерная норма есть выпуклая оболочка ранга на единичном спектральном шаре. Поэтому регуляризованная факторизация эквивалентна задаче восстановления матрицы с минимальной ядерной нормой (Srebro et al., 2004; Hastie et al., 2015): при достаточно большом $k$ именно $\lambda$ , а не $k$ , управляет эффективным рангом решения. Это объясняет наблюдаемую на практике устойчивость качества к увеличению $k$ при фиксированной регуляризации.

У того же критерия есть и вероятностное прочтение. Если положить оценки нормально распределёнными вокруг $p_u^{\top} q_i$ , а на факторы наложить гауссовские априорные распределения с нулевым средним, то минимизация регуляризованной ошибки совпадает с поиском апостериорного максимума (MAP), причём $\lambda$ равно отношению дисперсии шума к дисперсии априорного распределения. Эта модель — вероятностная матричная факторизация (Salakhutdinov, Mnih, 2008) — превращает эвристический штраф в следствие байесовских допущений и открывает путь к полностью байесовским вариантам.

Наконец, факторы не определены однозначно. Для любой обратимой матрицы $G$ размера $k \times k$ замена $P \to PG$ и $Q \to Q (G^{-1})^{\top}$ не меняет произведения $P Q^{\top}$ , а для ортогональной $G$ сохраняется и значение фробениусова штрафа. Решение определено лишь с точностью до поворота латентного пространства — поэтому отдельные координаты обученных факторов, в отличие от упорядоченных по дисперсии осей классического SVD, как правило, не имеют самостоятельного смысла, и попытки «прочитать» отдельную латентную ось чаще всего обманчивы.

Смещения и базовый предиктор

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

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

где $\mu$ — глобальное среднее всех оценок, $b_u$ — смещение пользователя, $b_i$ — смещение объекта. Латентная часть $p_u^{\top} q_i$ моделирует уже остаток после вычитания этих базовых уровней, что заметно повышает точность и устойчивость.

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

Обозначим ошибку на наблюдаемой ячейке $e_{ui} = r_{ui} - \hat{r}_{ui}$ . Для каждой пары $(u,i) \in \Omega$ параметры обновляются по антиградиенту с шагом $\gamma$ :

$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)$

Аналогично обновляются смещения: $b_u \leftarrow b_u + \gamma(e_{ui} - \lambda b_u)$ и $b_i \leftarrow b_i + \gamma(e_{ui} - \lambda b_i)$ . Сложность одной эпохи — $O(|\Omega| \cdot k)$ , то есть линейна по числу наблюдений, что и сделало метод практичным на матрицах Netflix.

ALS: попеременные наименьшие квадраты

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

$p_u = \bigl(Q_{\Omega_u}^{\top} Q_{\Omega_u} + \lambda I\bigr)^{-1} Q_{\Omega_u}^{\top} r_u$

где $Q_{\Omega_u}$ — подматрица факторов объектов, оценённых пользователем $u$ , $r_u$ — вектор его оценок, $I$ — единичная матрица размера $k \times k$ . Симметрично пересчитывается $Q$ при фиксированной $P$ . ALS легко распараллеливается (строки $P$ независимы) и особенно популярен для данных с неявной обратной связью, где формулировка Ху, Корена и Волински (Hu et al., 2008) вводит веса доверия $c_{ui} = 1 + \alpha r_{ui}$ и суммирование уже по всем парам, а не только по наблюдаемым.

NMF: неотрицательное матричное разложение

Если потребовать $P \ge 0$ и $Q \ge 0$ поэлементно, факторы становятся аддитивными «частями»: предпочтение складывается из неотрицательных вкладов, что повышает интерпретируемость. Ли и Сын (Lee, Seung, 1999) предложили мультипликативные правила обновления, монотонно убывающие по ошибке и автоматически сохраняющие неотрицательность без проекции. Платой за интерпретируемость становится менее гибкая модель: запрет на отрицательные координаты сужает класс представимых взаимодействий.

От оценок к ранжированию

В большинстве промышленных задач явных оценок нет, а есть неявные сигналы (клики, прослушивания), и пользователю нужен короткий упорядоченный список. Минимизация RMSE здесь плохо согласована с целью: важна не точность абсолютного балла, а правильный порядок объектов. Ренгле с соавторами (Rendle et al., 2009) предложили критерий BPR (Bayesian Personalized Ranking), который оптимизирует попарное предпочтение — вероятность того, что объект, с которым было взаимодействие, окажется в выдаче выше объекта без взаимодействия:

$\max_{P,\,Q} \sum_{(u,\,i,\,j)} \ln \sigma\bigl(p_u^{\top} q_i - p_u^{\top} q_j\bigr) - \lambda\,\Omega(P, Q)$

где $\sigma$ — логистическая функция, тройка $(u, i, j)$ состоит из пользователя, наблюдённого объекта $i$ и случайного ненаблюдённого $j$ , а $\Omega(P, Q)$ — регуляризатор. Та же факторизация, но иная функция потерь — и модель учится ранжировать, а не предсказывать балл.

Естественно спросить, не пора ли заменить само скалярное произведение обучаемой нелинейной мерой сходства — например, многослойным перцептроном. Долгое время считалось, что такая нейронная коллаборативная фильтрация строго мощнее. Ренгле с соавторами (Rendle et al., 2020) показали обратное: при аккуратном подборе гиперпараметров обычное скалярное произведение устойчиво превосходит обученные MLP-сходства на тех же данных, а перцептрону, вопреки теореме об универсальной аппроксимации, эмпирически трудно воспроизвести даже простое скалярное произведение. Помимо точности, скалярное произведение допускает поиск ближайших соседей сублинейной сложности (maximum inner product search), тогда как обучаемая мера требует полного перебора. Этот результат вернул матричной факторизации статус сильной и недооценённой базовой модели.

Свойства

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

Линейная по числу наблюдений сложность обучения и компактность модели — хранится $(m+n)k$ чисел вместо плотной матрицы из $mn$ элементов.
Сжатие в латентное пространство сглаживает разреженность: предсказание возможно даже для пар, не имеющих общих соседей, что недоступно чисто соседским методам.
Гибкость каркаса: смещения, неявная обратная связь, временной дрейф и контентные признаки встраиваются как дополнительные слагаемые предиктора.
Сильная и дешёвая базовая модель: при аккуратной настройке скалярное произведение конкурентоспособно с куда более тяжёлыми нейросетевыми сходствами и допускает быстрый поиск ближайших соседей.

Ограничения

Проблема холодного старта: для нового пользователя или объекта без истории взаимодействий вектор факторов оценить не из чего.
Билинейность взаимодействия: модель улавливает лишь согласование факторов через скалярное произведение и не выражает напрямую логических условий вида «нравится A, только если есть B».
Невыпуклость по $(P, Q)$ означает зависимость результата от инициализации и гиперпараметров; глобальный оптимум не гарантирован, а отдельные латентные оси из-за поворотной неоднозначности обычно не интерпретируемы.
Усиление популярностного смещения: оптимизация RMSE склонна точнее обслуживать активных пользователей и популярные объекты, обедняя разнообразие выдачи в «длинном хвосте».
Рассогласование потерь и цели: RMSE оптимизирует абсолютный балл, тогда как качество рекомендаций определяется порядком объектов, что и мотивирует переход к ранжирующим критериям.

Применение

Матричная факторизация стала ядром промышленных рекомендательных систем медиа-сервисов, маркетплейсов и музыкальных платформ. Исторический эталон — конкурс Netflix Prize, где факторизационные модели сформировали основу победившего ансамбля. В системах с неявной обратной связью (прослушивания, покупки, клики) доминирует ALS-формулировка с весами доверия, реализованная в распределённых фреймворках вроде Spark MLlib. Латентные представления, обученные факторизацией, используются и за пределами прямого предсказания оценок — как признаки для последующих ранжирующих моделей и как инициализация для нейросетевых рекомендаций. Учебные и исследовательские эксперименты опираются на датасеты MovieLens, Netflix и Last.fm и на библиотеки Surprise, implicit и LightFM.

См. также

Ссылки

Simon Funk. Netflix Update: Try This at Home (2006) — исходное описание Funk SVD.
Архив конкурса Netflix Prize
Rendle et al. Neural Collaborative Filtering vs. Matrix Factorization Revisited (2020) — скалярное произведение против обученных нейросетевых сходств.
Документация библиотеки Surprise
Библиотека implicit (ALS для неявной обратной связи)

Литература

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

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

Koren Y. Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model // Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). — 2008. — С. 426–434.

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.

Lee D. D., Seung H. S. Learning the parts of objects by non-negative matrix factorization // Nature. — 1999 T. 401. — С. 788–791.

Salakhutdinov R., Mnih A. Probabilistic Matrix Factorization // Advances in Neural Information Processing Systems (NeurIPS). — 2008 T. 20. — С. 1257–1264.

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

Srebro N., Rennie J., Jaakkola T. Maximum-Margin Matrix Factorization // Advances in Neural Information Processing Systems (NeurIPS). — 2004 T. 17. — С. 1329–1336.

Rendle S., Freudenthaler C., Gantner Z., Schmidt-Thieme L. BPR: Bayesian Personalized Ranking from Implicit Feedback // Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI). — 2009. — С. 452–461.

Hastie T., Mazumder R., Lee J., Zadeh R. Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares // Journal of Machine Learning Research. — 2015 T. 16. — С. 3367–3402.

Rendle S., Krichene W., Zhang L., Anderson J. Neural Collaborative Filtering vs. Matrix Factorization Revisited // Proceedings of the 14th ACM Conference on Recommender Systems (RecSys). — 2020. — С. 240–248.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=SVD_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%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»