evblue

# No Bidding, No Regret: Pairwise-Feedback Mechanisms for Digital Goods and
Data Auctions

Zachary Robertson
Department of Computer Science
Stanford
<EMAIL_ADDRESS>
&Oluwasanmi Koyejo
Department of Computer Science
Stanford
<EMAIL_ADDRESS>

###### Abstract

The growing demand for data and AI-generated digital goods, such as
personalized written content and artwork, necessitates effective pricing and
feedback mechanisms that account for uncertain utility and costly production.
Motivated by these developments, this study presents a novel mechanism design
addressing a general repeated-auction setting where the utility derived from a
sold good is revealed post-sale. The mechanism’s novelty lies in using
pairwise comparisons for eliciting information from the bidder, arguably
easier for humans than assigning a numerical value. Our mechanism chooses
allocations using an epsilon-greedy strategy and relies on pairwise
comparisons between realized utility from allocated goods and an arbitrary
value, avoiding the learning-to-bid problem explored in previous work. We
prove this mechanism to be asymptotically truthful, individually rational, and
welfare and revenue maximizing. The mechanism’s relevance is broad, applying
to any setting with made-to-order goods of variable quality. Experimental
results on multi-label toxicity annotation data, an example of negative
utilities, highlight how our proposed mechanism could enhance social welfare
in data auctions. Overall, our focus on human factors contributes to the
development of more human-aware and efficient mechanism design.

##  1 Introduction

Marketplaces generating digital goods, such as personalized written content
and artwork based on user requests, have garnered significant attention in
recent years due to their ability to scale and adapt to user preferences (Mor,
2023; Paul and Dang, 2023). Such generative marketplaces possess immense
potential to revolutionize the economy through applications such as online
advertising (Paul and Dang, 2023), a market where spending is expected to
exceed $700 billion in 2023 (Sta, 2023). However, they face challenges in
collecting accurate and timely human feedback, as well as in managing compute
costs for the most advanced models, which the CEO of OpenAI has described as
"eye-watering" (Karpf, 2023). This problem is particularly acute since the
value each user derives from a fulfilled request is typically only known after
allocation.

In this paper, we examine the general repeated-auction setting where the
utility derived from sold digital goods is revealed to bidders post-sale. In
this setting, digital goods are "made-to-order" based on user requests. A key
challenge is that users could provide inaccurate or misleading feedback, which
would harm revenue generation. To address these challenges, we propose an
auction mechanism that is robust to strategic reporting on the user side and
no-regret in revenue on the market side. Our pricing mechanism is based on a
pairwise comparison model that asks the user to report if the value of their
allocation is above an arbitrarily selected reference point, avoiding the
learning-to-bid problem that has been a point of concern in previous works
(Feng et al., 2018; Guo et al., 2022).

Our main contribution is a novel auction mechanism for selling digital goods
that are costly to produce and whose utility to a particular user is
uncertain. We outline our main contributions below:

  1. 1.

Feedback-based auction mechanisms: This study introduces a feedback-driven,
contextual, asymptotically truthful mechanism that eliminates the need for
users to know their value for generating a digital good beforehand. By
allocating goods to agents and subsequently collecting feedback on their
satisfaction, the mechanism effectively sidesteps the learning-to-bid problem.

  2. 2.

Analysis of efficiency: An in-depth analysis of the proposed mechanism is
presented. We establish finite-time regret bounds for truthful reporting,
participation, and welfare-revenue generation against the standard second-
price auction. We also show the underlying expected utilities can be
identified from pairwise comparisons without relying on distributional
assumptions.

  3. 3.

Welfare maximizing data acquisition: We also explore how to use our mechanism
as a payment rule for toxicity annotation, a setting with negative utilities
that are only realized after the mechanism purchases a label from a user. We
discuss this setting further in Section 5.2.

We tackle two main technical challenges. First, akin to (Nazerzadeh et al.,
2013), we utilize a learning algorithm for the expected utility function but
diverge from their history-dependent rule, which requires $O(H^{2})$ calls to
the model for $H$ allocation rounds to enhance computational efficiency. Our
Lemma 5.2 outlines that providing inaccurate or misleading feedback isn’t
particularly profitable, achieved through a refined strategic reporting and
regret analysis. Secondly, our mechanism features a simplified reporting rule,
negating the need for agents to accurately learn to bid, as seen in works like
(Feng et al., 2018; Guo et al., 2022). Although common among all prior work we
are aware of, we also dismiss the unrealistic assumption of precise value
reporting as it essentially requires reporting a real number with infinite
precision. In Theorem 5.5, we establish a mechanism that uses feedback reports
free from distributional assumptions on underlying utilities.

The remainder of this paper is organized as follows. In Section 2, we review
related work in auctions with incomplete information, mechanism design, and
data pricing. In Section 3, we formalize our setting and describe the
background for our approach. In Section 4 we introduce our proposed mechanism,
and in Section 5 we present our main results for the proposed mechanism.

Figure 1: This is an illustration of our proposed mechanism introduced in
Section 4. In the left panel we start period $t$, each agent $i\in[n]$ submits
a request $w_{it}$ (prompt) for a made-to-order digital good, and then the
mechanism determines a boolean-valued allocation assignment $x_{it}$ for each
agent. If the $j^{\text{th}}$ agent receives an allocation for their request
("Mona Lisa") then the agent receives a digital good made according to their
request. After a digital good is produced, the agent self-reports a Boolean
value, denoted by $r_{jt}$, indicating if the value of their allocation is
above an arbitrarily selected reference point. Alternatively, the mechanism
produces multiple digital goods and has the user rank them. A priori, it is
not obvious how to design a mechanism robust to strategic manipulation. This
paper devises a simple mechanism based on a second-price auction that is
asymptotically truthful.

##  2 Related work

Our work builds on research in the fields of auctions with incomplete
information, machine learning for mechanism design, and data pricing.

###  2.1 Mechanism design and machine learning

Our work intertwines mechanism design and machine learning to address
challenges in pricing and feedback systems for digital goods and data (Balcan
et al., 2005; Devanur and Kakade, 2009; Babaioff et al., 2009, 2015). We also
draw from the intersection of machine learning and mechanism design for
allocating digital goods (Immorlica et al., 2005; Agarwal et al., 2009;
Mahdian and Tomak, 2008; Nazerzadeh et al., 2013).

The proposed mechanism is distinguished by two key differences from existing
works that also investigate online auction design (Devanur and Kakade, 2009;
Nazerzadeh et al., 2013; Babaioff et al., 2009). For exact truthfulness,
strict characterizations on attainable regret rates have been established for
deterministic payment rules (Devanur and Kakade, 2009; Babaioff et al., 2009).
Weaker asymptotic truthfulness has also been considered under the pay-per-
action framework known in online advertising (Immorlica et al., 2005; Mahdian
and Tomak, 2008; Nazerzadeh et al., 2013). Most related to our work is
(Nazerzadeh et al., 2013), which studies the pay-per-action setting, which
allows reporting value after allocation, and proposes a history-dependent
pricing rule. Our work builds on this progress by studying contextual
auctions, removing the history-dependent pricing rule, and eliminating the
requirement for an exact value offering a human-aware perspective and a more
computationally-efficient mechanism. See Table 1 for a comparison between
these approaches and our proposal.

###  2.2 Partially-informed auctions

Auction design with incomplete information has been a topic of interest in
recent years (Bergemann and Pesendorfer, 2007; Feng et al., 2018; Epasto et
al., 2021; Guo et al., 2022). In particular, (Bergemann and Pesendorfer, 2007)
considers single-item multi-bidder auctions where information is only
partially revealed to bidders. (Feng et al., 2018) investigates the single-
item setting where bidders learn to bid with partial feedback and obtain no-
regret against the best fixed bid in hindsight. (Guo et al., 2022) extend this
analysis by considering context and propose no-regret algorithms that are
efficient from the buyer’s perspective with applications to privacy. However,
all of this prior work requires that the agent learn-to-bid, which requires
additional effort and is commonly understood to lower an agent’s welfare (Cai
et al., 2015). Our work takes a different approach to study partially-informed
auctions by focusing on user compatibility to provide their value after
allocation while still maintaining the connection to these privacy
considerations (Epasto et al., 2021). See Table 1 for a comparison between
(Guo et al., 2022) and our proposal.

###  2.3 Welfare and truthful elicitation

In the realm of data pricing and acquisition, we draw from research on
learning-based data pricing (Chen et al., 2023; Zhao and Ermon, 2021;
Karimireddy et al., 2022), peer-prediction mechanisms (Prelec, 2004; Witkowski
and Parkes, 2012; Cai et al., 2015). In particular, (Cai et al., 2015)
develops a model for constructing statistical estimators in the presence of
costly information revelation, while (Prelec, 2004) and (Witkowski and Parkes,
2012) propose peer-prediction techniques for eliciting truthful information
without the need for ground-truth data. These works have made significant
contributions to understanding optimal mechanisms but are more concerned with
obtaining truthful responses rather than the socially efficient allocation of
goods.

In recent years, the question of worker welfare during data acquisition has
become a central issue. In particular, recent work on OpenAI’s toxicity filter
had to be halted because data annotation had a traumatic effect on workers
(Perrigo, 2023). Toxic data annotation, in general, is known to have traumatic
effects on workers (Burns et al., 2008; Arsht and Etcovitch, 2018; Steiger et
al., 2021; Perrigo, 2023). In particular, (Steiger et al., 2021) proposes
preventing or reducing exposure as a potential technological intervention
strategy. One of our contributions is to formalize this problem as an instance
of a reverse auction (negative utilities) in our setting and demonstrate
theoretically and empirically that we can asymptotically maximize the social
welfare of workers.

Table 1: Comparison of our mechanism with prior work Auction | Strategy | Feedback | Local | Efficient
---|---|---|---|---
Mechanism | Robust | Reporting | Payments | User-Strategy
(Devanur and Kakade, 2009) | ✓ | $\times$ | ✓ | $\times$
(Nazerzadeh et al., 2013) | ✓ | ✓ | $\times$ | $\times$
(Guo et al., 2022) | ✓ | $\times$ | ✓ | $\times$
This Work | ✓ | ✓ | ✓ | ✓

##  3 Preliminaries

In this section, we overview the problem setting under consideration and
introduce our key definitions. Discussion of how to learn a payment rule is
discussed in Section 4. As an example (Figure 1), agents could be competing
for resources to generate artwork, where the space of prompts is
$\mathcal{W}$, the space of digital goods is $\mathcal{O}$, and the mechanism
determines the price and allocation of resources. We summarize our notation in
Appendix A provided in the supplementary materials.

Problem Setting: We consider a scenario where a set of $n$ agents compete for
allocations across discrete periods $t=1,2,\ldots,H$, up to a horizon $H$. A
mechanism $\mathcal{M}$ oversees pricing for allocations. At each period $t$
the following happens:

  1. 1.

Each agent $i\in[n]$ submits a request $w_{it}\in\mathcal{W}$ sampled
independently from one another, and a Boolean-valued array of allocations
$x_{it}$ is generated for the agents.

  2. 2.

If the $j^{\text{th}}$ agent receives an allocation, then the agent receives a
digital good $o_{jt}\in\mathcal{O}$ sampled some distribution conditioned on
$w_{jt}$ which is sold to the agent.

  3. 3.

The non-negative value of the agent who receives an allocation during period
$t$ is denoted by a bounded random variable
$u_{jt}:\mathcal{W}\times\mathcal{O}\to[0,1]$.

  4. 4.

The agent pays an amount $p_{jt}$ determined by the mechanism and then reports
a Boolean variable $r_{jt}(c)$ indicating if $u_{jt}$ is above some value $c$
which is to be chosen randomly.

We’ll emphasize that $u_{it}$ has randomness from the requests $w_{it}$ and
the mechanism that generates outputs $o_{it}$. Since agent’s know their
requests, we’ll use $u_{it}(w)$ to denote the utility random variable given a
request $w$. Our main assumption is an independence assumption on the
requests.

######  Assumption 3.1.

For each agent $i\in[n]$, their request and output sequences $w_{it}$ and
$o_{it}$ are independent of other agents and allocations.

Assumption 3.1 allows sequential generation, such as written content, but
precludes collusion among agents or exploiting specific prompts for high
utility. We also introduce notation for an ideal setting where we have perfect
knowledge of the agents’ expected values.

$\mu_{i}(w_{it}):=\mathbb{E}[u_{it}(w_{it})|\\{(w_{ik},u_{ik})\\}_{k<t}],\
x_{it}:=\mathbb{I}(\mu_{i}(w_{it})\geq\mu_{j}(w_{jt})\ \forall j)$ (1)

This defines the agent’s expected utility and allocation. We will design
$\mathcal{M}$ (Section 4) so that agents have no-regret for participating and
truthful reporting along with comparable revenue and social welfare to a
standard auction format. To introduce the key definitions, we just need to
know $\mathcal{M}$ will determine allocations $\hat{x}_{it}$ and prices
$p_{it}$ using value estimates $\hat{\mu}_{it}\sim\mu_{i}$ from the reports.

######  Definition 3.2.

The $i^{\text{th}}$ agent is considered truthful if
$r_{it}(c)=\mathbb{I}(u_{it}\geq c)$ for all $t$ and $c\in[0,1]$.

This means they respond to the queries in Fig 1 accurately. In our setting,
there are numerous reporting strategies
$r_{it}:(\mathcal{W}\times\mathcal{O})\times[0,1]\to\\{0,1\\}$ the agents
could use. Our focus lies in designing a mechanism such that agent incentives
are aligned with truth-telling. Another important criterion for each agent is
that they have no-regret for participation.

######  Definition 3.3.

$\mathcal{M}$ is asymptotically ex ante individually rational if each agent
$i\in[n]$ has no-regret for participation when they are truthful.
Specifically, the long-term total utility of the agent is nonnegative:

$\liminf_{H\to\infty}\mathbb{E}\left[\sum_{t=1}^{H}\hat{x}_{it}\mu_{i}-p_{it}\right]\geq
0$

While definition 3.3 captures the rationality of each truthful agent’s
participation, it does not guarantee no-regret against other reporting
strategies.

######  Definition 3.4.

Let $U_{i}(H)$ be the expected total utility of the $i^{\text{th}}$ agent
using a truthful reporting strategy and $\hat{U}_{i}(H)$ be the maximum
expected profit whenever all other agents are truthful. We say that
$\mathcal{M}$ is asymptotically truthful if truthful reporting is no-regret
against strategic reporting:

$\hat{U}_{i}(H)-U_{i}(H)=o(H)$

This definition is similar to previous definitions in that it ensures that
deviating from truthful reporting is relatively unprofitable (Pavan et al.,
2009; Nazerzadeh et al., 2013). The main distinction is that it is regret-
based which enables us to obtain rates in our analysis. While an asymptotic
definition seems limiting, strong notions, such as dominant strategy incentive
compatibility, are achievable only in limited settings (Pavan et al., 2009;
Kakade et al., 2013).

We also desire $\mathcal{M}$ to have no-regret against an idealized auction.
We compare the welfare and revenue of our mechanism to a baseline given by the
second-price auction known to be welfare and revenue maximizing (Myerson,
1981). In this format, allocations go to the highest bidder, say, the
$i^{\text{th}}$ agent who will pay $\gamma_{t}=\max_{j\not=i}\mu_{j}(w_{jt})$
to $\mathcal{M}$. Otherwise, they pay nothing.

######  Definition 3.5.

We say $\mathcal{M}$ is asymptotically ex-ante welfare maximizing if it has
no-regret against the welfare generated by a second-price auction:

$\mathbb{E}\left[\sum_{t=1}^{H}\sum_{i=1}^{n}\hat{x}_{it}\mu_{i}(w_{it})\right]-\mathbb{E}\left[\sum_{t=1}^{H}\max_{i}(\mu_{i}(w_{it}))\right]=o(H)$

######  Definition 3.6.

We say $\mathcal{M}$ is asymptotically equivalent to the revenue of the
second-price auction if it has no-regret against the revenue generated by a
second-price auction:

$\mathbb{E}\left[\sum_{t=1}^{H}\sum_{i=1}^{n}\hat{x}_{it}p_{it}\right]-\mathbb{E}\left[\sum_{t=1}^{H}\gamma_{t}\right]=o(H)$

##  4 The proposed mechanism

Input : Exploration rate $\eta_{t}$, agent submissions $w_{it}$

Output : Tuple of context-report pairs

1 for  _$t=1,2,\cdots$_ do

2 if  _$\text{explore with probability }\eta_{t}$_ then

3 $i=\text{sample}([1,...,n])$ ;

4 $x_{it}=1$ ;

5 $c_{it}=\text{sample}([0,1])$ ;

6 $p_{it}=0$ ;

7 $r_{it}(c_{it})=\text{agent-report}(w_{it},c_{it})$ ;

8

9 else

10 $i=\text{argmax}_{j}\hat{\mu}_{jt}(w_{jt})$ ;

11 $x_{it},y_{it}=1$ ;

12 $p_{it},c_{it}=\max_{j\not=i}\hat{\mu}_{jt}(w_{jt})$ ;

13 $r_{it}(c_{it})=\text{agent-report}(w_{it},c_{it})$ ;

14

15 end if

16

17 end for

Algorithm 1 Feedback-Driven Mechanism

In our approach, as illustrated in Figure 1 and implemented in Algorithm 1, we
aim to estimate the utility function of each agent using a learning algorithm
$\mathcal{L}$, connecting with the high-level goals of the paper by designing
an auction mechanism that improves welfare in digital goods and data auctions.
Ideally, we would know $\mu_{i}$ for each agent $i\in[n]$ and allocate using a
second-price auction. The challenge lies in the potential misreporting of
observed utilities by agents to gain utility.

The basic mechanism is a second-price payment rule estimated with a learning
algorithm $\mathcal{L}$. We fit $\hat{\mu}_{it}$ using $\mathcal{L}$ and a
data set of context and reporting tuples $\\{(w_{ik},r_{ik},c_{ik})\\}_{k\in
S_{it}}$, where $c_{ik}=p_{ik}$ represents the price comparison, and $S_{it}$
denotes periods of allocation to the $i^{\text{th}}$ agent up to time $t$.
Simultaneously, the proposed mechanism performs a variant of $\epsilon$-greedy
allocation, allocating to agents with the highest estimated value during
exploitation rounds indicated by $y_{it}$ or exploring by allocating for free
to a randomly chosen agent with probability $\eta_{t}\in[0,1]$. During
exploration rounds, agents still compare to a price point $c_{it}$ sampled
from a distribution over $[0,1]$. Finally, the exploitation round payments are
$\hat{\gamma}_{t}=\text{max}_{j\not=i}\hat{\mu}_{jt}(w_{jt})$, with $i$
indicating the allocated agent. In general, the payment $p_{it}$ equals
$y_{it}\hat{\gamma}_{t}$.

To study allocation and payment, we define the best empirical estimate under
$\mathcal{L}$ of an agent’s expected utility and allocation using the data set
$\\{(w_{ik},c_{ik},r_{ik})\\}_{k\in S_{it}}$.

$\hat{\mu}_{it}(w_{it}):=\mathbb{E}_{\mathcal{L}}[u_{it}|\\{(w_{ik},c_{ik},r_{ik})\\}_{k\in
S_{it}}],\
\hat{x}_{it}:=\mathbb{I}(\hat{\mu}_{it}(w_{it})>\hat{\mu}_{jt}(w_{jt})\
\forall j)$ (2)

where $\mathbb{E}_{\mathcal{L}}$ is an estimate under $\mathcal{L}$ for the
true expected value. Discussion of a concrete choice of a learning algorithm
is delayed until Section 5.1. It is worth remarking that these definitions
differ from equation 1 because the agent merely reports their relative utility
against $c_{ik}$.

It is worth making a few remarks comparing our mechanism (see Table 1) to
related works implementing online auctions with learned expected values
(Devanur and Kakade, 2009; Nazerzadeh et al., 2013; Babaioff et al., 2015; Guo
et al., 2022). Our design deviates significantly in key areas. We allow agents
to self-report their satisfaction, circumventing the "learn-to-bid" assumption
adopted by (Guo et al., 2022). We introduce a simplified reporting rule that
directly links reports to current payments via binary feedback, which
simplifies value reporting for agents, a notable contrast from all of these
works. This strategy also contrasts with the computationally demanding
history-dependent payment rule used by (Nazerzadeh et al., 2013), which scales
quadratically. This tailored approach marks our mechanism as both efficient
and user-side oriented, as per our prior technical discussion.

##  5 Analysis

We develop sufficient conditions for the learning algorithm $\mathcal{L}$
applied in Algorithm 1 to estimate the $\mu_{i}$ that results in a mechanism
$\mathcal{M}$ that meets our social efficiency criterion. We then explore how
to implement the learning algorithm and examine a relevant data acquisition
example. Our main condition involves the error from $\mathcal{L}$ applied to
truthful reporting data from exploration rounds:

$\Delta_{t}:=\mathbb{E}[\max_{k}|\mu_{k}(w_{kt})-\hat{\mu}_{kt}(w_{kt}|x_{kt^{\prime}}=1,y_{kt^{\prime}}=0,0\leq
t^{\prime}<t)|]$ (3)

As the number of exploitation allocations is dependent on the other agents’
behavior, we focus on performance using just the randomly allocated
exploration rounds. Our main result offers valuable insights into the
performance of mechanism $\mathcal{M}$ using intuitive conditions on the
learning algorithm $\mathcal{L}$.

######  Theorem 5.1.

Suppose our mechanism $\mathcal{M}$ estimates agent values bounded to the
unit-interval using some learning algorithm $\mathcal{L}$. Suppose the
expected error of this algorithm is monotone decreasing in the number of
samples and that for all time,

$\sum_{t=1}^{H}\Delta_{t}=o\left(\sum_{t=1}^{H}\mathbb{E}[\eta(t)]\right)=o(H)$
(4)

then the mechanism $\mathcal{M}$ satisfies the following:

  1. 1.

Is asymptotically individually rational and asymptotically truthful

  2. 2.

Is asymptotically welfare and revenue maximizing.

  3. 3.

Compared to a second-price auction $\mathcal{M}$ can obtain welfare and
revenue regret $\tilde{O}(H^{2/3})$ if there is a learning algorithm
$\mathcal{L}$ for valuations with slow learning rate $\tilde{O}(H^{-1/2})$ and
regret $\tilde{O}(H^{1/2})$ if there is an algorithm with a fast rate
$\tilde{O}(H^{-1})$.

The primary assumption is that the expected sum of errors for the learning
algorithm decreases quickly relative to the sum of expected regret terms
$\mathbb{E}[\eta(t)]$ over the entire horizon $H$. Although we can always
increase the number of exploration rounds for a consistent algorithm to meet
this condition, doing so may significantly reduce revenue. We discuss a
concrete learning algorithm in Section 5.1.

The proof of this result relies on determining whether strategic reporting can
be profitable for an agent, which we bound in terms of the error induced by
the learning algorithm. We outline the main steps here and defer the proof to
Appendix B.1 in the supplementary materials.

######  Lemma 5.2.

A single agent providing misleading feedback can increase their expected
utility up to time $H$ by no more than $6\Sigma_{t\in[H]}\Delta_{t}$.

###### Proof Sketch.

