# Ad-load Balancing via Off-policy Learning in a Content Marketplace

Hitesh Sagtani, Madan Jhawar, Rishabh Mehrotra, Olivier Jeunen
hiteshsagtani,madangopal,rishabhmehrotra<EMAIL_ADDRESS>ShareChat

###### Abstract.

Ad-load balancing is a critical challenge in online advertising systems,
particularly in the context of social media platforms, where the goal is to
maximize user engagement and revenue while maintaining a satisfactory user
experience. This requires the optimization of conflicting objectives, such as
user satisfaction and ads revenue. Traditional approaches to ad-load balancing
rely on static allocation policies, which fail to adapt to changing user
preferences and contextual factors. In this paper, we present an approach that
leverages off-policy learning and evaluation from logged bandit feedback. We
start by presenting a motivating analysis of the ad-load balancing problem,
highlighting the conflicting objectives between user satisfaction and ads
revenue. We emphasize the nuances that arise due to user heterogeneity and the
dependence on the user’s position within a session. Based on this analysis, we
define the problem as determining the optimal ad-load for a particular feed
fetch. To tackle this problem, we propose an off-policy learning framework
that leverages unbiased estimators such as Inverse Propensity Scoring (IPS)
and Doubly Robust (DR) to learn and estimate the policy values using offline
collected stochastic data. We present insights from online A/B experiments
deployed at scale across over 80 million users generating over 200 million
sessions, where we find statistically significant improvements in both user
satisfaction metrics and ads revenue for the platform.

††copyright: none

##  1\. Introduction

Ad-load balancing plays a critical role in content marketplaces, including
prominent platforms like Facebook, Instagram, Sharechat and Youtube, where we
need to determine the optimal ad-load during a user session. On one hand,
maximizing user satisfaction is crucial to provide a positive user experience
and ensure long-term engagement. On the other hand, advertising revenue is a
key factor for the sustainability and profitability of the platform. The
challenge lies in finding the right balance between these objectives. In this
paper, we propose a novel approach to ad-load balancing that leverages off-
policy learning using unbiased estimators.

In our approach, we define the problem as determining the optimal ad-load for
a particular feed fetch, considering the conflicting objectives of user
satisfaction and ads revenue. However, the complexities of the problem go
beyond the mere trade-off between these two metrics. User heterogeneity is an
important factor to consider, as different cohorts of users may have varying
ad-tolerance levels. Some users may be more accepting of ads, while others may
be more sensitive to excessive ad exposure. Furthermore, the impact of other
contextual signals adds another layer of complexity. The satisfaction drop
caused by increased ad-load may vary depending on _where_ in the session the
user finds themselves.

Even though this problem is at the heart of online content marketplaces, it
has received little attention in the research literature so far. Indeed,
publicly available work does not discuss how advances in machine learning can
be leveraged for this common use-case. To address this gap, we propose an off-
policy bandit formulation for ad-load balancing in the context of a social
media platform. Our approach leverages user, content, and ads-related features
as contextual information within the bandit framework. We explore different
ways to model the action space, going from mere ad _volume_ to the _position_
of the ads in the feed. The contextual bandit paradigm allows us to make
informed decisions that balance user satisfaction and advertising revenue,
considering user heterogeneity and session context. We leverage counterfactual
optimization techniques on offline collected stochastic data, making use of
unbiased estimators based on Inverse Propensity Scoring (IPS) and Doubly
Robust (DR) methods (Saito and Joachims, 2022). This enables us to evaluate
the effectiveness of various ad-load allocation policies in improving both
user satisfaction and ads revenue reliably, from offline data.

Finally, we present insights from A/B experiments into the behavior of the
selected policies. We observe directional alignment between our off- and
online experiments, in that the top candidates based on offline policy value
estimation lead to statistically significant improvements in _both_ user
satisfaction metrics and advertising revenue compared to homogeneous and
static allocation policies, highlighting the value that personalisation can
bring.

In summary, the contributions of our work include the following:

  1. (1)

We introduce the “ _ad-load balancing_ ” problem, which is at the heart of
online content marketplaces but has received little attention in the research
literature.

  2. (2)

We motivate the problem and its nuances through insights obtained from real-
world data (§3).

  3. (3)

We propose an off-policy contextual bandit framework to tackle the problem via
counterfactual optimisation (§4).

  4. (4)

We present results from live experiments that highlight the effectiveness of
our approach, leading to online improvements in both user- and advertiser-
focused objectives (§5).

Figure 1. Heatmap visualising Pearson’s correlation coefficient among the
user-focused objectives we consider.

##  2\. Related Work

Ad load personalisation. Online advertising is at the heart of the modern web,
and a very lively research area as a result (Bagherjeiran et al., 2022). The
majority of existing work typically focuses on the advertising stack itself,
from bidding (Cai et al., 2017; Jeunen et al., 2022b, 2023a) and response
modeling (McMahan et al., 2013; He et al., 2014) to auctions (Liu et al.,
2021; Jeunen et al., 2023b). Even though the trade-offs and tensions between
advertising load and other platform objectives are widely reported and
apparent, works that directly tackle this problem are scarce. Works exist to
tackle ad fatigue from repeated impressions due to the same ad (Abrams and
Vee, 2007), or general “banner blindness” as a result from ad overload
(Resnick and Albert, 2014). Other seminal work leverages counterfactual
reasoning techniques to gain insights into search engine advertising (Bottou
et al., 2013). To the best of our knowledge, our work is the first that
provides a practical and effective method to deal with personalised ad load
balancing in online content marketplaces.

Multi-objective optimisation. Advertising problems in content marketplaces
inherently deal with multiple stakeholders that each have multiple, possibly
conflicting, objectives. Abdollahpouri et al. provide an overview of the
problems that typically arise in multi-stakeholder recommender systems, and
common approaches to solving them (Abdollahpouri et al., 2020). Zheng and Wang
discuss multi-objective optimisation methods proposed in the research
literature (Zheng and Wang, 2022). Mehrotra et al. propose a bandit-based
multi-objective optimisation method geared towards music streaming platforms
(Mehrotra et al., 2020), adopting a Generalised Gini Index (GGI) aggregation
function to balance multiple objectives (Busa-Fekete et al., 2017). Our work
complements this existing research literature by showing how simple
scalarisation techniques, which are commonly used in multi-objective
contextual bandit use-cases, can be effective in solving the personalised ad
load balancing problem.

Counterfactual learning and evaluation. As machine learning use-cases in
modern web platforms move from making _predictions_ to making _decisions_ , a
parallel shift is happening from _supervised_ learning approaches towards
those that leverage _bandit_ feedback (Jeunen et al., 2022a). Due to the
challenges that arise with real-time learning, these systems typically operate
in a batch fashion (Swaminathan and Joachims, 2015b). This line of work is
closely related to the offline Reinforcement Learning (RL) literature (Levine
et al., 2020), but practical applications often rely on the _bandit_
assumption (i.e. the Markov Decision Process consists of a single timestep or,
analogously, there is no _state_) (Bottou et al., 2013; Ma et al., 2020;
Jeunen et al., 2022b). We leverage recent advances in this field to our use-
case, and provide a more detailed overview in Section 4.3.

Figure 2. Visualising the inverse relation between user satisfaction & ads
objectives, w.r.t. advertisement positions.

##  3\. Nuances of Ad-load balancing

In this section, we provide a motivating analysis of the ad-load balancing
problem and highlight the challenges it entails: starting with the trade-off
between user satisfaction and ads objectives, then discussing heterogeneity
among users towards ads tolerance. To gain an understanding of these
challenges, we consider metrics such as retention, user engagement, time
spent, ad impressions, and ad clicks to quantify the trade-off in our proposed
framework.

###  3.1. Data Context

We collected user data from ShareChat, a widely popular multilingual social
media application with over 180 million monthly active users in India,
supporting 18 regional languages. Our dataset consists of feed-level data from
a randomly selected sample of 5 million users and approximately 250 million
feeds.

Typically, a social media platform presents consecutive feed fetches with 10
posts. In order to reduce the action space for off-policy modeling (and hence,
the variance of the estimators), we propose to treat a single feed as multiple
independent smaller feeds. This strategy is further elaborated in Section
4.2.1. Specifically, we suggest treating a single feed of 10 posts as two
independent feeds, each with 5 posts, with the possibility of having 0, 1, or
2 ads.

###  3.2. Trade-Off between ads and user satisfaction

To better motivate the need for ad-load balancing, we analyze the global
trade-off between ads and user satisfaction metrics. We consider
_satisfaction_ metrics such as engagement, video play (a binary metric
indicating whether a particular video type has been played beyond a specific
threshold value), feed depth scrolled (representing the number of successive
feed fetches by a user), as well as user _dissatisfaction_ metrics like feed
abandonment and session abandonment. In terms of advertising, we examine
metrics related to ad views and clicks. Figure 1 shows how such short-term
engagement signals are correlated to one another – and how user satisfaction
and dis-satisfaction signals are negatively correlated.

Trade-off with respect to the different ad positions: Figure 2 presents the
normalized values of satisfaction, dissatisfaction, and advertising metrics
for different ad-slots in a single feed fetch. We observe that increasing the
number of ads from 0 to 2 results in decreased satisfaction, increased user
dissatisfaction, but also higher ads impressions, clicks, and ultimately
(short-term) revenue. Similar effects are observed within ad-slots of 1 ad,
when a change in its position from 6 to 2 leads to variations in user metrics
due to early exposure to ads at the top of the feed. This phenomenon arises
because the view probability decreases for posts further down the feed. To
further support these arguments, we present the abandonment analysis in the
subsequent section.

Analysing Feed Abandonment: A key user dis-satisfaction metric is given by
_abandonment_ events. Indeed, if a user leaves the feed, we can interpret this
as a negative signal. Note that this would not always be the case – as all
users, including satisfied ones, leave the feed at some point. Nevertheless,
for the purposes of this analysis we can interpret it as such. To observe the
causal effect that advertisements have on abandonment probabilities, we ran an
online test with a static advertising policy and uniformly randomly ranked
content. Indeed, this ensures that the effects of enjoyable content are
uniform over the positions, and any observed effects come from other sources
(we effectively perform an _intervention_ (Pearl, 2009)). As such, if we
observe increased abandonment probabilities at the fixed advertisement
positions in the feed, this indicates a negative _causal_ effect of
advertisements on user satisfaction. Figure 3 visualises insights from this
experiment, with the position on the feed on the x-axis and the abandonment
probability on the y-axis. Note that we present _normalized_ values of
probabilities in the figure (by dividing the actual probability with some
constant) to remove commercially sensitivite information. We observe clear
negative effects that we would wish to alleviate with more intelligent
allocation policies.

Figure 3. Static advertisement positions lead to increased feed abandonment
probabilities (normalised at position 1) right after the ads.

###  3.3. Heterogeneity across users

In the previous section, we observed the global trade-off between user
satisfaction (SAT) and ads metrics. However, it is important to acknowledge
that different user cohorts have varying tolerance levels for ad-load,
resulting in user heterogeneity. Figure 4 illustrates the changes in SAT and
ads metrics when the ad-load is increased for users in every alternate feed
fetch by 1 additional ad. We primarily consider language and fatigue score
(Sagtani et al., 2023) to cohort users. The fatigue score was proposed as a
surrogate metric for user inactivity on the platform. A lower fatigue score
indicates highly active users, while a higher fatigue score suggests inactive
users.

For both user cohorts, we observe an increase in ads impressions after
increasing the ad-load in alternate feed fetches. The left section of Figure 4
demonstrates that the decrease in user satisfaction metrics is less pronounced
for Tamil and Telugu users compared to Hindi and Kannada users. Similarly, for
users with lower fatigue scores, the decrease in user satisfaction metrics is
less significant compared to users with higher fatigue scores. Additionally,
we note that ads impressions _decrease_ as fatigue score increases, as more
active users tend to perform more feed scrolling, resulting in increased
impression opportunities. These findings highlight the heterogeneity in ad-
tolerance among user cohorts and emphasize the importance of incorporating
user context to determine the appropriate ad-load.

Table 1. Optimally learned weights for user (dis-)satisfaction metrics and advertising objectives in our reward function. Signal | Weight | Description
---|---|---
User (dis-)satisfaction signals |  |
Engagements | 0.5995 | User’s engagement signals such as likes, sharing on other platforms & downloads
Video play | 0.6235 | A binary metric indicating whether a particular video type has been played
Percentage video watch | 0.3464 | A continuous variable indicating the fraction of the video watched by the user.
Feed depth scrolled | 0.3213 | The number of successive feed fetches by a user
Video skip | -0.1432 | A binary label, positive if a video watch is less than 2 seconds
Discounted feed abandonment | -0.3742 | Did the user quit the feed, but enter another feed without quitting the session after the ad?
Discounted Session abandonment | -1.2345 | Did the user quit the session entirely after the ad?
Ads objective signals |  |
Impression | 0.2234 | Did the user see the ad in case of CPM campaign?
Clicks | 0.5135 | Did the user click on the ad in case of CPC campaign?
Install | 0.7823 | Did the user install the app in case of CPI campaign?

##  4\. Problem Formulation

Contextual and personalised ad-load balancing is an important and common
problem – but data-driven approaches have not been reported in the research
literature. As we effectively aim to maximise cumulative _rewards_ by
assigning the right _actions_ to _contexts_ , the problem setting matches the
contextual bandit paradigm. On-policy bandit approaches that learn online are
ill-suited for our setting, as they might show unpredictable behaviour once
deployed (van den Akker et al., 2023). Instead, the logged data mentioned in
Section 3.1 allows us to leverage advances in off-policy learning for our use-
case. We leverage three well-known families of methods: the Direct Method
(DM), Inverse-Propensity-Weighted (IPW) empirical risk minimisation (ERM), and
a doubly robust variant (Dudík et al., 2011; Su et al., 2019; Swaminathan and
Joachims, 2015a, c). In what follows, we introduce these methods, and explore
various options when designing the action space and the reward function.

###  4.1. Propensity score validation

We collect data from a uniform random logging policy in the form (x, a, ra,
pa), where $x\sim D(x)$ is the observed context, $a\in A$ is the action drawn
using uniform random distribution over the action space, ra is the
corresponding reward we observe and pa is the propensity score of selecting an
action.

Off-policy evaluation and learning approaches that rely on importance sampling
or IPW require _full support_ of the logging policy (Owen, 2013). This implies
that the probability with which the logging policy selects actions should be
non-zero for every possible context-action pair: $p_{a}>0\ \forall a\in A$.
This requirement is easily verified for the uniform random policy, as
$p_{a}=1/\left|A\right|$ where A is the action space. Aside from this explicit
assumption – practical applications often prohibit effective unbiased reward
estimation because due to a variety of reasons (London and Joachims, 2022; van
den Akker et al., 2023). Mehrotra et al. (Mehrotra et al., 2020) and Li et al.
(Li et al., 2015) propose two simple tests that validate the logged propensity
scores, which we explicitly adopt here.

Figure 4. Visualising user-level heterogeneity to advertising effects, across
language and fatigue score.

Arithmetic Mean Test: To assess the accuracy of the randomized data collection
process, we examine the frequency of a specific action $a$ in the data and
compare it to the expected number of occurrences based on the logged
propensity scores. Our analysis reveals that the observed difference is not
statistically significant, suggesting that there are no errors in the
randomized data collection process.

Harmonic Mean Test: We verify the mean of the random variable in Equation 1
below is close to 2.

(1)
$\mathbb{E}_{a}\left[\dfrac{\mathbb{I}(a=a^{*})}{p_{a^{*}}}+\dfrac{\mathbb{I}(a\neq
a^{*})}{1-p_{a^{*}}}\right]\approx 2$

Note that the control variate test proposed by London and Joachims is not
directly applicable in our setting as it requires a fixed target policy, which
we are yet to learn (London and Joachims, 2022). Additionally, note that this
type of logging policy is devoid of either observed or unobserved confounding
by design (Jeunen and London, 2023).

Table 2. Type and description of some of the most important features used to represent contextual signals in our bandit setup. Attribute Type | Name | Description
---|---|---
User (Dynamic) | Current Interactions | Counters of hourly and daily interactions like engagement, time spent, and views.
Activity | Login counters like average inactivity last week, logins yesterday, etc.
Historical Interactions | Counters over the last 3, 5 and 7 day window.
Embeddings | Dot product between pre-computed user embedding and average of post embedding in the feed.
Fatigue Score | Described in section 3.3 – proposed by (Sagtani et al., 2023)
User (Static) | Platform Age | Number of days since user signed up on the platform.
Language | One-hot encoding of the user language.
Location | One-hot encoding of state, district, and city.
Content | Genre | A genre affinity score and the number of posts in the feed.
Distinct Genres | Taken as proxy for diversity, as the number of distinct genres in the feed.
Post Age | Average age of posts in the feed.
Advertisements | Previous Ad Slots | Ad-slots in the previous feed request.
Ad Gap | Number of posts between the last ad in the previous feed and the first ad in the current feed.
Average Ad Load | average number of ads per feed in last 3, 5 feed fetches
Total Ad Impressions | Number of ad impressions for this user in the current session.
IAB Category | Interactive Advertising Bureau (IAB) content taxonomy relating to the ad.
Clicks & Impressions | The user advertising impressions and clicks in several time windows.

###  4.2. Off-policy bandit formulation

####  4.2.1.  Designing the action space

Two natural choices arise when considering _actions_ in the ad-load balancing
problem:

Volume of advertisements. We can consider fixed ad positions in the feed, and
model the number of ads we wish to show in a given feed fetch: $0,1,2$. A
clear advantage of this approach is its simplicity – but it lacks the
expressiveness to explicitly tackle the position effects we observe in Figure
2.

Volume and position of advertisements. To overcome the limitation of the first
approach, we model an action as _both_ the number of ads as well as the
position of the ads in the feed fetch. This accounts for the heterogeneous
distribution in the expected rewards for different ad positions. One challenge
with this approach is the combinatorial explosion of the size of the action
space. In general, for a feed of length n and fixed number of i ads in the
feed for $i\leq n$, the total number of arms is given by the binomial
coefficient ${n\choose i}$. As such, the total number of possible combinations
for all possible ad loads and positions are given by $\sum_{i=0}^{n}{n\choose
i}=2^{n}$. With exponentially many actions, the propensity of each action
becomes $1/2^{n}$ when following a uniform logging policy. Although the reward
estimates from IPW estimators are still unbiased, their variance quickly
becomes problematic. To deal with this effectively, we include two further
considerations:

  1. (1)

The standard length of a feed fetch $n$ is $10$, which would imply an action
space of $1024$. We treat a feed of 10 length as two independent feeds of $5$
length each, allowing us to reduce the size of the action space by a factor
$2^{5}=32$ to $32$.

  2. (2)

We analyzed the effect of increasing the gap between consecutive ads on user
satisfaction metrics. When the gap between consecutive ads was $\leq 3$ or an
ad was placed at $1^{st}$ position, we observed significant satisfaction
losses, which are undesirable for the platform. Therefore, we removed such
combinations from the action space.

####  4.2.2. Designing the reward function

The ad-load balancing problem is inherently multi-stakeholder and multi-
objective. Indeed, _users_ and _advertisers_ have their own objectives which
can be conflicting. We define an explicit reward metric for both:

User Satisfaction is not straightforward to measure from implicit feedback.
The core hypothesis many platforms make, is that _retention_ reflects users’
satisfaction with the system. We model this with a binary label: “ _do users
come back to the system tomorrow?_ ” and call it _D1 Retention_. Because
retention is a long-term and delayed signal, adopting it directly as a reward
can be challenging. As such, we consider feed-level user (dis-)satisfaction
signals mentioned in table 1 to model a reward that serves as a proxy metric
for retention. Let $\delta_{1}$ be user’s _D1 Retention_ , $\phi{(x,a)}$ be
the user SAT metric, and $x_{i}$ be the value of $i^{th}$ (dis-)satisfaction
signal with weight $w_{i}$. We adopt linear scalarization to estimate D1
retention from these different signals using Equation 2, where $\rho$
indicates Pearson’s correlation:

(2)
$\begin{split}\phi^{\star}=\operatorname*{arg\,max}_{\phi}\rho(\delta_{1},\phi{(x,a)}),\text{
with }\phi{(x,a)}=\sum_{i}w_{i}\cdot x_{i}.\end{split}$

The objective in Equation 2 is maximised by learning a linear model via
gradient ascent on empirical logged data. The optimal weights obtained for
each signal $x_{i}$ in the user SAT metric $\phi{(x,a)}$ are provided in Table
1, along with corresponding signal descriptions. Notably, positive signals
hold positive weights, while negative signals carry negative weights in the
final user SAT reward. Finally, we also emphasize certain considerations to
keep in mind while designing the reward for abandonment signals below.

Discounting & Attribution of Abandonment Dissatisfaction Signal: Usually,
users scroll through feeds continuously until they either switch to a
different feed or exit the session. We define $rank_{i}$ as the user’s current
feed fetch count in a series of consecutive feed fetches and $rank_{d}$ is the
total number feeds scrolled consecutively where $rank_{i}<=rank_{d}$, then
user abandons the feed at $rank_{d}$. As users leave a sequence of feeds at
varying points, dissatisfaction from leaving the first feed is more pronounced
than leaving, say, the $10^{th}$ feed. This is because users have already
consumed around 50 posts by the $10^{th}$ feed. So, the abandonment cost
should be lower at higher feed depths. Additionally, some of the abandonment
cost at a particular feed depth may or may not be attributed to the previous
feed depths. If $\lambda$ is the final feed abandonment signal, we account for
both discounting and attribution as:

(3) $\displaystyle\lambda$ $\displaystyle=\text{Discounted
Signal}\cdot\text{Signal Attribution}$ (4)
$\displaystyle=\frac{1}{\log(1+rank_{d})}*\alpha^{rank_{d}-rank_{i}}$

where 0 ¡ $\alpha$ ¡= 1, is a hyper-parameter controlling the degree of
attribution. If $\alpha=1$, full cost is attributed to the previous feeds, and
if $\alpha\rightarrow 0^{+}$, almost no cost is attributed to the previous
feed fetches.

Similar to feed abandonment, we apply a discount to the session abandonment
signal depending on the amount of time the user has already spent in the
session.

Advertising objectives can be manifold but are typically focused on revenue.
Nevertheless, similar to true user satisfaction, advertising revenue is a
long-term metric that is not easily plugged in directly as a reward. As short-
term proxies, we adopt a scalarised version of advertising impressions, clicks
and installs that maximises the pearson correlation with revenue. Let $Rev$ be
_revenue_ , $\psi{(x,a)}$ be the ads-objective, and $x_{i}$ be the value of
$i^{th}$ ads objective signal with weight $w_{i}$. We adopt linear
scalarization to estimate revenue from these different signals using Equation
5, where $\rho$ indicates Pearson’s correlation coefficient:

(5)
$\begin{split}\psi^{\star}=\operatorname*{arg\,max}_{\psi}\rho(\text{Rev},\psi{(x,a)}),\text{
with }\psi{(x,a)}=\sum w_{i}*x_{i}.\end{split}$

Similar to user SAT optimization, Equation 5 is maximised by learning a linear
model via gradient ascent on empirical logged data. The optimal weights
obtained for each signal $x_{i}$ in the ads objective $\psi{(x,a)}$ are
provided in Table 1, along with corresponding signal descriptions.

Final reward Let $\phi^{\star}{(x,a)}$ and $\psi^{\star}{(x,a)}$ be the
optimal user SAT metric and advertising objective respectively obtained from
methods above, then the final reward is a weighted combination of both as
follows:

(6)
$\begin{split}R=\beta*\phi^{\star}{(x,a)}+(1-\beta)*\psi^{\star}{(x,a)},\\\
\text{with }\beta\in[0,1].\end{split}$

####  4.2.3. Designing a context representation

We use user, content and advertisement attributes as contextual signals. Some
of the features along with the description are listed in Table 2. As part of
the feature pre-processing we removed the features with high
multicollinearity. Figure 5 visualises a heatmap of correlation of important
features with our user SAT reward signals. Note, Like, Shares & favs
(download) are the different types of engagement signal users can do with a
post. Dot features highlighted in the correlation heatmap are the dot product
between the pre-trained embedding of users and post on a particular signal and
per view attributes are the counter attributes for a user/post in a specific
time window. For eg: $UserLike/View\\_1day$ mean the total number of likes /
total number of views of a user on the platform in 1 day window. From the
plot, we observe that these features have high correlation with individual
reward signals for engagements (e.g. 0.18 for “likes”) and hence utility of
including such features in our dataset.

Figure 6 illustrates the correlation between advertisement features and both
the advertising objective and the user dis-satisfaction signal. Alongside
traditional counter features (impressions/clicks on an advertisement in
various time windows) and IAB category features, real-time features such as
ad-slots displayed in the last feed fetch and the average ad-load in the
current session are important and their significance is highlighted by their
strong correlation with clicks. A high positive correlation between the number
of ads, representing an ad-heavy feed, leads to higher feed- and session-
abandonment, but also more advertising clicks. This makes the trade-off
inherent to our problem apparent.

Figure 5. Heatmap of Pearsons’ correlation coefficients between features and
satisfaction signals.

###  4.3. Off-policy learning and evaluation

The research literature has conventionally focused on so-called _on-policy_
bandit approaches, where a policy is deployed and allowed to learn and update
in real-time. Although the advantages of this approach are apparent — it
should be clear that it brings significant challenges. Indeed, not only does
it require significant engineering bandwidth to set up the proper
infrastructure, we essentially would have no way of properly vetting the ad
load balancing policy before deployment. For these reasons, _off-policy_
bandits are generally preferred in real-world applications (Chen et al., 2019;
Ma et al., 2020).

Off-policy learning is often called _counterfactual_ learning – as it aims to
optimise a policy for a counterfactual estimate of the reward that policy
would have collected. A _policy_ is a contextual probability distribution,
often obtain through a parametric model. We will denote such a parametric
policy with shorthand notation
$\pi_{\theta}(a|x)\equiv\mathsf{P}(A=a|X=x;\Pi=\pi_{\theta})$.

We wish to learn the parameters $\theta^{\star}$ that maximise the estimated
expected value we obtain under the policy $\pi_{\theta^{\star}}$ on logged
data $\mathcal{D}$:

(7)
$\theta^{\star}=\operatorname*{arg\,max}_{\theta\in\Theta}V(\pi_{\theta},\mathcal{D}).$

Several families of estimators exist for $V$.

##### The Direct Method (DM)

So-called _value_ -based methods leverage supervised learning methods for
reward estimation.111These are often referred to as Q-learning in the
reinforcement learning literature. In the direct method, the parameters
$\theta$ are used to learn a model for the reward an action yields, given a
context: $\widehat{r}(a|x)\approx\mathbb{E}[R|X=x,A=a]$. The reward model
$\widehat{r}(a|x)$ can then be used to estimate the policy value:

(8)
$\widehat{V}_{\text{DM}}(\pi_{\theta},\mathcal{D})=\sum\limits_{(x,a,r_{a},p_{a})\in\mathcal{D}}\sum\limits_{a^{\prime}\in
A}\pi_{\theta}(a^{\prime}|x)\cdot\widehat{r}(a^{\prime}|x).$

From Eq. 8, we can observe that the optimal policy for a given reward
regressor $\widehat{r}_{\theta}(a|x)$ is the deterministic policy that chooses
the action with the highest reward estimate:
$\operatorname*{arg\,max}_{a^{\prime}\in A}\widehat{r}(a^{\prime}|c)$. As this
foregoes the need of sampling from a policy, they are widely used in practice.
Then, the parameters ${\theta}$ are used for $\widehat{r}$, as $\pi$ reduces
to the simple decision rule laid out above. Although value-based methods
generally have low variance, they are biased estimators. Advances exist in the
research literature to improve on such methods, typically by adopting some
form of _pessimism_ in the reward model (Mykhaylov et al., 2019; Jeunen and
Goethals, 2021, 2023).

##### Inverse Propensity Weighting (IPW)

_Policy_ -based methods directly learn a parametric policy, foregoing the need
to learn an explicit reward model. Inverse Propensity or Weighting (IPW) is
the workhorse behind this line of work (Bottou et al., 2013). Using the logged
propensities $p_{a}$, we can obtain an unbiased estimator of the reward that a
new policy $\pi$ would have obtained on a logged dataset $\mathcal{D}$:

(9)
$\widehat{V}_{\text{IPW}}(\pi_{\theta},\mathcal{D})=\sum\limits_{(x,a,r_{a},p_{a})\in\mathcal{D}}r_{a}\cdot\frac{\pi_{\theta}(a|x)}{p_{a}}.$

Although it is easy to see that Equation 9 is unbiased, it typically leads to
excessive variance. Extensions of this estimator typically aim to handle that
directly: by capping (Ionides, 2008) or self-normalising (Swaminathan and
Joachims, 2015d; Joachims et al., 2018) the weights, or adding regularisation
terms to the objective (Maurer and Pontil, 2009; Swaminathan and Joachims,
2015b; Ma et al., 2019; Faury et al., 2020; Si et al., 2020; Jeunen et al.,
2020). Similarly to the value-based family, these extensions can be
interpreted as mathematical _pessimism_ (Jeunen and Goethals, 2023). Recent
work has shown that _gradient boosting_ techniques and models (such as
Gradient Boosted Decision Trees (GBDTs) (Prokhorenkova et al., 2018)) are
amenable to such policy learning objectives (London et al., 2023).

Figure 6. Heatmap of Pearson’s correlation coefficients between features and
dissatisfaction / advertising signals.

##### Doubly Robust (DR)

The value- and policy-based families both have their own advantages and
characteristics. Dudík et al. introduce an estimator that leverages _both_ a
reward model $\widehat{r}$ _and_ the logging propensities $p_{a}$: the Doubly
Robust estimator (Dudík et al., 2011). It derives its name from a desirable
property, in that it is unbiased if _either_ the logged propensities, or the
reward model are.

(10) $\begin{gathered}\widehat{V}_{\text{DR}}(\pi_{\theta},\mathcal{D})=\\\
\sum\limits_{(x,a,r_{a},p_{a})\in\mathcal{D}}\left((r_{a}-\widehat{r}(a|x))\cdot\frac{\pi_{\theta}(a|x)}{p_{a}}+\sum\limits_{a^{\prime}\in
A}\pi_{\theta}(a^{\prime}|x)\cdot\widehat{r}(a^{\prime}|x)\right)\end{gathered}$

DR extends DM with an IPW-term that weights the error of the reward regressor.
Extensions exist that learn $\widehat{r}$ to minimise DR’s variance
(Farajtabar et al., 2018), optimise the DM–IPS balance (Su et al., 2019), or
introduce further transformations that bound expected error (Su et al., 2020).
Other work has shown that DR can still be outperformed by either IPW or
standalone DM (Jeunen and Goethals, 2020). In other words, there is “ _no free
lunch_ ”.

##  5\. Experimentation

In order to empirically validate the effectiveness of our proposed framework
through experimentation, we would require stochastic logged data with user and
advertising context, advertising positions with associated propensity values,
as well as user feedback on both ads and non-ads content. To the best of our
knowledge and at the time of writing, no such datasets are publicly available.
Hence, we need to resort to proprietary datasets. We note that our proposed
framework is general, and makes few assumptions about the nature of the
problem setting. As a result, we believe that our introduced framework and
results can extend to other platforms with similar or different feed models
(Chuklin et al., 2015; Jeunen, 2023).

###  5.1. Policy Design

To achieve a balanced trade-off between user satisfaction and ads objectives,
we propose various policy designs, including both baseline and counterfactual-
based approaches.

####  5.1.1. Baseline Policies

We begin by defining a range of baseline policies, including heuristic-based
and learned strategies to jointly optimize user satisfaction (SAT) and ads
objectives.

  1. (1)

Optimizing User SAT: The first policy we investigate optimises only user
satisfaction by setting $\beta=1$ in equation 6. Optimizing such a policy
leads to no ads for every feed fetch, aligning with offline observations where
ad-free slots yield highest user SAT metrics (Figure 2).

  2. (2)

