Memory Augmented Neural Model for Incremental Session-based Recommendation

1 Introduction

Due to new privacy regulations that prohibit building user preference models from historical user data, it is getting important to utilize short-term dynamic preferences within a browser session. Session-based Recommendation (SR) is therefore increasingly used in interactive online computing systems. The goal of SR is to make recommendations based on user behavior obtained in short web browser sessions, and the task is to predict the users' next actions, such as clicks, based on previous actions in the same session.

To better address the dynamic nature of SR tasks, we study it from an incremental learning perspective, referred to as Incremental Session-based Recommendation. In this setting, new items and preferences appear incrementally, and models need to incorporate the new preferences incrementally while preserving old ones that are still useful. The setup requires a recommender to be incrementally updated with data observed during the last time period and evaluated on the events in the following time period. We summarize three main challenges of incremental SR scenarios: (i). catastrophic forgetting [McCloskey and Cohen, 1989]: incorporating new patterns requires additional training and often reduces performance on old patterns. (ii). computation efficiency: models need to be efficient as they need to be frequently updated with new data. (iii). sample efficiency: the number of observations on new items and patterns is often small such that models need to capture them quickly with limited observations.

Recently proposed neural approaches [Hidasi et al., 2016; Li et al., 2017; Hidasi and Karatzoglou, 2018; Liu et al., 2018; Sun et al., 2019] have shown great success in a static setting where the set of items and the distribution of preferences during testing are assumed to be the same as in the training phase. However, this assumption rarely holds in realworld recommendation applications. As our first contribution, we show that neural recommenders can also be efficiently and effectively used for incremental SR scenarios by applying small incremental updates. To the best of our knowledge, this is the first study of neural models for SR from an incremental learning perspective. We found that incrementally updating neural models using a single pass with a small learning rate through new data helps to capture new patterns incrementally. However, using large learning rates (or equivalently multiple passes) degrades performance badly due to overfitting new patterns and forgetting old ones.

Our main contribution is to propose a method called Memory Augmented Neural model (MAN) inspired by a framework proposed for language model [Merity et al., 2017; Grave et al., 2017a], neural machine translation [Tu et al., 2018], and image recognition [Orhan, 2018] tasks. MAN augments a neural recommender with a nonparametric memory to capture new items and preferences incrementally. The predictions of neural and memory components are combined by a lightweight gating network. MAN is agnostic to the neural model as long as it learns meaningful sequence representations, therefore, it can be easily and broadly applied to various neural recommenders. The nonparametric memory component of MAN helps to deal with all three challenges of incremental SR mentioned above. First, it achieves a long-term memory to remember long histories of observations to mitigate catastrophic forgetting. Second, it is very efficient to update because it is not trained jointly with the base neural recommender. Third, the nonparametric nature by itself helps to better capture new patterns with a smaller number of observations to address the third challenge of sample efficiency. Through extensive experiments, we show that MAN boosts the performance of different neural methods and achieves stateof-the-art. We also demonstrate that it is particularly good at capturing preferences on new and infrequent items.

2 RelatedWork

Incremental learning for recommendation is an important topic for practical recommendation systems where new users, items, and interactions are continuously streaming in. For the standard recommendation task of predicting ratings or clicks, different learners have been studied based on matrix factorization (MF) with online updating, including [He et al., 2016]. For sequential recommendation tasks, the interaction matrix to be decomposed is constructed from sequential user feedback. [Rendle et al., 2010] proposes FPMC to factorize the transitions in Markov chains with low-rank representation. Later, [He and McAuley, 2016] proposes to FOSSIL with factorized Markov chains to incorporate sequential information. Recently, SMF is proposed by [Ludewig and Jannach, 2018] for SR using session latent vectors. However, these MF-based methods are expensive to train. For example, [Li et al., 2017; Wu et al., 2019] reported that even 120GB memory is not enough to train FPMC. Therefore, they are in principle not suitable for incremental settings.

Session-based recommendation can be formulated as a sequence learning problem to predict the user's sequential behavior. It can be solved by recurrent neural networks (RNNs). The first work (GRU4Rec, [Hidasi et al., 2016]) uses a gated recurrent unit (GRU) to learn session representations from previous clicks and predict the next click. Based on GRU4Rec, [Hidasi and Karatzoglou, 2018] proposes new ranking losses on relevant sessions, and [Tan et al., 2016] proposes to augment training data. NARM [Li et al., 2017] augments GRU4Rec with a bilinear decoder and an additional attention operation to pay attention to specific parts of the sequence. Base on NARM, [Liu et al., 2018] proposes STAMP to model users' general and short-term interests using two separate attention operations, and [Ren et al., 2019b] proposes RepeatNet to use an additional repeat decoder based on an attention mechanism to predict repetitive actions in a session. Recently, [Wu et al., 2019] uses graph attention to capture complex transitions of items. Motivated by the recent success of Tansformer [Vaswani et al., 2017] and BERT [Devlin et al., 2018] for language model tasks, [Kang and McAuley, 2018] proposed SASRec using the the Transformer operation and [Sun et al., 2019] proposed BERT4Rec using the training scheme of BERT to model bi-directional information through Cloze tasks. Despite the broad exploration and success, these methods are all studied in a static SR scenario without considering new items and patterns that appear continuously.

Nonparametric methods [H¨ardle and Linton, 1994] are ideal for incremental learning tasks thanks to their computation efficiency. The amount of information they capture increases as the number of observations grows. Simple itembased collaborative filtering methods using nearest neighbors have been proven to be effective and are widely employed in industry. Markov models [Shani et al., 2005] also support updating the transition probabilities incrementally. However, the Markov assumption is often too strong, and it limits the recommendation performance. Recently, [Jannach and Ludewig, 2017] proposed SKNN to compare the entire current session with historical sessions in the training data. They show that SKNN is very efficient and achieves strong results. Lately, variations [Ludewig and Jannach, 2018; Garg et al., 2019] of SKNN have been proposed to consider the position of items in a session or the timestamp of a past session. [Mi and Faltings, 2017; 2018] built a nonparametric recommender based on a structure called context tree to model suffixes of a sequence. These simple nonparametric methods are independent from the neural approaches. In this paper, we combine the edges of both neural and nonparametric models for incremental SR scenarios.

Memory-augmented neural models [Graves et al., 2014] have been well-known for the purpose of maintaining longterm memory, which is also recently explored for sequential recommendation tasks [Chen et al., 2018; Ren et al., 2019a]. However, the goal of maintaining long-term memory is not the central concern in incremental SR scenarios. This category of memory-augmented neural models differ from ours in the sense that their memory components are parametric as they need to be trained jointly with the rest of the model. Therefore, they are not suitable be updated frequently without catastrophic forgetting in incremental SR scenarios.

Our work is largely inspired by a recently proposed nonparametric memory module that is not trained jointly with neural models. [Grave et al., 2017b; Merity et al., 2017] introduce a cache to augment RNNs for language modeling task. They later improve this cache to unbounded size [Grave et al., 2017a] and achieve significant performance improvement. A similar memory module is also proposed for neural machine translation tasks [Tu et al., 2018] and image recognition tasks [Orhan, 2018].

3 Model

Background. session-based recommendation, an event is a click on an item and the task is to predict the next event based on a sequence of events in the current web-browser session. Suppose Y is the set of all candidate items, and the size is n. Existing neural session-based recommenders typically contain two modules: an encoder gθ(x1:t) to compute a compact sequence representation ct of the sequence of events x1:t until time t, and a decoder fω(ct) to compute an output distribution P N ∈ Rn to predict the next event. Recurrent neural networks (RNNs) and fully-connected layers are common choices for encoder and decoder respectively. In our later experiments, we included models that use different types of encoders and decoders. Our MAN framework is agnostic to the neural recommender, therefore, readers can use many other neural architectures with an encoder-decoder structure.

Next, we present the Memory Augmented Neural recommender (MAN) to augment a neural session-based recommender with a cache-like nonparametric memory to incrementally incorporate new items and preferences. We first introduce the architecture of the cache-like memory. Then we describe how to use it to generate nonparametric memory predictions, and how to merge memory and neural predictions through a lightweight gating network.

3.1 Nonparametric Memory Structure

Our memory M is an array of slots in the form of (key, value) pairs [Miller et al., 2016] in Eq.(1). M is queried by keys and returns corresponding values. We define the keys to be input sequence representations cm computed by the neural encoder, and the values to be the corresponding label ym of the next event. To scale to a large set of observations and long histories in practical recommendation scenarios, we do not restrict the size of M but store all pairs (cm, ym) from previous events.

3.2 Memory Prediction

To support efficient incremental learning, the memory module is not trained jointly with the neural recommender. Instead, it directly predicts the next event by computing a probability distribution using entries stored in M. For an input sequence x1:t, we first match the current sequence representation ct = gθ(x1:t) against M to retrieve K nearest neighbors N(ct) = {(ck, yk, dk)}Kk=1 of ct, where dk is the Euclidean distance between the sequence representation ck of the k-th neighbor and ct. Then, we use the K nearest neighbors to compute a non-parametric memory prediction P M ∈ Rn using a variable kernel density estimation by:

where P M (yi) is the probability on an item yi ∈ Y, δ(yt = yk) is Kronecker delta which equals one when the equality holds and zero otherwise, K is a Gaussian kernel (K(x) = exp(-x2 /2)), and d⋆ is the Euclidean distance between ct and its closest neighbor in N(ct). P M only assigns non-zero probability to at most K (number of neighbors) items because the probabilities assigned to items that do not appear in the nearest neighbors are zero. As a result, P M is a very sparse distribution as a mixture of the labels in N(ct) weighted by their similarities to ct. To capture new preference patterns incrementally, M is queried and updated incrementally during the testing phase such that P M is up-to-date.

3.3 Gating Network to Combine Memory and Neural Predictions

The neural prediction P N mainly captures static old preference patterns while the nonparametric memory prediction P M can model infrequent and new preference patterns incrementally. To flexibly work with both scenarios, these two predictions are combined. A simple way proposed by [Grave et al., 2017a; Orhan, 2018] is linearly interpolating them with a fixed weight, and we later call this version "MAN-Shallow" in our experiments in Section 4.5.

To better merge these two predictions at different sequential contexts, we propose to use a lightweight gating network

[Bakhtin et al., 2018] w(ct) to learn the mixing coefficient as a function of the sequence representation ct. We use a lightweight fully connected neural network defined in Eq.(3) with a single hidden layer of 100 hidden units, tanh as hidden layer activation function, and a Sigmoid function at the output layer.

The output of w(ct) is a scalar between 0 and 1 that measures the relative importance of P N , while the other 1-w(ct) fraction is multiplied to P M . The final prediction distribution P MAN is an learning interpolation of P M and P N weighted by the output of w(ct) computed in Eq.(4) .

The gating network is trained with cross-entropy loss using P MAN as predictive distribution after the normal training of the neural model with both P N and P M are fixed. The gradients are not computed for the large number parameters of the neural model to avoid computation overhead and interference with the trained neural model. Inspired by [Bakhtin et al., 2018], it is trained using only validation data. The idea is to train it using data not seen during the pre-training phase to better predict new preferences that might appear in incremental SR scenarios. We randomly select 90% validation data for training and the remaining 10% for early stopping. We compared this setup with training using the whole training set, and we found that our setup achieves better performance while being much more efficient.

3.4 Efficient Large-scale Nearest Neighbor Computation

As the number of events in practical SR scenarios is huge and we do not restrict the size of M, computing nearest neighbors frequently to generate P M can be expensive. We apply a scalable retrieval method used by [Grave et al., 2017a]. To avoid exhaustive search, an inverted file table T is maintained. Keys in M are first clustered to a set of clusters using k-means, then all keys in M can be associated with one centroid. When we query ct in M, it is searched by firstly matching to a set of centroids to get the closest cluster and then the set of keys in this cluster.