The proof of Lemma 5.2 relies on evaluating the expected utility of an agent
deviating from a truthful strategy. We first ignore exploration allocations
since they are strategy independent. We then consider an agent who deviates
from a truthful reporting strategy $T$ to another strategy $L$. We fix
$\hat{\mu}_{it}$ as the utility estimated from data collected under strategy
$T$. We then analyze the expected utility of both strategies. The expected
profit of such a strategy is given by the difference between the expected
utilities under the new strategy $L$ and the truthful strategy $T$. We
decompose this profit into three cases, corresponding to the different
allocation times for the item to the agent: those in $S_{L}\setminus S_{T}$,
those in $S_{T}\setminus S_{L}$, and those in $S_{T}\cap S_{L}$. For each
case, we establish bounds on the differences between the expected utilities of
the two strategies. These bounds involve the estimates of utilities for
different agents under both strategies and the true utilities of the allocated
items. We then combine the results of these cases and obtain an upper bound on
the profit of deviating from the truthful strategy, which is
$O(\mathbb{E}[\Sigma_{t}\Delta_{t}])$ over all time steps up to time $H$. ∎

This bound is worse than (Nazerzadeh et al., 2013) by a constant factor since
we do not use a history-dependent payment rule which can correct for its past
estimation errors. Unlike this work, we use a regret-based framework to
proceed with the rest of the analysis.

######  Lemma 5.3.

$\mathcal{M}$ is asymptotically truthful and individually rational.

###### Proof Sketch.

Notice that the expected profit from exploration rounds is the same between
strategies. Therefore, by Lemma 5.2 we have
$\hat{U}_{i}(H)-\text{U}_{i}(H)\leq 6\Sigma_{t\in[H]}\Delta_{t}$. We also have
asymptotic individual rationality because we can bound the overcharges to the
agent,

$\mathbb{E}\left[\sum_{t\in
S_{T}}\hat{\gamma}_{t}-\mu_{i}(w_{it})\right]\leq\mathbb{E}\left[\sum_{t\in
S_{T}}\hat{\mu}_{it}(w_{it})-\mu_{t}(w_{it})\right]\leq\mathbb{E}\left[\sum_{t}\Delta_{t}\right]$

As we send the horizon to infinity, we see that these overcharges are bounded
by the error rate. By assumption, this term is dominated by the free
allocations, so we have asymptotic ex-ante individual rationality. ∎

Now we examine the question of regret concerning welfare and revenue
objectives. Our mechanism may lose revenue during exploration and due to
estimation error during exploitation.

######  Lemma 5.4.

$\mathcal{M}$ is asymptotically welfare and revenue maximizing. Compared to a
second-price auction $\mathcal{M}$ can obtain welfare and revenue regret
$\tilde{O}(H^{2/3})$ if there is a learning algorithm $\mathcal{L}$ for
valuations with slow learning rate $\tilde{O}(H^{-1/2})$ and regret
$\tilde{O}(H^{1/2})$ if there is an algorithm with a fast rate
$\tilde{O}(H^{-1})$.

Remarks: Our results improve upon (Nazerzadeh et al., 2013), which does not
provide finite-time regret rates for their algorithm. Furthermore, compared to
(Guo et al., 2022), which only considers a single agent against a post price,
our mechanism considers a multi-agent setting without assuming the agents’
ability to bid. In this work, they establish this bound for applications to
user privacy where the context is masked in order to preserve privacy. Since
masking is deterministic in this work, we can use standard results from
realizable learning theory, see Anthony et al. (1999), to conclude our
algorithm also achieves $\tilde{O}(H^{-1/2})$ in the stochastic setting. In
general, it is unclear if using an adaptive algorithm would help given
$\Omega(H^{2/3})$ lower-bounds on regret in this setting (Devanur and Kakade,
2009; Babaioff et al., 2009). Despite these limitations, our mechanism
showcases the importance of feedback and welfare in shaping digital goods and
data auction mechanisms that are more efficient and user-friendly.

###  5.1 Estimating the value model with pairwise feedback

To make our theory concrete, we can consider $\mu_{i}$ that follows a linear
model with $d$-features and with standard independent noise and realizability
assumption. We will call the resulting mechanism using uniformly sampled
comparison prices, linear regression algorithm $\mathcal{L}$, and exploration
rate $\eta$ by $\mathcal{M}_{\eta}(\text{linear})$.

######  Theorem 5.5.

For an exploration rate $\eta_{t}=t^{-1/3}\cdot(n\log(t))^{(1+2\epsilon)/3}$
we have that $\mathcal{M}_{\eta}(\text{linear})$ satisfies the conditions of
Theorem 5.1 and so is asymptotically individually rational, incentive
compatible, and no-regret in revenue and welfare.

The full proof is provided in Appendix B.2 in the supplementary materials. The
main technical step in the proof is to identify the underlying utility from
pairwise reports. In our mechanism, we obtain reports $r_{it}$ from agents
regarding if the random utility $u_{it}$ derived from their allocation for a
request $w_{it}$ is satisfactory. This is based on being above or below some
reference payment $c$. Our model is that $r_{it}(c)=\mathbb{I}(u_{it}\geq c)$.
In particular, we have the following,

######  Lemma 5.6.

If $u$ is a nonnegative random variable, we have that,

$\mu=\int_{0}^{1}\mathbb{P}(u\geq c)dc$ (5)

interpreting the integral as a Lebesgue integral with respect to the Lebesgue
measure.

An immediate corollary of Lemma 5.6 is that the least-squares estimator for
the conditional expectation $\mathbb{E}[r_{i}|w]$ given by $\hat{r}_{i}(w)$
equals $\hat{\mu}_{i}(w)$ in the population setting under uniform random
sampling of comparison prices. Another implication of this result is that we
also obtain a data set of labeled comparisons expressing human feedback on the
performance of the underlying generative process. One potential application is
in the context of reinforcement learning from human feedback (Christiano et
al., 2017). In this setting, we would also allow comparisons between generated
outputs and then train the value model using these pairwise comparisons as
constraints.

###  5.2 Experiment with toxicity annotation

(a) Welfare regret

(b) Welfare histogram

Figure 2: Welfare is the sum of the utilities of all agents across all the
allocation periods. We compare the expected welfare regret (a) of different
allocation mechanisms for data acquisition vs. an ideal allocation mechanism.
Our relative feedback approach elicits relative utility information,
regression fits values using utility reports from agents, and uniform
allocation methods such as peer prediction make assignments at random. The
welfare histogram (b) shows the distribution of welfare losses for each agent
under different allocation mechanisms.

In some cases, allocations to users might result in negative utility, which
would mean the mechanism pays users for reporting feedback. For instance, the
employment of low-wage workers to enhance AI systems has brought about ethical
concerns, such as the distressing impact on workers who review harmful content
(Steiger et al., 2021; Perrigo, 2023). In particular, (Steiger et al., 2021)
proposes preventing or reducing exposure as a potential technological
intervention strategy. In this section, we present two experiments to evaluate
our mechanism as an intervention strategy 111We provide the code for our
experiments in the supplementary materials.

For the experiments, we use multi-label data from the Toxic Comment
Classification Challenge on Kaggle, which contains a large number of Wikipedia
comments labeled by human raters for toxic behavior, including categories such
as toxic, severe-toxic, obscene, threat, insult, and identity-hate (Kag,
2018). We assess the welfare regret of various allocation strategies by
comparing them to the strategy that allocates resources to the agent with the
highest expected welfare during each period. This concept is formally defined
in definition 3.5. The expected utility is modeled with a linear model, as
discussed in Section 5.1, and employs 30-dimensional PCA analysis to GloVe
features for the data representation (Pennington et al., 2014). Our experiment
involves 10 agents and spans 5000 rounds of allocation. We assume that each
agent possesses a fixed type sensitivity of which they are unaware, which
determines their utility function. Every agent classifies examples sampled
i.i.d from the dataset as toxic or non-toxic by reporting their relative
utility from viewing the example. Moreover, when an agent encounters an
example with a label matching their type sensitivity, they lose one unit of
utility. For instance, an agent may be particularly sensitive to obscene
examples.

We evaluate the welfare performance of three mechanisms: our method based on
relative feedback, approaches that directly regress utility, and uniform
assignment approaches. The direct utility regression methods, including
(Devanur and Kakade, 2009; Babaioff et al., 2009; Nazerzadeh et al., 2013),
vary in terms of payment structures, while learn-to-bid methods (Guo et al.,
2022) assume workers estimate their own value and learn to bid accordingly.
Uniform assignment approaches, on the other hand, make no attempt to intervene
in the content allocation process and encompass most peer-prediction methods
that pay based on conformity rather than utility, focusing on incentive
compatibility issues (Prelec, 2004; Witkowski and Parkes, 2012; Cai et al.,
2015).

Our experimental results in Figure 2(a) and 2(b) show that using an auction
mechanism can significantly improve the welfare of the allocations given to
agents over the peer-prediction method and performs favorably to the optimal
allocation strategy. Moreover, our relative elicitation mechanism is
competitive with the full information set but has the advantage of being
simpler for users to report on. For example, while we make no further
modifications to the calculation of welfare beyond what has already been
discussed, some works assume there is a further cost to complicated
elicitation strategies (Cai et al., 2015).

##  6 Limitations and future work

Our proposed approach has some limitations that warrant further exploration.
While we propose an intervention method to improve the social welfare of
workers doing toxic annotation, other aspects, such as negative psychological
impacts and systemic issues around who does such work, are left unaddressed.
While we provide a mechanism for the dynamic setting, we assume value evolves
independently of other agents and the mechanism allocations, which prohibits
us from studying collusion or adversarial scenarios. In particular, agents who
make alias accounts could game the mechanism for free exploration allocations.
Also, it is possible a randomized approach could improve upon the rates
presented. Finally, we think further exploration as auction mechanism for
selling digital goods in real-world settings is an important direction.

##  7 Conclusions and societal impact

In this paper, we have presented a novel approach to auctioning AI services
that emphasizes user-friendly bidding, extends to multi-agent and contextual
settings, offers simpler mechanisms, and improved bounds. Our approach has the
potential for significant societal impact by facilitating a more efficient
allocation of AI services and enabling a wider range of users to access these
services without requiring them to have a deep understanding of their value.
At the same time, we recognize that the collection of feedback or toxic
annotation data may have negative externalities on the privacy and welfare of
workers. Addressing the limitations and ethical concerns identified, we can
move towards a future where AI services are more accessible, efficient, and
ethically responsible, ultimately leading to a positive impact on society.

## Acknowledgments and Disclosure of Funding

I’d like to thank Ellen Vitercik for advising during the initial development
of theory for the mechanism. I’d also like to thank Neil Band for suggesting I
pursue simplifying the reporting method.

