Хабрахабр

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

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

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

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

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

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

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

  • Когда пользователей много (почти всегда), задача поиска ближайшего соседа становится плохо вычислимой. Например, для 1 млн пользователей нужно рассчитать и хранить $\frac{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})$

Насколько высока концентрация интересных товаров в начале списка рекомендаций

Если мы возьмем рекомендательные системы в онлайн бизнесе, то они, как правило, преследует две (иногда противоречивые) цели:

  1. проинформировать пользователя об интересном товаре,
  2. побудить его совершить покупку (путем рассылки, составления персонального предложения и т.д.).

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

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

Тестирование с пользователем

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

$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). Также для обхода переобучения к среднеквадратичной ошибке добавляются регуляризационные коэффиценты. Оптимизация происходит поочередно, сначала по факторам пользователей, потом по факторам товаров.

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

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

Ассоциативные правила (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 рекомендации), но она легко трансформируется в задачу матчинга пользователей и товаров.

Многообразие архитектур глубоких сетей безгранично, поэтому 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)$

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

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

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

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

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

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

Резюме

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть