Урок 39. PCA, эмбеддинги и рекомендации

В прошлом уроке PCA раскладывала данные по немногим осям. Тот же приём низкого ранга работает и там, где таблица почти пустая: в рекомендациях. Мы дадим каждому пользователю и каждому фильму короткий вектор так, чтобы скалярное произведение предсказывало оценку, а близость векторов рисовала карту вкусов. Все числа ниже посчитаны на настоящих оценках MovieLens.

Почти пустая матрица

Пусть $r_{ui}$ — оценка, которую пользователь $u$ поставил фильму $i$ . В таблице «пользователи × фильмы» заполнена лишь малая часть клеток: в наборе MovieLens 100K это $100\,000$ оценок при $943$ пользователях и $1682$ фильмах — меньше одной клетки из ста. Пустую клетку нельзя заменить нулём: пропуск означает «не смотрел», а не «не понравилось».

Поэтому модель учат только на наблюдаемых парах $\Omega$ . Матричная факторизация приближает оценку так:

\hat r_{ui}=\mu+a_u+b_i+p_u^\top q_i,

где $\mu$ — общая средняя оценка, $a_u$ — щедрость пользователя, $b_i$ — репутация фильма, а $p_u,q_i\in\mathbb R^d$ — короткие латентные векторы.

УпражнениеОдин прогноз

Пусть $\mu=3$ , $a_u=0{,}2$ , $b_i=-0{,}1$ , вектор пользователя $p_u=(1,2)$ , вектор фильма $q_i=(0{,}5,-1)$ . Чему равен прогноз оценки? Как он изменится, если оба вектора удвоить?

Показать ответ

$\hat r_{ui}=\mu+a_u+b_i+p_u^\top q_i=3+0{,}2-0{,}1+(1\cdot0{,}5+2\cdot(-1))=3{,}1-1{,}5=1{,}6$ . При удвоении обоих векторов скалярное произведение вырастет вчетверо: $(2p_u)^\top(2q_i)=4\,p_u^\top q_i=-6$ , и прогноз станет $3{,}1-6=-2{,}9$ — вне шкалы оценок. Поэтому на длину векторов и накладывают штраф-регуляризацию.

Сначала смещения, потом факторы

Прежде чем гнаться за латентными векторами, стоит выжать простое. Уже одни смещения $\hat r_{ui}=\mu+a_u+b_i$ учитывают, что один зритель ставит всем на балл выше, а иной фильм всем нравится сильнее среднего. Это сильный базовый уровень.

Каскадная диаграмма реального прогноза MovieLens: общая средняя 3,53, плюс вкус пользователя 0,13, плюс репутация фильма 0,38, плюс совпадение вкусов 0,68, итог 4,72 при истинной оценке 5 — Рис. 39.1. Из чего складывается прогноз оценки
Реальный прогноз, разложенный на вклады: общая средняя, щедрость пользователя, репутация фильма и, наконец, совпадение вкусов $p_u^\top q_i$ . Латентные векторы берут на себя только то, что не объяснили смещения.

ДанныеРепутация фильма

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

Параметры подбирают методом наименьших квадратов только по известным клеткам, со штрафом за большие векторы:

\min_{p,q,a,b}\sum_{(u,i)\in\Omega}\bigl(r_{ui}-\mu-a_u-b_i-p_u^\top q_i\bigr)^2 +\lambda\Bigl(\sum_u\lVert p_u\rVert^2+\sum_i\lVert q_i\rVert^2\Bigr).

УпражнениеПочему не ноль

В таблице оценок $99\%$ клеток пусты. Почему нельзя просто записать в них ноль и обучить модель на всей матрице сразу, как делает обычный PCA?

Показать ответ

Ноль — это конкретная низкая оценка, а пропуск означает «не смотрел». Заполнив пропуски нулями, мы заставили бы модель предсказывать, что все неоценённые фильмы пользователю не нравятся, — прямая ложь про $99\%$ данных. Поэтому сумма ошибок берётся только по наблюдаемым парам $\Omega$ ; в этом ключевое отличие от плотного PCA, который работает по всем клеткам.

