# An Efficient Group-based Search Engine Marketing System for E-Commerce

Cheng Jie, Da Xu, Zigeng Wang, Lu Wang, Wei Shen  Walmart
LabsSunnyvaleCaliforniaUSA cheng.jie, da.xu, zigeng.wang0, lu.wang3,
<EMAIL_ADDRESS>
(2021)

###### Abstract.

With the increasing scale of the search-engine marketing, designing an
efficient bidding system is becoming paramount important for the success of
e-commerce company. The critical challenges faced by a modern industrial-level
bidding system include: 1. the catalog is huge and the relevant bidding
features are of high sparsity; 2. the large volume of bidding requests induces
significant computation burden to both the offline and online serving. In this
paper, we introduce the development and deployment process of the bidding
system for search engine marketing on Walmart.com, which successfully handles
hundreds of millions of biddings each day. We show and discuss the real-world
performances of state-of-the-art deep learning methods, and reveal how we find
their as the production-optimal solutions.

Clustering, Intention embedding, SEM bidding

††copyright: acmcopyright††journalyear: 2021††doi: 10.1145/1122445.1122456

##  1\. Introduction

In the modern era, online advertising has become a primary channel to deliver
promotional marketing messages to customers. Among the various forms of online
advertising, _search engine marketing_ (SEM) promotes business by showing and
recommending advertisements on search-result pages. In particular, _sponsored
search auctions_ contribute significantly to online advertising revenue as
search results often have more prominent exposure.

The business impact of SEM attracts increasing attention from both academia
and industry, specifically, the problems are appeal to the domains of
economics and computer science(Zhang et al., 2021). Over the years, a large
body of literature studies the constrained bidding optimization model, which
maximizes business objectives under the prefixed spending limit. For instance,
(Feldman et al., 2007) and (Borgs et al., 2007) establish SEM bidding models
for a single advertiser as constrained optimization problems in a
deterministic setting where the advertisers’ position, clicks, and the cost
associated with a bid are known a priori. In comparison, SEM bidding as an
optimization problem under the stochastic setting has been studied in
(Abhishek and Hosanagar, 2012). More recently, there is a emerging stream of
work which are dedicated to formulating the SEM bidding optimization as a
reinforcement learning based (Prashanth et al., 2016) dynamic pricing
problem(Zhu et al., 2021c), (Zhu et al., 2021a), (Zhu et al., 2021b) by
incorporating the sequential behavior of SEM ads (Shen et al., 2020).

While the seminal works have established rigorous mathematical properties for
SEM bidding, their optimization models are often too restrictive for practical
implementation. In real-world productions, the high volume of candidate ads is
a crucial factor that hinders the applicability of those methods. The two
challenges that stem from the industrial scale of ads are: (1). the feedback
data of most SEM ads are inevitably sparse due to the limited slots at search
engine platforms, preventing an accurate and effective estimation of their
performances; (2). complex bidding evaluations are prohibitive because the
volume of ads is enormous, and the frequency of bidding operations is very
high.

### SEM bidding through clustering ads intentions

In this paper, we introduce a generic bidding framework targeting the above
challenges. The SEM solution proposed in our paper is currently in production
for the multi-million-scale ads bidding for Walmart’s e-commerce business. As
we demonstrate in detail later in section 2, the solution of our system
comprises of two critical components:

  * •

a deep-learning-based multi-stage predictive algorithm for predicting the
performance of the advertisement through their multi-modality signals,
including the user feedback data and the contextual features of ads;

  * •

an optimization algorithm that assigns a bidding price for each ad, based on
its performance forecast for the desired business objectives.

Toward our goals, we first redesign a Transformer-based (Vaswani et al., 2017)
deep-learning language model to extract vector representations of the ads,
which captures the customer’s intentions when landing on the ads page. The
advantage is that we can now fully leverage the geometric characteristics of
the representations to aggregate ads’ information that would be sparse
otherwise (detailed in Section 3). The multi-stage prediction algorithm, which
then augments the grouping patterns of features via ads clustering, further
alleviates the sparsity issue of the features. In the meantime, the
clustering-based solution improves the scalability of the second-stage
optimization algorithm by significantly reducing the number of entities in the
downstream evaluation of the bids.

We thoroughly examine the performance of the proposed solutions via both
offline studies and online experiments in Section 5. As expected, the
clustering step is essential for trading off the sparsity, accuracy, and
scalability.

The previous literature addresses the sparsity issue primarily by using the
ads’ “keywords” in addition to the feedback data (Hillard et al., 2010).
However, using word tokens as a categorical feature can pose severe problems
in building predictive models due to the high cardinality. Unlike (Hillard et
al., 2010), our approach constructs continuous vector representations of ads
and therefore avoids the tenuous work of dealing with massive word tokens. We
point out that the ideas of clustering SEM ads have also been proposed to
overcome the high computation demands (Chen et al., 2013; Zhu et al., 2020).
However, the clustering algorithms developed in the above work are based on
the distributions of SEM ads’ historical feedback data, thereby excluding
those with sparse historical features, which is problematic for modern SEM
applications.

##  2\. Background for SEM Bidding

We first introduce the underlying bidding model and system that powers
Walmart’s SEM business.

###  2.1. SEM bidding model with single objective

Suppose an advertiser wants to maximize its revenue under the budget
$\mathcal{B}$, we denote $\mathcal{K}$ as the set of ads which the advertiser
would like to bid on. The SEM bidding model can be formulated as the following
constrained optimization problem:

(1) $\displaystyle\max_{\\{b_{k}\\}}E[\sum_{k\in\mathcal{K}}R_{k}(b_{k})]$ (2)
$\displaystyle s.t.\sum_{k\in\mathcal{K}}E[C_{k}(b_{k})]\leq\mathcal{B}$

where $R_{k}$, $C_{k}$ denote the revenue and cost function of ad $k$ with
regard to the bid $b_{k}$.

Practically, the cardinality of $\mathcal{K}$ is huge given the large number
of items on list of the eCommerce merchandise’s website. The large volume of
ads raises two challenges: 1. It becomes impossible to accurately predict all
the revenue function $R_{k}(b_{k})$ and cost function $C_{k}(b_{k})$. 2.
Solving the KKT condition in 6 becomes intractable given the size of the
problem.

In order to address the practical challenges for solving the large scale
random optimization problem under constraint of 1, we proposed the following
approaches so that the magnitude of the optimization problem can be reduced
dramatically.

First, inspired by the previous literature((Mohammad Mahdian, 2009), (Chen et
al., 2013), (Lin et al., 2018)) and the observation that many SEM ads indeed
have very close customer intentions, we propose a bidding scheme where the bid
is determined on the level of ad groups instead of individual ad. To this end,
the bidding scheme will cluster the ads into groups based on their embedded
vectors of deep-learning customer intention model, and set up the optimization
model at the level of ad group. Through some notation changes, the SEM bidding
model on ad group level can be formulated as follows:

(3) $\displaystyle\max_{\\{b_{g}\\}}E[\sum_{g\in\mathcal{G}}R_{g}(b_{g})]$ (4)
$\displaystyle
s.t.\sum_{g\in\mathcal{G}}E\left[C_{g}(b_{g})\right]\leq\mathcal{B},$

where $\mathcal{G}$ stands for the set of ad groups determined through the
clustering step, and $b_{g}$ is the bidding value assigned to all the ads at
group $g$. Based on our practical work of ad embedding and clustering, the ad
group level bidding model usually only has $3\%-5\%$ scale of the individual
level bidding model. Section 4 will give a detailed discussion on the ads
embedding and clustering steps.

With the SEM bidding model set up on the level of ad group, finding an optimal
solution to the problem is still quite onerous given that the forms of
expected revenue $E(R_{g}(b_{g}))$ and cost functions $E(C_{g}(b_{g}))$ are
unknown. However, by adding some practically reasonable assumptions on the
expected revenue and cost functions, the optimal solution on 3 can be achieved
in a quite efficient approach. Before presenting the assumption used for
solving the problem 3, we introduce the expected click function on bid value
as $E[CLK(b)]$, and propose the following definitions of RPS(revenue per
spend) and RPC(revenue per click) below.

###### Definition 0.

The RPS, i.e, revenue per spend, is defined as the amount of revenue an ad is
bringing in on one unit of spend. Mathematically, for an ad group $g$, its
$RPS_{g}=\frac{E[R_{g}(b_{g})]}{E[C_{g}(b_{g})]}$.

###### Definition 0.

The $RPC$, i.e, revenue per click, is defined as the amount of revenue an ad
is bringing in on one click, for a given ad $g$, we denote its revenue per
click as $RPC_{g}$.

###### Assumption 1.

