Matrix Factorization

2009 год. Netflix Prize. Команда BellKor's Pragmatic Chaos берёт главный приз - 1 миллион долларов. Их решение: ансамбль из сотен моделей, ядро которого - SVD. Матрица оценок Netflix в 500 миллионов пользователей x 15 000 фильмов заполнена менее чем на 1%. Это 7.5 триллиона пустых ячеек. Matrix factorization заполняет их, «угадывая» скрытые предпочтения, которых нет в данных. Сто чисел на пользователя вместо терабайтов пустоты.

• **Netflix Prize** (2009) - победивший ансамбль использовал SVD и его вариации как основу, комбинируя latent factor модели с neighborhood подходами
• **Spotify Discover Weekly** использует matrix factorization на матрице «пользователь x трек» из миллиардов прослушиваний (implicit feedback) для генерации персонализированных плейлистов
• **Apache Spark MLlib** реализует ALS как основной production-ready алгоритм рекомендаций, обрабатывая петабайты данных в распределённых кластерах

Предварительные знания

• Collaborative Filtering

Netflix Prize и рождение modern recommender systems

2006 год. Netflix объявляет конкурс с призом 1 миллион долларов: улучшить Cinematch (их рекомендательный алгоритм) на 10% по RMSE. Три года борьбы - участвовало более 2000 команд из 186 стран. Победитель BellKor's Pragmatic Chaos достиг 10.06% улучшения за несколько часов до финального дедлайна. Их подход объединил SVD++, temporal dynamics и neighbourhood models. Ирония: Netflix так и не запустил победный алгоритм в продакшн - к тому времени бизнес сместился на streaming, где implicit feedback (время просмотра) важнее explicit оценок.

SVD: скрытые факторы предпочтений

Почему одним людям нравится «Inception», «Interstellar» и «Matrix»? Потому что за этими фильмами стоит **скрытый фактор** - назовём его «mind-bending sci-fi». Этот фактор нигде не записан в базе данных, но он существует в паттернах оценок. **Matrix Factorization** извлекает такие скрытые факторы автоматически, раскладывая матрицу оценок на произведение двух меньших матриц.

**SVD (Singular Value Decomposition)** разлагает матрицу оценок **R** (m пользователей x n товаров) на три матрицы: **R ≈ U · Σ · V^T** - **U** (m x k) - матрица пользователей: каждая строка - вектор скрытых предпочтений пользователя - **Σ** (k x k) - диагональная матрица значимости каждого фактора - **V^T** (k x n) - матрица товаров: каждый столбец - вектор скрытых характеристик товара **k** - число скрытых факторов (обычно 20-200). Это «сжатое» представление: вместо хранения всех оценок, храним k чисел на пользователя и k на товар.

**Latent factors не имеют названий.** SVD находит математические оси, максимизирующие объяснённую дисперсию. Интерпретация «sci-fi» или «romance» - постфактум, по корреляциям. Иногда фактор не поддаётся интерпретации - это комбинация нескольких аспектов. Модели не нужно «понимать» факторы, чтобы делать точные предсказания.

**Классический SVD не работает с пропусками.** `numpy.linalg.svd` требует полную матрицу - без нулей/NaN. В реальной матрице оценок 97-99% ячеек пусты. Нельзя просто заменить пропуски нулями - это исказит разложение (ноль != «не оценено»). Решения: 1. заполнить средними оценками 2. использовать ALS или SGD-оптимизацию, которые работают только с известными ячейками.

**Выбор k (число факторов)** - компромисс между точностью и обобщением. k=2 - слишком грубо, k=1000 - переобучение. На MovieLens-10M оптимум обычно k=50-200. Практический подход: посмотреть на спад сингулярных значений (scree plot) и выбрать «локоть» - точку, после которой значения падают медленно.

ALS: итеративная оптимизация для разреженных матриц

Классический SVD требует полную матрицу. Но в Netflix 99% ячеек пусты. Как быть? **ALS (Alternating Least Squares)** решает эту проблему лаконично: вместо разложения полной матрицы, он **оптимизирует** только по **известным оценкам**. Это как собирать пазл, видя только 1% кусочков - но алгоритм восстанавливает целую картину.