Карта вкусов

Латентные векторы фильмов можно нарисовать. Обучим модель с двумя факторами на настоящих оценках и разложим фильмы на плоскости.

Двумерная карта векторов фильмов MovieLens. Star Wars рядом с научной фантастикой, Крёстный отец и Криминальное чтиво в одном углу, семейные фильмы в другом; подпись, что оси не имеют закреплённого смысла — Рис. 39.2. Карта вкусов из настоящих оценок
Двумерные векторы фильмов, обученные только по оценкам. «Звёздные войны» садятся рядом с фантастикой, «Крёстный отец» и «Криминальное чтиво» — в своём углу. Никто не задавал жанров: близость возникла из того, кто как оценивал.

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

Потрогай карту

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

Оси карты можно повернуть

У красивой карты есть подвох: отдельная ось не имеет закреплённого смысла. Для любой ортогональной матрицы $R$ (поворота) скалярные произведения сохраняются:

(Rp_u)^\top(Rq_i)=p_u^\top R^\top R\,q_i=p_u^\top q_i.

Значит, всю карту можно повернуть — прогнозы не изменятся ни на йоту. Поэтому нельзя объявить «первая координата — это комедийность»: смысл проверяют соседями и корреляцией с известными атрибутами, а не подписью к одной оси.

ИнвариантПоверни — прогноз тот же

Общий поворот всех векторов не меняет ни расстояний, ни скалярных произведений, ни прогнозов. Оси карты не единственны — инвариантна только геометрия близости.

Это та же неоднозначность, что у скрытого кода автокодировщика: смысл несёт геометрия представления, а не номер координаты.

УпражнениеЧто переживает поворот

После общего поворота всех векторов ортогональной матрицей прогнозы не изменились. Что ещё осталось прежним — расстояния между фильмами, знак отдельной координаты, порядок рекомендаций? Что не сохраняется?

Показать ответ

Сохраняется всё, что зависит только от скалярных произведений: попарные расстояния $\lVert q_i-q_j\rVert$ , углы, ближайшие соседи и, значит, весь порядок рекомендаций. Не сохраняется смысл отдельной оси: знак и величина конкретной координаты $q_{i1}$ меняются при повороте, поэтому «первая координата — это комедийность» не может быть объективной характеристикой.

::::

Сколько факторов брать

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

Три кривые RMSE на тесте против числа факторов: все оценки падают с 0,94 при одних смещениях до 0,91; популярные фильмы (head) предсказываются точнее, редкие (tail) держатся около 1,05 — Рис. 39.3. Ошибка против числа факторов
Ошибка на тесте падает с $0{,}94$ (одни смещения) до примерно $0{,}91$ и выходит на полку. Популярные фильмы всегда предсказываются точнее редких: у них больше оценок, и вектор устойчивее.

Обратите внимание: одни смещения уже дают $0{,}94$ , а факторы улучшают лишь до $0{,}91$ . Сложность обязана зарабатывать право на ответ — если персональный вектор не бьёт базовый уровень, он не нужен.

УпражнениеПочему хвост труднее

На карте RMSE редких фильмов (tail) держится около $1{,}05$ , а популярных (head) — около $0{,}90$ , при любом числе факторов. Почему у редких фильмов вектор предсказывает хуже, и помогает ли тут увеличение $d$ ?

Показать ответ

Вектор фильма оценивается по его оценкам: у популярного их тысячи, у редкого — единицы, поэтому его $q_i$ почти шум и легко переобучается. Увеличение $d$ не спасает, а вредит: больше параметров на тот же скудный сигнал усиливают переобучение (кривая tail даже слегка растёт). Помогают регуляризация, опора на смещение $b_i$ и контентные признаки — но не рост $d$ .

Холодный старт

