End-to-End User Behavior Retrieval in Click-Through Rate Prediction Model

Qiwei Chen
Both authors contributed equally to this research.
Changhua Pei
[1]

Alibaba Group.

Shanshan Lv

Alibaba Group.

Chao Li

Alibaba Group.

Junfeng Ge

Alibaba Group.

Wenwu Ou

Alibaba Group.

Click-Through Rate (CTR) prediction is one of the core tasks in recommender systems (RS). It predicts a personalized click probability for each user-item pair. Recently, researchers have found that the performance of CTR model can be improved greatly by taking user behavior sequence into consideration, especially long-term user behavior sequence. The report on an e-commerce website shows that 23% of users have more than 1000 clicks during the past 5 months. Though there are numerous works focus on modeling sequential user behaviors, few works can handle long-term user behavior sequence due to the strict inference time constraint in real world system. Two-stage methods are proposed to push the limit for better performance. At the first stage, an auxiliary task is designed to retrieve the top-$k$ similar items from long-term user behavior sequence. At the second stage, the classical attention mechanism is conducted between the candidate item and $k$ items selected in the first stage. However, information gap happens between retrieval stage and the main CTR task. This goal divergence can greatly diminishing the performance gain of long-term user sequence. In this paper, inspired by Reformer, we propose a locality-sensitive hashing (LSH) method called ETA (End-to-end Target Attention) which can greatly reduce the training and inference cost and make the end-to-end training with long-term user behavior sequence possible. Both offline and online experiments confirm the effectiveness of our model. We deploy ETA into a large-scale real world E-commerce system and achieve extra 3.1% improvements on GMV (Gross Merchandise Value) compared to a two-stage long user sequence CTR model.

<concept_desc>Computer systems organization Embedded systems</concept_desc>
<concept_desc>Computer systems organization Redundancy</concept_desc>
<concept_desc>Computer systems organization Robotics</concept_desc>
<concept_desc>Networks Network reliability</concept_desc>

[500]Computer systems organization Embedded systems
[300]Computer systems organization Redundancy
Computer systems organization Robotics
[100]Networks Network reliability

§ INTRODUCTION

Recommendation systems (RS) are widely deployed to address the information overload problem. Among all those deep learning models used in RS, Click-Through Rate (CTR) prediction model is one of the most important one. Both industry and academy pay much attention on improving the AUC (area under the ROC curve) of CTR model in order to improve the online performance of RS. In the past decade, the performance of CTR model has been improved greatly.

One of the remarkable milestones is the introducing of user behavior sequence, especially the long-term user behavior sequence <cit.>. According to the report of <cit.>, 23% of users in an e-commerce website have more than 1000 clicks during the past 5 months. How to effectively utilize the massive and informative user behaviors has become more and more important, which is also the goal of this paper.

Various methods are proposed to model sequential user behavior data. Early approaches, such as the sum/mean pooling methods,  RNN-based methods <cit.>, CNN-based methods <cit.> and self-attention-based methods <cit.> encode different length of user behavior sequence into fixed dimensional hidden vector. However, they fail to capture the dynamic local interests of an user when scoring different candidate items. These methods also introduce noises by encoding all user historical behaviors.
To overcome the drawbacks of the global pooling methods, DIN <cit.> is proposed to generate various user sequence representations according to different candidate items by target attention mechanism, where the target candidate item acts as query $\bm{Q}$ and each item in the sequence acts as key $\bm{K}$ and value $\bm{V}$. However, due to the expensive computation and storage resources, DIN uses the recent 50 behaviors for target attention, which ignores the resourceful information in the long user behavior sequence and is obviously sub-optimal.

Recently, methods such as SIM <cit.> and UBR4CTR <cit.> are proposed to capture user dynamic interests from longer user behavior sequence and become the SOTA (state-of-the-art) methods. These methods act in a two-stage way. In the first stage, an auxiliary task is designed to retrieve the top-$k$ similar items from long-term user behavior sequence, such that the top-$k$ similar items are prepared in advance. In the second stage, the target attention mechanism is conducted between target item and $k$ items selected in the first stage. However, the information used for retrieval stage is divergent or outdated with the main CTR model. For example, UBR4CTR <cit.> and SIM <cit.> use attributes such as category to select items from user behavior sequence which share the same attribute with target candidate item, which is divergent with the target of CTR model. SIM <cit.> also tried to building an offline inverted index
based on the pre-trained embedding. During training and inference, the model can search the top-$k$ “similar” items. But most of the CTR model is in online learning paradigm and the embedding is updated continuously. Thus the pre-trained embedding in offline inverted index is outdated compared with the embedding in online CTR model. Whether the divergent target or the outdated retrieval vector, it will prevent the long-term user behavior sequence to be full utilized.

In this paper, we propose a method called ETA, enabling end-to-end long-term user behavior retrieval to mitigate the aforementioned information gap (i.e., divergent target and outdated embedding) in CTR prediction task. We use SimHash to generate a fingerprint for each item in user behavior sequence. Then the hamming distance is used to help select top-$k$ items for target attention. Our method reduces the retrieval complexity from $O(L*B*d)$ multiplication to $O(L*B)$ hamming distance calculation, where $L$ is the length of behavior sequence, $B$ is the number of candidate items to be scored by CTR model at each recommendation and $d$ is the dimension of item embedding. The reduction of complexity helps us removing the offline auxiliary model and conducting real-time retrieval during training and serving procedure. This improves the ranking improvements greatly compared with SOTA models. The contributions of our paper can be summarized in three-fold.

* We propose an End-to-end Target Attention method for CTR prediction task, which is called as ETA. To the best of our knowledge, ETA is the first work to model the long-term user behavior sequence with CTR model in an end-to-end way.

* Both offline experiments and online A/B tests show that ETA achieves significant performance improvements compared with the SOTA models. We get an extra 3.1% improvements on GMV after deploying ETA into a large-scale real world E-commerce platform when compared with a two-stage CTR model.

* Comprehensive ablation studies are conducted to reveal the hands-on practical experiences for better modeling sequential user behaviors under the limitation of inference time constraint.

* Our method can also be extended to other scenario to other models which need to handle extreme long sequence, e.g., long sequence time-series forecasting models.

§ RELATED WORK

CTR prediction task is one of the crucial tasks in recommender systems, online advertising and information retrieval. The CTR model predicts the probability of an user clicking on a certain target item. The output probability can be used as the ranking score for the downstream ranking tasks. The accuracy of CTR model can greatly affect the online performance of online systems. For example, in our online RS, 0.1$\%$ AUC improvement of CTR model can bring millions of real-world clicks and revenue. Tremendous works focus on improving the accuracy of CTR model in different ways, which can be divided into three categories: feature interaction, user behavior sequence and long-term user behavior sequence.

Feature Interaction: The intuition of feature interaction is to memorize the co-occurrence pattern in the feature space together with label. For example, a feature $AND(user\_installed\_app=netflix$, $impression\_app=pandora)$ can better capture the pattern for an user who clicked or did not click a certain recommended App. A series of works are published to model the feature interactions more effectively. The representative works are FM<cit.>, FFM<cit.>, GBDT$+$LR<cit.>, Wide&Deep<cit.>, FNN<cit.>, AFM<cit.>, DeepCross<cit.>, DeepFM<cit.>, PNN<cit.> and xDeepFM<cit.>. Various differences can be found between any two models, e.g., whether the deep learning technique is used, whether the embedding of weights and features are shared or whether feature engineering is needed.

User Behavior Sequence: The user behavior sequence is highly personalized for each user and contains spatio-temporal user interest information. Introducing the sequential user behaviors into CTR model is a remarkable milestone. Youtube<cit.> uses watched video sequence and search tokens in their model to capture the user interests. To better extract user interests from the user behavior sequence, various models are proposed, including CNN <cit.>, RNN <cit.>, Attention <cit.> and Capsule Network <cit.>. However, the user interest vectors learned from the above models are global for a certain user. DIN <cit.> proposes an attention based method called target attention to capture the diverse local interests for a certain user facing with different target items.

Long-term User Behavior Sequence: Despite the powerful ability to capture the diverse user interests, the computation of target attention is costly. The strict limit of online inference time prevents DIN-like models from using longer user sequence. MIMN <cit.> can handle long-term user behavior sequence by decoupling the user interest modeling with the rest of CTR task. The user interest vector is updated offline in an asynchronous way whenever a new behavior is observed. As there is no inference time limit offline, MIMN can model any sequence lengths theoretically. However, MIMN can not learn various user interest vectors for different target items. SIM <cit.> and UBR4CTR <cit.> defeat MIMN in CTR task and become the SOTA models. Both SIM and UBR4CTR adopt two-stage architecture to model long-term user behavior sequence. At first stage, an auxiliary task is designed to retrieval the top-$k$ similar items from long-term user behavior sequence. At second stage, target attention is conducted between target item and $k$ items selected in the first stage.

Besides the above related works on CTR prediction task, plenty of works aim to improve the efficiency and effectiveness of transformer. Reformer <cit.> and Informer <cit.> are the most relevant works. However, they only focus on the optimization of classical transformer and cannot be directly used on CTR prediction task because of the strict inference time constraint for large scale online recommendation systems.

§ PRELIMINARIES

In this section, we first give the formulation of CTR prediction task. Then we introduce how the fingerprint of a $d$-dimensional embedding vector is generated by SimHash mechanism.

§.§ Formulation of CTR Prediction Task

CTR prediction task is widely deployed in  online advertising, recommender systems and information retrieval. It aims to solve the following problem:

Given an impression $j$ where an item is displayed to an user, predict the probability of user click (labeled as $y_{j}$) using the feature vector $x_{j}$.

\begin{equation}
p_{j} = P(y_j=1|~x_{j};\theta); \textit{j} \in \mathcal{I}.
\end{equation}

CTR task is usually modeled as a binary classification problem. For each impression $j \in \mathcal{I}$, a binary label $y_j$ is recorded according to whether the item is clicked or not. Then CTR model is trained in a supervised way to minimize the cross entropy loss, which is shown as Equation <ref>, where $N$ is the number of impressions. $x_{j}$ and $y_j$ are feature vector and label of impression $j$ respectively. $\theta$ represents the trainable parameters of CTR model. For ease of presentation, we list the notations used in this paper in Table <ref>.

\begin{equation}
\begin{split}
\mathcal{L}_{CTR}(\theta) = - \frac{1}{N} \sum_{j=1}^{N} & ~ \Big(~ y_j*log(p_j) + (1-y_j)*log(1-p_j) \Big).
\end{split}
\label{eq:cross_entropy}
\end{equation}

Illustration of Locality-sensitive of SimHash for two vectors $\bm{x}$ and $\bm{y}$. The detailed implementation is shown in Algorithm <ref>. Each $d$-dimensional vector is converted to a $m$-length signature vector. Each random rotation here can be regarded as one “hash function”. The rotation is implemented by multiplying a random hash column vector $\bm{H}(i)$ (Line 2 in Algorithm <ref>). After random rotation, the spherical points are projected to signed axes (Line 3-7 in Algorithm <ref>).  Here we use 4 hash function and two projection axes to map each vector into 4 binary bits. We can observe that only those vectors who are close to each other can share more same 0/1(s), which is shown at the bottom part.

A $d$-dimensional embedding vector $\bm{e}_{k} \in \mathbb{R}^{1 \times d}$
A fix random hash matrix $\bm{H} \in \mathbb{R}^{d \times m}$, each column
can be regraded as one hash function.
A binary signature vector $\bm{sig}_{k} \in \mathbb{R}^{1 \times m}$ for $\bm{e}_{k}$.

