DMRAN:A Hierarchical Fine-Grained Attention-Based Network for Recommendation

1 Introduction

A user's next choice is relevant to her previous behaviors [Wang et al., 2018; Zhou et al., 2018; Zhu et al., 2018; Zhu et al., 2017]. Then, a typical personalized recommendation process can be naturally divided into the following steps: (1) modeling the users' historical behaviors to capture the potential co-occurrence relationship between different items; and (2) exploiting the co-occurrence relationship to predict the next item that a user is likely to interact with. Here, the co-occurrence relationships are also called sequential patterns or dependencies.

Recently, inspired by the success of the attention mechanism [Bahdanau et al., 2015], the related models equipping RNN with an attention mechanism have been proposed and achieved good results in recommendations [Chen et al., 2018; Khattar et al., 2018]. In contrast to RNN, the attention mechanism can maintain a variable-length memory, and thus provides complementary information to the sequence patterns attention modeled by RNN. In addition, it can reduce the online service delay and the time cost of offline training. Some studies [Wang et al., 2018; Zhou et al., 2018] adopt a structure that is only composed of the attention mechanism, as the attention computation is parallel compared to the sequential computation of RNN.

∗ corresponding author

Figure 1: An example of the difference between the one-dimensional attention and the multi-dimensional attention

Intuitively, a user interacts with an item, may just like some aspects of the item. For example, as shown in Figure 1, a user may buy a piece of clothing because of its style, rather than the brand. In other words, the impact of different features of an item on the next choice is different.

However, the existing attention based recommendations [Wang et al., 2018; Zhou et al., 2018; Chen et al., 2018; Yu et al., 2019; Yu et al., 2018] do not consider such different preferences. Specifically, this attention-based pooling can be formulated as Cj = ∑ni=1 aij ⃗ vi , where aij is a scalar and measures the dependency between itemi and itemj, or the attention of itemi to itemj. ⃗ vi is an abstract representation of the i-th item in user historical interaction sequence. In one-dimensional attention, each dimensional in ⃗ vi will multiply by the same value of aij, and thus, different abstract features/aspects of an item are assigned the same weight.

To this end, we propose Double Most Relevant Attention Network (DMRAN) to learn the sequential patterns for the next-item recommendation. Specifically, different from previous approaches, like ATEM [Wang et al., 2018] and LARN [Pei et al., 2017], this method encodes the time signal by converting continuous temporal features into discrete features, and then performs Item Level Attention and Feature Level Self-attention. By Item Level Attention, the uncorrelated interference items in the sequence of the historical behaviors are initially filtered out, and thus it can reduce the size of the sequence. By Feature Level Self-attention, the different features of an item can be given different weights, and thus it can capture more fine-grained user preferences, which is a multi-dimensional self-attention. The main contributions of our work are summarized as follows:

• To the best of our knowledge, this is the first method that adopts two different levels of attention mechanisms simultaneously for recommendations, which can capture more fine-grained user preferences and generate a highlevel representation of a user.
• Our DMRAN has the advantages of one-dimensional attention and multi-dimensional self-attention at the same time, i.e., the good efficiency and effectiveness.
• We perform extensive experiments on two real-world datasets. The results show our model outperforms the state-of-art methods in terms of Area Under Curve (AUC) and the training time.

2 RelatedWork

2.1 Sequential Recommendation

Recurrent Neural Networks (RNN) together with its variants LSTM and GRU have been widely applied in sequential recommendation, including session-based GRU [Hidasi et al., 2016], dynamic recurrent model [Yu et al., 2016], and hierarchical personalized RNN model [Quadrana et al., 2017]. These RNN-based methods encode historical interaction records into a latent state vector representing the preferences of a user. Although the state vector is able to capture sequential patterns, it still suffers from several issues. For example, it can hardly to be parallelized, and has low efficiency. In addition, it can hardly to preserve long-term dependencies, and emphasize the impact of the recent behaviors excessively.

Inspired by the capability of extracting local features and good efficiency, CNN has been used in sequential recommendation. Similar to the sentence embedding task [Vieira and Moura, 2017], Caser [Tang and Wang, 2018] uses the 1-D convolution layer and the max-over-time pooling layer to encode historical interactions into a vector to represent the preferences of a user. However, in CNN, the fixed-size encoding vector may not support both short and long sequences well.

2.2 Attention and Self-Attention

Attention has been widely used in, such as machine translation task [Bahdanau et al., 2015], and reading comprehension [Cui et al., 2017; Cheng et al., 2016], as it can preserve the highly related elements by assigning different weights for each element in a sequence. For the next-item recommendation, the attention-based transaction embedding model (ATEM) [Wang et al., 2018] can learn an attentive context embedding that intensifies relevant items but downplays those irrelevant to the next choice. Different from attention, self-attention considers the inner-relations of a sequence, and thus can learn the sequence patterns and internal dependencies. Following the structure of Transformer [Vaswani et al., 2017], ATRank [Zhou et al., 2018] transforms the interaction sequence into a new sequence via self-attention, and has achieved good performance in the next-item recommendation.

3 ProblemFormulation

We first define notations used throughout the paper, and then formalize the problem.

Let U = {u1, u2, . . . , u|U|} denote the set of users and I = {i1, i2, . . . , i|I|} denote the set of items, where |U| and |I| denote the number of elements in the set of User U and Item I respectively. Our task focuses on personalized recommendation, where we concern whether a user u ∈ U had interacted with an item i ∈ I at relative time index t. Hence each interaction record can be formulated as a trituple it (u) = 〈u, i, t〉. By sorting the interaction records in ascending order according to the corresponding time signal, we can form an interaction sequence for user u, denoted as Su = (i1 (u) , i2 (u) , ...in (u) ), where n is the length of the interaction sequence.

The task of personalized recommendation aims to rank all items in a candidate set based on their probabilities that a user will interacted with at the next time. Formally, the problem can be defined as follows.

Input: The interaction sequences of all users, namely S = {S1, S2, ...S|U|}.

Output: A personalized ranking model for recommendation, denoted as frec, which can output the k items that the corresponding user is most likely to interact with at the next time, when entering a user's interaction sequence Su.

4 Double Most Relevant Attention Network

The overall architecture of DMRAN is shown in Figure 2. Next, we discuss each of them in detail.

4.1 Input EmbeddingWith Time Signals

Similar to discrete word symbols in natural language processing [Mikolov et al., 2013], the original item IDs have very limited representation capacity. Therefore, our model first employs a fully connected layer to embed item IDs (i.e., one-hot representations) into a continuous low-dimensional space. Formally, let V ∈ Rde×|I| be a matrix consisting of the item embedding, where de is the dimensionality of the latent embedding spaces. In addition, to compensate for the loss of temporal order information caused by abandoning the sequence model RNN, following the ATRank [Zhou et al., 2018], we split the time signals based on days into multiple granularity, e.g., the continuous time signal in range of [0, 1), [1, 2), [2, 4), . . . , [2k , 2(k+1) ) can be mapped to the discrete feature 0, 1, 2, . . . , (k+1), and then we can get a matrix T ∈ Rde×(k+2) that includes the time signal embedding. It's worth noting that different behavior groups may have different granularities of time slicing. Finally, we can encode the behavior of a user it (u) = 〈u, i, t〉 as

where i-t is the result of t mapping; i and i-t index the ith and (i-t)th column of V and T respectively; ⊕ is the concatenation operator; dense() refers to a full connected layer. To keep the notations simple, in the rest of this paper, we ignore the subscript t and use ui to replace uit. Thus, the interaction sequence Su can be encoded as a 2-D matrix H ∈ Rn×de .

4.2 ItemLevel Attention

After the embedding, we will pick the informative items that can reflect the user's interests or relevant to the next choice from the corresponding interaction sequence. Thus, onedimensional attention can be adopted, like ATEM [Wang et al., 2018], where the items being more informative or relevant to the next choice are given larger weights. Specifically, the attention mechanism takes the interaction sequence H as input, and outputs a vector of weights a ∈ Rn :

where j ∈ {1, 2, ..., n}, Ws1 ∈ Rde×de , ws2 ∈ Rde , and the attention score e (uj) is a scalar. E.q. 4 ensures the sum of the computed weight αj equals 1.

Then we sum up the interaction sequence H according to the weight provided by a to get a vector m ∈ Rde :

where m can be seen as an abstract representation of the user's interests. Inspired by the discovery of sentence embedding task [Lin et al., 2017], this vector m focuses on a special set of related words or phrases, and only reflects an aspect of the overall semantics of a sentence. Analogy to our task, the vector representation m usually focuses a small proportion items in the interaction sequence, and thus cannot cover all interests of a user, especially for a long interaction sequence. Thus, to represent the multifaceted and overall preferences of a user, we perform multiple hops of attention and get multiple and different vectors that focuses on different component of the interaction sequence. For simplicity, the above process is formalized:

where ws2 ∈ Rde is extended into Ws2 ∈ Rr×de , softmax() is performed along the second dimension of its input, thus the vector a ∈ Rn becomes a weight matrix A ∈ Rr×n , and the embedding vector m ∈ Rde becomes a embedding matrix M ∈ Rr×de , where r is the number of components that are expected to be extracted from the interaction sequence.

The above attention makes our model focus on the items that can reflect the users' multifaceted interests and can reduce the interference from the irrelevant items. Thus it can be understood as a high level representation of one query "which items are informative or relevant to the next choice?".

4.3 Feature Level Self-attention

The affect of different features of an item to the next choice is different and there are even some irrelevant features which tends to overwhelm the influence of a few truly relevant ones. Thus, to capture more fine-grained user preferences, we give more attention on these relevant features, after picking out the relevant items. Specifically, we propose a feature level selfattention. Instead of computing a one-dimensional attention scalar score for each element of a sequence, the feature level self-attention computes a multi-dimensional alignment vector for any two elements of a sequence.

Suppose mi and mj are two vectors in embedding matrix M, which represent two different components of the interaction sequence H respectively, so the attention f (mi, mj) ∈ Rde betweenmi andmj is:

where all the parameter matrices Ws3,Ws4,Ws5 ∈ Rde×de , the two bias terms bs1,bs2 ∈ Rde , and tanh() is a nonlinear activation function.

Then, the alignment vector βij betweenmi tomj can be computed by normalizing along each dimension by E.q. 10 and E.q. 11 as follows.

where k ∈ {1, 2, ...de}, [∗]k indexes the kth dimension of the vector ∗, and a large [βij]k means that the kth abstract feature ofmj is strongly relevant withmi. Finally, the output of this attention mechanism is still a matrix and its shape is consistent with the corresponding M, denoted as ̂ M ∈ Rr×de :

Following the definition of Hadamard product 1 , we use "◦" to represent the element-wise product between two vectors with the same shape.

To sum up, the feature level self-attention computes a weight vector for each element. The more the relevant features of an item, the larger the weight. This can model more detailed dependencies between two interactions and capture more fine-grained user preferences. The above process can be viewed as another query "which features are the relevant ones over the relevant items?".

4.4 DownstreamApplication Network

After obtaining the matrix ̂ M and matrix M, we need to sort the candidate set Cu, according to the similarity between the user's interests and the corresponding item. The similarity is usually expressed by a score of scalar, and the higher the score, the higher the similarity [Zhou et al., 2018; Ying et al., 2018]. Specifically, following ATRank [Zhou et al., 2018], we employ vanilla attention and inner product to compute the corresponding preference score scorec of the candidate item c ∈ Cu, as follows:

where ic is the embedding of the candidate item c; the function fvanilla() represents the execution process of vanilla attention [Vaswani et al., 2017; Zhou et al., 2018] that maps the matrix M or ̂ M to a vector h ∈ Rde or ̂h ∈ Rde through the embedding ic, and the h or ̂h can be understood as a overlap between the candidate item c and the user's interests. For flexibility and simplicity, the function fvanilla() can be replaced by a mean operation along the second dimension of the matrix ̂ M or M in some scenarios; the function ffusion() refers to the fusion operation by a dimension-wise fusion gate [Shen et al., 2018].

4.5 Optimizing The Framework

Based on the above steps, we have built up the personalized recommendation model frec. Then we consider how to train this model.

Given the interaction sequence Su of user u, we take the first (t-1) items and the tth item from it, denoted Sc and it, respectively. Then, we can construct such set Du = {(Sc, it) | t = 2, 3, ..., n}. Recall our task is to predict the most likely item which will be interacted by the user at the next time, for the corpus S = {S1,S2, ...S|U|}, a natural optimization objective to maximize is:

1 https://en.wikipedia.org/wiki/Hadamard product (matrices)

With this definition, achieving the goal defined in E.q. 18 will force the item it to be the one that the user is most likely to interact at the next time. Nevertheless, optimising the objective function is non-trivial since each evaluation of the softmax function needs to traverse all items, leading to expensive time cost. To reduce the complexity, we employ the idea of negative sampling, which approximates the costly denominator term of softmax with some sampled negative instances [Mikolov et al., 2013; Yin et al., 2018].

Let NSu (Sc) denote the negative instance for Sc, where NSu (Sc) /∈ Sc, we can then approximate the conditional probability P (it | Sc) defined in E.q. 19 as:

where the probability P (z | Sc) is defined as:

where σ denotes the sigmoid function 1/ (1+ e-x ). By replacing P (it | Sc) in E.q. 19 with the definition of P (it,NSu (Sc) | Sc), we can get the approximated objective function to be optimized. Namely, the probability that the ground-truth sample appears as the next should be maximized, whereas the probability that the negative sample appears as the next should be minimized.

Finally, the objective function can be defined as:

where Θ is the set of model parameters; Θuv = {U, V } is the set of embedding of users and items; Θa is the set of weight in model; the last item ∥∥(AAT - I )∥∥2 is to punish redundancy between different vectors [Lin et al., 2017], and thus can learn multifaceted interests of a user.

5 Experiment

We aim to answer the following questions in our experiments:

• Q1. How does DMRAN perform in terms of efficiency and effectiveness, compared to the state-of-the-art methods?
• Q2. How do Item Level Attention (ILA) and Feature Level Self-attention (FLSA) affect the performance of DMRAN?
• Q3. How does the key hyper-parameter r (i.e., the number of rows in matrixM) affect the performance of DMRAN?

5.1 Experimental Settings

Dataset

We perform experiments on two real-world datasets. The details of them are shown in Table. 1.

The Amazon datasets [McAuley et al., 2015] accumulate user behavior log, and we adopt its two subsets: Electronics, and Clothing. For the interaction sequence (i1 (u) , i2 (u) , ...in (u) ) for user u, we use the first k interaction behaviors (i1 (u) , i2 (u) , ...ik (u) ) to predict the (k +1)th behavior ik+1 (u) in the training set, where k = 1, 2, . . . , n - 2, and we use the first (n-1) behaviors (i1 (u) , i2 (u) , ...in-1 (u) ) to predict the last one in (u) in the test set U t . In addition, in our experiments, like ATRank, the category information of each item is considered in Amazon Electronic dataset.

Evaluation Metrics

Same as ATRank [Zhou et al., 2018], our model is a ranking framework which aims to further sort the candidate set delivered by a candidate generation model. Therefore, we adopt the AUC metric shown in E.q. 23 to investigate how the positive samples being ranked over negative samples, which has been widely used in evaluating the performance of ranking frameworks in recommendations [Covington et al., 2016].

where I + u denotes the positive samples set for user u, and I - u denotes the corresponding negative samples set. pu,i is the predicted probability that a user u chooses item i in the test set U t , it can be calculated by E.q. 19. δ(·) is an indicator function which returns 1 if pu,i > pu,j , and 0 otherwise. Note that, the higher the value of AUC, the better the quality of the recommendation.

Baselines

We compare DMRAN with the following baseline methods, including one classic recommendation method (i.e., BPR-MF), three NN-based methods (i.e., Bi-LSTM, BiLSTM+Attention, and CNN+Pooling), and one attentionbased method (i.e., ATRank), that is the most promising recommendation method.

• BPR-MF [Rendle et al., 2009]: This method optimizes the matrix factorization (MF) model with a pairwise ranking-aware objective and aims to maximize the difference between positive and negative items. BPR-MF does not model the time signals.
• Bi-LSTM [Zhang et al., 2014]: This method implements an improved version of the Bi-LSTM network for the next-item recommendation and employs rankingbased loss functions for learning the model.
• Bi-LSTM+Attention: A vanilla attention [Vaswani et al., 2017] is add on the top of the Bi-LSTMmethod.
• CNN+Pooling [Tang and Wang, 2018]: This method adopts a 1-D convolution structure with max-pooling to extract user preferences from their historical behaviors.
• ATRank [Zhou et al., 2018]: Inspired by the great success of Transformer [Vaswani et al., 2017], this method exploits multi-head self-attention mechanism to model the users' interaction sequences for capturing user preferences.

In addition, to evaluate the impact of each part of our model, we compare DMRAN with its three variants, denoted as DMRAN No Time, DMRAN Item, and DMRAN Feature respectively. DMRAN No Time does not consider the time signal behind each historical behavior, DMRAN Item and DMRAN Feature remove Feature Level Self-attention and Item Level Attention from DMRAN, respectively.

Hyperparameter

All models are trained with stochastic gradient descent (SGD). The learning rate starts at 1.0. The batch size, L2loss weight, and the size of all hidden layers are set to 32 or 16, 5e-5 or 1e-4, and 128, respectively. For DMRAN, we apply a gird search in {2, 5, 8, 10, 15, 20} for the special hyperparameter r i.e., the number of rows as shown in E.q. 8. In addition, to ensure the robustness, the residual connection, layer normalization and feed forward network [Vaswani et al., 2017] are adopted for implementations.

5.2 Comparison Of Performance (Q1)

Table. 2 lists AUC values by the baseline methods, DMRAN and its variants in Amazon Electronic and Clothing datasets. From the table, we can observe:

1. DMRAN always achieves the best performance, compared with all other methods. Specifically, DMRAN improves 0.24% and 0.80% of AUC compared with the second best method (i.e., ATRank) in Amazon Electronic and Clothing datasets, respectively. This demonstrates the effectiveness of DMRAN in capturing the fine-grained user preferences.
2. DMRAN outperforms DMRAN No Time in Amazon Electronic dataset. Specifically, the relative performance improvement is 2.52% of AUC. This fact indicates the good effectiveness of modeling the time signals in some scenarios.

Figure. 3 shows the evolution of AUC values in the Amazon Electronic dataset along with the training procedure. We can see that DMRAN converges fast, and compared to ATRank, DMRAN does not lead to overfitting that causes a rapid drop in AUC. This indicates the efficiency and effectiveness of DMRAN in training the model parameters.

To sum up, compared to all baseline methods, DMRAN can get the best ranking result with a good efficiency.

5.3 The Impact of ILA and FLAT (Q2)

Item Level Attention and Feature Level Self-attention are two main parts of our model. We compare DMRAN with its two variants, i.e., DMRAN Item and DMRAN Feature.

From the Table. 2, we can see that DMRAN Item achieves better performance compared with DMRAN Feature. Based on the statistics, the AUC value of DMRAN Feature is 0.69% and 3.80% less than that of DMRAN Item in Amazon Electronic and Clothing datasets, respectively. In addition, the AUC value of DMRAN Item is only 0.15% and 0.16% less than that of the second best method (i.e., ATRank) respectively. This indicates that Item Level Attention is essential for our model and guarantees the effectiveness of DMRAN.

Figure. 4 shows the convergence process of DMRAN, DMRAN Item, and DMRAN Feature in Amazon Electronic dataset. We can see that DMRAN Item converges faster than DMRAN, and DMRAN converges faster than DMRAN Feature. The reasons are as follows.

1. Item Level Attention only computes a weight for each item, but Feature Level Self-attention computes different weights for each features of each item. Thus DMRAN Feature converges slowly than DMRAN Item.

(2) Item Level Attention makes the interaction sequence (i.e., H) into a shorter sequence (i.e., M), while extracting the relevant items. Thus, compared to DMRAN Feature, DMRAN converges faster.

In addition, as shown in Table. 2, the AUC value of DMRAN is 0.40% and 0.96% more than that of DMRAN Item in Amazon Electronic and Clothing datasets, respectively. This indicates that Item Level Attention can reduce the interference of items that are irrelevant to users' interests on Feature Level Self-attention.

5.4 The Impact of Multiple Vectors (Q3)

Figure. 5 shows the AUC values by DMRAN based on different r values in Amazon Electronic and Clothing datasets. We can observe:

1. When r = 2, the AUC value is the minimal in all the cases. Specifically, the AUC values with r = 2 are 0.40% and 1.08% less than that of the best performing DMRAN in Amazon Electronic and Clothing datasets, respectively. This indicates that multiple rows in the interaction sequence embedding matrix M can provide complementary information about the users preferences for better recommendations.

(2) The AUC value of DMRAN with r = 2 is 0.8896 in Amazon Electronic test set. With the increase of the r value to 8 and 10, the AUC value increases to 0.8921 and 0.8932, respectively. While when r reach to 15 and 20, the corresponding AUC values drop to 0.8915 and 0.8910, respectively. This is because: (i) At first, with the increase of r value, there will be more information about users' interests to be embedded in the matrix M, and thus the AUC value increases. (ii) However, when r reaches a large value, some useless information that does not match the users' interests will be embedded in the matrix M as well. Thus, the AUC value decreases.

6 Conclusion

In this paper, we have proposed a hierarchical fine-grained Attention-based network (DMRAN) for the next-item recommendation. Based on the two levels of attention mechanism with time encoding, DMRAN not only intensifies relevant items and downplays those irrelevant to the next choice, but also picks out the relevant aspects of the relevant items. Finally, the fine-grained and dynamic user preferences can be captured. Extensive validations on two real-world datasets have demonstrated the superiority of DMRAN against other state-of-the-art methods.

Acknowledgements

This work was supported in part by National Natural Science Foundation of China (NSFC) (Grant No. 61572336, 61836007, 61832017, 61532018), Natural Science Research Project of Jiangsu Higher Education Institution (No. 18KJA520010), and A Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).