# User Response Prediction in Online Advertising

Zhabiz Gharibshah<EMAIL_ADDRESS>Dept. of Computer & Elect. Eng. and
Computer Science, Florida Atlantic University777 Glades RoadBoca RatonFL33431
and  Xingquan Zhu<EMAIL_ADDRESS>Dept. of Computer & Elect. Eng. and Computer
Science, Florida Atlantic University777 Glades RoadBoca RatonFL33431

###### Abstract.

Abstract-Online advertising, as the vast market, has gained significant
attentions in various platforms ranging from search engines, third-party
websites, social media, and mobile apps. The prosperity of online campaigns is
a challenge in online marketing and is usually evaluated by user response
through different metrics, such as clicks on advertisement (ad) creatives,
subscriptions to products, purchases of items, or explicit user feedback
through online surveys. Recent years have witnessed a significant increase in
the number of studies using computational approaches, including machine
learning methods, for user response prediction. However, existing literature
mainly focuses on algorithmic-driven designs to solve specific challenges, and
no comprehensive review exists to answer many important questions. What are
the parties involved in the online digital advertising eco-systems? What type
of data are available for user response prediction? How to predict user
response in a reliable and/or transparent way? In this survey, we provide a
comprehensive review of user response prediction in online advertising and
related recommender applications. Our essential goal is to provide a thorough
understanding of online advertising platforms, stakeholders, data
availability, and typical ways of user response prediction. We propose a
taxonomy to categorize state-of-the-art user response prediction methods,
primarily focus on the current progress of machine learning methods used in
different online platforms. In addition, we also review applications of user
response prediction, benchmark datasets, and open-source codes in the field.

††copyright: acmlicensed††journal: CSUR††journalyear: 2021††journalvolume:
1††journalnumber: 1††article: 1††publicationmonth: 1††price: 15.00††doi:
10.1145/3446662††journal: CSUR††journalvolume: 37††journalnumber: 4††article:
111††publicationmonth: 8

##  1\. Introduction

Online advertising (Zhu et al., 2017a), as a multi-billion dollars business,
provides a common marketing experience when people are accessing to online
services using electronic devices, such as desktop computers, tablets,
smartphones etc. Using Internet as a means of advertising, different
stakeholders act in the background to provide and deliver advertisements to
users through numerous platforms, such as search engines, news sites, social
networks, where dedicated spots of areas are used to display advertisement
(ad) along with search results, posts, or page content.

Similar to the traditional media, such as printing magazines and newspapers
where specific spaces are assigned to be sold for ads, a portion of online
services and websites are filled with clickable components to display
marketing messages. Under such circumstances, the ads to be displayed to
audience (i.e., users) are either pre-sold (i.e., negotiated) by sellers
(publishers) to buyers (advertisers) or they are dynamically selected through
a real-time bidding (or auction) (Yuan et al., 2014; Wang et al., 2016). In
online advertising, advertisers are bidding an ad opportunity, but only the
winner has the chance to serve their ads to users (so only the winner needs to
pay to the publisher for the purchase of the auctioned ad opportunity). During
the whole process, the effectiveness of the online advertising is typically
evaluated through signals made by users towards the displayed ads. These
signals are typically considered as user responses starting with a click on
ads in web-pages or a tap on screen in mobile apps. Once displayed ads are
clicked by users, the payment/revenue is generated between advertisers and
publishers. As a result, for both advertisers and publishers, it is crucial to
design a user response based pricing model.

Predicting a click, as the first measurable user response, is an important
step for many digital advertising and recommendation systems to capture the
user propensity to following up actions, such as purchasing a product or
subscribing a service. Based on this observed feedback, these systems are
tailored for user preferences to decide about the order that ads should be
served to them. In the era of search engines and social websites, companies
like Google introduce paid search advertising (Rutz and Bucklin, 2011) via
user intents recognized through the query keywords. In social media marketing,
platforms like Facebook provide advertisers with user demographic information
from user-generated content for viral marketing (Chu, 2011). In conventional
advertising in TV or printed newspapers, monitoring the effectiveness of ads
is difficult. However, online advertising leverage performance metrics for
targeting ad audience, so stakeholders can immediately obtain ad advertising
feedback, through clicks, conversions, and other types of user response, to
adjust their budget, price for bidding etc. (Wang et al., 2016).

The essential goal of different types of advertising systems, either
traditional media based or modern online advertising based, is to find the
best matching between audience (users) and ads, given contextual features in
each platform. From computational perspective, this is equivalent to finding a
way to accurately predict positive or negative user responses to an ad, given
observed user data. It is shown that the accurate prediction of user response
metrics can directly determine the revenue for both publishers and advertisers
(Chapelle et al., 2014; Agarwal et al., 2010). The variation of the problem is
defined by the availability of context in different platforms. The context in
search engines are query generated by users. In display advertising, the
context is considered as websites visited by users, and in-app advertising the
context is the specific logical stage in mobile apps for marketing.

For years, industry and academia have developed numerous approaches to use
holistic data to predict positive response of users where the positive
response is typically defined in the form of the estimation of click-through
rate on ads or user interactions for purchasing a product, i.e. a conversion.
Such approaches vary from data hierarchy (Agarwal et al., 2010; Agarwal et
al., 2007; Oentaryo et al., 2014b; Lee et al., 2012), clustering (H. et al.,
2010; Regelson et al., 2006; Reps et al., 2014; Wang et al., 2011),
collaborative filtering (Menon et al., 2011; Liu et al., 2015a),
classification (Rendle, 2010; Dalessandro et al., 2014; Xu and Wu, 2020;
Blondel et al., 2016; Huang et al., 2019), to graph and network based analysis
(Wang et al., 2018a, 2019d).

As data are becoming rapidly available, machine learning based approaches have
been used in nearly all domains to solve different types of challenges for
knowledge discovery (Zhu and Davidson, 2007). For online advertising, this is
especially true. Since the very beginning, industry has been actively seeking
effective and efficient computational methods to tackle the data volumes and
real-time decision challenges. Many approaches, such as deep learning and
factorization machine based methods, demonstrate a great potential to
accurately estimate user responses (Juan et al., 2017; Guo et al., 2017), but
the data intensive nature and the real-time requirement have made the accurate
user response prediction for online advertising extremely challenging. Here,
we briefly summarize the major challenges as the following fourfold:

  * •

Scalability: In real-world advertising eco-system, the number of visited web-
pages is extremely large. Combining with factors like the number of unique
visiting users and the amount of ads, it results in a giant dataset for
analysing. In many studies (Chen et al., 2016) machine learning has been
applied to predict user response and boost the personalizing of digital
advertising. It is important to design solutions for large scale advertising
data (Chapelle et al., 2014; Pi et al., 2019; Wang et al., 2018; Ge et al.,
2018).

  * •

Response rarity: Statistics shows that the rate of click and conversion of all
types of ads is not more than 2 percent over all displaying ads. Therefore,
finding a way to overcome class imbalance issue and mitigate the adverse
effects on prediction results is a challenge for the prediction algorithms.

  * •

Data sparsity: This issue in online advertising and recommender systems stems
from two factors. First, majority of input data consist of categorical
features which need to use binary representation, resulting in high
dimensional vectors with very few non-zero values. Additionally, interactions
between users and items follow the power law distribution, meaning majority
users are interacting with a small number of items and products.

  * •

Cold start: This is the common challenge for new new ads, products, and
services, because no historical user information available is available to be
used for estimation.

Indeed, many solutions have been proposed, but primarily focus on new methods
for user response prediction. Several works propose to study current business
model and technologies evolved from traditional media buying (Yuan et al.,
2014; Chen et al., 2016), or review display advertising literature and new
directions (Choi et al., 2019). In (Yuan et al., 2014), the authors go over
the business model of real-time bidding by introducing keys actors in the
market for ad delivery. From economic perspective, (Choi et al., 2019)
outlines the eco-system of display ad market and non-guaranteed selling
channels provided to buy and sell ads in real-time. It reviews the disciplines
regarding the ad pricing decision made by different actors like advertisers
and publishers and other intermediary nodes. The study (Chen et al., 2016)
reviews the technologies provided for online and mobile advertising, including
pricing models implemented between advertisers and publishers, inherent
networking schemes by addressing the user privacy and malicious ad related
activities.

Unfortunately, all existing works, including the literature review, do not
provide a complete overview about types of user response and underlying
technical solutions in online advertising. Answers to many key questions
remain unclear for both industry and academia, especially for someone who just
steps into the online advertising field. What are the main advertising
platforms? What type of user response can be modeled/predicted using
computational approaches? What are the features and the source of features
useful for use response prediction? How to utilize features for use response
prediction? What are the main types of technical solutions for user response
prediction? Are there any benchmark and online resources (datasets/software)
available for evaluation purposes?

In this paper, we provide a comprehensive literature review of the latest
computational methods for user response prediction in online advertising, with
a focus on machine learning based approaches. To the best of knowledge this is
the first survey study which is focusing on computational approaches for user
response prediction. Our review covers different types of user response
prediction tasks ranging from click-through rate prediction to user post-click
experience evaluation. Our survey includes the description of the online
advertising eco-system, platforms, data sources, and early studies for user
response prediction. We also consider the most recent work in this context
which propose more advanced algorithmic designs and feature extraction
methods.

##  2\. Advertising Eco-System & User Response

In this section, we introduce key components and important concepts of online
advertising eco-system. For ease of understanding, we summarize key concepts
and their descriptions in Table A.1.

###  2.1. Online Advertising Eco-System

Online digital adverting heavily relies on real-time bidding (auction) (Yuan
et al., 2014) for advertisers to make decisions to display ads in online
portals. In this architecture, an ad exchange network connects sellers
(publishers) and buyers (advertisers), so they can negotiate to respond to ad
requests in real time. In order to participate in the ad bidding, publishers
and advertisers connect to the ad exchange network through SSP (Supply-Side
Platform)s and DSP (Demand-Side Platform)s, respectively, to cast auctions
(for SSP) and manage bids (for DSP), therefore ads are eventually delivered to
different media platforms, e.g. a third-party website, search engine result
page, or the web-page of social networks.

In Figure 1, we illustrate an online advertising eco-system. The workflow
starts with an event when a user, i.e. an audience, launches an URL request
from a publisher’s web page. The ad request for ad placements is sent to SSP
to trigger an ad auction call (i.e. an opportunity). If the requested web-page
contains available ad placement, the ad call will be submitted to Ad Exchange
Network, leading to negotiations with advertisers through DSP based on bidding
mechanism. The winning advertiser will insert ad script in the user requested
page, so the ad is eventually delivered to the user. In the case that the
displayed advertisement matches to the user preference, user response in the
form of click or further user engagements, like purchasing or subscription, is
generated.

The revenue of advertisers and publishers, in the online advertising, is based
on the user response such as clicks or conversions. Therefore, serving users
with ads best matching to their preference is of interests to both advertisers
and publishers. Under such circumstances, using context to find users’
preference plays an essential role for user response prediction. The
information from publisher websites is usually obtained from crawling the web-
pages to summarize the context. It is then complimented by online analysis of
cookie data and browsing history made by users. Such information allows system
to identify user interest and response regarding ad impression.

Figure 1. Advertising Eco-system. From left to right, a process is triggered
when users start to interact with online services through either visiting a
web-page, searching an item, or checking the social media in publisher
website. In the case that the web-page has web placement available, the
publisher sends ad request through SSP node to the Ad Exchange. The bid
request related to requested ads are forwarded from Ad Exchange to DSP nodes
which represent advertisers. After getting relevant user information, such as
user profile and their previous interaction, through DMPs, the auction is set
up to gather bid among DSPs. The bidder with the highest bid wins and its ad
script is forwarded to the publisher to be embedded in the page requested by
users.

###  2.2. User Response Types

In web applications like web search engines, display advertising,
recommendation systems, or e-commerce platforms, a user response to
advertisements starts with a simple click on the ad or a touch on the screen
in mobile app. This action is considered as an implicit positive user response
which will direct users to a landing web-page. If ad content matches to user
preferences, it encourages users to follow up promoted messages by generating
the next clicks which can end up with desired activity such as a purchase. In
online advertising the initial click or final purchase actions over displayed
advertisements are considered as the critical measures to evaluate the
performance of user response predictive models. Online advertising systems are
generally integrated with recommendation systems in e-commerce platforms to
provide users with ranked items based on explicit user’s rating and implicit
feedback. These feedback can be measured using different metrics to show the
performance of the advertising systems. In the following subsections, we
define prevalent metrics in this domain.

####  2.2.1. Click-Through Rate

Click-through rate (CTR) value is of the most important metrics to evaluate
the quality of ads and the performance of campaign ads. Two elements to
calculate the click-through rate values are clicks and impressions. The click-
through rate is typically defined as the number of click events over
impressions or the percentage of served advertisement ending up with user
click events.

(1) $\displaystyle CTR=\dfrac{\\#~{}of~{}Clicks}{\\#~{}of~{}Impressions}$

The number of impressions are perceived as the number of times an ad or a
promoted product is served to the users’ device which is engaged to an active
online platform, where the publisher can be the website of search engine, a
social media, or a third-party website. A click event is an indicator of user
engagement, which can be a mouse click on ad creatives on a desktop system or
touching them on mobile devices. The definition of click event is extended in
different applications like the number of downloads (Liu et al., 2020a), or in
the social media context as positive and negative actions like reply,
commenting, sharing, dismiss, etc. (Li et al., 2015). Common issue that
frequently exists regarding this metric is data class imbalance problem where
the number of clicks compared to the number of impressions is very few. Some
studies (Zheng et al., 2010; Kumar et al., 2018) suggest that relying on this
metric to evaluate the performance of e-commerce search results can be noisy
and generate misleading outcomes.

####  2.2.2. Conversion Rate

In order to evaluate user experience and activities after the click, metrics
are introduced to evaluate ad campaigns following cost-per-conversion business
model. The desired actions for advertisers like purchases, subscription of
service, registrations, and installation of a software, are considered
examples of conversion events.

Conversion rate is simply defined as the proportion of users who visited ad
creative in online portal and chose to take any above mentioned actions after
opening the landing website.

(2) $\displaystyle CVR=\dfrac{\\#~{}of~{}Conversions}{\\#~{}of~{}Impressions}$

A conversion is generally considered as a user response following a temporal
order of events starting with the page visit, ad display, click, to the
conversion. In the case that the sequence of conversion, click, and visit of
ads are all available, the prediction of conversion rate is defined as a post-
click conversion prediction. The essential goal of the problem is to estimate
the probability of a conversion event given clicks and the context (Ma et al.,
2018; Wen et al., 2019).

####  2.2.3. User Engagement

Recommender systems have been commonly used in different application platforms
range from social networks and news feed services to e-commerce portal and
entertainment data stream services. The common problem in these system is the
overload of information that users are confronted with the high volume of
items being overwhelming to browse. The priority of these systems is to
attract more users by replying their requests with a relevant list of items
matched with their preferences. So, the common objective is to recommend a
small set of items which includes promoted ones to get immediate implicit user
feedback (e.g. CTR) while keeps users activating. User engagement objectives
have been studies differently in prior research. There are some studies which
model active users by following churn-rate and dwell time analysis. Recent
studies have modeled user engagement using multi-objective optimizations. So
two recommending and online advertising are optimized together to satisfy user
experience in the long-term (Zhao et al., 2020b; Zhao et al., 2020).

With the advent of smartphones and the increase in their popularity among
users, there is a surge of interest in developing softwares operating on this
platform. As a result, a new online advertising, called in-app advertising,
emerges where specific spots on screen before completing a transition in the
app are designed for commercial ads. In this context, some studies proposed to
provide personalized ads (Xu et al., 2020; Kumar et al., 2018) which are
evaluated by studying different users activity patterns to model users’
engagement. Because smartphone platforms are personalized with respect to
individual users, user response can be extended to the user engagement concept
with the general questions to learn the factors which can (1) retain user
being active to use an online service, like streaming providers and (2) also
help gain revenue through directing people to take a desirable action with
regard to ads. Therefore, several researches (Liu et al., 2019; Rutz et al.,
2019) investigate features leading to user engagement with regard to mobile
apps, and a recent work (Barbaro et al., 2019) proposes to study factors which
are resulting in users being disengaged from mobile apps through hierarchical
clustering models.

In video streaming platformss like YouTube, video ads have become a modern
effective way of conveying commercial messages via telling a story to users.
In this context, video completion rate value is a metric designed to evaluate
the effectiveness of video advertisements and user engagements111It is defined
as the percentage that videos are watched to the end. The more time the video
ad is watched by users, the higher the chance it may influence users to take
follow-up actions.. As it is shown in (Krishnan and Sitaraman, 2013) the
content, position and length of video ad along with the length and the
provider of host videos in addition to user connection information (geography
and connection devices) are key factors to impact video completion rates and
evaluating the effectiveness of video ads.

In the context of e-commerce system, use engagement is generally evaluated by
ranking metrics used in information retrieval systems. The performance of
ranking in the produced ordered lists is established by considering a samples
of users who have positive interaction with items. Generally, there is a
chance that items preferred by users are missing in the list. Mean average
precision at rank K ($MAP@K$), mean average recall at rank K ($MAR@K$) and
Normalized Discounted Cumulative Gain at rank K, are the frequent metrics
which give more details about the ranking performance. The $MAP@K$ assesses
how much system can incorporate relevant items in the list. The second one
$MAR@K$ checks how well model can create a list from all available items being
relevant to user preferences. Due to the fact that the relevancy of items to
user preferences are not the same, $NDCG@K$ consider the performance to put
the more relevant items before the others in the recommended list $S$. It
gives more significance to hit rates happened at higher ranks of the
recommended list. According to Eq. (4), for each item in the recommended list,
$rel_{s,r}=1$ represents a case that the item $s$ ranked at $r$ is matched
with the ground-truth otherwise it would be $rel_{s,r}=0$. A log factor is
used to assign a penalty with regard to position of items in the list.

(3) $\displaystyle
MAP@K=\dfrac{\\#~{}of~{}recommended~{}items~{}being~{}relevant}{\\#~{}of~{}recommended~{}items}$
$\displaystyle
MAR@K=\dfrac{\\#~{}of~{}recommended~{}items~{}being~{}relevant}{\\#~{}of~{}relevant~{}items}$
(4) $\displaystyle NDCG@K=\dfrac{\sum\nolimits_{s\in
S}\sum\limits_{r=1}^{K}\dfrac{rel_{s,r}}{\log_{2}(r+1)}}{\\#~{}of~{}recommended~{}items}$

####  2.2.4. Explicit user feedback

In contrast to implicit user feedback, explicit rating score information
allows users to express their interests or opinions through online methods
like surveys. Compared to implicit user feedback, this information are scarce
since they require users to provide additional input with regard to items via
surveys and online forms. In addition, they may come with bias in user’s
opinions. Implicit feedback are frequently analyzed through models for
classification tasks where explicit user responses are adopted for regression
tasks such as rating prediction so that user rating score with regard to new
items are estimated by the system.

Table 1 summarizes characteristics and challenges of different user response
types.

Table 1. The characteristics of different user response types. Metric |  Abundance |  Accuracy | User feedback |  Illustration of user preferences |  Description
---|---|---|---|---|---
Implicit |  Explicit |
Click-Through Rate |  High |  Low |  ✓ |  |  Positive |  Often not the final goal
Conversion Rate |  Low |  High |  ✓ |  |  Positive |  Needs a domain specific definition
User Engagement |  High |  High |  ✓ |  |  Positive |  Assumes a direct trend between retention & engagement Takes short-term or sequential user behavior and intents
User rating scores |  Low |  High |  |  ✓ |  Pos. and Neg. |  Sparse data

##  3\. Features for User Response Prediction

User response prediction plays an essential role for online advertising and
recommender systems (Lee et al., 2012), where the prediction is typically
defined as the probability of users making a positive response on promoted
item in a marketplace, ad, or news article in online platforms (Menon et al.,
2011; Shioji and Arai, 2017; Wang et al., 2016). The performance-based
advertising is the paradigm mainly followed in online advertising systems,
where the predicted probability is not only used as an indicator to present
user preferences, it is also involved in bidding strategies to determine the
revenue of advertiser and publishers (Richardson et al., 2007).

Figure 2 shows the workflow of typical user response prediction models
consisting of two main stages. The first stage is related to data collected
from different data sources (Users, Advertisers and Publishers) in online
advertising systems. After the pre-processing and labeling steps, data samples
are described with series of features (fields) along with label (class) values
which are normally specified as binary user response value such as 1 for
click, conversion, purchasing, etc. and 0 otherwise. For recommendation
systems, the output in Figure 2 is an ordered list of promoted/recommended
products. For the prediction task, it will output probability of users making
an interaction (e.g. a click) on items in the list. Like typical machine
learning problems, the input data should be described through feature vectors
to capture the class correlation, meaning that features need to be
discriminative for the prediction task. Therefore, during the second
(learning) phase, features are extracted using different approaches, such as
(1) using data fields to represent users, pages, etc. and create sparse
features; or (2) using embedding based approaches to create dense features.

Figure 2. The schema of user response prediction workflow. Embedding layer is
the common paradigm to deal with high dimensional binary representation in
user response prediction. They can either be set by pre-defined values or be
trained as internal parameters in end-to-end models like deep learning
methods. The output can be considered as two types of user responses a) a
scalar value of predicted score for an interaction between given user $u_{i}$
and item $I_{j}$ b) a ranked list of regular and promoted items ordered by
predicted user response scores.

###  3.1. Type of Features

In order to accurately predict user response, it is important to train models
using discriminative features. In the following subsection, we will discuss
features studied by various methods.

####  3.1.1. Multi-field categorical features

The typical input data fed into online advertising systems are generally
formed as multi-field categorical values. Contrary to continuous features
which are generally found when dealing with images or audios, the input data
contains an array of categorical fields including Gender, City, Age, Id,
$\cdots$ and device type and ad category, $\cdots$, to describe users and ads
or the other related objects in the system. An event representing the user
interaction with online advertising includes features from different actors
like users, publishers, advertisers and the context in online advertising
systems. A representative list of categorical features corresponding to user
profile and behavior, advertisement and publisher’s web-page is provided in
Table 2. The one-hot encoding is the conventional approach to deal with this
type of data (He et al., 2014). As shown in Figure 3, each field is shown as a
binary vector. The dimension of vector is determined by the number of unique
values which are taken in the field in which one entry is set as one while the
remaining as zero. In this example, fields like gender has the length of 2 and
the length of weekday is 7. The simple way to represent features is the
concatenation of these vectors which typically creates a high dimensional
sparse binary vector. In the mathematical way, considering the input data with
$n$ feature fields and $x_{i}$ is the hot-encoded vector of the field feature
$i$ with dimension of $K_{i}$ where $\sum_{j=1}^{n}|x_{i}|=k$. In the case
$k=1$, we have one-hot-encoded vectors while $k>1$ refers to multi-hot-
encoding (Gharibshah et al., 2020; Zhou et al., 2018b; Niu et al., 2018) that
feature field is represented by more than one value entries. To handle the
high dimensionality issue, the common approach for many classification based
methods is employing the embedding step to generate condensed embedding
vectors. These vectors can be concatenated like
$x=[x_{1},...,x_{i},...,x_{n}]$ to create input layer of different user
response predicting models.

Figure 3. The characteristics of multi-field categorical features as the input to user response prediction models. The binary representation of multi-categorical features is created using one-hot-encoding Object |  Features
---|---
User |  Id, location(Area, city, country), IP, Network Spec, Browser cookie, Gender, Age , Date
Advertiser |  Ad id, Ad group Id, Campaign Id, Ad Category, Bid, Ad Size, Creative, Creative Type, Advertiser Network
Publisher |  Publisher(Id), Site, Section, Ad Placement, Content Category, Publisher Network, Device type, Page Referrer
Context |  Serve time, Response Time
Table 2. Representative categorical features corresponding to the main online
advertising objects

####  3.1.2. Textual features

In search advertising, ads are displayed in the search result pages,
incorporating textual data such as headline, relevant keywords and the body to
highlight the details of promoted products. Many research proposes to treat
click-through rate prediction task as the similarity learning between users’
query keywords and keywords of ads using their proposed text based similarity.
For example, keywords in the title and body of advertisements (Baqapuri and
Trofimov, 2014; Effendi and Ali, 2017) and keywords in user queries are
considered as two sources of data to extract textual features in many designed
models (Edizel et al., 2017; Wang et al., 2018b; Gligorijevic et al., 2018).
Relying only on ad textual content and user query at character- and word-
level, a deep CTR prediction model (Edizel et al., 2017) collects data from
textual letters of query along with the title, the description, and the ad
URL. They are organized to feed into system as a one-hot-encoded matrix.

####  3.1.3. Visual features

E-commerce platforms, which are available through web portals and mobile apps,
are hosts of many categorical ads and items. Each item is generally described
by texts and images, acting as visual features to attract users’ attention.
Categorical features are generally used for model user behavior history.
However, the data sparsity issue in categorical data encourages to consider
intrinsic visual information in images for the development of further methods
(Ge et al., 2018; Chen et al., 2016). There is also an increasing interest to
develop video ads for digital streaming platforms in which user responses
generally happen by clicking on the image section (Shi et al., 2020). Very
recently, user facial information along with user behavior history is proposed
to use for modeling user purchase interest. Analyzing this type data can
provide an estimation of some user profile information such as gender, age and
ethnicity which in turn draw inferences about user background and status and
their manner for purchasing(Liu et al., 2020).

###  3.2. Organization of Features

Earlier studies to analyze user responses in online advertising mainly use one
type of multi-field, visual or textual features for model designing, mainly
because of their transparency and easy to interpret. Advanced models are later
studied to extract complex features for better prediction accuracy. In the
following section, we will go over a couple of models which take advantage of
two important layout of features such as sequential and hybrid features to
improve the performance of predictive models.

####  3.2.1. Temporal and sequential (user behavior) features

Users activities are commonly recorded as data logs available in many online
data provider services. Considering the sequence of user actions w.r.t.
different types of ads are valuable features for analyzing user response
prediction (Zhou et al., 2019a; Qiu et al., 2020; Yong et al., 2020). The
majority of proposed methods are categorized into recurrent neural network
based and network based models (detailed in Sections 4.3 and 4.4.2). Some
studies in literature showed that the history of previous visited pages,
clicked ads (Xu et al., 2020), not-clicked ads (Ouyang et al., 2019a) sorted
by time in system can be leveraged to model sequential dependency between
input features. Several studies have shown the importance of these features to
enhance the performance of various user response prediction tasks (Zhou et
al., 2018b; Feng et al., 2019; Zhou et al., 2019a; Gligorijevic et al., 2019).

In (Zhou et al., 2018b) user behavior features are represented as a list of
visiting events of ads, each of which are described by categorical features
about goods, shop, and page categories of past user-defined time points. Each
time point is described using multi-hot-encoding.

Sessions are also used to represent user’s behavior history (Feng et al.,
2019). Separated by occurring time, user activities are considered homogeneous
in very short time slots within sessions but different with regard to other
sessions. User interaction patterns over time are evolving in short-term and
long-term trends. A common scenario is to deal with virtually short-term
sequences of user behaviors when user profile (e.g. ID) of active users is not
accessible via log-in to system. So, the task of predicting user responses is
defined to extract relevant patterns based on limited actions of anonymous
users. In this case, the complete user interaction histories are also
organized into sessions (Qiu et al., 2020; Zhang et al., 2020). The long-term
user interaction can also be studied to create user profile behavior. It can
not only provide indication of user intent change over time which can be used
to improve the predication user responses, the popularity pattern regarding
products can also be identified to remind users about a product according
their previous interactions. In (Gligorijevic et al., 2019) authors consider a
sequence of user activity events before and after the ad click and
corresponding passed time-slot to investigate the potential user conversion
intents. They analyzed the effect of elapsed time as a feature for conversion
rate prediction and using targeting and retargeting222A cookie based
advertising which tracks users clicking or visiting ad in a website who have
not taken further actions against promoted products. Using this paradigm
advertising systems remind users their previous interest about a promoted
product. paradigm for different users in online advertising systems.

####  3.2.2. Hybrid Features

Combining different types of features are also studied to enhance user
response prediction. Some studies use textual features along with multi-field
categorical features to improve the performance of recommendation systems in
e-commerce platforms (Niu et al., 2018) and the sponsored search marketing
(Covington et al., 2016). Some research consider the compounds of categorical
features and image data (Ge et al., 2018; Chen et al., 2016) and the
combination of categorical features with video data (Shi et al., 2020) to
improve predictions. The combination of different features in modeling lead to
various compound embedding layer for input data to generate a condensed
feature representation, with pooling being employed to reduce parameters and
cope with over-fitting. Max and sum pooling are also studied as the
aggregation mechanism in some studies (Covington et al., 2016; Ge et al.,
2018). The concatenation of feature embedding vectors is a straightforward
approach commonly used in many studies (Qu et al., 2016; Shan et al., 2016;
Zhang et al., 2016b; Liu et al., 2019). Recently, an adaptive approach to
combine most relevant features from different feature types is employed based
on attentive mechanism (Ge et al., 2018; Zhou et al., 2018b).

##  4\. User Response Prediction Frameworks

For years, user response prediction, in online advertising, has been
continuously evolving. Early approaches usually reply on hand crafted features
to dissect data into different segments, where each segment contains users
with similar response. Therefore, the click-through rate values or conversion
rate values estimated on each segment can be used to estimate future (new)
users’ CTR values. Following similar approaches, clustering or collaborative
filter based approaches are also proposed to recommend ads to users. In the
context of recommendation systems, the ordered list of items including
promoted products are proposed to users by predicting how likely the list
contains items matching to user preferences. The evaluation of these systems
are examined with different ranking and regression metrics (Detailed in
Section 2.2). Typical types of recommender systems have analyzed past user
interactions to detect a connection between users and products either through
studying users with same tastes or similar items visited by different users.
Recently, machine learning, especially deep learning, based approaches, are
becoming increasingly popular for user response prediction, mainly because
these approaches can simultaneously accommodate a large number of features,
and learn to create new features, for accurate user response prediction.

In Table 3, we propose a taxonomy of user response prediction, which includes
hierarchical based methods, collaborative filtering based approaches,
supervised, semi-supervised and unsupervised learning studies. In the case
that labeled data are available, supervised learning algorithms leverage the
label in the definition of the loss function in their learning procedure.
Unsupervised learning rely on unlabeled data for the loss function
optimization. Semi-supervised models are between supervised and unsupervised
models where their objective functions are optimized considering both data
with and without labels. The supervised methods can be further categorized
into basic predictive models and ensembles ones whereas semi-supervised and
unsupervised category consists of network-based and clustering based methods.
The last category in the taxonomy includes stream-based methods. Following
subsections will discuss and review representative methods in each category.

Category |  Publication
---|---
Data Hierarchy Based |  (Agarwal et al., 2010; Agarwal et al., 2007; Oentaryo et al., 2014b; Lee et al., 2012; Kota and Agarwal, 2011; Chao Huang and Chawla, 2019)
Collaborative-Filtering Based | Hierarchy Based |  (Menon et al., 2011; Liu et al., 2015a)
| Network Based |  (Koren, 2008; Wang et al., 2018a, 2019d, 2019a; He et al., 2020)
| Hybrid Methods |  (He et al., 2017; Wu et al., 2019; Chen et al., 2017)
Supervised Learning |  Predictive Models |  Logistic Regression |  (Lee et al., 2012; Kumar and Salo, 2016; Dalessandro et al., 2015; He et al., 2014; Chapelle et al., 2014; Vasile et al., 2017; Ren et al., 2016; Zhang et al., 2016c; Aryafar et al., 2017; Zhu et al., 2017b)
|  |  Factorization Machines |  (Rendle, 2010; Oentaryo et al., 2014b; Pan et al., 2016; Juan et al., 2017; Pan et al., 2018; Punjabi and Bhatt, 2018; Liu et al., 2017; Huang et al., 2019; Zhang et al., 2019; Chen et al., 2019; Oentaryo et al., 2014b; Zhang et al., 2016b; Qu et al., 2018)
|  |  Deep Learning Methods |  (Covington et al., 2016; Shan et al., 2016; Zhou et al., 2018b; Ouyang et al., 2019a; Song et al., 2019; Xu et al., 2020; Ge et al., 2018; Yang et al., 2019; Zhou et al., 2019b, a; Feng et al., 2019; Pi et al., 2019; Chao Huang and Chawla, 2019; Bigon et al., 2019; Liu et al., 2019; Liu et al., 2015b; Edizel et al., 2017; Chen et al., 2016; Gligorijevic et al., 2018; Niu et al., 2018; Chao Huang and Chawla, 2019; He et al., 2017)
|  |  Hybrid Methods |  (Guo et al., 2017; Qu et al., 2016; Cheng et al., 2016)
|  Ensemble Methods |  Cascading |  (Zhang et al., 2016b)
|  |  Stacking |  (Aryafar et al., 2017)
|  |  Boosting |  (Livne et al., 2020)
|  |  Mixed |  (Wen et al., 2018)
Un-supervised & Semi-supervised Learning |  Network Based |  Network Embedding: (Node Embedding, GNN Based methods, User Intention Network Modeling) |  (Wang et al., 2018; Li et al., 2019, 2019; Qiu et al., 2020; Yong et al., 2020; Ying et al., 2018)
|  |  Knowledge Network Based: (Node Embedding, Meta-path Based methods, GNN Based methods) |  (Wang et al., 2018b; Fan et al., 2019; Wang et al., 2019c; Qu et al., 2019; Wang et al., 2019a; He et al., 2020; Wang et al., 2019b; Zhang et al., 2019a)
|  Clustering Based |  |  (H. et al., 2010; Regelson et al., 2006)
Stream-Based Data |  (Diaz-Aviles et al., 2012; Li et al., 2015; Ktena et al., 2019; Zhou et al., 2016; Lalmas et al., 2015; Barbieri et al., 2016; Ruihong et al., 2020)
Table 3. A taxonomy of user response prediction in online advertising, along
with representative publications

###  4.1. Data Hierarchy Based Approaches

Using unstructured input features, data sparsity and cold start are common
issues in online advertising and recommender systems. Data hierarchy based
methods refer to approaches that organize data in a hierarchical format (Liu
et al., 2017). The motivation is to build a tree structured hierarchy, using
some selected features, such that each leaf nodes represents a user groups
sharing similar response. This hierarchy provides valuable information to show
correlation between user responses at different level of granularity, which
alleviates the adverse effect of limited historical information about users.

####  4.1.1. Data Hierarchy

As the first attempt to cope with data sparsity and limited historical data in
online advertising, hierarchical structures of publisher web pages, ads and
end-users are commonly used to address correlation between input features
(Agarwal et al., 2010; Agarwal et al., 2007; Oentaryo et al., 2014b; Lee et
al., 2012; Liu et al., 2017). In this case, users, web-pages and ads are
grouped based on different factors, such as demographic or geographic
information about users, domain and content of web pages and the context and
campaign of ads. An example of the data hierarchy is shown in Figure 4. From
advertiser perspective, the hierarchy can be created by classifying ads based
on campaign, content type, and advertisers. For publishers, web-pages can be
grouped using simply URL path or the content category. Users can also be
organized as hierarchical data using third party information like user
geographic, ad and web-page visit history etc. Studies show that data
hierarchy for ads, pages, and users provides useful knowledge to handle data
rarity in click-through prediction (Lee et al., 2012). Partitioning input
space using tree structure represents similarity between connected nodes with
respect to user responses in local areas (Oentaryo et al., 2014b; Agarwal et
al., 2007). In industry, these data hierarchies are created and maintained by
domain experts.

(a) Advertiser hierarchy

(b) Publisher hierarchy

Figure 4. The sample taxonomy representing a hierarchical structure for
Advertiser and Publisher data where a) demonstrates grouping ad creatives
through multi-level joint points when they are of same campaigns and are
designed for the same devices by an individual advertiser b) indicates the
publisher hierarchy from ad placement in web-pages, the running devices and
grouping of publishers

####  4.1.2. Representative Hierarchy Based CTR Prediction Frameworks

Input features of online advertising systems consist of various sparse
categorical features, which contribute to generate rare user responses such as
clicks or conversions. To address these issues, many methods propose to create
a hierarchical structure from input features to estimate user response from
previous similar available samples (Lee et al., 2012; Agarwal et al., 2007).

##### Problem Definition

For ads being served to users multiple times, the baseline problem to predict
user response is defined as: given a pair of web-page $j$ and ad $k$, the
probability of response, like a mouse click, is calculated through the
probability formula $P_{jk}=Pr(Click|Impression;j,k)$. This probability, a.k.a
Click-through rate value (CTR), can be computed via binomial maximum
likelihood estimation (MLE) where $V_{jk}$ indicates the number of times ad
$k$ is displayed on the web page $j$, and $C_{jk}$ is the indicator of click
number, respectively (Wang et al., 2011; Richardson et al., 2007). For the
case $V_{jk}=0$ or equals to a small value, the value of MLE estimate for CTR
values becomes unreliable. Therefore, in literature, different methods are
proposed to exploit hierarchical information for smoothing out the MLE
predictions.

For instance, authors in (Agarwal et al., 2007) proposed to utilize two
hierarchical structures between input features related to web-pages and ads to
improve the prediction of user click responses in online advertising. In this
study, they tackled a form of sparsity issue in the input data with a few
number of available clicks and impressions. In order to reduce the variance
made by the sparse clicks and/or impressions, a sampling approach is used to
alleviate the rarity issue via negative sampling of majority class, i.e. web-
pages without a click response. To control the effect of the bias made by
sampling, a two-step method is used to predict the click-through rate. In the
first step, a maximum entropy model is optimized based on an iterative
proportional fitting method to estimate the actual number of impressions at
all defined levels in the hierarchical structure. A tree-shaped Markov model
is then used to predict the click-through rate value in the whole levels of
the hierarchy using correlations between sibling nodes.

Further, a log-linear model (LMMH) (Agarwal et al., 2010) is introduced to
improve user response prediction by exploiting correlations between sibling
nodes at different data hierarchy levels. To increase the scalability of model
to large dataset, a spike and slab variable selection method is proposed to
control number of parameters in the regression model. This method deals with
rare response rates by pooling data along a directed acyclic graph (DAG)
obtained through a cross-product of multiple hierarchies.

Another study (Kota and Agarwal, 2011) advances the LMMH method using higher
order feature interactions by fitting local LMMH models to relatively
homogeneous subsets of the data. Given a relatively homogeneous partitioning
of the feature space, several local LMMH models are fitted to data subsets on
different nodes of a decision tree. To address over-fitting issue in the
model, models are coupled with a temporal smoothing procedure designed based
on a fast Kalman filter style algorithm.

Last but not least, a study (Lee et al., 2012) investigates the data hierarchy
for three objects of users, advertisers and publishers to deal with the data
sparsity and class imbalance problem for conversion prediction. Taking
conversion event as Bernoulli random variable with two possible values of
conversion and no conversion, a binomial distribution is used to model the
conversion given a triple of user $u_{i}$ and ad ${a_{k}}$ and web-page
$p_{j}$. To address the data sparsity, they propose to capture the correlation
in the conversion output using clustering of similar users with regard to
conversion rate values, grouping advertisements from the same campaigns and
web-pages with same category types. The conversion estimation is calculated at
different levels of the hierarchy made from the cross product of levels in
three hierarchical structures of users, publishers and advertisers via the
maximum likelihood estimation as follows.

(5) $\displaystyle P(Y=1|u\in C_{u_{i}},p\in C_{p_{j}},a\in
C_{a_{k}})=\begin{cases}\dfrac{C_{ijk}}{I_{ijk}}&\text{if $I_{ijk}>0$}\\\
unknown&\text{otherwise}\\\ \end{cases}$

where $C_{u_{i}}$ is the cluster that $u_{i}$ belongs to. $C_{p_{j}}$ and
$C_{a_{k}}$ indicate the cluster of web-page $p_{j}$ and ad $a_{k}$,
respectively. The final estimation of the conversion rate value is then
modelled using logistic regression from the linear combination of MLE
estimators at different hierarchical levels.

###  4.2. Collaborative Filtering Based Approaches

Collaborative filtering is an effective approach to predict online user
interests. The general idea is to analyze previous behaviors of users to
predict possible future user interests or to generate suggestions that may
match to the preferences of the new similar users.

##### Problem Definition

For collaborative filtering methods, the input is an incomplete sparse matrix
$X\in R^{m\times n}$ of user-item preferences, which suffers from the data
sparsity, i.e. some $X_{ij}$ entries are missing. The goal is to fill in
missing entries with predicted scores. The state of the art in collaborative
filtering is matrix factorization (Hu et al., 2008; Menon et al., 2011) which
is based on an idea that the matrix of users’ preferences w.r.t items $X$ can
be factorized into two low-rank matrices of Users $\alpha$ and Items $\beta$.
It is modelled as $X\simeq\alpha^{T}\beta$, where $\alpha\in R^{k\times m}$
and $\beta\in R^{k\times n}$ and $k$ is the dimension of latent features.
Conceptually, each $\alpha_{i}$ represents a user, and each $\beta_{j}$
represents an item. The simplest factorization model is to solve the following
optimization where latent feature vector of users and items are controlled
with user-defined regularization function $\sigma$ in different studies to
prevent the model from the over-fitting issue (Menon et al., 2011; Koren,
2008).

(6)
$\displaystyle\underset{\alpha,\beta}{\min}\dfrac{1}{|O|}\sum_{(i,j)\in{O}}(X_{ij}-\alpha_{i}^{T}\beta_{j})^{2}+\sigma(\alpha,\beta)$

In general, collaborative filtering is based on the past interactions between
users and products. It can be seen as the implicit feedback like click or
conversion event on products or explicit feedback like product ratings.
Interactions between web-pages and ad banners can be shown as a matrix of web-
page-by-ad feedback score (click-through or conversion rate rate or product
rate values). The correlation between web-pages and ads is captured to
calculate predicted scores for missing entries which can be intuitively
related to the user response prediction task. The major studies in this
category take advantage of collaborative filtering methods along with side
information such as the user and item neighborhood models (Koren, 2008), the
data hierarchies (Menon et al., 2011; Liu et al., 2015a) and knowledge graph
data (Wang et al., 2018a, 2019d). Hybrid models are used to tackle scenarios
with data sparsity and cold start problems to improve the prediction
performance. It is conventional that initial models resorted to apply matrix
factorization and inner-product operator on latent factor vectors to establish
connection between users and items. Recently, neural architecture (He et al.,
2017; Wu et al., 2019) and attention mechanism (Chen et al., 2017) are
proposed as the alternative to learn higher order interactions on data. The
user responses analyzed to evaluate the performance of models in the studied
papers range from explicit product rate scores (Koren, 2008; Wu et al., 2019)
to implicit user feedback like CVR scores in (Wang et al., 2018a, 2019d; Menon
et al., 2011) and recommended ordered list (He et al., 2017; Chen et al.,
2017).

One of initial works in the collaborative filtering domains, developed based
on latent factor models like singular value decomposition, is known as
SVD++(Koren, 2008). For a personalized recommendation system task, the authors
improve the accuracy of system by addressing both explicit and implicit user
feedback in a hybrid model. To do so, additional terms are added to optimize
the loss function (6) which is organized in three levels. In the first level,
bias terms, in form of the addition of average of rating value of all items,
the bias in average rating made by user $\alpha_{i}$, and the corresponding
bias for item $\beta_{i}$ to control the discrepancy between actual values and
predicted values in the loss function, are added. In the second level, a loss
function is defined by adding a term to include implicit available feedback.
They refer to all items that user had an interaction before. The implicit
feedback here are considered from a series of browsing, purchasing and search
user history in e-commerce systems. In the last level, a neighborhood model
which addresses the effect of bias in average rating value made by neighbor
users and items is added. Combining these terms together, the parameters of
proposed model are updated using gradient descent optimization. It led to an
improvement calculated for product rating prediction and providing top-$k$
personalized recommendation tasks.

In an extended matrix factorization design (Menon et al., 2011), hierarchical
information of web-page and ads are integrated as additional side information
into latent features of collaborative filtering to tackle data sparsity and
cold start problem. Explicit features from ads and web-pages in side
information are linearly augmented to implicit features using a log-linear
latent features model and user-interest propagation framework (FIP) to enrich
input features. As a hybrid method, it includes hierarchical structural
information into their factorization model using three learning ideas such as
hierarchical regularization, agglomerate fitting and residual fitting.

In online advertising, interactions are generally made between multiple
entities including users, items, and ads. Tensor factorization, as an extended
version of matrix factorization, can use the similarity between different
types to predict potential interaction between pair of instances. To address
the compound similarity of entities with regard to a possible interaction, a
Hierarchical Interaction Representation model (Liu et al., 2015a) is proposed
to provide a joint representation to model mutual actions between different
entities. Three dimensional tensor multiplication is used for modeling
characteristics of pair of entities.

Recently, some studies (Wang et al., 2018a, 2019d) propose to organize user
and ad as heterogeneous information graph to improve collaborative filtering.
Authors in (Wang et al., 2018a) suggests an end-to-end learning method to
incorporate side information from knowledge graph (KG) into an item-based
collaborative filtering approach for click-through rate prediction. They
propose an extended knowledge graph embedding method which starts building an
initial user preference sets in the knowledge graph that are originally set up
from previous user click activities. An iterative propagation of user
preferences along edges over the knowledge graph is used to create $k$ Ripple
sets to model potential user liking versus items. Learning an embedding vector
for each ripple set, the embedding vector of user response versus items is
calculated from the sum of corresponding embedding vector of ripple sets. The
click-through rate score of user $u$ versus item $v$ is modeled using dot
product embedding vectors of $u$ and $v$ each of which are trained based on a
Bayesian framework and gradient descent learning.

###  4.3. Supervised Learning Based Approaches

In this section, we review supervised learning based methods which formulate
the prediction of user response rates as binary or multi-class classification
task in online advertising platforms. These methods can be categorized into
two categories including the basic and ensemble predictive methods. Following
the structure in Figure 2, input features are generally considered as multiple
feature fields gathered from different sources like user, advertiser and
publisher. The input layer in classification methods are considered as a
numeric vector from concatenation of all fields.

(7) $\displaystyle x=\left[x_{1}||x_{2}||\cdots||x_{n}\right]$

where $n$ is the number of features and $x_{i}$ is the representation of field
$i$. For categorical data, feature value is encoded into a numeric vector
through directly one-hot-encoding. Fields with continuous values are first
discretized to be encoded to binary vectors by one-hot encoding.

##### Logistic Regression based methods

Logistic regression is one of the first attempts to train models to predict
user response from input categorical features. As it is shown in Figure 6(a),
this method uses linear combination of coefficient values and input sparse
binary feature vector to predict the binary output value. Given the input
dataset with $m$ instances of ($x_{i}$,$y_{i}$) where $x_{i}\in\\{0,1\\}^{n}$
is an $n$-dimensional feature vector and $y_{i}$ is the label to represent the
user response as (click:1, no-click:0). The predicted probability of $x_{i}$
belonging to class 1 is modeled by Sigmoid function as:

(8) $\displaystyle Pr(y=1|x_{i},w)=\dfrac{1}{1+\exp(-w^{T}x_{i})}$

The model coefficient $w\in\mathbb{R}^{d}$ is achieved by minimizing the
negative log likelihood as follows:

(9)
$\displaystyle\min_{w}\dfrac{\lambda}{2}\left\lVert{w}\right\rVert^{2}+\sum_{j=1}^{m}\log(1+\exp(-y_{i}\phi_{LR}(w,x_{i})))$

where $\phi_{LR}(w,x)=w_{0}+w^{T}x=w_{0}+\sum_{j=1}^{n}w_{i}x_{i}$ is the
linear combination of coefficients along with bias value $w_{0}$ and features
that $w_{0}\in\mathbb{R}$ and $w\in\mathbb{R}^{n}$. As it is shown in
literature Eq. (9) is convex and differentiable, so gradient based
optimization techniques can be applied.

##### Challenges and extended methods

Some studies (Chapelle et al., 2014) indicate that the implementation of
logistic regression methods is possible with high scalability through Maximum
Entropy approach and a generalized mutual information and feature hashing as
the regularization. However, modeling linear interaction between feature
values only address the effect of features with class label separately.
Therefore, it cannot always generate an acceptable performance in user
response prediction task which gets impacted by some issues such as class
imbalance originated from low click and conversion rates, the cold start issue
for new instances, long cycle of user purchase responses, and non-linear
interaction between input features. Authors in (Dalessandro et al., 2015) use
historical information of brand website visit as the proxy to model predictor
using logistic regression model. A study (Lee et al., 2012) suggests to create
hierarchy structure from previous user performances that is captured from
grouping ad campaigns and publisher pages and users. A logistic regression
model is used for linear combination of local MLE estimators.

Employing the side information using transfer learning has also been studied
in some work (Dalessandro et al., 2014; Yang et al., 2016). In (Dalessandro et
al., 2014) a transfer learning method is developed to combine data from a
model on small set of conversion data to improve post-view conversion rate for
large number of ad campaigns where click event is not necessarily required. In
(Yang et al., 2016) a transfer learning approach was developed to design a
natural learning processing method to capture transferable information of
related campaigns. It is motivated by the fact that the similar searched
content and visited web-pages by users can be indicators of their future
purchase interest. In another work, a practical result from applying logistic
regression for big data in social media platform demonstrated that the
weakness of linear modeling could be reduced by cascading with decision tree
models to implement non-linearity of input categorical data (He et al., 2014).

##### Factorization Based Methods

In order to consider non-linear interaction between features values,
factorization machines (FM) combine support vector machine method with
factorization models (Rendle, 2010). This allows the method to carry out
parameter estimation under the data sparsity using linear complexity. This can
be done by modeling the feature value interactions through a product of two
latent vectors $v_{i},v_{j}\in\mathbb{R}^{k}$. The dimensionality of latent
vectors is the hyper-parameter that defines the number of latent factors.

(10)
$\displaystyle\phi_{FM}=w_{0}+w^{T}x+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle{v_{i},v_{j}}\rangle{x_{i}x_{j}}$

(a) FM

(b) FFM

Figure 5. a) FM Model: The architecture of Factorization Machines method as
the extension of logistic regression by using dot-product $\otimes$ operators
fed by dense embedding vectors of input sparse features. b) Field-aware
factorization machines (FFM) model: The structure is similar to FM model. The
difference is that the sparse interaction between each feature value in the
current field $i$ with another one in the other field (ex. $i+1$) is modeled
by a separated embedding vector. Each feature field $i$ is represented by an
embedding matrix.

Figure 5(a) shows the architecture of factorization machines as the
combination of two terms including the feature interaction
$\langle{v_{i},v_{j}}\rangle$ and linear information $w_{0}+w^{T}x$ to model
click responses. The idea is that embedding vectors of features can be trained
well to preserve feature interaction through dot product operation if there
are enough occurrences that the features appear in the dataset.

##### Extended Factorization Machines models

Since factorization machines have a closed form equation that can be
calculated in linear time, it is shown that the parameters of models can be
trained using gradient based methods like stochastic gradient descend
optimization (SGD) (Rendle, 2010). Some studies showed that FTRL-Proximal
algorithm with $L_{1}$ regularization and per-coordinate learning rate, which
was successfully used for logistic regression based models (McMahan et al.,
2013), can also outperform SGD algorithm for extended factorization machine
models (Ta, 2015). However, this method suffers from some limitations.

One of the downsides of factorization machines modeling is that for multi-
field categorical data, feature values may come from different field feature
that may change the interaction between feature values. But most methods deal
with feature values uniformly. Therefore, Field-aware Factorization Machine
(FFM) (Juan et al., 2017) is proposed to discriminate the interaction between
various feature values of different fields. To this end, it suggests to add
one dimension to model parameters to allocate more than one embedding vector
to features since pair of features incorporate different feature types
information. This changes the modelling of feature interaction as the
following equation:

(11)
$\displaystyle\phi_{FFM}=w_{0}+w^{T}x+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle{v_{i,F(j)},v_{j,F(i)}}\rangle{x_{i}x_{j}}$

where $F(i)$ is an indicator of field name that feature corresponding to the
first entry of feature interaction while $F(j)$ is an indicator of field name
that feature is related to the second entry of interaction. Lack of
consideration into the importance of features and the limitation of inner-
product to model feature interaction are two issues in baseline methods of
factorization methods have been studied in many other works as follows.

The baseline factorization machine methods usually consider all combinations
of feature values in different fields with the same weight. But interactions
between features often vary and do not have equal values. So there is a chance
that using less important features in the training set, the noise is actually
learnt by the model which can have the adverse effect on the performance. This
motivates studies to impose weights on the interactions (Pan et al., 2018;
Xiao et al., 2017; Huang et al., 2019) To this end, authors in (Pan et al.,
2018) proposed a weighted version of field-aware factorization machine (FwFM)
that can use the memory efficiently for model parameters. It adds more
information through a weight matrix to consider the difference in the strength
of interaction between feature values originating from different pair of
fields. In (Xiao et al., 2017) follows a deep learning study in which the
importance of feature interaction were studied using an attention network
through a layer to learn corresponding weights. A study (Oentaryo et al.,
2014b) centered the work on a different aspect to use a cost sensitive
approach to address the cold-start issue and using the data hierarchy for the
data sparsity. They designed an importance-aware loss function to assign the
more importance weights and penalty values for ad samples which are shown more
to users but their user response predicted wrongly. Authors in (Punjabi and
Bhatt, 2018) also proposed a robust factorization machines method considering
user response prediction as a classification problem under the noise. The
uncertainty within input samples is modeled by an optimization through an
uncertainty vector with each dimension corresponding to independent noise
value.

