03.06.2019       Выпуск 285 (03.06.2019 - 09.06.2019)       Статьи

Рекомендации в Okko: как заработать сотни миллионов, перемножив пару матриц

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

 

К счастью, у нас есть Rekko — система персональных рекомендаций, которая уже год успешно помогает пользователям Okko выбирать фильмы и сериалы из более чем десяти тысяч единиц контента. В статье я расскажу вам как она устроена с алгоритмической и технической точек зрения, как мы подходим к её разработке и как оцениваем результаты. Ну и про сами результаты годового A/B теста тоже расскажу.

Для начала немного истории. Okko начал своё существование в 2011 году как часть Йоты, запустившись под именем Yota Play.

Читать>>




Экспериментальная функция:

Ниже вы видите текст статьи по ссылке. По нему можно быстро понять ссылка достойна прочтения или нет

Просим обратить внимание, что текст по ссылке и здесь может не совпадать.

Rekko — персональные рекомендации в онлайн-кинотеатре Okko

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

К счастью, у нас есть Rekko — система персональных рекомендаций, которая уже год успешно помогает пользователям Okko выбирать фильмы и сериалы из более чем десяти тысяч единиц контента. В статье я расскажу вам как она устроена с алгоритмической и технической точек зрения, как мы подходим к её разработке и как оцениваем результаты. Ну и про сами результаты годового A/B теста тоже расскажу.

Для начала немного истории. Okko начал своё существование в 2011 году как часть Йоты, запустившись под именем Yota Play.

Старый интерфейс Yota Play

Уже в 2011 году пользователи с энтузиазмом воспринимали идею легального просмотра кино в интернете

Yota Play был уникальным для своего времени сервисом: он тесно интегрировался с социальными сетями и использовал информацию о просмотренных и оценённых друзьями фильмах во многих частях сервиса, в том числе и в рекомендациях.

Социальные рекомендации в Yota Play

В 2012 социальные рекомендации было решено дополнить алгоритмическими. Так появился «Оракул» — первая рекомендательная система онлайн-кинотеатра Okko. Вот несколько выдержек из его дизайн-документа:

Аналогичный подход использован и в реализованной системе персональных рекомендаций. Используется шкала уровней от “ничто” (пустота, отсутствие) до “всё” (полностью, максимально). В диапазоне [127..+127] 0 – является серединой или “нормой”. По такой шкале оценивается и степень симпатии к главному герою и субъективная цена товара и степень “красного” цвета. Например, размер вселенной оценивается значением +127 (по шкале габаритов), а темнота значением — 127 (по шкале интенсивности освещенности).

При выработке рекомендаций, важным является не только предыстория, но и характер конкретного пользователя. Персональный профиль также содержит 4-ре шкалы типов характеров (по К. Леонгарду – демонстративный, педантичный, застревающий, возбудимый).

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



Кадр из фильма «Страх и ненависть в Лас-Вегасе»

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

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

Архитектура «Оракула»

К середине 2013 года всех начало понемногу отпускать и было наконец-то решено проверить качество рекомендательной машины. Для этого специально обученный редактор заполнил основные разделы приложения и был запущен A/B тест: половина пользователей видела выдачу алгоритма, половина — выбор редактора.

Это сейчас мы с вами читаем статьи об очередных победах искуственного интеллекта и с ужасом представляем себе день, когда тот лишит нас работы. Тогда, в 2013, ситуация обстояла иначе: человек героически победил машину, создав ещё больше рабочих мест в отделе контента. «Оракул» выключили и больше никогда не включали. Вскоре исчезли и все социальные фишки, а Yota Play превратился в Okko.

Интерфейс онлайн-кинотеатра Okko сразу после переименования

Период с 2013 по 2016 год ознаменовался «зимой» искуственного интеллекта и тоталитарным правлением контентного отдела: персональных рекомендаций в сервисе не существовало.

К середине 2017 года стало понятно что так жить дальше нельзя. Успехи Netflix были на слуху у каждого и вся индустрия бурными темпами двигалась в сторону персонализации. Пользователей перестали интересовать «тупые» статичные сервисы, они уже начинали привыкать к «умным» интерфейсам, понимающим их с полуслова и предугадывающим все их желания.

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

По итогам полугодового A/B теста никаких статистически значимых отличий в контрольной и тестовых группах выявлено не было.

Результаты A/B теста с интеграцией сторонних поставщиков рекомендаций

Как раз к концу этого A/B теста я и пришёл в Okko, чтобы вместе с главой аналитики Михаилом Алексеевым (malekseev) начать делать сервис по-настоящему персональным. Менее чем через год к нам присоединился Данил Казаков (xaph), окончательно сформировав текущую команду.

Общие соображения

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

Комикс с сайта xkcd.com про машинное обучение

Главное этому соблазну не поддаваться. Задача научного сообщества — добиться максимального скора на протухших и синтетических датасетах — зачастую не совпадает с задачей бизнеса — заработать побольше денег, затратив при этом поменьше ресурсов.

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

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

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

Текущий дашборд Rekko, например, сравнивает контрольную и тестовую группу по более чем 50 метрикам, среди которых есть выручка, время пребывания в сервисе, время выбора фильма, количество просмотров по подписке, конверсия в покупку и автопродление и многие другие. И да, мы всё ещё храним небольшую группу пользователей, которые никогда не получали персональные рекомендации (простите).

О рекомендательных системах

Для начала небольшое введение в рекомендательные системы.

Задача рекомендательной системы состоит в том, чтобы для каждого пользователя$u \in U$по его истории взаимодействия с элементами$i \in I$построить отношение порядка на множестве всех элементов. Означает это вот что: какие бы два произвольных элемента мы не взяли, мы всегда сможем сказать, какой из них является более предпочтительным для пользователя, а какой менее.

Иллюстрация отношения порядка на множестве фильмов

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

Иллюстрация отображения множества фильмов на множество вещественных чисел

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

В идеальном случае нам потребуется целое семейство отношений порядка, зависящих от контекста. Если пользователь зашёл в коллекцию «Боевики», он скорее всего предпочтёт фильм «Разрушитель» фильму «Оскар», но в коллекции «Фильмы с Сильвестром Сталлоне» предпочтение вполне может быть обратным. Аналогичные примеры можно привести для дня недели, времени дня или устройства, с которого пользователь зашёл в сервис.

Иллюстрация отображения множества фильмов на множество вещественных чисел с учётом контекста

Традиционно все методы построения персональных рекомендаций делятся на три большие группы: коллаборативная фильтрация (collaborative filtering, CF), контентные модели (content models, CM) и гибридные модели, объединяющие первые два подхода.

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

Иллюстрация матрицы взаимодействия для методов коллаборативной фильтрации

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

Контентные модели — произвольные методы машинного обучения для решения задач классификации или регрессии, параметризованные некоторым набором параметров$\theta$. На вход они принимают признаки пользователя и признаки элемента, а выходом служит степень релевантности данного элемента данному пользователю. Обучаются такие модели не на взаимодействиях всех пользователей и всех элементов, как методы коллаборативной фильтрации, а лишь на отдельных прецедентах.

Иллюстрация контентных моделей

Такие модели, как правило, гораздо более точны, чем методы коллаборативной фильтрации, но сильно проигрывают им в скорости. Представьте, если у нас есть функция некоторого общего вида, принимающая на вход признаки пользователей и элементов, то её необходимо вызвать для каждой пары$(u, i), u \in U, i \in I$. В случае с тысячью пользователей и десятью тысячами элементов это уже миллион вызовов.

Гибридные модели объединяют достоинства обоих подходов, предлагая качественные рекомендации за приемлемое время.

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

Иллюстрация двухуровневой архитектуры

Такая архитектура имеет множество плюсов:

  1. Коллаборативная и контентная части не связаны между собой и могут обучаться отдельно с разной частотой;
  2. Качество всегда лучше, чем у коллаборативной модели отдельно;
  3. Скорость гораздо выше, чем у контентной модели отдельно;
  4. «Бесплатно» получаем вектора из коллаборативной модели, которые затем можно использовать для решения смежных задач.

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

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

В качестве контентной модели можно использовать вообще любой подход, от линейной регрессии до глубоких сеток.

Мы в Okko в данный момент остановились на комбинации матричной факторизации с WARP loss и градиентного бустинга над деревьями, о чём я сейчас подробно и расскажу.

Первый этап: отбор кандидатов

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

Иллюстрация матричного разложения

При этом, естественно, мы свободны в выборе критерия схожести имеющейся и восстанавливаемой матриц. Самый простой критерий — среднеквадратическое отклонение.

