Привет, Хабр!

На связи участница профессионального сообщества NTA Ульянова Дарья.

Рекомендательные системы стали нормой, все к ним привыкли точно также как и к быстрому Wi‑Fi, навигатору или беспроводным наушникам. Они просто делают жизнь немного проще, и всем от этого выгода: пользователям, которым не приходится лишний раз искать на маркетплейсе любимую зубную пасту или корм для собаки; сервису, которому выгодно, чтобы пользователи заказывали больше.

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

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

Рекомендательные системы: quick overview

Но прежде всего пара слов о самих рекомендательных системах.

Рекомендательные системы (Recommender Systems, RecSys) — это сложные алгоритмы, созданные для релевантных рекомендаций продуктов/услуг пользователям.

Рекомендательные системы делятся на две большие группы: неперсонализированные и персонализированные.

Первые основываются на популярности товаров или их новизне.

Вторая группа намного обширней: с ней мы сталкиваемся, когда авторизируемся на сервисах или заходим под одним и тем же ip‑адресом несколько раз на сайт. В ней рекомендации строятся на основе нашей предыдущей деятельности на сайте или сервисе и оставленной там информации.

Персонализированные RecSys состоят из трех разных подходов к рекомендациям:

1. Контент основанные системы (Content based RecSys). Эта техника представляет собой алгоритм, зависящий от предметной области, в нем большое внимание уделяется анализу характеристик (атрибутов) элементов для создания прогнозов. Рекомендации строятся на основе профилей пользователей с использованием функций, извлеченных из ранее оцененных элементов; в основном пользователю рекомендуются элементы с предсказанной положительной оценкой. Техника используется в случаях, когда необходимо рекомендовать музыку, документы, новости или веб‑страницы, похожие на какую‑то определенную. Ярким примером прогноза на основе контента является рекомендация треков, похожих по звучанию или содержанию на какой‑то другой, такая функция есть во многих музыкальных сервисах.

2. Коллаборативная фильтрация (Collaborative Filtering) — основное направление рекомендательных систем. Использует историю, с чем взаимодействовали пользователи, для построения прогноза другим пользователям. Это происходит следующим образом: создается матрица предпочтений пользователей в отношении элементов, далее подбираются пользователи с соответствующими интересами (соседи), путем вычисления сходства между их профилями, чтобы делать рекомендации. Используются в случае сложных предсказаний, когда сложно выявить схожесть между элементами, например, в кино‑рекомендациях или при рекомендации музыки в целом.

   Здесь, в свою очередь, есть два подхода:

   • Memory‑based подход. Использует различные алгоритмы при объединении предпочтений соседей для создания предсказаний. Предсказания строятся на основе схожести пользователей (user‑based) или схожести предметов (item‑based). В первом случае, ищутся пользователи с похожими предпочтениями и товары, которые им понравились, затем рекомендуется первому пользователю то, что понравилось другому, и наоборот. Во втором случае вычисляется сходство между товарами, а не юзерами. Item‑based подход считается более стабильным и показывает лучшие результаты, так как сходство товаров статично, а вкусы юзеров могут быстро меняться.

   • Model‑based подход. Модель обучается на основе предпочтений соседей и далее делает рекомендации. Процесс обучения осуществляется при помощи машинного обучения или data mining.

3. Гибридные системы. Это микс методов коллаборативной фильтрации и рекомендаций на основе контента для повышения точности и производительности рекомендательных систем.

Есть ещё одна классификация рекомендательных систем: онлайн и оффлайн.

Онлайн отличаются от оффлайн тем, что их основная задача «поймать» изменения популярности определенных товаров. Данных в таком случае недостаточно, чтобы была возможность «поймать» такие изменения методами коллаборативной фильтрации, поэтому онлайн методы менее персонализированы из‑за недостатка релевантных персональных данных.

Измерение качества рекомендаций

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

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

1. Разбиваем выборку сессий на обучение и тест.

2. Оптимизируем оффлайн-метрику качества на обучении.

3. Оцениваем качество на тесте и выбираем модель.

4. Внедряем модель в рекомендательный сервис.

5. Проводим AB-тестирование и измеряем онлайн-метрику. Подробнее про AB-тестирование: можно почитать здесь.

Онлайн‑ и оффлайн‑метрики могут быть слабо связаны, поэтому чтобы улучшить онлайн‑точность нужно оптимизировать разные аспекты качества оффлайн метрик.

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

Оффлайн-метрики

Начну изучение оффлайн‑метрик оценки recsys с RMSE.

Root Mean Squared Error (RMSE) — точность предсказаний рейтингов. Формула выглядит следующим образом:

где u — конкретный user/пользователь/клиент; i‑ конкретный item/предмет/товар; r_ui— оценка пользователем u товара i; ȓ_ui— предсказанная оценка пользователем u товара i.

Данная метрика имеет особое место в истории развития рекомендательных систем. Именно RMSE использовался для измерения качества рекомендаций в конкурсе от Netflix.

Однако точность предсказаний не гарантирует хороших рекомендаций. В данном случае предсказанные ȓ_ui для каждого пользователя ранжируются в порядке убывания, и ему предлагается ТОП-10 или ТОП-20, а остальное откидывается, что не целесообразно с точки зрения вычислений.