У совсем нового пользователя оценок нет — вектор $p_u$ не из чего оценить. Помогают несколько стартовых вопросов, популярный список и контекст. Новый фильм страдает так же: его начальный вектор берут из жанров, описания и обложки, а потом уточняют по просмотрам.

РежимНачать без оценок

Холодный старт — отдельный режим. Пока у пользователя нет истории, первый вектор вкуса собирают из популярного, жанровых подсказок и пары вопросов, а не из факторизации.

Холодный старт не смешивают с обычным тестом: пользователей и фильмы, полностью отсутствовавшие в обучении, честно выделяют и сообщают охват (coverage), а не выкидывают перед подсчётом метрики.

Что рекомендация измеряет на самом деле

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

Разбиение на обучение и тест здесь тоже тонкое: для явных оценок историю делят по времени (ранние в обучение, поздние в тест), иначе будущий вкус помогает предсказать прошлый — прямая утечка данных. А кроме точности измеряют разнообразие и охват: список из десяти почти одинаковых продолжений может иметь высокую метрику и быть бесполезным.

Русская линия ведёт к Л. В. Канторовичу — математику и экономисту, нобелевскому лауреату, создателю линейного программирования и теории оптимального распределения ресурсов. Рекомендация по духу и есть оптимальное распределение внимания, а низкий ранг — наилучшее простое приближение сложной таблицы, ровно в канторовичевом смысле.

Коротко о рекомендациях

Рекомендательная система раскладывает почти пустую таблицу оценок на короткие векторы: скалярное произведение предсказывает оценку, а близость векторов рисует карту вкусов. Смещения снимают простые эффекты, латентные факторы ловят взаимодействия, а их число подбирают по отложенной ошибке. Оси карты можно повернуть, поэтому смысл несёт геометрия, а не координата. И под всеми красивыми картами лежит трезвость: метрика смещена выбором показа, редкие объекты предсказываются хуже, а холодный старт требует отдельного режима. Дальше — эмбеддинги содержания, где близость строится не из оценок, а из самого объекта.

Задачи

4баллов

Матрица оценок пользователей $U1,U2,U3$ фильмам $I1,\ldots,I4$ равна $R=\left(\begin{smallmatrix}5&4&?&1\\4&?&2&1\\?&5&3&?\end{smallmatrix}\right)$ ; восемь чисел наблюдаются, четыре знака ? пропущены. Найдите среднее $\mu$ по наблюдаемым оценкам. При $\lambda=2$ выполните ровно один упорядоченный проход: сначала для каждого пользователя $a_u=\sum_{i\in I_u}(r_{ui}-\mu)/(\lambda+|I_u|)$ , затем для каждого фильма $b_i=\sum_{u\in U_i}(r_{ui}-\mu-a_u)/(\lambda+|U_i|)$ , используя уже найденные $a_u$ . Заполните четыре пропуска формулой $\hat r_{ui}=\mu+a_u+b_i$ без обрезки, выпишите порядок вычислений и проверьте все промежуточные числители.

5баллов

Прогноз определён явно: $\hat r_{ui}=\mu+a_u+b_i+\sum_{\ell=1}^{2}p_{u\ell}q_{i\ell}$ . При $p_u=(1,2)$ , $q_i=(0{,}5,-1)$ , $\mu=3$ , $a_u=0{,}2$ , $b_i=-0{,}1$ вычислите каждое слагаемое и $\hat r_{ui}$ . Затем поверните оба вектора матрицей $R=\left(\begin{smallmatrix}0&-1\\1&0\end{smallmatrix}\right)$ , пересчитайте прогноз и докажите для любой ортогональной $R$ ( $R^\top R=I$ ), что $(Rp_u)^\top(Rq_i)=p_u^\top q_i$ . Объясните, почему смещения и среднее при повороте не меняются.

5баллов

