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

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


    Коллаборативная фильтрация (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})$ Насколько высока концентрация интересных товаров в начале списка рекомендаций
    Если мы возьмем рекомендательные системы в онлайн бизнесе, то они, как правило, преследует две (иногда противоречивые) цели:

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

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

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

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


    Источник

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

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

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

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

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


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

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

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

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

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

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

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

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

    Источник

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


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


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

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


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

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

    • +39
    • 5,2k
    • 9

    ГК ЛАНИТ

    306,62

    Ведущая многопрофильная группа ИТ-компаний в РФ

    Поделиться публикацией

    Похожие публикации

    Комментарии 9
      +1
      Отличный, почти академический обзор.
      Но есть вопрос.
      Вот продаю красные туфли и точно знаю кому, сколько и за сколько продал. А теперь хочу продавать красные кеды. И ни один из методов изложенных выше не даст ответа — выстрелят красные кеды или нет.
      Эти методы хороши для изучения прошлого, прошлых привычек, прошлых предпочтений.
      Когда появляется новый товар, то не с чем сравнивать. Можно только выдвинуть гипотезу, что, те кто носит красные туфли будут носить красные кеды, можно и любую другую.
      Только вот нет инерционности в пристрастиях. Носит и носит чел красные туфли, а тут на работе намекнули и всё, он теперь носит синие. Никакая изложенная выше метода это не сможет предсказать.

      Но обзоры классные, полные и подробные. Даже A/B к месту упомянут )))
        +1
        Эта проблема частично освещена в первой статье в разделе «Проблема холодного старта».

        Так же, я думаю, в примере красных кед имеет смысл все товары, в т.ч. новые, экспертным путем пометить некими атрибутами (тип обуви, материал, цвет и т.д.) и сравнивать товары в т.ч. в разрезе данных атрибутов. В таком случае, даже не имея никакой статистики по новому товару, у нас будет статистика по атрибутам, которая уже со старта даст возможность формировать рекомендации, хоть и не такие точные.
          0
          Да, по этому принципу как раз работают Content-Based рекомендации. Товар новый, но все понимают как он соотносится с остальными товарами. Не обязательно даже экспертно, по фоткам можно много чего разметить, уж цвет то точно (как тут например).
          0
          Пока у нас нет искусственного интеллекта, способного делать обобщения без обучающей выборки, все завязано на данные. Если вы выходите на рынок с новым продуктом и хотите что-то спрогнозировать, то ни один алгоритм вам ничего не гарантирует. Т.е. вы конечно можете его использовать (если уверены что найденные моделью закономерности сохраняются при переходе train -> prod), но будете делать это на свой страх и риск.

          В целом, мне кажется это вопрос адекватной оценки рисков. Если от модели зависят ваши финансы, то на нее стоит полагаться только когда вы ее хорошо протестировали, в том числе в целевой среде.
          +1
          Насчет близости товаров. Можно построить вектор по характеристикам товаров, по одной размерности на фасет, и получить дескриптор, по которому искать соседей. Почему до сих пор нет сервиса, позволяющего этот дескриптор получить по любому товару с характеристиками? Любой интернет-магазин способен упорядочить значения фасетов: ведь все, что нужно сделать владельцу интернет-магазина, это расставить значения характеристик по оси, и выгрузить это в какой-то внешний сервис, который возвращает дескриптор, который сайт сохраняет к себе в базу, и по нему дает рекомендации о ближайших соседях. Альтернативно этот дескриптор может кидаться в другой сервис, который тупо возвращает набор айдишников товаров, близких к этому (при условии, что их дескрипторы тоже отправлялись, конечно). Дополнительно можно еще feature vector от картинки вычислять и обогащать.
            0
            Если я Вас правильно понял, то это описание алгоритма Content-Based фильтрации. Честно говоря, не особо слежу за готовыми решениями в этой области, но был уверен, что это много где реализовано. Во всяком случае функционал довольно базовый. Всякие ПО для интернет магазинов, системы индексированного поиска и прочее.
            0
            Зря вы картинки с обувью поставили. У обуви есть особенность: она может тупо не подойти (более того — скорее всего, так и будет, поиск «своей колодки» — обычное дело). Именно для обуви хотелось бы видеть в первую очередь классификацию «по анатомии», чтобы сразу выбирать только из подходящих моделей.
              +1
              Вы правы. Вообще идея интересная, я бы разделил на 2 подзадачи — одну, связанную с подбором оптимального размера одежды — тут и CV, и сенсоры, и вообще есть где развернуться. Но подходящий размер только половина дела, важно чтобы понравился цвет/фасон и прочее (кто-то любит носить посвободнее, кто-то наоборот). На этот вопрос как раз хорошо отвечают рекомендательные алгоритмы. Далее результаты можно объединить в единый pipeline рекомендаций.
              +2
              Отличный обзор. Жаль, не могу плюсануть.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое