Хабрахабр

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

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

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

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

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

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

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

Отзывы пользователей о стоимости контента в онлайн-кинотеатре

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда при перемножении матриц их произведение $\langle p_u , q_i \rangle$ будет означать величину предполагаемого взаимодействия между данным пользователем и элементом. Пусть $p_u$ — строка матрицы пользователей, соответствующая пользователю $u \in U$, а $q_i$ — столбец матрицы элементов, соответствующий элементу $i \in I$. Посчитав теперь среднеквадратическое отклонение между этой величиной и априорно известным значением взаимодействия $r_$ для всех пар взаимодействовавших пользователей и элементов $(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 не выдерживает никакой критики. Мы хотим получить отношение порядка на множестве, а вместо этого оптимизируем среднеквадратическое отклонение. Вспомните формулировку задачи построения рекомендательной системы.

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

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

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

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

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

Теперь мы можем ввести ранк $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$ верно и нулю иначе.

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

Соответственно и его вектор $p_u$ окажется фиксированным. Зафиксируем пользователя $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%.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: Airflow и Luigi. DAG — крайне популярная структура для организации вычислений. Luigi разработан в Spotify, активно развивается, полностью написан на питоне, легко расширяется и позволяет очень гибко организовывать вычисления. Мы в Okko остановились на последнем.

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

# 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)

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

Часть из них занята непосредственной работой, часть — подсчётом метрик и отправкой их в наш BI инструмент Splunk. В данный момент Lynch состоит из 47 уникальных задач, производящих около 100 своих экземпляров. Об ошибках тоже пишет, но уже в личку. Основные статистики и отчёты о своей работе 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. Ожидаемо в топе оказались участники, построившие двухуровневую систему, похожую на нашу. А участник с восьмого места сумел забраться на него с помощью лишь моделей коллаборативной фильтрации.

Евгений Смирнов, занявший в соревновании второе место, выступил с докладом на Data Fest 6, где подробно рассказал о своём решении.

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

Заключение

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

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

Показать больше

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

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

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

Кнопка «Наверх»