In current online advertising applications, look-alike methods are valuable and commonly used to identify new potential users, tackling the dificulties of audience expansion. However, the demographic information and a variety of user behavior logs are high dimensional,noisy, and increasingly complex, which are challenging to extract suitable user profiles. Usually, rule-based and similaritybased approaches are proposed to profile the users' interests and expand the audience. However, they are specific and limited in more complex scenarios. In this paper, we propose a new end-to-end solution, unifying the feature extraction and profile prediction stages. Specifically, we present a neural prediction framework and leverage it with the intuitive audience feature extraction stages. We conduct extensive study on a real and large advertisement dataset. The results demonstrate the advantage of the proposed approach, not only in accuracy but also generality.
• Information systems → Online Advertising; • Human-centered computing → User Models; • Theory of computation → Computational Advertising theory; • Computing methodologies → Factorization methods;
The remarkable growth of online advertisement enables the ad-vertisers to sync up their products according to the fastchanging needs of the consumer. As the development of e-commerce platforms has introduced SMEs (Small and medium-sized enterprises) to enter consumers’ sight, large enterprise advertisers face the crisis of slowing business growth and falling revenue. Therefore, brand advertisers have begun to pay more attention to the contribution of advertising to sales conversion, the actual revenue brought by advertising, requiring advertising agencies and third-party suppliers to provide more refined performance data of advertising efects.
Meanwhile, the emergence of big data technology has subverted the operation model of the entire advertising industry and the traditional way of evaluating advertising efects. By tracking and obtaining user behavior data, a third-party supplier of advertising monitor can analyze the data according to the advertiser needs, not only understanding the communication efects and sales conversion rate generated by the advertisement in time but also predicting the user conversion probability to some extent. Through analysis and modeling on massive data of user behavior, advertisers can accurately reach the target consumer. Therefore, how to better utilize the advertising monitor data in order to optimize ad serving and improve marketing conversion rate has become an important issue.
One of the main challenges in ad serving is how to find the best converting prospects. A typical way is to do audience expansion, that is, to identify and reach new audiences with similar interests to the original target audience. Usually, the methodology used in audience expansion problem is called look-alike modeling. Given a seed user set S from a universal set U , look-alike models essentially ifnd groups of audiences from U − S who look and act like the audience in S.
The data flow of audience expansion service is illustrated in Figure 1. The data runs between advertisers and our universal advertising monitor system across diferent media platforms. The original users come from the advertiser’s CRM System selecting the consumers who recently exercise the purchase actions. Then the users who are tracked by the universal advertising monitor will be matched and treated as "seed" users.
In this paper, we build up a closed-loop data solution for brand advertisers and combines multiple techniques of selecting negative samples and extracting features, as well as machine learning lookalike models to reach the targeted audience. Which greatly enhances the conversion efect of ad serving. Based on the "seed" users and universal user set from advertising monitor, we build a lookalike model to predict the probability to be the target audience for all users. Afterward, according to the advertising budget, lookalike model will yield the corresponding number of expanded users to be reached through ad serving system. Finally, the ad serving performance is evaluated by advertiser’s site monitor system that record sales conversion shortly.
But both traditional and current look-alike strategies for an advertiser to look for the target audience are mainly based on user demographics. There are two main problems with demographicsbased audience segmentation: user demographics (age, gender, and geographical location) itself is not precise as it is estimated via various statistical methods or machine learning models based on a small group of surveyed samples (10-100 thousand); the number of users that are specified by demographics is large, more sophisticated screening is required. Accordingly, the details of user behavior data should be harnessed in machine learning models to target accurate audience segment. At the same time, there are two main problems that need to be solved based on user behavior data modeling: user-generated behavior data through the Internet is generally high-dimensional and sparse; advertisers usually can only provide positive samples, while negative samples need to be carefully picked up from a substantial unlabeled sample set.
Besides, the ecologically closed Internet tycoons (represented by Facebook, Amazon, Tencent, Alibaba and etc.) provide the advertisers the capability to perform audience expansion within their own platforms. However, ad serving data of these platforms are not connected with the advertiser’s CRM (Customer Relationship Management) system. Thus, it is dificult to directly track the real conversion rate. In order to verify that lookalike models based on the user behaviour work better than traditional demographicsbased approach regarding the sales conversation rate, we need to integrate data flow during the whole advertising life cycle.
The contributions of this paper can be summarized as follows. • We have improved the commonly used ad serving mode from demographics-based crowd segmentation to a comprehensive audience expansion framework. • We propose a lookalike model that has better generalization ability for audience expansion problem. • We conduct extensive and efective experiments to extract negative samples from unlabeled data. • We prove the efectiveness of the proposed lookalike models in an online environment.
The rest of the paper is organized as follows. In Section 2, we review the related work on various kinds of look-alike models and illustrate diferent design philosophy behind them.
Section 3.3 gives out the formal problem statement and specifies the notations used in the paper. We then introduces our proposed lookalike models and Section 3.4 reveals the sampling strategies. The evaluation of the algorithm is presented in Section 4. Finally the conclusion and future work are discussed in Section 5. 2
We briefly review the related literature of look-alike modeling. Generally in online user-targeted advertising areas, look-alike modeling which supports audience expansion system can be categorized in three lines: rule-based, similarity-based and model-based.
Rule-based approaches focus on explicit positioning, where
users with specific demographic tags (age, gender, geography) or
interests are targeted directly for advertiser. The core technical
support in the background is user profile mining, which means,
the interest tags are inferred from the user behaviour [
Similarity-based approaches apply diferent similarity
metrics to solve the problem of look-alike modeling. Naive
similaritybased method computes pairwise similarities between and seed
user and all the other users in the set while the locality-sensitive
hashing (LSH) [
Model-based look-alike systems fall into two categories:
unsupervised and supervised learning. For instance, k-means
clustering [
A key challenge in applying collaborative filtering lies also on
the extreme sparsity of interaction between users and campaign
and the way Kanagal et al. [
Here we first formalize the problem and then list the feature extraction and the prediction framework. 3.1
We formalize the look-alike modeling as a prediction problem. Advertisers submit a list of customers, which we call seed user set S, as positive samples and there are a universal user set U existing in advertising monitor platform. Then the problem is transformed into a Positive and Unlabeled learning problem: using a small number of labeled positive samples S and a large number of unlabeled samples U − S to derive a prediction classifier. Eventually unlabeled users are scored by the classifier and the target audience set T is taken out according to advertising requirements. The dataset sizes are typically configured in real business environment as follows: ∥S ∥ = 0.1−0.2M(Million), ∥T ∥ = 10−20M and ∥U ∥ = 2000−3000M. Meanwhile, a user is represented by a feature vector which indicates the user’s past behaviour collected by the advertising monitor system. The feature vector always occurs with high-dimension D and extreme sparsity. D is usually around 100-300 thousands and only 0.1 percent of the feature vector are non-zero elements. 3.2
Here we introduce the feature extraction and analysis stages in the lookalike model.
Each row of the original data collected by advertising monitor
system represents an ad impression. The "CLICK" column is an
indicator that shows whether or not the advertisement is clicked
by the corresponding user (1 represents CLICK while 0 means
the opposite). As shown in Table 1, The main information of an
ad impression includes timestamp, user_ id and an spid. The spid
refers to the specific information of an advertisement where they
are multi-field categorical data [
The user behaviour is represented by a high-dimensional sparse feature vector where each feature corresponding to the times an advertisement is clicked or impressed. One typical feature extraction result is shown in Table 2, User "66a7988f " is impressed by spid1 and spid2 both 3 times while he only clicks spid2 once. The user feature vector will be normalized afterwards. The normalization approach is as follows where f req represents the original frequency and norm_f req is the frequency after normalization:
1 norm_f req = 1 + exp(− f r1e0q ) f req > 0 (1) 0 f req = 0
To this end, every feature value is converted to a number between 0 and 1.
It is noteworthy that the data label is the purchase tag (meaning the corresponding user has purchase action) from CRM system of a particular brand advertiser over a period of time, while features represent the impression and click behaviour for ads of diferent brands. Unlike the high-dimensional sparse feature transformed by one-hot encoder in CTR prediction task, the original feature space is already sparse and high-dimensional.
The intuitive idea of utilizing spid as feature is that the ads are somehow correlated to the websites highly indicating user interests. That is to say, when an internet user is impressed by an specific ad, the ad itself could describe the user interests to some extend. Moreover, "CLICK" information directly connects user intention. The detailed comparison of diferent feature extraction methodologies will be incorporated in Section 4.2. 3.3
We continue to introduce the lookalike model techniques used in our audience expansion system. Multilayer Perceptron (MLP) is a feedforward neural network consisting of several layers. By adding non-linear activation functions, MLP can fit high-order non-linear features. Figure 2 illustrates a MLP network added by a scale layer.
y = mlp(A(W ◦ X ) + bias), A ∈ Rk×n (3)
The model expressibility of Equation 2 and 3 is the same so that there is no diference at model prediction stage. That is to say, the theoretical optimal solution of MLP and Scale-MLP are the same. However, deep models don’t always converge to the same optimal solution in practice, therefore, the efectiveness of actual models obtained from Scale-MLP and MLP are often diferent on diferent datasets.
To be detailed, the essential diference lies in the way backpropagation update the network parameter during model training stage. Compared to a standard MLP, Equation 3 reflects that the network need feedforward an intermediate result wj xj after the scale layer added. When MLP updates the parameter matrix A during backpropagation , the partial derivative regarding ai j is xj ; for Scale-MLP, the partial derivative regarding ai j is wj xj while regarding wj is xj . In another word, the value of feature xj in MLP can directly afect the parameters ai j , i = 1...k; for Scale-MLP, feature xj can only update wj .
Assuming that the influence of diferent features on the model is quite diferent, the fluctuation of feature values will make training process dificult to converge. Suppose that the feature xj has little efect for the target, when the values of xj drifts, it will cause training dificulty unless the absolute value of parameters ai j , i = 1...k are all small; on the other side, as long as the absolute value of the only afected parameter wj in Scale-MLP model is small, the influence of the feature on the target can be made smaller. To conclude, adding the scale layer and updating the parameters of the scale layer during backpropagation can directly change the final influence of each feature on the model.
Generally saying, for MLP model, matrix A captures the firstorder combinatoric features. In order to learn high-order features, the model need to fit the data by adjusting both the parameters of matrix A and the hidden layers of MLP. Due to the sparsity of feature space and importance of diferent features varies, the parameters of matrix A cannot be very efectively trained. Under such circumstances, the MLP model is easier to overfit. On the contrast, the Scale-MLP model only needs to train the parameters of the scale layer properly for the same purpose. Therefore, ScaleMLP model is much simpler to train in our setting.
Another angel to look at the functionality of the new model is that it adds randomness to the original user feature vector. In other words, if a user is not impressed by some ad, it doesn’t mean that he/she is totally not interested in that ad. Therefore, the scale layer will help to learn a model which has better generalization capability for this task. 3.4
Model Training 3.4.1 The Impact of Sampling Ratio. We evaluate the impact of sampling ratio based on diferent number of positive and unlabeled samples, seeing unlabeled as negative label. The standard classification algorithm we choose is Logistic Regression. The key metrics need to be taken care are test recall and threshold, meaning positive sample recall on testing data set and the corresponding probability boundary. The number of positive and negative samples in testing data set are 34657 and 72464. The evaluation result in Table 3 shows when ratio of positive and unlabeled reaches 1:2 (the number of positive and negative samples are 69331 and 134584 respectively), the threshold doesn’t change significantly when more unlabeled samples are added. Considering both training eficiency and efectiveness, it is practical to set the sampling ratio of positive:negative as 1:2.
3.4.2 Sampling Techniques. For general classification problem,
to determine where the class boundary is, at least some of the
negative samples to be close to the positive ones are chosen. Take
"active learning" [
Besides randomly selecting negative samples and directly apply
standard classifier to the PU learning problem, we compare the
efectiveness of three other sampling techniques: spy, pre-train and
bootstrap sampling. The "Spy" [
Input: Positive Sample Set P , Unlabeled Sample Set U Output: Negative Sample Set N with size k 1 Randomly select a subset from P as the spy set P ′; 2 Train a classifier M based on P − P ′ and U + P ′; 3 Select a subset N of k samples from U with least prediction scores; 4 Return N ;
Input: Positive Samples Set P , Unlabeled Sample Set U ,
Validation Set V
Output: Negative Sample Set N with size k 1 Randomly select a subset N with size k from U ; 2 while true do 3 Randomly select a subset N ′ from N ; 4 Train a classifier M based on P and N ′, and evaluate the model on V ; 5 if the accuracy of M doesn’t improve on V then 6 Return N ; 7 break;
A more sophisticated approach [
Input: Positive Sample Set P , Unlabeled Sample Set U Output: Negative Sample Set N with size k 1 for t ≤ T do 2 Bootstrap a subset U ′ from U ; 3 Train a classifier M on P and U ′; 4 Predict U − U ′ using classifier M; 5 Record the classifying scores;
7 Select a subset N of k samples with least average scores; 8 Return N ;
Table 4 shows the experimental result of diferent sampling approaches. The samplinд parameter represents the percentage of unlabeled samples picked out as negative and threshold indicates the corresponding probability boundary. From the result table it can be seen that when spy and bootstrap approaches sample half size of the unlabeled data, it still guarantees almost the same level of recall on testing data while regarding pre-train sampling approach, the recall on test data is much lower. On the sampling eficiency, spy approach can only run one iteration compared to the other two which need converge after several rounds. Therefore, it is both eficient and efective to utilize spy sampling approach in our setting.
Logistic Regression: Logistic Regression (LR) is probably the most widely used baseline model. Suppose there are n features {x1, x2, ..., xn } and xi is either 0 or 1, consider an LR model without a regularization term:
y = bias + βT X (4) where β is the coeficient vector. This simple linear model misses the crucial feature crosses, therefore, the Degree-2 Polynomial (Poly2) model is always provided to ease the problem.
y = bias + βT X + XW XT (5) where W is a symmetric parameter matrix with the elements on the diagonal are all equal to 0.
Factorization Machine In order to extract feature crosses while
reducing the influence of high-dimensional sparse features, Rendle
[
To overcome this problem, we will decompose W into V V T where each vi in V = (v1, v2, ..., vn )T can be seen as a latent kdimensional factor of original feature. The Degree-2 F M model equation is defined as: y = bias + βT X + XV V T XT , V ∈ Rn×k (6)
At this time, the number of parameters need to be estimated is n · k and easier to train even under sparsity setting as F M model break the independence of the interaction parameters by factorizing them. 4 4.1
Regarding the model implementation, we use MXNet1 on a standalone 1080TI GPU to compare diferent model efects and figure out model parameters. When predicting the universal user pool consisting of nearly 2.5 billion users, we used distributed MXNet on a 80-cores hadoop cluster to re-train the model and it took nearly 4 hours to finish the prediction of all users. 4.2
Table 5 shows the impact of diferent feature engineering approaches. In this table, T ime Slice indicates the strategy of calculating the user behaviour by time slice (None: no time slice; day: slice by day; holiday: slice by holiday and weekday; month: slice by month). For example, if we extract features of user activities by month, one typical feature could be that one specific user is impressed by an ad of "Maybelline" 5 times in July. In general, only activities happening in last three months are to be extracted. Click means whether we distinguish between click action from impression. The experimental results based on LR model (training data volume: 428484; testing data volume: 107121; positive and negative ratio is 1:2) show that if the features are calculated by month and click action is separated from impression, the AU C value will reach 0.8465 in testing phrase which is the best among all settings. Therefore, this feature engineering strategy will be applied in various model methodologies afterwards. trainDataSet: Different model performance
From the experiment results in Figure 3, we can see that the efect of the multi-layer perceptron is better than that of LR and FM, and adding the batch normalization layer and the scale layer can both improve the model performance and convergence speed of the model. Therefore, Scale-BN-MLP outperforms other models regarding AU C value during training phrase. Meanwhile, the convergence speed of Scale-BN-MLP (4 epochs) is the fastest one among all models, requiring early stopping to yield the optimal model in 0 5 15 20 0 5 15 20 practice. The result confirms the derivation in section 3.3. Figure 4 shows diferent learning rates for Scale-BN-MLP model in training and testing data set, the convergence speed performs well when learning rate equals to 0.0001(1e-4). ATV (Average Transaction Value), CPO (Cost Per Order), CPA (Cost Per Action) and Incremental ROI listed in this table. All indicators of our model perform far better than traditional demographic-based approaches. 5
In this paper, we showed an data application architect to utilize advertisement monitor data in audience expansion system for brand advertisers, compared to traditional ad serving based on demographics, the lookalike model in our application focuses on analysing user behaviour. Regarding the way of picking up the negative samples from unlabeled data, we compared four sampling techniques and the impact of diferent sampling ratios in order to figure out the best setting. Meanwhile, to overcome the sparsity and high dimension of feature space, we proposed Scale-MLP, a modified MLP by adding a scale layer, although the training AUC is lower than other traditional learning strategies, however, it gains performance improvement when generalizing the model to testing data while the eficiency of Scale-MLP is comparable to other approaches. Lastly we prove that the lookalike model outperforms traditional ad serving mechanisms in real business environment.
Several directions exist for future research. The rich information contained in the advertisement could be harnessed to investigate more sophisticated look-alike models. For example, we could incorporate advertising information including advertiser, brand and product in order to explore more detailed feature interactions. For diferent advertisers’ campaign, adaptive user feature representation also need to be taken into consideration. Meanwhile, CTR prediction task will be a challenging and interesting problem under the setting of growing diversity in targeting users and cross-media advertising platforms. CTR prediction results could be utilized for the purpose of omni-channel uniform budget allocation to efectively enhance ROI by matching brands/products with diferent media platforms.