Анатомия рекомендательных систем. Часть вторая30.08.2018 12:47

Неделю назад я делал здесь обзор существующих алгоритмов рекомендаций. В этой статье я продолжу данный обзор: расскажу об item-based варианте коллаборативной фильтрации, о методах, основанных на матричных разложениях, проблемах тестирования, а также о менее «раскрученных» (но не менее интересных) алгоритмах.

8b52a355264c4e3eefba433cc39055fc.jpg


Коллаборативная фильтрация (Item-based вариант)


Подход Item-based является естественной альтернативой классическому подходу User-based, описанному в первой части, и почти полностью его повторяет, за исключением одного момента — применяется он к транспонированной матрице предпочтений. Т.е. ищет близкие товары, а не пользователей.

Напомню, пользовательская коллаборативная фильтрация (user-based CF) ищет для каждого клиента группу наиболее похожих на него (в терминах предыдущих покупок) клиентов и усредняет их предпочтения. Эти усредненные предпочтения и служат рекомендациями для пользователя. В случае же с товарной коллаборативной фильтрацией (item-based CF) ближайшие соседи ищутся на множестве товаров — столбцов матрицы предпочтений. И усреднение происходит именно по ним.

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

Преимущества Item-based перед User-based:

  • Когда пользователей много (почти всегда), задача поиска ближайшего соседа становится плохо вычислимой. Например, для 1 млн пользователей нужно рассчитать и хранить $\frac{1}{2} 10^6 * 10^6$ ~ 500 млрд расстояний. Если расстояние кодировать 8 байтами, это получается 4TB для одной только матрицы расстояний. Если мы делаем Item-based, то сложность вычислений снижается с $O(N^2n)$ до $O(n^2N)$, а матрица расстояний имеет размерность уже не (1 млн на 1 млн) а, например, (100 на 100) по количеству товаров.
  • Оценка близости товаров гораздо более точная, чем оценка близости пользователей. Это прямое следствие того, что пользователей обычно намного больше, чем товаров и следовательно стандартная ошибка при расчете корреляции товаров там существенно меньше. У нас просто больше информации, чтобы сделать вывод.
  • В user-based варианте описания пользователей, как правило, сильно разрежены (товаров много, оценок мало). С одной стороны это помогает оптимизировать расчет — мы перемножаем только те элементы, где есть пересечение. Но с другой стороны — сколько соседей не бери, список товаров, которые в итоге можно порекомендовать, получается очень небольшим.
  • Предпочтения пользователя могут меняться со временем, но описание товаров штука гораздо более устойчивая.


В остальном алгоритм почти полностью повторяет User-based вариант: то же косинусное расстояние как основная мера близости, та же необходимость нормализации данных. Число соседних товаров N обычно выбирают в районе 20.

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

Несколько возможных усовершенствований алгоритма:

  • Интересная модификация — считать «похожесть» продуктов не типичным косинусным расстоянием, а сравнивая их содержание (content-based similarity). Если при этом пользовательские предпочтения никак не учитываются, такая фильтрация перестает быть «коллаборативной». При этом вторая часть алгоритма — получение усредненных оценок — никак не изменяется.
  • Другая возможная модификация — при вычислении item similarity взвешивать пользователей. Например, чем больше пользователь сделал оценок, тем больший у него вес при сравнении двух товаров.
  • Вместо простого усреднения оценок по соседним товарам можно подбирать веса, делая линейную регрессию.


При использовании item-based подхода рекомендации имеют тенденцию быть более консервативными. Действительно, разброс рекомендаций получается меньше и следовательно меньше вероятность показать нестандартные товары.

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

Оценка качества системы


Тестирование рекомендательной системы — процесс непростой и всегда вызывающий множество вопросов, главным образом из-за неоднозначности самого понятия «качество».

Вообще, в задачах машинного обучения есть два основных подхода к тестированию:

  • offline тестирование модели на исторических данных с помощью ретро-тестов,
  • тестирование готовой модели с помощью A/B тестирования (запускаем несколько вариантов, смотрим какой дает лучший результат).


Оба этих подхода активно применяются при разработке рекомендательных систем. Начнем с offline тестирования.

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

Стандартный подход — это кросс-валидация методами leave-one-out и leave-p-out. Многократное повторение теста с усреднением результатов позволяет получить более устойчивую оценку качества.

  • leave-one-out — модель обучается на всех оцененных пользователем объектах, кроме одного, а тестируется на этом одном объекте. Так делается для всех n объектов, и среди полученных n оценок качества вычисляется среднее.
  • leave-p-out — то же самое, но на каждом шаге исключается p точек.


Все метрики качества можно условно разделить на три категории:

  • Prediction Accuracy — оценивают точность предсказываемого рейтинга,
  • Decision support — оценивают релевантность рекомендаций,
  • Rank Accuracy метрики — оценивают качество ранжирования выдаваемых рекомендаций.


К сожалению, не существует единой рекомендуемой метрики на все случаи жизни и каждый, кто занимается тестированием рекомендательной системы, подбирает её под свои цели.

Когда рейтинги оцениваются по непрерывной шкале (0–10), как правило, достаточно метрик класса Prediction Accuracy.

Название Формула Описание
MAE (Mean Absolute Error) $E(|P-R|)$ Среднее абсолютное отклонение
MSE (Mean Squared Error) $E(|P-R|^2)$ Среднеквадратичная ошибка
RMSE (Root Mean Squared Error) $\sqrt{E(|P-R|^2)}$ Корень из среднеквадратичной ошибки

Метрики класса Decision Support работают с бинарными данными (0 и 1, да и нет). Если в нашей задаче рейтинги изначально откладываются по непрерывной шкале, их можно перевести в бинарный формат, применив решающее правило — скажем, если оценка меньше 3.5, считаем оценку «плохой», а если больше, то «хорошей».

Название Формула Описание
Precision $\frac{TP}{TP+FP}$ Доля рекомендаций, понравившихся пользователю
Recall $\frac{TP}{TP+TN}$ Доля интересных пользователю товаров, которая показана
F1-Measure $\frac{2PR}{P + R}$ Среднее гармоническое метрик Precision и Recall.
Полезно, когда заранее невозможно сказать, какая из метрик важнее
ROC AUC Насколько высока концентрация интересных товаров в начале списка рекомендаций
Precision@N Метрика Precision, посчитанная на Top-N записях
Recall@N Метрика Recall, посчитанная на Top-N записях
AverageP Среднее значение Precision на всем списке рекомендаций

Как правило, рекомендации выводятся списком из нескольких позиций (сначала топовая, затем в порядке убывания приоритета). Метрики класса Rank Accuracy измеряют насколько правилен порядок показа рекомендаций в отсортированном списке.

Название Формула Описание
Mean Reciprocal Rank $E(\frac{1}{pos})$ На какой позиции списка рекомендаций пользователь находит первую полезную
Spearman Correlation $E(|P-R|^2)$ Корреляция (Спирмена) реального и прогнозируемого рангов рекомендаций
nDCG $\sum{\frac{R(i)}{max(1,log(i))}}$ Информативность выдачи с учетом ранжирования рекомендаций
Fraction of Concordance Pairs $P(X_{R} > X_{P})$» /></td> <td>Насколько высока концентрация интересных товаров в начале списка рекомендаций</td> </tr></table><p> Если мы возьмем рекомендательные системы в онлайн бизнесе, то они, как правило, преследует две (иногда противоречивые) цели: </p> <ol><li>проинформировать пользователя об интересном товаре, </li> <li>побудить его совершить покупку (путем рассылки, составления персонального предложения и т.д.).</li> </ol> <p><br />Как и в любой модели, направленной на мотивацию пользователя к действию, оценивать следует только инкрементальный прирост целевого действия. Т.е., например, при подсчете покупок по рекомендации нам нужно исключить те, которые пользователь и так сам бы совершил без нашей модели. Если этого не сделать, эффект от внедрения модели будет сильно завышен.</p> <p>Lift — показатель того, во сколько раз точность модели превосходит некий baseline алгоритм. В нашем случае baseline алгоритмом может быть просто отсутствие рекомендаций. Данная метрика хорошо отлавливает долю инкрементальных покупок и это позволяет эффективно сравнивать разные модели.</p> <h3><span>Тестирование с пользователем</span></h3><p> <br /></p> <div><img src=

Источник

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