We assume that for a given ad group $g$, its revenue per click $RPC_{g}$ is
insensitive to the change of bid value $b_{g}$. Furthermore, we assume that
expected click is linear function on $b_{g}$, i.e.,
$E[CLK_{g}(b_{g})]=c_{g}b_{g}$.

###### Remark 1.

With most of search engine platforms now switching to first-price auction
model, the bid price $b_{g}$ now is essentially the cost of a click. As a
result, based on assumption 1, $E[C_{g}(b_{g})]=c_{g}b^{2}_{g}$ for any ad
group $g$.

Under the assumption 1 of expected revenue cost function, we can state and
prove the following theorem regarding the optimal condition of the SEM
optimization problem 1.

###### Theorem 3.

Under assumption 1, the optimal solution of the optimization problem 3 is
achieved when the RPS(revenue per investment) is equal for $\forall k$.

###### Proof.

The Lagrangian of 3 can be written as

(5)
$\displaystyle\mathcal{L}=E[\sum_{g\in\mathcal{G}}R_{g}(b_{g})]-\lambda\\{\mathcal{B}-\sum_{g\in\mathcal{G}}E\left[C_{g}(b_{g})\right]\\},$

The KKT condition of 3 is

(6) $\displaystyle\forall
g:\frac{d\mathcal{L}}{db_{g}}=\frac{d}{db_{g}}E[\sum_{g\in\mathcal{G}}R_{g}(b_{g})]-\lambda\frac{d}{db_{g}}E[C_{g}(b_{g})]=0,\lambda>=0$
(7) $\displaystyle\mathcal{B}-\sum_{g\in\mathcal{G}}E[C_{g}(b_{g})]>=0$

The KKT condition of 6 implies that an optimal solution exists when the
following quotient

(8)
$\displaystyle\frac{d}{db_{g}}E\left[\sum_{g\in\mathcal{G}}R_{g}(b_{g})\right]/\frac{d}{db_{g}}E\left[C_{g}(b_{g})\right]$

takes the same value across $\forall g$. Under assumption 1, we have

(9) $\displaystyle E[R_{g}(b_{g})]=E[CLK(b_{g})]\cdot
RPC_{g}=c_{g}b_{g}RPC_{g}$ (10) $\displaystyle
E[C_{g}(b_{g})]=E[CLK(b_{g})]\cdot b_{g}=c_{g}b^{2}_{g}$

(11)
$\displaystyle\frac{d}{db_{g}}E\left[\sum_{g\in\mathcal{G}}R_{g}(b_{g})\right]/\frac{d}{db_{g}}E\left[C_{g}(b_{g})\right]=\frac{RPC_{g}}{2b_{g}}$

Notice that under assumption 1, its revenue per spend
$RPS_{g}=\frac{E(R_{g}(b_{g}))}{E(C_{g}(b_{g}))}=\frac{RPC_{g}}{b_{g}}$.
Hence, the KKT condition 11 is equivalent to that $RPS_{g}$ are equal across
$\forall g$. ∎

Addition to the conclusion of theorem 3, recall that assumption 1 claims that
$RPC_{g}$ are steady against $b_{g}$. Henceforth, the key step in optimizing 3
is predicting the revenue per click value for each ad group $g$.

###### Remark 2.

Note that the classical singular-ad bidding algorithm can be easily recovered
by replacing the ad group $g$ with the single ad.

###### Remark 3.

There exists scenarios that the business goal on SEM bidding system is
pursuing a balanced optimal condition targeted at more than one objectives. In
those cases, optimization function 3 becomes a weighted sum of multiple
expectations of different objectives. Similar assumptions and approaches as
Assum 1 and thm 3 can be applied to solve such optimization problem, which are
skipped in this paper to reduce redundancy.

Figure 1. Overview of the infrastructure for providing SEM ads’ bids by our
approach.

###  2.2. SEM bidding system

The results in the previous section suggest that the critical tasks for
determining the bids of SEM ads is to accurately predict the revenue per click
for each ad group $g$. In the sequel, we propose a design of the SEM ads
bidding system illustrated in Fig 1. In Figure 1, the first task for obtaining
the $RPC$ predictions is clustering the pool of SEM ads into ad groups. It
consists of two steps: 1. building a representation learning model that
encodes SEM ads into embeddings; 2. clustering SEM ads into ad groups. After
creating the SEM ad groups, the system will aggregate the features for ads
within each ad group, and then train a predictive model to accurately forecast
the $RPC_{g}$ for each ad group. We plug the $RPC_{g}$ back to the
optimization problem and obtain the final bidding $b_{g}$ for each
$g\in\mathcal{G}$ as $b_{g}=RPC_{g}/RPS_{g}$, where $RPS_{g}$ is known in
advance.