Идея ALS: ищем матрицы **P** (users x k) и **Q** (items x k), такие что **R ≈ P · Q^T**. Минимизируем ошибку только на известных оценках: **min Σ(u,i)∈known (r_ui - p_u · q_i^T)² + λ(||P||² + ||Q||²)** Слагаемое **λ(||P||² + ||Q||²)** - это **регуляризация**, предотвращающая переобучение. Без неё модель «запомнит» тренировочные оценки, но будет плохо предсказывать новые.

**ALS масштабируется параллельно.** При фиксированном Q обновление каждого p_u **независимо** от остальных пользователей. Это значит, что шаг 1 легко параллелизируется по пользователям, шаг 2 - по товарам. Поэтому **Apache Spark MLlib** выбрал ALS как основной алгоритм рекомендаций - он идеально ложится на MapReduce.

**SGD vs ALS:** альтернатива ALS - **Stochastic Gradient Descent (SGD)**. SGD обрабатывает одну оценку за раз (быстрые обновления), ALS - целую строку/столбец (более стабильные шаги). SGD быстрее на плотных данных, ALS - лучше параллелизируется и работает с implicit feedback. Netflix Prize победитель использовал SGD, Spark MLlib - ALS.

NMF: интерпретируемые неотрицательные факторы

SVD и ALS дают факторы с **отрицательными** значениями. Что значит «пользователь имеет -0.5 по фактору 3»? Сложно интерпретировать. **NMF (Non-negative Matrix Factorization)** добавляет одно ограничение: **все значения в P и Q неотрицательны**. Это радикально меняет интерпретацию - факторы становятся **аддитивными частями**.

Интуиция: оценка фильма складывается из «сколько в нём sci-fi» + «сколько drama» + «сколько comedy». Каждый компонент >= 0 - фильм не может иметь «минус comedy». NMF находит именно такое разложение: **R ≈ W · H**, где все элементы W и H >= 0. - **W** (users x k) - сколько каждый пользователь «интересуется» каждым фактором - **H** (k x items) - сколько каждый товар «содержит» каждого фактора

**NMF и тематическое моделирование (topic modeling).** NMF применяется не только для рекомендаций. Если R - матрица TF-IDF (документы x слова), NMF находит «темы»: фактор = набор слов с весами. Тема 1: {machine: 0.8, learning: 0.7, neural: 0.6}. Тема 2: {market: 0.9, stock: 0.7, price: 0.6}. Неотрицательность критична - слово не может «отрицательно» относиться к теме.

**NMF не работает с отрицательными данными.** Если нормализовать оценки (вычесть среднюю), значения станут отрицательными - NMF выдаст ошибку или бессмысленный результат. Для NMF используйте сырые оценки (1-5 звёзд) или нормализуйте в диапазон [0, 1]. Это ограничение - плата за интерпретируемость.

**Когда выбрать NMF вместо SVD?** Если нужно **объяснить** рекомендацию: «Рекомендуем этот фильм, потому что пользователь любит sci-fi (фактор 1) и фильмы с неожиданной развязкой (фактор 3)». SVD не даёт такой интерпретации - его факторы смешивают позитивные и негативные компоненты.

Implicit Feedback: клики вместо звёзд

Netflix просит поставить оценку 1-5 звёзд. Но 99% взаимодействий пользователей - **без оценок**: клики, просмотры, время на странице, покупки, добавление в корзину, пропуск трека. Это **implicit feedback** - система наблюдает за действиями пользователя, а не спрашивает его мнение. И данных здесь на порядки больше.

Ключевое отличие от explicit ratings: - **Нет негативных сигналов.** Пользователь не кликнул на товар - это не значит, что товар ему не нравится. Возможно, он его не заметил. - **Разная сила сигнала.** Кликнул - слабый сигнал. Купил - сильный. Посмотрел 95% фильма - очень сильный. Пропустил через 2 минуты - негативный. - **Шум.** Клик на рекламу, случайный тап на мобильном, покупка подарка для другого человека - всё это шум в implicit feedback.