## References

  * Mor [2023] Mar 2023.  URL https://www.jpmorgan.com/insights/research/generative-ai.
  * Paul and Dang [2023] Katie Paul and Sheila Dang.  Facebook owner meta announces tests of generative ai ads tool, May 2023\.  URL https://www.reuters.com/technology/facebook-owner-meta-announces-tests-generative-ai-ads-tool-2023-05-11/.
  * Sta [2023] Feb 2023.  URL https://www.statista.com/outlook/dmo/digital-advertising/worldwide.
  * Karpf [2023] David Karpf.  Money will kill chatgpt’s magic, Jan 2023.  URL https://www.theatlantic.com/technology/archive/2022/12/chatgpt-ai-chatbots-openai-cost-regulations/672539/.
  * Feng et al. [2018] Zhe Feng, Chara Podimata, and Vasilis Syrgkanis.  Learning to bid without knowing your value.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , pages 505–522, 2018.
  * Guo et al. [2022] Wenshuo Guo, Michael Jordan, and Ellen Vitercik.  No-regret learning in partially-informed auctions.  In _International Conference on Machine Learning_ , pages 8039–8055. PMLR, 2022.
  * Nazerzadeh et al. [2013] Hamid Nazerzadeh, Amin Saberi, and Rakesh Vohra.  Dynamic pay-per-action mechanisms and applications to online advertising.  _Operations Research_ , 61(1):98–111, 2013.
  * Balcan et al. [2005] M-F Balcan, Avrim Blum, Jason D Hartline, and Yishay Mansour.  Mechanism design via machine learning.  In _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_ , pages 605–614. IEEE, 2005.
  * Devanur and Kakade [2009] Nikhil R Devanur and Sham M Kakade.  The price of truthfulness for pay-per-click auctions.  In _Proceedings of the 10th ACM conference on Electronic commerce_ , pages 99–106, 2009.
  * Babaioff et al. [2009] Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins.  Characterizing truthful multi-armed bandit mechanisms.  In _Proceedings of the 10th ACM conference on Electronic commerce_ , pages 79–88, 2009.
  * Babaioff et al. [2015] Moshe Babaioff, Robert D Kleinberg, and Aleksandrs Slivkins.  Truthful mechanisms with implicit payment computation.  _Journal of the ACM (JACM)_ , 62(2):1–37, 2015\.
  * Immorlica et al. [2005] Nicole Immorlica, Kamal Jain, Mohammad Mahdian, and Kunal Talwar.  Click fraud resistant methods for learning click-through rates.  In _Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005. Proceedings 1_ , pages 34–45. Springer, 2005.
  * Agarwal et al. [2009] Nikhil Agarwal, Susan Athey, and David Yang.  Skewed bidding in pay-per-action auctions for online advertising.  _American Economic Review_ , 99(2):441–447, 2009\.
  * Mahdian and Tomak [2008] Mohammad Mahdian and Kerem Tomak.  Pay-per-action model for on-line advertising.  _International Journal of Electronic Commerce_ , 13(2):113–128, 2008.
  * Bergemann and Pesendorfer [2007] Dirk Bergemann and Martin Pesendorfer.  Information structures in optimal auctions.  _Journal of economic theory_ , 137(1):580–609, 2007.
  * Epasto et al. [2021] Alessandro Epasto, Andrés Muñoz Medina, Steven Avery, Yijian Bai, Robert Busa-Fekete, CJ Carey, Ya Gao, David Guthrie, Subham Ghosh, James Ioannidis, et al.  Clustering for private interest-based advertising.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 2802–2810, 2021.
  * Cai et al. [2015] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou.  Optimum statistical estimation with strategic data sources.  In _Conference on Learning Theory_ , pages 280–296. PMLR, 2015.
  * Chen et al. [2023] Siyu Chen, Jibang Wu, Yifan Wu, and Zhuoran Yang.  Learning to incentivize information acquisition: Proper scoring rules meet principal-agent model.  _arXiv preprint arXiv:2303.08613_ , 2023.
  * Zhao and Ermon [2021] Shengjia Zhao and Stefano Ermon.  Right decisions from wrong predictions: A mechanism design alternative to individual calibration.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2683–2691. PMLR, 2021.
  * Karimireddy et al. [2022] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I Jordan.  Mechanisms that incentivize data sharing in federated learning.  _arXiv preprint arXiv:2207.04557_ , 2022.
  * Prelec [2004] Drazen Prelec.  A bayesian truth serum for subjective data.  _science_ , 306(5695):462–466, 2004.
  * Witkowski and Parkes [2012] Jens Witkowski and David Parkes.  A robust bayesian truth serum for small populations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26, pages 1492–1498, 2012.
  * Perrigo [2023] Billy Perrigo.  Exclusive: Openai used kenyan workers on less than $2 per hour to make chatgpt less toxic.  _Last accessed_ , 19, 2023.
  * Burns et al. [2008] Carolyn M Burns, Jeff Morley, Richard Bradshaw, and José Domene.  The emotional impact on and coping strategies employed by police teams investigating internet child exploitation.  _Traumatology_ , 14(2):20–31, 2008.
  * Arsht and Etcovitch [2018] Andrew Arsht and Daniel Etcovitch.  The human cost of online content moderation.  _Harvard Journal of Law and Technology_ , 2018.
  * Steiger et al. [2021] Miriah Steiger, Timir J Bharucha, Sukrit Venkatagiri, Martin J Riedl, and Matthew Lease.  The psychological well-being of content moderators: the emotional labor of commercial moderation and avenues for improving support.  In _Proceedings of the 2021 CHI conference on human factors in computing systems_ , pages 1–14, 2021.
  * Pavan et al. [2009] Alessandro Pavan, Ilya R Segal, and Juuso Toikka.  Dynamic mechanism design: Incentive compatibility, profit maximization and information disclosure.  _Profit Maximization and Information Disclosure (May 1, 2009)_ , 2009\.
  * Kakade et al. [2013] Sham M Kakade, Ilan Lobel, and Hamid Nazerzadeh.  Optimal dynamic mechanism design and the virtual-pivot mechanism.  _Operations Research_ , 61(4):837–854, 2013.
  * Myerson [1981] Roger B Myerson.  Optimal auction design.  _Mathematics of operations research_ , 6(1):58–73, 1981.
  * Anthony et al. [1999] Martin Anthony, Peter L Bartlett, Peter L Bartlett, et al.  _Neural network learning: Theoretical foundations_ , volume 9.  cambridge university press Cambridge, 1999.
  * Christiano et al. [2017] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Kag [2018] 2018\.  URL https://tinyurl.com/jigsaw-toxic-comment-challenge.
  * Pennington et al. [2014] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543, 2014.
  * Györfi et al. [2002] László Györfi, Michael Köhler, Adam Krzyżak, and Harro Walk.  _A distribution-free theory of nonparametric regression_ , volume 1.  Springer, 2002.

##  Appendix A Summary of notation

Table 2: Summary of notation Notation | Definition
---|---
$i\in[n]$ | Agent $i$ out of $n$
$t\in[H]$ | Periods $t$ in horizon $H$
$w_{it}\in\mathcal{W}$ | Agent request
$o_{it}\in\mathcal{O}$ | Produced good from request
$u_{it}\in[0,1]$ | Agent $i$ utility at time $t$
$\mu_{i}$ | Expected value function of agent $i$
$\mathcal{L}$ | Learning algorithm for $\mu_{i}$
$\Delta_{t}$ |  $\mathcal{L}$’s error - exploration rounds
$\eta_{t}$ | Exploration frequency
$\hat{\mu}_{it}$ | Estimate for $\mu_{i}$ with $\mathcal{L}$
$\hat{\gamma}_{t}$ | Estimated second-price
$S_{it}$ | Allocations of $i$ up to time $t$
$x_{it}\in\\{0,1\\}$ | Allocation indicator
$\hat{x}_{it}$ | Allocations with $\mathcal{L}$
$y_{it}\in\\{0,1\\}$ | Exploitation indicator
$r_{it}\in\\{0,1\\}$ | Report of agent $i$ at time $t$
$p_{it}$ | Payment of agent $i$ at time $t$
$c_{it}$ | Comparison price

##  Appendix B Omitted proofs

###  B.1 Proof of theorem 5.1

See 5.1

We proceed by first showing that strategic reporting isn’t particularly
profitable compared to the profit from free allocations. Following this, we
establish asymptotic truthfulness and individual rationality properties.
Finally, we analyze the welfare and revenue regret of our mechanism.

See 5.2

###### Proof.

Recall that $\Delta_{t}$ is the expected maximum error of the learning
algorithm over all the agents $i\in[n]$ with respect to exploration round
data. We denote the set of allocation times with
$S:=\\{t\in[H]:\hat{x}_{it}=1\\}$. Recall there are numerous reporting
strategies $r_{it}:(\mathcal{W}\times\mathcal{O})\times[0,1]\to\\{0,1\\}$ each
agent could use. Accordingly, when it is important to specify the reporting
strategies used by the agents, we will adorn these definitions in some fashion
with the relevant strategy $L$ e.g., $S_{L}$,
$\hat{x}_{it}(L),\hat{\mu}_{it}(w_{it}|L)$.

We ignore exploration allocations since they are strategy independent and
therefore cancel each other out. Still, our agent may try to deviate from
being truthful under some reporting strategy $T$ to some other reporting
strategy $L$ that induces a new set of allocation times $S_{L}$ for the item
to the agent. We fix $\hat{\mu}_{it}$ to represent the utility estimated from
data collected under strategy $T$. By the tower property the expected utility
for a given strategy satisfies,

$U_{i}(L,H)=\mathbb{E}\left[\sum_{t\in
S_{L}}u_{it}(w_{it})-\hat{\gamma}_{t}(L)\right]$ $=\mathbb{E}\left[\sum_{t\in
S_{L}}\mathbb{E}\left[u_{it}(w_{it})-\hat{\gamma}_{t}(L)\big{|}\\{(w_{ik},c_{ik},r_{ik})\\}_{k\in[t]}\right]\right]$
$=\mathbb{E}\left[\sum_{t\in S_{L}}\mu_{i}(w_{it})-\hat{\gamma}_{t}(L)\right]$

Accordingly, the expected profit of such a strategy is given by,

$\text{Profit}(L,H)=U_{i}(L,H)-U_{i}(T,H)$ $=\mathbb{E}\left[\sum_{t\in
S_{L}}\mu_{i}(w_{it})-\hat{\gamma}_{t}(L)\right]-\mathbb{E}\left[\sum_{t\in
S_{T}}\mu_{i}(w_{it})-\hat{\gamma}_{t}(T)\right]$ $=\mathbb{E}\left[\sum_{t\in
S_{L}\setminus
S_{T}}\mu_{i}(w_{it})-\hat{\gamma}_{t}(L)\right]-\mathbb{E}\left[\sum_{t\in
S_{T}\setminus
S_{L}}\mu_{i}(w_{it})-\hat{\gamma}_{t}(T)\right]+\mathbb{E}\left[\sum_{t\in
S_{T}\cap S_{L}}\hat{\gamma}_{t}(T)-\hat{\gamma}_{t}(L)\right]$

In the last line, observe that whenever $t\in S_{T}\setminus S_{L}$ we have
that $\hat{\mu}_{it}(w_{it}|T)>\hat{\gamma}_{t}(T)$ and so,

$\mu_{i}(w_{it})-\hat{\gamma}_{t}(T)=\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T)+\underbrace{\hat{\mu}_{it}(w_{it}|T)-\hat{\gamma}_{t}(T)}_{>0}$
$\Rightarrow\mu_{i}(w_{it})-\hat{\gamma}_{t}(T)\geq\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T),\quad
t\in S_{T}\setminus S_{L}$

For $t\in S_{L}\setminus S_{T}$ let $j$ be the agent who would receive the
item if agent $i$ were truthful. We have
$\hat{\mu}_{jt}(w_{jt}|T)\geq\hat{\mu}_{it}(w_{it}|T)$. So we have,

$\mu_{i}(w_{it})-\hat{\gamma}_{t}(L)\leq\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T)+\hat{\mu}_{jt}(w_{jt}|T)-\hat{\gamma}_{t}(L)\quad
t\in S_{L}\setminus S_{T}$

We also have that $\hat{\mu}_{jt}(w_{jt}|L)\leq\hat{\gamma}_{t}(L)$ so we
have,

$\mu_{i}(w_{it})-\hat{\gamma}_{t}(L)\leq(\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T))+\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}\quad
t\in S_{L}\setminus S_{T}$

Finally, for $t\in S_{T}\cap S_{L}$ we let $j\not=i$ be the agent with the
highest $\hat{\mu}_{jt}(w_{jt}|T)$. So we have,

$\hat{\gamma}_{t}(T)-\hat{\gamma}_{t}(L)\leq\hat{\mu}_{jt}(w_{jt}|T)-\hat{\mu}_{jt}(w_{jt}|L)\leq\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}$