Первый и самый очевидный сценарий — анализ событий сайта. Мы смотрим, что пользователь делает на сайте, обращает ли внимание на наши рекомендации, переходит ли по ним, какие фичи системы пользуются спросом, какие — нет, какие товары лучше рекомендуются, какие хуже. Чтобы понять какой из алгоритмов в целом работает лучше или просто попробовать новую перспективную идею, делаем A/B тестирование и собираем результат.

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

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

Неявные рейтинги и унарные данные


В начале своего развития рекомендательные системы применялись в сервисах, где пользователь явно оценивает товар путем выставления ему рейтинга — это и Amazon, и Netflix и прочие сайты интернет торговли. Однако с ростом популярности рекомендательных систем возникла потребность применять их ещё и там, где никаких рейтингов нет — это могут быть банки, автомастерские, ларьки с шаурмой и любые другие сервисы, где по какой-то причине невозможно наладить систему оценивания. В этих случаях интересы пользователя можно вычислить лишь по косвенным признакам — о пользовательских предпочтениях говорят определенные действия с товаром, например, просмотр описания на сайте, добавление товара в корзину и т.д. Здесь используется принцип «купил — значит любит!». Такая система неявного оценивания называется Implicit Ratings.

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

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

  • она ему действительно не интересна (это отрицательный кейс),
  • она ему интересна, но он просто не знает о ней (это пропущенный положительный кейс).


Но у нас нет никаких данных, чтобы отличить первый случай от второго. Это плохо, потому что обучая модель, мы должны подкреплять её на положительных кейсах и штрафовать на отрицательных, а так будем почти всегда штрафовать, и в итоге модель будет смещенной.

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

В обоих примерах задача превращается в задачу Unary Class Classification.

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

_9ko4r9kinlai0dlsohqumxh13k.jpeg

Источник

Алгоритмы факторизации


Было бы здорово описать интересы пользователя более «крупными мазками». Не в формате «он любит фильмы X, Y и Z», а в формате «он любит современные российские комедии». Помимо того, что это увеличит обобщаемость модели, это еще решит проблему большой размерности данных — ведь интересы будут описываться не вектором товаров, а существенно меньшим вектором предпочтений.

Такие подходы еще называют спектральным разложением или высокочастотной фильтрацией (поскольку мы убираем шум и оставляем полезный сигнал). В алгебре существует много различных разложений матриц, и одно из наиболее часто используемых называется SVD-разложением (singular value decomposition).

Метод SVD применялся в конце 80-х для выборки похожих по смыслу, но не по содержанию страниц, а затем стал использоваться и в задачах рекомендаций. В основе метода — разложение исходной матрицы рейтингов ® в произведение 3 матриц:

$R = U * D * S$, где размеры матриц $(k,m) = (k,r) * (r,r) * (r,m)$, а r —
ранг разложения — параметр, характеризующий степень детализации разложения.

Применяя данное разложение к нашей матрице предпочтений, мы получаем две матрицы факторов (сокращенных описаний):

U — компактное описание предпочтений пользователя,
S — компактное описание характеристик продукта.

Важно, что при таком подходе мы не знаем, какие именно характеристики соответствуют факторам в уменьшенных описаниях, для нас они закодированы какими-то числами. Поэтому SVD является неинтерпретируемой моделью.

Для того, чтобы получить приближение матрицы предпочтений достаточно перемножить матрицы факторов. Сделав это получим оценку рейтинга для всех пар клиент-продукт.

Общее семейство подобных алгоритмов называется NMF (non-negative matrix factorization). Как правило вычисление таких разложений весьма трудоемко, поэтому на практике часто прибегают к их приближенным итеративным вариантам.

ALS (alternating least squares) — популярный  итеративный алгоритм разложения матрицы предпочтений на произведение 2 матриц: факторов пользователей (U) и факторов товаров (I). Работает по принципу минимизации среднеквадратичной ошибки на проставленных рейтингах. Оптимизация происходит поочередно, сначала по факторам пользователей, потом по факторам товаров. Также для обхода переобучения к среднеквадратичной ошибке добавляются регуляризационные коэффиценты.

31687f3859ed3bd36b9c769dceaaae60.png


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

Другие подходы


Ассоциативные правила (Association Rules)