Пусть$p_u$— строка матрицы пользователей, соответствующая пользователю$u \in U$, а$q_i$— столбец матрицы элементов, соответствующий элементу$i \in I$. Тогда при перемножении матриц их произведение$\langle p_u , q_i \rangle$будет означать величину предполагаемого взаимодействия между данным пользователем и элементом. Посчитав теперь среднеквадратическое отклонение между этой величиной и априорно известным значением взаимодействия$r_{ui}$для всех пар взаимодействовавших пользователей и элементов$(u, i) \in T$, получим функцию потерь, которую можно минимизировать.

$\min \frac{1}{\lvert T \rvert} \sum_{(u, i) \in T} (r_{ui} - \langle p_u , q_i \rangle)^2$

Как правило, к ней ещё добавляют регуляризацию.

$\min \frac{1}{\lvert T \rvert} \sum_{(u, i) \in T} (r_{ui} - \langle p_u , q_i \rangle)^2 + \lambda ( \sum_u \lVert p_u \rVert^2 + \sum_i \lVert q_i \rVert^2 )$

Такая задача не выпукла и NP-сложна. Однако легко заметить, что при фиксировании одной из матриц задача превращается в линейную регрессию относительно второй матрицы, а значит, мы можем искать решение итеративно, попеременно замораживая то матрицу пользователей, то матрицу элементов. Такой подход называется Alternating Least Squares (ALS).

Главный плюс ALS — скорость и возможность лёгкого распараллеливания. За это его так любят в Яндекс.Дзене и Вконтакте, где и пользователи и элементы исчисляются десятками миллионов.

Однако если мы говорим об объёме данных, помещающимся на одной машине, ALS не выдерживает никакой критики. Главная его проблема — он оптимизирует не ту функцию потерь. Вспомните формулировку задачи построения рекомендательной системы. Мы хотим получить отношение порядка на множестве, а вместо этого оптимизируем среднеквадратическое отклонение.

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

Давайте посмотрим, что мы можем с этим сделать. В голове у пользователя все элементы, с которыми он провзаимодействовал, расположены в некотором порядке. Например, он точно знает, что «Интерстеллар» лучше, чем «Притяжение», «Притяжение» и «Чужой» одинаково хорошие фильмы, и все они чуть хуже, чем «Терминатор». При этом к фильмам, которые пользователь ещё не смотрел, он тоже испытывает некоторое отношение, причём ко всем одинаковое. Он может считать, что такие фильмы априори хуже тех фильмов, что он посмотрел. Или он может считать, что, например, «Прометей» — плохой фильм, и любой фильм, который он ещё не смотрел, будет лучше него.

Иллюстрация отношения порядка на множестве фильмов в голове пользователя

Представим, что по некоторым признакам поведения пользователя в сервисе мы умеем восстанавливать этот порядок, отображая элемент, с которым он провзаимодействовал, в целое число с помощью функции$\rho: U \times I \to \mathbb{Z}$. Множество всех фильмов, с которыми пользователь$u$провзаимодействовал, обозначим как$I_u$. Условимся, что$\rho(u, j) = 0$, если пользователь не взаимодействовал с фильмом$j$, то есть$j \notin I_u$. Таким образом, если пользователь посчитал фильм плохим, то$\rho(u, i) < 0$, а если хорошим, то$\rho(u, i) > 0$.

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

Теперь мы можем ввести ранк$rank: U \times I \to \mathbb{N}$.

$rank(u, i) = \sum_{ j \in I: \rho(u, j) < \rho(u, i)} \textrm{I} ( \langle p_u , q_i \rangle < 1 + \langle p_u , q_j \rangle )$

$\textrm{I}(x)$здесь обозначает индикаторную функцию и равна единице, если$x$верно и нулю иначе.

Давайте остановимся на минуту и подумаем, что такой ранк означает.

Зафиксируем пользователя$u$, это — какой-то конкретный пользователь, какой именно — нас не интересует. Соответственно и его вектор$p_u$окажется фиксированным.

Возьмём теперь любой фильм, который он посмотрел, например «Интерстеллар». В формуле это$i$. Далее найдём фильм, который пользователь считает хуже, чем «Интерстеллар». Мы можем выбирать из «Притяжение», «Чужой», «Прометей», либо любого фильма, который он ещё не смотрел.

Иллюстрация нарушения отношения порядка

Возьмём «Притяжение». В формуле это$j$. Теперь проверим, если взять вектор «Интерстеллар»$q_i$и домножить на вектор пользователя, будет ли результат больше, чем результат умножения вектора «Притяжение»$q_j$на тот же самый вектор пользователя. Для надёжности учтём зазор в единицу. Теперь сделаем это для «Чужого», для «Прометея» и для всех фильмов, которые пользователь ещё не посмотрел и просуммируем.

