Часть II · Кандидатогенерация · глава 5 из 19

Коллаборативная фильтрация и меры похожести

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

Что унести из главы

Все меры похожести — это одна формула с разной нормировкой: $|A \cap B| / (|A|\,|B|)^{\alpha}$. Косинус — $\alpha = 0.5$, Жаккар — примерно линейно, PMI — $\alpha = 1$.
Порядок пар меняется на противоположный. Косинус ставит первой пару блокбастеров, PMI — пару из пятнадцати наблюдений. Обе меры «правы» по-своему.
PMI сходит с ума на редком: два айтема, которых посмотрел один и тот же человек, дают PMI = 13.8 — втрое больше честной пары с шестьюстами наблюдениями.
Похожесть можно не считать, а выучить. EASE и SLIM — та же формула скоринга, но веса берутся из регрессии, и это чинит сразу три болезни посчитанных мер.

1. Идея коллаборативной фильтрации

«Похожим людям нравится похожее». Формально — два зеркальных подхода.

	User-based	Item-based
логика	найти похожих пользователей, взять то, что понравилось им	найти айтемы, похожие на те, что пользователь уже брал
что считаем	похожесть между пользователями	похожесть между айтемами
сколько объектов	пользователей обычно больше и они менее стабильны	айтемов меньше, похожести стабильнее во времени
в проде	редко	почти всегда: матрицу можно посчитать заранее и хранить как списки

Формула скора и что в ней стоит понимать

Для item-based скор айтема $i$ для пользователя $u$ — это сумма по тому, с чем пользователь уже взаимодействовал:

$$ \hat{s}(u, i) \;=\; \sum_{j \in H(u)} \mathrm{sim}(i, j) $$

где $H(u)$ — история пользователя. То есть: пройти по всему, что человек уже брал, и сложить, насколько каждое из этого похоже на кандидата.

Часто добавляют нормировку на $\sum_j \mathrm{sim}(i,j)$ или ограничивают сумму top-$k$ ближайшими соседями — иначе длинная история размывает сигнал, а шумные слабые связи в сумме перевешивают несколько сильных.

Ключевое: вся модель — это матрица $\mathrm{sim}$. Что в неё подставить — и есть содержание главы.

2. Меры похожести на одной оси

Для бинарных данных (взаимодействовал / нет) три классические меры записываются почти одинаково.

$$ J(A,B) = \frac{|A \cap B|}{|A \cup B|}, \qquad \cos(A,B) = \frac{|A \cap B|}{\sqrt{|A|\,|B|}}, \qquad \mathrm{PMI}(A,B) = \log \frac{P(A,B)}{P(A)P(B)} $$

Одна ось: сила нормировки

Все три имеют вид $|A \cap B| \big/ (|A|\,|B|)^{\alpha}$ — различается только показатель, то есть насколько жёстко мера штрафует популярность.

Мера	Нормировка	Блокбастер 10⁶ и нишевый 10³, пересечение 900
сырое число совпадений	$\alpha = 0$ — никакой	900
косинус	$\alpha = 0.5$ — корень	0.0285
Жаккар	примерно линейная	0.0009
PMI и родственники	$\alpha = 1$ — полная	9·10⁻⁷ до нормировки

Нагляднее всего в частном случае, когда нишевый айтем целиком вложен в блокбастер — все, кто смотрел $B$, смотрели и $A$. Тогда Жаккар равен $|B|/|A|$, а косинус — $\sqrt{|B|/|A|}$:

$\|B\|/\|A\|$	Жаккар	Косинус
1 / 100	0.0100	0.1000
1 / 1 000	0.0010	0.0316
1 / 10 000	0.0001	0.0100

Числа воспроизводятся скриптом _tools/similarity.py в этом репозитории.

Жаккар давит разрыв в популярности линейно, косинус — корнем. Отсюда практическое: косинус мягче к популярному, Жаккар жёстче.

«Косинус же штрафует популярность» — смотря с чем сравнивать

Здесь легко запутаться, потому что косинус встречается в двух разных сюжетах и оказывается по разные стороны.

Косинус против скалярного произведения — это про обученные эмбеддинги. Скалярное произведение раскладывается как $|a||b|\cos\theta$, а норма в матричной факторизации выучивает популярность. Косинус делит на нормы и выбрасывает её целиком. Здесь косинус популярность штрафует.
Косинус против Жаккара — это про сырые множества взаимодействий. У обеих мер в числителе $|A \cap B|$, различает знаменатель, и знаменатель Жаккара жёстче. Здесь косинус к популярности мягче, причём в тридцать с лишним раз: 0.0285 против 0.0009.

Противоречия нет: сравнения разные. Но на собеседовании фраза «косинус убирает популярность» без уточнения, с чем сравниваем, — повод для встречного вопроса.

PMI: сравнение не с размерами, а с ожиданием

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

$$ \mathbb{E}\bigl[|A \cap B|\bigr] \;=\; \frac{|A|\cdot|B|}{N}, \qquad \mathrm{PMI} \;=\; \log \frac{|A \cap B|}{\mathbb{E}\bigl[|A \cap B|\bigr]} $$

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

Четыре пары, аудитория миллион

Пара	$\|A\|$	$\|B\|$	пересечение	ожидалось	косинус	Жаккар	PMI	NPMI
два блокбастера	500 000	400 000	210 000	200 000	0.470	0.304	0.05	0.031
два нишевых	2 000	3 000	600	6	0.245	0.136	4.61	0.621
нишевый + сверхредкий	2 000	20	15	0.04	0.075	0.007	5.93	0.534
блокбастер + нишевый	500 000	2 000	1 200	1 000	0.038	0.002	0.18	0.027

Числа воспроизводятся скриптом _tools/similarity.py в этом репозитории.

Порядок получается противоположным:

косинус и Жаккар: блокбастеры → нишевые → сверхредкий → блокбастер с нишевым;
PMI: сверхредкий → нишевые → блокбастер с нишевым → блокбастеры.

Разберём первую строку — она главная

Пересечение двух блокбастеров огромно, 210 тысяч человек, и косинус с Жаккаром объявляют эту пару самой похожей в таблице.

Но случайно ожидалось 200 тысяч. То есть фактической связи почти нет: люди смотрели оба фильма не потому, что те похожи, а потому что оба смотрели все. PMI это видит: $\ln(210000/200000) = 0.05$, практически ноль.

И наоборот, у двух нишевых пересечение всего 600 человек — вдесятеро меньше. Зато ожидалось шесть. Превышение в сто раз, $\ln 100 = 4.61$. Вот это настоящая связь.

И сразу обратная сторона: PMI сходит с ума на редком

Третья строка таблицы: пара «нишевый + сверхредкий» получает у PMI 5.93 — больше, чем честная пара нишевых с их 4.61. При том что вся оценка построена на пятнадцати наблюдениях.

Доведём до предела. Пусть два айтема посмотрел ровно один человек, и это один и тот же человек:

$$ \mathrm{PMI} \;=\; \ln\frac{1 \cdot 10^{6}}{1 \cdot 1} \;=\; 13.8 $$

Втрое больше, чем у пары с настоящей связью на шестистах наблюдениях. Чистый шум занимает первое место.

Причина: PMI измеряет, во сколько раз превышено ожидание, а когда ожидание близко к нулю, любое единичное совпадение даёт гигантское отношение.

NPMI и чего он не чинит

Нормировка на $-\log P(A,B)$ наказывает именно редкость: чем реже пара, тем больше знаменатель.

$$ \mathrm{NPMI}(A,B) \;=\; \frac{\mathrm{PMI}(A,B)}{-\log P(A,B)} \;\in\; [-1, 1] $$

В таблице видно, что это работает: NPMI ставит пару нишевых (0.621) выше пары со сверхредким (0.534), восстанавливая здравый порядок. Но полностью проблему не снимает — 0.534 всё ещё очень высоко для пятнадцати наблюдений.

Чего NPMI не делает — вопреки распространённому мнению

Часто говорят, что NPMI «убирает популярность». Это неверно, и проверяется прямо: возьмите три пары с одинаковым превышением ожидания — популярную, среднюю и нишевую. NPMI даст им разные значения, и популярная получит больше, потому что у неё меньше знаменатель $-\log P(A,B)$.

То есть NPMI не нейтрален к популярности — он вносит собственное, обратное PMI предпочтение. На практике это скорее к лучшему (шум давится), но формулировка «очищено от популярности» неточна.

Поэтому в проде NPMI почти всегда идёт с двумя добавками: порог по числу совстречаемостей (пары с $|A \cap B| < 10\ldots50$ выбрасываются вовсе) и сжатие в сторону нуля для малых счётчиков.

Что здесь надо увидеть

Переключайте меру и смотрите, как меняется состав топа соседей, а не только числа. У косинуса наверху популярное, у PMI — редкое.
Поставьте порог по числу совстречаемостей: у PMI из топа исчезает шум, и порядок становится осмысленным. Это и есть тот приём, который применяют в проде.
Обратите внимание на нормировку эмбеддингов: скалярное произведение и косинус дают разный топ, потому что норма выучивает популярность.

Что сказать на собесе: «Все меры — одна формула с разной силой нормировки. Косинус мягче Жаккара к популярному, PMI сравнивает не с размерами, а с ожиданием и потому взрывается на редком. В проде — NPMI с порогом по совстречаемостям».

3. Похожесть можно не считать, а выучить

Все меры выше объединяет одно: формулу выбрал человек, и она смотрит на пару айтемов изолированно от всех остальных. EASE и SLIM снимают оба ограничения.

Одна задача в одну строку

Ищем item-item матрицу $B$, приближающую матрицу взаимодействий саму собой:

$$ X \;\approx\; XB $$

Расписав ячейку, получаем скор айтема $i$ для пользователя $u$:

$$ \hat{x}_{ui} \;=\; \sum_{j\,:\,x_{uj}=1} B_{ji} $$

Это ровно та же формула, что у item-based CF в начале главы. Отличие одно: раньше веса брались из готовой меры похожести, теперь столбец $j$ матрицы $B$ — коэффициенты линейной регрессии, предсказывающей столбец $j$ матрицы $X$ по всем остальным столбцам.

Отсюда всё остальное: регрессия видит предикторы вместе, а не по одному.

EASE: аналитическое решение

$$ \min_{B}\ \lVert X - XB\rVert_F^2 + \lambda \lVert B \rVert_F^2 \qquad \text{при } \operatorname{diag}(B) = 0 $$

Ограничение на диагональ обязательно: без него есть тривиальное решение $B = I$ — каждый айтем идеально предсказывается сам собой, ошибка ноль, пользы ноль.

Задача решается в замкнутой форме. Обозначив $G = X^{\top}X + \lambda I$ и $P = G^{-1}$:

$$ B_{ij} = -\frac{P_{ij}}{P_{jj}}\ (i \ne j), \qquad B_{jj} = 0 $$

Никакого градиентного спуска — одно обращение матрицы.

Что означает $-P_{ij}/P_{jj}$

Формула выглядит артефактом вывода, но у неё точный смысл. $P = (X^{\top}X + \lambda I)^{-1}$ — оценка прецизионной матрицы, обратной ковариационной.

Известный факт из графических моделей: условное матожидание одной переменной при известных всех остальных равно $\mathbb{E}[x_j \mid x_{-j}] = x_{-j} \cdot B_{-j,j}$ — то есть это и есть правило предсказания EASE.

Отсюда строгое различие с косинусом. Ноль в ковариационной матрице — маргинальная независимость: «встречаются вместе не чаще случайного». Ноль в прецизионной — условная: «не добавляют друг о друге ничего сверх остального каталога». Косинус, Жаккар и PMI живут в первом мире, EASE — во втором.

Что это даёт на числах

Синтетический лог на 20 000 корзин, где порождающий процесс известен. Предсказываем «хлопья»:

Предиктор	Доля корзин	Косинус	EASE
молоко	0.373	0.720	0.319
молоко лайт (почти дубль)	0.359	0.705	0.245
пакет (берут почти все)	0.901	0.499	0.083
кофе (не связан)	0.301	0.302	0.024
мюсли-конкурент (субститут)	0.197	+0.135	−0.115

Числа воспроизводятся скриптом _tools/ease_demo.py в этом репозитории.

Три поломки посчитанной похожести видны сразу:

Популярность притворяется связью. «Пакет» по косинусу получает третье место, выше кофе. Он не предсказывает хлопья — он просто лежит в каждой корзине.
Дубликаты считаются дважды. Косинус даёт молоку и молоку-лайт в сумме 1.426; EASE делит вес между коллинеарными предикторами: 0.564.
Отрицательной связи не существует. Субститут по косинусу получает +0.135, по регрессии −0.115. Формула похожести отрицательный вес выдать не может по построению.

SLIM и чем EASE от него отличается

SLIM появился раньше (2011) и решает ту же задачу с двумя добавками: $L_1$-регуляризацией, дающей разреженную $B$, и ограничением $B \ge 0$.

Что показал эксперимент Стека

NDCG@100 на трёх стандартных датасетах:

Модель	ML-20M	Netflix	MSD
EASE	0.420	0.393	0.389
EASE с занулёнными отрицательными весами	0.402	0.373	0.379
SLIM	0.401	0.379	не досчитался

Таблица 1 из Steck, 2019.

Вторая строка — ключ. Это тот же EASE, у которого просто зачеркнули отрицательные веса, и он немедленно опускается до уровня SLIM. Весь отрыв объясняется ограничением $B \ge 0$ — тем самым, из-за которого субститут в примере выше получил ноль вместо −0.115.

Цифра, переворачивающая интуицию: около 60% выученных весов отрицательны, на всех трёх датасетах. Модель тратит бо́льшую часть ёмкости на то, чтобы говорить, чего пользователю не надо.

Что не умеет ни один item-item метод

Холодный старт не решается вообще. У нового айтема столбец в $X$ нулевой, значит и в $B$ нулевой: порекомендовать его невозможно ни при каких условиях.
Никакого контекста. Ни времени, ни устройства, ни признаков пользователя — только множество его айтемов.
Порядок истории игнорируется. $x_u$ — множество, а не последовательность.
Память квадратична по каталогу. Для EASE $B$ плотная: 30 тысяч айтемов во float64 — около 7 ГБ, миллион невозможен. Ради этого SLIM и придуман.

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

Вопросы с собеседований

Чем отличаются Жаккар, косинус и PMI?

Силой нормировки. Все три имеют вид $|A\cap B| / (|A||B|)^{\alpha}$: косинус $\alpha = 0.5$ (корень), Жаккар примерно линейно, PMI $\alpha = 1$ (полная нормировка).

Практически: косинус мягче к популярному, чем Жаккар — в примере с блокбастером 10⁶ и нишевым 10³ при пересечении 900 косинус даёт 0.028, Жаккар 0.0009, разница в тридцать раз.

PMI отвечает на другой вопрос: не «насколько велико пересечение», а «во сколько раз оно больше ожидаемого при независимости». Поэтому два блокбастера с пересечением 210 тысяч при ожидаемых 200 тысячах получают у PMI почти ноль, а два нишевых с пересечением 600 при ожидаемых шести — 4.61.

Почему PMI нельзя использовать в чистом виде?

Он взрывается на редких парах. Пара из пятнадцати наблюдений получает PMI 5.93 — больше, чем честная пара на шестистах наблюдениях с её 4.61. В пределе: два айтема, которых посмотрел ровно один и тот же человек, дают $\ln 10^6 = 13.8$, то есть чистый шум занимает первое место.

Причина в том, что PMI меряет отношение к ожиданию, а когда ожидание близко к нулю, любое единичное совпадение даёт гигантское отношение.

Лечение — NPMI (нормировка на $-\log P(A,B)$, которая наказывает редкость) плюс обязательно порог по числу совстречаемостей и сжатие для малых счётчиков. Одного NPMI мало: пара из пятнадцати наблюдений всё ещё получает 0.534.

Правда ли, что NPMI очищает похожесть от популярности?

Нет, и это распространённая неточность. Проверяется прямо: возьмите три пары с одинаковым превышением ожидания — популярную, среднюю и нишевую. NPMI даст им разные значения, причём популярная получит больше, потому что у неё меньше знаменатель $-\log P(A,B)$.

То есть NPMI вносит собственное предпочтение, обратное тому, что делает PMI. На практике это скорее полезно — шум давится, — но формулировка «очищено от популярности» неверна.

Чем выученная item-item матрица лучше посчитанной?

Формула скоринга у них одна и та же: пройти по истории и сложить веса. Различие в том, откуда веса. Посчитанная мера смотрит на пару айтемов изолированно, регрессия видит все предикторы вместе.

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

Формально $B_{ij} = -P_{ij}/P_{jj}$ — это коэффициенты частной регрессии, то есть переход от маргинальной зависимости к условной.

EASE или SLIM: в чём разница и что выбрать?

EASE — это SLIM, с которого сняли $L_1$ и ограничение $B \ge 0$. Взамен появляется решение в замкнутой форме: одно обращение матрицы вместо координатного спуска по столбцам.

По качеству разрыв объясняется целиком ограничением на знак: EASE с занулёнными отрицательными весами падает ровно до уровня SLIM (0.402 против 0.401 на ML-20M). Около 60% весов в EASE отрицательны — модель тратит большую часть ёмкости на «чего не надо».

Выбор по ресурсам: EASE стоит $O(|I|^3)$ времени и $O(|I|^2)$ памяти, зато не зависит от числа пользователей. Для десятков тысяч айтемов — берите EASE. Если каталог таков, что плотная матрица не помещается, — SLIM с его разреженностью.

Шпаргалка одним экраном

Формула CF

$\hat s(u,i) = \sum_{j \in H(u)} \mathrm{sim}(i,j)$. Вся модель — матрица sim.

Одна ось

$|A\cap B|/(|A||B|)^\alpha$. Косинус 0.5, Жаккар ~1 линейно, PMI 1. Косинус мягче к популярному.

PMI

Сравнивает с ожиданием $|A||B|/N$, а не с размерами. Взрывается на редком: шум даёт 13.8.

NPMI

Делит на $-\log P(A,B)$. Порядок чинит, популярность не убирает. Нужен порог по совстречаемостям.

EASE

$X \approx XB$, $B_{ij} = -P_{ij}/P_{jj}$ — частная регрессия. Ловит субституты: 60% весов отрицательны.

Общий предел

Холодный старт не решается вовсе, контекста нет, память $O(|I|^2)$. Отсюда — кандген, а не финальная модель.

Первоисточники

G. Linden, B. Smith, J. York. Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing 2003.
G. Bouma. Normalized (Pointwise) Mutual Information in Collocation Extraction, 2009 — откуда взялась нормировка NPMI.
H. Steck. Embarrassingly Shallow Autoencoders for Sparse Data, WWW 2019 — EASE, вывод и сравнение со SLIM.
X. Ning, G. Karypis. SLIM: Sparse Linear Methods for Top-N Recommender Systems, ICDM 2011.
Числа главы: _tools/similarity.py и _tools/ease_demo.py в этом репозитории.

Мера	Нормировка	Блокбастер 10⁶ и нишевый 10³, пересечение 900
сырое число совпадений	\(\alpha = 0\) — никакой	900
косинус	\(\alpha = 0.5\) — корень	0.0285
Жаккар	примерно линейная	0.0009
PMI и родственники	\(\alpha = 1\) — полная	9·10⁻⁷ до нормировки