After substitution, we end up with a simplified expression for the
$i^{\text{th}}$ agent’s profit:

$\text{Profit}(L,H)\leq\mathbb{E}\left[\sum_{t\in S_{L}\setminus
S_{T}}(\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T))+\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}\right]$
(6) $-\mathbb{E}\left[\sum_{t\in S_{T}\setminus
S_{L}}\mu_{i}(w_{it})-\hat{\mu}_{it}(w_{it}|T)\right]+\mathbb{E}\left[\sum_{t\in
S_{T}\cap
S_{L}}\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}\right]$

To proceed, we observe that:

$\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{k}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}$

$\leq\max_{k\not=i}|\mu_{k}(w_{k})-\hat{\mu}_{kt}(w_{kt}|T)|+|\mu_{k}(w_{kt})-\hat{\mu}_{kt}(w_{kt}|L)|$
$\leq\max_{k\not=i}|\mu_{k}(w_{kt})-\hat{\mu}_{kt}(w_{kt}|T)|+\max_{k\not=i}|\mu_{k}(w_{kt})-\hat{\mu}_{kt}(w_{kt}|L)|$

Recall the assumption that only the agent $i$ is misreporting. Therefore, all
the agents except $i$ are truthful so each term can be bounded by $\Delta_{t}$
and so we end up with,

$\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}\leq
2\max_{k}|\mu_{k}(w_{kt})-\hat{\mu}_{kt}(w_{kt}|T)|$
$\Rightarrow\mathbb{E}[\max_{k\not=i}\\{\hat{\mu}_{kt}(w_{kt}|T)-\hat{\mu}_{kt}(w_{kt}|L)\\}]\leq
2\Delta_{t}$

Here we are using the assumption that the learning algorithm is proper since
$\Delta_{t}$ is the expected error over only the exploration rounds.
Substituting the result into Eq. 6 we obtain:

$\text{Profit}(L,H)\leq 6\sum_{t=1}^{H}\Delta_{t}$

as claimed, which completes the proof.

∎

See 5.3

###### Proof.

Notice that we have,

$\text{U}_{i}(H)=\mathbb{E}\left[\sum_{t\in
S_{T}}(\mu_{i}(w_{it})-\hat{\gamma}_{t})\right]+\frac{1}{n}\mathbb{E}\left[\sum_{t=1}^{H}\eta_{t}\mu_{i}(w_{it})\right]$

$\hat{U}_{i}(H)-\text{U}_{i}(H)\leq
6\Sigma_{t\in[H]}\Delta_{t}=o\left(\mathbb{E}\left[\sum_{t}\eta_{t}\right]\right)=o(H)$

The last step follows from Lemma 5.2 and since, by assumption, the free
allocation rate strictly dominates the error rate of the estimation procedure.

We also have asymptotic individual rationality because we can bound the
overcharges to the agent,

$\mathbb{E}\left[\sum_{t\in
S_{T}}\hat{\gamma}_{t}-\mu_{i}(w_{it})\right]\leq\mathbb{E}\left[\sum_{t\in
S_{T}}\hat{\mu}_{it}(w_{it})-\mu_{i}(w_{it})\right]\leq\mathbb{E}\left[\sum_{t}\Delta_{t}\right]$

As we send the horizon to infinity, we see that these overcharges are bounded
by the error rate and, by assumption, this term is dominated by the free
allocations, so we have,

$\mathbb{E}\left[\sum_{t\in
S_{T}}\hat{\gamma}_{t}-\mu_{i}(w_{it})\right]\leq\mathbb{E}\left[\sum_{t}\Delta_{t}\right]=o\left(\mathbb{E}\left[\sum_{t}\eta_{t}\right]\right)=o(H)$

which establishes asymptotic ex-ante individual rationality. ∎

See 5.4

###### Proof.

We present the argument for revenue regret here. The argument for welfare
regret goes similarly. The revenue minus free allocations satisfies,

$\text{Revenue}(H)=\mathbb{E}\left[\sum_{t=1}^{H}(1-\eta_{t})\hat{\gamma}_{t}\right]\geq\mathbb{E}\left[\sum_{t=1}^{H}(1-\eta_{t})(\gamma_{t}-\Delta_{t})\right]$

$\geq\mathbb{E}\left[\sum_{t=1}^{H}\gamma_{t}\right]-\mathbb{E}\left[\sum_{t=1}^{H}\eta_{t}\right]-\mathbb{E}\left[\sum_{t=1}^{H}\Delta_{t}\right]$

We conclude that,

$\text{Regret}(H)\leq\mathbb{E}\left[\sum_{t=1}^{H}\eta_{t}\right]+\mathbb{E}\left[\sum_{t=1}^{H}\Delta_{t}\right]$

We call $N_{t}=\sum_{k=1}^{t}\eta_{k}$ the expected number of exploration
rounds and $N_{t}(i)$ the number of exploration rounds given to the
$i^{\text{th}}$ agent. Now we consider events when they are near their
expectation. We use the following multiplicative Chernoff bound for sums of
random variables bounded to the unit-interval
222https://en.wikipedia.org/wiki/Chernoff_bound:

$\mathbb{P}(N_{t}\leq(1-\delta)\mu)\leq e^{-\delta^{2}\mu/2}$

We define the event $\mathcal{A}=\\{N_{t}\geq\frac{1}{2}\mathbb{E}[N_{t}]\\}$
to capture the situation where the empirically observed number of exploration
rounds is not too far below the expectation. Using the Chernoff bound we see,

$\mathbb{P}(\lnot\mathcal{A})\leq e^{-\mathbb{E}[N_{H}]/8}$

We also the event $\mathcal{B}=\\{N_{t}(i)\geq\frac{1}{2n}N_{t}\\}$ that the
number of exploration rounds for a particular agent $i$ is not too far from
the expectation. Using the Chernoff bound once again we have,

$\mathbb{P}(\lnot\mathcal{B})\leq e^{-N_{H}/8n}\\\
\Rightarrow\mathbb{P}(\lnot\mathcal{B}|\mathcal{A})\leq
e^{-\mathbb{E}[N_{H}]/16n}$

Conditioned on both of these events we have,

$\mathbb{E}[\Delta_{t}]\leq\mathbb{E}[\Delta_{t}|\mathcal{A}\land\mathcal{B}]\cdot\mathbb{P}(\mathcal{A}\land\mathcal{B})+1\cdot\mathbb{P}(\mathcal{A})\cdot\mathbb{P}(\lnot\mathcal{B}|\mathcal{A})+1\cdot\mathbb{P}(\lnot\mathcal{A})$
(7)

We will use the fact that conditional on $\mathcal{A}\land\mathcal{B}$ we have
$\mathbb{E}[N_{t}(i)]\geq\frac{t\cdot\eta_{t}}{4n}$. There will be two cases
to consider. The first corresponds to a slow learning algorithm, and the
second to a fast learning algorithm.

Case 1: We have $\mathbb{E}[\Delta_{t}|N_{t}(i)=t]=O(\sqrt{\log(t)/t})$.

Without loss of generality, we can scale the bound and shift $t$ by a constant
so that we can assume $\mathbb{E}[\Delta_{t}|N_{t}(i)=t]\leq\sqrt{\log(t)/t}$.
From this, we deduce that:

$\mathbb{E}[\Delta_{t}|\mathcal{A}\land\mathcal{B}]\leq\sqrt{\frac{4n\log\left(\frac{t\eta_{t}}{4n}\right)}{t\eta_{t}}}\leq\sqrt{\frac{4n\log(t/4)}{t\eta_{t}}}$
$\Rightarrow\mathbb{E}[\Delta_{t}]\leq\sqrt{\frac{4n\log(t/4)}{t\eta_{t}}}+e^{-t\eta_{t}/8}+e^{-t\eta_{t}/16n}$

where in the last step we substitute into Eq. 7. For $t\geq 4e$ we have,

$\sqrt{\frac{4n\log(t/4)}{t\eta_{t}}}\geq\sqrt{\frac{4n}{t\eta_{t}}}$

Therefore,

$\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/16n}}{\sqrt{\frac{4n\log(t/4)}{t\eta_{t}}}}\leq\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/16n}}{\sqrt{\frac{4n}{t\eta_{t}}}}=\sqrt{\frac{2}{e}}$
$\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/8}}{\sqrt{\frac{4n\log(t/4)}{t\eta_{t}}}}\leq\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/8}}{\sqrt{\frac{4n}{t\eta_{t}}}}=\sqrt{\frac{1}{n\cdot
e}}$

Subsequently, we have for $t\geq 4e$ that,

$\mathbb{E}[\Delta_{t}]\leq c\cdot\sqrt{\frac{n\log(t)}{t\eta_{t}}}\ ,\quad
c=2\cdot\left(1+\sqrt{2/e}+\sqrt{1/e}\right)$

Now we take $\eta_{t}=t^{-1/3}\cdot(n\log(t))^{(1+2\epsilon)/3}$ and then for
$t\geq 4e$ we arrive at,

$\mathbb{E}[\eta_{t}]=t^{-1/3}\cdot(n\log(t))^{(1+2\epsilon)/3}$
$\mathbb{E}[\Delta_{t}]\leq
c\cdot\sqrt{\frac{n\log(t)}{t^{2/3}\cdot(n\log(t))^{(1+2\epsilon)/3}}}=c\cdot
t^{-1/3}(n\log(t))^{(1-\epsilon)/3}$

We see from an integration that
$\text{Regret}(H)=O(H^{2/3}\cdot\log(H)^{(1+2\epsilon)/3})$ which establishes
the result. Since
$\Sigma_{t}\mathbb{E}[\Delta_{t}]=o(\Sigma_{t}\mathbb{E}[\eta_{t}])$ this
regret bound is consistent with the assumption in Theorem 5.1.

Case 2: We have $\mathbb{E}[\Delta_{t}|N_{t}(i)=t]=O(\log(t)/t)$.

Without loss of generality, we can scale the bound and shift $t$ by a constant
so that we can assume $\mathbb{E}[\Delta_{t}|N_{t}(i)=t]\leq\log(t)/t$. From
this we deduce that,

$\mathbb{E}[\Delta_{t}|\mathcal{A}\land\mathcal{B}]\leq\frac{4n\log\left(\frac{t\eta_{t}}{4n}\right)}{t\eta_{t}}\leq\frac{4n\log(t/4)}{t\eta_{t}}$
$\Rightarrow\mathbb{E}[\Delta_{t}]\leq\frac{4n\log(t/4)}{t\eta_{t}}+e^{-t\eta_{t}/8}+e^{-t\eta_{t}/16n}$

where in the last step we substitute into Eq. 7. For $t\geq 4e$ we have,

$\frac{4n\log(t/4)}{t\eta_{t}}\geq\frac{4n}{t\eta_{t}}$

Therefore,

$\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/16n}}{\frac{4n\log(t/4)}{t\eta_{t}}}\leq\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/16n}}{\frac{4n}{t\eta_{t}}}=\frac{4}{e}$ $\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/8}}{\frac{4n\log(t/4)}{t\eta_{t}}}\leq\sup_{t\geq
4e}\frac{e^{-t\eta_{t}/8}}{\frac{4n}{t\eta_{t}}}=\frac{2}{n\cdot e}$

Subsequently, we have for $t\geq 4e$ that:

$\mathbb{E}[\Delta_{t}]\leq c\cdot\frac{n\log(t)}{t\eta_{t}}\ ,\quad
c=4\cdot\left(1+6/e\right)$

Now we take $\eta_{t}=t^{-1/2}\cdot(n\log(t))^{(1+\epsilon)/2}$ and for $t\geq
4e$ we arrive at,

