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

Рекомендации городов в booking.com, картинка отсюда

В этой статье мы опишем наше решение задачи, которое заняло 5е место на соревновании. Наше решение основано на нейросетевом механизме внимания, а так же на основе listwise-метода обучения ранжированию LambdaRank. Наше решение выбирает правильный город в четыре рекомендованных города с вероятностью 55.5%, что есть довольно неплохой результат, учитывая что алгоритму необходимо было выбирать 4 города из практически 40000 возможных.

Эта статья расширенная версия нашей статьи, которая была принята и опубликована на воркшопе по web-туризму в рамках конференции WSDM.

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

Описание задачи

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

В тестовой части датасета, последний город в путешествии и страна последнего города были замаскированы; остальные параметры, например дата въезда и дата выезда, доступны. Задача участников соревнования для каждого путешествия из тестовой части датасета порекомендовать 4 варианта последнего города. Участники оценивались по метрике Accuracy@4. По сути, эта метрика показыват сколько процентов рекомендаций содержали правильный город.

Переранжирующая модель на основе механизма внимания.

Метрика Accuracy@4 по своей сути является метрикой ранжирования: мы можем сгенерировать скор для всех возможных городов, отсортировать их и оценить вероятность с которой целевой город окажется среди топ-4х городов. Так как наша целевая метрика является метрикой ранжирования, мы решали задачу как задачу ранжирования.
Сама по себе метрика Accuracy@4 не очень удобна для оптимизации напрямую, тал как она учитывает выставленный скор только для четырех городов и никак не учитывает взаимный порядок между этими четыремя городами. Для того, чтобы облегчить себе задачу, мы заменили эту метрику другой популярной метрикой ранжирования, а именно метрикой NDCG@40.

Так как метрика NDCG@K зависит не только от элементов, включенных в список рекомендаций, но и от их относительного порядка, ее значение более стабильно по сравнению с метрикой Accuracy@K. Кроме того, мы увеличили стабильность метрики за счет того, что выбрали большее значение K (40 вместо 4).

Еще одной проблемой метрик ранжирования, таких как NDCG@K или Accuracy@K, является тот факт, что их значение изменяется скачкообразно при изменении порядка элементов в списке рекомендаций. Это означает, что такие метрики не являются гладкими и дифференцируемыми и их нельзя напрямую оптимизировать классическим методом градиентного спуска.

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

Для прямой оптимизации метрики NDCG существует метод LambdaMART[1]. Это метод, работающий на основе градиентного бустинга над деревьями принятия решений. Например, он реализован в популярных библиотеках LightGBM и XGboost и является рабочей лошадкой для решения задач ранжирования. Например, этот метод работает в Bing для ранжирования поисковых результатов, применяют в Amazon, да и Яндексовый YetiRank является близким родственником данного подхода.
В основе метода лежит идея замены градиента лосс-функции специально сконструированными значениями, называемыми лямбда-градиент, используя которые в методе градиентного спуска можно оптимизировать метрику NDCG. Мы реализовали этот метод для обучения нейросетей и применили для решения нашей задачи. В итоге, верхнеуровнево, наше решение выглядит следующим образом:

1. Выбрать города-кандидаты для рекомендаций при помощи простых эвристических алгоритмов.
2. Сгенерировать матрицу C фичей для кандидатов.
3. Сгенерировать векторные представления T предыдущих городов в текущей поездке при помощи Transformer-like архитектуры.
4. Сгенерировать векторное представление F целевого города на основе доступных фичей. Несмотря на то что мы не знаем идентификатор города, мы можем использовать такие параметры как дата въезда и выезда, тип устройства и т.д.
5. Сгенерировать скор для кандидатов и отсортировать их в соответствии с этим скором. Для этого, мы применяем механизм внимания между кандидатами и посещенными городами. Результат этой операции скалярно умножаем на векторное представление фичей и получаем результат.

Теперь разберем нашу модель подробнее.

Генерация лейблов

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

1) Сортируем города из путешествия по времени
2) Несколько последних городов в путешествии объявляем "целевыми". Конкретное количество целевых городов определяем случайным образом для каждого путешествия
3) Назначаем для i-го города в целевой части скор 2^-i. Идея назначать экспоненциально уменьшающийся вес базируется на том, что чем на более далекое будущее приходится посещение города, тем меньше влияние предыдущих городов и тем больше влияние других факторов, которые наша модель не может учесть.

Отбор кандидатов для ранжирования

Наша подход основан на методе оптимизации LambdaRANK.
Этот подход требует довольно тяжелых вычислений, и поэтому мы можем его применять только на ограниченном количестве кандидатов. Поэтому, нам необходимо было отобрать города-кандидаты используя более простой подход. Для того, чтобы тренировать нашу модель за разумное время мы решили ограничиться 500 городами-кандидатами для каждого путешествия из 39870 возможных. Мы использовали смесь простых моделей для того, чтобы выбрать эти 500 кандидатов.

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

Вот список простых моделей и правил, которые мы использовали для генерации 500 кандидатов:

1. Все предыдущие посещенные города из путешествия

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

2. Transition chain

Данная модель использует последовательную природу посещений городов в модели.
Предположим, что в нашем датасете всего $M$ городов, и каждое путешествие представляет из себя последовательность из $K$ городов, где $K$-й город в последовательности это наш целевой город. Мы можем создать матрицу переходов в последний город $T \in R^{M \times M}$, которую мы заполним, используя следующую процедуру:

procedure fillTransitionMatrix     T  zero matrix with size M  M      for current_trip in trips do:     last_city  current_trip [1]         prev_cities  current_trip [: 1]         for city in prev_cities do:             T [city][last_city] += 1.         end for     end forend procedure

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

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

3. BookerTripCountryTop

Данный метод представляет из себя простую эвристику. Мы отбираем самые популярные города для путешествий, среди пользователей из страны, совпадающей со страной текущего пользователя, которые путешествовали в страну, которая совпадает со страной последнего города из текущего путешествия.
Используя данную эвристику мы добавляли города в множество кандидатов, до тех пор, пока его размер не достиг 350.

4. LastCityCountryTop

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

Используя эвристики описанные выше, мы зачастую могли полностью заполнить множество кандидатов. Однако, в некоторых ситуациях, нам не хватало городов. Например, такое могло случится, когда пользователь из редкой страны путешествует в другую редкую страну в этом случае алгоритмы TransitionChain, BookerTripCountryTop и LastCityCountryTop могут сгенерировать лишь небольшое количество городов-кандидатов с ненулевым скором. В такой ситуации мы использовали два дополнительных метода отбора кандидатов, используя следующие эвристики:

5. BookerCountryTop Самые популярные города среди путешественников из страны, совпадающей со страной текущего пользователя.

6. GlobalTop Самые популярные города в датасете.

Используя описанные шесть эвристик мы могли гарантированно заполнить массив из 500 городов-кандидатов. Наши эксперименты показали, что используя данные эвристики, вероятность включения нужного города в список кандидатов (метрика recall@500) составляет примерно 90%.

Генерируем фичи для кандидатов.

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

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

Генерируем векторе представление путешествия

Наша модель использует нейросетевую архитектуру, похожую на архитектуру Transformer[2] для того, чтобы закодироияя. Архитектура Transformer хорошо подходит для обработки текстов. Использование данной архитектуры базируется на том факте, что последовательность городов в путешествии похожа на последовательность слов в тексте.

Мы сгенерировали векторное представление каждого города в путешествии используя следующие признаки:

• Эмбеддинг города, 32 обучаемых параметра.
• Эмбеддинг страны пользователя, 32 обучаемых параметра.
• Эмбеддинг страны города 32 обучаемых параметра. Данный эмбеддинг использует те же веса, что и эмбеддинг страны пользователя.
• Эмбеддинг источника траффика(affiliate id) 5 обучаемых параметров
• Некоторое количество фичей, разработанных нами вручную, включая:
  Количество ночей между въездом и выездом в отель.
  Захватывает ли остановка в отеле выходные? (хороший признак для того, чтобы отличать командировки)
  Совпадает ли страна города с предыдущими со страной предыдущих городов в путешествии.
  День недели и неделя в году для даты въезда и выезда.
  Совпадает ли страна пользователя и страна города?
  Год въезда. 3 параметра, one-hot encoded. В датасете представлены путешествия только за 3 года.
  Месяц въезда. 12 параметров, one-hot encoded.

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

Для того, чтобы получить более качественное семантическое представление городов в путешествии, мы закодировали их используя один полносвязный слой нейросети размерности 115. Для того, чтобы учесть позицию города в путешествии, мы так же умножили этот вектор на эмбеддинг позиции. В оригинальной архитектуре Transformer, авторы используют фиксированные эмбеддинги, основанные на функциях $sin$ и $cos$ Вместо этого, мы использовали два обучаемых эмбеддинга, представляющих собой позицию города относительно начала и конца путешествия. Мы сконкатенировали эти эмбеддинги и пропустили их через один полносвязный слой для того, чтобы получить финальный эмбеддинг города в путешествии.

Transformer-like блок. По сравнению с оригинальным блоком transformer, мы заменили сложение на умножение в residual-связи

Для того, чтобы смоделировать взаимодействия городов друг с другом, мы воспользовались архитектурой Transformer. Оригинальный блок архитектуры Transformer состоит из одного Self-Attention слоя, Dense-слоя, Residual-связи и нормализации. На хабре уже неоднократно разбирали архитектуру Transformer, поэтому мы не будем описывать ее тут. Единственная разница нашего transformer-like блока с оригинальным, заключается в том, что для residual связи мы используем не сложение, а умножение. Наши эксперименты показали, что на данном датасете, умножение позволяет обучиться быстрее и позволяет достичь более высокого результата.

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

1. Закодировали матрицу городов-кандидатов, используя один полносвязный слой нейросети.
2. Полученные представления городов-кандидатов мы пропустили через один Transformer-like блок. Интуитивно города кандидаты не являются независимыми и, зная какие есть другие кандидаты, нейросети будет легче подобрать правильный скор для текущего города.
3. При помощи одного слоя MultiHeadAttention смоделировали взаимодействия с предыдущими городами из путешествия. На выходе мы получили эмбеддинги городов-кандидатов в контексте текущего путешествия.

Архитектура нашей нейросети.

Финальный скор для каждого города-кандидата мы генерировали при помощи умножения (dot product) эмбеддинга города-кандидата на закодированное представление фичей последнего города. По условиям задачи, нам не известен последний город, но известные некоторые характеристики поездки в этот город, например время въезда и выезда и источник трафика. Мы закодировали эти параметры, используя те же самые процедуры, которые мы использовали для кодирования фичей городов в путешествии. Дополнительно, мы пропустили эти фичи через один полносзвязный слой нейросети, для того чтобы получить проекцию в то же пространство, в которое мы спроектировали эмбеддинги городов-кандидатов.

Обучаем модель

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

Мы взяли имплементацию метода из библиотеки lightgbm в качестве референсной и написали собственную имплементацию, которая подходит для обучения нейросетей. Как показали наши эксперименты, использование метода LambdaRANK позволило нам намного быстрее обучать нашу нейросеть ранжировать города, по сравнению с использованием бинароной кроссэнтропией. Кроме того, метрика NDCG, которую оптимизирует LambdaRANK показала практически идеальную корелляцию с метрикой Accuracy@4, поэтому в целом обучая модель получать хороший скор NDCG, мы автоматом получали хорошее значение Accuracy@4.

Для тренировки мы использовали оптимизатор Adam с ранней остановкой после 50 эпох без улучшения метрики Accuracy@40

Метрики Accuracy@4 и NDCG@40. Видно что метрики кореллируют практически идеально. Такой выскоий уровень корреляции подсказывает что оптимизируя одну метрику, мы автоматом оптимизируем и другую

Для имплементации нашей нейросети мы использовали библиотеки Tensorflow и Keras. Тренировка заняла примерно 7 часов на GPU Nvidia RTX 3090.

Оценка качества модели и результаты

Схема валидации нашей модели была основана на отдельных путешествиях. Так как с нашей точки зрения большой разницы между частями train и test датасета не было, мы объединили эти части и использовали обе из них как для тренировки модели, так и для оценки качества. Мы случайным образом отобрали 4000 путешествий в тестовое множество (наше тестовое, не путать с частью test датасета) и еще 4000 в валидационное. Остальные путешествия из обоих датасетов мы поместили в тренировочную выборку. На этапе валидации и тестирования модели мы использовали все города кроме последнего для того, чтобы предсказать один последний город в каждом путешествии (стратегия leave one out).

Метрики

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

• Accuracy@4 Метрика использованная организаторами соревнования для оценки моделей.
• NDCG@40 Метрика которую мы использовали в для оптимизации нашей нейросети. Как мы показали выше, данная метрика хорошо кореллирует с метрикой Accuracy@4.
• Leaderboard По сути, это та же самая метрика Accuracy@4, измеренная организаторами соревнования на закрытой части датасета. По условиям соревнования, мы могли померять эту метрику лишь дважды: один раз для "предварительной" модели, и один раз для финальной модели.

Сравнение метрик с простыми моделями:

Для оценки качества нашей модели мы использовали следующие бейзлайны:

• GlobalTop, LastCityCountryTop, TransitionChain простые эвристические алгоритмы которые мы использовали для отбора кандидатов.
• TruncatedSVD Популярный подход для решения задачи построения рекомендательных систем на основе матричного разложения. Мы использовали реализацию TruncatedSVD из библиотеки sklearn.
• SelfAttention end-to-end версия нашей модели. Архитектура данной модели похожа на нашу финальную модель. Отличие в том, что мы рассчитываем скор для всех городов, а не для топ-500 кандидатов. Из-за этого модель была более тяжеловесной, и мы не могли использовать фичи, которые мы генерировали вручную (например похожесть на предыдущие города из путешествия). По сути, при помощи Transformer-like части нашей модели мы генерировали эмбеддинг путешествия, и сравнивали с выученными эмбеддингами городов. Эту модель мы использовали для промежуточной оценки результата.
• LambdaMART Так как мы использовали подход LambdaRANK, мы хотели попробовать сравнить нашу имплементацию с классической реализацией данного подхода на деревьях принятия решений. Мы использовали имплементацию LambdaRANK из библиотеки lightgbm. Подход базировался тольк о на вручную сгенерированных фичах (описанных в секции "генерируем фичи для кандидатов" выше).

Результаты сравнения моделей представлены в следующей таблице:

Заключение

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

Ссылки:
[1] Burges CJ. From ranknet to lambdarank to lambdamart: An overview
[2] Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser L, Polosukhin I. Attention is all you need. arXiv preprint arXiv:1706.03762. 2017 Jun 12.

(https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.180.634&rep=rep1&type=pdf). Learning. 2010 Jun 23;11(23-581):81.