RecSys Часть II · Кандидатогенерация · глава 6 из 19
Матричная факторизация, ALS и fold-in
Тот же коллаборативный сигнал, но обобщение устроено принципиально иначе: не через прямые совстречаемости, а через сжатие в несколько координат. Из-за этого факторизация видит связи там, где соседи видят пустоту — и ломается там, где соседи работают. Разбираем механизм с числами, выводим ALS, и отдельно — как выдать вектор пользователю, которого не было в обучении.
- Факторизация — метод внутри коллаборативной фильтрации, а не альтернатива ей. И «выученная» не значит «факторизованная»: EASE тоже обучается, но раскладывать ничего не пытается.
- Обобщение идёт через узкое горлышко. Айтемы, встретившиеся вместе 12 раз из 20 000, получают у соседей косинус 0.04, а у факторизации ранга 2 — 0.98.
- Ранг — это гипотеза «любой вкус есть смесь \(d\) архетипов». При \(d = 6\) на матрице 30×40 параметров становится больше, чем наблюдений.
- Для нового пользователя переобучение не нужно. Fold-in — решение одной системы \(d \times d\), то есть та же гребневая регрессия, что внутри ALS.
1. Где факторизация стоит среди остального
Термины путают постоянно, поэтому сразу расставим.
Матрицу взаимодействий \(R\) размера \(|U| \times |I|\) приближаем произведением двух тонких:
$$ R \;\approx\; P Q^{\top}, \qquad P \in \mathbb{R}^{|U| \times d},\ \ Q \in \mathbb{R}^{|I| \times d}, \qquad \hat r_{ui} = p_u^{\top} q_i $$Каждому пользователю и каждому айтему сопоставляется вектор из \(d\) чисел, а предсказание — их скалярное произведение. Обучаемся только по наблюдённым ячейкам:
$$ \min_{P,Q} \sum_{(u,i) \in \Omega} \bigl(r_{ui} - p_u^{\top}q_i\bigr)^2 \;+\; \lambda\bigl(\lVert P\rVert^2 + \lVert Q\rVert^2\bigr) $$Сумма по \(\Omega\), а не по всем парам, — принципиально: пропуск это неизвестность, а не ноль.
Настоящее сингулярное разложение требует полной матрицы. У нас дыры, и заполнить их нулями нельзя по причине из главы про данные.
То, что после Netflix Prize называют SVD, — это градиентный спуск Саймона Функа по наблюдённым ячейкам. Название прижилось, метод другой. На собеседовании уточнить эту разницу — дешёвый способ показать, что вы понимаете постановку, а не запомнили аббревиатуру.
2. Чем это отличается от соседей
Главное отличие не в формуле, а в том, откуда берётся обобщение.
Синтетика: два айтема A и C грузятся на один латентный вкус, но оба редкие, поэтому вместе почти не встречаются. B — частый айтем того же вкуса, E — айтем другого вкуса.
| sim(A, C) | sim(A, B) | sim(A, E) | |
|---|---|---|---|
| совстречаемость | A и C вместе — 12 раз из 20 000 | ||
| соседи, косинус | 0.0396 | 0.1256 | — |
| факторизация, ранг 2 | +0.980 | +0.889 | −0.622 |
Числа воспроизводятся скриптом _tools/mf_demo.py в этом репозитории.
Соседи считают A и C почти несвязанными и ставят B втрое ближе к A. Факторизация восстанавливает, что A и C — практически дубликаты по вкусу, имея на руках двенадцать совпадений.
Механизм: сжатие в две координаты не оставляет модели места хранить каждый айтем отдельно. Чтобы объяснить данные, ей приходится найти общие оси — и на этих осях A и C оказываются рядом, потому что связаны с одними и теми же третьими айтемами.
Возьмём айтемы-субституты: аудитории не пересекаются вовсе, ни одного совместного взаимодействия.
| соседи | sim(A,C) = 0.000 | «нет данных» |
| факторизация | sim(A,C) = −1.000 | «противоположны» |
Это разные утверждения, и второе соседи выразить не могут в принципе. Ноль у kNN означает отсутствие информации; минус единица у факторизации — содержательный вывод об отношении.
Отсюда и практическое разделение: соседи хороши там, где сигнала много и нужна объяснимость, факторизация — там, где надо дотянуться до связей, которых в прямых совпадениях нет.
3. Как это обучают
SGD: вывод в две строки
Для одного наблюдения ошибка \(e_{ui} = r_{ui} - p_u^{\top}q_i\), функция потерь \(L = e_{ui}^2 + \lambda(\lVert p_u\rVert^2 + \lVert q_i\rVert^2)\). Дифференцируем:
$$ \frac{\partial L}{\partial p_u} = -2e_{ui}q_i + 2\lambda p_u, \qquad \frac{\partial L}{\partial q_i} = -2e_{ui}p_u + 2\lambda q_i $$Шаг спуска (двойку прячем в \(\eta\)):
$$ p_u \leftarrow p_u + \eta\,(e_{ui}\,q_i - \lambda\,p_u), \qquad q_i \leftarrow q_i + \eta\,(e_{ui}\,p_u - \lambda\,q_i) $$Читается по-человечески: сдвинь вектор пользователя в сторону вектора айтема пропорционально ошибке, и симметрично.
ALS: почему его любят в проде
Задача не выпукла по \((P, Q)\) вместе, но выпукла по каждой матрице отдельно. Зафиксируем \(Q\) — тогда для пользователя \(u\) остаётся обычная гребневая регрессия. Приравняв производную нулю:
$$ \bigl(Q_u^{\top}Q_u + \lambda I\bigr)\,p_u = Q_u^{\top} r_u \quad\Longrightarrow\quad p_u = \bigl(Q_u^{\top}Q_u + \lambda I\bigr)^{-1} Q_u^{\top} r_u $$где \(Q_u\) — строки тех айтемов, с которыми \(u\) взаимодействовал. Затем симметрично фиксируем \(P\) и решаем для айтемов. Повторяем.
Три причины, по которым это удобно в проде:
- каждый \(p_u\) считается независимо от остальных — идеально параллелится по пользователям;
- нет learning rate, который надо подбирать;
- сходится за десяток итераций, а не за десятки эпох.
Обратите внимание на размер системы: \(d \times d\), где \(d\) — ранг, обычно десятки. Обращается матрица размера с ранг, а не с каталог.
Ранг — это гипотеза, а не гиперпараметр
Слово «ранг» здесь не метафора. У произведения двух матриц ширины \(d\) ранг не превышает \(d\) — факт линейной алгебры. Выбирая \(d\), мы буквально утверждаем: любой вкус есть смесь \(d\) архетипов.
При \(d = 2\) гипотеза жёсткая, при \(d = 50\) — почти ни к чему не обязывающая. И у неё есть измеримая цена.
Число обучаемых параметров равно \((|U| + |I|)\cdot d\). Для матрицы 30×40, заполненной на 45%, где треть отложена в проверку — около 378 обучающих наблюдений:
| Ранг \(d\) | Параметров | На одно наблюдение |
|---|---|---|
| 1 | 70 | 0.19 |
| 2 | 140 | 0.37 |
| 4 | 280 | 0.74 |
| 6 | 420 | 1.11 — больше, чем данных |
Числа воспроизводятся скриптом _tools/mf_demo.py.
При \(d = 6\) модель может подогнать обучающие данные почти точно, ничего при этом не выучив. Это и есть переобучение — и видно оно только на отложенной выборке, потому что обучающая ошибка при этом падает.
Две роли регуляризации
В функции потерь \(\lambda\) — штраф за длину векторов, в решении ALS он превращается в \(\lambda I\) на диагонали. Обычно называют только первую роль.
Пользователю с одной оценкой выгодно выдать огромный вектор, идеально в эту оценку попадающий. Штраф за длину делает это невыгодным, вектор остаётся коротким — а короткий вектор даёт предсказание, близкое к среднему.
То есть \(\lambda\) заставляет модель говорить «не знаю» там, где данных мало, вместо того чтобы уверенно выдумывать.
Вторая роль чисто вычислительная и о ней забывают. Матрица \(Q_u^{\top}Q_u\) для пользователя с двумя-тремя взаимодействиями вырождена: ранг меньше \(d\), обратной не существует.
Добавка \(\lambda I\) делает её обратимой всегда. Поэтому в ALS регуляризация не опция, а условие работоспособности: при \(\lambda = 0\) решение для редкого пользователя просто не считается.
- Двигайте ранг и смотрите на обе ошибки. Обучающая падает монотонно, отложенная имеет минимум — и он в районе истинного ранга данных.
- Увеличьте ранг за минимум: обучающая ошибка продолжает падать, отложенная растёт. Это ровно та арифметика «параметров больше, чем наблюдений» из таблицы выше.
- Поднимите \(\lambda\): минимум по рангу сдвигается вправо. Регуляризация позволяет держать больший ранг, не переобучаясь, — за счёт того, что каждая координата используется осторожнее.
Что сказать на собесе: «Ранг — это гипотеза о числе латентных факторов. Подбирается по отложенной выборке, а не по обучающей: обучающая ошибка монотонно падает и ничего не подсказывает».
4. iALS: что делать, когда негативов нет
Всё выше предполагало, что \(r_{ui}\) — оценка. В неявных данных оценки нет: мы видим «слушал», но не видим «не понравилось». А если учиться только по наблюдённым парам, то все они позитивны, и тривиальное решение — предсказывать единицу везде.
Решение Hu, Koren и Volinsky: учиться на всех парах, но с разным весом.
$$ \min_{P,Q}\; \sum_{u,i} c_{ui}\bigl(\mathbb{1}[r_{ui} > 0] - p_u^{\top}q_i\bigr)^2 \;+\; \lambda\bigl(\lVert P\rVert^2 + \lVert Q\rVert^2\bigr), \qquad c_{ui} = 1 + \alpha\, r_{ui} $$Разделены две вещи, которые в явном фидбеке слиты:
- целевая переменная — бинарное «есть предпочтение или нет»;
- вес \(c_{ui}\) — насколько мы в этом уверены: слушал сто раз или один.
Ненаблюдённые пары входят с весом 1 — это мягкие негативы: модель предполагает отсутствие интереса, но слабо, и одно наблюдение эту гипотезу перебивает.
Параметр \(\alpha\) — гиперпараметр, и он не единица: в исходной работе разумные значения порядка десятков. Он задаёт, во сколько раз наблюдение весомее пропуска.
Наивно сумма по \(|U|\times|I|\) неподъёмна. Но в решении ALS она раскладывается:
$$ Q^{\top}C_u Q \;=\; Q^{\top}Q \;+\; Q^{\top}(C_u - I)Q $$Первое слагаемое не зависит от пользователя и считается один раз на итерацию. Второе — сумма только по тем айтемам, где \(c_{ui} \ne 1\), то есть по наблюдённым, которых мало.
Именно этот трюк и сделал iALS практичным. Без него «учиться на всех парах» осталось бы теоретическим предложением.
5. Новый пользователь: fold-in
Пользователь пришёл, что-то посмотрел, а модель обучалась вчера. Переобучать ради него весь ALS — не вариант. И не нужно.
Векторы айтемов \(Q\) уже обучены и меняются медленно. Значит, для нового пользователя достаточно решить ровно тот шаг ALS, который отвечает за пользователей:
$$ p_{\text{new}} = \bigl(Q_s^{\top}Q_s + \lambda I\bigr)^{-1} Q_s^{\top} r_s $$где \(Q_s\) — векторы айтемов, с которыми человек уже взаимодействовал. Это система \(d \times d\): при ранге 8 — восемь на восемь, микросекунды.
Проверка на синтетике: каталог 300, ранг 8, у нового пользователя 25 взаимодействий, его векторов не было в обучении вообще.
Топ-25 предсказания совпадает с его настоящими интересами в 17 случаях из 25 — при том что модель увидела его первый раз и решила одну систему 8×8.
Числа воспроизводятся скриптом _tools/mf_demo.py.
Отсюда практический вывод: холодный старт по пользователям решается дёшево, если есть хоть немного истории. Холодный старт по айтемам — нет: у нового айтема нет вектора \(q_i\), а без него он не участвует ни в одном скоре.
6. Где факторизация упирается
| Ограничение | В чём состоит |
|---|---|
| Холодный старт по айтемам | нового айтема нет в \(Q\); контентные признаки модель не принимает по построению |
| Нет контекста | ни времени суток, ни устройства, ни того, что человек делает прямо сейчас |
| Порядок истории игнорируется | \(p_u\) выучивается по множеству взаимодействий; «вчера» и «два года назад» неразличимы |
| Только одна форма взаимодействия | скалярное произведение. Всё, что не выражается им, модель выразить не может |
| Popularity bias в геометрии | норма \(\lVert q_i\rVert\) растёт с популярностью, а MIPS её не сокращает — см. главу про смещения |
Первые три ограничения снимаются одним и тем же ходом: заменить обучаемый вектор айтема на вычисляемый из признаков. Это следующая большая линия учебника — от матричной факторизации к двухбашенным моделям.
Вопросы с собеседований
Чем матричная факторизация отличается от коллаборативной фильтрации?
Это не альтернативы: факторизация — метод внутри коллаборативной фильтрации. CF делится на подходы по соседям (kNN, item-item — считаем похожести прямо по матрице) и обучаемые, куда входит факторизация, а также EASE и SLIM. Причём «обучаемая» и «факторизованная» — разные свойства: EASE обучается, но матрицу не раскладывает.
Содержательное отличие в механизме обобщения. Соседи обобщают через прямые совстречаемости, факторизация — через сжатие в \(d\) координат. Поэтому она находит связи там, где совпадений почти нет: в примере айтемы, встретившиеся вместе 12 раз из 20 000, получают у соседей косинус 0.04, а у факторизации ранга 2 — 0.98.
И обратное: у взаимоисключающих айтемов соседи дают 0 («нет данных»), факторизация −1 («противоположны»). Второе утверждение соседям недоступно.
Почему «SVD» в рекомендациях — не SVD?
Настоящее сингулярное разложение требует полной матрицы. У нас матрица разреженная, и заполнять пропуски нулями нельзя: пропуск означает «не показывали», а не «не понравилось».
То, что стали называть SVD после Netflix Prize, — градиентный спуск Саймона Функа по наблюдённым ячейкам, то есть минимизация ошибки только на известных парах с регуляризацией. Название прижилось, метод другой.
Почему ALS предпочитают SGD в продакшене?
Задача не выпукла по \((P,Q)\) вместе, но выпукла по каждой матрице отдельно. Зафиксировав \(Q\), для каждого пользователя получаем обычную гребневую регрессию с решением \(p_u = (Q_u^\top Q_u + \lambda I)^{-1} Q_u^\top r_u\).
Отсюда три преимущества: каждый \(p_u\) считается независимо и задача идеально параллелится; нет learning rate, который надо подбирать; сходимость за десяток итераций. Система при этом размера \(d \times d\) — с ранг, а не с каталог.
SGD выигрывает, когда матрица очень разреженная и нужна онлайн-донастройка, а также когда лосс не квадратичный — для BPR или логистического ALS не выведешь.
Что такое ранг и как его выбирать?
Ранг — число координат у каждого вектора, и это содержательная гипотеза: «любой вкус есть смесь \(d\) архетипов». У произведения матриц ширины \(d\) ранг не превышает \(d\), поэтому выбор \(d\) ограничивает то, что модель вообще способна выразить.
Цена измерима: параметров \((|U| + |I|)\cdot d\). На матрице 30×40 с 378 обучающими наблюдениями ранг 6 даёт 420 параметров — больше, чем данных, и модель подгонит обучающую выборку, ничего не выучив.
Подбирается по отложенной выборке. Обучающая ошибка монотонно падает с ростом ранга и не подсказывает ничего; минимум есть только у отложенной.
Зачем нужна регуляризация в ALS — назовите обе роли.
Первая, обычная: сжатие к нулю. Пользователю с одной оценкой выгодно выдать огромный вектор, идеально в неё попадающий; штраф за длину делает это невыгодным, и модель говорит «не знаю» вместо того, чтобы уверенно выдумывать.
Вторая, о которой забывают: обусловленность. Матрица \(Q_u^\top Q_u\) для пользователя с двумя-тремя взаимодействиями вырождена — её ранг меньше \(d\), обратной не существует. Добавка \(\lambda I\) делает её обратимой всегда, поэтому при \(\lambda = 0\) решение для редкого пользователя просто не посчитается.
Как iALS работает с неявным фидбеком?
Разделяет цель и уверенность. Целевая переменная бинарная — «есть предпочтение», а вес \(c_{ui} = 1 + \alpha r_{ui}\) показывает, насколько мы в этом уверены: слушал сто раз или один. Учимся на всех парах, а не только на наблюдённых, и ненаблюдённые входят с весом 1 — это мягкие негативы, которые одно наблюдение перебивает.
Сумма по всем парам не взрывается из-за разложения \(Q^\top C_u Q = Q^\top Q + Q^\top(C_u - I)Q\): первое слагаемое не зависит от пользователя и считается раз на итерацию, второе — сумма только по наблюдённым, которых мало.
И \(\alpha\) — настоящий гиперпараметр, не единица: разумные значения порядка десятков.
Как выдать рекомендации пользователю, которого не было в обучении?
Fold-in. Векторы айтемов уже обучены и меняются медленно, поэтому достаточно решить ровно тот шаг ALS, который отвечает за пользователей: \(p_{\text{new}} = (Q_s^\top Q_s + \lambda I)^{-1} Q_s^\top r_s\), где \(Q_s\) — векторы того, с чем человек взаимодействовал.
Это система \(d \times d\) — при ранге 8 микросекунды, никакого переобучения. На синтетике с каталогом 300 и 25 взаимодействиями топ-25 совпадает с настоящими интересами в 17 случаях из 25.
Важно, что обратное не работает: холодный старт по айтемам так не лечится. У нового айтема нет вектора, и взять его неоткуда — нужны контентные признаки, то есть другая архитектура.
Шпаргалка одним экраном
Место
MF — метод внутри CF. «Обучаемая» ≠ «факторизованная»: EASE учится, но не раскладывает.
Обобщение
Через узкое горлышко, а не через совпадения. 12 совстречаемостей из 20 000 → косинус 0.04 у соседей, 0.98 у MF.
ALS
\(p_u = (Q_u^\top Q_u + \lambda I)^{-1} Q_u^\top r_u\). Параллелится, без learning rate, десяток итераций.
Ранг
Гипотеза о числе архетипов. Параметров \((|U|+|I|)d\); подбирается по отложенной.
iALS
Цель бинарная, вес \(c = 1 + \alpha r\). Пропуски — мягкие негативы. \(\alpha\) порядка десятков.
Fold-in
Система \(d\times d\), переобучение не нужно. Работает для пользователей, не работает для айтемов.
Первоисточники
- Y. Koren, R. Bell, C. Volinsky. Matrix Factorization Techniques for Recommender Systems, IEEE Computer 2009 — каноническая сводка после Netflix Prize.
- Y. Hu, Y. Koren, C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets, ICDM 2008 — iALS, уверенность вместо оценки и разложение, делающее задачу подъёмной.
- S. Rendle, C. Freudenthaler et al. BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI 2009 — попарная альтернатива квадратичному лоссу.
- S. Rendle, W. Krichene et al. Neural Collaborative Filtering vs. Matrix Factorization Revisited, RecSys 2020 — почему скалярное произведение до сих пор трудно побить.
- Числа главы:
_tools/mf_demo.pyв этом репозитории.