Не так давно на платформе Boosters прошел контест рекомендательных систем от онлайн-кинотеатра Okko — Rekko Challenge 2019. Для меня это был первый опыт участия в соревновании с лидербордом (ранее пробовал силы только в хакатоне). Задача интересная и знакома мне из практики, призовой фонд есть, а значит, был смысл участвовать. В итоге я занял 14 место, за что организаторы выдали памятную футболку. Приятно. Спасибо.

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

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

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

Постановка задачи

Подробнее о задаче и данных можно почитать в статье организаторов. TL;DR здесь я опишу необходимый минимум для понимания контекста.

В датасете чуть более десяти тысяч фильмов с анонимизированными атрибутами. В качестве матриц взаимодействия user-item доступны следующие варианты:

• транзакции — содержит факты покупки пользователями контента/ взятия в аренду/ просмотра по подписке;
• рейтинги — оценки фильмов пользователями;
• закладки — событие добавления фильма в закладки.

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

$$

Контент же имел следующий набор атрибутов:



Про них можно подробно почитать в статье организаторов, но хочется сразу уделить внимание тому, что бросилось в глаза: параметр «attributes». В нем был мешок категориальных атрибутов с кардинальностью в ~36 тысяч. В среднем было по 15 значений на фильм. На первый взгляд в этих значениях зашифрованы как раз самые основные атрибуты, описывающие контент: актеры, режиссеры, страна, подписки или коллекции, к которым принадлежит фильм.

Необходимо предсказать 20 фильмов, которые тестовые пользователи посмотрят в следующие два месяца. Тестовые пользователи — это 50 тысяч из всех 500 тысяч пользователей. На лидерборде они поделены пополам: по 25 тысяч в public/private.

Метрика

В качестве метрики организаторы выбрали Mean Normalize Average Precision на 20 элементах (MNAP@20). Основное отличие от обычного MAP в том, что для пользователей, не посмотревших 20 фильмов в тестовом периоде, нормирование происходит не на k, а на фактическое значение просмотренных фильмов.



Прочитать подробнее и посмотреть код на Cython можно здесь.

Валидация

Приступаем к решению задачи. Прежде всего надо было решить на чем валидироваться. Так как предсказывать нам надо фильмы в будущем, то делать простое разбиение по пользователям мы не можем. Из-за того, что время анонимизировано, пришлось для начала хотя бы примерно его расшифровать. Для этого я взял несколько пользователей, составил график по транзакциям и выявил некую сезонность. Было предположено, что она ежедневная, а зная разницу во времени между сутками, мы можем посчитать, за какой период были выгружены данные. Оказалось, что это были транзакции за 6 месяцев. Позже это подтвердилось в телеграм-канале, где происходило обсуждение контеста.



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

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



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

Попытка деанонимизации данных

Для начала я решил попробовать деанонимизировать все фильмы, чтобы:

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

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

Первым делом я решил распарсить сайт Okko и вытащить оттуда все фильмы вместе с их свойствами (рейтинг, продолжительность, возрастные ограничения и другие). Ну как распарсить — все оказалось достаточно просто, в данном случае можно было воспользоваться API:



Зайдя в каталог и выбрав конкретный жанр или подписку нужно было всего лишь зайти в любой из элементов. В ответе на запрос выше вываливается весь массив фильмов в жанре/подписке со всеми атрибутами. Очень удобно :)


Осталось пройтись по всем жанрам, распарсить JSON, а затем разрешить дубликаты, так как один фильм может принадлежать нескольким жанрам/подпискам.

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

«Дело в шляпе, — подумал я, — осталось только смержить». «Дело — шляпа», — понял я на следующий день: данные не сопоставлялись абсолютно. Об этом ниже.

Во-первых, размер каталога существенно отличался: в датасете — 10200, собрал с сайта — 8870. Это следовало из историчности датасета: было выкачано лишь то, что на сайте есть сейчас, а данные конкурса — за 2018 год. Какие-то из фильмов уже стали недоступны. Упс.

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

feature5 — возрастное ограничение. Понять это было достаточно легко. Кардинальность признака — 5 уникальных float значений и «-1». Среди собранных данных был найден атрибут «ageAccessType» как раз с кардинальностью 5. Маппинг выглядел следующим образом:

catalogue.age_rating = catalogue.age_rating.map({0: 0, 0.4496666915: 6
0.5927161087: 12
0.6547073468: 16
0.6804096966000001: 18})

feature2 — преобразованный рейтинг фильма с кинопоиска. Изначально на этапе EDA идею, что мы имеем дело с рейтингом, подала корреляция параметра с общим количеством просмотров. Впоследствии уверенности в том, что это рейтинг именно с кинопоиска подтвердило наличие параметра «kinopoiskRating» в данных сайта.

Еще на шаг ближе к матчингу! Теперь осталось найти способ обратного преобразования для представленного в анонимизированном виде параметра feature2.

Вот как выглядит распределение значений в feature2:



А так распределение значений параметра kinopoiskRating:



Когда я показал эти изображения коллеге Саше, он сразу увидел, что это степень тройки. Тройки у математиков не в почете, а вот число Pi очень даже. В итоге, получилось так:



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

Аппроксимировать, кстати, не самое подходящее слово. Нужно решение с ошибкой, практически равной нулю. Точность в собранных данных — 2 знака после разделителя. Если учесть, что фильмов с рейтингом 6.xx достаточно много и имеются фильмы с одинаковым рейтингом, то за precision здесь стоит побороться.

Что же еще можно попробовать? Можно опереться на минимальное и максимальное значение и воспользоваться MinMaxScaler, но ненадежность этого метода сразу вызывает сомнения. Напомню, что количество фильмов изначально не сошлось, и наш датасет — исторический, а на сайте — текущее состояние. Т.е. нет гарантий, что фильмы с минимальным и максимальным рейтингом в обеих группах идентичны (так и оказалось: у них было различное возрастное ограничение, и длительность не сходилась от слова «совсем»), как нет и понимания того, как часто OKKO обновляет у себя в API ежедневно меняющийся рейтинг кинопоиска.

Так стало понятно, что мне нужны еще кандидаты атрибутов для сопоставления.

Что еще есть интересного?

feature1 — какая-то дата. По идее, для дат организаторы обещали сохранение раprecisionсстояний, что подразумевало линейную функцию. В общем, преобразование должно было быть идентичным атрибуту tsдля матриц взаимодействий. Если посмотреть на распределение фильмов по feature_1…



… то сразу отметается гипотеза даты выхода фильма. Интуиция подсказывает — количество выпускаемых индустрией фильмов должно расти со временем. Это подтверждается чуть ниже.

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







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

Решение

1. Простые модели

Осознав, что не все так просто, я принялся смиренно работать с тем, что есть. Для начала, хотелось начать с простого. Я попробовал несколько часто используемых в индустрии решений, а именно: коллаборативную фильтрацию (в нашем случае item-based) и факторизацию матриц.

В сообществе широко используется пара подходящих для этих задач библиотек на python: implicit и LightFM. Первая умеет факторизацию на основе ALS, а также Nearest Neighbour Collaborative Filtering с несколькими вариантами предобработки item-item матрицы. У второй два отличительных фактора:

• Факторизация основана на SGD, что дает возможность использовать функции потерь на основе сэмплирования, в том числе WARP.
• Использует гибридный подход, соединяя в модели информацию об атрибутах пользователя и айтемов таким образом, что латентный вектор пользователя — сумма латентных векторов его атрибутов. И аналогично для айтемов. Этот подход становится чрезвычайно удобным при наличии проблемы холодного старта для пользователя/айтема.

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

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

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

2. Привет бустингу

Что может быть лучше, чем одна модель? Правильно: несколько моделей.

Поэтому следующим вариантом стало ансамблирование или, в контексте рекомендаций, ранжирующая модель второго уровня. В качестве подхода я взял эту статью от ребят из Avito. Вроде бы готовил строго по рецепту, периодически помешивая и приправляя атрибутами фильмов. Единственным отклонением было количество кандидатов: я брал топ-200 из LightFM, т.к. при 500 000 пользователей большее количество просто не помещалось в память.

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

После нескольких дней экспериментов пришло осознание, что ничего не работает и ничего не заработает само. Или я не умею это готовить (спойлер: правильный второй ответ). Что же я делаю не так? На ум пришли две причины:

• С одной стороны брать топ-200 из модели первого уровня здраво с точки зрения генерации «hard negative» сэмплов, т.е. тех фильмов, что также релевантны для пользователя, но не просмотрены им. С другой стороны, некоторые из этих фильмов могут быть просмотрены в тестовом периоде, а мы подаем эти примеры как негативные. Далее я решил снизить риски влияния этого факта, перепроверив гипотезу следующим экспериментом: взял для обучающей выборки все позитивные примеры + случайные. Скор на тестовой выборке не улучшился. Тут необходимо уточнить, что в семплировании на тесте все также были топ-предсказания из модели первого уровня, ибо на лидерборде никто не скажет мне все позитивные примеры.
• Из 10 200 фильмов, доступных в каталоге, какие-либо взаимодействия совершались лишь с 8 296 фильмов. Еще почти 2 000 фильмов были лишены внимания пользователей, отчасти потому что были недоступны для покупки/аренды/в рамках подписки. Ребята в чате спрашивали, могут ли недоступные фильмы стать доступными в тестовом периоде. Ответ был положительный. Выкидывать их однозначно нельзя. Таким образом, я предположил, что еще почти 2 000 фильмов будут доступны в ближайшие 2 месяца. Иначе зачем закидывать их в датасет?

3. Нейроночки

Из предыдущего пункта напрашивался вопрос: как мы можем работать с фильмами, по которым еще совсем нет взаимодействий? Да, вспоминаем item features в LightFM, но как помним, они не зашли. Что еще? Нейронки!

В арсенале open source есть пара достаточно популярных высокоуровневых библиотек для работы с рекомендательными системами: Spotlight от Maciej Kula (автора LightFM) и TensorRec. У первого под капотом PyTorch, у второго — Tensorflow.

Spotlight умеет выполнять факторизацию на implicit/explicit-датасетах нейронками и sequence модели. При этом в факторизации «из коробки» нет возможности добавить user/item-фичи, поэтому бросаем.

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

• representation graph — способ преобразования (его можно задать различным для user/item) входных данных в embedding, на основе которого будут происходить расчеты в prediction graph. Выбор состоит из слоев с различными вариантами активаций. Также есть возможность воспользоваться абстрактным классом и воткнуть кастомное преобразование, состоящее из последовательности слоев keras.
• prediction graph позволяет выбрать операцию в конце: любимый dot product, euclidean и cosine distance.
• loss — тоже есть, из чего выбрать. Порадовала имплементация WMRB (по сути тот же WARP, только умеет обучаться батчами и распределенно)

Самое главное, что TensorRec как раз и умеет работать с контекстными фичами, да и вообще автор признается, что изначально вдохновился идеей LightFM. Что ж, посмотрим. Берем взаимодействия (только транзакции) и item features.

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

Помимо этого, была еще пара неудобств, с которыми пришлось столкнуться:

1. От изменения флага verbose у метода fit не менялось ничего и никаких вам callback’ов не предусмотрено. Пришлось написать функцию, которая внутри делала обучение одной эпохи, используя метод fit_partial, а далее прогоняла валидацию для train и test (в обоих случаях использовались сэмплы для ускорения процесса).
2. В целом, автор фреймворка большой молодец и везде утилизирует tf.SparseTensor. Однако стоит понимать, что в качестве prediction, в том числе и для валидации, вы получаете результат в dense виде вектора с длиной n_items для каждого юзера. Из этого следует два совета: сделайте цикл для формирования предсказаний батчами (метод библиотеки такого параметра не имеет) с фильтрацией top-k и готовьте планки с оперативной памятью.

В конечном итоге на лучшем варианте конфигурации удалось выжать 0.02869 на моей тестовой выборке. На LB было что-то похожее.

Ну а на что я надеялся? Что добавление нелинейности в item features даст двукратный прирост в метрике? Наивно.

4. Бек ту таск

Так, подождите. Кажется, я снова упоролся в жонглирование нейронками. Какую гипотезу я вообще хотел проверить, когда взялся за это дело? Гипотеза звучала так: «В последующие 2 месяца отложенной выборки на лидерборде встретятся почти 2 000 новых фильмов. Часть из них заберет на себя увесистую долю просмотров».

Так можно проверить это в 2 шага:

1. Неплохо бы посмотреть, сколько у нас добавилось фильмов в честно отколотом нами тестовом периоде относительно train. Если брать только просмотры, то «новых» фильмов всего 240(!). Гипотеза сразу пошатнулась. Кажется, что закупка нового контента не может отличаться на такое кол-во от периода к периоду.
2. Добиваем. У нас есть возможность обучить модель использовать только представление, основанное на item features (в LightFM, например, это делается по умолчанию, если мы заранее не застэкали матрицу атрибутов с identity матрицей). Далее для инфренеса мы можем подать в эту модель только(!) наши недоступные и не встречающиеся ранее фильмы. Из этих результатов мы делаем сабмит и получим 0.0000136.

Бинго! Значит, что можно перестать «выжимать» семантику из атрибутов фильмов. Кстати, впоследствии, на DataFest ребята из ОККО рассказали, что большинство из недоступного контента были просто какие-то старые фильмы.

Нужно пробовать что-то новое, а новое — хорошо забытое старое. В нашем случае не совсем забытое, а то, что было пару дней назад. Коллаборативная фильтрация?

5. Тюним бейзлайн

Чем можно помочь бейзлайну с CF?

Идея №1

В интернетах я нашел презентацию про использование likelihood ratio test с целью фильтрации незначительных фильмов.

Ниже оставлю свой код на python для расчета LLR score, который пришлось написать на коленке для теста этой идеи.


В итоге получившуюся матрицу можно использовать как маску, чтобы оставить только наиболее значимые взаимодействия и здесь есть два варианта: использовать threshold или оставлять top-k элементов с наивысшим значением. Таким же образом используется объединение нескольких влияний на покупку в один скор для ранжирования айтемов, иными словами тест показывает насколько важно, к примеру, добавление в избранное относительно возможной конвертации в покупку. Выглядит многообещающе, но использование показало, что фильтрация с использованием LLR score дает совсем миниатюрный прирост, а объединение нескольких скоров только ухудшает результат. Видимо, способ не под эти данные. Из плюсов могу отметить только то, что разбираясь с тем, как реализовать эту идею, мне пришлось покопаться у implicit под капотом.

Пример применения этой кастомной логики в implicit оставлю под катом.


Идея №2

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

1. Пользователи, которые смотрят в сервисе в основном новинки
2. «Досматривающие». То есть те, кто пришли сравнительно недавно и могут смотреть ранее популярные фильмы.

Таким образом, можно разделить коллаборативную составляющую на две разных группы автоматически. Для этого я выдумал функцию, которая ставила вместо implicit-значений «1» или «0» на пересечении пользователя и фильма значение, показывающее насколько важен этот фильм в истории просмотров пользователя.

$$

где StartTime — дата выхода фильма, а ?WatchTime — это разница между датой выхода и датой просмотра пользователем, а ? и ? — гиперпараметры.

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

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



При помощи этой идеи простая модель на одной матрице дала скор 0.03627 на локальной валидации и 0.03685 на public LB, что сразу выглядит как хороший буст в сравнении с предыдущими результатами. На тот момент это вывело меня, приблизительно, в топ-20.

Идея №3

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



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

Итого, путем работы с данными, мы добились скора 0.040312 на локальной тестовой выборке, а сабмит с этими параметрами дал результат в 0.03870 и 0.03990 на public/private части соответственно и обеспечил меня 14-м местом и футболкой.

Acknowledgments

Вести проекты в jupyter notebook — неблагодарное дело. Ты постоянно теряешься в своем коде, который раскидан по нескольким тетрадям. А трекать результаты только в output ячеек совсем опасно с точки зрения воспроизводимости. Поэтому датасаентисты справляются кто как может. Мы с коллегами сделали свой фреймворк на основе cookiecutter-data-science — Ocean. Это средство создания структуры и ведения проекта. О его плюсах можно прочитать в нашей статье. Во многом благодаря хорошему подходу к разделению экспериментов я не сошёл с ума и не запутался при проверке гипотез.

Секрет успеха (не моего)

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



Осознав, что это глупость, я начал искать ну совсем уж изощренные способы, вроде вот этого:



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

Вывод

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

Получается, что для меня опыт участия был действительно полезным в профессиональном плане. Спасибо за прочтение статьи; вопросы, пожелания, замечания приветствуются.