Feature Staleness Aware Incremental Learning for CTR Prediction

1 Introduction

Click-through Rate (CTR) prediction is to estimate the probability of a user clicking a recommended item in a specific context [Qu et al., 2016; Cheng et al., 2020; Zhou et al., 2018; Guo et al., 2018; Sun et al., 2019; Zhikai and Yanyan, 2022]. As real-world recommender systems often encounter billions of user interactions every day, various methods [Chen et al., 2013; Barrett et al., 2017; Zhikai and Yanyan, 2023; Teredesai et al., 2019] have been proposed to update CTR prediction model in an incremental manner, which means that model will be fine-tuned with newly arrived data and possibly with part of historical data.

Typically, CTR prediction models [Krishnapuram et al., 2016; Guo et al., 2017; Mi et al., 2020; Peng et al., 2021]

involve a low-level feature embedding layer, followed by the high-level feature interaction and prediction layers. The parameters in the high-level layers are always updated with incremental data. However in the low-level layer, the feature embeddings will not be updated and get stale when the corresponding features do not appear in the incremental data [Wang et al., 2020]. For instance, if samples with "personal care products" feature only exist in previous time spans and missing in later time spans, the embedding of feature "personal care products" will be stale and become incompatible with the parameters in the high-level layers. When new samples with "personal care products" feature appear in incremental datasets, the model may not predict the CTR on them precisely. We call this problem the feature staleness problem.

Example 1. We use a real CTR prediction data Avazu [Wang et al., 2020] as examples which both consist of a pretraining dataset and ten consecutive incremental datasets denoted as {D0,D1, · · · ,D10}. We choose a state-of-the-art incremental learning (IL) method [Peng et al., 2021] as the base incremental method (BM) for illustration. In each time span t, we fine-tune the model parameters with Dt. We then test the BM on samples in Dt+1 which contain features with different staleness. The staleness is defined as the number of consecutive time spans for which a feature has been absent. We use the staleness to represent the out-of-date extent of a feature embedding. The average AUC performance on ten incremental datasets is reported in Figure 1. We can see that the model reports a lower average AUC on samples containing features with larger staleness, which reflects that the model suffers from the feature staleness problem on stale features, especially the feature absent for a long time, during the testing phase.

A vanilla way to mitigate the feature staleness problem is to replay all the samples, which contain stale features in each incremental step, to ensure all the feature embeddings are updated, which is referred as Full Stale Sampling (FSS). FSS can serve as a replay plug-in for the base model. As presented in Figure 1, BM+FSS can achieve remarkable AUC improvement on samples with stale features. However, this vanilla way has two limitations. First, in practice, the distribution of features can be scattered and vary among all incremental datasets. The set of all historical samples containing stale features will have an unaffordable size, and randomly sampling a subset cannot guarantee a high coverage of stale features. Second, it treats all stale features in the same way regardless of the extent of feature's staleness, which is not reasonable. For instance, repeatedly updating low-frequency features which keep stale for a long time will increase the risk of over-fitting [Wang et al., 2017]. On the contrary, some features are only stale for a few time spans, which are similar to unstale features, should be updated normally. The improvement on samples with smaller staleness features is more remarkable in Figure 1, which validates the second limitation.

In this paper, we propose a Feature Staleness Aware Incremental Learning method for CTR prediction (FeSAIL) to overcome the above mentioned limitations. We introduce a staleness aware sampling algorithm (SAS) using a fixedsize reservoir to store samples with stale features. We aim to cover as many features with small staleness values as possible, which is formulated as a maximum weighted coverage problem and solved by a greedy algorithm with an approximation ratio of 1 - 1e compared to the optimal solution. We then introduce a staleness aware regularization mechanism (SAR) to restrict the updating of feature embeddings according to the extent of features' staleness.

The major contributions are summarized as follows.