Optimizing Ads Objective: We solely optimize the ads objective by setting
$\beta=0$ in equation 6. While optimizing for the user SAT gives no ads at
all, this approach maximize the ads with minimal user SAT. Our experiments
consistently yield an ads position of “2 and 6”, in line with offline ad
reward patterns (Figure 2).

  3. (3)

Random Policy: We move from single-objective optimization to policies
considering both user SAT and ads objectives. We start with a random policy
which selects an arm from the action space using a uniform random
distribution.

  4. (4)

Static Policy: We define static policy as a function of offset and
$post\\_gap$ (post_gap is the number of non-ad posts between consecutive ads),
wherein offset is the position of the ad on the very first feed fetch by the
users after which ads are displayed with a fixed $post\\_gap$. For instance, a
static policy of $(3,5)$ positions the first ad at “3”, maintaining a
consistent gap of 5 non-ad posts.

  5. (5)

User Fatigue Based Policy: The baselines we have looked so far are either hard
coded heuristics w.r.t. advertising _load_ and _positions_ , or they optimize
for single objective. We leverage a method based on the fatigue score (learned
using GBDT model) (Sagtani et al., 2023) to optimize both the user SAT and
ads-objective. Let $\phi_{u}$ represents the user’s fatigue score, $\theta$
represents the default number of ads shown to users in a feed on the platform,
and $\theta_{u}$ represents the updated number of ads shown to the user. Then,
the fatigue score-based policy can be formulated as:

$\theta_{u}=\begin{cases}\theta+1,&\text{if }\phi_{u}<\alpha\\\
\theta,&\text{if }\alpha<\phi_{u}<\beta\\\ \theta-1,&\text{if
}\phi_{u}>\beta\\\ \end{cases}$

where $0<\alpha<\beta<1$ are the thresholds for low and high fatigue users
because of the ads respectively. Users with fatigue scores because of ads
below $\alpha$ experience an increased ad load, while scores above $\beta$
result in a reduced ad load. As this baseline optimises both user SAT and
advertising objectives in a personalised manner, it is a much stronger
baseline than (1)–(4). This is reflected in our empirical results.

####  5.1.2. Policies based on counterfactual estimators

In addition to the aforementioned baselines, we optimize policies
parameterised by Multi-Layer Perceptrons (MLPs) and Gradient-Boosted Decision
Trees (GBDTs) using the unbiased estimators (IPW and DR, see Section 4.3) from
logged data. We fine-tune the reward function from equation 6 across various
$\beta$ values. Additionally, alongside propensity-based methods, we train
MLPs and GBDTs to predict the reward function, known as the Direct Method.

Table 3. Online A/B: % change in user SAT and ads metrics w.r.t. control. All results are statistically significant (2 tailed t-test at p¡0.05 after Bonferroni correction) except for those marked by+. |  |  | SAT Metrics | Ads Metrics
---|---|---|---|---
Variant | $\beta$ | Objective | D1 Retention | Time spent | Views | Engagements | Video play | Impressions | Clicks | Revenue
variant-1 | 0.7 | DR | -0.01+ | -0.01+ | -0.1 | -0.24 | -0.07+ | 1.14 | 1.91 | 1.65
variant-2 | 0.8 | DR | 0.04+ | 0.14 | 0.02+ | -0.09+ | 0.19 | 0.79 | 2.05 | 1.45
variant-3 | 0.9 | DR | 0.08 | 0.22 | 0.15 | -0.02+ | 0.31 | 0.28 | 0.52 | 0.2

###  5.2. Offline Experiments

The Open Bandit Pipeline library (Saito et al., 2020) was used for training
and evaluating these policies. For hyperparameter tuning of the supervised
models, we performed a randomized grid search over various combinations and
selected the parameters that yielded the best performance on the validation
set. We report the optimal hyperparameters for our GBDT and MLP models in the
supplementary material.

Figure 7 illustrates the percentage loss in Satisfaction (SAT) and ads
objectives for a particular policy compared to the optimal policy described
under section 5.1.1 for each objective in isolation. The losses are calibrated
on a scale of 0-100 for ads and 100-0 for no ads. The _offset_ of the static
policy are highlighted in the figure and have a “post gap”$=5$. From the plot,
we observe that the baseline policies exhibit higher SAT and ads loss compared
to the counterfactual policies, indicating their Pareto inefficiency. Among
the baselines, the fatigue score-based policy performs best, exhibiting the
lowest loss in both SAT and ads reward. This result highlights the potential
of personalization in attaining better outcomes over static policies while
simultaneously optimizing both objectives.

Among the counterfactual based policies, by varying the $\beta$ value (from
equation 6) from $0.7$ to $0.9$ we observe a decrease in user SAT loss and an
increase in ads objective loss. This suggests that $\beta$ serves as a trade-
off parameter between SAT and ads objectives, with all points lying on the
same Pareto front. For $\beta=0.8$, both GBDT and MLP models exhibit similar
losses in both SAT and ads objectives. Additionally, we observed that policies
trained with the DM objective were Pareto inefficient compared to policies
trained with the IPW and DR objectives. The convergence of IPW and DR
indicates the reliability of our propensity scores in estimating rewards.

Figure 7. Offline evaluation, comparing % loss in satisfaction and advertising
objectives w.r.t. baseline policies.

###  5.3. Deployment & Online A/B Experiment

Based on the offline results, we conducted A/B tests for three policies as
outlined in Table 3. Online experiments were conducted over a span of two
weeks, involving approximately 5 million daily active users. At the start of
the experiment, a uniform random policy was applied to 1% of randomly selected
active users in the variant, with their data logged to retrain the offline
learned policies retraining. For the remaining users, the learned policies
were deployed. To gradually transition to the learned policies for all users,
the percentage of users exposed to the random policy was progressively reduced
over the course of several days. The re-trained model was stored in a cloud
storage bucket, assigned an incremented version, and deployment in service
that loaded the updated model. The learned policy models were deployed in a
Kubernetes cluster with each pod having around 64 vCPUs, 240GB of RAM and
NVIDIA T4 GPUs with horizontal auto-scaling enabled based on the request rate
& cpu utilization of pod. The online p99 inference latency was approximately
25 milliseconds during peak traffic.

All the variants employed GBDT models to parameterise the learned policy. All
the variant policies used GBDTs to parameterise the learned policy, and the
doubly robust estimator as their objective. The control group was shown a
personalized policy that only considers the “fatigue score” to increase or
lower the ad-load (Fatigue baseline in Figure 7 (Sagtani et al., 2023)). We
tracked a number of user SAT and revenue metrics including Retention, Time
spent, video plays, ads impressions, ads clicks.

variant-1, with $\beta=0.7$, exhibited negative satisfaction metrics but
demonstrated a high ads objective, indicating a trade-off that favored ads and
was not suitable for the platform. In contrast, both variant-2 and variant-3
showed positive SAT and ads objectives, suggesting that optimizing for
multiple objectives based on context enabled us to capture user heterogeneity
and achieve gains in all objectives without adversely affecting others. When
comparing variant-2 and variant-3, we observed that increasing the $\beta$
value from 0.8 to 0.9 resulted in higher user satisfaction but a lower ads
objective.

The analysis of variant-2 provides valuable insights into the effectiveness of
the policy. By examining the distribution of ad-slots based on ad-position and
user features, we gained a deeper understanding of its performance. In terms
of feed depth, we observed that for the first feed, the policy shifted nearly
half of the ads to the $4^{th}$ position, while distributing the remaining ads
between positions “3” and “2”. This adjustment resulted in a reduced ad-load
from “3” to “4” for most cases and ultimately led to an improvement in user
satisfaction (SAT). For the next 3-4 feeds, the ad-load increased compensating
for the revenue loss in the first feed.

Another interesting finding emerged when analyzing the policy’s behavior
across consecutive feeds. It exhibited an alternating pattern of high and low
ad-loads. For instance, if the user had no ads in the last feed, the policy
predominantly displayed first ad at $2^{nd}$ position. Conversely, if the ads
count in the last feed were 2, the ads were primarily shown at positions “5”,
“6” or no ads at all. However, when there was only 1 ad in the last feed, the
policy displayed ads of various positions, indicating a mixed approach.

Additionally, we examined the relationship between ad display and fatigue
score. Notably, as the fatigue score increased, the policy reduced the
frequency of ad displays and shifted towards lower ad-loads. Conversely, for
users with very high fatigue scores ($\geq 0.85$), the policy displayed higher
ad-loads. Further analysis revealed that users with high fatigue scores tended
to have a higher churn rate, meaning they were more likely to discontinue
using the platform. As a result, the policy optimized the ads objective by
increasing ad exposure to these users, as their SAT improvement was minimal.

Taking into account the insights gained from the A/B test and the analysis of
variant-2, the policy was deployed in production serving 100% traffic cross
180 million monthly active users.

##  6\. Discussion & Future Work

In conclusion, we have presented the “ad-load balancing” problem, emphasizing
the trade-off between user satisfaction and ads objectives, as well as user-
level heterogeneity. Through the use of an off-policy learning framework and
unbiased estimators, we have successfully learned effective policies to tackle
this challenge. Our approach has resulted in improvements in both user
satisfaction and ads revenue metrics for the platform. While linear
scalarization helps decide the trade-off between user satisfaction and ads-
objectives, we envision future extensions to research and include more
sophisticated functions to have more fine grained control over these
objectives.

