greenwo1f Feb 20 2019 at 15:44

Как мы решали задачу продолжения плейлистов на RecSys Challenge и заняли 3 место

8 min

14K

AvitoTech corporate blogPython*Algorithms*Mathematics*Machine learning*

В 2018 наша команда традиционно приняла участие в RecSys Challenge. Это ежегодный конкурс по рекомендательным системам, проводимый в рамках конференции RecSys. Он не такой масштабный, как конкурсы на Kaggle, но считается одним из самых престижных соревнований по рекомендательным системам. В этот раз задача была музыкальной — нужно было построить систему автоматического продолжения плейлистов. В этом посте я подробно рассказываю о нашем решении. Приглашаю под кат.

О конкурсе

В этом году данные для конкурса предоставил Spotify — музыкальный стриминговый сервис (который, к сожалению, официально не доступен в РФ). Рекомендации являются одной из самых важных частей продукта в Spotify и позволяют пользователям находить новую музыку, формировать плейлисты или слушать радио, построенное на основе их предпочтений.

Участникам конкурса нужно было создать алгоритм автоматического продолжения плейлиста [automatic playlist continuation]. В качестве данных для обучения был представлен The Million Playlist Dataset, название которого говорит само за себя. Помимо информации о том, какие треки содержатся в плейлисте, также была предоставлена мета-информация о треках: исполнитель, название, длительность, название альбома.

Более детально про конкурс можно прочитать здесь.

Задача конкурса

Задача конкурса является классической для рекомендательных систем: сгенерировать top-K рекомендаций для пользователя, зная историю его действий, но вместо привычных user-item тут фигурируют playlist-track. Если говорить более формально, то в тестовых данных были даны части плейлистов (далее — сид [seed]), причем было несколько разных способов их формирования. Для K = (5, 10, 25, 100) были сиды с первыми K треками и K треками, выбранными случайно. Также были сиды с первым треком и только с названием плейлиста. Треки, которые не вошли в сид (holdouts), нужно было предсказать. Для каждого плейлиста требовалось сделать ровно 500 предсказаний.

Метрики

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

R-Precision

Эта метрика показывает, какую долю релевантных треков мы угадали.

$R-precision=\frac{|G\cap{}R_{1:|G|}|}{|G|}$

NDCG

Это классическая метрика качества ранжирования, про нее можно прочитать, например, здесь

Clicks

В Spotify есть механизм для продолжения плейлиста (его можно увидеть на скриншоте в начале статьи): предлагается несколько треков, которыми можно расширить плейлист, а если ни один не подошел, то можно нажать кнопку refresh и получить следующую порцию рекомендаций. Количество таких обновлений до первого выбора — и есть метрика Clicks. Если более просто — позиция первой релевантной рекомендации (в данном случае поделённая на 10).

Далее командам присваивается ранг по каждой из метрик. Затем ранги агрегируются по схеме Borda Count Election Strategy. Если $inline$ — это количество участников, то команда с рангом 1 получает $inline$ очков, команда с рангом 2 получает $inline$ очков и так далее.

Решение

Схема валидации

Для воспроизведения train/test разбиения мы разбили исходный датасет на три части: первая часть содержала 980k плейлистов, вторая и третья части содержали по 10k соответственно. Затем каждый плейлист из второй и третьей части разбивался на seed и holdout части, причем размеры seed частей выбирались так же, как в предоставленном тестовом наборе, а оставшиеся треки попадали в holdout.

Отбор кандидатов

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

Отбор кандидатов при помощи матричной факторизации

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

Для матричной факторизации мы использовали библиотеку LightFM c WARP (Weighted Approximate-Rank Pairwise) loss. Также у нас было две разных модели — одна для плейлистов, в которых есть не пустой seed, другая — для плейлистов, у которых есть только название (cold start).

WARP Loss

Эта функция потерь лучше других показывает себя в задачах ранжирования. Она работает с тройками (user, positive_item, negative_item) и имеет одну очень важную особенность — выбор негативных примеров происходит не случайно, а таким образом, чтобы выбранные негативные примеры «ломали» текущее ранжирование модели, т.е. были выше, чем позитивный пример.

Таким образом, процедура обучения модели с использованием WARP loss будет примерно следующей:

Для пары $(user, positive\_item)$ выберем случайный негативный пример среди всех остальных айтемов (важно понимать, что так стоит делать только в том случае, когда вероятность выбрать негативный пример, который на самом деле будет позитивным, достаточно мала). Посчитаем предсказание модели на парах $(user, positive\_item)$ и $(user, negative\_item)$ и, если не произошло нарушения порядка (то есть, модель предсказала больший score для позитивного примера), то продолжаем сэмплировать негативные примеры до тех пор, пока нарушение не произойдет.
Если мы получили нарушение с первой попытки, то можно сделать большой градиентный шаг, так как это означает, что на данный момент модель часто ставит негативные примеры выше позитивных и надо сильно обновлять ее веса. Если же нам пришлось долго искать подходящий негативный пример, то делаем маленький шаг — модель уже достаточно хорошо обучена.

Более формальное описание WARP loss можно прочитать в оригинальной статье или в этом посте.

LightFM

Первый вариант модели использовал только коллаборативную информацию: наличие трека track_id в плейлисте playlist_id, представленное в виде бинарной разреженной матрицы. Ряд матрицы соответствовал плейлисту, колонка — треку.

$inline$

LightFM + text features

Эта модель использует эмбеддинги слов из названия плейлиста вместо playlist_id. Эмбеддинг плейлиста — это сумма эмбеддингов его слов.

$inline$
$b_p = \sum_{i\in{f_p}}{b_i}$ , $q_p = \sum_{i\in{f_p}}{q_i}$ ,
где $inline$ — это слова из названия плейлиста.

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