$\mathbb{E}[\eta_{t}]=t^{-1/2}\cdot(n\log(t))^{(1+\epsilon)/2}$
$\mathbb{E}[\Delta_{t}]\leq
c\cdot\frac{n\log(t)}{t^{1/2}\cdot(n\log(t))^{(1+\epsilon)/2}}=c\cdot
t^{-1/2}(n\log(t))^{(1-\epsilon)/2}$

We see from an integration that
$\text{Regret}(H)=O(H^{1/2}\cdot\log(H)^{(1+\epsilon)/2})$ which establishes
the result. Since
$\Sigma_{t}\mathbb{E}[\Delta_{t}]=o(\Sigma_{t}\mathbb{E}[\eta_{t}])$ this
regret bound is consistent with the assumption in Theorem 5.1.

∎

###  B.2 Proof of theorem 5.5

See 5.5

To get the result, we need to show linear regression converges and that it
converges to expected utility. Here we’ll establish that the expectation of
the reports does in fact equal expected utility. Later we will establish
convergence of the regression to expected utility.

See 5.6

###### Proof.

Given any measurable function $u:\Omega\to[0,\infty]$ from a sample space
$\Omega$ to the nonnegative real numbers, there is a sequence of nonnegative
simple functions $u_{t}$ increasing pointwise to $u$. This means we can
construct a sequence of nonnegative simple random variables $u_{t}$,
increasing to $u$. To proceed, we look at the range set $R_{t}$ of the
$u_{t}$, which will be of finite cardinality. Moreover, each element in the
range will be separated with some margin $\epsilon>0$. Index these sets with
$R_{t}(k)$ in order taking $R_{t}(0)$ to be a greatest lower bound. We have,

$\sum_{k=R_{t}(0)}^{|R_{t}|}P(u_{t}\geq
R_{t}(k))=\sum_{k=R_{t}(0)}^{|R_{t}|}\sum_{m=k}^{|R_{t}|}P(m+\epsilon>u_{t}\geq
m)$ $=\sum_{m=R_{t}(0)}^{|R_{t}|}\sum_{k=1}^{m}P(m+\epsilon>u_{t}\geq m)$
$=\sum_{m=R_{t}(0)}^{|R_{t}|}mP(m+\epsilon>k\geq
m)=\sum_{m=R_{t}(0)}^{|R_{t}|}\int_{[m,m+\epsilon)}md\nu$
$=\sum_{m=R_{t}(0)}^{|R_{t}|}\int_{[m,m+\epsilon)}u_{t}d\nu=\int
u_{t}d\nu=\mathbb{E}[u_{t}]$

Our construction also implies $\mathbb{P}(u_{t}\geq z)$ increases to
$\mathbb{P}(u\geq z)$ monotonically with respect to the sequence. It is not
hard to see that this sequence of functions is measurable. Therefore, by the
monotone convergence theorem,

$\mathbb{E}[u]=\lim_{n\to\infty}\int_{0}^{\infty}\mathbb{P}(u_{t}\geq
z)dz=\int_{0}^{\infty}\mathbb{P}(u\geq z)dz$

which concludes the proof. ∎

For the main result. It is relatively well-known that well-specified linear
regression converges in its predictions.

######  Lemma B.1.

([Györfi et al., 2002]) Let $\hat{\mu}_{t}$ be an empirical least squares
estimator for a linear valuation function $\mu$, which may depend on the input
data $w_{1},\ldots,w_{t}$. Denote the $L_{2}(\nu)$ norm with respect to the
probability measure $\nu$ of the data as $\|\cdot\|$. Then,

$\mathbb{E}[\|\hat{\mu}_{t}-\mu\|^{2}]\leq c\cdot\cfrac{(\log(t)+1)\cdot
d}{t}$

for some constant $c$.

Since $\nu$ is a probability measure, by the monotone property for
$L_{p}(\nu)$ norms we have that,

$\mathbb{E}[\|\hat{\mu}_{t}-\mu\|]\leq\sqrt{\mathbb{E}[\|\hat{\mu}_{t}-\mu\|^{2}]}\leq\sqrt{c\cdot\cfrac{(\log(t)+1)\cdot
d}{t}}$

Recall that $\Delta_{t}$ is the expected maximum error of the learning
algorithm over all the agents $i\in[n]$ with respect to exploration round
data. A simple bound works for our purposes,

$\Delta_{t}\leq
n\cdot\mathbb{E}[\|\hat{\mu}_{t}-\mu\|]=O\left(\sqrt{\cfrac{\log(t)}{t}}\right)$

so with $\eta_{t}=t^{-1/3}\cdot(n\log(t))^{(1+2\epsilon)/3}$ we satisfy the
necessary condition to invoke Theorem 5.1.


# METHOD TO CLASSIFY SKIN LESIONS USING DERMOSCOPIC IMAGES

Hemanth Nadipineni
Department of Computer Science
Indian Institute of Information Technology, Design and Manufacturing,
Kancheepuram
Chennai, Tamil Nadu, India
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
https://github.com/callmehetch/SkinLesion/blob/master/3b_unet.ipynb

###### Abstract

Skin cancer is the most common cancer in the existing world constituting one-
third of the cancer cases. Benign skin cancers are not fatal, can be cured
with proper medication. But it is not the same as the malignant skin cancers.
In the case of malignant melanoma, in its peak stage, the maximum life
expectancy is less than or equal to 5 years. But, it can be cured if detected
in early stages. Though there are numerous clinical procedures, the accuracy
of diagnosis falls between 49% to 81% and is time-consuming. So, dermoscopy
has been brought into the picture. It helped in increasing the accuracy of
diagnosis but could not demolish the error-prone behaviour. A quick and less
error-prone solution is needed to diagnose this majorly growing skin cancer.
This project deals with the usage of deep learning in skin lesion
classification. In this project, an automated model for skin lesion
classification using dermoscopic images has been developed with
CNN(Convolution Neural Networks) as a training model. Convolution neural
networks are known for capturing features of an image. So, they are preferred
in analyzing medical images to find the characteristics that drive the model
towards success. Techniques like data augmentation for tackling class
imbalance, segmentation for focusing on the region of interest and 10-fold
cross-validation to make the model robust have been brought into the picture.
This project also includes usage of certain preprocessing techniques like
brightening the images using piece-wise linear transformation function,
grayscale conversion of the image, resize the image. This project throws a set
of valuable insights on how the accuracy of the model hikes with the bringing
of new input strategies, preprocessing techniques. The best accuracy this
model could achieve is 0.886

_K_ eywords Skin Lesion Classification $\cdot$ Deep Learning $\cdot$
Convolutional Neural Network

##  1 Introduction

Skin lesion refers to the abnormality on the skin. Skin lesions may be of type
cancerous, allergic, etc. Among these, cancer-causing skin lesions are
hazardous to health. Some forms of these cancerous lesions are deadly.
Melanoma is considered to be the one with a high mortality rate of 8% among
the cancerous lesions. The occurrence rate of melanoma is increasing day by
day [1].

Skin cancers are classified majorly into two types. They are

  * •

Melanoma Skin Cancers (MSC),

  * •

Non-Melanoma Skin Cancers (NMSC).

In total, there are 8 types of cancerous skin lesions and are classified as
follows :

Figure 1: Classification of skin lesions

Clinically, skin cancers are diagnosed based on ABCDE rule [2]. Where,

  * •

A - Asymmetry

  * •

B - Border irregularity

  * •

C - Color of lesion

  * •

D - Diameter of lesion

  * •

E - Enlarging lesion.

This above diagnosis can be done through the naked eye. But most skin cancers
mimic each other with ABCDE properties. So, there is a possibility of making
an error. And there are other clinical procedures like biopsy, etc and are
error-prone. On average, the accuracy of the specialists ranges between 49% to
81%, with one-third of melanomas are wrongly predicted as benign lesions [3,
4, 5, 6, 7]. So dermoscopy came into existence.

Dermoscopy is one of the most important techniques to examine skin lesions and
can capture high-resolution images of the skin escaping the interruption of
surface reflections. Dermoscopy helped in making more accurate decisions
compared to traditional clinical procedures [8].

Dermoscopy increased the sensitivity, specificity but could not eradicate the
probability of making errors and all the above clinical procedures are time-
consuming, requires human efforts. Early detection of melanoma can save the
lives of people. So, a technique is to be created which is fast and less
error-prone.

On the other hand, machine learning, especially deep learning-based algorithms
have become a methodology of choice for analyzing medical images. A deep
convolution algorithm can be more objective, accurate, and reproducible when
it has been well trained. So, this related study lead to the conclusion that
developing an automated model for skin cancer classification using dermoscopic
images can aid us in taking quicker, error-less decisions.

This project deals with developing an automated model for skin lesion
classification involves the creation of different models and usage of
different strategies. The dataset is class imbalanced, so data augmentation is
done using affine transformations( rotate, scale, etc) to generate sufficient
numbers of images to tackle class imbalance. Skin lesion images have been
segmented to the lesion part so that the model is made to concentrate more on
the lesion region and exclude the surrounding healthy skin. 10-fold cross-
validation has been brought into the picture. Cross-validation makes the model
robust. The accuracy will be the mean of the accuracy of all the folds of
data.

###  1.1 Motivation

  * •

Manual interpretation demands high time consumption and is highly prone to
mistakes.

  * •

Early detection and treatment can save more than 95% of people.

  * •

Automated skin lesion classification model makes the work easier and faster.

###  1.2 Objectives of the work

  * •

To propose a deep learning model to automatically classify skin lesions.

  * •

To validate the proposed model for robustness.

##  2 Literature Work

Initially, the major work was done on developing an automated model for
diagnosing lesions based on ABCDE properties. In these models [9, 10, 11],
they converted these ABCDE properties of each image into numerical figures,
generated a cumulative score by adding all the numerical figures of each
property and diagnose the images based on the cumulative score. There is
another developed on a seven-point checked checklist [12], considered to be an
improvisation of ABCDE properties.

Later, the work was done on the classification of skin lesion images using
Raman spectroscopy. Raman spectroscopy is a noninvasive optical procedure fit
for estimating vibrational methods of biomolecules inside practical tissues.
In this study, they [13, 14] tested the application of an integrated Raman
spectroscopy real-time framework for the in vivo diagnosis of skin cancer

In recent times, the major work was carried out on developing models based on
CNN variants (ResNet, EfficientNets, SENet, so on) for classifying skin
lesions using dermoscopic images [15, 16, 17]. They preprocessed the images to
eliminate the not interesting regions like eliminating dark circles in the
images around the lesion region, contrast balancing, etc. They used data
augmentation, random cropping strategies for tackling class imbalance. 5-fold
cross-validation, Ensembling strategy for making the model robust.

Let’s have a broader look at these three models as they include state-of-the-
art CNN architectures, intriguing input strategies, and modern robust training
techniques.

The present models are evaluated on ISIC 2019 dataset

###  2.1 Input and Expected Output

The input dataset is ISIC 2019 dataset and it consists of dermoscopic images
related to ’8’ different skin lesions. The expected output of the images is a
one-hot vector of size ’8’

###  2.2 Preprocessing

There are certain images in which lesion is surrounded by black color. So this
part of the image with pixel value ’0’ place no role in learning the
characteristics of the images. So, the darker parts of the image area to be
removed. This helps in two ways - i) Helps us concentrate more on a region of
interest. ii) Decreasing the size of the image lessens the computation time.

This task is achieved in the following steps: i)Take the image which is
surrounded completely by black color. ii) Find a threshold which
highlights(make pixel value as ’1’) the lesion region and darkens(make pixel
value as ’0’) the surrounded black region when the value greater than equal to
the threshold is put as ’1’ and rest as ’0’. iii) Find the major axis
endpoints and minor axis endpoints of the highlighted regions. extract the
rectangular region whose length is equal to the length of the major axis,
breadth is equal to the length of the minor axis.

The color contrast of all the images differ a lot so apply Minkowski norm with
p = 6 to make the contrast of all the images to as similar as possible

$d(x,y)=(\sum_{i=0}^{n-1}|x_{i}-y_{i}|^{p})^{1/p}$

##  3 Deep Learning Models

###  3.1 Architecture

These papers involved state-of-the-art deep CNN architectures for training.
They are i) EfficientNets: This family of models includes eight different
models that are structurally similar and are pretrained on the ImageNet
dataset. ii)SENet154, iii) ResNet.

The input sizes of all these networks are different. The depth of a network
increases with the increase in the size of the input image.

The count of images of each class is not the same. When a model is trained
with this unequal count dataset, the model gets biased in classifying the
images. The model may end up predicting the given image as the class with high
image count as it learned more characteristics related to that class. So this
data imbalance should be tackled to generalize your model. To augment the
data.

###  3.2 Data Augmentation

The data augmentation is done through affine transformations and it involves:
i) Random brightness, ii) contrast changes, iii) random flipping, iv) random
rotation, v) random scaling, vi) random shear, vii) CutOut - This involves
creating holes of different sizes on the images i.e. technically making a
random portion of image inactive.

The additional data of ’995’ healthy dermoscopic images from the 7-point
dataset are also added to the dataset. The data augmentation technique helps
in creating additional so that training dataset can be balanced and training
the model with wide varieties of skin lesion image variations.

###  3.3 Input Strategy

The complete training dataset is segregated into five folds. Each fold
consists of images related to one particular class. Two ways of passing inputs
have been followed: i)Same-sized cropping: Patches of equal sizes are taken
from the preprocessed images and are trained. ii) Random-sized cropping:
Patches of random sizes are taken from the preprocesses images and are scaled
to the required size are trained.

####  3.3.1 Training

All these models are trained using ’Adam’ optimizers, all the other parameters
like batch_size and learning are adjusted based on the GPU memory requirements
of each architecture.

Internal evaluation is based on the mean values of sensitivities.

$S=1/C\sum_{i=1}^{C}TP_{i}/Tp_{i}+FN_{i}$

where,
TP = True positives, FN = Fales negatives, C = number of classes.

###  3.4 Ensembling

They create large ensemble out of all the trained models. An optimal subset of
models is selected based on cross-validation performance. Top configurations
of our choice can be selected and used for prediction.

###  3.5 Literature Table

Title | Authors | Dataset | Target Classes
---|---|---|---
| Classification of malignant
---
melanoma and benign skin
lesions: implementation of
automatic abcd rule
| R. Kasmi,
---
K. Mokrani
EDRA [9] |  | Melanoma,
---
benign skin
lesions
| Melanoma recognition
---
framework based on
expert definition of
abcd for dermoscopic images
| Q. Abbas,
---
M. Emre Celebi,
I. F. Garcia,
W. Ahmad.
EDRA [10] | Melanoma
| Multi-Category Skin Lesion
---
Diagnosis Using Dermoscopy
Images and Deep CNN
| Steven Zhou1,
---
Yixin Zhuang,
Rusong Meng
ISIC 2019 |  | Melanoma, Melanocytic Nevus
---
Basal Cell Carcinoma, Actinic Keratosis,
Benign Keratosis, Dibrofitoma,
Vascular Lesion,
Squamous cell Carcinoma
| Automatic diagnosis of
---
melanoma: a software
system based on the
7-point check-list
| G. Di Leo,
---
A. Paolillo,
P. Sommella,
G. Fabbrocini
public [12] | Melanoma
| In vivo nonmelanoma skin
---
cancer diagnosis using
raman microspectroscopy
| C. A. Lieber,
---
S. K. Majumder,
D. L. Ellis,
D. D. Billheimer,
A. Mahadevan-Jansen
IRB(patients) [13] |  | Melanoma, Melanocytic Nevus
---
Basal Cell Carcinoma, Actinic Keratosis,
Benign Keratosis, Dibrofitoma,
Vascular Lesion,
Squamous cell Carcinoma
| Real-time raman
---
spectroscopy for in vivo
skin cancer diagnosis
| H. Lui, J. Zhao,
---
D. McLean,,
H. Zeng
| Vancouver General
---
Hospital Skin Care
Centre(patients) [14]
| Melanoma, Melanocytic Nevus
---
Basal Cell Carcinoma, Actinic Keratosis,
Benign Keratosis, Dibrofitoma,
Vascular Lesion,
Squamous cell Carcinoma
| Skin lesion classification
---
using ensembles of multi-
resolution efficientnets
with meta data
| N. Gessert,
---
M. Nielsen,
M. Shaikh, R. Werner,
A. Schlaefe
ISIC 2019 [15] |  | Melanoma, Melanocytic Nevus
---
Basal Cell Carcinoma, Actinic Keratosis,
Benign Keratosis, Dibrofitoma,
Vascular Lesion,
Squamous cell Carcinoma

##  4 Proposed method

This project involves development of three models -

  * •

Model - 1

  * •

Model - 2 :

    * –

CNN Model - 1 - One Path

    * –

CNN Model - 2 - Dual Path

where, model - 2 involves two CNN Models. The ’Model-1’ takes the original
images as input, ’Model-2’ with ’CNN Model - 1’ takes image formed with the
multiplication of original image and segmented mask as an input ans ’Model -
2’ with ’CNN Model - 2’ takes both original image and segmented mask as
inputs. There is the usage of different input strategies, preprocessing
techniques, and training techniques. The detailed description is as follows :

###  4.1 Input and Expected Output

The input is ISIC 2019 dataset and the expected output is ’one-hot vector’ of
size ’8’as explained above.

Figure 2: Input and expected ouput of the model developed

The dataset is an accumulation of 3 different datasets.

  * •

Ham_1000 (600 x 450) pixels.

  * •

BCN_2000 (1024 x 1024) pixels.

  * •

MSK (1024 x 1024) pixels.

The total count of images is 25331. The count of images for each class is
unequal which leads to class imbalance. Each class images’ resolutions differ
from other class images.

MLN MCN BCC AK BK DF VL SCC
4522 12875 3323 867 2624 239 253 628

Challenges faced: i) Class imbalance, ii) varying contrast of images, iii)
Improper images(lesion color is similar to the skin color), iv) Different
resolutions for images.

###  4.2 Classification Model - 1

The ’Model - 1’ involves simple preprocessing of the input image, then pass
the preprocessed image as an input to the CNN model, train the model, and
start classifying the images.

Figure 3: Architecture of Classifcation ’Model - 1’

This model is used to study the effectiveness of CNN in capturing features of
an image for classification. The major concentration is on CNN and it’s
variants as they are good at capturing neighbourhood properties in an image
which is essential in differentiating one skin cancer image from another
image.

####  4.2.1 Preprocessing

All the input images are of various sizes so to pass these images as input to
the model developed they should be of the same size. So, in this phase, all
the images are scaled down to the size 512 x 512 pixels. These images are
further converted into grayscale. This is from our intuition that skin lesion
classification does not depend on the color of the lesion.

Figure 4: shows how an input image is preprocessed to the required form

####  4.2.2 CNN Architecture of Classification ’Model - 1’

This is the architecture of the developed CNN Model :

Figure 5: CNN architecture of Classification ’Model - 1’

The size of the input image is ’512 x 512’ pixels and the kernel size is ’3 x
3’. In the convolution layer - 1, ’64’ filters are used which results in the
creation of ’64’ feature maps and size of the output image shrinks to ’510 x
510’ pixels. Then this output is passed as an input to the max pool layer - 1
with stride ’2’ for the filters, which results in the creation of ’64’ feature
maps whereas the size of the output images shrinks to the size ’255 x 255’.
Similarly, the number of feature maps at convolution layer - 2 is ’32’, the
output image size is ’253 x 253’. The number of feature maps at max pool layer
- 2 is 32, where the size of the output image is ’121 x 121’. At flattening
stage, the count of neurons is 121 x 121 x 32 = ’468512’. The number of a
neuron at Dense - 32 layer is ’32’. The number of neurons at the output layer
is ’8’. The model is trained on 90 percent of images with optimizer ‘Adams’
for ‘20’ epochs. The activation function at convolution and dense layers are
’Relu’.

$x=max(0,x)$

The activation function at output layer is ’softmax’.

$z_{i}=e^{x_{i}}/\sum_{j=1}^{K}e^{x_{j}}$

The loss function used is ’categorical cross_entropy’

$L(\hat{y},y)=-1/N\sum_{i}^{N}[y_{i}\log\hat{y}_{i}+(1-y_{i})\log(1-\hat{y}_{i})]$

The accuracy is 0.204. After going through past work done in the field and
clinical procedure for the diagnosis, there are some important issues where
model-1 least stressed.

The following can be considered as the drawbacks of the above model: i) Not
focussing more on regions of interest, ii) item Color plays a major role in
differentiation, iii) No tackling for class imbalance.

###  4.3 Classification Model-2

This model includes segmentation which helps us in extracting the region of
interest and helps us in concentrating more on the region of interest. The
input for the model is the same as the input for the model-1.

Figure 6: Architecture of Classification Model - 2

####  4.3.1 Preprocessing

The required lesion region of interest is segmented out from the given
dermoscopic images

Figure 7: shows how an input image is preprocessed to the required state

Steps involved are :

  * •

Brighten the image : Color of some class images is so light that there is no
distinction between the colors of skin and the lesion. This task is achieved
using the ‘piece-wise linear transformation’ function.

Figure 8: Piece-wise linear function

Where,

    * –

(r1,s1) , (r2,s2) as parameters stretches intensity levels,

    * –

Decreases intensity of dark pixels,

    * –

Increases intensity of bright pixels.

Logic for piece-wise linear transformation :

def pixelVal(pix, r1, s1, r2, s2):
if (0 <= pix and pix <= r1):
return (s1 / r1)*pix
elif (r1 < pix and pix <= r2):
return ((s2 - s1)/(r2 - r1)) * (pix - r1) + s1
else:
return ((255 - s2)/(255 - r2)) * (pix - r2) + s2

  * •

Grayscale the image : Convert image to grayscale, this makes the lesion region
to stand out with high brightness.

  * •

U-net Architecture : U-net,which is a CNN variant is the state-of-the-art
architecture for segmentation.

Figure 9: Architecture of U-Net

Sample Outputs :

Figure 10: Input images and their predicted segmentation masks

###  4.4 Tackling Data imbalance

The count of images for each class is -

MLN | MCN | BCC | AK | BK | DF | VL | SCC
---|---|---|---|---|---|---|---
4522 | 12875 | 3323 | 867 | 2624 | 239 | 253 | 628

The least size is ‘239’. So picking 239 images from each class, training the
model with a dataset of size ‘239 * 8’ images will not be robust. So,
additional data is to be created, and for that to happen ‘Data augmentation’
should be brought into the picture. The list of the classes with count lesser
than 2000: AK, DF, VL, SCC

So additional data has been created for the above-mentioned classes using
affine transformations. Affine transformations include rotation, cropping,
scaling, flipping(horizontal and vertical), shearing, changing contrast.

###  4.5 K-Fold Cross Validation

K-fold cross-validation technique makes the model robust. This model is made
robust through 10-fold cross-validation in which 1-fold is for validation and
9-other folds are for training.

So, the plan is to train the model on the dataset of 16000 images(2000 images
from each class). The model is to be trained for 10 times by giving a chance
for each fold to act as a validation data set. Find the best model at each
time of training and average the accuracies. The mean accuracy will be the
accuracy of the model.

###  4.6 CNN Model

The CNN model section explains about two developed CNN models. Of which one is
one pathed and another one is dual pathed.

####  4.6.1 CNN Model - 1(One path)

This CNN model -1 takes a multiplied image as an input. The multiplied image
is created by multiplying the original image with its corresponding
segmentation output.

Figure 11: Resultant mutliplied image

The architecture of CNN Model - 1 that makes use of this multiplied image.

