Хабрахабр

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

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

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

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

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

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

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

R-Precision

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

$R-precision=\fracR_{1:|G|}|}{|G|}$

NDCG

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

Clicks

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

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

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

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

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

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

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

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

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

WARP Loss

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

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

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

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

LightFM

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

$score(p, t) = b_t + b_t + <q_p, q_t>$

LightFM + text features

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

$score(p, t) = b_p + b_t + <q_p, q_t>$
$b_p = \sum_{i\in{f_p}}{b_i}$, $q_p = \sum_{i\in{f_p}}{q_i}$,
где $f_p$ — это слова из названия плейлиста.

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

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

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

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

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

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

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

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

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

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

Для трека $t$ посчитаем величины $n_{t,t_1},n_{t,t_2}, ..., n_{t,t_n}$ и для них посчитаем различные статистики: минимум, максимум, среднее и медиану. Пусть плейлист $p$ состоит из треков $t_1, t_2, ..., 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}}$. Нормировка помогает модели не переобучаться на популярные треки и более точно извлекать информацию о том, насколько треки действительно похожи.

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

Все признаки вычисляются для пары $(p, t)$.

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

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

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

Железо

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

Фейлы

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

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

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

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

Кнопка «Наверх»
Закрыть