Получим количество фильмов, которые наша модель матричного разложения ошибочно ставит выше, чем «Интерстеллар». В идеальной модели$r(u, i)$будет равно нулю для кадого пользователя и каждого элемента, с которым он провзаимодействовал.

Теперь достаточно легко записать общую ошибку модели.

$L = \sum_{u \in U, i \in I_u} \phi (rank(u, i))$

$\phi: \mathbb{N} \to \mathbb{R}$— некоторая функция, переводящая натуральный ранк в вещественное число. От её выбора зависит то, какую часть верхушки списка элементов мы хотим оптимизировать. Хорошим выбором может служить функция, описанная ниже, однако в реальных вычислениях ради скорости её можно аппроксимировать логарифмом.

$\phi(x) = \sum_{i=1}^x \frac{1}{i}$

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

Здесь нам поможет небольшой трюк: вместо честного ранка будем считать его аппроксимацию. Для этого из элементов$j$таких, что$p(u, j) < p(u, i)$будем выбирать случайные и проверять, не нарушается ли отношение$\langle p_u , q_i \rangle < 1 + \langle p_u , q_j \rangle$. Если отношение не нарушалось$N - 1$раз и нарушилось на шаге$N$, то примем в качестве ранка элемента$i$

$rank(u, i) \approx \lfloor \frac{\lvert I \rvert - 1}{N} \rfloor$

где$\lvert I \rvert$— общее число элементов.

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

Такая функция потерь называется WARP и впервые она была описана в статье WSABIE: Scaling Up To Large Vocabulary Image Annotation. Мы её видоизменили, добавив произвольные целочисленные ранки и понятие нейтрального ранка для элементов, с которыми пользователь не взаимодействовал. На нашей задаче это дало прирост метрик примерно в 10%.

Открытым остаётся вопрос выбора$\rho(u, i)$. В Okko пользователь может провзаимодействовать с контентом следующим образом:

  1. Купить навсегда;
  2. Взять в аренду;
  3. Посмотреть по подписке (или бесплатно);
  4. Добавить в закладки;
  5. Поставить рейтинг от 0 до 10.

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

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

В итоге, в качестве$\rho(u, i)$мы используем степенную функцию, зависящую от относительного времени просмотра. Степень определяется типом потребления. Ниже приведены примеры графиков для различных типов потребления, построенные с некоторыми случайными гиперпараметрами.

Пример графиков ранка для различных типов потребления

При этом$\rho(u, i) = -c$, если пользователь оценил фильм ниже своей средней оценки и$\rho(u, i) = c$, если выше.

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

Второй этап: ранжирование

Имея матрицы пользователей и элементов, легко посчитать top-N рекомендаций для пользователя: достаточно умножить его вектор на матрицу элементов и отсортировать результат по убыванию. Если элементов слишком много, можно воспользоваться подходом из статьи Approximate nearest neighbor algorithm based on navigable small world graphs и делать это за логарифмическое время вместо линейного.

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

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

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

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

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

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

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

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

Иллюстрация деления данных на тренировочные и тестовое множества для двухуровневой модели

На первом тренировочном множестве мы обучим модель первого уровня и построим кандидатов. Из кандидатов важно исключить те элементы, с которыми пользователь взаимодействовал в этом множестве. Затем мы посмотрим, с какими из кандидатов пользователь взаимодействовал во втором тренировочном множестве. Назовём их positives, а остальных кандидатов negatives. Это и будет нашим обучающим множеством для контентной модели.

Иллюстрация формирования тренировочного множества для двухуровневой модели

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

Что дальше? Самое простое и очевидное решение — решить задачу бинарной классификации и затем отсортировать элементы по убыванию вероятности быть положительным примером. Но можно снова вспомнить постановку задачи построения рекомендательной системы, понять, что бинарная классификация — не та задача, которую мы решаем, и опять перейти к задаче ранжирования.

В XGBoost и LightGBM основной функцией потерь для задач ранжирования является LambdaMART. Если не вдаваться в детали, интуиция за ней достаточно проста. Если$f(x_i)$— выход модели для примера$x_i$, то вероятность того, что элемент$i$будет иметь ранк выше чем элемент$j$, будет равна

$P_{ij} = P(i \gt j) = \frac{1}{1 + \exp(f(x_j) - f(x_i))}.$

Функция потерь тогда может быть записана следующим образом.

$L = - Y_{ij} \log{P_{ij}} - (1 - Y_{ij}) \log{(1-P_{ij})}$