$i \leftarrow 0$ $m-1$
$\bm{sig}_{k}[i] = \sum_{j=1}^{d}\indicator(\bm{e}_k[j]*H[j][i])$

$\bm{sig}_{k}[i] = 1$

$\bm{sig}_{k}[i] = 0$

Pseudo-code of SimHash algorithm.

§.§ SimHash

SimHash algorithm is first proposed by <cit.> and one of the well-known application is <cit.> which detects duplicate web pages by SimHash based fingerprints. SimHash function takes the embedding vector of an item as input and generates its binary fingerprint. Algorithm <ref> shows the pseudo code of one possible SimHash implementation. SimHash satisfies the Locality-sensitive properties: the outputs of SimHash are similar if the input vectors are similar to each other, which is illustrated in Figure <ref>. Each random rotation in Figure <ref> can be regarded as one “hash function”. The rotation is implemented by multiplying the input embedding vector with a random projection column vector $\bm{H}(i)$, which is shown in Line 2 of Algorithm <ref>. After random rotation, the spherical points are projected to signed axes (Line 3-7 in Algorithm <ref>). In Figure <ref>, we use 4 hash functions and two projection axes to map each vector into a signature vector with 4 elements. Each element in the signature vector is either 1 or 0. This vector can further be decoded using an integer to save storage cost and to speed up the following hamming distance calculation. From Figure <ref>, we can observe that nearby embedding vectors can get the same hashing signature with high probability (see the bottom part of Figure <ref> compared with the upper part of Figure <ref>). This observation is the so called “locality-sensitive” properties. With the local sensitive properties, the similarity between the embedding vectors can be replaced by the similarity between the hashed signature. In other words, the inner product between two vectors can be replaced by hamming distance. It is noteworthy that the SimHash algorithm is not sensitive to the selection each rotation “hashing function”. Any fixed random hash vectors are enough (see $\bm{H}(i)$ in Algorithm <ref>). It is easy to implement and can be easily applied to batches of embedding vectors.

ffn/.style = draw, rectangle, fill=yellow3, minimum width=3em, minimum height=1.5em,
item/.style = draw, rectangle, fill=blue1, minimum width=3em, minimum height=1.5em,
smallitem/.style = draw, rectangle, fill=blue0, minimum width=2.8em, minimum height=1.8em,
pvector/.style = draw, rectangle, fill=blue2, minimum width=2.8em, minimum height=1.8em,
transformer/.style = draw, rectangle, fill=padua, minimum width=3em, minimum height=1.5em,
norm/.style = draw, rectangle, fill=blue1, minimum width=5.5em, minimum height=1.2em, inner sep=0, outer sep=0,
dropout/.style = draw, rectangle, fill=blue2, minimum width=4.5em, minimum height=1.2em, inner sep=0, outer sep=0,
mh/.style = draw, rectangle, fill=yellow2, minimum width=5.0em, minimum height=2.0em,
ff/.style = draw, rectangle, fill=blue3, minimum width=4.5em, minimum height=1.5em,
softmax/.style = circle, draw, line width=0.5pt, minimum size=1.5em, inner sep=0pt, align=center,
relu/.style = draw, rectangle, fill=yellow3, minimum width=3.5cm, minimum height=0.2cm,
concat/.style = draw, rectangle, fill=yellow3, minimum width=15.0em, minimum height=0.2cm,
relu2/.style = draw, rectangle, fill=yellow2, minimum width=2.5cm, minimum height=0.2cm,
sigmoid/.style = draw, rectangle, fill=yellow1, minimum width=1.5cm, minimum height=0.2cm,
pretrain_item1/.style = draw, rectangle, fill=yellow4, minimum width=1.5cm, minimum height=0.25cm,
pretrain_item2/.style = draw, rectangle, fill=yellow3, minimum width=1.5cm, minimum height=0.25cm,
pretrain_item3/.style = draw, rectangle, fill=yellow2, minimum width=1.5cm, minimum height=0.25cm,
seq0/.style = draw, rectangle, fill=yellow0, minimum width=0.25cm, minimum height=0.25cm,
seq1/.style = draw, rectangle, fill=yellow1, minimum width=0.25cm, minimum height=0.25cm,
seq2/.style = draw, rectangle, fill=yellow2, minimum width=0.25cm, minimum height=0.25cm,
seq3/.style = draw=none, rectangle, fill=yellow3, minimum width=0.25cm, minimum height=0.25cm,
seq4/.style = draw=none, rectangle, fill=yellow4, minimum width=0.25cm, minimum height=0.25cm,
seq5/.style = draw=none, rectangle, fill=yellow5, minimum width=0.25cm, minimum height=0.25cm,
seq6/.style = draw=none, rectangle, fill=yellow6, minimum width=0.25cm, minimum height=0.25cm,
emb0/.style = draw=none, rectangle, fill=blue0, minimum width=0.25cm, minimum height=0.25cm,
emb1/.style = draw=none, rectangle, fill=blue1, minimum width=0.25cm, minimum height=0.25cm,
emb2/.style = draw=none, rectangle, fill=blue2, minimum width=0.25cm, minimum height=0.25cm,
emb3/.style = draw, rectangle, fill=blue3, minimum width=0.25cm, minimum height=0.25cm,
emb4/.style = draw=none, rectangle, fill=blue4, minimum width=0.25cm, minimum height=0.25cm,
emb5/.style = draw=none, rectangle, fill=blue5, minimum width=0.25cm, minimum height=0.25cm,
emb6/.style = draw=none, rectangle, fill=blue6, minimum width=0.25cm, minimum height=0.25cm,
temb6/.style = draw=none, rectangle, fill=yellow4, minimum width=0.75cm, minimum height=0.25cm,
embholder/.style = draw=none, rectangle, minimum width=0.3cm, minimum height=0.3cm,
mhtaholder/.style = draw=none, rectangle, minimum width=0.6cm, minimum height=0.6cm,

[inner sep=0pt] (in) at (0,0)
[inner sep=0pt, right of=in, node distance=] (i3) ;

[right of=i3, node distance=0.8cm] (i0) $\dots$;

[inner sep=0pt, right of=i0, node distance=0.8cm] (i1) ;

[inner sep=0pt, left of=in, node distance=2cm] (t1) ;

[inner sep=0pt] (lin) at (-10,0)
[inner sep=0pt, right of=lin, node distance=] (li3) ;

[inner sep=0pt, right of=li3, node distance=] (li2) ;

[right of=li2, node distance=0.8cm] (li0tmp) $\dots$;

[inner sep=0pt, right of=li0tmp, node distance=0.8cm] (li1tmp) ;

[right of=li1tmp, node distance=0.8cm] (li0) $\dots$;

[inner sep=0pt, right of=li0, node distance=0.8cm] (li1) ;

[embholder, right of=i1, node distance=2.0cm] (upholder1) ;

[embholder, right of=upholder1, node distance=2.0cm] (contextholder1) ;

($(i1)+(0.4,-0.4)$) – ($(in)+(-0.4,-0.4)$)   node[black,midway,xshift=0cm,yshift=-0.8cm,align=center]
Short-term User
Behavior Sequence

($(li1)+(0.4,-0.4)$) – ($(lin)+(-0.4,-0.4)$)   node[black,midway,xshift=0cm,yshift=-0.8cm,align=center]
Long-term User
Behavior Sequence

[below of=t1, node distance=1.0cm] (ta) Target Item;
[below of=ta, yshift=0.5cm] ($x_t$)

[below of=upholder1, node distance=1.0cm] (up) User Profile;
[below of=up, yshift=0.5cm] ($x_u$);

[below of=contextholder1, node distance=1.0cm] (context) Context;
[below of=context, yshift=0.5cm] ($x_c$);

[embholder, above of=lin, node distance=] (linholder) ;
[embholder, above of=li3, node distance=] (li3holder) ;
[embholder, above of=li2, node distance=] (li2holder) ;
[embholder, above of=li1tmp, node distance=] (li1tmpholder) ;
[embholder, above of=li1, node distance=] (li1holder) ;

[embholder, above of=t1, node distance=] (t1holder) ;

[embholder, above of=in, node distance=] (inholder) ;
[embholder, above of=i3, node distance=] (i3holder) ;
[embholder, above of=i3, node distance=] (i0holder) ;

[embholder, above of=upholder1, node distance=] (upholder1holder) ;
[embholder, above of=contextholder1, node distance=] (contextholder11holder) ;

[embholder, left of=linholder, node distance=] (leftlinholder) ;
($(leftlinholder.north west) $) rectangle ($(contextholder11holder.south east)$) node[thick,pos=.5] (embedding) ;

[embholder, above of=linholder, node distance=0.3cm] (linholder2) ;
[embholder, above of=li3holder, node distance=0.3cm] (li3holder2) ;
[embholder, above of=li2holder, node distance=0.3cm] (li2holder2) ;
[embholder, above of=li1tmpholder, node distance=0.3cm] (li1tmpholder2) ;
[embholder, above of=li1holder, node distance=0.3cm] (li1holder2) ;
[embholder, above of=t1holder, node distance=0.3cm] (t1holder2) ;

[embholder, right of=linholder2, node distance=] (linholder21) ;
[embholder, right of=li3holder2, node distance=] (li3holder21) ;
[embholder, right of=li2holder2, node distance=] (li2holder21) ;
[embholder, right of=li1tmpholder2, node distance=] (li1tmpholder21) ;
[embholder, right of=li1holder2, node distance=] (li1holder21) ;

[embholder, right of=t1holder2, node distance=] (t1holder21) ;

[embholder, left of=linholder2, node distance=] (leftlinholder2) ;
[blue3] ($(leftlinholder2.north west)+(0.0,0.07)$) rectangle ($(t1holder21.south east)+(0.0,0.07)$) node[thick,pos=.5] (hash) Hashing Layer;

[left of=linholder2, node distance=2.1cm, yshift=0.4cm] (hashtext) SimHash Function;
[-Latex[length=1mm, width=0.8mm]] ($(hashtext.east)$) – ($(leftlinholder2.west)$) ;

[left of=linholder, node distance=2.1cm, yshift=0cm] (embtext) Embedding Layer;
[-Latex[length=1mm, width=0.8mm]] ($(embtext.east)$) – ($(leftlinholder.west)$) ;

[seq2, above of=in, node distance=] (s00) ;

[seq1, above of=s00, node distance=] (s02) ;
[seq0, above of=s02, node distance=] (s03) ;
[above of=in, node distance=] () $\bm{e}_1$;

[seq2, above of=i3, node distance=] (s10) ;

[seq1, above of=s10, node distance=] (s12) ;
[seq0, above of=s12, node distance=] (s13) ;
[above of=i3, node distance=] () $\bm{e}_2$;

[above of=i0, node distance=] () $\dots$;

[seq2, above of=i1, node distance=] (s30) ;

[seq1, above of=s30, node distance=] (s32) ;
[seq0, above of=s32, node distance=] (s33) ;
[above of=i1, node distance=] () $\bm{e}_k$;

($(s03.north west)+(-0.35, 0.3)$) rectangle ($(s33.north east)+(0.35, 0.8)$) node[thick,pos=.5] (mhta) Multi-Head Target Attention;

[-Latex[length=1mm, width=0.8mm]] (s00 |- embedding.north) – ($(s00.south)$) ;