Почему в модели $\hat r_{ui}=\mu+a_u+b_i+p_u^\top q_i$ смещения обучают до и вместе с факторами? Рассмотрите пользователя, ставящего всем на балл выше среднего, и фильм, который всем нравится на полбалла сильнее. Покажите, что без членов $a_u,b_i$ скалярное произведение $p_u^\top q_i$ вынуждено кодировать эти два простых сдвига направлениями латентного пространства, и объясните, чем это вредит интерпретации и обобщению.

6баллов

Используйте GroupLens MovieLens 100K, файл u.data (100 000 строк user_id,item_id,rating,timestamp). Для временного разбиения отсортируйте строки по $(\texttt{timestamp},\texttt{user\_id},\texttt{item\_id})$ и возьмите первые $80\,000$ в train, следующие $10\,000$ в validation, последние $10\,000$ в test. Сравните с перестановочным разбиением тех же размеров через default_rng(17).permutation. В каждом протоколе обучите baseline $\hat r_{ui}=\mu+a_u+b_i$ поочерёдным пересчётом: $\mu$ — train-среднее, все $a_u,b_i$ стартуют нулём, ровно $20$ циклов $a_u=\sum_{i\in I_u}(r_{ui}-\mu-b_i)/(\lambda+|I_u|)$ (с $b$ прошлого цикла), затем $b_i=\sum_{u\in U_i}(r_{ui}-\mu-a_u)/(\lambda+|U_i|)$ . Неизвестному user/item ставьте смещение $0$ . Выберите $\lambda\in\{0,1,5,10,20\}$ по validation-RMSE. На test сообщите RMSE всех строк и только «известных», долю новых пользователей и фильмов, охват и сравните временное разбиение с перестановочным.

6баллов

На том же u.data для каждого пользователя отсортируйте оценки по $(\texttt{timestamp},\texttt{item\_id})$ : первые $\lfloor0{,}8n_u\rfloor$ в train, остальные в test. Для $d\in\{2,8,32\}$ и seed $17,23,41$ обучите $\hat r_{ui}=\mu+a_u+b_i+p_u^\top q_i$ методом ALS: чередуйте пересчёт смещений и гребневые решения для $p_u$ и $q_i$ при $\lambda=15$ , $14$ сверток. Сообщите test-RMSE всех известных пар, отдельно для верхней и нижней четверти фильмов по числу оценок, и устойчивость $2$ -мерной карты между seed (средний угол между подпространствами $V^\top\tilde V$ ). Убедитесь, что RMSE падает от $d{=}2$ к $d{=}8$ и выходит на полку.

5баллов

Докажите инвариантность прогноза к повороту строго: пусть все векторы заменены на $p_u\to Rp_u$ , $q_i\to Rq_i$ с ортогональной $R$ . Покажите, что не только каждое $p_u^\top q_i$ , но и все попарные расстояния $\lVert q_i-q_j\rVert$ сохраняются, а значит, ранжирование рекомендаций и ближайшие соседи не меняются. Выведите отсюда, что осям карты нельзя приписывать абсолютный смысл, и предложите, как проверять гипотезу «эта ось — жанр» через корреляцию с известными метками.

6баллов

Постройте ранжирующую оценку на u.data. Для каждого пользователя candidate set — все train-фильмы, кроме уже оценённых им в train; релевантные — его test-фильмы с рейтингом $\ge4$ . Обучите факторную модель ( $d=32$ , ALS) и для каждого пользователя с непустым релевантным множеством отранжируйте кандидатов по прогнозу. Сообщите macro-Recall@10 и объясните, почему эта величина зависит от размера candidate set: сравните ожидаемую вероятность случайного попадания в top-10 среди $100$ и среди $10\,000$ кандидатов.

PCA, эмбеддинги и рекомендации

Почти пустая матрица

Сначала смещения, потом факторы

Карта вкусов

Потрогай карту

Ваш вектор вкуса и рекомендации

Оси карты можно повернуть

Сколько факторов брать

Популярные и редкие

Холодный старт

Коротко о рекомендациях

Задачи