Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''Claude Opus 4.8''' и проверена участником [[Участник:Nikita Saveliuk|Nikita Saveliuk]] 01:22, 5 июля 2026 (MSD)}} {{TOCright}} Приближение матрицы «пользователь–объект» произведением матриц низкого ранга — один из центральных подходов [[Коллаборативная фильтрация|коллаборативной фильтрации]], известный в рекомендательных системах под названием '''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), ставшей канонической ссылкой. == Постановка задачи == Пусть имеется <tex>m</tex> пользователей и <tex>n</tex> объектов. Известные оценки образуют разреженную матрицу <tex>R \in \mathbb{R}^{m \times n}</tex>, где элемент <tex>r_{ui}</tex> — оценка, поставленная пользователем <tex>u</tex> объекту <tex>i</tex>. Заданы лишь оценки из наблюдённого множества пар <tex>\mathcal{K}</tex>; подавляющее большинство элементов <tex>R</tex> отсутствует. Задача — предсказать неизвестные оценки <tex>r_{ui}</tex> для пар <tex>(u, i) \notin \mathcal{K}</tex> и на их основе ранжировать объекты для пользователя. Специфика задачи — именно в неполноте <tex>R</tex>. Классическое сингулярное разложение требует полностью заданной матрицы: сумма квадратов отклонений в теореме Эккарта–Янга берётся по всем элементам. Для разреженной <tex>R</tex> это выражение не определено. Заполнение пропусков возвращает задачу в область применимости SVD, но вносит систематическое смещение (заполняющее значение становится «целью» для ненаблюдённых пар) и уничтожает разреженность, делая разложение неподъёмным по памяти. Поэтому в рекомендательных системах оптимизируют иную, определённую только на наблюдённой части величину. == Метод == === Классический SVD и теорема Эккарта–Янга === Любая матрица <tex>R \in \mathbb{R}^{m \times n}</tex> раскладывается в произведение: ::<tex>R = U \Sigma V^{\top}</tex>, <br /> где <tex>U</tex> и <tex>V</tex> — ортогональные матрицы левых и правых сингулярных векторов, а <tex>\Sigma</tex> — диагональная матрица неотрицательных сингулярных чисел. Оставив <tex>k</tex> наибольших сингулярных чисел и соответствующие векторы, получаем усечённое разложение <tex>R_k = U_k \Sigma_k V_k^{\top}</tex> ранга <tex>k</tex>. По теореме Эккарта–Янга оно оптимально: ::<tex>\| R - R_k \|_F = \min_{\mathrm{rank}(B) \le k} \| R - B \|_F</tex>, <br /> то есть среди всех матриц ранга не выше <tex>k</tex> усечённый SVD ближе всего к <tex>R</tex> по норме Фробениуса. Именно этот результат делает SVD инструментом снижения размерности. Существенно, что оптимизируемая норма берётся по '''всем''' элементам матрицы — что и требует её полной заданности. === Матричная факторизация как «SVD» в рекомендациях === В рекомендательной постановке каждому пользователю сопоставляется вектор скрытых факторов <tex>p_u \in \mathbb{R}^{k}</tex>, каждому объекту — вектор <tex>q_i \in \mathbb{R}^{k}</tex>, а оценка приближается их скалярным произведением: ::<tex>\hat{r}_{ui} = p_u^{\top} q_i</tex>, <br /> Векторы факторов ищутся минимизацией регуляризованной квадратичной ошибки '''только по наблюдённым оценкам''': ::<tex>\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)</tex>, <br /> Здесь <tex>P</tex> и <tex>Q</tex> — матрицы факторов пользователей и объектов, <tex>\lambda</tex> — коэффициент <tex>L_2</tex>-регуляризации, сдерживающий переобучение на пользователях и объектах с малым числом оценок. Ключевое, но часто упускаемое обстоятельство: решение этой задачи в общем случае '''не совпадает''' с усечённым сингулярным разложением какой-либо матрицы. Во-первых, ортогональность <tex>U</tex> и <tex>V</tex> здесь не накладывается — <tex>p_u</tex> и <tex>q_i</tex> произвольны. Во-вторых, сумма берётся не по всей матрице, а лишь по <tex>\mathcal{K}</tex>, поэтому гарантия оптимальности Эккарта–Янга неприменима. В-третьих, в отличие от полного SVD, имеющего замкнутое решение, эта задача невыпукла по паре <tex>(P, Q)</tex> и решается итеративно, с риском попасть в локальный минимум. Классический SVD оказывается частным случаем: если бы <tex>R</tex> была полностью наблюдаема, а <tex>\lambda = 0</tex>, минимизация той же ошибки по всем элементам восстановила бы усечённое разложение с точностью до вращения факторов. Название «SVD» удержалось по историческим причинам (Funk, Netflix Prize), обозначая регуляризованную матричную факторизацию. === Обучение через стохастический градиентный спуск === Для каждой наблюдённой оценки вычисляется ошибка предсказания: ::<tex>e_{ui} = r_{ui} - \hat{r}_{ui}</tex>, <br /> Дифференцируя слагаемое целевой функции по <tex>p_u</tex> и <tex>q_i</tex>, получаем шаги стохастического градиентного спуска, обновляющие факторы навстречу антиградиенту: ::<tex>p_u \leftarrow p_u + \gamma\bigl( e_{ui}\, q_i - \lambda\, p_u \bigr)</tex>, <br /> ::<tex>q_i \leftarrow q_i + \gamma\bigl( e_{ui}\, p_u - \lambda\, q_i \bigr)</tex>, <br /> где <tex>\gamma</tex> — скорость обучения. Каждое обновление затрагивает только факторы, участвующие в данной оценке, поэтому одна эпоха стоит порядка <tex>|\mathcal{K}|</tex> операций и линейна по числу известных оценок — это и обеспечивает масштабируемость на разреженных данных. === Учёт смещений === Значительная доля дисперсии оценок объясняется не взаимодействием, а систематическими сдвигами: одни пользователи ставят в среднем выше, одни объекты популярнее. Их выносят в отдельные слагаемые: ::<tex>\hat{r}_{ui} = \mu + b_u + b_i + p_u^{\top} q_i</tex>, <br /> где <tex>\mu</tex> — глобальное среднее, <tex>b_u</tex> и <tex>b_i</tex> — смещения пользователя и объекта. Смещения обучаются теми же шагами SGD: ::<tex>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)</tex>, <br /> Учёт смещений заметно повышает точность и позволяет скалярному произведению <tex>p_u^{\top} q_i</tex> моделировать именно отклонение от базового уровня, а не общий сдвиг. === SVD++ и неявная обратная связь === Даже без явной оценки сам факт взаимодействия (просмотр, клик, покупка) несёт информацию о предпочтениях. Модель SVD++ добавляет к вектору пользователя вклад объектов, с которыми он взаимодействовал: ::<tex>\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)</tex>, <br /> где <tex>N(u)</tex> — множество объектов с неявной обратной связью пользователя <tex>u</tex>, <tex>y_j</tex> — обучаемые векторы этих объектов, а нормировка <tex>|N(u)|^{-\frac{1}{2}}</tex> уравнивает вклад пользователей с разной активностью. SVD++ был одним из сильнейших одиночных предикторов в решениях Netflix Prize. === ALS как альтернатива обучению === Целевая функция невыпукла по паре <tex>(P, Q)</tex>, но выпукла по каждой матрице при фиксированной другой. Это основа метода ''попеременных наименьших квадратов'' (ALS): при фиксированных факторах объектов оптимальные факторы каждого пользователя находятся в замкнутом виде как решение гребневой регрессии: ::<tex>p_u = \bigl( Q_{(u)}^{\top} Q_{(u)} + \lambda I \bigr)^{-1} Q_{(u)}^{\top} r_{(u)}</tex>, <br /> где <tex>Q_{(u)}</tex> — матрица факторов объектов, оценённых пользователем <tex>u</tex>, а <tex>r_{(u)}</tex> — вектор его оценок. Затем факторы объектов пересчитываются симметрично, и шаги чередуются. ALS легко распараллеливается по пользователям и объектам и особенно удобен для неявной обратной связи, где сумма идёт по всем парам с весами-уверенностями (Hu et al., 2008), что делает поэлементный SGD неэффективным. == Свойства == === Преимущества === * Стоимость эпохи SGD линейна по числу известных оценок, что обеспечивает масштабируемость на разреженных данных. * Модель естественно расширяется смещениями, неявной обратной связью и временными эффектами без смены каркаса. * Скрытые факторы дают компактное представление пользователей и объектов, пригодное и для других задач (поиск похожих, кластеризация). * ALS-вариант хорошо распараллеливается и подходит для неявной обратной связи с весами-уверенностями. === Ограничения === * Задача невыпукла: результат зависит от инициализации и гиперпараметров, возможны локальные минимумы. * Проблема холодного старта: для новых пользователей и объектов без оценок факторы не определены. * Скрытые факторы, в отличие от сингулярных векторов, не ортогональны и, как правило, не интерпретируются напрямую. * Базовая модель линейна по факторам и не улавливает сложные нелинейные взаимодействия, для которых применяют нейросетевые расширения. == Применение == SVD-факторизация применяется в рекомендациях фильмов, музыки, товаров и контента — всюду, где есть матрица взаимодействий «пользователь–объект». Она служит сильным базовым методом и компонентом ансамблей, а также источником эмбеддингов для последующих моделей ранжирования. Вариант для неявной обратной связи используется там, где явных оценок нет, а есть только события взаимодействия: просмотры, прослушивания, клики. == См. также == * [[Коллаборативная фильтрация]] * [[Рекомендательные системы]] * [[Сингулярное разложение]] * [[Матричная факторизация]] * [[Стохастический градиентный спуск]] == Ссылки == * [https://sifter.org/~simon/journal/20061211.html Simon Funk. Netflix Update: Try This at Home (блог, 2006)] * [https://developers.google.com/machine-learning/recommendation Google. Recommendation Systems (учебный курс)] == Литература == * {{статья |автор = Koren Y., Bell R., Volinsky C. |заглавие = Matrix Factorization Techniques for Recommender Systems |издание = Computer (IEEE) |год = 2009 |том = 42 |номер = 8 |страницы = 30–37 |ссылка = https://doi.org/10.1109/MC.2009.263 }} * {{статья |автор = 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 |ссылка = https://doi.org/10.1109/ICDM.2008.22 }} * {{статья |автор = Sarwar B., Karypis G., Konstan J., Riedl J. |заглавие = Application of Dimensionality Reduction in Recommender System — A Case Study |издание = WebKDD Workshop |год = 2000 |ссылка = http://files.grouplens.org/papers/webKDD00.pdf }} * {{статья |автор = Eckart C., Young G. |заглавие = The approximation of one matrix by another of lower rank |издание = Psychometrika |год = 1936 |том = 1 |номер = 3 |страницы = 211–218 |ссылка = https://doi.org/10.1007/BF02288367 }} * {{cite web |url = https://sifter.org/~simon/journal/20061211.html |title = Netflix Update: Try This at Home |author = Funk S. |date = 2006 |accessdate = 2026 }} [[Категория:Рекомендательные системы]] [[Категория:Машинное обучение]] [[Категория:Коллаборативная фильтрация]]

• Шаблон:Cite web
• Шаблон:Mbox
• Шаблон:TOCright
• Шаблон:Well
• Шаблон:Переводы
• Шаблон:Статья

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