В 2008 году Hu, Koren и Volinsky (из Yahoo! и AT&T Labs) опубликовали ключевую статью **«Collaborative Filtering for Implicit Feedback Datasets»**. Их идея: ввести **confidence (уверенность)**. Чем больше взаимодействий - тем выше уверенность, что пользователю нравится товар. Формула: **c_ui = 1 + α × r_ui**, где r_ui - число взаимодействий.

**Confidence weighting - суть implicit подхода.** Один клик → c = 1 + 40×1 = 41. Тридцать прослушиваний → c = 1 + 40×30 = 1201. Модель «уверена» в предпочтении пропорционально количеству взаимодействий. Но даже нулевые ячейки имеют c = 1 - модель слабо, но считает их негативными предпочтениями. Это решает проблему «отсутствие клика != не нравится».

**Exposure bias - главная ловушка implicit feedback.** Пользователь кликает только на то, что ему **показали**. Если система никогда не показала товар - кликов нет, и модель считает, что товар не интересен. Это замкнутый цикл: непоказанные товары не получают кликов → ранжируются ниже → показываются ещё реже. Решение: exploration (случайные рекомендации) и causal inference методы.

**На практике: комбинируйте типы implicit сигналов.** Spotify использует «иерархию действий»: skip после 5 сек = сильный негатив, прослушал 70%+ = позитив, добавил в плейлист = сильный позитив, сохранил в библиотеку = очень сильный позитив. Каждое действие имеет свой вес при расчёте confidence. Это значительно богаче, чем одиночные клики.

Ключевые идеи

• **SVD** разлагает R ≈ U·Σ·V^T, извлекая скрытые факторы - 50-200 чисел, кодирующих вкус пользователя и суть товара. 7.5 триллиона пустых ячеек сжимаются до нескольких мегабайт
• **ALS** решает проблему разреженности: оптимизирует только по известным оценкам, чередуя обновление P и Q. Каждый шаг - линейная регрессия, легко параллелизируется (Spark MLlib)
• **NMF** жертвует точностью ради интерпретируемости: неотрицательные факторы = аддитивные «части» (жанры, темы). Можно объяснить рекомендацию пользователю
• **Implicit feedback** (Hu et al. 2008) - confidence-weighted ALS для кликов, просмотров, покупок. Масштабируется лучше explicit ratings, и именно на нём работают YouTube, Spotify, TikTok

Связанные темы

Matrix factorization - мост между классическим CF и современным deep learning для рекомендаций:

• Collaborative Filtering — Matrix factorization - продвинутая альтернатива neighborhood CF, решающая проблему разреженности
• PCA (Principal Component Analysis) — SVD - математическая основа PCA. Те же скрытые факторы, но применённые к dimensionality reduction

Вопросы для размышления

• SVD извлекает k скрытых факторов. Как определить оптимальное k? Какие метрики использовать: RMSE на валидации, scree plot, или бизнес-метрики (CTR, конверсия)?
• Implicit feedback не содержит явных негативных сигналов - пользователь не сказал «мне не нравится». Как отличить «не видел товар» от «видел, но не заинтересовался»? Какие дополнительные данные помогут?
• NMF даёт интерпретируемые факторы, но менее точен, чем SVD. В каких продуктах интерпретируемость рекомендаций критична (например, медицина, финансы), а в каких - нет (развлечения)?

Связанные уроки

• rec-02 — Collaborative filtering - фундамент перед matrix factorization
• ml-19-pca — SVD - математическая основа PCA, те же скрытые факторы
• rec-04 — Deep learning рекомендации строятся поверх идей MF
• aie-09-embeddings — Embeddings в LLM и user/item vectors - одна математика
• opt-01 — Методы оптимизации: ALS и SGD - частные случаи общих схем
• ml-01 — Основы ML: overfitting, regularization нужны для понимания ALS
• la-15-svd