The clustered memory supports efficient querying, yet it is memory consuming because each key in M needs to be stored. This can be greatly reduced by Product Quantization (PQ [Jegou et al., 2010]) that quantizes a vector by parts (subquantizers), and it does not directly store the vector but its residual, i.e., the difference between the vector and its associated centroids. We use 28 centroids, 8 sub-quantizers per sequence representation, and 8 bits allocated per sub-quantizer, then we only need the size of 16 (quantization code + centroid id = 8 + 8) bytes per vector. Therefore, a million sequence representations can be stored with only 16 Mb memory. With an inverted table and PQ, we have a fast approximate nearest neighbor retrieval method with a low memory footprint. We use the FAISS 1 open-source library that also supports GPU acceleration for implementation.

1 https://github.com/facebookresearch/faiss

Algorithm 1 Memory Augmented Neural Recommender

1: procedure TRAIN(Dtrain,Dvalid,M) 2: Train gθ, fω w.r.t. Dtrain 3: for (x1:t, yt) ∈ Dtrain do 4: Compute ct = gθ(x1:t); store (ct, yt) to M 5: end for 6: Build the inverted table T for M 7: Fix gθ, fω, and train w(ct) w.r.t. Dvalid 8: end procedure 9: procedure TEST(Dtest,M) 10: for (x1:t, yt) ∈ Dtest do 11: Compute ct = gθ(x1:t), and P N = fω(ct) 12: Query M and T to retrieve N (ct) 13: Compute P M by Eq.(2), P MAN by Eq.(4) 14: Update M and T with (ct, yt) 15: end for 16: end procedure

3.5 Overall MAN Algorithm

The computation pipeline and algorithm of MAN presented in Figure 1 and Algorithm 1. Next, we describe the training and testing procedures of MAN in detail, and also analyzed its computation efficiency.

Training procedure. MAN first trains the neural encoder and decoder on the training set Dtrain. Then, it computes sequence representations for all training data and stores them with corresponding labels to M. Afterwards, the clustered memory of the inverted table T is built with entries in M. Lastly, The gating network is trained on validation set Dvalid.

Testing procedure. The sequence representation ct and the neural prediction P N is first computed. Then, M and T are queried with ct to retrieve K nearest neighbors N(ct) to compute P M . To generate the final recommendation P MAN , P M is merged with P N weighted by the output of the gating network. Lastly, M and T are incrementally updated with the new testing pair (ct, yt). During testing, the clustered memory in T is not updated for the purpose of computation efficiency. Running k-means to update the clustered memory on huge data sets with large dimensions is computationally intensive. Therefore, we need to decide when and how to update the clustering algorithm, and there will be a trade-off between the performance benefits and the computation overhead. Studies on this part are left for interesting future work.

Computation efficiency analysis. During training, the additional training procedures of MAN on top of the regular neural recommender training are efficient. (i) Sequence representations of training data can be obtained directly from the last regular training epoch of the neural recommender, therefore, no computation overhead is injected at this step (line 3-5). 2). (ii) Building the clustered memory and the inverted table for entries in M (line 6) is also fast with the FAISS library. (iii) Training the lightweight gating network using only validation split (line 7) is much more efficient than the regular training of the base neural recommender. During testing, querying the memory to retrieve nearest neighbors can be done very efficiently supported by FAISS; a forward computation through the lightweight gating network is also efficient.

4 Experiments and Analyses

4.1 Datasets

YOOCHOOSE: This is a public dataset for RecSys Challenge 2015. 2 It contains click-streams on an e-commerce site over 6 months. Events in the last week are tested. Following [Tan et al., 2016; Li et al., 2017], we use the latest 1/4 training sequences because YOOCHOOSE is very large.

2 http://2015.recsyschallenge.com/challenge.html

DIGINETICA: This dataset contains click-streams data on another e-commerce site over a span of 5 months for CIKMCup 2016. 3 Events in the last four weeks are tested.

Items that appear less than five times, and sessions of length shorter than two or longer than 20 are filtered out. Statistics of the two datasets after pruning are summarized in Table 1, and the last 10% of the training data based on time is used as the validation set. Different from previous static settings that remove items not in the training phase from test sets, our test sets for the incremental SR task include events on new items that appear only during the testing phase. The last column indicates the percentage of events in the test data that involve items not part of the training data.

4.2 EvaluationMetrics