Aside from the above mentioned points, the capability of factorization
machines to address data sparsity issue using inner-product operation can be
limited when confronting high dimensional data. Modeling only 2nd-order
feature interactions is not expressive enough for implicit higher order
feature conjunctions. This stimulated motivations to propose high order
variants of factorization machines method (Xu and Wu, 2020; Blondel et al.,
2016; Huang et al., 2019). In (Huang et al., 2019) authors extended the
feature interaction modeling in factorization machines using a bilinear
interaction method which combines inner product and Hadamard product together
to generate a fine-grained feature interactions. Very recently, (Xu and Wu,
2020) proposed a score function to replace inner-product operation between
embedding vectors of input features. They discussed that using Lorentz
distance, the triangle inequality principle between two points with regard to
the origin point is not always consistent. They suggested to use the sign of
triangle inequality to learn feature interactions through a proposed Lorentz
embedding layer. To this end, a novel triangle pooling layer is proposed to
substitute for the typical factorization machines structure.

##### Hybrid Approaches

Hybrid methods follow a classification technique that involves a number of
heterogeneous methods each of which acts complementary to each other. Each
method solves a different task and the classification decision is reached by
the one method at the end. The distinction between ensemble methods and hybrid
methods is that the former models are trained separately to generate the
predictions at the inference time. On the contrary, hybrid models follow a
joint training which optimizes all parameters simultaneously. This idea makes
a motivation for attempts at developing more complex machine learning methods
which are able to model a non-linear user interaction in online advertising
systems. Regarding the user response prediction, the primitive predictors
based on the logistic regression or factorization machines have weakness to
capture limited range of feature interaction by addressing linear relations or
dot product interactions between input features. Their performance is suffered
from the data sparsity, class imbalance problem and cold-start problems. To
address these issues,hybrid architecture of classifiers has been proposed in
many studies. The categorization of hybrid models are presented as follows:

##### Logistic regression based methods

One of the first studies to improve logistic regression performance was the
addition of decision trees to the structure of model (He et al., 2014). In
order to address the data sparsity in input data consisting of multi-field
categorical data, they use a cascade of decision trees structured by boosting
ensemble paradigm to provide a non-linear transformation of categorical
features. Following a gradient boosting machine, the boosted decision trees
generate a feature vector with the user-defined dimension $k$ that is passed
to logistic regression classifier for prediction.

The success of deep learning methods in capturing higher order interactions
motivates research to include deep neural networks to improve the Logistic
Regression in different studies (Cheng et al., 2016; Shan et al., 2016).

Although the logistic regression models have shown a good scalability and
interpretability to handle the massive data in the online advertising industry
(Chapelle et al., 2014), the generalization of model for predicting new
samples is limited and highly dependant to whether high quality features can
be obtained through feature engineering. Using the polynomial regression
applied, the logistic regression model can only capture low-order feature
interactions. This drives authors in (Cheng et al., 2016) to approach a hybrid
structure of logistic regression and deep neural networks which are trained
jointly to consider low and high order feature interactions when there is the
data sparsity issue and dealing with massive data. As shown in Figure 6(b),
the framework includes two components i.e. wide and deep. Wide linear
component is modeled by the logistic regression classifier. It analyzes two
sets of input features including raw categorical features and transformed
features which are designed to memorize sparse feature interactions using a
cross-product feature transformation. Following the feature engineering
approach on the training data, the transformation function is designed to
represent the frequent co-occurrence of features to explore the possible
correlation with user responses. The deep neural network component is trained
to generalize the prediction for unseen inputs through low-dimensional
embeddings. In this model, the final output is calculated from the combination
of wide and deep components using the logistic loss function. In initial
studies, the embedding vectors are generated from a embedding dictionary by
feature hashing method (Chapelle et al., 2014) where most frequent categorical
values are transformed by projecting into pre-defined fixed-size numerical
vectors (Covington et al., 2016; Cheng et al., 2016; Shan et al., 2016). The
other models covered in the next section fix this issue using trainable
embedding vectors.

Some recent studies in this category extend different elements in the hybrid
design like embedding vectors (He and Chua, 2017; Niu et al., 2018; Zhou et
al., 2019b) and neural network architectures (Shan et al., 2016; Zhou et al.,
2018b, 2019a) to improve prediction performance. Although it is typically
expected that stacking of multi-layer fully connected neural networks can
capture arbitrary non-linear relations between input features, dealing with a
lot of parameters can cause different issues such as the degradation and over-
fitting. A study (Shan et al., 2016) proposes to use a residual neural network
for a deep component, where five hidden layers of residual units combined with
original input features are added to the result of two layers of ReLU
transformations. The effect of aggregation of embedding vectors on the
prediction performance is also studied in (He and Chua, 2017). The baseline
methods (Cheng et al., 2016; Shan et al., 2016) follow a simple concatenation
of embedding vectors in Figure 6(b) to be fed in a deep component to capture
feature conjunctions. They demonstrate that it may carry less non-linear
information in the low-level. Therefore, they suggest a Bi-Interaction pooling
encoder to capture more informative feature interactions. Considering an
embedding vector for each feature value, the Bi-Interaction pooling operation
is designed to generate the aggregated vector as follows:

(12) $\footnotesize
f_{BI}(V_{x})=\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_{i}\mathbf{v}_{i}\odot
x_{j}\mathbf{v}_{j}$

where $V_{x}=\\{x_{1}\mathbf{v_{1}},...,x_{n}\mathbf{v_{n}}\\}$ is the set of
embedding vectors, $x_{i}$ is binary feature value in sparse input vector,
$\mathbf{v_{i}}$ is embedding vector and $\odot$ operator makes element-wise
product of two vectors.

Further, authors in (Niu et al., 2018) pinpointed that the semantic intrinsic
relations between embedding vectors of user and ads can be captured through
their proposed structured semantic models. They propose a series of orthogonal
convolution and pooling operators rather than trainable convolutional
operators which can be applied as embedding vectors to address semantic
relations in input features. Experiments reported in the above studies show
that applying hybrid methods can improve logistic regression, which highly
depends on the quality of features prepared by using feature engineering. This
encourages further studies to develop extensions of factorization machines
with better generalization ability.

##### Factorization based hybrid methods

(a) LR

(b) Wide&Deep

Figure 6. a) Logistic Regression (LR) model: linear modeling of sparse feature
values b) Hybrid model (Wide & Deep model) as the alternative to Factorization
Machines to use a deep component to capture higher ($\geq$two) order feature
interactions combined with the Logistic Regression addressing low order
feature interactions

In (Guo et al., 2017), the authors provided a successful version of hybrid
methods as the stack of factorization machines and fully-connected neural
networks. The success of this design later led to employ this structure as a
base for developing many extensions (Wang et al., 2018; Zhang et al., 2019).
The study pinpointed that Wide & Deep method (Cheng et al., 2016) has some
challenges in modeling of feature interactions, since the wide component
includes the logistic regression model trained using a feature engineering. It
can cause a poor generalization. They investigated to use a factorization
machine to automatically capture feature interactions from one-hot-encoded
features. Following the structure shown in Figure 7(a), the proposed model,
DeepFM, combines the power of factorization machines and deep learning for the
feature learning in a recommendation application. The new neural network
architecture models linear and 2nd order feature interactions through FM and
models high-order feature interactions by fully connected neural network.
Replacing the logistic regression with factorization machines and using a
shared embedding layer between these two components, they build a model in an
end-to-end manner without a feature engineering.

Figure 8 shows the embedding layer structure, which is designed to project
discrete feature values to a dense numerical vector space. This projection is
modelled by a layer of linear neurons defined on the top of one-hot-encoded
input vectors (Guo and Berkhahn, 2016). It includes an embedding matrix of
parameters learned for each feature field. Embedding vector representing each
categorical field can be shown as follows:

(13) $\displaystyle e_{i}=W_{i}x_{i}$

where $e_{i}$ is the dense embedding vector and $x_{i}$ is the sparse binary
representation. $W_{i}$ is the embedding matrix for i-field with the dimension
of $m_{i}\times d_{i}$. $m_{i}$ denotes the number of discrete values for
categorical field $i$ and $d_{i}$ is the user-defined dimension of dense
embeddings. In practice, the functionality of embedding layer is identical to
one layer of densely connected neurons without considering bias links and
activation functions. It is shown that the embedding matrix $W_{i}$ can be
considered a lookup table for each field. This is because in the case of one-
hot-encoded input, the multiplication of input with embedding vectors in Eq.
(13) can be replaced by corresponding embedding vectors at referred indices in
the embedding matrix. Randomly initialized, the weights $w_{ij}$ in the
embedding matrix are trained during the optimization of the target value in
different models.

(a) DeepFM

(b) DeepFFM

Figure 7. a)Hybrid model (DeepFM): It is combined by a deep component (fully
connected neural network) with a Factorization Machines method(Figure 5(a))
using a shared embedding layer to feed dense embedding vectors as the input to
the structure b)Hybrid model (DeepFFM): It cascades the FFM interaction model
in Figure 5(b) to a MLP network as the deep component.  Figure 8. The
structure of embedding layer to generate dense embedding vectors. It includes
a linear mapping from discrete categorical features represented by one-hot-
embedded vectors to dense numerical embedding vectors. It equals to a layer of
linear neurons above input layer whose weights are getting trained using
gradient descent optimization. The weights are formed in a embedding
matrix(lookup table) to accomplish the linear transformation. The rows in the
matrix represent embedding vectors for discrete values in the categorical
fields

In (Qu et al., 2016) a new hybrid is proposed through combining embedding
vectors and a cascade of factorization machines and a MLP network. This method
takes advantage of learning ability of neural networks and discriminative
power of latent patterns in a more effective way than MLPs, through adding a
product layer between the embedding layer and the first layer of the fully
connected neural network. The model is examined with inner and outer product
operations in the product layer, to examine different methods to model the
feature interactions, combined with Stochastic Gradient Descent training
(using L2 regularization) and a dropout mechanism to address the over-fitting
issue.

As introduced in Section 4.3, in FFM(Juan et al., 2017) method as the field-
aware factorization machines, each feature value is represented by more than
one embedding vectors to model combinatorial features in input space. It
addresses different weights for interactions occurring between different
feature types.

The large number of features in latent vectors generally cause space
complexity problem and memory bottleneck (Juan et al., 2017). In addition, DNN
based models may run into insensitive gradient issue when dealing with multi-
field categorical data which deter the progress of gradient based
optimization. To tackle these challenges, a net-in-net architecture is
proposed as the generalization of kernel product (Qu et al., 2018) to model
feature interactions. So a micro network including one layer of the fully
connected neural network cascaded by dot-product feature latent features is
used as the special kernel function to alternate a simple inner-product
function in factorization machines.

Following the success of field-aware factorization machines (Juan et al.,
2017) in capturing feature interaction with regard to feature fields
information, a study (Yang et al., 2019) extends this idea to provide a hybrid
model of FFM and a fully connected deep neural network to learn feature
conjunctions in the input data, as shown in Figure 7(b). In this case, each
sparse input feature is represented by multiple embedding vectors to address
the effect of feature with regard to the feature field in inner (dot-product)
feature interactions. The embedding vector are organized as a 2-dimensional
matrix with size of $k\times n$ where $k$ is the dimension of embedding and
$n$ is the number of feature fields. Applying $n(n-1)/2$ inner-product
calculations between pair of embedding vectors to generate intermediary input
vectors, the predicted click-through rate value is generated from the output
of Deep component. Field-aware Neural Factorization Machines (Zhang et al.,
2019) further extends this method, by introducing a Bi-Interaction operator
with a wide concatenation based on Hadmard product operator as the alternative
to the inner product layer in Figure 7(b). Using Bi-interaction operator to
calculate feature interaction, the dimension of input vector of deep component
is changed to $n(n-1)/2\times k$. The increase of parameters in the embedding
vectors of field-aware based factorization machines methods can decrease the
prediction performance because of the over-fitting issue. Therefore, it
demands to select features before the feature interaction procedure in
factorization machines. Compared to Attentional Factorization Machines method
(Xiao et al., 2017) which captures important cross features interaction step
in FM model, a recent study (Zhang et al., 2019) evaluates the importance of
features before applying feature interaction step using Squeeze-Excitation
network (Huang et al., 2019; Zhang et al., 2019). The authors (Zhang et al.,
2019) introduced an attention-based method to selectively use more informative
features in embedding vectors. They propose to apply Compose-Excitation
network as the extension of Squeeze-Excitation Networks to select important
feature representations.

##### Generic hybrid methods

Some studies (Wang et al., 2017a; Lian et al., 2018) develop a hybrid method
to generalize the idea of factorization machines method. The authors in (Wang
et al., 2017a) extended the second order feature interaction in factorization
machines to higher order levels through a multi-layer network structure where
the maximum level of interaction order is determined by the number of layers.
Considering the structure of DeepFM method in Figure 7(a), a cross network is
employed for feature crossing operation using equation (14) through weighted
dot product of current output vectors at subsequent layers.

(14)
$\displaystyle\mathbf{x}_{l+1}=\mathbf{x}_{0}\cdotp\mathbf{x}_{l}^{\intercal}\cdotp
w_{l}+b_{l}+\mathbf{x}_{l}$

where $\mathbf{x}_{l}\in\mathbb{R}^{d}$ denotes the output vector calculated
at level $l$ and $w_{l}\in\mathbb{R}^{d}$ and $b_{l}\in\mathbb{R}^{d}$
constitute system parameters in this structure. In the first layer, the dot-
product of concatenated embedding vectors $\mathbf{x_{0}}$ are used to
generate the first output. For input data as a multi-field categorical data,
the proposed component explains the main difference between this model and
factorization machines methods in which dot product interaction here is
applied on the concatenation of feature fields rather than between pair of
feature fields. The study (Lian et al., 2018) is the other extended work to
create a new cross network in which feature interaction is modeled at a
vector-wise level through outer product instead. This leads to generating an
embedding matrix in which the operation in each layer has intuitively
connection to convolution neural networks by considering the weights as
filters.

##### Deep learning based methods

In literature, various deep learning techniques have been studied for the user
response prediction. The majority of previous work following a deep network
structure are typically based on two components of embedding and interaction
basically designed through deep neural networks to capture non-linear feature
interaction in sparse input data. Figure 9 demonstrates the structure of this
paradigm. Embedding component is designed to transform the sparse input data
into a low-dimensional dense latent space. The embedding vectors are then
processed by applying an aggregation mechanism to produce a fixed length
vector for the deep component. The high-order interactions between features
are addressed through feeding a fixed-length vector into the deep neural
network component generally implemented by the multi-layer perceptron
(Covington et al., 2016; Shan et al., 2016). Gradient based training is
adopted to learn the non-linear correlation between user features and user
responses. In this regard, there are lots of studies conducted to improve the
performance of each component. Table 4 demonstrates a summary of
representative methods mainly developed based on multi-layer perceptron,
recurrent neural networks and convolutional neural networks some of which are
combined with attention mechanism design their proposed models.

In online advertising, input features can be gathered from different sources.
In Figure 9, sparse binary features representing the input data can be grouped
into multiple categories like Table 2 regarding users, advertisers and
context. Deep neural network can process input data vectors with a fixed
length dimension. However, using a fixed-length vector for users with diverse
interests against advertisements can be bottlenecks for prediction, since each
user and web-page can have different labels and diversities at the same time.
Addressing the variety of user interest generally needs the expansion in the
dimension of embedding vector for user features in the aggregation step which
increase the risk of over-fitting and the cost of computation.

Dealing with this issue, two sub categories of features such as user profiles
and user behaviors (Zhou et al., 2018b) are proposed for click-through rate
prediction, where an array of user behavior in a period of time attributed by
categorical data (Zhou et al., 2018b; Ouyang et al., 2019a) like visited good,
shop and web-page category ids, are used to describe users and their
interests. The idea is further followed by (Ge et al., 2018) to model user
behaviors from the continuous image data. In the case of categorical features,
since the category of a shop and web-page visited by users may be shown with
multiple values, the binary representations are modeled by multi-hot-encoding.
They also address the importance of feature interaction in modeling of user
behaviors. To this end, they design a local activation unit to provide an
adaptive feature representation with regard to different ads, and assign
weights to the relevant pair of a visited page and advertisement in the user
behavior sequence with regard to the targeted ad. The output vectors are later
passed to a weighted sum pooling to generate a fixed length user behavior
embedding vector, and then passed into deep component to generate the
predicted output value.

Figure 9. DNN based architecture (Embedding & MLP) including two main steps
embedding layer followed by the aggregation operation to generate a merged
vector. The vector is used as the input for second step using MLP to generate
predicted user response value(CTR, CVR, …) developed in different studies. The
selected input features are chosen user profile and online user behaviour
sequence in addition to those selected for Ads and context

The application of attention units to model user behavior history has also
been studied for click-through rate and conversion rate prediction (Song et
al., 2019; Ouyang et al., 2019a; Xu et al., 2020; Ge et al., 2018; Wang et
al., 2018b; Li et al., 2020; Gao et al., 2018). A multi-head self-attentive
networks (Song et al., 2019) is proposed where features are mapped to multiple
subspaces through multi-head mechanism. This would help the model to consider
different orders of feature interaction with adaptive weights. In addition,
this method proposes a residual neural network rather than the conventional
MLP network to model high order combinatorial feature interactions. The study
(Ouyang et al., 2019a) extends the analysis of user behavior from two temporal
and spatial aspects. Because a web-page can be filled with more than one ad,
they model user behavior history not only by ads clicked by users but also
those not clicked by users. They consider ads shown in the same page above or
below the targeted in both spatial and temporal order. Their interactions to
targeted ads are modeled by adding an attention based factorization machines
layer followed by a fully connected neural network. In (Xu et al., 2020) the
multi-head attention mechanism is adopted to model the user behavior history
from a sequence of clicked/purchased advertisement information by adding
discriminative features likes dwell time on landing page for a conversion rate
prediction task.

Some studies also extend the deep component using different structures of MLP
based networks (Ouyang et al., 2019b; Ma et al., 2018; Wen et al., 2019;
Ouyang et al., 2019c). In order to tackle the data sparsity, researchers
(Ouyang et al., 2019c) propose to consider input features to be fed into a
couple of sub-nets built based on MLP network for a feature interaction
modeling, using features of users, query and ads entities. The sub-nets are
created to model the interactions between user-ad, the correlation between
ads. These models are then combined with the third one designed for the
prediction in a joint optimization. For conversion events followed after
clicking on ads, a deep learning based model is developed (Ma et al., 2018;
Wen et al., 2019) to consider not only all clicked ad impressions, but also
include all impressions and further user actions like “add to card” (DAction)
and “add to wish list” (OAction) taking place before conversion events.
Following a multi-task framework, multiple deep components are trained for
each event to generate the prediction of conversion post-click rates.

For the embedding, some studies propose to handle categorical and continuous
input features at the same time (Zhou et al., 2019b; Ge et al., 2018). For
images, convolutional neural network have been developed in several studies
(Ge et al., 2018; Chen et al., 2016; Yang et al., 2019). In the scale of
industrial applications, authors in (Ge et al., 2018) suggest to generate
embedding vectors of images using a pre-trained very deep convolutional neural
network rather than employing an end-2-end training model. The convolutional
networks are also adopted in (Liu et al., 2019) to extract implicit features
from the sparse input data and deal with the overfitting issue in fully
connected based networks (Covington et al., 2016). In the proposed model, the
convolutional neural network structure designed based on shared weights
followed by pooling module can considerably reduce the number of parameters.
Considering these embedding vectors along with raw features result aggregated
vector to be processed by a deep multi layer perceptron component.

##### Recurrent neural network based methods

Deep neural networks is typically made of multi layer fully connected neurons.
Following a stateless structure for neurons, the independent features
incorporate the data that flow through multi-layer perceptrons to generate the
output without backward links. Considering independently visited or clicked
advertisements to model the user behavior history fail to extract efficient
useful user interests with regard to user response prediction. Therefore,
recurrent neural networks are developed to process the sequence of input data
sorted by time to improve user response prediction performance (Li et al.,
2019; Zhou et al., 2019a; Feng et al., 2019; Pi et al., 2019; Chao Huang and
Chawla, 2019; Zhang et al., 2014).

In online advertising or e-commerce platforms, user intention is often not
explicitly expressed through their behavior history. Therefore, it is hard to
identify real interested users only based on captured online user behaviors.
In addition, living in a dynamic life environment, people’s knowledge increase
and their latent interest and behavior may change over time (Pan et al.,
2019), indicating that temporal correlation in online user behaviors can show
the evolution in the user interest to have more tendency to advanced items
compared to previous converted ones. It leads to studies of developing LSTM
models based on user behavior sequence from previous bought and clicked items
to predict conversion rates (Pan et al., 2019). Following Figure 9, to
aggregate embedding vectors, two categories of aggregation modules are
generally discussed in different recurrent neural network based studies. The
approaches like min-max or sum pooling based aggregation are generally applied
to model user behavior from independent input features. In the body of neural
network structure, GRU/LSTM neural units were commonly used in many studies to
model latent user interests (Li et al., 2019; Zhou et al., 2019a; Feng et al.,
2019; Pi et al., 2019).

Comparing to deep neural network based methods, recurrent neural networks
suffer from computational and storage overheads. They include hidden states in
the structure to capture user interests from sequence of user behavior data.
Therefore, it makes it difficult to use these network for industrial
applications visiting numerous users and ads everyday. It causes limitations
to apply these methods to model long term user interests based on long
sequential user history records. To tackle these challenges, some studies
introduced memory based architectures (Ouyang et al., 2019b; Pi et al., 2019;
Chao Huang and Chawla, 2019).

##### Convolutional neural network based methods

Studying to design deep learning network structures are not limited to above
discussed ones, since the input space suffer from the data sparsity which
makes it hard to learn directly using simple gradient descent methods.
Although the deep neural network including multi-layer perceptrons in theory
is known as an universal approximator which has a capacity to capture almost
all non-linear feature interaction in input space, but the order of magnitude
of parameters used a fully connected neural network deters to capture feature
interaction in a sparse feature space and leads to over-fitting issue. This
encourages to apply convolutional neural networks (CNN) which benefits from
parameter sharing and pooling mechanism to work with a feasible number of
parameters (Liu et al., 2019; Liu et al., 2015b; Edizel et al., 2017; Gao et
al., 2018; Chan et al., 2018). Dealing with image data along with multi field
categorical data, CNN networks are used to extract non-linear latent features
in the form of embedding vectors for raw pixel image data (Ge et al., 2018;
Chen et al., 2016; Gligorijevic et al., 2018; Niu et al., 2018). As one of the
primitive studies, authors in (Liu et al., 2015b) conducted experiments to
apply convolution filters followed by a flexible max pooling in a CNN network
on two datasets including multi-field categorical data and a series of
impressions in an e-commerce platform to capture neighbor patterns in input
data. The downside of this method was that they applied the convolution for
neighbors field feature while the feature interaction between non-neighbor
fields is neglected. However, for user response prediction tasks, any order of
feature fields are possible. The order of feature fields in the certain
alignment in input data does not have meaningful inference like images or
texts. Therefore, the other studies developed methods to take advantage of
both CNN and deep multi layer perceptron to address high order and low order
feature interactions.

For news recommendation, a knowledge-aware model (Wang et al., 2018b) proposes
to use knowledge graph to represent news items, with each news article being
attributed by word, contexts, and entity embeddings. For user response
prediction, CNN network, previously proposed for sentence representation
learning, is used to generate the final embedding vector of user and ad
features. Attentive neural network is applied to address user interest
diversity to estimate click-through rate values.

Table 4. Summary of selected DNN based user response prediction methods with a
hybrid structure.

Main DNN Structure | System Framework |  Method |  Features |  Application Domain |  Predict. Task
---|---|---|---|---|---
Embedding Component |  Deep
Component |  Aggregation |  |  |
MLP |  All features:RE${}^{\text{a}}$ |  MLP |  FM/Pooling Layer |  DSTN (Ouyang et al., 2019a) |  User, Query, Ad, Context, User clicked ad history |  E-commerce${}^{\text{b}}$ |  CTR
All features: RE${}^{\text{a}}$ |  MLP |  Concatenation |  MA-DNN (Ouyang et al., 2019b) |  User, Query, Ad, Memorized user interest (memory link) |  E-commerce${}^{\text{b}}$ |  CTR
All features: RE${}^{\text{a}}$ cascaded by FM |  MLP |  Concatenation |  PNN (Qu et al., 2016) |  User behavior ,item , context information |  Display advertising |  CTR
All features: RE${}^{\text{a}}$ |  MLP alongside FM |  Concatenation |  DeepFM (Guo et al., 2017) |  User behavior ,item , context information |  Display advertising |  CTR
All features: RE${}^{\text{a}}$ |  Multiple MLP Stacking |  Concatenation |  $ESMM$ ($ESM^{2}$) (Wen et al., 2019; Ma et al., 2018) |  User, Item, users’ historical preference scores |  E-commerce${}^{\text{b}}$ |  CVR
All features: RE${}^{\text{a}}$ |  Multiple MLP Stacking |  Concatenation |  DeepMCP (Ouyang et al., 2019c) |  User, Query, Ad, Context, negative ad sample features |  E-commerce${}^{\text{b}}$ |  CTR
All features: RE${}^{\text{a}}$ |  MLP alongside Hadamard product layer |  Concatenation |  NCF (He et al., 2017) |  The identity of Users and Items |  Movie/Image recommendation |  Ranking
All features: via Auto- feature grouping and high-order feature interaction selection |  MLP alongside FM |  Concatenation |  AutoGroup (Liu et al., 2020a) |  User behavior ,item , context information |  Display advertising |  CTR
CNN |  CNN(Pre-trained CNN model using orthogonal base convolutions) |  W&D(Cheng et al., 2016) |  Concatenation |  W&D SSM (Niu et al., 2018) |  User behavior ,item , context information |  Display Advertising |  CTR
Image ad features: CNN subnet
Other Ad features: fully connected subnet |  MLP |  Batch
Normalization |  DeepCTR (Chen et al., 2016) |  Image,categorical (Impression) |  Display Advertising |  CTR
All features:RE${}^{\text{a}}$ augmented to CNN subnet |  MLP |  Concatenation |  FGCNN (Liu et al., 2019) |  Categorical+continuous features in display advertising |  Display Advertising |  CTR
Ad,Query features (under character-level): 1d CNN subnet, Ad,Query features (word-level) |  MLP |  Cross-convolutional pooling |  DCP/DWP (Edizel et al., 2017) |  Ad, Query |  Sponsored search |  CTR
RNN |  Ad, context features:RE${}^{\text{a}}$
User behavior features: Hierarchical GRU based memory network |  MLP |  Concatenation |  HPMN (Ren et al., 2019) |  User behavior sequence,item context info |  E-commerce${}^{\text{b}}$ |  CTR
All features: RE${}^{\text{a}}$ |  MLP
LSTM |  Concatenation |  NTF (Wu et al., 2019) |  User behavior sequence,item, time |  Recommendation |  Product rate
Ad, context features:RE${}^{\text{a}}$
User behavior features: Memory induction GRU based unit |  MLP |  Concatenation |  MIMN (Pi et al., 2019) |  User behavior sequence,item context info |  Display advertising |  CTR
Neural Attention |  RE${}^{\text{a}}$ |  Multi-head ResNet |  Concatenation |  AutoInt (Song et al., 2019) |  User profile, item attributes |  Display advertising |  CTR
user profile, Ad features: RE${}^{\text{a}}$
User behavior features: Self Attentive Bi-LSTM |  MLP |  Concatenation |  DSIN (Feng et al., 2019) |  User profile, User behavior sequence, item, |  Display advertising |  CTR
User behavior (event) sequence: RE${}^{\text{a}}$
User behavior (timestep) sequence: Attentive embeddings followed Bi-GRU |  MLP |  Attention Mechanism |  DTAIN (Gligorijevic et al., 2019) |  Event, Timestep information |  E-commerce${}^{\text{b}}$ |  CTR
user profile, Ad, context features:RE${}^{\text{a}}$
User behavior features: self Attentive GRU relative to target ad |  MLP |  Concatenation |  DIEN (Zhou et al., 2019a) |  User profile, User behavior sequence, item, |  E-commerce${}^{\text{b}}$
Display advertising |  CTR
User behavior sequence features: RE${}^{\text{a}}$ controlled by multi-head
self-attention structure
Other features: RE${}^{\text{a}}$ |  Jointly training two MLP stacks for CTR and CVR |  Concatenation |  PFD+MD (Xu et al., 2020) |  User, Item, Post- click info, User Clicked/Purchased sequence, User-item interaction statistical info |  Display Advertising |  CVR,
CTR
User profile features: RE${}^{\text{a}}$ User behavior sequence features based on Ad image: Pre-trained embeddings |  MLP |  Concatenation,
Sum/Max/
Pooling |  DICM |  User, Ad (image), user behavior sequence(image) (Ge et al., 2018) |  E-commerce${}^{\text{b}}$ |  CTR
Pre-trained knowledge graph Word embeddings combined with, entity and context embeddings via CNN |  MLP |  Attentive pooling,
Concatenation |  DKN (Wang et al., 2018b) |  User (clicked news item), News item |  News recommendation |  CTR
Query & ad under word-level: 1)Pre-trained word embedding, 2) regular embedding${}^{\text{a}}$ Followed by bi-LSTM and MLP |  CNN
MLP |  Pooling, Query-Ad tensor matching |  DSM (Gligorijevic et al., 2018) |  Ad(title, URL, description), query words |  Sponsored search |  CTR

${}^{\text{a}}$ Regular Embedding using trainable look-up table parameters
(matrix embedding per feature) following the structure shown in Figure 8
---
${}^{\text{b}}$ In the e-commerce scenarios, the prediction task is defined as
the the probability that user clicks or makes an conversion on the recommended
items(ads)

##### Other methods

In the previous section, we have provided an review on classification methods
ranging from linear logistic regression based methods to advanced deep
learning based methods. A few other classification based methods which may
gain attention are generative adversarial network (GAN) based models (Li et
al., 2020; Deng et al., 2017), transfer learning (Zhang et al., 2016a; Su et
al., 2017), fuzzy design (Jiang et al., 2018), decision trees (Wen et al.,
2018; Gupta and Pal, 2019) and multi task learning (Wang et al., 2019d; Pan et
al., 2019b) approaches.

####  4.3.1. Ensemble Based Approaches

While early proposals for user response prediction mainly use linear logistic
regression classifiers, which provide the simplicity along with the
scalability, modern approaches are developed to address non-linear
interactions in data using methods likes factorization machines, generalized
version of decision trees, and neural networks. Some studies show that using a
single machine learning method may lead to non-optimal results, and propose a
new aspect of development to design a model structured from an ensemble of
machine learning models. These models can bring more improvement in the level
of accuracy for the prediction task. Generally, the design of ensemble models
are mainly categorized into four sections like Bagging and Boosting, Stacked
Generalization and Cascading shown in Figure 10 (Alpaydin, 2010).

Figure 10. Ensemble structure types: a) Bagging randomly samples training
data, with replacement, to generate N subset data and train N predictor
models. The final result is the combination of N classifier outputs; b)
stacking: N models are trained in parallel based on the same training data.
The final output is combined through a meta-classifier. This classifier is
fitted on the output of base classifiers; c) Boosting(AdaBoost): a series of
predictor models are trained using a subset of training data sequentially. The
subsets of data are created adaptively using misclassified samples in previous
model; d) Cascading: is based on concatenation of multiple classifiers

The combination of different classification methods in the form of ensemble
structures are utilized in different studies. The study in (Zhang et al.,
2016b) followed a cascading version of an ensemble model which includes two
learners. They investigated the performance of combining factorization
machines with a fully connected neural network to predict CTR values for the
digital advertising. Because of the data sparsity in the categorical input
data, the feature interaction cannot be easily detected directly using deep
neural networks which generally lead to the overfitting issue. They propose to
cascade factorization machines to a deep neural network in order to address
this issue.

In the context of e-commerce websites, (Aryafar et al., 2017) suggested multi-
modal ensemble learning to consider texts and images of posts as different
modalities. They separately built a logistic regression model for historical
CTR values and another model for embedding vectors of images and textual
information. Following the multi-modal learning approach, the stacking
ensemble model is used to combine linearly their results by passing to the
final logistic regression classifier.

In another study, authors in (Wen et al., 2018) propose to develop an ensemble
model for conversion rate prediction which is mainly based on GDBT learners.
Following the Cascading and stacking techniques, they used multi-level cascade
of GBDT models to extract features which are coming for values received from
the previous model. To improve the diversity of extracted features, multiple
cascade of decision trees are aggregated like Figure 11 through the
concatenation to be passed to the conclusive GDBT to generate the final
features for the classification. As a part of the contribution of this work,
in order to improve the prediction performance, the importance of input
features is also considered. They use a separate GBDT model to pre-process the
input raw features and generate two class of features that have weak and
strong correlations (WCF and SCF) with regard to the prediction result. These
class of features are used relatively as the input to train the model.

Figure 11. Ensemble GBDT model: a) Input features randomly selected from the
feature pool fed into GDBT model. Their importance for prediction is evaluated
based on their correlation to class labels by traversing from the root node
into leaf in a tree. They are sorted into two categories according to the
explanatory power into WCF(Weak correlation features) and SCF(Strong
correlation features) b)The structure of proposed multi-level deep cascade
trees including stacking multiple sequence of GDBTs

In literature, some works also comparatively study the effect of ensemble
techniques (Ling et al., 2017; King et al., 2015). Following the ensemble
techniques introduced in the beginning part and the goal to improve click-
through rate values, the study in (Ling et al., 2017) examined two ensemble
techniques Boosting and Cascading with GBDT, LR and a fully connected deep
neural network classifiers. They compared the performance of corresponding
single learners with the cascaded and boosted version of pair of models in the
click-through rate prediction for the sponsored search advertising. For the
sponsored search advertising application again, the study in (King et al.,
2015) made a comparison between the effect of four different structures of
ensemble learning such as the majority voting, bagging, boosting and stacking
for pay-per-click classification. The features are selected from different
information sources like the attributes describing ad impression, click-
through rate value, conversion rate value, and the position of ads in addition
to the textual features captured from the title and the body of ads and
campaign categories. They are joined together to train ensemble learners such
as Naïve Bayes, Logistic Regression, Decision tree and SVM to estimate the
pay-per-click value of campaigns.

###  4.4. Unsupervised and Semi-supervised Approaches

In this section, we review two categories of methods in the literature that do
not fully rely on labeled data. In this case, the predictive models are
designed based on the implicit and explicit pattern in data. Semi-supervised
models refers to approaches like graph neural network based models that
involve designing a user feedback estimation model using both labeled and un-
labeled sampled data. Two categories of these methods are represented in the
following sub-sections.

####  4.4.1. Clustering Based Approaches

Clustering methods have also been investigated in the literature for online
advertising. As an unsupervised approach, clustering involves grouping sample
data into related clusters based on similarity among data points.

Some studies develop statistical clustering methods categorical data in
different contexts, such as $k$-modes (Sharma and Gaud, 2015) as an
alternative to the popular $k$-means method which uses hamming distance as the
distance metric, COOLCAT made by (Barbará et al., 2002) uses the notion of
entropy for the similarity metric, or CLOPE clustering approach in (Yang et
al., 2002) research which develops a scalable method to leverage the trend of
a height-width ratio of the cluster histogram as the similarity criterion. But
these categorical clustering methods are not well studied in the online
advertising with the multi-field categorical data.

On the other hand, some clustering based studies proposed the idea to improve
classification based methods. As the initial study in this category, to
supplement the logistic regression (Chapelle et al., 2014) and gradient
boosting decision trees (GBDT) (H. et al., 2010) methods for user response
prediction task , authors in (Regelson et al., 2006) propose to use feedback
features which are prepared from historical user behaviors. Considering
advertiser and publisher come from with different hierarchical granularity,
they incorporated the combination of publisher page and advertisement along
with user-publisher-creative which are created based on the hierarchical
structure of user as the new features. The extra features are quantized using
the $k$-means clustering to be added to input features for training.

Some methods (Regelson et al., 2006; Reps et al., 2014; Wang et al., 2011)
organize the user input, such as keywords used in search engine or pages
visited by users, by using clustering to reduce the severity of above
mentioned issues and improve the correlation with user responses. In (Regelson
et al., 2006), the authors suggest that since a different click response
probability can be assumed for different query keywords, the topic of ads and
query keywords can be used to organize data into clusters where more closely
related terms have more similar click-through rate values. They propose to
generate groups of terms using hierarchical clustering and keyword-advertiser
matrix. The similarity of samples intra and between clusters are evaluated by
the textual similarity of terms in ads. Therefore, assuming the fixed CTR
value for clusters, the estimated value of click-through rate for new samples
is determined by the nearest neighbor clusters.

####  4.4.2. Network Based Framework

With development on the Internet, information networks are the common element
of online businesses. In this subsection, we will go over approaches
addressing the network structure in the input data to develop predicting
models for the user response prediction.

##### Graph embedding based methods

Recent years have seen a lot of studies which focused on the application of
network representation learning methods for recommender systems and the user
response prediction. Motivated by the success of CNN and RNN, there has been
an interest in developing neural network based models for the graph structured
data. Considering three major challenges in recommender systems, scalability,
data sparsity, and cold start, many methods have been proposed in the
literature using graph embedding (Wang et al., 2018) and graph neural network
(Kim et al., 2019; Li et al., 2019; Fan et al., 2019).

Figure 12. The billion-scale commodity embedding proposed by (Wang et al.,
2018) for E-commerce recommendation in Alibaba: a) user behavior sequences
including items(Ads) visited in one or more session specified by dash lines.
b) item(ad) graph generated user behavior sequences that a direct edge
representing two subsequent items(ad) in user history. c) generating sequence
of nodes using random walk in graph following Deepwalk method. d) Proposed
graph embedding algorithm to use side information to reduce data sparsity.
Field 0 specifies a node in random walk and field 1 to field $n$ are the one-
hot-encoded vectors for side information corresponding to the ad node in the
graph. Hidden layer is a weighted average aggregation of dense embedding
vectors

Authors in (Wang et al., 2018) designed a recommender model based on the graph
embedding which takes advantage of side information to cope with the three
challenges. The model includes two sections such as matching and ranking.
Focusing on the first section with the network of users interacting with items
in an e-commerce website, they applied DeepWalk (Perozzi et al., 2014) to
generate embedding vectors of items in the directed graph of items formed
using user online behavioral history. Because of the data sparsity, there is a
lack in the number of interaction in the graph. Therefore, as the part of the
contribution, side information such as the price value, shop, category and
brand, are included as the one-hot encoded vectors in network representation
learning procedure.

Graph Neural Networks (GNN) are known as one the most effective solutions to
develop predictive models for network based data. Extended from recurrent
neural networks and convolutional neural networks, GNNs have a unique
capability to generalize neural networks to cope with directed and un-directed
input graphs, by using an iterative process to propagate node status over
their neighborhoods. After optimization, it can provide an embedding output of
nodes in the graph in which the feature information are aggregated using their
neighbor nodes. Recently, GNN based methods have received more attention for
online advertising and recommendation systems applications (Kim et al., 2019;
Li et al., 2019; Fan et al., 2019; Wang et al., 2019a, b; Zhang et al.,
2019a). Like deep learning based models in Table 4, Embedding and Interaction
components are two major components in the design of these predictive models
in the literature. The embedding component is dedicated to map information
associated to node and edges in the graph-structured data into numeric
vectors. However, the interaction component tries to make the reconstruction
of user feedback in the system. This part can be designed by different ways
through a MLP component in deep learning based models (Wang et al., 2019b) or
inner-product between embedding vectors (Wang et al., 2019a) or element-wise
multiplication of embeddings (Zhang et al., 2019a) to represent collaboration
between users and items to rank and predict user preferences in recommendation
and online advertising systems. The embedding component is developed using
recent advance in graph neural networks. Authors in (Wang et al., 2019a; He et
al., 2020) propose an propagation layer in their embedding component to refine
embedding vectors via aggregation of embedding vectors of neighboring nodes in
the graph. The model in (Wang et al., 2019a) is built using the message-
passing architecture and defining a model via layer-wise message constructing
and aggregating operations. A recent study (Li et al., 2019) addresses the
limitation of methods like DeepFM (Guo et al., 2017), by considering a graph
structure for feature fields in the input data in which nodes corresponding to
feature fields interact with others through weighted edges to reflect the
importance of field interactions. A GNN based model is developed to model
complex interaction between input field features. In this model, field feature
as the nodes in graph are attributed by hidden state vector which is updated
using a recurrent approach. An interaction step parameter is defined to
consider higher and lower interactions between nodes and their neighbor nodes
which are located in one or more hops away. The ending point of the model
includes an attention layer to predict CTR values.

One essential challenge of network embedding for the user response prediction
is that the embedding learning might not be directly optimized towards the
underlying user response prediction. Following an unsupervised learning, nodes
are represented using embedding vectors, however, they may not be optimized
for downstream tasks like the click-through rate prediction. This issue can be
considered as the bottleneck to improve the task. Therefore, the user
intention modeling is considered as an alternative (Zhou et al., 2018b,
2019a). Considering the sequence of the user behavior from the interaction
between users and ads in the user intent modeling still have some challenges
like the data sparsity and weak generalization. A study (Li et al., 2019)
showed that sequence of user behavior can be organized as a co-occurrence
commodity graph with node representing clicked commodities and weighted edges
describing number of co-occurrence times. To address the sparsity problem, a
multi-layered neighbor diffusion is performed on the commodity graph. The
preceding result is combined with using an attention layer to generate user
intention features. These features combine with other ones, such as user
profiles, query keywords, and context in fully connected network, for the
click-through prediction.

##### Knowledge graph based methods

Knowledge graphs (KG) are semantic heterogeneous networks including a
collection of entities with attributes that are inter-connected together
through edges. They are usually described through a triplet with relation
connecting head and tail entities like (Head, Relation, Tail). This structure
of data has been studied for different applications like link prediction
(Dunlavy et al., 2011) and Web search analysis (Torres et al., 2014). The
advantages of the knowledge graph for applications suffering from data
sparsity and cold start problems, such as recommendation systems, have been
observed from different perspectives. First, networks can provide additional
semantic relationship information to improve the recommendation performance.
Moreover, the diversity of information in the knowledge graph can extend the
information for matching with user interests. In addition, the historical
information linked to items in recommender systems can provide implication
ability for the system. In summary, we separate knowledge graph based methods
for recommender systems and online advertising into three categories:
embedding-based, path-based, and hybrid methods.

###### Network embedding methods

This category of methods aim to map the components of the knowledge graph,
including entities and relations, into low-dimensional embedding space to
preserve network structural information (Wang et al., 2017b). Some jointly
incorporate heterogeneous attributes and content that are assigned to nodes in
the graph for modeling (Zhang et al., 2019a).

For example, knowledge graph based representation for news recommendation
(Wang et al., 2018b) has been studied to address the challenge of topic and
time sensitivity for news items selected and visited by users. It means that
users generally visit selected news at a short specific of time which may not
happen later. In addition, news content usually has brief words and diverse
topics. To handle these challenges, a deep neural network is proposed to take
advantage of a customized CNN module as the key component to model user
interest through multiple channels which consider both word semantics
information and corresponding information from a generated knowledge graph
data. This leads to generating three categories of embedding vectors for words
in the body of news, the associated entity and immediate neighbors in
knowledge graph. In the design, an attention mechanism is used to aggregate
embedding vectors of user behavior sequences. They avoid using concatenation
strategy for the aggregation in this step since entity and word embeddings may
have different dimension generated from different contexts. The output are fed
into a fully connected neural network to learn the probability of user’s click
for a selected news piece. Likewise, a study (Zhang et al., 2019a) presents a
heterogeneous graph neural network model which adopts the aggregation of
feature information with regard to a sampled neighboring nodes. A node
sampling procedure is suggested to aggregate selected neighbors grouped by
their types and their frequency in a designed random walks. Using attention
mechanism, the content embedding of neighbor nodes with the same type are
first aggregated. It is then followed by another attention round to aggregate
embedding vectors of neighbor nodes from different types in the graph. They
train embeddings using heterogeneous skip-gram learning. To compare the
performance of proposed model, element-wise multiplication and inner-product
operations of user and items embedding vectors are used to simulate user
response for link prediction and recommendation experiments.

###### Meta-path based methods

This category contains knowledge graph embedding methods which employ meta-
path schemes as the guideline to generate random walks and in turn embedding
vectors. Although many studies in the category have shown a decent performance
for recommender systems (Fan et al., 2019; Zhang et al., 2019b), current
methods heavily rely on manually building random walk corpus for further
processes. The selection of meta-path schemes are generally considered as the
hyper-parameters set differently by researchers in experiments. So this can be
an issue in practice. To tackling this problem, attention mechanism has been
employed in recent studies. Authors in (Wang et al., 2019b) design a
heterogeneous graph neural network to automatically address the effect of
different neighboring nodes and meta-paths using two-level attention layers.
In the first level, node-level attention is applied to train the weights for
meta-path guided neighbors of each node in the graph. It is then fed to a
semantic attention step to calculate weighted combination of different meta-
paths for the node embeddings. The predicted interaction between different
node types in heterogeneous graph is modelled through training a fully
connected neural network at the end.

###### Other knowledge based methods

In this section, we present hybrid knowledge based methods which learn
user/item embeddings by exploiting structural information in the knowledge
graphs (Wang et al., 2019c; Qu et al., 2019). Recently, a study (Wang et al.,
2019c) discusses the extension of GNN method made for a knowledge graph where
the edge weights between user and item nodes are not available beforehand. So
a personalized scoring function is proposed for training to determine the edge
weights via a supervised approach following a relational heterogeneity
principle in the knowledge graph. To address the data sparsity issue in
recommendation systems, a leave-one-out loss function is used as a label
smoothness regularization to calculate predicted weight values. It leads to
calculating node embeddings through aggregating node’s feature information
over the local neighborhood of the item node with different weights.

A common approach to model user response in knowledge graph based methods is
to apply aggregation mechanism to combine embedding vectors of user and items
entities via average pooling or attention units over their neighbors. Authors
in (Qu et al., 2019) consider this as early summarization problem. They argue
that modeling user response using the inner product of embedding vectors of
user and item can have a limitation for user response prediction. Accordingly,
a neighborhood interaction model is proposed to integrate a higher order
neighbor-neighbor interactions through a bi-attention network in the
aggregation step to improve user click through rate prediction.

###  4.5. Stream Based Framework

Online advertising is essentially a streaming platform, where users, auctions,
and ads are continuously and dynamically changing (Wang et al., 2016). In this
context, data stream refers to continuous feeds of news and information
generated by users in an interactive way (Leong et al., 2014). Social media
platforms are examples of these systems in which millions of users generate
data continuously being uploaded. The stream environment provides an
opportunity to emerge in-stream advertising with commercials in stream of
data. Also known as native advertising, in-stream ads look similar to regular
feeds. They are differentiated by an assigned tag indicating a commercial
target or the content of feed.

The performance of advertising strategies for stream data has been studied
from different aspects according to the condition and policies in online
platforms. Click-through rate value is not only a metric to evaluate user
experiences. Many studies have developed methods to address pre-click and
post-click user experiences (Lalmas et al., 2015; Barbieri et al., 2016; Zhou
et al., 2016). From a different perspective, user response prediction was cast
to evaluate ad quality. The high rate of quality value is considered as the
positive influence for users to use the platform more and produce even more
click responses for the long run. There are some studies experimenting a model
to address the impact of ads quality for predicting user response and user
engagement, based on in-app advertising such as Yahoo Gemini platform (Lalmas
et al., 2015; Barbieri et al., 2016). To this end, a post-click experience
instead of click-through rate value is used to evaluate the user experience on
the landing page of advertising web-sites. Post-click experience is attributed
by metrics like dwell time and the bounce rate. The former measures the
spending time in the landing page where the latter indicates the percentage of
short and momentary dwell times. The level of user engagement with ads is
considered to have a natural connection to the time length users spend in
landing websites.

Aside from ad quality metric, in the context of social media, CTR prediction
for stream data in Twitter is first studied (Li et al., 2015), where positive
use responses are defined as retweet, reply, and actual click on promoted
tweets. They also use a dismiss feature in Twitter to identify explicit
negative instances for the analysis. According to the fact that the number of
spots dedicated for promoted tweets are limited, in this study a learning-to-
rank method with a calibration mechanism is proposed to combine traditional
classification with pair-wise learning to address data sparsity and
scalability issues. They formalize two problems of classification and ranking
in the framework.

In an alternative work (Diaz-Aviles et al., 2012), time-sensitivity of
streaming data in Twitter and the short memory issue for online learning are