- PVSM.RU - https://www.pvsm.ru -
В 2018 наша команда традиционно приняла участие в RecSys Challenge [1]. Это ежегодный конкурс по рекомендательным системам, проводимый в рамках конференции RecSys. Он не такой масштабный, как конкурсы на Kaggle, но считается одним из самых престижных соревнований по рекомендательным системам. В этот раз задача была музыкальной — нужно было построить систему автоматического продолжения плейлистов. В этом посте я подробно рассказываю о нашем решении. Приглашаю под кат.
В этом году данные для конкурса предоставил Spotify [2] — музыкальный стриминговый сервис (который, к сожалению, официально не доступен в РФ). Рекомендации являются одной из самых важных частей продукта в Spotify и позволяют пользователям находить новую музыку, формировать плейлисты или слушать радио, построенное на основе их предпочтений.
Участникам конкурса нужно было создать алгоритм автоматического продолжения плейлиста [automatic playlist continuation]. В качестве данных для обучения был представлен The Million Playlist Dataset, название которого говорит само за себя. Помимо информации о том, какие треки содержатся в плейлисте, также была предоставлена мета-информация о треках: исполнитель, название, длительность, название альбома.
Более детально про конкурс можно прочитать здесь [1].
Задача конкурса является классической для рекомендательных систем: сгенерировать top-K рекомендаций для пользователя, зная историю его действий, но вместо привычных user-item тут фигурируют playlist-track. Если говорить более формально, то в тестовых данных были даны части плейлистов (далее — сид [seed]), причем было несколько разных способов их формирования. Для K = (5, 10, 25, 100) были сиды с первыми K треками и K треками, выбранными случайно. Также были сиды с первым треком и только с названием плейлиста. Треки, которые не вошли в сид (holdouts), нужно было предсказать. Для каждого плейлиста требовалось сделать ровно 500 предсказаний.
Одной из особенностей конкурса было то, что метрика была не одна, как это принято на большинстве соревнований, а несколько. Ниже расскажу про каждую из них.
Эта метрика показывает, какую долю релевантных треков мы угадали.
Это классическая метрика качества ранжирования, про нее можно прочитать, например, здесь [3]
В Spotify есть механизм для продолжения плейлиста (его можно увидеть на скриншоте в начале статьи): предлагается несколько треков, которыми можно расширить плейлист, а если ни один не подошел, то можно нажать кнопку refresh и получить следующую порцию рекомендаций. Количество таких обновлений до первого выбора — и есть метрика Clicks. Если более просто — позиция первой релевантной рекомендации (в данном случае поделённая на 10).
Далее командам присваивается ранг по каждой из метрик. Затем ранги агрегируются по схеме Borda Count Election Strategy. Если — это количество участников, то команда с рангом 1 получает очков, команда с рангом 2 получает очков и так далее.
Для воспроизведения train/test разбиения мы разбили исходный датасет на три части: первая часть содержала 980k плейлистов, вторая и третья части содержали по 10k соответственно. Затем каждый плейлист из второй и третьей части разбивался на seed и holdout части, причем размеры seed частей выбирались так же, как в предоставленном тестовом наборе, а оставшиеся треки попадали в holdout.
В рекомендательных системах часто используется двухэтапный подход: сначала при помощи более простой модели (например, матричная факторизация [4]) из всего множества айтемов отбираются кандидаты, а затем кандидаты ранжируются более сложной моделью (например, градиентным бустингом [5]) на более широком наборе признаков. Отбор кандидатов необходим, в первую очередь, из-за ограниченных вычислительных ресурсов: если в качестве кандидатов использовать всё множество доступных треков, то на один плейлист нам пришлось бы прогнать через модель порядка миллиона объектов.
Матричная факторизация является одним из самых распространенных подходов к построению рекомендательных систем. Основная идея этого метода состоит в том, чтобы представить разреженную матрицу взаимодействий юзеров и айтемов в виде произведения двух матриц (U и I) меньшей размерности. Тогда мы сможем получить рекомендации для юзера, умножив вектор из матрицы U на матрицу I.
Для матричной факторизации мы использовали библиотеку LightFM [6] c WARP (Weighted Approximate-Rank Pairwise) loss [7]. Также у нас было две разных модели — одна для плейлистов, в которых есть не пустой seed, другая — для плейлистов, у которых есть только название (cold start).
Эта функция потерь лучше других показывает себя в задачах ранжирования. Она работает с тройками (user, positive_item, negative_item) и имеет одну очень важную особенность — выбор негативных примеров происходит не случайно, а таким образом, чтобы выбранные негативные примеры «ломали» текущее ранжирование модели, т.е. были выше, чем позитивный пример.
Таким образом, процедура обучения модели с использованием WARP loss будет примерно следующей:
Более формальное описание WARP loss можно прочитать в оригинальной статье [8] или в этом посте [9].
Первый вариант модели использовал только коллаборативную информацию: наличие трека track_id в плейлисте playlist_id, представленное в виде бинарной разреженной матрицы. Ряд матрицы соответствовал плейлисту, колонка — треку.
Эта модель использует эмбеддинги слов из названия плейлиста вместо playlist_id. Эмбеддинг плейлиста — это сумма эмбеддингов его слов.
, ,
где — это слова из названия плейлиста.
Таким образом мы решаем проблему холодного старта — можем предоставлять более качественные рекомендаций для плейлистов, у которых дано только название.
Организаторами конкурса была предоставлена информация также и о том, сколько треков было в скрытой части плейлиста. Если в скрытой части было треков, то мы выбираем кандидатов. Природа этих чисел — это простая эвристика, придуманная из следующих соображений: мы хотим иметь достаточное количество кандидатов для маленьких плейлистов (поэтому ), а также хотим, чтобы финальный датасет имел примерно 10 миллионов строк из соображений производительности по времени и памяти (поэтому k 15, а не k 50, например).
После того, как мы отобрали кандидатов, мы можем рассматривать задачу построения рекомендаций как задачу бинарной классификации: для каждого из треков в отобранных кандидатах мы учимся предсказывать, действительно ли этот трек был в плейлисте.
В нашем тренировочном датасете каждый ряд будет содержать признаки для пары (плейлист, трек), а лейблом будет 1 при наличии трека в плейлисте и 0 при отсутствии.
В качестве признаков использовались несколько различных групп.
Как уже было описано выше, в модели LightFM мы получили векторы и скаляры .
В качестве признаков будем использовать , < и ранг трека t среди всех кандидатов для плейлиста p (ранг вычислялся по формуле [10]). Эти четыре признака были взяты из обеих моделей LightFM и LightFM Text.
Пусть — это количество плейлистов, содержащих треки и вместе, а — количество плейлистов, содержащих трек . Это значения вычислялись на фиксированном наборе плейлистов, состоящем из всех seed частей.
Пусть плейлист состоит из треков . Для трека посчитаем величины и для них посчитаем различные статистики: минимум, максимум, среднее и медиану. Затем посчитаем эти же статистики для величин . В первом случае мы просто смотрим, насколько часто целевой трек встречался вместе с треками из плейлиста, а во втором случае мы ещё нормируем это на частоту встречаемости других треков. Нормировка помогает модели не переобучаться на популярные треки и более точно извлекать информацию о том, насколько треки действительно похожи.
Все признаки вычисляются для пары .
Для построения финальных рекомендаций мы использовали XGBoost [11]. Модель обучалась на , гиперпараметры подбирались на по метрике ROC AUC [12]. Эта метрика была выбрана, так как она является классической для задач классификации. Не все признаки одинаково полезны, поэтому интересно будет посмотреть на значения feature importance модели.
Feature | Gain |
co-occurrence normalized mean | 1049 |
model, dot product | 101 |
playlist count | 100 |
co-occurrence normalized max | 74 |
tracks holdout count | 63 |
co-occurrence median | 33 |
track count | 29 |
model, dot product | 28 |
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 у всех команд на лидерборде. Мы не придали этому значения, а в конце соревнования выяснили, что организаторы добавили еще одну составляющую в метрику — совпадение исполнителя трека. Это также можно было добавить в метрику валидации и, возможно, улучшить скор.
Наше решение [13] оформлено в виде Jupyter-ноутбуков и его можно воспроизвести(!), последовательно их запустив. Только для этого понадобится машина с 200Gb+ RAM и пара дней времени.
Команда, которая заняла первое место, также регулярно участвует в RecSys Challenge и занимает высокие места. Их решение похоже на наше, но реализовано на Java [14].
У вторых финалистов достаточно интересный подход — они использовали Denoising Autoencoder для восстановления плейлистов из их частей [15].
Если посмотреть на финальный лидерборд, то по метрикам ранжирования (R-Precision и NDCG) наша команда занимает шестое и четвертое место, а по метрике Clicks — первое. Как же так получилось? А получилось так из-за хорошего решения задачи холодного старта при помощи модели LightFM Text. Метрика Clicks более жёстко штрафует в тех случаях, когда мы не угадываем ни одного трека из плейлиста. Использование модели LightFM Text улучшило среднюю метрику Clicks с 2.2 до 1.78.
Подход с отбором кандидатов с помощью более простой модели и дальнейшим ранжированием более сложной моделью все еще является одним из самых успешных в классических задачах построения top-K рекомендаций. Но при этом очень важно правильно построить схему валидации так, чтобы можно было сравнивать и модели отбора кандидатов, и модели ранжирования между собой.
Также эта схема вполне подходит для production систем — можно начать строить свою рекомендательную систему на основе матричной факторизации, а затем улучшить её, добавив вторую стадию.
Если остались какие-то вопросы по статье, смело задавайте их в комментариях :)
P. S. Более подробную статью об этом мы написали для воркшопа на конференции RecSys. Доступ к её материалам на сайте ограничен, поэтому, поэтому, если вам интересно узнать чуть больше деталей о нашем решении, напишите мне в личку.
Автор: greenwo1f
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/309417
Ссылки в тексте:
[1] RecSys Challenge: https://recsys-challenge.spotify.com/
[2] Spotify: https://www.spotify.com/
[3] здесь: https://en.wikipedia.org/wiki/Discounted_cumulative_gain
[4] матричная факторизация: https://en.wikipedia.org/wiki/Matrix_factorization_(recommender_systems)
[5] градиентным бустингом: https://en.wikipedia.org/wiki/Gradient_boosting
[6] LightFM: https://github.com/lyst/lightfm
[7] WARP (Weighted Approximate-Rank Pairwise) loss: https://lyst.github.io/lightfm/docs/examples/warp_loss.html
[8] в оригинальной статье: https://static.googleusercontent.com/media/research.google.com/ru//pubs/archive/37180.pdf
[9] в этом посте: https://building-babylon.net/2016/03/18/warp-loss-for-implicit-feedback-recommendation/
[10] по формуле: https://habr.com/ru/company/avito/blog/439206/#lightfm
[11] XGBoost: https://github.com/dmlc/xgboost
[12] ROC AUC: https://en.wikipedia.org/wiki/Receiver_operating_characteristic
[13] Наше решение: http://bit.ly/2BJYBaC
[14] реализовано на Java: https://github.com/layer6ai-labs/vl6_recsys2018
[15] Denoising Autoencoder для восстановления плейлистов из их частей: https://github.com/hojinYang/spotify_recSys_challenge_2018
[16] Источник: https://habr.com/ru/post/439206/?utm_campaign=439206
Нажмите здесь для печати.