HR@k: Average hit rate when the desired item is amongst the top-k recommended items. It can be interpreted as precision [Liu et al., 2018; Wu et al., 2019] or recall [Hidasi et al., 2016; Li et al., 2017; Jannach and Ludewig, 2017] because we predict the immediate next event.

MRR@k: HR@k does not consider the order of the items recommended. MRR@k measures the mean reciprocal ranks of the desired items in top-k recommended items.

4.3 Models and Training Details

A wide range of neural and non-paramtric session-based recommenders are compared:

Item-KNN: This simple baseline recommends top items similar to the single last item in the current session based on co-occurrence statistics of two items in other sessions.

(S)-SKNN: Instead of considering only the last item, SKNN [Jannach and Ludewig, 2017] compares all items in the current session with items in other sessions. S-SKNN [Ludewig and Jannach, 2018] is an improved version that assigns more weights to items that appear later in a session.

CT [Mi and Faltings, 2018]: It builds a nonparametric recommender based on a structure called Context Tree to model suffixes of a sequence.

GRU4Rec [Hidasi and Karatzoglou, 2018]: It uses an RNN with GRU as encoder. It also uses specialized ranking-based losses computed w.r.t. the most relevant samples, which perform better than their initial version [Hidasi et al., 2016].

NARM [Li et al., 2017]: It improves the encoder of GRU4Rec with an item-level attention and replaces the decoder by a bilinear decoding scheme.

MAN (proposed): The method proposed in this paper. Two versions (MAN-GRU4Rec and MAN-NARM) are tested using GRU4Rec and NARM as base neural models respectively. Unless mentioned specifically, MAN is based on NARM. 4

3 http://cikm2016.cs.iupui.edu/cikm-cup

During training, hidden layer size of GRU4Rec and NARM is set to 100, and the item embedding size of NARM is set to 50; the batch size is set to 512 and 30 epochs are trained for both models. Hyper-parameters of different models are tuned on validation splits to maximize HR@5. The number of nearest neighbors of MAN is set to 50 for YOOCHOOSE and 100 for DIGINETICA. During testing, we update different neural models and MAN incrementally using a single gradient descent step as every batch of 100 events are tested. Learning rates for neural models are 5e-4 and 1e-4 for YOOCHOOSE and DIGINETICA, and the learning rate to update the gating network is 1e-3. Other pure nonparametric methods (Item-KNN, (S)-SKNN, CT) are also incrementally updated as every batch of 100 events is tested.

4.4 Experiment Results

In this section, we first study the effect of using different learning rates to update neural models incrementally. Then, we analyze the overall performance of different methods and plot the incremental performance of two representative methods as more events are tested.

Effect of incremental learning rate. Before we proceed to our main results, we first highlight that the degree of updates is important when neural models are updated incrementally. As an example, we show results of using different learning rates to update NARM in Table 2. We can see that using large learning rates 5 to incrementally update NARM degrades performance severely, while using relatively small learning rates outperforms the version when NARM is fixed during testing (η = 0). We believe that large learning rates cause the model to overfit new patterns while catastrophically forgetting old patterns. Therefore, we contend that incremental updates for neural models needs to be small.

4 In this paper, we chose the two most representative base neural models (GRU4Rec and NARM) to evaluate MAN. As MAN is agnostic to the neural model, the exploration of using MAN on top of other neural recommenders is left for future work.

5 Using multiple incremental training epochs has a similar effect as using large earning rates in one epoch.

Overall performance. The results of different methods on two datasets are summarized in Table 3. Several interesting empirical results can be noted: First, MAN-NARM achieves the top performance. Both MAN-NARM and MAN-GRU4Rec consistently outperform their individual neural modules (NARM and GRU4Rec) with notable margins. This result shows that our MAN architecture effectively helps standard neural recommenders for incremental SR scenarios. Second, MAN is not sensitive to neural recommenders. We observed that even though NARM significantly outperforms GRU4Rec, MAN-GRU4Rec and MAN-NARM show comparable performances. We contend that the memory predictions effectively compensate the failed predictions of GRU4Rec. Third, (S)-SKNN and CT are much stronger nonparametric methods than Item-KNN, with CT being slightly better. They both outperform GRU4Rec on two datasets, and their performance gaps compared to MAN and NARM are smaller on the YOUCHOOSE dataset that contains more new events.