Ассоциативные правила обычно используются при анализе продуктовых корреляций (Market Basket Analysis) и выглядят примерно так «если в чеке клиента есть молоко, то в 80% случаев там будет и хлеб». То есть если мы видим, что молоко в корзину клиент уже положил, самое время напомнить о хлебе.

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

RBM (restricted Bolzman Machines)

Ограниченные машины Больцмана — относительно старый подход, основанный на стохастических рекуррентных нейронных сетях. Он представляет собой модель с латентными переменными и в этом похож на SVD-разложение. Здесь также ищется наиболее компактное описание пользовательских предпочтений, которое кодируется с помощью латентных переменных. Метод не был разработан для поиска рекомендаций, но он успешно использовался в топовых решениях Netflix Prize и до сих пор применяется в некоторых задачах.

Автоэнкодеры (autoencoders)

В основе лежит все тот же принцип спектрального разложения, поэтому такие сети еще называют denoising auto-encoders. Сеть сначала сворачивает известные ей данные о пользователе в некоторое компактное представление, стараясь оставить только значимую информацию, а затем восстанавливает данные в исходной размерности. В итоге получается некий усредненный, очищенный от шума шаблон, по которому можно оценить интерес к любому продукту.

DSSM (deep sematic similiarity models)

Один из новых подходов. Все тот же принцип, но в роли латентных переменных здесь внутренние тензорные описания входных данных (embeddings). Изначально модель создавалась для матчинга запроса с документами (как и content-based рекомендации), но она легко трансформируется в задачу матчинга пользователей и товаров.

4d1933702c1fd2030b0fff74560b0c6b.png


Многообразие архитектур глубоких сетей безгранично, поэтому Deep Learning предоставляет действительно широкое поле для экспериментов в области рекомендательных систем.

Гибридные решения


На практике редко используется только один подход. Как правило несколько алгоритмов комбинируются в один, чтобы достичь максимального эффекта.

Два главных преимущества объединения моделей — это увеличение точности и возможность более гибкой настройки на разные группы клиентов. Недостатки — меньшая интерпретируемость и бОльшая сложность реализации и поддержки.

Несколько стратегий объединения:

  • Weighting — считать средневзвешенный прогноз по нескольким оценкам,
  • Stacking — предсказания отдельных моделей являются входами другого (мета)классификатора, который обучается правильно взвешивать промежуточные оценки,


  • Switching — для разных продуктов/пользователей применять различные алгоритмы,
  • Mixing — вычисляются рекомендации по разным алгоритмам, а потом просто объединяются в один список.


Например, используется content-based recommender, а в качестве одной из фич — результат коллаборативной фильтрации.

Feature Weighted (Linear) Stacking:

$P(u,i) = w_1 P_1(u,i) + w_2 P_2(u,i) + … + w_n P_n(u,i)$


Веса $ w_1,w_2 … w_n $ обучаются на выборке. Как правило, для этого используется логистическая регрессия.

Stacking в общем виде:

$ P(u,i) = f_1(u,i) P_1(u,i) + f_2(u,i) P_2(u,i) + … + f_n(u,i) P_n(u,i)$

2baa713e45d7c09a42a6f084efdcc227.gif


Краткое описание решения Netflix


Netflix Prize — это конкурс, проводившийся в 2009 году, в котором требовалось спрогнозировать оценку пользователями фильмотеки Netflix. Неплохие призовые в 1 млн долларов вызвали ажиотаж и привлекли большое количество участников, в том числе довольно известных людей в ИИ.

Это была задача с явными рейтингами, оценки ставились по шкале от 1 до 5, а точность прогноза оценивалась по RMSE. Большинство первых мест заняли большие ансамбли классификаторов.

Победивший ансамбль использовал модели следующих классов:

  • basic model — регрессионная модель, основанная на средних оценках
  • collaborative filtering — коллаборативная фильтрация
  • RBM — ограниченные машины Больцмана
  • random forests — предиктивная модель


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

Резюме


Постановка задачи генерации рекомендаций очень проста — мы составляем матрицу предпочтений с известными нам оценками пользователей, если получается, дополняем эти оценки информацией по клиенту и товару, и пытаемся заполнить неизвестные значения.

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

Но в целом все это многообразие сводится к очень небольшому набору подходов, которые я и попытался описать в данной статье.

Напоминаю про наши вакансии.

© Habrahabr.ru