[-Latex[length=1mm, width=0.8mm]] (s10 |- embedding.north) – ($(s10.south)$) ;
[-Latex[length=1mm, width=0.8mm]] (s30 |- embedding.north) – ($(s30.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(s03.north)$) – (s03 |- mhta.south) ;

[-Latex[length=1mm, width=0.8mm]] ($(s13.north)$) – (s13 |- mhta.south) ;

[-Latex[length=1mm, width=0.8mm]] ($(s33.north)$) – (s33 |- mhta.south) ;

[seq2, above of=t1, node distance=] (ti0) ;

[seq1, above of=ti0, node distance=] (ti2) ;
[seq0, above of=ti2, node distance=] (ti3) ;
[above of=t1, node distance=] () $\bm{e}_t$;
[right of=ti2, node distance=] () $\bm{h}_{t}$;
[left of=ti2, node distance=] () $\bm{e}_{t}$;

[emb3, right of=ti0, node distance=] (tv0) ;

[fit=($(ti3.north west)+(-0.4, 0.1)$) ($(tv0.south east)+(0.4, -0.1)$), inner sep=0pt, draw=black, thick, dotted, rounded corners=1pt] (dottedrect) ;

[seq2] (up0) at ($(upholder1holder)+(0.0,1.5)$) ;

[seq1, above of=up0, node distance=] (up2) ;
[seq0, above of=up2, node distance=] (up3) ;

[seq2, above of=contextholder11holder, node distance=1.5cm] (c0) ;

[seq1, above of=c0, node distance=] (c2) ;
[seq0, above of=c2, node distance=] (c3) ;

[-Latex[length=1mm, width=0.8mm]] (up.north) – (upholder1holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (context.north) – (contextholder11holder.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(upholder1holder.north)$) – (up0.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(contextholder11holder.north)$) – (c0.south) ;

[seq2, above of=lin, node distance=] (s00) ;

[seq1, above of=s00, node distance=] (s02) ;
[seq0, above of=s02, node distance=] (s03) ;
[above of=lin, node distance=] () $\bm{e}_{k+1}$;
[right of=s02, node distance=] () $\bm{h}_{k+1}$;

[emb3, right of=s00, node distance=] (v00) ;

[seq2, above of=li3, node distance=] (s10) ;

[seq1, above of=s10, node distance=] (s12) ;
[seq0, above of=s12, node distance=] (s13) ;
[above of=li3, node distance=] () $\bm{e}_{k+2}$;
[right of=s12, node distance=] () $\bm{h}_{k+2}$;

[emb3, right of=s10, node distance=] (v10) ;

[seq2, above of=li2, node distance=] (s20) ;

[seq1, above of=s20, node distance=] (s22) ;
[seq0, above of=s22, node distance=] (s23) ;
[above of=li2, node distance=] () $\bm{e}_{k+3}$;
[right of=s22, node distance=] () $\bm{h}_{k+3}$;

[emb3, right of=s20, node distance=] (v20) ;

[seq2, above of=li1, node distance=] (s30) ;

[seq1, above of=s30, node distance=] (s32) ;
[seq0, above of=s32, node distance=] (s33) ;
[above of=li1, node distance=] () $\bm{e}_{n}$;
[right of=s32, node distance=] () $\bm{h}_n$;

[emb3, right of=s30, node distance=] (v30) ;

[seq2, above of=li1tmp, node distance=] (s30tmp) ;

[seq1, above of=s30tmp, node distance=] (s32tmp) ;
[seq0, above of=s32tmp, node distance=] (s33tmp) ;
[above of=li1tmp, node distance=] () $\bm{e}_j$;
[right of=s32tmp, node distance=] () $\bm{h}_j$;

[emb3, right of=s30tmp, node distance=] (v30tmp) ;

[embholder, left of=s03, node distance=] (lefts03) ;
[embholder, right of=s33, node distance=] (rights33) ;
($(lefts03.north west)+(0.0, 0.2)$) rectangle ($(rights33.north east)+(0.0, 0.7)$) node[thick,pos=.5] (hamming) Hamming Distance $+$ Top-K;

[above of=li0, node distance=, xshift=0.25cm] () $\dots$;
[above of=li0tmp, node distance=, xshift=0.25cm] () $\dots$;

[emb3,xshift=4.0cm,yshift=0.2cm] at (hamming) (topktv0) ;

[above of=topktv0, node distance=] () $\bm{h}_t$;

[seq2, above of=lin, node distance=] (ss00) ;

[seq1, above of=ss00, node distance=] (ss02) ;
[seq0, above of=ss02, node distance=] (ss03) ;

[seq2, above of=li2, node distance=] (ss20) ;

[seq1, above of=ss20, node distance=] (ss22) ;
[seq0, above of=ss22, node distance=] (ss23) ;

[seq2, above of=li1, node distance=] (ss30) ;

[seq1, above of=ss30, node distance=] (ss32) ;
[seq0, above of=ss32, node distance=] (ss33) ;

[embholder, left of=ss03, node distance=] (leftss03) ;
[embholder, right of=ss33, node distance=] (rightss33) ;
($(leftss03.north west)+(0.0, 0.3)$) rectangle ($(rightss33.north east)+(0.0, 0.8)$) node[thick,pos=.5] (mhta2) Multi-Head Target Attention.;

[fit=($(mhta2.north west)+(-1.5, 1.0)$) ($(li1.south east)+(0.5, 0.0)$), inner sep=0pt, draw=blue, thick, dotted, rounded corners=4pt] (dottedrect2) ;
[] at ($(mhta2.north west)+(0.5, 2.0)$) (etau) Long-term Interest Extraction Unit;

[-Latex[length=1mm, width=0.8mm]] ($(etau.south)$) – ($(etau.south)+(0.0,-0.8)$) ;

[seq2,xshift=4.0cm,yshift=0.2cm] at (mhta2) (taright0) ;

[seq1, above of=taright0, node distance=] (taright2) ;
[seq0, above of=taright2, node distance=] (taright3) ;
[above of=taright3, node distance=] () $\bm{e}_t$;

[temb6, above of=c3, node distance=2.8cm] (temblongseq5) ;
[temb6] at (up3 |- temblongseq5) (temblongseq4) ;
[temb6] at (mhta |- temblongseq5) (temblongseq3) ;
[temb6] at (dottedrect |- temblongseq5) (temblongseq2) ;
[temb6] at (mhta2 |- temblongseq5) (temblongseq1) ;

($(temblongseq1)+(-0.4,0.4)$) – ($(temblongseq5)+(0.4,0.4)$)   node[black,midway,xshift=0cm,yshift=-0.6cm,align=center] (concatemb)

[concat, above of=concatemb, node distance=1.5cm] (concat) Concatenate;
[relu, above of=concat, node distance=0.7cm] (relu1) Leaky ReLu;
[above of=relu1, node distance=0.6cm] (hidden) $\vdots$;
[relu2, above of=relu1, node distance=0.7cm] (relu2) Leaky ReLu;
[sigmoid, above of=relu2, node distance=0.7cm] (sigmoid) Sigmoid;
[above of=sigmoid, node distance=1cm] (output) $p(y_i|\mathcal{H}_{lu},\mathcal{H}_{su}, x_u, x_t, x_c ; \theta)$;

[-Latex[length=1mm, width=0.8mm]] ($(concat.north)$) – ($(relu1.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(relu2.north)$) – ($(sigmoid.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(sigmoid.north)$) – ($(output.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(concat.south)+(0.0,-0.4)$) – ($(concat.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(up3.north)$) – ($(temblongseq4.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(c3.north)$) – ($(temblongseq5.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(mhta.north)$) – ($(temblongseq3.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(dottedrect.north)$) – ($(temblongseq2.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(mhta2.north)$) – ($(temblongseq1.south)$) ;

[-Latex[length=1mm, width=0.8mm]] (dottedrect |- mhta2) – (rights33.north east |- mhta2.east) ;

[-Latex[length=1mm, width=0.8mm]] (dottedrect |- hamming) – (rights33.north east |- hamming.east) ;

[-Latex[length=1mm, width=0.8mm]] (dottedrect |- mhta) – ($(t1 |- mhta) + (1.5,0.0)$) ;

[seq2,xshift=-2.5cm,yshift=0.2cm] at (mhta) (taright0) ;

[seq1, above of=taright0, node distance=] (taright2) ;
[seq0, above of=taright2, node distance=] (taright3) ;
[above of=taright3, node distance=] () $\bm{e}_t$;

[-Latex[length=1mm, width=0.8mm]] ($(linholder.north)$) – ($(s00.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li3holder.north)$) – ($(s10.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li2holder.north)$) – ($(s20.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li1tmpholder.north)$) – ($(s30tmp.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li1holder.north)$) – ($(s30.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(t1holder.north)$) – ($(ti0.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(t1holder2)$) – ($(t1holder21)$)  – ($(tv0.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li1holder2)$) – ($(li1holder21)$)  – ($(v30.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li1tmpholder2)$) – ($(li1tmpholder21)$)  – ($(v30tmp.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(li2holder2)$) – ($(li2holder21)$)  – ($(v20.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(li3holder2)$) – ($(li3holder21)$)  – ($(v10.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(linholder2)$) – ($(linholder21)$)  – ($(v00.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(v00.north)$) – (v00 |- hamming.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(v10.north)$) – (v10 |- hamming.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(v20.north)$) – (v20 |- hamming.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(v30tmp.north)$) – (v30tmp |- hamming.south) ;
[-Latex[length=1mm, width=0.8mm]] ($(v30.north)$) – (v30 |- hamming.south) ;

[] ($(s03.north)$) – (s03 |- hamming.south) ;
[] ($(s13.north)$) – (s13 |- hamming.south) ;
[] ($(s23.north)$) – (s23 |- hamming.south) ;
[] ($(s33tmp.north)$) – (s33tmp |- hamming.south) ;
[] ($(s33.north)$) – (s33 |- hamming.south) ;

[-Latex[length=1mm, width=0.8mm]] (s03 |- hamming.north) – ($(ss00.south)$) ;

[-Latex[length=1mm, width=0.8mm]] (s23 |- hamming.north) – ($(ss20.south)$) ;
[-Latex[length=1mm, width=0.8mm]] (s33 |- hamming.north) – ($(ss30.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(ss03.north)$) – (ss03 |- mhta2.south) ;

[-Latex[length=1mm, width=0.8mm]] ($(ss23.north)$) – (ss23 |- mhta2.south) ;

[-Latex[length=1mm, width=0.8mm]] ($(ss33.north)$) – (ss33 |- mhta2.south) ;

The model structure of our ETA (End-to-end Target Attention) model.

relu/.style = draw=none, rectangle, fill=yellow3, minimum width=3.5cm, minimum height=0.15cm,
concat/.style = draw=none, rectangle, fill=yellow3, minimum width=15.0em, minimum height=0.15cm,
relu2/.style = draw=none, rectangle, fill=yellow2, minimum width=2.5cm, minimum height=0.15cm,
sigmoid/.style = draw=none, rectangle, fill=yellow1, minimum width=1.5cm, minimum height=0.15cm,
temb6/.style = draw=none, rectangle, fill=yellow4, minimum width=0.75cm, minimum height=0.25cm,
embholder/.style = draw=none, rectangle, minimum width=0.3cm, minimum height=0.3cm,
smallembholder/.style = draw=none, rectangle, minimum width=0.4cm, minimum height=0.4cm,
mhtaholder/.style = draw=none, rectangle, minimum width=0.4cm, minimum height=0.4cm,
softmax/.style = circle, draw, line width=0.5pt, minimum size=2.0em, inner sep=0pt, align=center,
mhta/.style = draw, rectangle, fill=yellow3, minimum width=15.0em, minimum height=0.2cm,
topk/.style = draw, rectangle, fill=yellow3, minimum width=15.0em, minimum height=0.2cm,
mhta2/.style = draw, rectangle, fill=yellow3, minimum width=10.0em, minimum height=0.2cm,
bits/.style = draw, rectangle, fill=blue1, minimum width=0.35cm, minimum height=0.35cm,
bits2/.style = draw, rectangle, fill=blue2, minimum width=0.35cm, minimum height=0.35cm,
line/.style=->,shorten >=0.01cm,shorten <=0.01cm,thick,
crossline/.style = draw, -latex',
connector/.style = draw,circle,node distance=3cm,fill=yellow!20

connect/.style args=(#1) to (#2) over (#3) by #4
insert path=
let 1=($(#1)-(#3)$), 1=veclen(1,1),
2=atan2(1,1), 3=abs(#4), 4=#4>0 ?180:-180  in
(#1) – ($(#1)!\n1-\n3!(#3)$)
arc (2:2+4:3) – (#2)

[inner sep=0pt] (in) at (0,0)
[inner sep=0pt, right of=in, node distance=] (i3) ;

[right of=i3, node distance=] (i0) $\dots$;

[inner sep=0pt, right of=i0, node distance=] (i1) ;

[embholder, right of=i1, node distance=] (upholder1) ;

[embholder, right of=upholder1, node distance=] (contextholder1) ;

[inner sep=0pt, left of=in, node distance=] (t1) ;

[inner sep=0pt, left of=t1, node distance=] (li1) ;

[left of=li1, node distance=] (li0) $\dots$;

[inner sep=0pt, left of=li0, node distance=] (li1tmp) ;

[left of=li1tmp, node distance=0.8cm] (li0tmp) $\dots$;

[inner sep=0pt, left of=li0tmp, node distance=] (li2) ;

[inner sep=0pt, left of=li2, node distance=] (li3) ;

[inner sep=0pt, left of=li3, node distance=] (lin)

($(i1)+(0.4,-0.4)$) – ($(in)+(-0.4,-0.4)$)   node[black,midway,xshift=0cm,yshift=-0.8cm,align=center]
Short-term User
Behavior Sequence

($(li1)+(0.4,-0.4)$) – ($(lin)+(-0.4,-0.4)$)   node[black,midway,xshift=0cm,yshift=-0.8cm,align=center]
Long-term User
Behavior Sequence

[below of=t1, node distance=] (ta)  Target Item;
[below of=ta, yshift=0.5cm] ($x_t$)

[below of=upholder1, node distance=] (up)  User Profile;
[below of=up, yshift=0.5cm] ($x_u$);

[below of=contextholder1, node distance=] (context)  Context;
[below of=context, yshift=0.5cm] ($x_c$);

[softmax, above of=in, node distance=] (e1) $\bm{e}_{1}$;
[softmax, above of=i3, node distance=] (e2) $\bm{e}_{2}$;
[ above of=i0, node distance=] (e0) $\dots$;
[softmax, above of=i1, node distance=] (ek) $\bm{e}_{k}$;

[mhtaholder, above of=e1, node distance=1.75cm] (e1holder) ;
[mhtaholder, above of=e2, node distance=1.75cm] (e2holder) ;
[mhtaholder, above of=ek, node distance=1.75cm] (ekholder) ;

[fill=yellow1,draw=none] ($(e1holder.south west)+ (-0.5, 0.0)$ ) rectangle ($(ekholder.north east)+ (0.5, 0.0)$) node[thick,pos=.5] (mhta) Multi-Head Target Attention.;

[-Latex[length=1mm, width=0.8mm]] (e1.north) – (e1holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (e2.north) – (e2holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (ek.north) – (ekholder.south) ;

[softmax, above of=lin, node distance=] (ek1) $\bm{e}_{k+1}$;
[softmax, above of=li3, node distance=] (ek2) $\bm{e}_{k+2}$;
[softmax, above of=li2, node distance=] (ek3) $\bm{e}_{k+3}$;
[softmax, above of=li1tmp, node distance=] (ej) $\bm{e}_{j}$;
[softmax, above of=li1, node distance=] (en) $\bm{e}_{n}$;
[above of=li0tmp, node distance=] (e0tmp) $\dots$;
[above of=li0, node distance=] (e0) $\dots$;

[above of=ek1, node distance=] (fk1) $f(\cdot)$;
[above of=ek2, node distance=] (fk2) $f(\cdot)$;
[above of=ek3, node distance=] (fk3) $f(\cdot)$;
[above of=ej, node distance=] (fj) $f(\cdot)$;
[above of=en, node distance=] (fn) $f(\cdot)$;
[above of=e0tmp, node distance=] (f0tmp) $\dots$;
[above of=e0, node distance=] (f0) $\dots$;

[softmax, above of=t1, node distance=] (et) $\bm{e}_{t}$;
[softmax, above of=up, node distance=] (eu) $\bm{e}_{u}$;
[softmax, above of=context, node distance=] (ec) $\bm{e}_{c}$;v

[-Latex[length=1mm, width=0.8mm]] (up.north) – (eu.south) ;
[-Latex[length=1mm, width=0.8mm]] (context.north) – (ec.south) ;

[embholder, above of=et, node distance=0.5cm] (etholder) ;
[embholder, right of=ek1, node distance=0.2cm] (ek1holder) ;
[embholder, right of=ek2, node distance=0.2cm] (ek2holder) ;
[embholder, right of=ek3, node distance=0.2cm] (ek3holder) ;
[embholder, right of=ej, node distance=0.2cm] (ejholder) ;
[embholder, right of=en, node distance=0.2cm] (enholder) ;

[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (et |- etholder) – (ek1holder |- etholder)  – (ek1holder |- fk1.south) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (ek2holder |- etholder)  – (ek2holder |- fk2.south) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (ek3holder |- etholder)  – (ek3holder |- fk3.south) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (ejholder |- etholder)  – (ejholder |- fj.south) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (enholder |- etholder)  – (enholder |- fn.south) ;

[name path=ettoek1] (et |- etholder) – (ek1holder |- etholder);

[name path = ek2tofk2] (ek2.north) – (fk2.south);
[name intersections=of=ettoek1 and ek2tofk2];
(S)  at (intersection-1);

[name path=circle] (S) circle();

[name intersections=of = circle and ek2tofk2];

(I1)  at (intersection-1);
(I2)  at (intersection-2);

(ek2.north) – (I2);
[-Latex[length=1mm, width=0.8mm]] (I1) – (fk2.south) ;

[name path = ek3tofk3] (ek3.north) – (fk3.south);
[name intersections=of=ettoek1 and ek3tofk3];
(S)  at (intersection-1);

[name path=circle] (S) circle();

[name intersections=of = circle and ek3tofk3];

(I1)  at (intersection-1);
(I2)  at (intersection-2);

(ek3.north) – (I2);
[-Latex[length=1mm, width=0.8mm]] (I1) – (fk3.south) ;

[name path = ejtofj] (ej.north) – (fj.south);
[name intersections=of=ettoek1 and ejtofj];
(S)  at (intersection-1);

[name path=circle] (S) circle();

[name intersections=of = circle and ejtofj];

(I1)  at (intersection-1);
(I2)  at (intersection-2);

(ej.north) – (I2);
[-Latex[length=1mm, width=0.8mm]] (I1) – (fj.south) ;

[name path = entofn] (en.north) – (fn.south);
[name intersections=of=ettoek1 and entofn];
(S)  at (intersection-1);

[name path=circle] (S) circle();

[name intersections=of = circle and entofn];

(I1)  at (intersection-1);
(I2)  at (intersection-2);

(en.north) – (I2);
[-Latex[length=1mm, width=0.8mm]] (I1) – (fn.south) ;

[->,name path=line 1] (B) – (C);

[name path=line 2] (D) – (A);

[name intersections=of = line 1 and line 2];
(S)  at (intersection-1);

[name path=circle] (S) circle();

[name intersections=of = circle and line 2];
(I1)  at (intersection-1);
(I2)  at (intersection-2);

(D) – (I1);
[->] (I2) – (A);

[-Latex[length=1mm, width=0.8mm]] (ek1.north)  – (fk1.south) ;

[smallembholder, above of=fk1, node distance=0.8cm] (topk1holder) ;
[smallembholder, above of=fk2, node distance=0.8cm] (topk2holder) ;
[smallembholder, above of=fk3, node distance=0.8cm] (topk3holder) ;
[smallembholder, above of=fj, node distance=0.8cm] (topjholder) ;
[smallembholder, above of=fn, node distance=0.8cm] (topnholder) ;

[dashed] ($(topk1holder.south west)$) rectangle ($(topnholder.north east)$) node[pos=.5] (topk) Top-K Retrieval;

[-Latex[length=1mm, width=0.8mm]] (fk1.north)  – (topk1holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (fk2.north)  – (topk2holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (fk3.north)  – (topk3holder.south) ;
[-Latex[length=1mm, width=0.8mm]] (fj.north)  – (topjholder.south) ;
[-Latex[length=1mm, width=0.8mm]] (fn.north)  – (topnholder.south) ;

[smallembholder, above of=topk1holder, node distance=1.0cm] (tak1holder) ;
[smallembholder, above of=topk2holder, node distance=1.0cm] (tak2holder) ;
[smallembholder, above of=topk3holder, node distance=1.0cm] (tak3holder) ;
[smallembholder, above of=topjholder, node distance=1.0cm] (tajholder) ;
[smallembholder, above of=topnholder, node distance=1.0cm] (tanholder) ;
[fill=yellow1,draw=none] ($(tak1holder.south west)$) rectangle ($(tanholder.north east)$) node[thick,pos=.5] (mhta2) Multi-Head Target Attention.;

[dashed] ($(tak1holder.north west)+(-0.5, 0.7)$) rectangle ($(li1)+(0.5, -2.0)$) node[pos=.5] (dottedunit) ;
[below of=lin, node distance=2.3cm, xshift=1.5cm] (unit) Long-term Interest Extraction Unit.;

[-Latex[length=1mm, width=0.8mm]] (topk1holder.north)  – (tak1holder.south) ;

[-Latex[length=1mm, width=0.8mm]] (topk3holder.north)  – (tak3holder.south) ;

[-Latex[length=1mm, width=0.8mm]] (topnholder.north)  – (tanholder.south) ;

[smallembholder, above of=topk2holder, node distance=0.6cm] (cutk2) $\times$;
[smallembholder, above of=topjholder, node distance=0.6cm] (cutj) $\times$;
[-Latex[length=1mm, width=0.8mm]] (topk2holder.north)  – (cutk2) ;
[-Latex[length=1mm, width=0.8mm]] (topjholder.north)  – (cutj) ;

[temb6, above of=mhta2, node distance=] (temblongseq1) ;
[temb6] at (et |- temblongseq1) (temblongseq2) ;
[temb6] at (mhta |- temblongseq1) (temblongseq3) ;
[temb6] at (up |- temblongseq1) (temblongseq4) ;
[temb6] at (context |- temblongseq1) (temblongseq5) ;

($(temblongseq1)+(-0.4,0.2)$) – ($(temblongseq5)+(0.4,0.2)$)   node[black,midway,xshift=0cm,yshift=-0.6cm,align=center] (concatemb)

[concat, above of=concatemb, node distance=1.2cm] (concat) Concatenate;
[relu, above of=concat, node distance=0.6cm] (relu1)  ReLu;
[above of=relu1, node distance=0.6cm] (hidden) $\vdots$;
[relu2, above of=relu1, node distance=0.6cm] (relu2)  ReLu;
[sigmoid, above of=relu2, node distance=0.6cm] (sigmoid) Sigmoid;
[above of=sigmoid, node distance=0.8cm] (output)  $p(y_i|\mathcal{H}_{lu},\mathcal{H}_{su}, x_u, x_t, x_c ; \theta)$;

[-Latex[length=1mm, width=0.8mm]] ($(concat.north)$) – ($(relu1.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(relu2.north)$) – ($(sigmoid.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(sigmoid.north)$) – ($(output.south)$) ;

[-Latex[length=1mm, width=0.8mm]] ($(concat.south)+(0.0,-0.2)$) – ($(concat.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(eu.north)$) – ($(temblongseq4.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(ec.north)$) – ($(temblongseq5.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(mhta.north)$) – ($(temblongseq3.south)$) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] ($(et.north)$) – ($(temblongseq2.south)$) ;
[-Latex[length=1mm, width=0.8mm]] ($(mhta2.north)$) – ($(temblongseq1.south)$) ;

[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (et |- mhta2) – (en.east |- mhta2.east) ;

[embholder, left of=e1, node distance=0.7cm] (mhtaleftholder) ;
[line width=0.35mm, -Latex[length=1.5mm, width=1.3mm]] (et |- mhta) – (mhtaleftholder |- mhta.west) ;

[embholder, left of=ek1, node distance=0.3cm] (ek1leftholder) ;
[embholder, left of=ek1leftholder, node distance=0.3cm] (ek1leftleftholder) ;

[embholder, left of=ek1leftholder, node distance=1.5cm] (ek1leftleflefttholder) ;

[mhtaholder] at (ek1leftholder |- output) (fa) [;
[mhtaholder, right of=fa, node distance=] (fa1) $a_1$;
[mhtaholder, right of=fa1, node distance=] (fa2) $a_2$;
[mhtaholder, right of=fa2, node distance=] (fa3) $\dots$;
[mhtaholder, right of=fa3, node distance=] (fa4) $a_n$;
[mhtaholder, right of=fa4, node distance=] (fa5) ];

[left of=fa, node distance=1cm] (fa0) $\bm{e}_{k+1}$:;

[mhtaholder, below of=fa, node distance=2.5cm] (fb) [;
[mhtaholder, right of=fb, node distance=] (fb1) $b_1$;
[mhtaholder, right of=fb1, node distance=] (fb2) $b_2$;
[mhtaholder, right of=fb2, node distance=] (fb3) $\dots$;
[mhtaholder, right of=fb3, node distance=] (fb4) $b_n$;
[mhtaholder, right of=fb4, node distance=] (fb5) ];

[left of=fb, node distance=1cm] (fb0) $\bm{e}_{t}$:;

[bits, below of=fa4, node distance=0.8cm] (ba0) 1;
[left of=ba0, node distance=0.45cm] (ba1) $\dots$;
[bits, left of=ba1, node distance=0.45cm] (ba2) 1;
[bits2, left of=ba2, node distance=0.35cm] (ba3) 0;
[bits, left of=ba3, node distance=0.35cm] (ba4) 0;

[below of=fa0, node distance=0.8cm] (fatext) $\bm{h}_{k+1}$:;

[bits, above of=fb4, node distance=0.8cm] (bb0) 1;
[left of=bb0, node distance=0.45cm] (bb1) $\dots$;
[bits, left of=bb1, node distance=0.45cm] (bb2) 1;
[bits2, left of=bb2, node distance=0.35cm] (bb3) 1;
[bits, left of=bb3, node distance=0.35cm] (bb4) 0;

[above of=fb0, node distance=0.8cm] (fbtext) $\bm{h}_{t}$:;

[above of= bb0, node distance=0.5cm, xshift=2cm] (hamming) Hamming Distance;

[-Latex[length=1mm, width=0.8mm]] (ba0.east) – (hamming.west) ;
[-Latex[length=1mm, width=0.8mm]] (bb0.east) – (hamming.west) ;

[dashed, blue6] (ek1leftleflefttholder |- fa.north) rectangle (en |- fb.south) node[pos=.5] (frec) ;

($(fa4.south)+(0.0,0.0)$) – ($(fa1.south)+(0.0,0.0)$)   node[black,midway,xshift=0cm,yshift=-0.6cm,align=center] (simhasha)

($(fb1.south)+(0.0,0.5)$) – ($(fb4.south)+(0.0,0.5)$)   node[black,midway,xshift=0cm,yshift=0.0cm,align=center] (simhashb)

[right of=simhasha, node distance=1.4cm, yshift=0.5cm] (simhashtexta) SimHash;

[right of=simhashb, node distance=1.4cm, yshift=0.1cm] (simhashtextb) SimHash;

[line, bend left, dashed, blue6] (fk1.west) edge (ek1leftleflefttholder |- hamming.south);

[left of=ek1, node distance=2.0cm] (embedding) Embedding Layer;

[left of=fk1, node distance=2.0cm] (similarity) Similarity Functions;

[-Latex[length=1mm, width=0.8mm]] (embedding.east) – (ek1.west) ;

[-Latex[length=1mm, width=0.8mm]] (similarity.east) – (fk1.west) ;

The illustration of our ETA (End-to-end Target Attention) model. $\bm{e}_{k+1} \in  \mathbb{R}^{d \times 1}$ and $\bm{e}_{t} \in  \mathbb{R}^{d \times 1}$ represent the embedding vectors of behavior item $k$+$1$ and target item $t$. $d$ is the dimension of item embedding. $\bm{h}_{k+1}$ and $\bm{h}_t$ are the fingerprints of item $k$+$1$ and $t$ generated by SimHash function. A $d$-dimensional embedding $\bm{e}_{k+1}$ can be hashed into a $m$-bit integer. Note that the projections of embedding vectors $\bm{e}_{k+1}$ and $\bm{e}_t$ before SimHash are omitted in the figure for clarity. The other notations can be find in Table <ref>.

§ MODEL

Notations used in this paper.
max width=1.0

Notation.     Description.

$\mathcal{I}$     The set of impressions.

$p_j$     The click probability of a certain impression $j$.

$y_j$     The label of click on impression $j$.

$x_j$     The feature vector on impression $j$.

$\theta$     The parameters of CTR model.

$d$      The dimension of item embedding.

$\bm{e} \in  \mathbb{R}^{d \times 1}$     The item embedding vector.

$\bm{h} \in \mathbb{R}$     The hashed fingerprint of embedding vector $\bm{e}$.

$\text{sig}_i$     The bit vector generated by $i^{th}$ hash function.

$m$     The bit-length of hashed fingerprint $\bm{h}$.

$\mathcal{H}_{lu}$     Long-term user behavior sequence.

$\mathcal{H}_{su}$     Short-term user behavior sequence.

$x_u$     Raw features of user profile.

$x_c$     Raw features of context information.

$x_t$     Raw features of target item.

L     The length of long-term user behavior sequence.

B     The number of candidate items to be predicted in each user request.

$\bm{e}_u, \bm{e}_c, \bm{e}_t$     The embedding vectors of user profile, context and target item respectively.

$\bm{E}_s \in  \mathbb{R}^{L \times d}$     Embedding matrix of long-term user behavior sequence.

$\bm{E}_t \in  \mathbb{R}^{1 \times d}$     Embedding matrix of target item.

$f(\cdot)$     The similarity function of two embedding vectors.

In this section, we first introduce the detailed architecture of our ETA (End-to-End Target Attention) model. Then we introduce different sub-modules of ETA model. At last, we introduce the hands-on experiences for the deployment of ETA.

§.§ Model Overview

As shown in Figure <ref>, our model takes user/item-side features as input and outputs the click probability of a certain user-item pair.

$\mathcal{H}_{lu}$, $\mathcal{H}_{su}$, $x_u$, $x_t$ and $x_c$ are raw input features. $\theta$ represents the trainable parameters. Having these features, we use Long-term Interest Extraction Unit (Section <ref>), Multi-head Target Attention (Section <ref>) and Embedding Layer (Section <ref>) to convert $\mathcal{H}_{lu}$, $\mathcal{H}_{su}$, $x_u$, $x_t$ and $x_c$ into hidden vectors respectively. Then the hidden vectors are concatenated together and are fed into the MLP (Multi-layer Perception) part. At the last layer of MLP, sigmoid function is used to map the hidden vector into a scalar $p(y_j|\mathcal{H}_{lu},\mathcal{H}_{su}, x_u, x_t, x_c ; \theta)$ which represents the click probability of a certain user-item pair. This probability can be used as the ranking score for the downstream tasks.

§.§ Embedding Layer

The features of our model can be divided into four different categories: the long (short)-term user behavior sequence $\mathcal{H}_{lu}$ ($\mathcal{H}_{su}$), features of target item ($x_t$), user profile information ($x_u$) and context information ($x_c$).

In our paper, we mainly focus on how to make better use of long-term user behavior sequence

$\mathcal{H}_{lu}$, which is split from whole user sequence after removing the short-term user behaviors $\mathcal{H}_{su}$. We encode the short-term user behavior sequence in the same way with DIN <cit.> and propose new architecture Long-term Interest Extraction Unit to handle $\mathcal{H}_{lu}$. $x_t$ represents the features of the target item, including item id, statistic features and categorical ids (category id, shop id, brand idetc.). The categorical ids are friendly to cold-start items <cit.>.

$x_u$ represents user profile information which is similar with YouTube <cit.>, e.g., age, gender and purchase level.
$x_c$ represents the context information, e.g., the hour of day,

which is mainly used to learn the bias part of the model.

For different types of features, we adopt different embedding techniques. The raw input features are mainly divided into two types: the categorical features and the numerical features. In our model, we use one-hot encoding for categorical features. For numerical features, we first divide the features into different numerical buckets. Then we apply one-hot encoding to identify different buckets, which is the similar way with <cit.>. Note that the one-hot encoding vectors can be extremely sparse because there are billions of item ids. Thus we map all one-hot embedding vectors into low-dimensional hidden vectors to reduce the number of parameters. We use $\bm{e}_i \in  \mathbb{R}^{d \times 1}$ to represent the embedding vectors of item $i$. All the embedding vectors of user behavior items are then packed together into a matrix $\bm{E}_s \in  \mathbb{R}^{L \times d}$, which is shown in Equation <ref>. $L$ is the length of user behavior sequence and $d$ is the embedding size.

\begin{align}
\bm{E}_s &= \begin{bmatrix}
\bm{e}_{1}^\top \\
\bm{e}_{2}^\top \\
\vdots \\
\bm{e}_{L}^\top
\end{bmatrix}.
\label{eq:embeddingmatrix}
\end{align}

§.§ Multi-head Target Attention

Multi-head attention is first proposed by <cit.> and is widely applied on CTR prediction tasks <cit.>. In CTR prediction task, target item acts as query ($\bm{Q}$) and each item in user behavior sequence acts as key ($\bm{K}$) and value ($\bm{V}$). We call this multi-head attention structure as multi-head target attention, which is abbreviated as TA.

The calculation of TA is shown in Equation <ref>. The main part of TA is dot-product attention, which is shown in Equation <ref>. The dot-product attention is made up of two steps. Firstly, similarities are calculated between each behavior item and target item according to their embedding matrices $\bm{Q}$ and $\bm{K}$. Secondly, the normalized similarities are used as the attention weights to calculate the weighted sum embedding of all the behavior items, whose embedding matrix is represented as $\bm{V}$.

\begin{equation}
\begin{split}
\text{TA}(\bm{E}_t,\bm{E}_s) & = \text{Concat}(\text{head}_1,...,\text{head}_h)\bm{W^O}, \\
\text{where~head}_i &= \text{Attention}(\bm{E}_t\bm{W}_i^Q, \bm{E}_s\bm{W}_i^K, \bm{E}_s\bm{W}_i^V),
\end{split}
\label{eq:mhta}
\end{equation}

\begin{equation}
\text{Attention}  (\bm{Q,K,V})   = \text{softmax}\left(\frac{\bm{QK}^T}{\sqrt{d_k}}\right)\bm{V},
\label{eq:dotattention}
\end{equation}

where $\bm{E}_t \in \mathbb{R}^{1 \times d}, \bm{E}_s \in \mathbb{R}^{L \times d}$ are input embedding matrices for target item and behavior sequence respectively. $L$ is sequence length and $d$ is the embedding size of hidden vector for each behavior item. Note that we only select one piece of sample instead of a batch of samples for clarity. Matrices $\bm{Q,K,V}$ represent queries, keys and values respectively. $d_k,d_q,d_v$ is the embedding size for each row vector of $\bm{K,Q,V}$. $\sqrt{d_k}$ is used to avoid large value of the inner product. softmax function is used to convert the value of inner-product into the adding weight of the value vector $\bm{V}$. $\bm{W}_i^Q \in \mathbb{R}^{d \times d_k},\bm{W}_i^K \in \mathbb{R}^{d \times d_k},\bm{W}_i^V \in \mathbb{R}^{d \times d_v}$. $\bm{W^O} \in \mathbb{R}^{hd_v \times d}$ is the projection matrix. $h$ is the number of headers.

§.§ Long-term Interest Extraction Unit

This part is the main contribution of our ETA model. It extends the encoding length of user behavior sequence from tens to thousands or longer to capture the long-term user interests. As mentioned before, the complexity of multi-head target attention  is $O(L*B*d)$ where $L$ is the length of user sequence, $B$ is the number of candidate items and $d$ is the representation dimension. In large-scale online system, $B$ is close to 1000 and $d$ is close to 128. Thus directly conducting multi-head target attention on thousands of long-term user behaviors is infeasible.

According to Equation <ref>, softmax is dominated by the largest elements, for each query we only need to focus on the keys that are closest to the query, which is also confirmed by <cit.>. Thus we can first retrieval top-$k$ items from the behavior sequence and conduct the multi-head target attention on these $k$ behaviors. However, a good retrieval algorithm should satisfy two constraints: 1) the target of retrieval part should keep the same with the whole CTR model. Only in this way can the top-k retrieved items contribute the most to the CTR model. 2) the retrieval time should satisfy the strict inference time limit to make sure the algorithm can be applied in real-world system to serve millions of request per second. We compare different retrieval algorithms in Table <ref>. SIM <cit.> and UBR4CTR <cit.> build offline inverted index to enable
quick searching during training and inference. However, the inputs they used for building the index are attribute information (e.g., category) or pre-trained embedding of items, which are different with the embedding used in CTR model. This gap violate the above constraint 1) and may lead to performance degradation. If we directly use the embedding in CTR model and search the k-nearest neighbor by inner product, $O(L*B*d)$ multiplications are needed and the inference time increases greatly. $d$ is the dimension of the embedding vector. $L$ and $B$ are the number of behavior items and target items respectively. This will violate the above constraint 2) and can not be deployed online. Our ETA uses SimHash to convert the inner product of two vectors into hamming distance calculation, which is shown in Figure <ref>. This makes it possible to be deployed in real world recommendation system. Besides, the local sensitive property of SimHash ensures that the fingerprint can always keep in sync with the original embedding in CTR model. The evaluation in Section <ref> shows that this compatibility can greatly improve the performance. How to choose the right hash function and the joint learning between the retrieval part and the rest part of ETA will be explained in Section <ref> and Section <ref>.

After SimHash function and hamming distance layer, top-$k$ similar behavior items are selected from $\mathcal{H}_{lu}$, then the aforementioned multi-head target attention is conducted to generate the hidden vector. This vector acts as the representation of long-term user interest and is fed into the MLP (Multi-layer Perception) layers together with other vectors. The formulation of long-term user interest unit is shown in the following Equation <ref>.

Comparison between different retrieval algorithms. $d$ is the dimension of the embedding vector. $L$ and $B$ are the number of behavior items and target items respectively. $m$ is the dimension of fingerprint generated by SimHash. $M$ is the size of attribute inverted index for each user. In real world CTR model, $L=1024, B=1024, d=128, m=4, M=300$. It is not worthy that directly conduct inner product online violate the time constraint and can not be deployed in large scale online RS.
max width=1.0

Retrieval input.       Retrieval method.      Gap of goal between retrieval and CTR model.      Retrieval complexity.     Representative.

Attribute.     Offline inverted index     Big     $O(B*log(M))$     SIM(hard) <cit.> and UBR4CTR <cit.>

Pre-trained embedding     Offline inverted index and Euclidean distance     Medium      $O(B*M*d)$     SIM(soft) <cit.>

SimHash-based fingerprint.     Hamming distance     Small     $O(B*L*m)$     ETA

Embedding of CTR model.     Inner product     No     $O(B*L*d)$     Can not deploy.

\begin{equation}
\text{LTI}(\bm{E}_t,\bm{E}_{s}) = \text{TA}(\bm{E}_t,\bm{E}_{s}^{'}),
\label{eq:longtermunit}
\end{equation}

\begin{align}
\bm{E}_{s}^{'} &= \begin{bmatrix}
\bm{e}_{1}^\top \\
\bm{e}_{i}^\top \\
\vdots \\
\bm{e}_{k}^\top
\end{bmatrix} ,
\end{align}

\begin{align}
\bm{e}_i & \in topk(HammingDistance(\bm{h}_i, \bm{h}_t)), \\
\bm{h}_i & = SimHash(\bm{e}_i), \bm{h}_t = SimHash(\bm{e}_t),
\end{align}

where LTI and TA is short for long-term user interest extraction unit and multi-head target attention respectively. $\bm{E}_{s} \in \mathbb{R}^{|\mathcal{H}_{lu}| \times d}$ is the embedding matrix of long-term user behavior sequence $\mathcal{H}_{lu}$. $\bm{E}_{s}^{'} \in \mathbb{R}^{k \times d}$ consists of top $k$ rows selected from $\bm{E}_{s_1}$ which have the largest hamming distances with target item $\bm{E}_{t} \in \mathbb{R}^{1 \times d}$.

Similarity Function As shown in Figure <ref>, we use SimHash function and hamming distance to calculate the similarity of two embedding vectors instead of inner product. SimHash function takes the output of aforementioned embedding layer as input. For each input embedding vector, the SimHash function generates its compressed number as the fingerprint. SimHash satisfies the locality sensitive properties: the hashing output is similar if the input features are similar to each other. Thus, the similarity between the embedding vectors can be replaced by the similarity between the hashed fingerprints. A $d$-dimensional embedding vector can be encoded into $m$-bit number. Then the similarity between two fingerprints can be measured by hamming distance.

Top-K Retrieval The top-$k$ retrieval layer can find the top-k similar user behavior items with target item more efficiently by hamming distance compared with the inner-product based models. The hamming distance for two integers is defined as the number of different bits positions at which the corresponding bits are different. To get the hamming distance of two $m$-bit numbers, we first conduct $XOR$ and then count the number of bits in 1. If we define the multiplication as the atomic operation, then the complexity of hamming distance for two $m$-digit numbers is $O(1))$.
The total complexity of the hamming distance based top-$k$ retrieval is $O(L*B*1)$, where $L$ is the sequence length, $B$ is the number of candidate items. It is noteworthy that the hashed fingerprints can be stored in an embedding table with the model each time the SimHash function is conducted. During the inference time, only embedding lookup is needed and its complexity is negligible.

However, for the traditional k-nearest neighbor retrieval algorithm <cit.>, the complexity is $O(L*B*d*n*log(n))$, where $d$ is the dimension of the embedding vector. $O(d*n*log(n))$ is the complexity of inner product for two $d$-dimensional embedding vectors. $O(n*log(n))$ is the complexity of multiplication of two float32 format numbers <cit.>.
For online settings where $d=128$ and $n=32$, theoretically hamming distance based retrieval can reduce at least $128 * 32$ times computation costs compared with the inner product based method. In practice, we observe about $128\times$ speedup ratio. It is hard to reach the theoretical bound for many reasons. For example, tensorcore in TensorFlow <cit.> optimizes the calculation of multiplication on GPU by automatic parallelization.

§.§ Complexity Comparison

In this section, we give a summary for our ETA by compare the complexities for different parts with the SOTA models. Besides the complexity, some key properties are also listed in Table <ref>.

As noted in Table <ref>, there are two ways to find the top-k similar user behavior items, hard retrieval and soft retrieval.

For hard retrieval method, the representative work is SIM(hard) <cit.>. SIM(hard) selects $k$ recent user behaviors which shares the same category (or other structured properties) with target item. However, for many recommender systems, the accurate category-like information is not available. For the soft retrieval method, the representative works are SIM(soft) <cit.> and UBR4CTR <cit.>. In soft retrieval method, each item in user sequence conducts inner product with target item to get the similarity. By sorting the items using the vector similarity value, one can get the top-k similar items.

However, the complexity of top-k similar vector retrieval is $O(L*B)$ of fp32 multiplication, where $L$ is the user sequence length and $B$ is the number of candidate items. In large-scale online system, both $L$ and $B$ are in thousands level. Thus traditional top-k similar vector retrieval requires at least 1,000,000 times inner product, which is not allowed in large-scale online system. In our online recommender system, the SLA for online inference is 100ms. To alleviate the online inference cost, SIM<cit.> adopts an off-line FAISS-like method. But the FAISS-like method has limitations too. The embedding used in offline retrieval system is got from the pre-trained model. The pre-trained embedding has gap with the embedding in CTR model. This gap may lead to performance degradation, which will be discussed in section <cit.>. Besides, for large-scale online RS, offline retrieval method leads to resources waste as millions of items are stored twice.

§.§ Deployment

In this section, we show how ETA is trained with the retrieval part. Then we introduce how to select the “hash function” used in SimHash algorithm. Then we introduce the engineer optimization tricks.

§.§.§ Joint learning of retrieval part

During the training stage, the retrieval part does not need updates of gradients. The goal of retrieval is to select the nearest neighbors of the keys to query for the following multi-head target attention part. After the top-k closest keys to query are selected, the normal attention and back propagation are conducted on the original embedding vectors of these top-k items. The only thing for retrieval is to initialize a fix random matrix $\bm{H} \in \mathbb{R}^{d \times m}$ (see Algorithm <ref>) at the beginning of training. As long as the input embedding vector $\bm{e}_k \in \mathbb{R}^{1 \times d}$ is updated, the signature of SimHash is updated correspondingly. The Locality-sensitive properties ensure that the top-k nearest keys to query in each iteration are selected using the latest embedding of CTR model seamlessly. Thus the gap of goal between retrieval and CTR model is much smaller than those other retrieval methods, e.g., offline inverted index based method shown in Table <ref>. From the perspective of the CTR model, the retrieval part is transparent but can ensure the model use the most closet items to conduct multi-head attention. The evaluation section (Sec. <ref>) shows that this end-to-end training without any pre-training or offline inverted index building can greatly improve the performance of CTR prediction task.

§.§.§ Selection of “Hash Function”

The SimHash is a well-known locality-sensitive hashing (LSH) <cit.> algorithm. The implementation of SimHash is shown in Algorithm <ref> where we use fix random hash vector to act as “hash function”. Any traditional hashing functions which hash the string to a random integer can also be used. However, in our algorithm we choose random hash vector and the implementation of Algorithm <ref> for the consideration of scalability and efficiency for matrix computation, which is the same with Reformer <cit.>. The locality-sensitive hashing is implemented by random rotation and projection. The random rotation refers to the multiplication between the embedding vector and a fix random hashing vector $\bm{H}(j)$. Any random $d$-dimensional vector can be used here. It is noteworthy that as we need to project the result of inner product into two singed axes to get binary signature, the element in $\bm{H}(j)$ should be generated randomly around 0.

§.§.§ Engineered Optimization Tricks

When the model is deployed online, the calculation of SimHash can be reduced one step further. For a m-length signature vector $\bm{sig}_k$ for embedding vector $\bm{e}_k$ calculated by Algorithm <ref>, we can use $log(m)$-bits integer to represent the signature vector because each element in $\bm{sig}_k$ is either 1 or 0. This can greatly reduce the cost of memory and can speed up the calculation of hamming distance. The calculation time of two integers can be conducted in $O(1)$ time complexity and can be neglected.

Time complexity of different models. $L$ is the length of user behavior sequence and $d$ is the dimension of embedding vector. $h$ is number of heads. $m$ is the dimension of fingerprint calculated by SimHash. $M$ is the size of attribute inverted index each user.
max width=1.0

Method        Training     Inference

SIM hard     $O(B * log(M)) + O(B * K * d * h)$     $O(B * log(M)) + O(B * K * d * h)$

SIM soft     $O(B * log(L) * d * d) + O(B * K * d * h)$     $O(B * L * d) + O(B * K * d * h)$

ETA     $O(B * L * d * d) + O(B * K * d * h)$     $O(B * L * m) + O(B * K * d * h)$

Corpus sizes of dataset used in this paper. SL is short for user Sequence Lenght.
max width=1.0

Users     Items      Category     Interaction      Max(SL)     Min(SL)     Median(SL)     Mean(SL)

Amazon(Book)     75,053     358,367     1,583     150,016      43,201     1     1     3

Taobao.     987,994     4,162,024      9,439     100,150,807      848     1     75     101

Industrial(Our Own)     -     -     -     -     -     -     -     -

Corpus sizes of dataset used in this paper.
max width=1.0

Users     Items      Categories     Instances

Taobao.     987,994     4,162,024      9,439     100,150,807

Industrial(Our Own)     0.4 billion     0.7 billion     24,568     142 billion

§ EXPERIMENTS

In this section, we conduct experiments to answer the following research questions.

* RQ1: Does our ETA model outperform the baseline models?

* RQ2: What is the inference time of our ETA model compared with the baseline models? Inference time is as important as performance because it decides whether the model can be deployed online for serving.

* RQ3: Which part of our ETA model contributes the most to the performance and inference time?

Before presenting the evaluation results, we first describe the datasets, baseline models, metrics and experimental settings.

§.§ Datasets

To conduct comprehensive comparisons between our ETA model and the baseline models, both public dataset and industrial dataset are used. Online A/B test is also conducted. For public dataset, we choose Taobao dataset, which is also adopted by baseline models SIM <cit.> and UBR4CTR <cit.>. An industrial dataset is prepared as the supplement for public dataset. Table <ref> gives a brief introduction of the datasets.

Taobao Dataset [<https://tianchi.aliyun.com/dataset/dataDetail?dataId=649   userId=1>]: This dataset is first released by <cit.> and is widely used as the public benchmark for CTR prediction task and sequential recommendation task. It is made up of users' behavior logs from Taobao Mobile App. The user behaviors include click, favorite, add to cart and buy. This dataset contains 100 million instances. In average, each user has about 101 interactions and each item receives over 24 interactions. The recent 16 behaviors are selected as short-term user behavior sequence and the recent 256 behaviors are selected as long-term user behavior sequence.

Industrial Dataset [This dataset will be released to public to help the research on long-term user interest modeling.]: This dataset is collected from our own online RS, which is one of the top-tier mobile Apps in our country. There are three advantages for our industrial dataset. (i) Our dataset contains impression interaction, which indicates an item is displayed to an user but not clicked by the user. Impression interaction is naturally the negative sample of CTR model. As a result, the tricky negative sampling is not needed. (ii) The user behavior sequence is much longer in our industrial dataset. There are over 142 billion instances and the average length reaches 938, which is 9 times longer than the public Taobao dataset. (iii) Our industrial dataset has more features designed by multiple software engineers which is closer to the real-world RS models. The recent 48 behaviors are selected as short-term user behavior sequence and the recent 1024 behaviors are selected as long-term user behavior sequence. In the ablation study, we also try the long-term user behavior sequence with the lengths in $\{256, 512, 2048\}$.

§.§ Baselines and Metrics

We compare our model with the following mainstream baselines for CTR prediction. Each baseline is chosen to answer one or more related research questions mentioned above.

* Avg-Pooling DNN: The simplest way to utilize user behavior sequence is average pooling which encodes the various length of user sequences into fixed-size hidden vector. This baseline can be regarded as variant of DIN by replacing the target attention with average pooling, which is similar to YouTube <cit.>. This baseline is mainly used to show the necessity of target attention when compared with DIN.

* DIN <cit.>: DIN is proposed to model personalized user interests with different target items by an attention mechanism, which is called as target attention. However, DIN only utilizes the short-term user behavior sequence.

* DIN (Long Sequence) is DIN equipped with long-term user behavior sequence $\mathcal{H}_{lu}$. $\mathcal{H}_{lu}$ is encoded by mean pooling. This baseline is used to measure the information gain of long-term user behavior sequence itself when compared with DIN.

* SIM(hard) <cit.>: SIM is the CTR prediction model which propose a search unit to extract user interest from long-term user behavior sequence in a two stage manner. SIM(hard) is SIM which searches the top-k behavior items by category id in the first stage.

* UBR4CTR <cit.>: UBR4CTR is also a two-stage method which utilizes the long-term user behavior sequence in CTR prediction task. In UBR4CTR, a query is prepared by a feature selection model to retrieve the most similar behavior items. An inverted index is prepared for online usage. As UBR4CTR and SIM are published almost simultaneously, they do not compare to each other. In our paper, we compare both UBR4CTR and SIM for the first time.

* SIM(hard)/UBR4CTR + timeinfo is SIM(hard)/UBR4CTR with time embedding when encoding the user behavior sequence.

In <cit.>, the authors propose SIM(soft) as the variants of base algorithm SIM(hard). They finally adopt SIM(hard) method as their online serving algorithm and deploy SIM(hard)+timeinfo online to serve the main traffic. This is because SIM(hard) does not need pre-training and is more friendly to system evolution and maintenance. Besides, SIM(hard) + timeinfo can achieve comparable performance with SIM(soft). Thus, we choose SIM(hard) and SIM(hard) + timeinfo as our strong baselines.

MIMN <cit.> is proposed by the same team with DIN. A multi-track offline user interest center is proposed by MIMN to extract the long-term user interest. At the publishing time, it achieves the state-of-the-art performance by leverage the long-term user behavior sequence. However, MIMN is defeated by SIM <cit.> from the same team. As MIMN contributes little to our research questions, we omit this baseline for the space limitation.

Metrics: For offline experiments, we adopt widely used area under ROC curve (AUC) as our main metric and Inference Time as a supplement metric. AUC is suitable for binary classification problem for measuring pairwise ranking performance. Inference Time is defined as the round-trip time when scoring a batch of items for a certain model request. We measure the Inference Time by deploying models online to serve user requests which are copied from product environment. The machines and the number of user requests are controlled same for fairness comparison.

For online A/B test, we use CLICK and CTR as evaluation metrics. CLICK is defined as the total number of clicked items. CTR is used to measure the willingness of click for users in the platform. It is defined as $CLICK/PV$ where PV is defined as the total number of displayed items.

§.§ Experimental Setup

In this section, we first introduce the pre-processing for offline datasets. Then we list the hyper-parameters of both baselines and our models.

Taobao Dataset only contains positive interactions, e.g., review, click, favorite, add to cart and buy. We use the same data pre-processing method with MIMN <cit.>. Firstly, for each user, we select the last behavior as the positive sample. Then we randomly sample a new item with same category as the negative sample for this user.

The rest behavior items are used as features. The samples are split into training set (80%), validation set (10%) and test set (10%) according to the timestamp $t$ of this sample.

Our Industrial dataset has positive and negative samples naturally because we log all the impressions for each user. An impression is labeled as positive if the item is clicked by the user. Otherwise, it is labeled as negative sample. We use the past two weeks' logs as training set and the following day as the test set, which is similar with SIM <cit.>.

For each model on different datasets, we use the validation set to tune the hyper-parameters to get the best performance. The learning rate is searched from $1\times10^{-4}$ to $1\times10^{-2}$. The L2 regularization term is searched from $1\times10^{-4}$ to $1$. All the models use Adam optimizer. The batch size is 256, 1024 for Taobao and our industrial dataset respectively.

Experimental results on Taobao Dataset. avg(48) and ta(48) represent encoding the user behavior sequence of length 48 by average pooling and target attention respectively. ta(256 -s- 48) represents conducting target attention on top-48 user behaviors which are selected via SimHash from the clipped user behavior sequence of length 256. Similarly, h in ta(256 -h- 48) represents the retrieval method of SIM(hard) and u in ta(256 -u- 48) represents the retrieval method of UBR4CTR. $\infty$ indicates the whole user behavior sequence. )
max width=1.0

Method       Encoding Manner     AUC

Avg-Pooling DNN     0 + avg(48)     0.9051

DIN     0 + ta(48)     0.9312

DIN (Long Sequence)     avg(256) + ta(48)     0.9358

UBR4CTR     ta(256 -u- 96)     -

UBR4CTR     ta($\infty$ -u- 96)     0.8496

UBR4CTR+timeinfo     ta(256 -u- 96)      -

UBR4CTR+timeinfo     ta($\infty$ -u- 96)     -

SIM(hard)     ta(256 -h- 48) + ta(48)     -

SIM(hard)     ta($\infty$ -h- 48) + ta(48)     0.9267

SIM(hard)+timeinfo     ta(256 -h- 48) + ta(48)      -

SIM(hard)+timeinfo     ta($\infty$ -h- 48) + ta(48)     0.9381

ETA      ta(256 -s- 48) + ta(48)     0.9425

ETA+timeinfo      ta(256 -s- 48) + ta(48)      -

Experimental results on Taobao Dataset.
max width=1.0

Method        AUC

Avg-Pooling DNN     0.8442

DIN      0.8626

DIN (Long Sequence)      0.8661

UBR4CTR      0.8651

UBR4CTR+timeinfo       0.8683

SIM(hard)     0.8675

SIM(hard)+timeinfo       0.8708

ETA      0.8721

ETA+timeinfo        0.8746

Experimental results on Industrial Dataset. avg(48) and ta(48) represent encoding the user behavior sequence of length 48 by average pooling and target attention respectively. ta(1024 -s- 48) represents conducting target attention on top-48 user behaviors which are selected via SimHash from the clipped user behavior sequence of length 1024. Similarly, h in ta(1024 -h- 48) represents the retrieval method of SIM(hard) and u in ta(1024 -u- 48) represents the retrieval method of UBR4CTR. $\infty$ indicates the whole user behavior sequence.  )
max width=2.0

No.       Method       Encoding Manner     AUC     Inference Cost(ms)

1      Avg-Pooling DNN     0 + avg(48)     0.7216     8

2      DIN     0 + ta(48)     0.7279     11

3      DIN (Long Sequence)     avg(1024) + ta(48)     0.7311     14

4      UBR4CTR     ta(1024 -u- 96)     0.7142     20

5      UBR4CTR     ta($\infty$ -u- 96)     0.7182     21

6      UBR4CTR+timeinfo     ta(1024 -u- 96)     0.7153     20

7      UBR4CTR+timeinfo     ta($\infty$ -u- 96)     0.7195     21

8      SIM(hard)     ta(1024 -h- 48) + ta(48)     0.7327     20

9      SIM(hard)     ta($\infty$ -h- 48) + ta(48)     0.7345     21

10     SIM(hard)+timeinfo     ta(1024 -h- 48) + ta(48)     0.7338     20

11      SIM(hard)+timeinfo     ta($\infty$ -h- 48) + ta(48)     0.7356     21

12     ETA      ta(1024 -s- 48) + ta(48)     0.7361     19

13     ETA+timeinfo      ta(1024 -s- 48) + ta(48)     0.7373     19

Experimental results on Industrial Dataset.
max width=2.0

Method        AUC     Inference Time(ms)

Avg-Pooling DNN     0.7216     8

DIN     0.7279     11

DIN (Long Sequence)      0.7311     14

UBR4CTR      0.7318     41

UBR4CTR+timeinfo     0.7331     41

SIM(hard)      0.7327     21

SIM(hard)+timeinfo      0.7338     21

ETA      0.7361     19

ETA+timeinfo      0.7373     19

Relative performance improvements and Inference Time in online A/B test compared with a DIN-based method without long-term user behavior sequence. Note that 1% improvement on GMV is a significant improvement because it means that millions of more revenues are brought to the recommender system.
min width=.4

Method      CTR     GMV     Inf. Time

SIM(hard)+timeinfo     4.53$\%$     6.6$\%$     21ms

ETA+timeinfo    6.33$\%$     9.7$\%$     19ms

§.§ Performance Comparison

Taobao Dataset: The evaluation results on Taobao dataset are shown in Table <ref>. From the table, we find that our ETA has stable performance improvements compared with all baselines. ETA outperforms SIM(hard) by 0.46% and outperforms DIN(Long Sequence) by 0.6%.
After adding time embedding, ETA+timeinfo outperforms SIM(hard)+timeinfo by 0.38% and outperforms DIN(Long Sequence) by 0.85%. Similar results can be observed on SIM(hard) and UBR4CTR.
It is observed that DIN(Long Sequence) brings 0.35% improvement on AUC compared to DIN, which shows the effectiveness of modeling the long-term user behavior sequence for CTR prediction.
We also find that UBR4CTR performs worse than DIN(Long Sequence). It is because that the feature selection model of UBR4CTR only selects the behaviors whose features(eg. category, weekday) are same with the target item. This kind of filtering in UBR4CTR helps removing noises away from the sequence, but can also lead to shorter user sequence, which is harmful when there are not enough items for top-k retrieval. From Table <ref>, we find that DIN outperforms Avg-Pooling DNN by 1.84%, demonstrating the fact that using target attention to encode the user sequence can greatly improve the performance.

Industrial Dataset: The evaluation results on our own Industrial Dataset are shown in Table <ref>. Note that 0.1% AUC improvement of CTR model can bring millions of real-world clicks and revenue in our online RS. Our ETA achieves the best performance compared with all baselines. Our base ETA achieves 0.34% and 0.43% improvements compared with SIM(hard) and UBR4CTR respectively. Our ETA+timeinfo achieves 0.35% and 0.42% improvements compared with SIM(hard)+timeinfo and UBR4CTR+timinfo respectively. Different from the experimental results in public dataset, SIM(hard)+timeinfo becomes the strongest baseline on Industrial Dataset and outperforms DIN(Long Sequence) by 0.27%. This is because of two reasons. On one hand, the user sequence length in Industrial Dataset is large enough, which is friendly to long-term user sequence based models. The average length of Industrial Dataset reaches 938, which is 9 times longer than the public Taobao dataset. On the other hand, DNN (Long Sequence) uses average pooling to encode the whole sequence without selection, which may import noises compared with retrieval based models such as UBR4CTR, SIM and ETA.

We can find another fact that SIM(hard) has 0.09% performance improvement compared with UBR4CTR. This is mainly caused by different processing methods on user behavior sequence. In SIM(hard), the user sequence is split into two separate sub-sequences, which is similar with our ETA in Figure <ref>. The short-term user behavior sequence $\mathcal{H}_{su}$ is made up of recent $k$ user behaviors from item 1 to item $k$. The long-term user behavior sequence $\mathcal{H}_{lu}$ is made up of another $k$ behaviors selected from item $k+1$ to item $n$. However, UBR4CTR selects a $2*k$-length behavior sequence from item $1$ to item $n$. As a result, the most recent $k$ items ($\bm{e}_1$ to $\bm{e}_k$ in Figure <ref>) are selected by SIM(hard) in 100% probability and are selected by UBR4CTR in $p$ probability decided by the feature selection model. However, timeinfo plays an important role in user interest modeling because user interest is dynamic and changes frequently. Thus SIM(hard) performs betther than UBR4CTR.

Online A/B Test: The evaluation results of online A/B test is shown in Table <ref>. Table <ref> shows the performance improvements over a DIN-based method, where the DIN-based method does not have long-term user behavior sequence. From Table <ref>, we find that our ETA+timestamp achieves 6.33% improvements on CTR and brings 9.7% extra GMV compared with the DIN-based method. Compared with the strongest baseline SIM(hard)+timeinfo, our ETA+timeinfo has extra 1.8% improvements on CTR and 3.1% improvements on GMV. Note that 1% improvement on GMV is a significant improvement because it means that millions of more revenues are brought to the recommender system.

xlabel=Bit-length of hashed fingerprint. (times of embedding size.),
xmin=0.25, xmax=4.0,
ymin=73.4, ymax=73.7,
legend pos=north west,
grid style=dashed,

AUC of ETA with different bit-lengths of hashed finger. The other model settings are the same with ETA in Table <ref>.

Ablation study of our ETA model on Industrial Dataset. v0 is the base version of ETA. avg($\cdot$) and ta($\cdot$) represent encoding user behaviors by average pooling and target attention respectively. ta(1024 -s- 48) represents conducting target attention on top-48 user behaviors selected from 1024 sequential user behavior items. Symbol s in ta(1024 -s- 48) represents SimHash is used to select top-48 from 1024. Similarly, symbol i in ta(1024 -i- 48) represents inner product is used to select top-48 from 1024.

ETA     Encoding     2*AUC     Inference

Version     Manner         Time(ms)

v0      ta(1024 -s- 48)      0.7361     19

v1      avg(1024)      0.7311     14

v2.1      ta(256 -s- 48)      0.7339     14

v2.2      ta(512 -s- 48)      0.7348     16

v2.3      ta(2048 -s- 48)      0.7394     23

v3      ta(1024 -i- 48)     0.7368     32

v4      ta(1024)      0.7371     35

§.§ Inference Time Comparison

Though the performance of CTR prediction is improved using long-term user behavior sequence, the model complexity increases accordingly. We measure the inference time of different models which are shown in Table <ref>. Avg-Pooling DNN has the smallest inference time of 8 milliseconds (ms). It  only encodes the recent behavior items with the average pooling method. After replacing average pooling to target attention, the inference time increases by 3ms (8ms to 11ms). After importing the long-term user behavior sequence, the inference time increases by another 3ms (11ms to 14ms) . SIM and our ETA have comparable inference time around 19$\sim$21 ms.

UBR4CTR has the largest inference time because an extra feature selection model is used before the retrieval stage, and an relative time-consuming IDF and BM25 based procedure is conducted online to get top-$k$ items.

§.§ Ablation Study

The results of ablation study is shown in Table <ref> to answer the research question RQ3. We use encoding manner to distinguish different versions (v0 to v4) of our ETA model. Note that v0 is the base version of ETA. The encoding manners are listed in the second column of Table <ref>, where avg($\cdot$) and ta($\cdot$) represent encoding user behaviors by average pooling and target attention respectively. ta(1024 -s- 48) represents conducting target attention on top-48 user behaviors selected from 1024 sequential user behavior items. Symbol s in ta(1024 -s- 48) represents SimHash is used to select top-48 from 1024. Similarly, symbol i in ta(1024 -i- 48) represents inner product is used to select top-48 from 1024.

From Table <ref>, the following observations are made. (i) Directly conduct multi-head target attention on the original 1024-length user sequence (v4) can achieve the best performance but have highest inference time at the same time. Comparing with v4, our base ETA (v0) selecting the top-$k$ behaviors for attention sacrifices about 0.1% AUC and reduces the inference time by 46%. (ii)  Comparing v3 with v0, replacing the SimHash with inner product at the retrieval stage achieves 0.07% improvement on AUC. However, the inference time increases by 68%, which is not acceptable with our strict online SLA (service level agreement). (iii) Trade-offs between AUC and inference time are observed when we change the length of user behavior sequence (v2.$x$ versus v0). The appropriate sequence length can be decided according to the requirements of online inference time. We also evaluate the performance under different bit-lengths of hashed fingerprints $\bm{h}$ generated by SimHash in Figure <ref>. As mentioned in Section <ref>, the bit-length of fingerprint can be controlled by the number of hash functions used in SimHash. We can find the fact that AUC can be improved by increasing the bit-length of $\bm{h}$. However, when bit-length of $\bm{h}$ is larger than $2\times$ embedding size, the improvement on AUC becomes marginal.

§ CONCLUSION

In this paper, we propose ETA model for CTR prediction task. To the best of our knowledge, ETA is the first method which can model the CTR together with long-term user behavior sequence in an end-to-end way. Compared to the SOTA two-stage models, the end-to-end paradigm enables the retrieval part share the information with the main part of CTR model seamlessly, which improves the prediction performance significantly. Besides, it is friendly for the maintenance and evolution of CTR model in large-scale online RS.
To achieve the goal of end-to-end online retrieval, we propose a SimHash based method to reduce the complexity of traditional top-$k$ retrieval from $O(L*B*d)$ multiplication to $O(L*B)$ hamming distance calculation, where $L$ is the length of user sequence. $B$ is the number of candidate items for each user request. $d$ is the dimension of item embedding.

Both offline and online experiments confirm the effectiveness of our ETA. The total GMV are improved by 3.1% in online A/B test compared with the SOTA model. ETA has been deployed online to serve the mainstream traffic.