Организаторами конкурса была предоставлена информация также и о том, сколько треков было в скрытой части плейлиста. Если в скрытой части было $inline$ треков, то мы выбираем $inline$ кандидатов. Природа этих чисел — это простая эвристика, придуманная из следующих соображений: мы хотим иметь достаточное количество кандидатов для маленьких плейлистов (поэтому $inline$ ), а также хотим, чтобы финальный датасет имел примерно 10 миллионов строк из соображений производительности по времени и памяти (поэтому k 15, а не k 50, например).

Ранжирование

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

В нашем тренировочном датасете каждый ряд будет содержать признаки для пары (плейлист, трек), а лейблом будет 1 при наличии трека в плейлисте и 0 при отсутствии.

В качестве признаков использовались несколько различных групп.

Признаки на основе модели LightFM

Как уже было описано выше, в модели LightFM мы получили векторы $inline$ и скаляры $inline$ .
В качестве признаков будем использовать $inline$ , < $inline$ и ранг трека t среди всех кандидатов для плейлиста p (ранг вычислялся по формуле). Эти четыре признака были взяты из обеих моделей LightFM и LightFM Text.

Признаки, основанные на со-встречаемости треков

Пусть $n_{i,j}$ — это количество плейлистов, содержащих треки $inline$ и $inline$ вместе, а $inline$ — количество плейлистов, содержащих трек $inline$ . Это значения вычислялись на фиксированном наборе плейлистов, состоящем из всех seed частей.

Пусть плейлист $inline$ состоит из треков $inline$ . Для трека $inline$ посчитаем величины $n_{t,t_1},n_{t,t_2}, ..., n_{t,t_n}$ и для них посчитаем различные статистики: минимум, максимум, среднее и медиану. Затем посчитаем эти же статистики для величин $\frac{n_{t,t_1}}{n_{t_1}},\frac{n_{t,t_2}}{n_{t_2}}, ..., \frac{n_{t,t_n}}{n_{t_n}}$ . В первом случае мы просто смотрим, насколько часто целевой трек встречался вместе с треками из плейлиста, а во втором случае мы ещё нормируем это на частоту встречаемости других треков. Нормировка помогает модели не переобучаться на популярные треки и более точно извлекать информацию о том, насколько треки действительно похожи.

Прочие признаки

Все признаки вычисляются для пары $inline$ .

Количество уникальных исполнителей в плейлисте $inline$ .
Количество уникальных альбом в плейлисте $inline$ .
Количество и доля треков в плейлисте $inline$ с таким же альбомом/исполнителем, как у трека $inline$ .
Сколько раз встретился трек $inline$ во всех плейлистах.
Сколько раз встретился исполнитель/альбом трека $inline$ во всех плейлистах.
Количество треков в seed и holdout частях плейлиста $inline$ .

Модель рекомендаций

Для построения финальных рекомендаций мы использовали XGBoost. Модель обучалась на $II_{candidates}$ , гиперпараметры подбирались на $III_{candidates}$ по метрике ROC AUC. Эта метрика была выбрана, так как она является классической для задач классификации. Не все признаки одинаково полезны, поэтому интересно будет посмотреть на значения feature importance модели.

Feature	Gain
co-occurrence normalized mean	1049
$cs_{text}$ model, dot product $inline$	101
playlist count	100
co-occurrence normalized max	74
tracks holdout count	63
co-occurrence median	33
track count	29
$inline$ model, dot product $inline$	28
$cs_{text}$ model, score rank	26
co-occurrence mean	20

Видно, что признак co-occurrence normalized mean значительно выделяется на фоне других. Это значит, что информация о со-встречаемости треков дает очень сильный сигнал, что, в общем-то, не удивительно. Также этот признак можно было использовать в качестве candidate selection вместо модели LightFM, и это давало результаты не хуже.

Прочее

Железо

Все модели обучались на сервере с Intel Xeon E5-2679 v3 (28 cores, 56 threads), 256Gb RAM. Обучение финального пайплайна занимало порядка 100 часов и потребляло 200Gb памяти в пике, причем значимая (около 90%) часть времени уходила на обучение модели отбора кандидатов. Модель ранжирования обучалась достаточно быстро — около двух часов (не считая подбор гиперпараметров).

Фейлы

Не обошлось и без фейлов.

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

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

Код

Наше решение оформлено в виде Jupyter-ноутбуков и его можно воспроизвести(!), последовательно их запустив. Только для этого понадобится машина с 200Gb+ RAM и пара дней времени.

Решения других участников

Команда, которая заняла первое место, также регулярно участвует в RecSys Challenge и занимает высокие места. Их решение похоже на наше, но реализовано на Java.

У вторых финалистов достаточно интересный подход — они использовали Denoising Autoencoder для восстановления плейлистов из их частей.

Заключение

Если посмотреть на финальный лидерборд, то по метрикам ранжирования (R-Precision и NDCG) наша команда занимает шестое и четвертое место, а по метрике Clicks — первое. Как же так получилось? А получилось так из-за хорошего решения задачи холодного старта при помощи модели LightFM Text. Метрика Clicks более жёстко штрафует в тех случаях, когда мы не угадываем ни одного трека из плейлиста. Использование модели LightFM Text улучшило среднюю метрику Clicks с 2.2 до 1.78.

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

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

Если остались какие-то вопросы по статье, смело задавайте их в комментариях :)

P. S. Более подробную статью об этом мы написали для воркшопа на конференции RecSys. Доступ к её материалам на сайте ограничен, поэтому, если вам интересно узнать чуть больше деталей о нашем решении, напишите мне в личку.

Tags:

Hubs: