Time-based Sequence Model for Personalization and Recommendation Systems

As a first step we pass each datapoint representing a sequence of events for a given user through an embedding layer that generates an embedding vector for each event. The use of an embedding layer is a standard step in deep learning solutions to the CTR problems [3, 13, 46].

We choose to use deep learning recommendation model (DLRM) [25] to express this embedding layer²²2Note that we stop DLRM one layer prior to the final output, where we have an embedding representation and before it is converted to a probability of a click by last layer of the model.. It accepts input continuous features x, a set of discrete features $\textbf{e}_{s}$ and generates an output embedding z. In particular, in our experiments we will be interested in three one-hot categorical features corresponding to user $\textbf{e}_{u}$, item $\textbf{e}_{i}$ and category $\textbf{e}_{c}$ as well as a single continuous feature x corresponding to time, as shown on Fig. 2. Notice that in DLRM categorical features get embedded into $\mathbb{R}^{d}$ using $\textbf{w}_{s}^{T}=\textbf{e}_{s}^{T}W$, where $W$ is a trainable weight parameter. On the other hand, continuous features are passed through the bottom multilayer perceptron (MLP), whose final dimension is the same as embedding dimension of all categorical features. In the following step we take all pairwise dot products between dense and categorical features. The final step of DLRM takes these dot products combined with embedded dense feature and passes it through the top MLP resulting in a vector $\textbf{z}\in\mathbb{R}^{n}$.

As a result of the application of DLRM to each position in the input sequence our output can be thought of as a time series in $\mathbb{R}^{n}$. We use notation $\textbf{z}_{t}$ for DLRM output of item at position $t$, and $\textbf{z}_{\tau}$ for the output of the last item.

The time series layer (TSL) is designed specifically for time series processing. The high-level purpose of this layer is to relate the time series vectors to the last item. In this layer we compute the similarities between the sequence of vectors $Z=[\textbf{z}_{1},\ldots,\textbf{z}_{\tau-1}]$ and the last item $\textbf{z}_{\tau}$, pass them though a MLP to create coefficients a and produce a context vector $\textbf{c}=Z\textbf{a}$ as shown in Fig. 3. We will use several such layers when composing the full model in the next section. Also, we point out that this scheme resembles an attention mechanism, with a few small but important modifications that will be discussed next.

The first modification is that the vectors $\textbf{z}_{t}$ are normalized by projecting them onto a unit sphere $\mathbb{S}^{n}$:

$$\textbf{z}_{t}=\textbf{z}_{t}/||\textbf{z}_{t}||_{2}$$

(8)

Also, we replace the dot product by one or more positive definite inner products

$$\langle\textbf{z}_{t},\textbf{z}_{\tau}\rangle=(A\textbf{z}_{t})^{T}(A\textbf{z}_{\tau})=\textbf{z}_{t}^{T}(A^{T}A)\textbf{z}$$

(9)

for some nonsingular matrix $A\in\mathbb{R}^{n\times n}$. The inner product achieves two inter-dependent goals: (i) capturing label dependence on coupling between time series in different coordinates of the embedded space, and (ii) learning different similarity measures in the embedded space.

Note that in combination with spherical projection dot product becomes a cosine similarity, a measure widely used in natural language processing (NLP) [36]. We also may view inner product between projected vectors as a more general similarity measure as compared to cosine similarity. We remark that the connection with NLP can be elucidated if we think of analogy of item vocabulary to word vocabulary, and probability of last item corresponding to probability of next word under a specific language model. The difference with NLP case is the size of vocabulary, which in our case can easily exceed tens of millions of items.

Let us now point out how our attention-like mechanism is different from multi-head attention [39]. Recall that in multi-head attention the similarity between key and query is constructed via

$$\langle\textbf{w},\textbf{v}\rangle=(F\textbf{w})^{T}(G\textbf{v}),$$

(10)

where $F$ and $G$ are matrices whose dimensions are chosen so that their outputs have same dimensionality. We remark that in our case we do not need to map a pair of vectors into a common space since they are already in the output space of DLRM embedding layer. Therefore, there are three major differences of our approach as compared to multi-head attention. First, there are fewer trainable parameters since it involves only one matrix $A$. Second, the weighting has a clear geometric interpretation since cosine similarity is directly related to a distance function on the unit sphere

$$D(\textbf{w},\textbf{v})=\frac{\cos^{-1}(\langle\textbf{w},\textbf{v}\rangle)}{\pi}$$

(11)

Finally, when using multiple TSLs, we will pair them with individual MLPs, while in multi-headed attention a single shared MLP is used for all. While these differences seem small, we will show in our experiments that they result in major improvement in the statistical performance of the model.

Let us now compose all layers together into a single model, that will be referred to as time-based sequence model (TBSM).

Notice that the output of embedding layer corresponding to (5) and TSL corresponding to (6) can be concatenated and supplied as an input $[\textbf{z}_{\tau},\textbf{c}]$ to the MLP which would produce probability of a click $p$.

Further, we may choose to use multiple TSLs, with different similarity measures between vectors, or even using different sequence lengths for each of them. In this case, we obtain $k$ concatenated outputs $[\textbf{z}_{\tau},\textbf{c}_{i}]$ and pass each of them through an independent MLP, resulting in a distinct probability $p_{i}$ for $i=1,...,k$. Once again note that this approach resembles the use of multiple heads in an attention mechanism [18, 35, 40, 43], but aside from the use of spherical projection in (8) and well defined inner products in (9), the output uses individual rather than shared MLPs.

Finally, note that we can interpret each $p_{i}$ as a probability obtained by using the corresponding similarity measure. We can also think of them as being produced by an ensemble of models [1, 11, 38]. In this scenario, the last MLP determines their contribution to the final probability of click $p$. The comprehensive design of TBSM showing all of these components together is outlined on Fig. 4.

In synthetic dataset we let a datapoint be a time series, with each position in the series being a randomly generated vector in $\mathbb{R}^{n}$. This has a similar structure to Taobao train dataset after it passes through model’s embedding layer, except that the binary label is made to explicitly depend on series data as follows.

Let us denote the first $\tau-1$ vectors in time series by $\textbf{z}_{i}$ and the last vector by $\textbf{z}_{\tau}$. Also, let $\tilde{\textbf{z}}$ denote a sum of $\delta$ (zero or more) vectors, each obtained by a random permutation of $n$ coordinates of $\textbf{z}_{\tau}\in\mathbb{R}^{n}$. Then, define the corresponding click/non-click label $l$ and function $f$ to be

	$\displaystyle l$	$\displaystyle=$	$\displaystyle\texttt{sign}(f)$		(12)
	$\displaystyle f$	$\displaystyle=$	$\displaystyle\sum_{i=1}^{\tau-1}{f_{1}(\langle\textbf{z}_{i},\textbf{z}_{\tau}\rangle)+f_{2}(\langle\textbf{z}_{i},\tilde{\textbf{z}}\rangle)}$		(13)

where $\langle.,.\rangle$ denotes an inner product. Note that the first term $f_{1}$ is a function of inner products between time series elements $\textbf{z}_{i}$ and $\textbf{z}_{\tau}$, while the second term $f_{2}$ contributes “mixed” products of coordinates in $\mathbb{R}^{n}$ (e.g. $\textbf{z}_{i}(1)\textbf{z}_{\tau}(2)$). We can control “complexity” of the dataset because we have a summand in $f_{2}$ for each permutation of vector $\textbf{z}_{\tau}$. If $f=f_{1}$, i.e. there are no mixed terms, then our time series in $\mathbb{R}^{n}$ can be thought of as $n$ independent time series in $\mathbb{R}^{1}$ that are completely decoupled from each other. The more summands we add into $f_{2}$ the stronger is coupling between time series in different coordinates. We will use this interplay to test different components of the model.

The raw Taobao User Behavior dataset has a total of about 4M items, 10K categories and 1M users. It is organized into a set of time series parameterized by a user. Each entry in the time series for a given user is a triple $(i,c,t)$, where user interacted with the item “$i$” belonging to category “$c$” at time “$t$”⁴⁴4For example, “soccer ball” and “sports” could be a valid item-category pair..

The processed Taobao User Behavior dataset is obtained from the raw dataset and organized into a set of datapoints, split across taobao_train.txt and taobao_test.txt files. We note that train dataset contains about 9M points, while test dataset contains a bit more than 296K points. A datapoint in processed dataset corresponds to a specific user and consists of

1. (i)

   user id $u$

2. (ii)

   pair of item and category id $(i,c)$

3. (iii)

   randomly generated (50/50 chance) binary label $l$

4. (iv)

   200 pairs $(i,c)$ which encode user’s true behavior

5. (v)

   200 pairs $(i,c)$ randomly taken from the full dataset of 4M items, but that are different from user’s true behavior

Notice that for a given user the sequence (iv) represent positive samples, i.e. clicks, while sequence (v) can be used to generate negative samples, i.e. non-clicks. Further, for users who have interacted with less than 200 items, the true behavior sequence is padded with zeros in front. In case user has longer than 200 item history, it is truncated at 200. The $200$-th point of true behavior sequence is special: if label $l=1$ the pair $(i,c)$ in (ii) is taken for true user history, otherwise if label $l=0$ the true point is replaced with randomly generated fake one taken from sequence (v).

7 123 50 1   0,45,12,...123  0,17,89,...50   98,112,75,... 43,765,14,...

For a fixed user behavior sequence length $\tau\leq 200$, the train and test datasets are constructed using the following scheme. For the train dataset, positive datapoints (with label $l=1$) are constructed by taking contiguous subsequences of length $\tau$ from $200$-item long full sequence starting at random position. The negative datapoints (with label $l=0$) are constructed by replacing the item id following the chosen subsequence of length $\tau-1$ by an item chosen from the randomly generated 200-item sequence for this user. For the test dataset, we always take last $\tau$ items for each user with the provided label, so no replacements are made in this case.

Finally we append user $u$ and time $t$ by taking $\tau$ equally-spaced values between $0$ and $1$ to each pair $(i,c)$ in length $\tau$ subsequence. Therefore, resulting in a final datapoint consisting of $\tau$ tuples $(u,i,c,l,t)$. Note that we think of each datapoint as a known time series of length $\tau-1$ and the last item whose probability we are trying to predict.

In synthetic dataset the binary label encodes varying degree of coupling between coordinates in a time series vector. Let $\delta$ be the number of summands in $\tilde{\textbf{z}}$ in the second term in (13) which reflects it. Let us consider the model where TSL uses similarity $\langle.,.\rangle$ measured by standard single dot product or multiple inner products defined in (8) and (9), as summarized in Tab. 1.

Notice that when there is no coupling between time series in different coordinates ($\delta=0$) the model using dot product in TSL has the best performance among the tested models. However, when strength of the coupling between coordinates increases (higher $\delta$) the performance for all models naturally deteriorates, but models with multiple inner products start to outperform the one with a single dot product, as shown on Fig. 5. Notice also that in this experiment 8-head attention model is doing no better than a random model, while TSL significantly outperforms it.

Let us now study the behavior of different variations of TBSM. We consider different similarity measures, number and lengths of sequences as well as different attention and LSTM-based mechanisms for processing time series data.

First, we experiment with different similarity measures in TSL. We let DotSim($\mathbb{R}^{n}$) refer to dot product in Cartesian coordinates, while GenSim($\mathbb{S}^{n}$) refer to inner product on a unit sphere computed using (8) and (9). Also, we test the performance of indefinite inner product refered to as IndSim($\mathbb{S}^{n}$), where we replace inner product in (9) through symmetric positive semi-definite matrix $A^{T}A$ by an inner product through a nonsingular matrix $A$, thereby allowing similarity to take negative values. At last, we let CosSim($\mathbb{S}^{n}$) refer to the model where after the unit sphere projection we apply dot product. Note that since dot product is a special case of inner product, all these variants of defining similarity measure between two vectors can be succinctly described as optionally doing the unit sphere projection followed by a particular type of inner product.

In order to compare GenSim($\mathbb{S}^{n}$), DotSim($\mathbb{R}^{n}$) and CosSim($\mathbb{S}^{n}$) similarity measures within TBSM, we record the corresponding mean $\mu$, standard deviations $\sigma$ and range $\rho$ of their AUC scores, which are $0.0023$ for the former and $0.0027$ for latter model. Assuming that AUC is normally distributed with given means and standard deviations the estimated chance that GenSim($\mathbb{S}^{n}$) performs better than DotSim($\mathbb{R}^{n}$) is $95\%$, as shown on Fig. 6. Finally, the loss and accuracy obtained during training of the best GenSim($\mathbb{S}^{n}$) model are shown on Fig. 7. Notice that the convergence shows the standard training L-shape curve, as expected.

Then, we experiment with different number and setup of TSLs. We let TSL (k-inner) designate a model with $k$ TSLs, each with its own inner product similarity measure on the unit sphere (after projection). We point out that GenSim($\mathbb{S}^{n}$) is a special case of TSL(k-inner) model with $k=1$. Moreover, we also test the use of different lengths subsequences. The idea of TSL(k-seq) approach is to directly amplify influence of most current items in the datapoint’s time series. To achieve this effect we compute context vector not only for the full $\tau=20$ series but also for the most recent $\tau=5$, $\tau=10$ and $\tau=15$ subsequences. In this case, the output of TSL consists of four pairs $(\textbf{z}_{\tau},\textbf{c}_{t})$, where $\textbf{c}_{t}$ is a context vector for the corresponding subsequence. This method can also be viewed as an example of ensemble technique, where instead of having different models we provide the same model with different data.

Third, we compare the performance of TBSM with TSL we have proposed versus two standard mechanisms for processing time series data. The first mechanism uses standard multi-head attention (MHA) with 8 heads to replace the TSL. Note that the output of TSL is one pair $(\textbf{z}_{\tau},\textbf{c})$, where c is the usual output of 8-head attention mechanism. Unlike the model with GenSim($\mathbb{S}^{n}$) here we map time series vectors into $\mathbb{R}^{n}$ (as opposed to $\mathbb{S}^{n}$) using Key and Query matrices, and weight normalization is done at the end using softmax function ensuring that the sum of weights across time series is $1$. Note that this normalization is across time series, while in our main model normalization (projection onto $\mathbb{S}^{n}$) is done for each time series vector individually.

The last mechanism replaces TSL with recurrent neural network based on LSTM cells [16]. These cells are sized to input and output $n$ dimensional vectors and are stacked into 5 vertical layers. In this case the output is a pair $(\textbf{z}_{\tau},\textbf{c})$, where c is the final hidden state. We remark that as compared to the default approach, LSTM model is not invariant under permutations of time series points.

The performance achieved by all of these variations is summarized in the Tab. 2. Notice that it is split into four parts following our experimental setup. The first part contains a class of smaller models, consisting of just one TSL. The best result in this class is achieved by the GenSim($\mathbb{S}^{n}$). The second class consists of larger models, the ones with more than one TSL. The overall best performing model TSL(8-inner) is in this class. The third class contains MHA- and LSTM-based models. Finally, we also add two well-known reference models MIMN [31] and DIEN [46] for comparison. Note that in our experiments TBSM significantly outperforms both of them.

We remark that although performance of all models was calculated over the same test dataset, train dataset for models presented in this paper is different from the one used for MIMN and DIEN. Our training data consists of datapoints which are random contiguous subsequences of length $\tau=20$ extracted from each user behaviour history, while the dataset which was used to train MIMN and DIEN models consisted of datapoints of full length history sequences for each user $\tau=200$. Therefore, we may conclude that in our experiments TBSM achieves higher statistical performance than existing more complex models, all while using shorter sequence lengths.