$Y_{ij}$здесь — истинная вероятность ранжирования. Мы определим её как 1 если$i \gt j$, 0 если$i \lt g$и 0.5 в случае$i = j$.

Двухуровневая модель даёт прирост метрик на 50% по сравнению с одноуровневой. Функция потерь ранжирования добавляет ещё 10%.

Бонус: похожие фильмы

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

Иллюстрация поиска похожих фильмов

Решение до безобразия простое: для каждого фильма мы берём его вектор и ищем к нему ближайшие по косинусной дистанции. На глаз выглядит вполне адекватно. Следующий уровень — добавить мета-информацию и использовать алгоритмы на графах.

Похожие фильмы до Rekko и с ним

Техническая реализация

Помимо алгоритмической части хочется рассказать немного и о реализации. Rekko состоит из трёх компонентов: lynch, rekko-tasks и rekko-service.

Lynch работает на одной мощной машине, периодически просыпается, подготавливает данные для микросервиса и складывает их в S3.

Микросервисы rekko-tasks и rekko-service находятся в продуктовой среде Okko рядом со всеми остальными микросервисами и базами данных. Первый из них постоянно мониторит S3 на предмет изменений, при наличии таковых скачивает их и складывает в продуктовые базы. Второй микросервис использует эти предпосчитанные результаты для того, чтобы в реальном времени отвечать на запросы пользователей и рассчитывать их рекомендации.

Архитектура сервиса

Микросервисы написаны на Python с использованием falcon, gunicorn и gevent и не представляют собой ничего интересного за исключением бизнес-логики. Как и все остальные микросервисы продуктовой среды Okko, они закрыты балансировщиком.

Lynch же гораздо интереснее.

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

  1. Загрузить новые данные, появившиеся с момента последнего пересчёта;
  2. Обработать их;
  3. Обучить матричную факторизацию;
  4. Построить кандидатов;
  5. Переранжировать кандидатов;
  6. Применить бизнес-правила;
  7. Выгрузить.

Вроде звучит не страшно, можно вынести каждую часть в отдельную функцию и просто вызвать их по очереди:

data = extract_data()
data = transform_data(data)

mf_model = train_mf_model(data)
candidates = build_candidates(mf_model)

predictions = build_predictions(content_model, candidates)
upload_predictions(predictions)

Ну всё, отлично поработали, расходимся? Не совсем. А что, если вся эта простыня где-то упадёт? Ну например из-за нехватки памяти. Придётся перезапускать всё заново, даже если мы уже потратили пару часов на то, чтобы обучить модель и построить кандидатов.

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

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

Иллюстрация зависимых задач

Уже неплохо. Но в реальности все необходимые вычисления едва ли будут описываться списком. Обучение матричной факторизации потребует не только данных о транзакциях, но ещё и об оценках пользователей, построение кандидатов потребует списка запомненных фильмов, чтобы исключить их, вычисление похожих фильмов потребует обученной матричной факторизации и мета-информации из каталога и так далее. Наши задачи выстраиваются уже не в односвязный список, а в ориентированный граф без циклов (Directed Acyclic Graph, DAG).

Иллюстрация DAG

DAG — крайне популярная структура для организации вычислений. Существуют два основных фреймворка для построения DAG: Airflow и Luigi. Мы в Okko остановились на последнем. Luigi разработан в Spotify, активно развивается, полностью написан на питоне, легко расширяется и позволяет очень гибко организовывать вычисления.

Задача в Luigi определяется классом, наследуемым от luigi.Task и реализующим три обязательных метода: requires, output и run. Вот так выглядит типичная задача:

# RekkoTask расширяет luigi.Task дополнительной функциональностью
class DoSomething(RekkoTask):
    # Параметры задачи
    date: datetime.datetime = luigi.DateSecondParameter()

    # Потребляемые ресурсы
    resources = {
        'cores': 4,
        'aws': 1,
        'memory': 8
    }

    # Namespace задачи для удобной группировки
    task_namespace = 'Transform'

    def requires(self):
        # Задачи, от которых данная зависит и чьи результаты ей требуются
        return {
            'data': DownloadData(date=self.date),
            'element_mapping': MakeElementMapping(date=self.date)
        }

    def output(self):
        # Куда данная задача запишет результат
        # Это может быть не только локальный файл, но и база данных и файл на s3
        return luigi.LocalTarget(
            os.path.join(self.data_root, f'some_output_{self.date}.msg'),
            format=luigi.format.Nop
        )

    def run(self):
        # Основной метод, где происходит вся работа

        # Загрузка данных из зависимых задач
        with self.input()['data'].open('r') as f:
            data = pd.read_csv(f)

        with self.input()['element_mapping'].open('r') as f:
            element_mapping = json.load(f)

        # Обрабатываем входные данные и считаем результат
        result = ...

        # Можем записать логи для отправки их затем в Splunk
        self.log(
            n_results=len(result)
        )

        # Атомарно записываем результат
        with self.output().open('w') as f:
            result.to_msgpack(f)