Более адекватные метрики качества рекомендаций: precision@k, recall@k и некоторые меры качества ранжирования MAP@k, NDCG@k рассмотрю дальше.

Precision@k — точность (доля релевантных среди найденных) первых k рекомендаций для u.

где R_u(k) ϵ I — первые k предсказаний для u; L_u ϵ I — истинные предпочтения u.

Recall@k — полнота (доля найденных среди релевантных) первых k рекомендаций для u.

Mean Average Precision for the first k recommendations (MAP@k) — одна из самых используемых метрик ранжирования. На русский перевод названия формулы звучит очень странно, постараюсь пояснить формулу, начиная с конца:

1. Preсision@k – точность первых k рекомендаций:

где y_j— релевантность: если j элемент предсказан верно, y_j = 1, иначе y_j = 0.

2. Average Precision@k — средний Preсision@k по позициям верно предсказанных элементов:

3. MAP@k – усредненное по всем users ap@k:

Пример ниже покажет более наглядно вычисление MAP@k.

Normalized Discounted Cumulative Gain for the first k recommendations (NDCG@k) — тоже популярная метрика ранжирования. Начну, как и с MAP@k с конца формулы:

1. Discounted Cumulative Gain@k — взвешенная сумма выигрышей:

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

2. Normalized Discounted Cumulative Gain@k — нормированная взвешенная сумма выигрышей:

где maxDCG@k– это DCG@k при идеальном ранжировании.

Чтобы рекомендательная система не была тривиальной и у пользователей создавалось впечатления, что их мысли читают, recsys должна учитывать множество критериев, ниже представлены самые популярные из них:

• "Разнообразие (diversity) – число рекомендаций из разных категорий или степень различия рекомендаций между сессиями. Пользователь должен видеть различный контент/товары, чтобы не чувствовать себя примитивным.
  Есть несколько способов введения разнообразий, здесь представлю формулу совокупного разнообразия (aggregate diversity) recsys — общее количество отдельных элементов, рекомендованных всем пользователям:
  

где P_H(u)‑ множество элементов с высокой оценкой пользователя, а Rec(u) — множество элементов, рекомендованных пользователю.

• Новизна (novelty) – сколько среди рекомендаций новых для пользователя.

Есть несколько способов рассчитать новизну, рассмотрю способ вычисления новизны по популярности. Новизна по популярности EPC(Expected Popularity Complement) измеряет возможность recsys рекомендовать элементы из длинного хвоста.

А вот и формула:

где rel(u,i_r)– релевантность элемента i_r (элемент, расположенный в ранжированном списке на r позиции из N возможных) для пользователя u ; (1 – pop(i_r)) – непопулярность элемента i_r; pop(i_r) – популярность считается как отношение рейтинга i_r на максимальный рейтинг элемента из множества  всех доступных элементов I.

• Покрытие (coverage) — доля объектов, которые хотя бы раз побывали среди рекомендованных. Бизнес в первую очередь бизнес, его задача продать товар/услугу, поэтому рекомендательная система должна рекомендовать все товары.
  Расчет покрытия зависит от вида конкретной задачи. Основная формула выглядит следующим образом:

где I_p— множество рекомендованных элементов, I — множество всех доступных элементов.

Покрытие каталога, например, можно рассчитать по формуле:

где I^j_L — множество рекомендованных элементов из списка L, возвращаемых за j‑ую рекомендацию; N — общее количество рекомендаций за рассматриваемый промежуток времени, I — множество всех доступных элементов.

• Догадливость (serendipity) – это то, о чем я упоминала ранее, способность угадывать спонтанные нетривиальные предпочтения пользователей.

 Догадливость можно измерить при помощи формулы:

где RS_i— элемент, принадлежащий множеству неожиданных рекомендаций UNEXP; u(RS_i) — полезность элемента u(RS_i) = 1, если RS_i полезен пользователю, иначе u(RS_i) = 0); N — общее количество рекомендаций за рассматриваемый промежуток времени.

Множество UNEXP = RS\PM, RS — рекомендации от recsys, PM — рекомендации от примитивной модели предсказаний.

Рекомендательная система должна учитывать все эти факторы при формировании предложений, поэтому на оценку recsys они тоже должны влиять. Можно оптимизировать линейную комбинацию критериев или оптимизировать один критерий при ограничении остальных.

Бизнес-метрики оценки успешности рекомендательных систем

Как измерить прибыльность рекомендательной системы для бизнеса? Как понять, что трата денег на ее разработку не была зря?

Эффективность и ценность рекомендательной системы для бизнеса зависит от различных факторов, включая область ее применения и бизнес‑модель компании. Например, компании, которые в основном получают прибыль от рекламы: онлайн издания или YouTube, которым выгодней, чтобы пользователь провел на их сервисе как можно больше времени, поэтому время сеанса пользователя в таком случае тоже может быть информативной метрикой оценки качества рекомендательной системы. В e‑commerce ключевым показателем эффективности recsys может быть прибыль и доля в ней покупок рекомендованных товаров.

Авторы статьи «Measuring the Business Value of Recommender Systems» выделяют 5 универсальных подходов для измерения влияния рекомендательных систем на бизнес, которые представлены ниже.

Ниже в таблице отражены основные комментарии к каждому подходу. Повторюсь: данные показатели можно измерить при помощи AB-тестирования.

Заключение

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