This paper describes an approach to solving the next destination city recommendation problem for a travel reservation system. We propose a two stages approach: a heuristic approach for candidates selection and an attention neural network model for candidates re-ranking. Our method was inspired by listwise learning-to-rank methods and recent developments in natural language processing and the transformer architecture in particular. We used this approach to solve the Booking.com recommendations challenge [3]. Our team achieved 5th place on the challenge using this method, with 0.555 accuracy@4 value on the closed part of the dataset.
• Information systems → Recommender systems; • Computing methodologies → Neural networks. 1 1.1
Next city in a trip recommendations is an important applied problem. When a user plans their trip, the ability to correctly predict next destination can directly benefit the user, saving them time on planning. The benefit of the user is important for the booking service provider - if the user gets precise recommendation, they are more likely to book it using the same platform and therefore increase the company revenue. In late 2020 Booking.com, the largest hotel reservations service provider, released a dataset and launched a public competition [3] with the goal of achieving the best Accuracy@4 metric. We built an attention based model for this competition and achieved 5th place with final score of 0.555 Accuracy@4 on the closed test set.
The dataset, released by booking.com, consists of two parts: train and test. Both parts include anonymized hotel checkins with following features: userId, checkinDate, checkoutDate, cityId, deviceClass, afiliateId, bookerCountry, hotelCountry, utripId. CityId and hotelCountry of the last checkin in the trip were masked in the test part of the dataset and were used for scoring by the competition organizers.
The goal of the competition was to generate recommendations list of 4 cities. The organizers used Accuracy@4 as the main contest metric, which essentially is a percentage of times when our recommendations contained correct cityId.
Accuracy@4 is a ranking metric; therefore, we solved the problem as a ranking problem. Accuracy@4 is not a very stable metric, as it does not take into account the order of the elements in the recommendations list and takes into account only 4 scores for each recommendation. Instead, we chose another popular ranking metric - NDCG@40[4] as our main optimization target. This metric is more stable as it considers the order of the elements in the list and takes into account 40 scores rather than 4.
We chose the 2-stages approach, which is popular for solving ranking problems. In the first stage, we selected 500 candidates from all cities using a mixture of simple models. In the second stage, we re-ranked the candidates using a self-attention neural network. We used LambdaRANK[2] approach for the optimization, as it optimizes the NDCG metric directly.
Our main model was inspired by the transformer architecture [9]. The architecture is designed for language processing and achieved state-of-the-art results in many text analysis tasks. The idea of utilizing a language model comes from the fact that a sequence of cities in the trip has a very similar structure as a sequence of words in the text. This idea was already successfully applied to recommender systems; see [8] for example.
On the high level, the model works as follows:
(
Even though the target city itself is unknown, the dataset
contains such features as checkinDate, checkoutDate,
deviceClass, afiliateId, bookerCountry, which we can use for
the prediction.
(
The model training process requires labeled data. To get the labels
for each trip, we performed the following procedure:
(
Our model uses the LamdaRANK ranking optimization approach[2], which involves heavy computations and only can generate scores for a limited amount of candidate cities at once. Given that, we needed to generate good candidates using some simpler approaches. To train the model reasonably fast, we limited the number of candidates to 500 (out of 39870). We used a mixture of simpler models to ifll the set of candidates.
Basic models for candidates selection. This paragraph describes
our basic models and heuristics that we used to produce a list of the
candidate cities. During each training epoch, we randomly chose
10000 trips to train our main neural model to prevent overfitting,
and we used the rest of the training set to re-train baseline models
and generate features. Here is the list of the models that we used
to generate candidates:
(
Let’s assume that the total number of cities in the dataset is equal to , and each trip has cities, where -th city is a target city. We can create transition matrix ∈ R× , which we can fill in a way, described in Algorithm 1.
The prediction process is straightforward: we take all cities in the trip (except target) and sum up all lines in the matrix corresponding to these cities, then we took cities with the highest scores and used them as predictions.
We generated recommendations for the trip using
TransitionsChain and added the resulting recommendations into
the candidates set until it reached size 150.
(
In some cases, we were not able to fill candidates set using
the models above. For example, when a user visited very
unpopular cities, we don’t have enough statistics in the training
set. In this case, we added candidates to the candidates set
from two additional models:
(
Our experiments have shown that this heuristic includes the right candidate into the set of candidates with 90% probability. 2.3
For each candidate, we generated a vector representation that included the following features: • City’s popularity globally and especially for booker’s country • City’s popularity according to current month and year • City’s score from TransitionsChain recommender. • Binary flag: is the candidate same city as the first city in the trip • Binary flags: for each of the last 5 cites in the trip - is the candidate the same as this city from the trip • Candidate’s cosine similarity with last 5 cities in a trip based on their co-occurrence in train data. 2.4
Our model used transformer[9]-like architecture to encode cities
from the trip history. We represented each city in the trip as a
vector, that included following parts:
(
Overall, each city in the trip was represented using 115 parameters. We stacked the cities’ representations in the trip and padded the matrix to the shape (50, 115), where 50 is the maximum possible number of cities in the trip.
To get a better semantic representation of the cities in the trip, we encoded each city using a single dense layer with 115 dimensions.
Similarly to the original transformer architecture, we combined city representation with positional embeddings. In the original paper[9] the authors use fixed embeddings, based on function. We replaced this with two learnable embeddings, representing the city’s position from the beginning and the end of the trip. These embeddings are then concatenated, passed through a dense layer, and multiplied with city representation vectors.
To model interactions of the cities in the trip, we added three transformer-like blocks. The original transformer block consists of multi-head attention, feed-forward layer, residual connection, and layer normalization. Our transformer-like block has a similar architecture with only a minor diference: we used Multiplication for residual connection instead of Sum. Our experiments have shown that the network with Multiplication instead of Sum required fewer epochs to train. Figure 3 shows architecture of the Transformer-like block used in our architecture.
We then used the Transformer-like part of the model to model interactions between candidate cities and cities from the trip. In addition to the features matrix described in section 2.3, we added city embedding and country embedding to each candidate. These embeddings share weights with the city embeddings and country embeddings from the trip-encoding part of the model. The candidates were additionally encoded using a feed-forward layer. We also added one transformer-like block to model the relationship between candidates. The idea is that the candidates are not independent, and the model should score candidates knowing about other candidates. A similar idea of modeling interactions between candidates for recommendations is described in [7]
We used one multi-head attention layer to model interaction between encoded user trips and encoded candidate cities. We hypothesize that this output layer contained semantically rich representations of the (trip, candidate) pairs.
To generate the model’s final scores, we used dot product operation with encoded features of the target city. The dataset contains all parameters of the target city, except cityId and countryId. We encoded these parameters using the same manually engineered features as described in section 2.3 and encoded them using a dense layer. 2.5
Our model’s goal was to rank candidates according to the label score, which constitutes a ranking task. The problem of direct optimization of the ranking metrics, such as Accuracy@4 or NDCG, is dificult because these metrics only depend on the order of the items and therefore are not smooth and can not be directly optimized gradient-descent technologies. To overcome this problem, we used the LambdaRANK approach described in [2]. The method’s idea is that instead of calculating the loss function and calculating its gradients, one can directly calculate gradients. The authors of [2] propose generating such gradients for optimizing the NDCG metric. We implemented this method and used it as our main optimization approach.
We optimised our network using Adam[5] optimiser. We trained our model using 50-epochs early stop criteria on val_accuracy_at_4 metric.
In this section, we describe the validation scheme, metrics and analyze our results. 3.1
Our validation scheme was based on trips. We used both train and test datasets provided by the competition organizers to train our model. We randomly allocated 4000 trips to the hold-out set, 4000 trips to the validation set, and the rest to the training set. We tried to predict the last city in the trip based on all previous cities’ information and available information about the last city in the validation and hold-out sets. 3.2
We used the following metrics to evaluate our models: • Accuracy@4: competition organizers proposed this metric.
The idea of Accuracy@4 is quite simple: it is equal to 1 if the target city in our top-4 prediction and 0 otherwise. • NDCG@40: according to our experiments, NDCG@40 is a more stable metric than previous ones. We also found that NDCG@40 and Accuracy@4 have a quite strong correlation (Figure 3.). One can find the details about the NDCG metric in [4] • Leaderboard: this metric is essentially the Accuracy@4 metric, calculated by the organizers on the closed part of the dataset. We could only calculate this metric for two models by the competition’s conditions - the one that we sent for the intermediate leaderboard and the final submission. 3.3
Model performance against baselines • GlobalTop, LastCityCountryTop, TransitionChain - baselines used as part of our candidates selection process (see section 2.2) • TruncatedSVD - a popular method of solving recommendations problem [6]. • SelfAttention - end-to-end version of our model. The model’s architecture consists of a transformer-like part of our model, followed by three dense layers, the last of which generates recommendation scores for all cities in the dataset. The main diference compared with the reranking attention model is that this model doesn’t use manually engineered candidate features. This makes the model simpler, and therefore the model can produce scores for all cities in the dataset rather than a small number of candidates. • LambdaMART - Gradient boosting trees implementation of the LambdaRANK approach. We used the same candidate generation procedure and same manually engineered features described in section 2.3. We used LambdaMART implementation from LightGBM lilbrary1.
Table 1 contains results of the comparison. Our final model demonstrates statistically significant improvement over baselines on the Accuracy@4 metric (p-value < 0.01 in two-tailed Z-test). 4
As this challenge has shown, combining the listwise ranking methods and neural models is a viable idea that allowed us to achieve a high score on the contest. The same optimization approach can be used with other architectures and solve many other ranking problems in the information retrieval area, including recommender systems and search results ranking. 1https://lightgbm.readthedocs.io/en/latest/ We used the following baselines to evaluate quality of our model: Atention-based neural re-ranking approach for next city in trip recommendations