Luigi сам проследит за тем, чтобы задачи выполнились в нужном порядке без превышения потребления доступных ресурсов. Если задачи могут выполняться параллельно, он запустит их параллельно, максимизируя утилизацию CPU и минимизируя общее время исполнения. Если какая-то задача завершится с ошибкой, он перезапустит её некоторое количество раз и в случае неудачи сообщит нам. При этом все задачи, которые могут быть выполнены, будут выполнены. Это означает, например, что ошибка в задаче ранжирования кандидатов не помешает посчитать и выгрузить список похожих фильмов.

В данный момент Lynch состоит из 47 уникальных задач, производящих около 100 своих экземпляров. Часть из них занята непосредственной работой, часть — подсчётом метрик и отправкой их в наш BI инструмент Splunk. Основные статистики и отчёты о своей работе Lynch также периодически присылает нам в телеграмм. Об ошибках тоже пишет, но уже в личку.

Мониторинг, сплиты и результаты

Первое правило Data Science: никому не рассказывать о зарплатах в Data Science. Второе правило Data Science: то, что нельзя измерить, нельзя улучшить.

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

Для работающих в продакшене моделей мы тоже считаем метрики, но уже подневные. Такие метрики достаточно волатильны, но по ним можно будет сказать, если модель вдруг по какой-то причине деградирует. При выводе в прод новой модели можно оставить её на неделю работать «вхолостую» и следить, чтобы метрики не проседали. После этого можно включить её для части пользователей, запустить A/B тест и следить уже за бизнес-метриками.

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

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

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

  1. Выручка по транзакционной и подписной моделям потребления (TVOD / SVOD revenue);
  2. Средняя выручка на посетителя (average revenue per visitor, ARPV);
  3. Средний чек (average price per purchase, APPP);
  4. Среднее число покупок на пользователя (average purchases per user, APPU);
  5. Конверсия в покупку (CR to purchase);
  6. Конверсия в просмотр по подписке (CR to watch);
  7. Конверсия в пробный период (CR to trial).

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

Вот так может выглядеть дашборд сравнения нескольких моделей:

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

Как я уже говорил в начале, мы сравниваем не только модели между собой, но и группу пользователей с рекомендациями против группы пользователей без рекомендаций. Это позволяет нам оценивать чистый эффект от внедрения Rekko и понимать, где мы в данный момент находимся и какой запас для усовершенствования ещё остаётся. Согласно этому A/B тесту на данный момент мы имеем:

  • ARPV +3.5%
  • ARPV с учётом маржинальности +5%
  • APPU +4.3%
  • CR to trial +2.6%
  • CR to watch +2.5%
  • APPP -1%

Фильмы в онлайн-кинотеатре условно можно разделить на две группы: новинки и старый контент. Новинки мы уже умеем хорошо продавать. Основное предназначение персональных рекомендаций — достать из каталога релевантный пользователям старый контент. Это ведёт к увеличению числа покупок и проседанию среднего чека, так как такой контент, естественно, дешевле. Но у такого контента ещё и высокая маржинальность, что компенсирует проседание чека и даёт прирост в выручке в пять процентов.

Более релевантный подписной контент привёл к увеличению конверсии в пробный период и смотрению по подписке.

Rekko Challenge

С 18 февраля по 18 апреля 2019 года мы совместно с платформой Boosters провели соревнование Rekko Challenge, где предложили участникам построить рекомендательную систему на основе анонимизированных продуктовых данных.

Таблица победителей Rekko Challenge

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

Евгений Смирнов, занявший в соревновании второе место, написал статью, где рассказал о своём решении.

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

Заключение

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

В будущих статьях мы расскажем вам ещё больше о внутренней кухне Okko, поэтому не забывайте подписываться и ставить лайки.






Разместим вашу рекламу

Пиши: mail@pythondigest.ru

Нашли опечатку?

Выделите фрагмент и отправьте нажатием Ctrl+Enter.

Система Orphus