## References

  * (1)
  * Abdollahpouri et al. (2020) Himan Abdollahpouri, Gediminas Adomavicius, Robin Burke, Ido Guy, Dietmar Jannach, Toshihiro Kamishima, Jan Krasnodebski, and Luiz Pizzato. 2020.  Multistakeholder recommendation: Survey and research directions.  _User Modeling and User-Adapted Interaction_ 30, 1 (01 Mar 2020), 127–158.  https://doi.org/10.1007/s11257-019-09256-1
  * Abrams and Vee (2007) Zoë Abrams and Erik Vee. 2007.  Personalized Ad Delivery When Ads Fatigue: An Approximation Algorithm. In _Internet and Network Economics_ , Xiaotie Deng and Fan Chung Graham (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 535–540.
  * Bagherjeiran et al. (2022) Abraham Bagherjeiran, Nemanja Djuric, Mihajlo Grbovic, Kuang-Chih Lee, Kun Liu, Wei Liu, Linsey Pang, Vladan Radosavljevic, Suju Rajan, and Kexin Xie. 2022.  AdKDD 2022. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ _(KDD ’22)_. ACM, 4852–4853.  https://doi.org/10.1145/3534678.3542920
  * Bottou et al. (2013) Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X. Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. 2013.  Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising.  _Journal of Machine Learning Research_ 14, 101 (2013), 3207–3260.  http://jmlr.org/papers/v14/bottou13a.html
  * Busa-Fekete et al. (2017) Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. 2017.  Multi-objective Bandits: Optimizing the Generalized Gini Index. In _Proceedings of the 34th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, 625–634.  https://proceedings.mlr.press/v70/busa-fekete17a.html
  * Cai et al. (2017) Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, and Defeng Guo. 2017.  Real-Time Bidding by Reinforcement Learning in Display Advertising. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ _(WSDM ’17)_. ACM, 661–670.  https://doi.org/10.1145/3018661.3018702
  * Chen et al. (2019) Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H. Chi. 2019.  Top-K Off-Policy Correction for a REINFORCE Recommender System. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ _(WSDM ’19)_. ACM, 456–464.  https://doi.org/10.1145/3289600.3290999
  * Chuklin et al. (2015) Aleksandr Chuklin, Ilya Markov, and Maarten de Rijke. 2015.  _Click Models for Web Search_.  Morgan & Claypool.  https://doi.org/10.2200/S00654ED1V01Y201507ICR043
  * Dudík et al. (2011) Miroslav Dudík, John Langford, and Lihong Li. 2011.  Doubly Robust Policy Evaluation and Learning. In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ _(ICML’11)_. Omnipress, 1097–1104.
  * Farajtabar et al. (2018) Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. 2018.  More Robust Doubly Robust Off-policy Evaluation. In _Proceedings of the 35th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer Dy and Andreas Krause (Eds.). PMLR, 1447–1456.  https://proceedings.mlr.press/v80/farajtabar18a.html
  * Faury et al. (2020) Louis Faury, Ugo Tanielian, Flavian Vasile, Elena Smirnova, and Elvis Dohmatob. 2020.  Distributionally Robust Counterfactual Risk Minimization. In _Proc. of the 34th AAAI Conference on Artificial Intelligence_ _(AAAI’20)_. AAAI Press.
  * He et al. (2014) Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, and Joaquin Quiñonero Candela. 2014.  Practical Lessons from Predicting Clicks on Ads at Facebook. In _Proceedings of the Eighth International Workshop on Data Mining for Online Advertising_ _(ADKDD’14)_. ACM, 1–9.  https://doi.org/10.1145/2648584.2648589
  * Ionides (2008) Edward L. Ionides. 2008.  Truncated Importance Sampling.  _Journal of Computational and Graphical Statistics_ 17, 2 (2008), 295–311.
  * Jeunen (2023) Olivier Jeunen. 2023.  A Probabilistic Position Bias Model for Short-Video Recommendation Feeds. In _Proceedings of the 17th ACM Conference on Recommender Systems_ _(RecSys ’23)_. ACM, 675–681.  https://doi.org/10.1145/3604915.3608777
  * Jeunen and Goethals (2020) Olivier Jeunen and Bart Goethals. 2020.  An Empirical Evaluation of Doubly Robust Learning for Recommendation. In _Proc. of the ACM RecSys Workshop on Bandit Learning from User Interactions_ _(REVEAL ’20)_.
  * Jeunen and Goethals (2021) Olivier Jeunen and Bart Goethals. 2021.  Pessimistic Reward Models for Off-Policy Learning in Recommendation. In _Proceedings of the 15th ACM Conference on Recommender Systems_ _(RecSys ’21)_. ACM, 63–74.  https://doi.org/10.1145/3460231.3474247
  * Jeunen and Goethals (2023) Olivier Jeunen and Bart Goethals. 2023.  Pessimistic Decision-Making for Recommender Systems.  _ACM Trans. Recomm. Syst._ 1, 1, Article 4 (feb 2023), 27 pages.  https://doi.org/10.1145/3568029
  * Jeunen et al. (2022a) Olivier Jeunen, Thorsten Joachims, Harrie Oosterhuis, Yuta Saito, and Flavian Vasile. 2022a.  CONSEQUENCES — Causality, Counterfactuals and Sequential Decision-Making for Recommender Systems. In _Proceedings of the 16th ACM Conference on Recommender Systems_ _(RecSys ’22)_. ACM, 654–657.  https://doi.org/10.1145/3523227.3547409
  * Jeunen and London (2023) Olivier Jeunen and Ben London. 2023.  Offline Recommender System Evaluation under Unobserved Confounding. In _RecSys 2023 Workshop: CONSEQUENCES – Causality, Counterfactuals and Sequential Decision-Making_.  arXiv:2309.04222
  * Jeunen et al. (2022b) Olivier Jeunen, Sean Murphy, and Ben Allison. 2022b.  Learning to Bid with AuctionGym. In _Proceedings of the Workshop on Knowledge Discovery and Data Mining for Online Advertising_ _(ADKDD ’22)_.
  * Jeunen et al. (2023a) Olivier Jeunen, Sean Murphy, and Ben Allison. 2023a.  Off-Policy Learning-to-Bid with AuctionGym. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ _(KDD ’23)_. ACM, 4219–4228.  https://doi.org/10.1145/3580305.3599877
  * Jeunen et al. (2020) Olivier Jeunen, David Rohde, Flavian Vasile, and Martin Bompaire. 2020.  Joint Policy-Value Learning for Recommendation. In _Proc. of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ _(KDD ’20)_. ACM, 1223–1233.
  * Jeunen et al. (2023b) Olivier Jeunen, Lampros Stavrogiannis, Amin Sayedi, and Ben Allison. 2023b.  A Probabilistic Framework for Learning Auction Mechanisms via Gradient Descent. In _Proceedings of the Workshop on Artificial Intelligence for Online Advertising_ _(AI4WebAds ’23)_.
  * Joachims et al. (2018) Thorsten Joachims, Adith Swaminathan, and Maarten de Rijke. 2018.  Deep Learning with Logged Bandit Feedback. In _Proc. of the 6th International Conference on Learning Representations_ _(ICLR ’18)_.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020.  Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.  arXiv:2005.01643 [cs.LG]
  * Li et al. (2015) Lihong Li, Shunbao Chen, Jim Kleban, and Ankur Gupta. 2015.  Counterfactual estimation and optimization of click metrics in search engines: A case study. In _Proceedings of the 24th International Conference on World Wide Web_. 929–934.
  * Liu et al. (2021) Xiangyu Liu, Chuan Yu, Zhilin Zhang, Zhenzhe Zheng, Yu Rong, Hongtao Lv, Da Huo, Yiqing Wang, Dagui Chen, Jian Xu, Fan Wu, Guihai Chen, and Xiaoqiang Zhu. 2021.  Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ _(KDD ’21)_. ACM, 3354–3364.  https://doi.org/10.1145/3447548.3467103
  * London and Joachims (2022) Ben London and Thorsten Joachims. 2022.  Control variate diagnostics for detecting problems in logged bandit feedback. In _RecSys 2022 Workshop: CONSEQUENCES – Causality, Counterfactuals and Sequential Decision-Making_.
  * London et al. (2023) Ben London, Levi Lu, Ted Sandler, and Thorsten Joachims. 2023.  Boosted Off-Policy Learning. In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 206)_ , Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (Eds.). PMLR, 5614–5640.  https://proceedings.mlr.press/v206/london23a.html
  * Ma et al. (2020) Jiaqi Ma, Zhe Zhao, Xinyang Yi, Ji Yang, Minmin Chen, Jiaxi Tang, Lichan Hong, and Ed H. Chi. 2020.  Off-Policy Learning in Two-Stage Recommender Systems. In _Proceedings of The Web Conference 2020_ _(WWW ’20)_. ACM, 463–473.  https://doi.org/10.1145/3366423.3380130
  * Ma et al. (2019) Yifei Ma, Yu-Xiang Wang, and Balakrishnan Narayanaswamy. 2019.  Imitation-Regularized Offline Learning. In _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 89)_. PMLR, 2956–2965.  https://proceedings.mlr.press/v89/ma19b.html
  * Maurer and Pontil (2009) Andreas Maurer and Massimiliano Pontil. 2009.  Empirical Bernstein Bounds and Sample Variance Penalization.  _Stat._ 1050 (2009), 21.
  * McMahan et al. (2013) H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, and Jeremy Kubica. 2013.  Ad Click Prediction: A View from the Trenches. In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’13)_. ACM, 1222–1230.  https://doi.org/10.1145/2487575.2488200
  * Mehrotra et al. (2020) Rishabh Mehrotra, Niannan Xue, and Mounia Lalmas. 2020.  Bandit based optimization of multiple objectives on a music streaming platform. In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_. 3224–3233.
  * Mykhaylov et al. (2019) Dmytro Mykhaylov, David Rohde, Flavian Vasile, Martin Bompaire, and Olivier Jeunen. 2019.  Three Methods for Training on Bandit Feedback. In _Proc. of the NeurIPS Workshop on Causality and Machine Learning_ _(CausalML ’19)_.
  * Owen (2013) Art B. Owen. 2013.  _Monte Carlo theory, methods and examples_.
  * Pearl (2009) Judea Pearl. 2009.  _Causality_.  Cambridge university press.
  * Prokhorenkova et al. (2018) Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. 2018.  CatBoost: unbiased boosting with categorical features. In _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc.  https://proceedings.neurips.cc/paper_files/paper/2018/file/14491b756b3a51daac41c24863285549-Paper.pdf
  * Resnick and Albert (2014) Marc Resnick and William Albert. 2014.  The Impact of Advertising Location and User Task on the Emergence of Banner Ad Blindness: An Eye-Tracking Study.  _International Journal of Human–Computer Interaction_ 30, 3 (2014), 206–219.  https://doi.org/10.1080/10447318.2013.847762
  * Sagtani et al. (2023) Hitesh Sagtani, Madan Gopal Jhanwar, Akshat Gupta, and Rishabh Mehrotra. 2023.  Quantifying and Leveraging User Fatigue for Interventions in Recommender Systems. In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Saito et al. (2020) Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita. 2020.  Open bandit dataset and pipeline: Towards realistic and reproducible off-policy evaluation.  _arXiv preprint arXiv:2008.07146_ (2020).
  * Saito and Joachims (2022) Yuta Saito and Thorsten Joachims. 2022.  Counterfactual Evaluation and Learning for Interactive Systems: Foundations, Implementations, and Recent Advances. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ _(KDD ’22)_. ACM, 4824–4825.  https://doi.org/10.1145/3534678.3542601
  * Si et al. (2020) Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. 2020.  Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 119)_ , Hal Daumé III and Aarti Singh (Eds.). PMLR, 8884–8894.  https://proceedings.mlr.press/v119/si20a.html
  * Su et al. (2020) Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudik. 2020.  Doubly robust off-policy evaluation with shrinkage. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 119)_ , Hal Daumé III and Aarti Singh (Eds.). PMLR, 9167–9176.  https://proceedings.mlr.press/v119/su20a.html
  * Su et al. (2019) Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. 2019.  Cab: Continuous adaptive blending for policy evaluation and learning. In _International Conference on Machine Learning_. PMLR, 6005–6014.
  * Swaminathan and Joachims (2015a) Adith Swaminathan and Thorsten Joachims. 2015a.  Batch learning from logged bandit feedback through counterfactual risk minimization.  _The Journal of Machine Learning Research_ 16, 1 (2015), 1731–1755.
  * Swaminathan and Joachims (2015b) Adith Swaminathan and Thorsten Joachims. 2015b.  Counterfactual Risk Minimization: Learning from Logged Bandit Feedback. In _Proc. of the 32nd International Conference on International Conference on Machine Learning_ _(ICML’15)_. JMLR.org, 814–823.
  * Swaminathan and Joachims (2015c) Adith Swaminathan and Thorsten Joachims. 2015c.  The self-normalized estimator for counterfactual learning.  _advances in neural information processing systems_ 28 (2015).
  * Swaminathan and Joachims (2015d) Adith Swaminathan and Thorsten Joachims. 2015d.  The Self-Normalized Estimator for Counterfactual Learning. In _Advances in Neural Information Processing Systems_. 3231–3239.
  * van den Akker et al. (2023) Bram van den Akker, Olivier Jeunen, Ying Li, Ben London, Zahra Nazari, and Devesh Parekh. 2023.  Practical Bandits: An Industry Perspective.  arXiv:2302.01223 [cs.LG]
  * Zheng and Wang (2022) Yong Zheng and David (Xuejun) Wang. 2022.  A survey of recommender systems with multi-objective optimization.  _Neurocomputing_ 474 (2022), 141–153.  https://doi.org/10.1016/j.neucom.2021.11.041