Figure 12: Architecture of CNN Model - 1(One path)

The size of the input image is ’256 x 256 x 3’ pixels and the kernel size is
’3 x 3’. In the convolution layer - 1, ’32’ filters are used which results in
the creation of ’32’ feature maps and size of the output image shrinks to ’254
x 254’ pixels. Then this output is passed as an input to the convolution layer
- 2, which results in the creation of ’64’ feature maps whereas the size of
the output images shrinks to the size ’252 x 252’. this output is passed as an
input to the max pooling layer with stride - ’2’, which results in the
creation of ’64’ feature maps whereas the size of the output images shrinks to
the size ’126 x 126’. At flattening stage, the count of neurons is 126 x 126 x
64 = ’1,016,064’. The number of neurons at Dense - 64 layer is ’64’. The
number of neurons at Dense - 32 layer is ’32’. The number of neurons at the
output layer is ’8’.

####  4.6.2 CNN Model - 2(Two path)

This model takes both the original image and segmented images as inputs, there
are parallel similar architectures for processing these inputs into the next
levels. These images are combined at the flattening stage and are connected to
the dense levels.

Figure 13: Architecture of CNN Model - 2(Two Path)

The output is a one-hot vector which points to the predicted class with value
‘1’.

The size of the input image passed to (path - 1) is ’256 x 256 x 3’ pixels and
the kernel size is ’3 x 3’. In the convolution layer - 1, ’32’ filters are
used which results in the creation of ’32’ feature maps and size of the output
image shrinks to ’254 x 254’ pixels. Then this output is passed as an input to
the convolution layer - 2, which results in the creation of ’64’ feature maps
whereas the size of the output images shrinks to the size ’252 x 252’. this
output is passed as an input to the max pooling layer with stride - ’2’, which
results in the creation of ’64’ feature maps whereas the size of the output
images shrinks to the size ’126 x 126’. At flattening stage, the count of
neurons is 126 x 126 x 64 = ’1,016,064’.

At the flattening stage ’path - 1’ which takes the original image as input
produces ’1,016,064’ neurons. So, till the flattening stage architecture is
the same as ’path - 1’. So the number of neurons contributed by ’path - 2’ to
the flattening stage is also ’1,016, 064’. Therefore, the total count of
neurons at the flattening stage is ’2,032,128’.

The number of the neuron at Dense - 64 layer is ’64’. The number of the neuron
at Dense - 32 layer is ’32’. The number of neurons at the output layer is ’8’.

The model is trained on 9-folds of images each time whereas the other one-fold
will acts as a validation data set. The process has to be repeated until each
acts as a validation set exactly once. The model is trained with optimizer
‘Adams’ for ‘2’ epochs. The batch_size is 75. The initialization of weights is
Keras default initialization i.e. Xavier uniform initialization. The
activation function at convolution and dense layers are ’Relu’.

$x=max(0,x)$

The activation function at output layer is ’softmax’.

$z_{i}=e^{x_{i}}/\sum_{j=1}^{K}e^{x_{j}}$

The loss function used is ’categorical cross_entropy’

$L(\hat{p},p)=-1/N\sum_{i}^{N}[p_{i}\log\hat{p}_{i}+(1-p_{i})\log(1-\hat{p}_{i})]$

The accuracy of the model is mean of the accuracies of all the k-models.

$Acc=(\sum_{i=1}^{K}Acc_{i})/K$

##  5 Results

The following table describes the accuracy of the models with different ways
of attempt.

Ways of attempt | Model - 1 |  | Model - 2 with
---
one path -CNN model
| Model-2 with
---
two path CNN model
| Without
---
Segmentation
0.204 | N.A | N.A
| With
---
Segmentation
0.412 | 0.561 | 0.576
| With Segmentation,
---
Augmented data
0.483 | 0.681 | 0.732
| With Segmentation,
---
Augmented data
10-fold cross validation
0.583 | 0.814 | 0.886

Accuracy measure = TP/( TP + FN)
Where,
True positive = predicting the true class correctly,
False negative = predicting the true class incorrectly.

When K-fold cross-validation is used accuracy measure is not just the accuracy
of one model but the mean of the accuracies of the K-models.

So, the accuracy of the model with K-fold cross-validation is

$Acc=(\sum_{i=1}^{K}Acc_{i})/K$

This table shows the comparison of this project with the state-of-the-art
models in terms of accuracy.

Model | Accuracy
---|---
| Skin lesion classification
---
using loss balancing and ensemble
of multi-resolution efficient nets [15]
0.926
| Multi-Category Skin Lesion
---
Diagnosis using dermoscopic images
and deep CNN models [16]
0.917
| Classification Model - 2
---
with two path CNN model
(The present project)
0.886
| ISIC 2019 Skin lesion analysis
---
towards melanoma detection [18]
0.851
| Skin lesion analysis towards
---
melanoma detection using siamese
network
0.832

###  5.1 Inferences

The accuracy of ’Model - 1’ is less than in all ways compared to ’Model - 2
with one path CNN model’ and ’Model - 2 with two path CNN model’. The
explanation for this kind of behaviour can be made from the number of neurons
involved in the training of the model. The number of neurons at the flattening
layer for i) ’Model - 1’ is ’4,68,512’, ii) ’Model - 2 with one path CNN
model’ is 1,016,064. iii) ’Model - 2 with two path CNN model’ is 2,032,128.
But there is a significant difference in the number of neurons between ’Model
- 2 with one path CNN model’ and ’Model - 2 with two path CNN model’ whereas
there is no significant difference in the accuracy. So, there is threshold
between ’4,68,512’ - ’1,016,064’ that surges up the accuracy but there is no
threshold between ’1,016,064’ - ’2,032,128’.

There is an improvement in the accuracy of injecting segmentation into the
model. This is happening because when the model is trained with an original
image without segmentation, the model tends to learn about the unwanted
characteristics of lesion classification. From the [fig 3.1] we can observe
that size of the skin lesion region is small compared to the image size. So,
to concentrate on the region of interest, the unwanted portion is to be
eliminated. So when the image the original is multiplied with the segmented
mask, the pixel values of an unwanted portion is set to ’0’. So they don’t
involve in training.

There is an improvement in accuracy when data augmentation is involved. This
is because the model is to made to learn on multiple skin variations. So this
helped model to learn variety characteristics related to skin lesions.
Therefore, it conveys that model with data augmentation tend to learn more
distinguishing characteristics features rather like a model without data
augmentation.

Involving segmentation, data augmentation, and other preprocessing techniques
can improve the accuracy of the model. But that model cannot give significant
results with the testing data until it is robust. The model trained can become
biased towards a certain class. So, to develop a generalized model, it should
be trained with a balanced data set.

##  6 Conclusion and Future Work

###  6.1 Conclusion

In this project of developing an automated model for skin lesion
classification, major work has done on improving the accuracy of the model by
bringing in new techniques into the model.

It is clear from the results, that there is an increment in the accuracy of
bringing new strategies into the picture. Though the CNN model is two-layered,
it is inferring that the effective preprocessing, input, and training
strategies can bring a significant change in the model’s accuracy. The
segmentation model ’U-net’ worked well.

###  6.2 Future Work

The developed ’model-2 with CNN mode-1’ which is of depth two layers produced
significant results. But bringing in the deep CNN models will be very helpful
in learning the distinguishing characteristics of the skin lesions from
dermoscopic images.

Work extensions -

  * •

Bringing in deep CNN variants (EfficientNets, SENet, ResNet, so on)

  * •

Involving ensembling methods can create a significant imapact in improving the
accuracy.

## References

  * [1] Alfred W Kopf, Darrell S Rigel, and Robert J Friedman.  The rising incidence and mortality rate of malignant melanoma.  The Journal of dermatologic surgery and oncology, 8(9):760–761, 1982.
  * [2] Robert J Friedman, Darrell S Rigel, and Alfred W Kopf.  Early detection of malignant melanoma: the role of physician examination and self-examination of the skin.  CA: a cancer journal for clinicians, 35(3):130–151, 1985.
  * [3] Andrew R MacKenzie-Wood, Gerry W Milton, and John W de Launey.  Melanoma: accuracy of clinical diagnosis.  Australasian journal of dermatology, 39(1):31–33, 1998.
  * [4] Caron M Grin, Alfred W Kopf, Bruce Welkovich, Robert S Bart, and Marcia J Levenstein.  Accuracy in the clinical diagnosis of malignant melanoma.  Archives of dermatology, 126(6):763–766, 1990.
  * [5] Maria Miller and A Bernard Ackerman.  How accurate are dermatologists in the diagnosis of melanoma? degree of accuracy and implications.  Archives of dermatology, 128(4):559–560, 1992.
  * [6] CA Morton and RM Mackie.  Clinical accuracy of the diagnosis of cutaneous malignant melanoma.  The British journal of dermatology, 138(2):283–287, 1998.
  * [7] Bernt Lindelöf and Mari-Anne Hedblad.  Accuracy in the clinical diagnosis and pattern of malignant melanoma at a dermatological clinic.  The Journal of dermatology, 21(7):461–464, 1994.
  * [8] Giuseppe Argenziano, Susana Puig, Zalaudek Iris, Francesco Sera, Rosamaria Corona, Mercè Alsina, Filomena Barbato, Cristina Carrera, Gerardo Ferrara, Antonio Guilabert, et al.  Dermoscopy improves accuracy of primary care physicians to triage lesions suggestive of skin cancer.  Journal of Clinical Oncology, 24(12):1877–1882, 2006.
  * [9] Reda Kasmi and Karim Mokrani.  Classification of malignant melanoma and benign skin lesions: implementation of automatic abcd rule.  IET Image Processing, 10(6):448–455, 2016.
  * [10] Qaisar Abbas, M Emre Celebi, Irene Fondón Garcia, and Waqar Ahmad.  Melanoma recognition framework based on expert definition of abcd for dermoscopic images.  Skin Research and Technology, 19(1):e93–e102, 2013.
  * [11] Nilkamal S Ramteke and Shweta V Jain.  Abcd rule based automatic computer-aided skin cancer detection using matlab.  International Journal of Computer Technology and Applications, 4(4):691, 2013.
  * [12] Giuseppe Di Leo, Alfredo Paolillo, Paolo Sommella, and G Fabbrocini.  Automatic diagnosis of melanoma: a software system based on the 7-point check-list.  In 2010 43rd Hawaii international conference on system sciences, pages 1–10. IEEE, 2010.
  * [13] Chad A Lieber, Shovan K Majumder, Darrel L Ellis, D Dean Billheimer, and Anita Mahadevan-Jansen.  In vivo nonmelanoma skin cancer diagnosis using raman microspectroscopy.  Lasers in Surgery and Medicine: The Official Journal of the American Society for Laser Medicine and Surgery, 40(7):461–467, 2008.
  * [14] Harvey Lui, Jianhua Zhao, David McLean, and Haishan Zeng.  Real-time raman spectroscopy for in vivo skin cancer diagnosis.  Cancer research, 72(10):2491–2500, 2012.
  * [15] Nils Gessert, Maximilian Nielsen, Mohsin Shaikh, René Werner, and Alexander Schlaefer.  Skin lesion classification using ensembles of multi-resolution efficientnets with meta data.  MethodsX, page 100864, 2020.
  * [16] Quoc V. Le Mingxing Tan.  Efficientnet: Rethinking model scaling for convolutional neural networks.  ICML 2019, 2019.
  * [17] Giuseppe Argenziano, HP Soyer, V De Giorgi, Domenico Piccolo, Paolo Carli, and Mario Delfino.  Interactive atlas of dermoscopy (book and cd-rom).  2000\.
  * [18] Linlin Shen Yuexiang Li.  Skin lesion analysis towards melanoma detection using deep learning network.  arXiv preprint arXiv:1703.00577, 2017.