##  3\. Embedding and Clustering of SEM Ads

The ad group level bidding model 3 requires that each ad cluster needs to
represent an unique and exclusive customer purchase intention. Otherwise, if
customer intentions of two ad groups overlap, the change of bid on one group
might impact the impressions and conversions of another group, violating the
bidding model assumption that each ad group behaves independently. To this
end, we devise two steps in order to segment the SEM ads into mutually
exclusive ad clusters in terms of customer intention: First, We build an
customer intention representation model which can assign a vector
representation of every ad. Second, based on the vector representations of
each ad, we design a multi-stage clustering method in order to cluster large
amount of ads into small to mid-sized ad groups.

###  3.1. Customer intention embedding model

In this section, we walk through the key component of the customer intention
embedding model. Customer intention of an SEM ad is defined as the integrated
purchase intention of the set of search queries leading to clicks of the ad’s
web page on search engine. For example, an ad has drawn clicks of customers
after searching queries like “apple phone 8 case” or “iphone 9 case” has
customer intention be case covers for various versions of iphone. If two ads
share a large portion of clicked search queries, their customer intentions
should be close to each other by definition. Therefore, customer intention
model is designed to reflect the co-click relationships among the SEM ads.

Interactive metric. We propose a measure named as interactive metric(IM) in
order to calibrate the extent of similarity between customer intentions of two
SEM ads. Formally speaking, given two SEM ads A1 and A2, we first find the
numbers of clicks of the two ads on their co-clicked queries and denote them
as $CLK_{(A1coA2)}$ and $CLK_{(A2coA1)}$. With the numbers of total historical
clicks of the two ads $CLK_{A1}$ and $CLK_{A2}$, the IM value between A1 and
A2 is defined as

(12) $\displaystyle
IM_{A1,A2}=\sqrt{\frac{CLK_{(A1coA2)}*CLK_{(A2coA1)}}{CLK_{A1}*CLK_{A2}}},$

Fig 2 provide a real-world example to further demonstrate how interactive
factor of two SEM ads is calculated. In fig 2, Ad1 and Ad2 have share search
queries “walmart chairs” and “Chairs Walmart”, along with corresponding 192
and 158 clicks on the shared queries. Moreover, the total number of historical
clicks for Ad1 and 2 are 192 and 172 respectively, leading to the IM value
between the two ads be $\sqrt{(192*158)/(192*172)}=0.958$.

Contextual features of SEM ad. When a search query appears, the search engine
will try to match it with the SEM ads according to the content of their
landing pages. In light of that, we select the ads’ website’s text content as
the main feature for the customer intention model, since the content should be
a critical factor in customers’ decision making. The text feature of an SEM ad
is a combination of titles and descriptions of products contained in the ad’s
website. For the SEM ads with more than one product, we choose the three top
products to constrain the length of the input feature. Once the features are
extracted, they are processed and converted through the standard tokenization
and padding procedures described in (Devlin et al., 2019).

Transformer-based customer intention representation model. Recently, the
attention-based encode-decode structure transformer has become the status quo
architecture for natural language processing tasks (Vaswani et al., 2017).
Motivated by the structure of the bidirectional transformer from (Devlin et
al., 2019), we built a transformer-based deep learning(Li et al., 2021) model
for extracting the customer intention from the text features of SEM ads. As we
show in Fig 3, for a given ad $A$ and its tokenized feature $T_{A}$, the model
will consecutively go through an initial embedding layer, $3$ transformer
layers, a dense pooling layer, and two feedforward layers before generating
the final $512$-dimension _normalized_ output vector.

Training data. The data we use for training the representation learning model
is the search_term_report from search engine, which provides the historical
statistics of interactions (e.g. clicks, impressions) between SEM ads and
their relevant search queries. Specifically, for each SEM ad, we will extract
historical click numbers between the ad and each search query that leads to
the clicks. Together with interactive metric $I$ defined at 12, we create a
data-set $\mathcal{D}$ containing all the tuples of SEM ads having co-clicked
queries together with their interactive metric. In addition to the above
positive instances, we need negative instances to cover larger support of the
distribution. For that purpose, we sample a certain number of ad tuples
without co-clicked queries and append the tuples onto the data-set
$\mathcal{D}$ by assigning them with an interactive metric value of $-1$. For
the best practice, the ratio between positive tuples and negative tuples
should approximately equal to the average positive interactive metric in the
feedback data.

Figure 2. Interactive metric: an example

Model training. Let $f_{\theta}(\cdot)$ denote a customer intention model with
parameter vector $\theta$. Given an ad tuple $(A_{i},A_{j})$ along with their
interactive metric $I_{ij}$, we define the loss function as

(13) $\displaystyle-
I_{ij}\log\sigma\big{(}f_{\theta}(T_{A_{i}})^{T}f_{\theta}(T_{A_{j}})\big{)},$

where $\sigma(\cdot)$ is the sigmoid function. The inner product of
$f_{\theta}(T_{A_{i}})^{T}f_{\theta}(T_{A_{j}})$ captures the cosine
similarity between the embeddings of $(A_{i},A_{j})$, given that output
vectors of the model $f_{\theta}(\cdot)$ are normalized. The structure of the
model, together with the procedure for calculating the loss function, are
presented in Figure 3. The optimization problem for finding the optimal
$\theta$ is now given by:

(14) $\displaystyle\theta^{\star}=\mathop{\rm
arg\,min}_{\theta\in\Theta}\sum_{(A_{i},A_{j})\in
DT}-I_{ij}\log\sigma(f_{\theta}(A_{i})^{T}f_{\theta}(A_{j})),$

The objective (14) indicates that the larger the interactive metric between
two ads, the more impact this ad instance will carry when determining model
parameter $\theta$. Including the negative instances will allow the model to
further separate ads that lack a shared customer intention. Moreover, using
negative samples can avoid over-fitting and the corner case where all SEM ads
having a similar embedding. We use the ADAM(Kingma and Ba, 2015) optimizer, a
variant of stochastic optimization (Jie et al., 2018; Han et al., 2021; Jie,
2018) for training (14).

Figure 3. SEM ads customer intention embedding model

###  3.2. Multi-stage SEM ads clustering algorithm

In what follows, we discuss clustering with ads embedding. Due to the high
volume of ads in modern SEM, it is impractical to apply the clustering
algorithms that require computing all the pair-wise distances. Here, we
present a multi-stage method that leverages the SEM ads’ taxonomy and
significantly reduces the computation demand.

SEM ads classification. The first step of the multi-stage clustering algorithm
is to classify each SEM ad into one of the _product types_ , which can be any
taxonomy that is labeled for the items: electronics, beverage, etc. Most
companies have the predefined taxonomy for each item, which should be actively
exploited. SEM ad with only one item can be directly concluded to its product
type, and serve as the training sample of the taxonomy classification model.
For SEM ads with more than one item, we train a feedforward neural network(Du
et al., 2020) to predict each ads’ product type, which takes the embedding of
the SEM ad as input.

Clustering within each product type. Following the classification, we apply
the ”bottom-up” Agglomerative clustering using embedding vectors as features
to create mutually exclusive ad groups for the SEM ads within each product
type. Naturally, the cosine distance is employed as the _linkage metric_ , and
it also allows us to determine the threshold based on which the final clusters
are formed. We point out that the first classification step significantly
reduces the computation complexity compared with directly clustering all the
ads.

##  4\. Predicting RPC for SEM ads

In the next step, we build a machine learning model for each ads cluster to
predict the key quantity of $RPC_{g}$, i.e. the revenue per click, whose role
was illustrated in Section 2.2.

Features. The features we use for predicting $RPC$ can be categorized into
three classes: 1. the historical feedback statistics such as clicks and
conversions; 2. the activity metric for the ad’s landing pages such as bounce
rate; 3. contextual features of the ad, such as aggregating the ads embedding
for each ad group.

Model selection. There are varieties of machine learning models(Jarrow et al.,
2021; Zhu, 2020) for predicting $RPC$. The most basic prediction model is
linear regression, and its apparent advantages are interpret-ability and
computational efficiency. However, linear regression model usually suffers
from low performance especially on the SEM ad groups features with complex
structures. Besides linear regression model, we also tried more complex
alternatives such as boosted regression tree(Friedman, 2001; Zhao et al.,
2018) and neural network. It turned out that when applied on our tabular of
features and responses($RPC$), neural network usually doesn’t attain as high
accuracy as boosted regression tree, according to our cross-validation
performance. Moreover, with recent developments of highly efficient gradient
boosting tree package such as _XGboost_ and _LightGBM_ , training an accurate
gradient boosting tree algorithm is manageable on the scale of our SEM ads’
features data. Tree explainers such as feature importance and SHAP value also
assist us in understanding the impact of each feature in predicting $RPC$,
although not as straightforward as linear regression model. As a result,
taking all factors(accuracy, interpret-ability, robustness etc) altogether
into consideration, we finally select _Gradient Boosting Tree_ as our $RPC$
prediction model $r$. In the next section, we will compare the prediction
performances among linear regression, gradient boosting tree and neural
network.

Model training We choose the clicks-weighted square error as the loss function
for model training because ad groups with higher clicks often have more impact
on the business. Formally, by denoting the parameter of the model by
$\eta\in\mathcal{H}$ and the total clicks of ad group by $C_{g}$, the
objective function is given by:

(15) $\displaystyle\eta^{\star}=\mathop{\rm
arg\,min}_{\eta\in\mathcal{H}}\frac{\sum_{g\in\mathcal{G}}C_{g}(r_{\eta}(X_{g})-RPC_{g})^{2}}{\sum_{g\in\mathcal{G}}C_{g}},$

where $r_{\eta}$ is the RPC predicitive model.

##  5\. Experiments and Analysis

We conducted both offline and online experiments to answer the following
questions:

Q1: Can ads clustering improve the RPC prediction accuracy by addressing the
spareness of feedback data?

Q2: Does the proposed two-step framework improve the business performance?

### Offline experiment: prediction accuracy comparison

The offline experiment is designed to test whether the proposed clustering
methods address the sparseness issue and improve RPC prediction accuracy. To
this end, we select a set of ads with a total number of $\sim$20 million, and
compare the accuracy of RPC predictions of 1. directly applying RPC prediction
on each SEM ads (the baseline singular-ad-based algorithm); 2. clustering SEM
ads before predicting RPC for each ad cluster (our cluster-based bidding
algorithm). For fair comparison, we evaluate the performance metric based on
each ad and set the predicted RPC of each ad equivalent to the predicted RPC
of its belonging ad cluster when using the second approach. According to the
operation protocol of Walmart, we predict the weekly RPC as described in
Section 4. For the proposed approach, we apply the methods introduced in
Section 3 to cluster SEM ads into ad groups, and aggregate the ad features
within each ad group. The summary statistics for the ad groups and the
original SEM ads are displayed in Table 1.

Table 1. SEM ads vs ad groups: Data-set overview

| SEM ads | SEM ad groups
---|---|---
Dataset sample size | 19.6 M | 1.8M
Missing feature (proportion) | 91.6$\%$ | 54.4$\%$
Non-empty response ratio | 6.7 $\%$ | 36.4 $\%$
Relative response RPC variance | 100$\%$ | 55$\%$

In table 1, the proportion of feature missingness is calculated based on the
non-contextual features, and due to Walmart’s privacy policy, the variances of
the RPC response variable are presented as percentage proportions to the
largest among the two datasets. Table 1 manifest the two benefits of ads
clustering: 1. the feature sparseness is dramatically improved as exemplified
by the reduced missing feature proportion, 2. the reduced variance of the
response variable indicates that the clustering algorithm tends to produce a
more robust output for the downstream $RPG$ modeling.

We experimented with three machine learning models for predicting the weekly
RPC: _linear regression_ (LR) model, _TabNet_ and _gradient boosting
regression tree_ (GBRT). We split the dataset into training, validation, and
test by $80\%-10\%-10\%$, where the test dataset is used to report the
predictive accuracy of the trained models. In addition to the click-weighted
MSE (WMSE) mentioned at section 4, we also include the click-weighted MAE
(WMAE) as performance metric. The performances of the trained models are
displayed on table 2. Figure 4 presents an example of the gradient boosting
trees when applied to the baseline and our approach, under their best hyper-
parameter combinations. Due to the privacy policy, we provide the accuracy
metric with respect to the baseline model, which is Linear regression(LR) on
the singular-ad-based algorithm. The model training, including hyper-parameter
tuning is conducted on a Linux system with 64 core 2.80GHz CPUs and 800 GB
memory.

Figure 4. Relative WMSE of the baseline and our approach when using GBRT. Table 2. The RPC prediction accuracy (relative to LR on singular-ad setting), and the offline model training time. Predictive model | WMSE(Relative to LR Singular) | WMAE(Relative to LR Singular) | Training time
---|---|---|---
Singular based | Cluster based | Singular based | Cluster based | Singular based | Cluster based
LR(reference point) | 100$\%$ | 92$\%$ | 100$\%$ | 86$\%$ | 8m | 2m
TabNet | 30$\%$ | 27$\%$ | 35$\%$ | 31$\%$ | 15h | 2.5h
Gradient boosting | 25$\%$ | 21$\%$ | 29$\%$ | 23$\%$ | 16h | 2h

The results from Table 2 and Figure 4 suggest that RPC prediction via ad
clustering consistently achieves better performances compared with the
singular ad prediction. Further, the computational time for training RPC at
the cluster level is considerably less than the singular-ad level.

### Online experiment: business efficiency comparison

We design the online AB testing experiment to see whether the clustering-based
bidding improves business performance, which is mainly reflected by the
revenue per spend (RPS). We use the stratified sampling to select 200,000 SEM
ads across different product types as our target ads pool, and compare the RPS
of clustering-based bidding algorithm and traditional singular-ad-based
bidding algorithm when applied on the selected SEM ads.

Here, we leverage the Draft $\&$ Experiment platform from Google
Adwords111https://ads.google.com, where the max capacity for a campaign is
200,000. to create a pair of control and test campaigns that host the 200k SEM
ads. The singular-based and clustering-based bidding algorithms are applied to
the control and test campaign, respectively. We set a common RPS goal for the
two algorithms to evaluate bids.

Table 3. Online AB testing results. Test | Metric(Relative to control) | Control | Test
---|---|---|---
AA period | Spend | 100$\%$ | 101$\%$
| RPS | 100$\%$ | 99$\%$
AB period | Spend | 100$\%$ | 102$\%$
| RPS | 100$\%$ | 109$\%$

The experiment session consists of one week of AA test, and one following week
of AB test. During the AB period, we keep the spending between control and
test campaigns close through some proportional bids adjustments.

The online testing results are presented in table 3, where we present metrics
relative to the control campaign. The test campaign’s RPS on the AB period
exemplifies that clustering-based bidding is able to achieve improved
performance compared with the singular-ad-based-bidding.

##  6\. Conclusion

This paper introduces a two-step clustering-based SEM bidding system that
integrates modern representation learning with the Transformer language model.
We describe the detailed development infrastructure that may bring insights to
both practitioners and researchers in this domain. The offline and online
experiments show that the proposed system compares favorably to the
alternatives in terms of accuracy and training efficiency. Our successful
deployment for Walmart e-commerce further reveals combining clustering with
modern representation learning as a scalable solution for industrial bidding
systems.

## References

  * (1)
  * Abhishek and Hosanagar (2012) V. Abhishek and K. Hosanagar. 2012.  Optimal bidding in multi-item multi-slot sponsored search auctions. In _EC ’12_.
  * Borgs et al. (2007) C. Borgs, J. Chayes, Nicole Immorlica, K. Jain, O. Etesami, and Mohammad Mahdian. 2007\.  Dynamics of bid optimization in online advertisement auctions. In _WWW ’07_.
  * Chen et al. (2013) Y. Chen, W. Liu, J. Yi, Anton Schwaighofer, and T. W. Yan. 2013.  Query clustering based on bid landscape for sponsored search auction optimization.  _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ (2013).
  * Devlin et al. (2019) J. Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _NAACL-HLT_.
  * Du et al. (2020) Tianming Du, Yanci Zhang, Xiaotong Shi, and Shuang Chen. 2020\.  Multiple Slice k-space Deep Learning for Magnetic Resonance Imaging Reconstruction.  _2020 42nd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC)_ (2020), 1564–1567.
  * Feldman et al. (2007) J. Feldman, S. Muthukrishnan, Martin Pál, and C. Stein. 2007.  Budget optimization in search-based advertising auctions.  _ArXiv_ abs/cs/0612052 (2007).
  * Friedman (2001) J. Friedman. 2001\.  Greedy function approximation: A gradient boosting machine.  _Annals of Statistics_ 29 (2001), 1189–1232.
  * Han et al. (2021) Yuzhen Han, Majid Mazouchi, S. Nageshrao, and H. Modares. 2021.  A Convex Programming Approach to Data-Driven Risk-Averse Reinforcement Learning.  _ArXiv_ abs/2103.14606 (2021).
  * Hillard et al. (2010) D. Hillard, Eren Manavoglu, H. Raghavan, C. Leggetter, E. Cantú-Paz, and R. Iyer. 2010\.  The sum of its parts: reducing sparsity in click estimation with query segments.  _Information Retrieval_ 14 (2010), 315–336.
  * Jarrow et al. (2021) Robert A Jarrow, Rinald Murataj, Martin T Wells, and Liao Zhu. 2021.  The Low-volatility Anomaly and the Adaptive Multi-Factor Model.  _arXiv preprint arXiv:2003.08302_ (2021).
  * Jie (2018) Cheng Jie. 2018\.  Decision Making Under Uncertainty: New Models and Applications.
  * Jie et al. (2018) Cheng Jie, A. PrashanthL., M. Fu, S. Marcus, and Csaba Szepesvari. 2018.  Stochastic Optimization in a Cumulative Prospect Theory Framework.  _IEEE Trans. Automat. Control_ 63 (2018), 2867–2882.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization.  _CoRR_ abs/1412.6980 (2015).
  * Li et al. (2021) Yifei Li, Kuangyan Song, Yiming Sun, and Liao Zhu. 2021\.  FrequentNet: A Novel Interpretable Deep Learning Model for Image Classification.  _Available at SSRN: https://ssrn.com/abstract=3895462_ (2021).
  * Lin et al. (2018) Kun Lin, Cheng Jie, and Steven I. Marcus. 2018.  Probabilistically distorted risk-sensitive infinite-horizon dynamic programming.  _Automatica_ 97 (2018), 1–6.  https://doi.org/10.1016/j.automatica.2018.07.028
  * Mohammad Mahdian (2009) Grant Wang Mohammad Mahdian. 2009\.  Clustering-Based Bidding languages for Sponsored Search.  _European Symposium on Algorithms_ (2009).
  * Prashanth et al. (2016) L.A. Prashanth, Cheng Jie, Michael Fu, Steve Marcus, and Csaba Szepesvári. 2016.  Cumulative Prospect Theory Meets Reinforcement Learning: Prediction and Control. In _Proceedings of The 33rd International Conference on Machine Learning_. 1406–1415.
  * Shen et al. (2020) W. Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Y. Hong, Z. Guo, Zongyao Ding, Pengjun Lu, and Pingzhong Tang. 2020.  Reinforcement Mechanism Design, with Applications to Dynamic Pricing in Sponsored Search Auctions.  _ArXiv_ abs/1711.10279 (2020).
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need.  _ArXiv_ abs/1706.03762 (2017).
  * Zhang et al. (2021) Yanci Zhang, Tianming Du, Yujie Sun, Lawrence Donohue, and Rui Dai. 2021.  Form 10-Q Itemization.  _ArXiv_ abs/2104.11783 (2021).
  * Zhao et al. (2018) Xinyan Zhao, Mengqi Zhan, and Cheng Jie. 2018.  Examining multiplicity and dynamics of publics’ crisis narratives with large-scale Twitter data.  _Public Relations Review_ 44, 4 (2018), 619–632.  https://doi.org/10.1016/j.pubrev.2018.07.004
  * Zhu (2020) Liao Zhu. 2020.  _The Adaptive Multi-Factor Model and the Financial Market_.  Ph.D. Dissertation. Cornell University.
  * Zhu et al. (2020) Liao Zhu, Sumanta Basu, Robert A. Jarrow, and Martin T. Wells. 2020\.  High-Dimensional Estimation, Basis Assets, and the Adaptive Multi-Factor Model.  _Quarterly Journal of Finance_ 10, 04 (2020), 2050017\.
  * Zhu et al. (2021a) Liao Zhu, Robert A. Jarrow, and Martin T. Wells. 2021a.  Time-Invariance Coefficients Tests with the Adaptive Multi-Factor Model.  _arXiv preprint arXiv:2011.04171_ (2021).
  * Zhu et al. (2021b) Liao Zhu, Ningning Sun, and Martin T. Wells. 2021b.  Clustering Structure of Microstructure Measures.  _arXiv preprint arXiv:2107.02283_ (2021).
  * Zhu et al. (2021c) Liao Zhu, Haoxuan Wu, and Martin T. Wells. 2021c.  A News-based Machine Learning Model for Adaptive Asset Pricing.  _arXiv preprint arXiv:2106.07103_ (2021).