Incremental performance. In Figure 2, we present incremental performance of MAN and NARM as more events are evaluated during testing. We also included versions that are fixed during the testing phase. In NARM-Fixed, the neural model is fixed. In MAN-Fixed, both the neural model and the gating networks are fixed, and only memory entries are incrementally expanded. Several results can be noted from Figure 2. First, MAN helps to boost performance both when Table 4: Ablation study for MAN. The large memory size and the gating network of MAN gain performance benefits.

the neural model is fixed and incrementally updated. MAN outperforms NARM by consistent margins, and MAN-Fix outperforms NARM-Fix by increasing margins. Second, incrementally updated models consistently outperform their fixed versions. Both MAN and NARM outperform their corresponding fixed versions with significant and increasing margins.

4.5 In-depth Analysis

In the following experiments, we conduct in-depth analysis to further understand the effectiveness and efficiency of different components of MAN and for what types of events MAN most improves predictions.

Ablation study. We further studied in Table 4 the effect of two setups in MAN, i.e., the large memory size and the combining scheme with a gating network. Two simpler versions are compared. (i) MAN-Shallow linearly combines neural and memory predictions with a fixed scalar rather than the weight output by the gating network. The scalar weight is tuned on validation splits to be 0.7 for YOOCHOOSE and 0.8 for DIGINETICA. This simple method serves as a strong baseline in learning new vocabularies in language model tasks [Merity et al., 2017; Grave et al., 2017a]. (ii) MAN-50k/10k use fixed-size memories that only store a limited number of recent events (50k/10k). MAN-Shallow is consistently inferior to MAN. It means the gating network makes a better decision to combine neural and memory predictions. Furthermore, the performance drops as the size of the memory decrease from unbounded (MAN) to 50k, and to 10k. It means that keeping a big memory that handles long histories achieves better recommendation performance. Despite the slight performance drop, the three simplified versions are more efficient, therefore, they are still suitable candidates for industry.

Visualization of gating network outputs. In this experiment, we further visualize the empirical distribution of the gating network outputs assigned to the parametric part. We demonstrate in Figure 3 that it indeed learns desired weight distributions to the parametric and non-parametric parts. For new items denoted by the red curve, outputs of the gating network tend to be small such that larger weights are assigned to the non-parametric memory prediction. Similarly, for old items denoted by the blue curve, outputs of the gating network tend to be large such that smaller weights are given to the non-parametric memory prediction.

Computation time. In Table 5, we report the total training time and average response time per recommendation of MAN compared to NARM. Both models are trained using a NVIDIA TITAN X GPU with 12GB memory. We can see that the extra training time and response time of MAN is trivial on top of the NARM. This empirical results, together with our analysis in Section 3.5, demonstrate that MAN is computation efficient.

Disentangled performance. To further understand for what types of events that MAN most improves predictions, we studied the disentangled performance when items are bucketed into five groups by their occurrence frequency in training data. Bucket 1 contains the least frequent items, and bucket 5 contains the most frequent items. Bucket splitting intervals are chosen to ensure the bucket size is the same. The disentangled performances of MAN and NARM across five buckets are reported in Table 6, and the results reveal that:

• Infrequent items are more challenging to predict. The performances of both methods have an increasing trend as item frequency increases.
• MAN is consistently better than NARM on all levels of item frequency.
• The improvement margin of MAN over NARM is very significant on infrequent items (small bucket number). Therefore, we contend that MAN it is especially good at learning new patterns and items with a small number of observations.

5 Conclusion

In this paper, we study neural methods in a realistic incremental session-based recommendation scenario. We show that existing neural models can be used in this scenario with small incremental updates, and we propose a general method called Memory Augmented Neural recommender (MAN) that is widely applicable to augment different existing neural models. MAN uses a efficient nonparametric memory to compute a memory prediction, which is combined with the neural prediction through a lightweight gating network. We show that MAN consistently outperforms state-of-the-art neural and nonparametric methods and it is particularly good at learning new items with insufficient number of observations.