{'fraction_non_alphanumeric': 0.03263467867659796, 'fraction_numerical': 0.011363242681448121, 'mean_word_length': 4.670005892751915, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Breaking the Softmax Bottleneck for Sequential Recommender Systems with Dropout and Decoupling

The Softmax bottleneck was first identified in language modeling as a theoretical limit on the expressivity of Softmax-based models. Being one of the most widely-used methods to output probability, Softmax-based models have found a wide range of applications, including session-based recommender systems (SBRSs). Softmax-based models consist of a Softmax function on top of a final linear layer. The bottleneck has been shown to be caused by rank deficiency in the final linear layer due to its connection with matrix factorization. In this paper, we show that there are more aspects to the Softmax bottleneck in SBRSs. Contrary to common beliefs, overfitting does happen in the final linear layer, while it is often associated with complex networks. Furthermore, we identified that the common technique of sharing item embeddings among session sequences and the candidate pool creates a tight-coupling that also contributes to the bottleneck. We propose a simple yet effective method, Dropout and Decoupling (D&D), to alleviate these problems. Our experiments show that our method significantly improves the accuracy of a variety of Softmax-based SBRS algorithms. When compared to other computationally expensive methods, such as MLP and MoS (Mixture of Softmaxes), our method performs on par with and at times even better than those methods, while keeping the same time complexity as Softmax-based models.


Introduction
Recommender systems are essential tools for online services to guide users through vast volumes of digital contents. As technology enables the Internet to become faster and more ubiquitous, the amount of online data is growing at an exponential rate. This rapid growth imposes challenges to both online service providers and their users with information overload. Designed to serve the purpose of filtering and prioritizing useful information, recommender systems have since found a wide range of applications in social media, eCommerce, and streaming services.
The Softmax bottleneck is a theoretical limit on the expressivity of Softmax-based models. It was first discovered by Yang et al. in language modeling. Language modeling faces a similar challenge as recommender systems when selecting the next word from a massive vocabulary. A linear-Softmax output layer is often adopted in these classification problems, when the number of labels is several orders of magnitudes larger than the dimension of hidden states. It consists of a Softmax function around logits, which are dot products between the hidden state and candidate word embeddings. The authors pointed out that its linearity causes the learned logit matrix to be low-rank. As a result, it limits the expressivity of the whole network, hence getting the name of the Softmax bottleneck.
Linear-Softmax layers are widely used in session-based recommender systems (SBRSs), which take a sequence of items in the session as input and predict the next item from a candidate pool. There are several reasons behind this. First, the accuracy of SBRSs really benefits from learning from the whole candidate pool, instead of having a candidate selection mechanism. Since the candidate pool is often massive in size, a linear-Softmax layer is almost the only computationally efficient choice. Second, the simplicity of linear-Softmax layers allows them to be accelerated substantially in production. The monotonic property of the Softmax function allows the logits to be used directly for ranking, and modern search engines support dot product ranking through spatial indices with logarithmic time complexity. The above reasons describe why Softmax output layers are almost unanimously adopted in SBRS research.
In this paper, we introduce more aspects of the Softmax bottleneck other than expressivity in the context of SBRSs. First, overfitting does occur in linear-Softmax layers. Often associated with complex and flexible networks, we show that overfitting could be a serious issue even in a dot product. We also show that with proper dropout layers, the accuracy of the whole network could be improved significantly on a variety of SBRSs. Second, although not always stated explicitly, the technique of sharing the item embeddings among session sequences and the candidate pool is almost adopted universally in research , Liu et al. [2018],  to boost performance. This tight-coupling simultaneously expects the embeddings to be the encoder inputs and also the weights in dot products. It could create interference that stops accuracy from further improvement. We show that a single layer of feedforward network could alleviate this problem.
Combining the above two ideas, we propose Dropout and Decoupling (D&D), a simple yet effective method that alleviates the previously mentioned problems. It also keeps the time complexity of linear-Softmax output layers in both training and query time. We compare our method to other computationally expensive methods, including MLP and MoS from Yang et al. [2018], and show that D&D performs on par with and at times even better than those methods. Our main contributions are summarized as follows: • We identify that overfitting is a prominent problem in Softmax-based session-based recommender systems.
• We show that sharing the item embedding layer among session sequences and the candidate pool introduces a tight-coupling that restrains performance in sessionbased recommender systems.
• We propose Dropout and Decoupling to effectively alleviate the above problems while keeping the same time complexity during both training and query.

Related Work
In this section, we will review related works on the Softmax bottleneck and recommender systems.

The Softmax Bottleneck
The Softmax bottleneck was first described by the work Yang et al. [2018] in language modeling. The authors identified linear-Softmax output layers as the source of limited expressivity. Natural languages are commonly believed to be highly diverse and context dependent Mikolov and Zweig [2012]. Modeling the probability logits using matrix factorization causes rank deficiency. To tackle this problem, MoS (mixture of Softmaxes) was proposed. As weighted mixtures of multiple Softmax components, MoS improves on both perplexity and rank of logit matrices. Several later works Yang et al. [2019], Kanai et al. [2018], Ganea et al. [2019] have proposed lightweight alternatives to the computationally expensive MoS, and also techniques to further improve MoS.

Session-based Recommender Systems
Session-based recommender systems learn user behavior from sequence data. Pioneer works in this field employs statistical models to capture sequential patterns. The problem has been formulated as decision tree learning Zimdars et al. [2001] and Markov decision process (MDP) Shani et al. [2002]. Later works Rendle et al. [2010], He and McAuley [2016] combine Markov chain with matrix factorization (MF) to model personalized behavior patterns.
Deep learning provides more sophisticated methods to encode user behavior sequences. RNN-based approaches Hidasi et al. [2016] were introduced to model sequential behavior. Later work Tan et al. [2016] enhances performance by proper data augmentation and considering temporal shift in data. CNN-based approaches Tang and Wang [2018] were also proposed. Dot-product attention , Liu et al. [2018] was introduced to capture user's current interests. Methods with self-attention Kang and McAuley [2018], Sun et al. [2019] were proposed to capture complex sequence patterns. GNN-based approaches  were also introduced to capture complex transitions between items.

Collaborative Filtering and CTR Prediction
Collaborative filtering (CF) tasks model interactions between users and items. They predict future interactions with a given set of past interactions. Pioneer works Salakhutdinov and Mnih [2007], Rendle et al. [2009] employed matrix factorization (MF) on user-item matrices. Autoencoder-based approaches Wu et al. [2016], Liang et al. [2018] were introduced to produce more robust reconstruction of user interactions. NCF He et al. [2017] generalizes MF and uses it in combination with MLP. CTR prediction tasks model click-through rate from more rich features. The features expand the data dimension and sparsity becomes a problem. To tackle this problem, wide & deep network Cheng et al. [2016] was proposed to use MLP with cross-product features. Many later works were inspired by this method. DeepFM Guo et al. [2017] combines MLP with a factorization machine (FM). DCN Wang et al. [2017] combines MLP with a proposed cross network.

Softmax Bottleneck in Language Modeling
We will briefly describe the Softmax bottleneck problem in language modeling, and the theoretical limit it imposes on the expressivity of the whole model.

Language Modeling
A language model consists of a vocabulary of words V = {x 1 , ..., x M } and a probability distribution P defined over all sentences in V, such as (x i1 , ..., x iT ). With factorization, P could be rewritten as a product of conditional distributions P (X 1 , ..., X T ) T t=1 P (X t |C t ), where C t = X <t is referred to as the context. This formula describes a random process which generates the next word in a given context. All sentences in the given corpus are assumed to be generated from a ground-truth distribution P * (X t |C t ). The goal of language modeling is to approximate P * with a parametric distribution P θ (X t |C t ).
The majority of language models adopt a Softmax output layer Yang et al. [2018]. In these models, a context, or an input sequence, is represented by a D-dimensional vector h j = f (c j ), where c j = (x j1 , ..., x jT ), and each word x i in the vocabulary are also represented by a D-dimensional vector w i . Then, the probability of the next word in a context is given by the linear-Softmax formula in equation 1.
θ is the parameters of the model. Training is done by optimizing the cross-entropy loss function in equation 2.
The Softmax Bottleneck The Softmax bottleneck comes down to the assumption that the ground-truth distribution of a language model could be approximated by the dot product of two low-rank matrices passed through a Softmax function. Let A ∈ R N ×M , H ∈ R N ×D , W ∈ R M×D denote the log of the groundtruth distribution, and the context representation matrix, the word embedding matrix respectively. In other words, denote the set of all matrices obtained by applying row-wise shift on A. They will all produce the same distribution P * due to the normalization property of the Softmax function. The linear-Softmax formula can approximate P * if and only if HW ⊤ approximates any matrix in F (A).
As shown in the original work Yang et al. [2018], the rank of HW ⊤ could not be greater than the number of dimension D, but the rank of A could be any number up to min(N, M ), which is usually several orders of magnitude larger than D. Combining with the fact |rank(A ′ ) − rank(A)| ≤ 1 for all A ′ ∈ F (A), it's almost certainly impossible for HW ⊤ to be in F (A). This expressivity limit caused by this rank deficiency is called the Softmax bottleneck.

Mixture of Softmaxes
To overcome rank deficiency, Yang et al. proposed where π j,k is the mixture weight of the k-th component and h j,k is the k-th context vector, shown in equations 4. The word embeddings are shared among all Softmax components to not significantly increase the model size.

Dropout and Decoupling
We will identify more aspects of the Softmax bottleneck problem, besides just expressivity, that restrain the accuracy of session-based recommender systems. Then, we will introduce Dropout and Decoupling, a simple yet effective method, to alleviate those problems.

Session-based Recommender Systems
Before going into details, we will first briefly describe session-based recommender systems (SBRS). A SBRS takes a session, or any of its prefix sequence, as input, and outputs a probability distribution over all candidate interactions to be the next one in the sequence. A session is a bounded sequence of interactions of a user with the system. The boundary is often defined at the end of a long period with no user activity. Since SBRSs with mixed action types are not discussed here, we will use the term items, the objects users interact with, to replace interactions from here. Figure 1 shows a high-level architecture of a general SBRS network. This architecture is adopted by the majority of state-of-the-art research Hidasi et al. [2016], , Liu et al. [2018], . The input consists of two parts: a sequence of session items, (x i1 , ..., x iT ), and a set of candidate items, {x 1 , ..., x N }. Both groups of items are converted into dense vectors by a shared item embedding. Then, the sequence of session item vectors, (v i1 , ..., v iT ), is encoded into a single vector representation, s, by a sequence encoder. Finally, both the session representation vector, s, and the candidate item vectors, {v 1 , ..., v N }, are fed into a probability encoder to produce output probabilities, In section 5, we will analyze Dropout and Decoupling on three representative SBRS models, which are GRU4Rec, NARM, and SR-GNN. All these three models fit into the architecture in figure 1, and adopt linear-Softmax layers as their probability decoders. They only differ in their sequence encoders, which are shown in more detail in figure 2. Using them as examples, we will show that Dropout and Decoupling could improve on a wide range of SBRS models.
GRU4Rec employs a GRU layer to encode session representations as h T shown in equation 5.
NARM applies a dot-product attention layer to the GRU outputs. Details of the attention layer is shown in equations 6, where q, c ∈ R D and W 1 , W 2 ∈ R D×D are model parameters. The bilinear layer described in the original paper is moved into probability decoders to fit in figure 1, and the final session representation becomes s.
SR-GNN replaces the GRU layer with a gated graph neural network (GGNN) Li et al. [2016]. It transforms ses-sion sequences into unweighted directed graphs. Item features are extracted by propagating information along both directions of the graph edges. The item features are then fed into the same dot-product attention layer in equations 6.

Overfitting in Linear-Softmax Layers
Overfitting is a phenomenon often associated with the model being more expressive than the data. However, it could still occur in networks as simple as a linear-Softmax layer. This counter-intuitive idea leaves this problem overlooked by previous work. Previous SBRS models mainly focus on the session and encoder dropout layers in figure 1a. We propose to add another candidate dropout layer, shown in figure 1b. In section 5, we will show that it significantly improves the accuracy of a wide range of SBRS models on a variety of datasets.
A linear-Softmax-based SBRS could be described mathematically by equations 7, where v i ∈ R E is an item embedding, f (·) is the sequence encoder, and s ∈ R D is the session representation. W ∈ R D×E is an optional matrix which is only required when the numbers of dimensions D and E are different.
During training, dropout layers are applied to the model. Equations 8 show this mathematically, and the last dropout function around v i is the candidate dropout layer that we've been proposing.

Tight-Coupling of Item Embedding Layers
Sharing the same item embedding layer among session and candidate items creates a tight-coupling between sequence encoders and probability decoders. It's a common technique that's been widely used in linear-Softmax-based SBRSs, shown in figure 1a. Hidasi et al. [2016], , . In practice, it's crucial to share learned information between sequence encoders and probability decoders through item embeddings for models to reach state-of-the-art accuracy.
This tight-coupling could also stop accuracy from further improvement through interference. The shared item embeddings are simultaneously expected to be the input of sequence encoders and also the weights used to measure its similarity with session representations. Figure 3a shows a block diagram of linear probability decoder. We propose to add a single feedforward layer, which consists of a linear  Dropout and Decoupling combines the two techniques mentioned above, shown in figure 1b. A candidate dropout layer is introduced to alleviate overfitting in the final linear layer. Depending on the dataset, an optional decoupling feedforward could be employed to loosen the tight-coupling between the sequence encoder and the probability decoder. We found Softplus works best among tanh, sigmoid, and ReLU as the activation function for the feedforward layer.

Rank Deficiency
Rank deficiency has been identified Yang et al. [2018] as the source of the Softmax bottleneck. The logits produced by a final linear layer form a low-rank matrix. Its rank is restrained by the number of hidden dimensions. MoS was proposed to tackle this issue. Figure 3d shows a block diagram of MoS. The session representation is encoded into K Softmax components by K feedforward layers with tanh as activation functions. Then, the output probability distribution is calculated as a weighted average over the components.
In user-based recommender systems, many works have proposed different ways to introduce flexibility to the network, and reach higher accuracy than the traditional matrix factorization (MF) method, which includes the equivalent of a Linear-Softmax layer. In particular, the idea of combining MLP and factorization machine (FM) has inspired numerous research works. We will include a version of these networks as probability decoder in section 5, and compare it against MoS and our D&D.  product of a session representation and a candidate item embedding both transformed by an individual linear layer.

Time Complexity Analysis
Time complexity is one important aspect of SBRSs during both training and query. Introducing complexity to the network could result in dramatic change in time complexity. During query, the time complexity is even more constrained. Breaking existing acceleration methods or requiring special operations could result in significant costs. We will focus our analysis on probability decoders in figure 3. Table 1 summarizes the time complexity of different probability decoders. We assume that the candidate pool size M is significantly larger than the other variables, which is over 10 4 in all our datasets. The batch number N , the number of hidden dimensions D, the size limit of query results L are of similar magnitude, which are usually around 10 2 . The number of MoS components K is usually around 10 1 .

Training Time Complexity
The time complexity of the linear decoder is O (N M D). The optional linear layer is omitted from the formula since the sequence encoder must have greater or equal terms. The decoupled decoder adds a feedforward layer to the candidate item embeddings. Since embeddings are the same for the whole batch, it could be calculated only once in each training step. Therefore, there's only an additional term O(M D 2 ), which could be omitted when M and N are of similar magnitude. The MLP decoder will increase the time complexity significantly to O(N M D 2 ). It might require candidate selection mechanisms to control the size of M and make training efficient. The MoS decoder has K Softmax components, and its time complexity is also K times higher.

Query Time Complexity
The time complexity of the linear decoder is O(D ln M + L ln L) for two reasons. First, since Softmax function preserves the order of logit values, it could be ignored for ranking. Second, a pre-built spatial index could be used to retrieve the top L dot-product values in log time. The decoupled decoder has the same time complexity as the linear decoder, because the results of the feedforward layer could be pre-computed. The MLP and MoS decoder could not be accelerated by conventional spatial indices. Therefore, their time complexities are linear to the candidate pool size M . Furthermore, the MoS decoder will require extra operations to calculate the denominator of K Softmax components, shown in equation 3. They both might need candidate selection mechanisms during query, which could hurt overall accuracy.

Experiments
In this section, we will first describe the setup of our experiments. Then, we will analyze the experiment results, and show the effect of Dropout and Decoupling.

Datasets and Preprocessing
We conducted our experiments on the following public real-world datasets from a wide range of different applications.
• Diginetica 1 was released at CIKM Cup 2016. It contains anonymized search and browsing logs collected from an e-commerce search engine over 6 months.
• RetailRocket 2 was released in a Kaggle contest. It contains sessions collected from a real-world ecommerce website over 5 months.
• Gowalla 3 Cho et al. [2011] contains check-in data collected from a geo-location-based social networking website over 21 months.
In preprocessing, we follow the common practice , Liu et al. [2018],  to remove items appearing less than 5 times and sessions with  Table 2: Statistics of datasets length 1. For Gowalla dataset, we split the user timelines into disjoint sessions at the end of each inactive period longer than 8 hours, and only keep items appearing no less than 20 times. Table 2 shows some statistics of the datasets after preprocessing, where # sessions does not include prefix sequences. In each session sequence, every element and its non-empty preceding sequence will be used as target and input of an individual sample. Preceding sequences are truncated to the latest 20 elements if its length exceeds this limit.

Algorithms
We applied our method to sequence decoders of the following representative works in SBRS to show that it's a general solution to the problems we mentioned. The encoders are also shown in detail in figure 2.
• NARM Li et al. [2017] employs RNNs with attention to capture users' main purposes and sequential behaviors.
• SR- GNN Wu et al. [2019] employs GGNNs with attention to obtain accurate item features through taking complex transitions of items into account.
We compared our decoupled decoder to the following decoders, which are shown in detail in figure 3.
• Linear consists of a final dot-product layer.
• Decoupled passes candidate item embeddings through a feedforward layer before the final dot-product layer.
• MLP performs entrywise products between candidate embeddings and session representations, and then passes the result through a final MLP layer.
• MoS Yang et al. [2018] recommends items similar to the previous item in the current session. Similarity is measured by a cosine index on the co-occurrence of items in the same session.
We also included some baseline algorithms for comparison, which could reveal different properties of each dataset.
• POP recommends the most frequent items in training set.
• S-POP recommends the most frequent items in the current session.
• Item-KNN recommends items similar to the previous item in the session. Similarity is measured by a cosine index on co-occurence of items in the same session.

Evaludation Protocol
We adopted the commonly used top-k metrics Hidasi et al. [2016], , Liu et al. [2018],  in our evaluation, which are HR@20 (hit rate, also called P@20 and Recall@20 with equivalent definitions) and MRR@20 (mean reciprocal rank). In order to produce unbiased results, each dataset is split into training, validation, and test sets. The most recent 10% of the time period is reserved for the test set, and 10% of the rest sessions are reserved for the validation set. Reported metrics are measured on the test set when the same metric reaches the highest point on the validation set. This prevents information from test and validation sets to leak into the model. Each datapoint is an average of 5 individual runs.

Parameter Setup
In order to have a common ground for comparison, the dimension of all hidden states and item embeddings are set to 100 for all models. We followed Tan et al. [2016],  to set the dropout ratios of GRU4Rec and NARM to 1 /4 for session embeddings and 0 and 1 /2 for encoder outputs, respectively. We adopted the same dropout scheme for SR-GNN as NARM, because we found it produces more stable results. In training, Adam is employed for optimization. The batch size is 200 and the learning rate is 10 −3 . There's no learning rate schedule and weight decay. For hyper-parameter tuning, we explored the following ranges: {0, 1 /8, 1 /4, 3 /8, 1 /2} for candidate dropout ratio, {1, 2, 3} for number of MLP layers, {2, 3, 4, 6, 8} for number of MoS components.

Performance Comparison
Intended to reveal basic properties of each dataset, the comparison of baseline models is shown in the top part of table 3. POP shows popularity-based recommendations generally perform poorly, while it's slightly better in Gowalla than in the others. S-POP shows session sequences are the most repetitive in RetailRocket and the least in Gowalla. Item-KNN shows the co-occurrence relation between items are the strongest in Gowalla and the Model Diginetica RetailRocket Gowalla HR MRR HR MRR HR MRR @20 @20 @20 @20 @20 @20  Table 3: Baseline Comparison weakest in RetailRocket. With the introduction of the attention mechanism and graph neural network, NARM and SR-GNN notably improve the performance over the pure RNN-based GRU4Rec on all 3 datasets. The comparison of linear-Softmax models is shown in the middle part of table 3.
Dropout and Decoupling significantly improve the performance of all sequence encoders on all datasets. Details are shown in the bottom part of table 3. There's two main effects to observe. First, the differences between sequence encoders become less significant. While our method enables all 3 sequence encoders to reach state-of-the-art performance level, the gap between them shrinks. This implies the overfitting and tight-coupling problems account for a significant part of the performance gap. Second, our method improves the most on RNN sequence encoder. It allows GRU4Rec to outperform more complex algorithms, NARM and SR-GNN, on Diginetica and Gowalla. It implies GRU4Rec is more susceptible to overfitting and tightcoupling. Our method provides an opportunity to revitalize RNN-based models.
The detailed comparison of probability decoders is shown in table 4, where the suffix δ indicates there's a candidate dropout layer. First, let's have a more detailed discussion on the optional decoupling feedforward layer in our method by comparing Linear-δ and Decoupled-δ. While overfitting is a general problem in linear-Softmax models, tight-coupling does not always harm performance. Decoupling generally improves performance with exceptions for GRU4Rec encoder and Gowalla dataset, where its effect is mixed. Second, more complex decoders, MLP-δ and MoSδ, could reach even higher performance metrics with much Decoder Diginetica RetailRocket Gowalla HR MRR HR MRR HR MRR @20 @20 @20 @20 @20 @20

Ablation Study
The importance of sharing item embeddings is shown by comparing SepEmb and Linear in table 5. SepEmb adopts separated embeddings for session and candidate items. The results show that metrics could drop significantly when sharing is not employed, especially in dataset Diginetica and RetailRocket. This partially explains why decoupling is more effective in these datasets, since the coupling tightens as the model learns more through shared embeddings.
The effect of candidate dropout layers is also shown by comparing table 5 to table 4. Universally, candidate dropout layers improve the performance of all models on all datasets in our evaluation. Conventional wisdom often associates overfitting with complex networks. In our experiments, candidate dropout layers are shown to be more effective in simpler networks, such as GRU4Rec encoder, Linear and Decoupled decoders. This implies that these simpler networks are actually more prone to overfitting.

Conclusions
The Softmax bottleneck is a serious problem in sessionbased recommender systems, that hasn't been examined by previous work. In this paper, the problem is investigated and more aspects of this issue are introduced. Overfitting Decoder Diginetica RetailRocket Gowalla HR MRR HR MRR HR MRR @20 @20 @20 @20 @20 @20  Table 5: Ablation Study in linear-Softmax layers and tight-coupling of item embeddings are identified as two major contributors to the bottleneck. Dropout and Decoupling (D&D), a simple yet effective method, is proposed to alleviate this bottleneck. Comprehensive experiments confirm that the proposed method can improve on a wide range of state-of-the-art models, while keeping the same time complexity during training and query.