[type=author, orcid=0000-0002-7572-1705]

[type=author, orcid=0000-0002-2304-7106]

[type=author, orcid=0000-0003-4659-6009]

[1]

[type=author, orcid=0000-0002-4577-3168]

[1]

1]organization=Department of Information and Communication Engineering, Daegu
Gyeongbuk Institute of Science & Technology, city=Daegu, postcode=42988,
country=Korea

2]organization=Division of Pediatric Cardiology, Department of Pediatrics,
Yonsei University College of Medicine, city=Seoul, postcode=03722,
country=Korea

[1]Corresponding author

# Explainable Deep Learning Algorithm for Distinguishing Incomplete Kawasaki
Disease by Coronary Artery Lesions on Echocardiographic Imaging

Haeyun Lee  Yongsoon Eun  Jae Youn Hwang<EMAIL_ADDRESS>Lucy Youngmin Eun
<EMAIL_ADDRESS>[  [

###### Abstract

Background and Objective: Incomplete Kawasaki disease (KD) has often been
misdiagnosed due to a lack of the clinical manifestations of classic KD.
However, it is associated with a markedly higher prevalence of coronary artery
lesions. Identifying coronary artery lesions by echocardiography is important
for the timely diagnosis of and favorable outcomes in KD. Moreover, similar to
KD, coronavirus disease 2019, currently causing a worldwide pandemic, also
manifests with fever; therefore, it is crucial at this moment that KD should
be distinguished clearly among the febrile diseases in children. In this
study, we aimed to validate a deep learning algorithm for classification of KD
and other acute febrile diseases.

Methods: We obtained coronary artery images by echocardiography of children (n
= 88 for KD; n = 65 for pneumonia). We trained six deep learning networks
(VGG19, Xception, ResNet50, ResNext50, SE-ResNet50, and SE-ResNext50) using
the collected data.

Results: SE-ResNext50 showed the best performance in terms of accuracy,
specificity, and precision in the classification. SE-ResNext50 offered a
precision of 76.35%, a sensitivity of 82.64%, and a specificity of 58.12%.

Conclusions: The results of our study suggested that deep learning algorithms
have similar performance to an experienced cardiologist in detecting coronary
artery lesions to facilitate the diagnosis of KD.

###### keywords:

Deep Learning Coronary Artery Lesion Kawasaki Disease

##  1 Introduction

Kawasaki disease (KD) is the most common acquired heart disease in childhood.
It was first described by Dr. Kawasaki in 1967 Kuo (2017). KD mostly occurs in
children aged less than 5 years and has a high prevalence in countries of
Northeast Asia, particularly Japan, South Korea, and Taiwan Makino et al.
(2015); Kim et al. (2017).

The main symptoms of KD are unexplained high fever, diffuse erythematous
polymorphous rash, bilateral conjunctival injection, cervical lymphadenopathy,
oral mucosal changes, and extremity changes, sometimes with perineal
desquamation, or reactivation of the bacillus Calmette–Guérin injection site
McCrindle et al. (2017); Dietz et al. (2017); Newburger et al. (2016); Singh
et al. (2018). While the widely used diagnostic criteria for KD are useful,
incomplete KD in infants or children aged 10 years or older can often be
problematic, causing misdiagnosis due to a lack of manifestation of the full
clinical criteria of classic KD. Nevertheless, this disease has a much higher
prevalence of coronary artery lesions McCrindle et al. (2017); Singh et al.
(2018).

Given the difficulty in diagnosing incomplete or “atypical” KD by clinical
features alone, identifying coronary artery findings by echocardiography,
along with evaluation of various biomarkers by blood tests, becomes more
significant for ensuring an appropriate diagnosis McCrindle et al. (2017).
Even though the choice of treatment with a high dose of intravenous
immunoglobulin infusion decreases the risk of coronary artery complications,
about 5% of treated children and 15–25% of untreated children have a risk of
coronary artery aneurysms or ectasia. Certainly, one of the fatal
complications of untreated KD is coronary artery aneurysm. Accordingly, the
role of echocardiography in recognizing coronary artery lesions is substantial
to ensure timely diagnosis and favorable outcome Na et al. (2019).

For the proper diagnosis of incomplete KD, the expert pediatric cardiologists
need to perform echocardiography to investigate the patient’s coronary
arteries. The most important therapeutic goal of KD is the prevention of
coronary artery aneurysm formation. When an aneurysm is noticed, it is
critical to prevent development of a giant aneurysm or formation of a thrombus
Rowley et al. (1988).

Unfortunately, without an experienced pediatric cardiologist and a KD expert,
it is challenging to diagnose incomplete KD because the fever patterns of many
acute febrile diseases in children appear similar to KD, particularly the
initial high grade of fever. In 2020, reports of severely ill pediatric cases
have shown that KD and coronavirus disease 2019 (COVID-19) presented similar
symptoms Jones et al. (2020); Viner and Whittaker (2020). Moreover, the
incidence of KD suddenly increased in Europe and the USA during the COVID-19
pandemic. In addition, KD-like multi-systemic inflammatory syndrome in
children affected many children in Europe and in the USA. This is of
particular concern, as it can result in missed or delayed KD diagnosis and
treatment Guan et al. (2020).

Several studies on computer-aided diagnosis based on deep learning algorithms
have shown good performance. Deep learning-based approaches for the diagnosis
of cancer or lesions have been shown to perform well and have already
surpassed human doctors in some categories Esteva et al. (2017). Additionally,
deep learning algorithms have shown better performance in the medical vision
field than conventional methods Liu et al. (2019). Several deep learning
algorithms have been proposed to diagnose various diseases, such as breast
cancer Lee et al. (2020), liver cancer Wu et al. (2014), and thyroid nodules
Ma et al. (2017) on ultrasound images. These medical deep learning algorithms
have been proposed for computer-aided enhancement of diagnostic performance.
However, deep learning algorithms have not yet been applied to KD diagnosis.

The purpose of this study was to assess whether explainable deep learning
algorithms could be used to identify coronary artery lesions on
echocardiographic images for the timely diagnosis of KD. We also evaluated the
performance of these algorithms in distinguishing KD from another acute
febrile disease, pneumonia.

##  2 Methods

###  2.1 Data Acquisition

To investigate whether it would be possible to distinguish between KD and
another similar acute febrile disease, we selected pneumonia as an alternative
representative acute febrile disease. Pneumonia is one of the most common
febrile diseases in children.

For this study, echocardiographic imaging data from January 2016 to August
2019 were acquired from Yonsei University Gangnam Severance Hospital. Giant
coronary aneurysm cases were excluded from this study. Echocardiographic
images of 88 children with incomplete KD and 59 children with pneumonia (147
in total) were acquired and labeled as KD and non-KD by an experienced
cardiologist. 2D echocardiographic coronary artery short axis view images were
obtained for the appropriate diagnosis when the children initially presented
with high grade fever. We cropped the echocardiographic images to $512\times
512$ pixels.

Figure 1: Echocardiography analysis process using deep learning algorithms in
this study.

###  2.2 Deep Learning Algorithm

In this study, to distinguish incomplete KD from non-KD using
echocardiographic images, we applied six deep learning architectures: VGG-19
Simonyan and Zisserman (2014), Xception Chollet (2017), ResNet-50 He et al.
(2016), ResNext-50 Xie et al. (2017), SE-ResNet-50, and SE-ResNext-50 Hu et
al. (2018).

VGG Simonyan and Zisserman (2014) is the most basic network with a simple
structure for classification and good performance. Therefore, it is still
widely used as a comparison architecture. Xception Chollet (2017) is a linear
stack of depth-wise separable convolutions with residual connections and shows
higher performance than the baseline Inception architecture Szegedy et al.
(2016). ResNet He et al. (2016) is a deep learning network which is stacked
more deeply using a skip connection and is being used in various fields.
ResNext Xie et al. (2017) has shown higher performance while reducing the
computation cost compared to the existing ResNet by using a group convolution.
SE-ResNet and SE-ResNext Hu et al. (2018) are networks in which squeeze-and-
excitation blocks are added to ResNet and ResNext, respectively Russakovsky et
al. (2015).

Since the data in our study were limited to training the models, only networks
with 50 or fewer convolution layers were used in this experiment. Thus, we
used VGG-19, Xception, ResNet-50, ResNext-50, SE-ResNet50, and SE-ResNext50 in
this experiment. We then evaluated the capability of the deep learning
algorithms to distinguish between KD and non-KD.

For the training, we used a stochastic optimization method (ADAM) Kingma and
Ba (2014) with parameter $\beta_{1}=0.9$, $\beta_{2}=0.999$, and
$\epsilon=10^{-8}$. The initial learning rate was $1e^{-3}$, and it decreased
by 1/10 every 30 epochs. We trained each network for a total of 120 epochs.
Training batch sizes consisted of 32 patches. We used a binary cross-entropy
loss function to train each network. We used the pretrained weights of each
network on ImageNet to achieve better performance Russakovsky et al. (2015).

The deep learning framework used for training and testing the deep learning
algorithms was PyTorch Paszke et al. (2017). We trained and tested all
networks using a 2-GHz Intel Xeon E5-2620 processor and an NVIDIA TITAN RTX
graphics card (24 GB).

Figure 2: The precision-recall curves of each deep learning algorithm for KD.
Areas under the precision-recall curve of VGG19, Xception, ResNet50,
ResNext50, SE-ResNet50, and SE-ResNext50 were 0.643, 0.752, 0.822, 0.830,
0.853, and 0.864, respectively.

###  2.3 Class Activation Map

To explain deep learning algorithms, we used the class activation map (CAM)
Zhou et al. (2016). Previously, it was not possible to know which salient
parts of a medical image would be highlighted by a deep learning algorithm for
classification. The CAM has been proposed to solve this issue and to be able
to explain deep learning algorithms. Most deep learning algorithms use a fully
connected layer to classify the values obtained by applying a global average
pooling (GAP) to the feature maps from the last convolution layer. A linear
transform with a class number of filters is then applied to the weight
obtained through GAP.

Here, to obtain the CAM, the weight of the linear transform for each class was
multiplied by the feature map obtained from the last convolutional layer. The
CAM at class $c$, $M_{c}(x,y)$, can be calculated as follows:

$\displaystyle M_{c}(x,y)$ $\displaystyle=\sum_{k}w_{k}^{c}F_{k}$ (1)
$\displaystyle=\sum_{k}w_{k}^{c}\sum_{x,y}f_{k}(x,y)$
$\displaystyle=\sum_{x,y}\sum_{k}w_{k}^{c}f_{k}(x,y)$

where $f_{k}(x,y)$ is a feature map from the last convolution layer for a unit
k, $w_{k}^{c}$ is the weight of linear transformation corresponding to class
$c$ for the unit $k$, and $x$ and $y$ are the spatial information of $f_{k}$
and $M_{c}$, respectively. The class activation map, $M_{c}(x,y)$, indicates a
class-specific highlight map at a spatial grid $(x,y)$. Therefore, through the
CAM, it is possible to understand which parts of the image are considered when
the deep learning algorithm proceeds with classification. Hence, the CAM is an
excellent tool for analyzing medical image deep learning algorithms Ma et al.
(2020); Qiao et al. (2019), as in this study.

Table 1: Diagnostic performance of deep learning algorithms. The best performance is in bold, and the second best performance is in underlined. Networks | VGG19 | Xception | ResNet50 | ResNext50 | SE-ResNet50 | SE-ResNext50
---|---|---|---|---|---|---
Accuracy | 64.33 | 67.50 | 67.14 | 71.60 | 70.42 | 72.88
F1 score | 70.72 | 74.74 | 71.68 | 77.17 | 75.56 | 78.26
Sensitivity | 72.64 | 80.70 | 70.69 | 77.13 | 77.64 | 82.64
Specificity | 51.33 | 47.67 | 61.67 | 57.67 | 59.67 | 58.12
Precision (PPV) | 73.20 | 70.78 | 73.99 | 75.10 | 74.61 | 76.35
NPV | 55.56 | 62.22 | 58.06 | 66.67 | 63.64 | 68.63

###  2.4 Ethics Statement

This study was approved by the Yonsei University College of Medicine
Institutional Review Board and the Research Ethics Committee of Severance
Hospital (study approval number: 2020-1127-001). All research was performed in
accordance with relevant guidelines and regulations. The requirement for
written informed consent was waived by the Institutional Review Board due to
the retrospective study design.

##  3 Results

Figure 3: Illustration of a class activation map of SE-ResNext50 for non-KD:
the first column shows the echocardiographic images of non-KD, the second
column shows the CAMs, and the third column shows the overlay of the
echocardiographic image and the CAM.

Since we conducted the experiments using 10-fold cross validation, there were
10 outcomes. Each subset had 137 or 138 echocardiographic images for training
and 16 or 15 echocardiographic images for testing. The test images in each
subset included 8 or 9 echocardiographic images labeled as KD and 6 or 7
echocardiographic images labeled as non-KD (pneumonia) by an echocardiographic
specialist. Table 1 shows the diagnostic performance of each network trained
with each subset for the test dataset. The accuracies of VGG19, Xception,
ResNet50, ResNext50, SE-ResNet50, and SE-ResNext50 were 64.33%, 67.50%,
58.58%, 71.60%, 63.72%, and 72.88% for the classification of KD and non-KD,
respectively. The F1 score of VGG19, Xception, ResNet50, ResNext50, SE-
ResNet50, and SE-ResNext50 were 70.72%, 74.74%, 71.68%, 77.17%, 75.56%, and
78.26% for the classification of KD and non-KD, respectively. In contrast, the
sensitivities of VGG19, Xception, ResNet50, ResNext50, SE-ResNet50, and SE-
ResNext50 were 72.64%, 80.70%, 82.22%, 77.13%, 87.64%, and 82.64%,
respectively. The specificities of VGG19, Xception, ResNet50, ResNext50, SE-
ResNet50, and SE-ResNext50 were 51.33%, 47.67%, 23.33%, 57.67%, 28.00%, and
58.12%, respectively. The precision (positive predictive value; PPV) of VGG19,
Xception, ResNet50, ResNext50, SE-ResNet50, and SE-ResNext50 were 73.20%,
70.78%, 62.36%, 75.10%, 65.18%, and 76.35%, respectively. The negative
predictive value (NPV) of VGG19, Xception, ResNet50, ResNext50, SE-ResNet50,
and SE-ResNext50 were 55.56%, 62.22%, 58.06%, 66.67%, 63.64%, and 68.63%,
respectively. In these results, SE-ResNext50 showed the best performance in
terms of accuracy, F1 score, sensivitivity, precision, and NPV for the
distinction of KD and non-KD. It identified 112 true-positive diagnoses among
153 images. Figure 2 shows the precision-recall curve of the deep learning
algorithms used for the classification between KD and pneumonia. The areas
under the precision-recall curve (AUPRC) of VGG19, Xception, ResNet50,
ResNext50, SE-ResNet50, and SE-ResNext50 were 0.643, 0.752, 0.822, 0.830,
0.853, and 0.864, respectively.

Figure 4: Illustration of a class activation map of SE-ResNext50 for KD: the
first column shows the echocardiographic images of KD, the second column shows
the CAMs, the third column shows the overlays of the echocardiographic images
and the CAM.

For non-KD, the echocardiographic images of pneumonia and its corresponding
CAM images are illustrated in Figure 3. These images were correctly identified
as non-KD by SE-ResNext50. The images in the first row represent the pneumonia
image correctly recognized as non-KD by SE-ResNext50, whereas the second row
shows the pneumonia image incorrectly classified as KD by SE-ResNext50.

For incomplete KD, the echocardiographic image of KD and its corresponding CAM
image are demonstrated in Figure 4. The images in the first row were correctly
identified as KD by SE-ResNext50, whereas the images in the second row were
incorrectly classified as non-KD by SE-ResNext50. The thicker red regions
indicate the parts of images focused on by the deep learning algorithm during
the process of classification as KD and non-KD.

##  4 Discussion

The goal of this study was to investigate the potential of explainable deep
learning algorithms to identify and differentiate KD from acute febrile
diseases. We therefore selected several well-known deep learning algorithms
(VGG19, Xception, ResNet50, ResNext50, SE-ResNet50, and SE-ResNext50) to
distinguish incomplete KD from other acute febrile diseases. We selected
pneumonia as a representative of other acute febrile diseases because it is
the most common febrile disease in children. KD and pneumonia show similar
fever patterns before the occurrence of respiratory symptoms in pneumonia.
Despite the small training dataset, the results in our study demonstrated that
the deep learning algorithms show excellent performance for the identification
of the KD. Nevertheless, as the performance of a deep learning algorithm
depends on the quantity of training data Sun et al. (2017); Rolnick et al.
(2017), the deep learning algorithm for KD diagnosis should be extended.

Figure 3 and Figure 4 show the parts of the echocardiographic images that are
considered important by the deep learning algorithm to distinguish between KD
and non-KD. These figures indicate that the explainable deep learning
algorithms identified KD by using the features of the coronary arteries. This
is comparable to how pediatric cardiologists diagnose and differentiate the
diseases. Clinical reports have mentioned that coronary artery imaging could
be key to the appropriate diagnosis of KD, particularly incomplete KD Kim et
al. (2017). Through this analysis, our results revealed that deep learning
algorithms can identify KD among KD and non-KD, as cardiologists do, which
suggests that deep learning algorithms could be applied in a clinical setting
to recognize incomplete KD among various acute febrile diseases in children.

Our experimental results showed the potential of explainable deep learning
algorithms to distinguish KD from acute febrile diseases. Among the tested
algorithms, SE-ResNext50 showed the highest accuracy, specificity, and
precision in the classification of KD and non-KD, whereas SE-ResNet50 showed
the highest sensitivity. However, as shown in the precision-recall-curves, SE-
ResNext50 showed the best performance among the algorithms in distinguishing
between KD and non-KD. In particular, SE-ResNext50 yielded a sensitivity of
82.64% and a specificity of 58.12%. This performance of SE-ResNext50 is
comparable to that of an experienced cardiologist (sensitivity of 85% and
specificity of 70%) Na et al. (2019).

Thus, these results indicate that explainable deep learning algorithms might
be used to diagnose KD at a general hospital without a KD expert. In Korea, an
experienced pediatric cardiologist is not always available at each hospital,
owing to a lack of human resources. Nevertheless, timely diagnosis of KD is
essential for proper treatment, to prevent poor outcomes of coronary artery
lesions.

In the global COVID-19 pandemic in particular, there is a risk that KD might
be misdiagnosed, as WHO stated that COVID-19 has a similar febrile clinical
presentation as KD Jones et al. (2020); Viner and Whittaker (2020). Therefore,
now more than ever, it is important to distinguish KD from other febrile
diseases in children; this may be possible by using an explainable deep
learning algorithm.

Previous studies have analyzed echocardiographic images using deep learning to
perform classification of myocardial disease Zhang et al. (2018), detect
hypertrophic cardiomyopathy, cardiac amyloid, and pulmonary arterial
hypertension Vidal et al. (2021), and evaluate chamber segmentation Leclerc et
al. (2019) and wall motion abnormalities Sanchez-Martinez et al. (2018); Omar
et al. (2018). However, there has been no study to date on diagnosis of
incomplete KD by echocardiographic images of coronary artery lesions using
deep learning, as we have done here. This study indicates that explainable
deep learning has potential to diagnose KD among acute febrile diseases. This
study had some limitations. First, we trained the deep learning algorithms
with a small amount of data. Second, the experiment was conducted using only
pneumonia as a non-KD acute febrile disease. To overcome the first and second
limitations, more data need to be collected on incomplete KD and other acute
febrile diseases, which would be considered as non-KD conditions. Training
algorithms using such data will provide a KD detection algorithm with higher
capability. Our work forms the basis for such future studies.

##  5 Conclusions

We have shown the feasibility of using an explainable deep learning approach
for detection of KD based on echocardiography images. The AUPRCs of the deep
learning algorithms, including VGG19, Xception, ResNet50, ResNext50, SE-
ResNet50, and SE-ResNext50, were found to be 0.643, 0.752, 0.822, 0.830,
0.853, and 0.864, respectively, for discrimination between KD and non-KD. In
particular, the SE-ResNext50 offered the best performance among the deep
learning algorithms with an accuracy of 72.88% and an AUPRC of 0.864. The
explainable deep learning algorithms highlighted salient features of coronary
arteries, similar to how an experienced pediatric cardiologist would examine
coronary artery regions for the detection of KD. Although the specificity of
deep learning algorithms was still lower than that of highly experienced
clinicians for the discrimination between incomplete KD and non-KD, the deep
learning algorithms used in this study were promising in terms of sensitivity
and precision. Therefore, deep learning algorithms may assist clinicians in
reducing the probability of misdiagnosing KD in clinical practice. The
abilities of deep learning algorithms should be further developed to be
comparable to the performance of highly experienced clinicians in order to
translate this approach to application in the clinic.

## Statements of ethical approval

The study was approved by the Ethics Committee of Severance Hospital. All the
participants provided their written informed consent to participate in this
study.

## Declaration of Competing Interest

There are no conflicts of interest to disclose for publication of this paper.

## Acknowledgements

This study was supported by a new faculty research seed money grant of Yonsei
University College of Medicine for 2020 (2020-32-0035).

## References

  * Kuo (2017) H.-C. Kuo,  Preventing coronary artery lesions in kawasaki disease,  Biomedical journal 40 (2017) 141–146.
  * Makino et al. (2015) N. Makino, Y. Nakamura, M. Yashiro, R. Ae, S. Tsuboi, Y. Aoyama, T. Kojo, R. Uehara, K. Kotani, H. Yanagawa,  Descriptive epidemiology of kawasaki disease in japan, 2011–2012: from the results of the 22nd nationwide survey,  Journal of epidemiology (2015) JE20140089.
  * Kim et al. (2017) G. B. Kim, S. Park, L. Y. Eun, J. W. Han, S. Y. Lee, K. L. Yoon, J. J. Yu, J.-W. Choi, K.-Y. Lee,  Epidemiology and clinical features of kawasaki disease in south korea, 2012–2014,  The Pediatric infectious disease journal 36 (2017) 482–485.
  * McCrindle et al. (2017) B. McCrindle, A. Rowley, J. Newburger, J. Burns, A. Bolger, M. Gewitz, A. Baker, M. Jackson, M. Takahashi, P. Shah, et al.,  American heart association rheumatic fever, endocarditis, and kawasaki disease committee of the council on cardiovascular disease in the young; council on cardiovascular and stroke nursing; council on cardiovascular surgery and anesthesia; and council on epidemiology and prevention. diagnosis, treatment, and long-term management of kawasaki disease: a scientific statement for health professionals from the american heart association,  Circulation 135 (2017) e927–e999.
  * Dietz et al. (2017) S. Dietz, D. Van Stijn, D. Burgner, M. Levin, I. Kuipers, B. Hutten, T. Kuijpers,  Dissecting kawasaki disease: a state-of-the-art review,  European journal of pediatrics 176 (2017) 995–1009.
  * Newburger et al. (2016) J. W. Newburger, M. Takahashi, J. C. Burns,  Kawasaki disease,  Journal of the American College of Cardiology 67 (2016) 1738–1749.
  * Singh et al. (2018) S. Singh, A. K. Jindal, R. K. Pilania,  Diagnosis of kawasaki disease,  International journal of rheumatic diseases 21 (2018) 36–44.
  * Na et al. (2019) J.-H. Na, S. Kim, L. Y. Eun,  Utilization of coronary artery to aorta for the early detection of kawasaki disease,  Pediatric cardiology 40 (2019) 461–467.
  * Rowley et al. (1988) A. H. Rowley, C. E. Duffy, S. T. Shulman,  Prevention of giant coronary artery aneurysms in kawasaki disease by intravenous gamma globulin therapy,  The Journal of pediatrics 113 (1988) 290–294.
  * Jones et al. (2020) V. G. Jones, M. Mills, D. Suarez, C. A. Hogan, D. Yeh, J. B. Segal, E. L. Nguyen, G. R. Barsh, S. Maskatia, R. Mathew,  Covid-19 and kawasaki disease: novel virus and novel case,  Hospital pediatrics 10 (2020) 537–540.
  * Viner and Whittaker (2020) R. M. Viner, E. Whittaker,  Kawasaki-like disease: emerging complication during the covid-19 pandemic,  The Lancet 395 (2020) 1741–1743.
  * Guan et al. (2020) W.-j. Guan, Z.-y. Ni, Y. Hu, W.-h. Liang, C.-q. Ou, J.-x. He, L. Liu, H. Shan, C.-l. Lei, D. S. Hui, et al.,  Clinical characteristics of coronavirus disease 2019 in china,  New England journal of medicine 382 (2020) 1708–1720.
  * Esteva et al. (2017) A. Esteva, B. Kuprel, R. A. Novoa, J. Ko, S. M. Swetter, H. M. Blau, S. Thrun,  Dermatologist-level classification of skin cancer with deep neural networks,  nature 542 (2017) 115–118.
  * Liu et al. (2019) S. Liu, Y. Wang, X. Yang, B. Lei, L. Liu, S. X. Li, D. Ni, T. Wang,  Deep learning in medical ultrasound analysis: a review,  Engineering 5 (2019) 261–275.
  * Lee et al. (2020) H. Lee, J. Park, J. Y. Hwang,  Channel attention module with multiscale grid average pooling for breast cancer segmentation in an ultrasound image,  IEEE transactions on ultrasonics, ferroelectrics, and frequency control 67 (2020) 1344–1353.
  * Wu et al. (2014) K. Wu, X. Chen, M. Ding,  Deep learning based classification of focal liver lesions with contrast-enhanced ultrasound,  Optik 125 (2014) 4057–4063.
  * Ma et al. (2017) J. Ma, F. Wu, J. Zhu, D. Xu, D. Kong,  A pre-trained convolutional neural network based method for thyroid nodule diagnosis,  Ultrasonics 73 (2017) 221–230.
  * Simonyan and Zisserman (2014) K. Simonyan, A. Zisserman,  Very deep convolutional networks for large-scale image recognition,  arXiv preprint arXiv:1409.1556 (2014).
  * Chollet (2017) F. Chollet,  Xception: Deep learning with depthwise separable convolutions,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 1251–1258.
  * He et al. (2016) K. He, X. Zhang, S. Ren, J. Sun,  Deep residual learning for image recognition,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * Xie et al. (2017) S. Xie, R. Girshick, P. Dollár, Z. Tu, K. He,  Aggregated residual transformations for deep neural networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 1492–1500.
  * Hu et al. (2018) J. Hu, L. Shen, G. Sun,  Squeeze-and-excitation networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 7132–7141.
  * Szegedy et al. (2016) C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, Z. Wojna,  Rethinking the inception architecture for computer vision,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2818–2826.
  * Russakovsky et al. (2015) O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al.,  Imagenet large scale visual recognition challenge,  International journal of computer vision 115 (2015) 211–252.
  * Kingma and Ba (2014) D. P. Kingma, J. Ba,  Adam: A method for stochastic optimization,  arXiv preprint arXiv:1412.6980 (2014).
  * Paszke et al. (2017) A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, A. Lerer,  Automatic differentiation in pytorch,  in: NIPS-W, 2017, pp. 1–4.
  * Zhou et al. (2016) B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, A. Torralba,  Learning deep features for discriminative localization,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2921–2929.
  * Ma et al. (2020) X. Ma, Z. Ji, S. Niu, T. Leng, D. L. Rubin, Q. Chen,  Ms-cam: Multi-scale class activation maps for weakly-supervised segmentation of geographic atrophy lesions in sd-oct images,  IEEE Journal of Biomedical and Health Informatics 24 (2020) 3443–3455.
  * Qiao et al. (2019) N. Qiao, M. Song, Z. Ye, W. He, Z. Ma, Y. Wang, Y. Zhang, X. Shou,  Deep learning for automatically visual evoked potential classification during surgical decompression of sellar region tumors,  Translational vision science & technology 8 (2019) 21–21.
  * Sun et al. (2017) C. Sun, A. Shrivastava, S. Singh, A. Gupta,  Revisiting unreasonable effectiveness of data in deep learning era,  in: Proceedings of the IEEE international conference on computer vision, 2017, pp. 843–852.
  * Rolnick et al. (2017) D. Rolnick, A. Veit, S. Belongie, N. Shavit,  Deep learning is robust to massive label noise,  arXiv preprint arXiv:1705.10694 (2017).
  * Zhang et al. (2018) J. Zhang, S. Gajjala, P. Agrawal, G. H. Tison, L. A. Hallock, L. Beussink-Nelson, M. H. Lassen, E. Fan, M. A. Aras, C. Jordan, et al.,  Fully automated echocardiogram interpretation in clinical practice: feasibility and diagnostic accuracy,  Circulation 138 (2018) 1623–1635.
  * Vidal et al. (2021) M. L. B. Vidal, G.-P. Diller, A. Kempny, W. Li, K. Dimopoulos, S. J. Wort, M. Gatzoulis,  Utility of deep learning algorithms in diagnosing and automatic prognostication of pulmonary arterial hypertension based on routine echocardiographic imaging,  Journal of the American College of Cardiology 77 (2021) 1670–1670.
  * Leclerc et al. (2019) S. Leclerc, E. Smistad, J. Pedrosa, A. Østvik, F. Cervenansky, F. Espinosa, T. Espeland, E. A. R. Berg, P.-M. Jodoin, T. Grenier, et al.,  Deep learning for segmentation using an open large-scale dataset in 2d echocardiography,  IEEE transactions on medical imaging 38 (2019) 2198–2210.
  * Sanchez-Martinez et al. (2018) S. Sanchez-Martinez, N. Duchateau, T. Erdei, G. Kunszt, S. Aakhus, A. Degiovanni, P. Marino, E. Carluccio, G. Piella, A. G. Fraser, et al.,  Machine learning analysis of left ventricular function to characterize heart failure with preserved ejection fraction,  Circulation: cardiovascular imaging 11 (2018) e007138.
  * Omar et al. (2018) H. A. Omar, J. S. Domingos, A. Patra, R. Upton, P. Leeson, J. A. Noble,  Quantification of cardiac bull’s-eye map based on principal strain analysis for myocardial wall motion assessment in stress echocardiography,  in: 2018 IEEE 15th International Symposium on Biomedical Imaging (ISBI 2018), IEEE, 2018, pp. 1195–1198.