• We observe the feature staleness problem existing in incremental learning of CTR prediction models and propose a feature staleness aware IL method named FeSAIL to mitigate this problem.
• We introduce the SAS algorithm based on feature staleness and solve it as a maximum weighted coverage problem greedily to guarantee the sampling efficiency. We also design the SAR algorithm for a fine-grained control of lowfrequency feature updating.
• We instantiate FeSAIL with a general deep learning-based CTR prediction model and conduct extensive experiments, which demonstrates that FeSAIL can efficiently alleviate the feature staleness problem and achieve 1.21% AUC improvement compared to the state-of-the-art IL methods for CTR prediction on three widely-used public datasets and a private dataset averagely.

2 Preliminaries

CTR prediction aims to estimate the probability that a user will click a recommended item. Generally, CTR models include three parts: embedding layer, interaction layer and prediction layer [Rendle et al., 2010; Guo et al., 2017; Wang et al., 2020; d'Aquin et al., 2020]. In typical CTR prediction tasks, the input of each sample is collected in a multi-field form [Wang et al., 2020; Wang et al., 2017; He and McAuley, 2016]. The label y of each sample is 0 or 1 indicating whether a user clicked an item. Each field Fi (1 ≤ i ≤ m) is filled with one specific feature fi from feature space Fi with size ni, where m is the number of fields. Each data sample is transformed into a dense vector via an embedding layer. Formally, for a sample d = {f1, f2, · · · , fm}, each feature is encoded as an embedding vector ei ∈ R1×k , where k is the embedding size. Therefore, each sample can be represented as an embedding list E = (e⊤1 , e⊤2 , · · · , e⊤m) ∈ Rm×k . Let the total number of features be N = ∑mi=1 ni. The embeddings of all the features form an embedding table E ∈ RN×k . In the interaction layer, existing models [Guo et al., 2017; Wang et al., 2017; Kang and McAuley, 2018; Caverlee et al., 2020] utilize product operation and multi-layer perception to capture explicit and implicit feature interactions. And prediction ˆ y is generated as the probability that the user will click on a specific item. The cross-entropy loss is calculated between the label y and the prediction ˆ y.

Given a series of CTR prediction datasets {D0,D1, · · · ,Dt, · · · } indexed by time span. In IL scenario, at time span t, Dt is the current dataset and Dthis = {D0,D1, · · · ,Dt-1} contains all the historical datasets. If we train the model using the current dataset and all the historical datasets, the size of the training data will grow overwhelmingly large. In many existing IL methods for CTR prediction [Mi et al., 2020; Mi and Faltings, 2020], instead of preserving the whole historical datasets, they first initialize a reservoir R0 using D0, which serves as a replay buffer. As time span t, they generate the reservoir Rt based on Rt-1 ∪Dt-1 and train the model using Rt and Dt, which can greatly reduce the size of the training data. In this paper, we follow this setting and investigate how to find an efficient way for sampling Rt from Rt-1 ∪Dt-1 and update the model parameters using Rt and Dt such that the model can achieve better performance on Dt+1 at each time span t.

3 The FeSAIL Approach

3.1 Overview

The FeSAIL is a feature staleness aware IL method for training CTR prediction models to mitigate the feature staleness problem. As presented in Figure 2, FeSAIL can be divided into sampling and training stages for each time span t: In the sampling stage, the staleness aware sampling (SAS) strategy first uses a reservoir Rt with a fixed size to store samples containing stale features and uses a greedy algorithm to cover as much staleness features as possible. In the training stage, the model will be trained on Rt and the incremental dataset Dt with the staleness aware regularization (SAR), which restricts the embedding updating of features according to the extent of features' staleness.

3.2 Staleness Aware Sampling (SAS)

In this section, we introduce how our method chooses samples for the reservoir based on the feature staleness. Our key insight is that resampling samples with stale features, which refer to the features not appearing in the current dataset, can help mitigate the performance degradation on new samples involving stale features, as illustrated Figure 1. A na¨ıve way to generate Rt is to choose the samples from Rt-1 ∪ Dt-1 containing features that do not appear in Dt, which is referred as Reservoir-based Stale Sampling (RSS). More formally, let FDt denote the feature set of Dt. We add a sample d = {f1, f2, · · · , fm} in Rt-1 ∪Dt-1 to Rt if d involves at least one feature that is not included in the feature set of Dt, i.e., ∃fi /∈ FDt where 1 ≤ i ≤ m. The model will be trained with Rt and Dt jointly. In this way, the chosen samples in Rt can supplement the feature set of Dt and update the feature embeddings such that the embeddings can adapt to the updated high-level layers in the model.

However, in real scenarios such as news and short video recommendation, the distribution of features can be quite scattered and vary among different incremental datasets [Huang et al., 2020a; Peng et al., 2021]. Even using the above mentioned method will still preserve samples with an uncontrollable size and incur high computation cost. A more desirable solution is to design a reservoir with a fixed size L to store historical samples with stale features. Honestly, a fixed-sized reservoir may not be able to cover all the stale features. To mitigate the performance degeneration to the maximal extent, we compute the fixed-size reser-

Algorithm 1: SAS algorithm

Input : a reservoir fromRSS Rt = {d1, d2, · · · , d|Rt|}, where each sample dl = {f1, f2, · · · , fm} associated weights {wi}mi=1 , a given capacity L Output: a collection of samples Rfixed t ⊆Rt 1 Rfixed t ← ∅; 2 for L iterations do 3 select dl ∈ Rt that maximizes Wl; 4 Rfixed t ←Rfixed t +dl; 5 end

voir based on two rules. First, the designed reservoir should cover as many stale features as possible. Second, the features with smaller staleness will be covered with higher priorities because they might have higher possibilities of reappearing again in future datasets. We first quantify the feature staleness. Formally, each feature fi is assigned with one staleness sti which is initially set as 0. At time span t, the staleness of feature fi will be:

where FDt denotes the set of feature values contained in Dt. Then we define the weight of each feature which has an inverse correlation with its staleness:

where func(·) is an inverse correlation function like an inverse proportional function or negative exponential function, and b is a bias term. Our goal is to select a fixed number of samples with as many stale features as possible, which can be formulated as follows.

Definition 1 (Stale Features Sampling (SFS)). Given the reservoir Rt = {d1, d2, · · · , d|Rt|} of RSS where each sample dl contains m features {f1, f2, · · · , fm} associated with weights {wi}mi=1 . The SFS problem is to find a collection of samples Rf ixed t ⊆Rt, such that the total number of samples in Rfixed t does not exceed a given capacity L and the total weight of features covered by Rfixed t is maximized.

The above problem is a generalized version of the standard maximum coverage problem (MCP) [Chekuri and Kumar, 2004], which has been proved that an exact solution is intractable because the search space is too large. We develop a greedy algorithm (SAS) which can yield an approximation ratio of 1 - 1e compared to the optimal solution.

Let Wl denote the total weight of the features covered by sample dl, but not covered by any sample in Rfixed t . As presented in Algorithm 1, SAS has L iterations. In each iteration, SAS will calculate Wl for each sample in Rt and select the sample with the maximum Wl.

Let bl denote the total weight till lth iteration, i.e., bl = ∑lj=1 Wj and OPT denote the optimal solution of the SFS.

Let cl denote the left weight for optimal, i.e., cl = OPT -bl. Let b0 = 0, c0 = OPT .

Lemma 1. In l + 1th iteration, we always have Wl+1 ≥ clL , where Wl+1 is a possible total weight.

Proof. The optimal solution reaches OPT weight at L iterations. That means, at each iteration l+1 there should be some unchosen samples in Rt whose contained weight greater than cl L-l ≥ clL . Otherwise, it was impossible to cover OPT weight at L steps by the optimal solution. Since the approximation algorithm is a greedy algorithm, i.e., choosing always the set covering the maximum weight of uncovered elements, the weight of chosen set at each iteration should be at least the 1L of the weight of remaining uncovered elements.

Lemma 2. In l +1th iteration, we have cl+1 ≤ (1- 1L )l+1 · OPT, where cl+1 is the optimal left weight.

Proof. We prove Lemma 2 by mathematical induction.

Base case: If l = 0,

So c1 ≤ (1 - 1L ) · OPT and the lemma holds when l = 0. Inductive hypothesis: Suppose the theorem holds for l ≥ 0.

Theorem 1. SAS can achieve an 1 - 1e approximation ratio compared to the optimal solution for SFS.

From Theorem 1, we know that SAS will drop about 30% more stale features than the optimal solution. However, the SAS chooses the features with small staleness in prior and the actual drop ratio of stale features will be about 10%, which is testified in Section 4.5. The complexity of SAS is O(|Rt| ∗ L ∗ m), where m is the number of feature fields and Rt| is the size of reservoir from RSS which still have high computation cost because both |Rt| and L can be million scales. We propose neighbour-based SAS which can decrease the complexity to O(|Rt| ∗m+ ¯ |Q|N ∗ L ∗ m), where the neighbours N refer to the samples which have at least one common stale features with the current chosen sample and ¯ |Q|N denotes the mean of the neighbour numbers. Before Line 3 of Algorithm 1, we only need to update Wl of these neighbour samples rather than all samples in the reservoir. Because only samples sharing at least one stale feature will be neighbors, ¯ |Q|N is much smaller than the total number of samples. For example in Avazu, the ¯ |Q|N is in the 1e3 scale and the sample number or the total feature number is in the 1e8 scale.

3.3 Staleness Aware Regularization (SAR)

Intuitively, the features keeping stale for a long time are probably low-frequency features. Updating their embeddings too frequently will increase the risk of over-fitting [Wang et al., 2017; Sun et al., 2022]. We follow the regularization-based methods [Mi et al., 2020] to restrict the embedding updating of these kind of features using regularization term. However, a certain ratio of features only stale for one or two time spans, whose regularization term will be quite large and become an unaffordable burden for the model training. Thus it is unreasonable to treat all stale features equally regardless of the extent of feature staleness. More formally, we add a regularization loss for feature fi, which is called guard:

where smax is the max staleness in the current time span, ∆ei is embedding change for feature fi between two consecutive mini-batches, and η is a hyperparameter used to exclude the extreme staleness value. smax is used to normalize the staleness to mitigate the influence of the dataset's overall staleness extent. Thus the total loss of FeSAIL will be:

where LCE,d refers to the cross entropy loss of model training on sample d, and λ is the regularization coefficient.

3.4 Implementation Details

We implemented our FeSAIL approach using Pytorch 1.10 on a 64-bit Linus server equipped with 32 Intel Xeon@2.10GHz CPUs, 128GB memory and four RTX 2080ti GPUs. The proposed FeSAIL is model-agnostic. To test its effectiveness, we instantiate it on a general deep learning-based Embedding&MLP model, a network architecture that most of the CTR prediction models developed in recent years are based on [Peng et al., 2021; Huang et al., 2020a; Lim et al., 2017]. By default, we set the inverse correlation function in Eq. (2) as the inverse proportional function and the bias term as 1. The sampling reservoir size L of Rt is the same size as the corresponding incremental dataset Dt. We use a grid search over the hidden layer size, initial learning rate and the number of cross layers. The batch size is set from 256 to 4096. The embedding size and hidden layer sizes are chosen from 32 to 1024. The η in Eq. (3) is from 5 to 10. We choose the Adam optimizer [Diederik P. Kingma, 2015] to train the model with a learning rate from 0.0001 to 0.001 and perform early stopping in the training process.

3.5 Complexity Analysis

Time Complexity. The computational complexity of SAS isO(|Rt|∗m+ ¯ |Q|∗L∗m) using neighbor based optimization. The regularization term for SAR has complexity as O((|Rt|+ |Dt|) ∗ m). Thus the total external time complexity will be negligible compared to model training.

Space Complexity. SAS needs to store |Rt| samples, the size of which is fixed and can be set according to the actual memory space. And the SAR is a non-parameterized module which does not require extra storage space.

4 Experiment

We conduct the experiments to evaluate the performance of our proposed method and answer the following questions :

• RQ1 Can the proposed FeSAIL outperform the existing IL methods on CTR prediction?
• RQ2 How do the SAR and SAS algorithms affect the effectiveness of FeSAIL ?
• RQ3 How do different inverse correlation functions and biases influence the performance of FeSAIL?
• RQ4 How does the SAS deal with features with different staleness?

4.1 Experimental Setups

Datasets. We use three real-world datasets from Criteo 1 , iPinYou 2 , Avazu 3 and one private industrial dataset collected from a commercial media platform.

• Criteo This dataset consists of 24 days' consecutive traffic logs from Criteo, including 26 categorical features and the first column as a label indicating whether the ad has been clicked or not.
• iPinYou This dataset is a public real-world display ad dataset with each ad display information and the corresponding user clicks feedback. The data logs are organized by different advertisers and in a row-per-record format. There are 21.92M data instances with 14.89K positive labels (click) in total. The features for each data instance are categorical.
• Avazu This dataset contains users' click behaviours on displayed mobile ads. There are 20 feature fields, including user/device features and ad attributes.
• Media This is a real CTR prediction dataset collected from a commercial media platform. We extract 48 consecutive hours of data that contains 337 categorial feature fields.

The detailed statistics of the datasets are listed in Table 1. For a fair comparison, we follow the same data preprocessing and splitting rule for all the compared methods.

Evaluation Metrics. We use the following two metrics for performance evaluation: AUC (Area Under the ROC curve) and Logloss (cross entropy), which are commonly used in CTR prediction works [Zhang et al., 2014; Zhu et al., 2019].

Baselines. We compare our proposed FeSAIL with six baselines including two existing sample-based and two model-based IL methods for training CTR prediction models.

• Incremental Update (IU) updates the model incrementally using only the new data.

1 https://www.criteo.com

2 https://www.iPinYou.com

3 https://www.kaggle.com/c/avazu-ctr-prediction

• Random Sample (RS) updates the model using the new data and the randomly sampled historical data.
• RMFX (sample-based) [Diaz-Aviles et al., 2012] is a matrix factorization-based model which uses an active learning sampling algorithm to replay the most informative historical samples.
• GAG (sample-based) [Huang et al., 2020b] is a method which uses a global attributed graph neural network for streaming session-based recommendation. We regard one sample in the CTR task as a piece of session in this model.
• EWC (model-based) [Kirkpatrick et al., 2016] is a general IL method which prevents the model from changing the informative parameters learned in previous datasets.
• ASMG (model-based) [Peng et al., 2021] is a metalearning-based incremental method for CTR prediction models, which uses a sequentialized meta-learner to generate model parameters in the next time span.

RMFX+SAR and GAG+SAR add the guard term in Eq. (3) on the loss function (SAR) of original RMFX and GAG. Similarly, EWC+SAS and ASMG+SAS use our sample method SAS to enhance the performance of EWC and ASMG, which is designed to prove the effectiveness of guarding term. Note that we use the same reservoir size for our SAR and samplebased baselines.

4.2 Experimental Results: RQ1

Table 2 presents the overall performance on four datasets (the results are all averaged over ten runs), where we have the following observations.

First, RS performs slightly better than IU, which reflects that the future samples also need the old knowledge preserved in historical samples. Second, RMFX+SAR and GAG+SAR perform better than RMFX and GAG respectively, which shows restricting the feature embedding updating according to its staleness can also improve the performance of methods with other sampling strategies. Third, EWC+SAS and ASMG+SAS perform better than EWC and ASMG respectively, which indicates using a fixed size reservoir to replay stale features is compatible with these model-based methods using other regularization strategies. Fourth, FeSAIL achieves 0.95%, 1.38%, 0.78% and 1.72% relative improvements compared to ASMG, the best baseline on four datasets, respectively. The reason why FeSAIL achieves greater improvement on Media might be that Media has lower feature staleness extentwhich is easier to be overcome by SAS. Figure 3 shows the disentangled performance at each time span. The performance of all methods has a similar trend on different datasets, and FeSAIL outperforms all the other methods in most time spans.

4.3 Ablation Study: RQ2

We perform an ablation study on Avazu to evaluate the effects of different components of FeSAIL on the performance. Similar conclusions can be drawn on Criteo, iPinYou and Media. Specifically, we consider the following settings.

• Incremental Update (IU) 4 updates the model incrementally using only the new data.

4 For a fair comparison, we supplement the latest historical samples to make the total sample size the same as FSS.

IU

Table 3: Average sampling and retraining time on Avazu.

• Full Stale Sampling (FSS) updates the model with new data and all the historical samples containing stale features.
• Reservoir-based Stale Sampling (RSS) updates the model using new data and all the samples in the reservoir.
• RSS+SAR add the SAR on RSS.
• RSS+SAS restrict the reservoir size of RSS using SAS.
• FeSAIL using both the SAR and SAS on RSS.

The results are presented in Figure 4. The line chart reflects the AUC difference between different methods. We can see that FeSAIL performs best among all the comparison methods, which shows the removal of any component from FeSAIL will hurt the final performance. SAR and SAS jointly contribute to improving the RSS performance. The bar chart reflects the sample number in each time span. We can see that FSS samples size increases during incremental learning

b

Figure 5: Parameter sensitivity w.r.t different inverse correlation functions and biases on Avazu.

due to the growing size of historical samples. However, the sample sizes of RSS and FeSAIL maintain relatively stable. Moreover, the sample size of FeSAIL is fixed and controllable, which is more friendly to real-world incremental recommendation systems. One concern of SAS is to control the time cost of sampling and model training. Table 3 shows the average sampling time and the retraining time of each method over different time spans on Avazu. The time cost for SAR is negligible compared to the total training time cost. SAS can remarkably reduce the sample size and accelerate model retraining. In the meanwhile, thanks to the neighbour-based SAS algorithm, the sampling time cost for SAS is bearable.

4.4 Parameter Sensitivity: RQ3

We investigate the sensitivity of choosing different inverse correlation functions func and bias b in Eq.(2). We choose Avazu, and report the average AUC (line chart) and Jaccard Similarity (JS) of chosen samples set with the control group (the group with the highest AUC) over ten time spans. The func is chosen between inverse proportional function 1/si and negative exponential function exp(si). The b is chosen from [0, 0.1, 0.5, 1, 2, 5, 10], where the larger b means the less consideration for feature staleness. As shown in Figure 5, the performance on two datasets achieve a similar JS with two func and b in the range [0.1, 0.5, 1, 2], which means the chosen samples set is insensitive to the func and the b within a moderate range and productively achieve a competitive AUC towards the control group. The reason might be that only the relative weight sum order of samples will influence the choosing order in Algorithm 1, and choosing different func and b with small values will not change the relative weight sum order of samples.

4.5 Case Study: RQ4

We perform a case study on iPinYou to illustrate the effectiveness of SAS in selecting samples. As presented in Figure 6, we have two observations. First, the overall feature drop ratio after SAS is around 10%, which is consistent with the approximation ratio given by Algorithm 1. Second, the features with larger staleness have a higher drop ratio in most time spans except in the first several time spans, which do not have features with staleness larger than its time span index. It means SAS prefers to choose features with smaller staleness, which is consistent with our motivation and mitigates the low-frequency features' influence on performance.

5 Conclusion

In this paper, we show the feature staleness problem existing in CTR prediction and propose a feature staleness aware IL method for CTR prediction (FeSAIL) to mitigate this problem by adaptively replaying samples containing stale features. We first introduce a feature staleness aware sampling algorithm (SAS) to guarantee sampling efficiency. We then introduce a feature staleness aware regularization mechanism (SAR) to restrict the low-frequency feature updating. We conduct extensive experiments and demonstrate that FeSAIL can efficiently tackle the feature staleness problem. On average, it achieves 1.21% AUC improvement compared to various state-of-the-art methods on three widely-used public datasets and a private dataset.

Acknowledgements

This work is supported by the National Key Research and Development Program of China (2022YFE0200500), Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102), the Tencent Wechat Rhino-Bird Focused Research Program, and SJTU Global Strategic Partnership Fund (2021SJTU-HKUST). Yanyan Shen is the corresponding author.