#  $\text{O}^{2}$PF: Oversampling via Optimum-Path Forest for Breast Cancer
Detection ††thanks: ∗Authors contributed equally. ††thanks: The authors would
like to thank FAPESP grants #2013/07375-0, #2014/12236-1, #2019/18287-0, and
#2019/07665-4, as well as CNPq grants #427968/2018-6 and #307066/2017-7.

Leandro A. Passos∗, Danilo S. Jodas∗, Luiz C. F. Ribeiro∗, Thierry Pinheiro,
João P. Papa  Department of Computing
São Paulo State University
Bauru, Brazil
{leandro.passos, luiz.felix<EMAIL_ADDRESS>{danilojodas,
<EMAIL_ADDRESS>
###### Abstract

Breast cancer is among the most deadly diseases, distressing mostly women
worldwide. Although traditional methods for detection have presented
themselves as valid for the task, they still commonly present low accuracies
and demand considerable time and effort from professionals. Therefore, a
computer-aided diagnosis (CAD) system capable of providing early detection
becomes hugely desirable. In the last decade, machine learning-based
techniques have been of paramount importance in this context, since they are
capable of extracting essential information from data and reasoning about it.
However, such approaches still suffer from imbalanced data, specifically on
medical issues, where the number of healthy people samples is, in general,
considerably higher than the number of patients. Therefore this paper proposes
the $\text{O}^{2}$PF, a data oversampling method based on the unsupervised
Optimum-Path Forest Algorithm. Experiments conducted over the full
oversampling scenario state the robustness of the model, which is compared
against three well-established oversampling methods considering three breast
cancer and three general-purpose tasks for medical issues datasets.

###### Index Terms:

Data imbalance, Oversampling, Optimum-Path Forest.

##  I Introduction

Computer-Aided Diagnosis (CAD) systems aim at helping physicians to quickly
report better diagnosis to patients, thus representing an essential step
towards dangerous disease accurate diagnosis. Besides, intelligent-based CAD
systems have successfully employed machine learning techniques, a promising
subfield of artificial intelligence, to tackle complicated problems that
demand knowledge and reasoning about the subject. Regarding the latter,
several works were developed in the last few years to aid detecting
atherosclerosis [1], Parkinson’s disease [2], and breast cancer [3], to name a
few.

Breast cancer is a dangerous illness, affecting millions of women, as well as
few men, around the world. According to the World Health Organization, such a
disease was responsible for the death of approximately $627,000$ women in
$2018$ worldwide [4]. Therefore, early diagnosis is crucial to effectively
prevent its progress, consequently making it possible to elaborate more
efficient treatment plans. In general, standard breast cancer diagnosis
consists of a visual analysis performed by professionals aiming to identify
possible abnormalities (e.g., nodules), which may indicate cancer risk signs.
Once identified, it is possible to extract relevant measures from such
nodules, assisting physicians to judge the presence or absence of cancerous
tissue.

Many image processing-based algorithms have also been proposed to help in such
tasks [5, 6, 7], as well as machine learning techniques, which have been
commonly employed for both nodule segmentation and classification. Agarap [8],
for instance, studied the performance of several machine learning techniques
to label a nodule as benign or malignant. Further, Passos et al. [9] developed
a neural network to tell benign from malignant nodules, and to label the
latter according to the most likely cancer type.

Moreover, once the nodules can be seen as abnormalities, their identification
can also be tackled in an unsupervised fashion. In such a direction, Ribeiro
et al. [10] used the unsupervised Optimum-Path Forest (OPF) [11] algorithm to
distinct malignant nodes from benign, obtaining significant results. The
unsupervised Optimum-Path Forest algorithm possesses properties commonly
employed to improve other machine learning techniques, such as the Brainstorm
Optimization [12], as well as to create new techniques, such as the OPF-based
approach for anomaly detection [13] and the Fuzzy OPF classifier [14].

Although the above-mentioned techniques obtained promising results in the
context of breast cancer detection, most of the classification algorithms
usually suffer from imbalanced dataset problems, which arises when the number
of samples among classes differs significantly. In this scenario, the trained
classifier is more likely to label a new sample as belonging to the most
common (majority) class, degrading its performance for the smallest (minority)
class. Moreover, such a situation may degenerate when the dataset presents
outliers. Numerous studies have also been proposed to cope with such a problem
in medical datasets [15, 16, 17]. Therefore, the generation of synthetic
samples for the minority class, which is usually referred to as oversampling,
is recognized as a prominent contribution to rebalancing the dataset for
classifier training purposes, consequently improving their robustness to label
minority class samples correctly. In this context, several powerful
oversampling strategies have been proposed in the literature to tackle such a
problem [18, 19, 20], most of them still presenting difficulties while
enforcing diversity among new synthetic samples, which denotes a problem that
worth to be addressed, since it can improve classifier generalization
properties.

To such an extent, this work proposes an approach to perform oversampling via
the Optimum-Path Forest, hereinafter named $\text{O}^{2}$PF. The method
employs the unsupervised OPF algorithm to capture features intrinsic to the
minority class into different clusters. Further, new training examples are
generated by sampling from a Gaussian distribution parametrized by the cluster
characteristics. Therefore, the main contribution of this paper are twofold:
(i) extending the OPF algorithm capabilities by introducing a novel
oversampling mechanism that enforces synthetic intra-class variability; and
(ii) studying how $\text{O}^{2}$PF can benefit the development of CAD systems
by extensively evaluating it on five tumor-classification and one retinopathy
identification tasks. Finally, the full-balanced datasets are employed to
train the OPF classifier, and results, i.e., the accuracy, recall, and
F1-measure, are compared against the ones obtained by the standard training
dataset without oversampling. Additionally, results are compared against three
baselines: SMOTE [18], the Borderline SMOTE [19], and ADASYN [20].

In the remainder of this paper, Section II presents the theoretical background
regarding the unsupervised and supervised OPF algorithm variants, whereas
Section III introduces the proposed approach. Further, Section IV outlines the
experimental setup and Section V discusses experimental results. Finally,
Section VI presents conclusions and future works.

##  II Background

This section presents the theoretical background regarding the unsupervised
and supervised variants of the OPF algorithm.

###  II-A Unsupervised Optimum-Path Forest

Let $\mathcal{D}=\left\\{\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}\right\\}$ be
a dataset such that $\bm{x}_{i}\in\mathbb{R}^{m}$ represents the features
extracted from the $i$-th sample. Further, let
$\mathcal{G}=(\mathcal{D},\mathcal{A}_{k^{\star}})$ be a graph where each node
corresponds to a different feature vector connected to its $k^{\star}$-nearest
neighbors, as defined in the adjacency relationship set
$\mathcal{A}_{k^{\star}}$.

The unsupervised OPF algorithm consists in partitioning the graph through a
competitive process, in which a few samples are marked as “prototypes” and
compete among themselves to conquer the remaining nodes. Such a procedure
partitions the $\mathcal{G}$ into optimum-path trees (OPTs) rooted at a
prototype, each corresponding to a cluster, where a sample is more similar to
the elements of its tree than any other tree. Overall, the process can be
divided into three steps: (i) computing a proper neighborhood size $k^{\star}$
and the adjacency relationship $\mathcal{A}_{k^{\star}}$, (ii) electing the
prototype nodes, and (iii) performing the competition process to partition the
dataset into OPTs.

Regarding the first step, different approaches may be considered. Among
others, Rocha et al. [11] proposed to find $k^{\star}$ by minimizing the
normalized graph cut function, as it takes into account the dissimilarities
between clusters as well as the similarity degree among samples of each
cluster.

Concerning the second step, the algorithm must select the prototypes to form
the root of each OPT (which will ultimately form clusters) to rule the
competition process and conquer the remaining samples in the graph. The
supervised OPF proposed by Papa et al. [21, 22] selects as prototypes the
nearest samples from different classes, found by computing the graph Minimum
Spanning Tree (MST). However, in the unsupervised variant, since labels are
usually unavailable, Rocha et al. [11] proposed to select the prototypes as
the samples located in the center of each cluster. To such an extent, all
samples are assigned a density score
$\rho(\bm{x}_{i}),\;\;\forall\bm{x}_{i}\in\mathcal{D}$, computed through a
Gaussian probability density function (pdf), defined as follows:

$\rho(\bm{x}_{i})=\frac{1}{k^{\star}\sqrt{2\pi\sigma^{2}}}\sum_{\forall\bm{x}_{j}\in\mathcal{A}_{k^{\star}}(\bm{x}_{i})}\exp\left(\frac{-d(\bm{x}_{i},\bm{x}_{j})}{2\sigma^{2}}\right),$
(1)

where $i\neq j$, $\sigma=d_{\max}/3$ and $d_{\max}$ stands for the maximum
arc-weight in $\mathcal{G}$. This formulation considers all adjacent nodes for
density computations, as the Gaussian distribution covers $99.7\%$ of the
samples with distance $d(\bm{x}_{i},\bm{x}_{j})\in[0,3\sigma]$.

After evaluating Equation 1 for each node in the graph, the density values are
used to populate a priority queue in a way that the unsupervised OPF maximizes
the cost of each sample, thus partitioning the graph into OPTs. Such a cost is
defined in terms of paths on $\mathcal{G}$, which is an acyclic sequence of
adjacent samples in $\mathcal{A}_{k^{\star}}$.

Let $\pi_{\bm{x}_{i}}$ be a path with terminus at sample $\bm{x}_{i}$ and
starting from some root $\mathcal{R}(\bm{x}_{j})$, being the latter the set of
all prototype samples. Further, let
$\pi_{\bm{x}_{i}}=\langle\bm{x}_{i}\rangle$ be a trivial path (i.e., a path
containing only one sample), whereas
$\pi_{\bm{x}_{i}}\cdot\langle\bm{x}_{i},\bm{x}_{j}\rangle$ denotes the
concatenation of a path $\pi_{\bm{x}_{i}}$ and the arc
$(\bm{x}_{i},\bm{x}_{j})$ such that $i\neq j$.

In the third step, the algorithm assigns to each path $\pi_{\bm{x}_{i}}$ a
value $f_{\min}(\pi_{\bm{x}_{i}})$ given by a smooth connectivity function
$f_{\min}:{\mathcal{D}}\rightarrow\mathbb{R}^{+}$, which must satisfy some
constraints to ensure the algorithm theoretic correctness [23, 24]. A path
$\pi_{\bm{x}_{i}}$ is considered optimal if ${f_{\min}(\pi_{\bm{x}_{i}})\geq
f_{\min}(\tau_{\bm{x}_{i}})}$ for any other path $\tau_{\bm{x}_{i}}$. Among
the proposed path-cost functions in the literature, the unsupervised OPF
relies on the following formulation:

$\displaystyle f_{\min}(\langle\bm{x}_{i}\rangle)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\rho(\bm{x}_{i})&\mbox{if
$\bm{x}_{i}\in\mathcal{R}$}\\\ \rho(\bm{x}_{i})-\delta&\mbox{otherwise.}\\\
\end{array}\right.$ (4) $\displaystyle
f_{\min}(\pi_{\bm{x}_{i}}\cdot\langle\bm{x}_{i},\bm{x}_{j}\rangle)$
$\displaystyle=$
$\displaystyle\min\\{f_{\min}(\pi_{\bm{x}_{i}}),\rho(\bm{x}_{j})\\},$

where
$\delta=\min_{\forall(\bm{x}_{i},\bm{x}_{j})\in\mathcal{A}_{k^{\star}}|\rho(t)\neq\rho(s)}|\rho(t)-\rho(s)|$
consists in the smallest quantity to avoid plateaus and over-segmentation in
regions near prototypes (i.e., areas with the highest density).

Among all possible paths $\pi_{\bm{x}_{i}}$ that originate in some local
maximum, i.e., some prototype, the OPF algorithm assigns to each sample a
final path whose minimum density value along it is maximum. Such final path
value is represented by a cost map $\mathcal{C}$, as follows:

$\mathcal{C}(\bm{x}_{i})=\max_{\forall\pi_{\bm{x}_{j}}\in\mathcal{D},\;i\neq
j}\\{f(\pi_{\bm{x}_{j}}\cdot\langle\bm{x}_{j},\bm{x}_{i}\rangle)\\}.$ (5)

The OPF algorithm maximizes
$\mathcal{C}(\bm{x}_{i})\;\forall\bm{x}_{i}\in\mathcal{D}$ by computing an
optimum-path forest for each sample in descending order of cost. Each forest
is encoded as an acyclic predecessor map $\mathcal{P}$ which assigns to each
sample $\bm{x}_{i}\notin\mathcal{R}$ its predecessor $\mathcal{P}(\bm{x}_{i})$
in the optimum path from $\mathcal{R}$, or a marker $nil$ when
$\bm{x}_{i}\in\mathcal{R}$.

It is important to remark that the unsupervised OPF algorithm determines the
number of clusters (OPTs) automatically, hence such information is not
required beforehand, differently from other algorithms. Furthermore, the only
hyperparameter that must be set is the search interval upper bound $k_{\max}$
for the proper neighborhood size $k^{\star}\in[1,k_{\max}]$.

###  II-B Supervised Optimum-Path Forest

Differently from its unsupervised version, the supervised variant uses a
fully-connected graph $\mathcal{G}^{\prime}=(\mathcal{D},\mathcal{B})$
instead. Moreover, the closest samples from different classes are marked as
prototypes, as aforementioned. Regarding the competition process, instead of
using Equation 4, the following smooth function is employed:

$\displaystyle f_{\max}(\langle\bm{x}_{i}\rangle)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}0&\mbox{if
$\bm{x}_{i}\in\mathcal{R}$}\\\ \infty&\mbox{otherwise.}\\\ \end{array}\right.$
(8) $\displaystyle
f_{\max}(\pi_{\bm{x}_{i}}\cdot\langle\bm{x}_{i},\bm{x}_{j}\rangle)$
$\displaystyle=$
$\displaystyle\max\left\\{f_{\max}(\pi_{\bm{x}_{i}}),d(\bm{x}_{i},\bm{x}_{j})\right\\}.$

Further, the following cost map is used to partition the graph:

$\mathcal{S}(\bm{x}_{i})=\min_{\bm{x}_{i}\in\mathcal{D}}\left\\{\max\left\\{\mathcal{S}(\bm{x}_{i}),d(\bm{x}_{i},\bm{x}_{j})\right\\}\right\\}.$
(9)

Such costs are used to initialize the algorithm before evaluating Equation 9,
which is performed for every node in an ascending order of costs. After
partitioning the graph, each prototype propagates its ground truth label to
all samples in its OPT. Afterwards, prediction is performed by solving the
same equation for new samples individually.

##  III Proposed Approach

Although the unsupervised OPF was conceived for clustering purposes, such
clusters possess a set of features that can also be employed to synthesize new
samples, thus being suitable for oversampling. This section describes the
procedure for a binary classification problem, which intends to oversample the
class composed of the smallest number of features. Notwithstanding, the same
approach can be easily applied to multiclass problems by individually
repeating the procedure for each class to be oversampled.

The process of synthetic samples generation contemplates two main steps: (i)
creating plausible samples, i.e., synthetic elements with characteristics that
are coherent with the selected class; and (ii) introducing sample variability,
avoiding making the classifier biased towards a subset of characteristics
present in that class. To tackle such issues, the $\text{O}^{2}$PF first
performs the clustering from minority class samples, which turns possible the
extraction of common patterns intrinsic to the class, i.e., the samples’
average position and variance. Further, the algorithm assumes that all
features from a class follow a normal distribution. Thus, a new sample
$\bm{z}\in\mathbb{R}^{m}$ can be generated by sampling such a distribution
from some of the $q$ clusters found. Notice the number of synthetic samples
generated by each cluster is proportional to the number of original samples
compounding it, i.e., we are always doubling the number of samples from the
minority class, although the user can set that percentage. The distribution is
performed as follows:

$\bm{z}\sim\mathcal{N}(\bm{\mu}_{q},\Sigma_{q}),$ (10)

where $\bm{\mu}_{q}\in\mathbb{R}^{m}$ stands for the distribution mean,
defined as the average feature vector from all samples within the $q$-th
cluster. Moreover, ${\Sigma_{q}\in\mathbb{R}^{m\times m}}$ is the covariance
matrix, computed as follows:

$\Sigma_{q}=\frac{1}{n_{q}-1}(X_{q}-\bm{\mu}_{q})(X_{q}-\bm{\mu}_{q})^{T},$
(11)

given that $X_{q}\in\mathbb{R}^{m\times n_{q}}$ is a matrix formed by
concatenating all $n_{q}$ cluster feature vectors. Figure 1 illustrates the
proposed approach behavior.

Figure 1: Oversampling using $\text{O}^{2}$PF. The image comprises WBCD
Diagnostic II dataset samples and synthetic points from the minority class
generated using $\text{O}^{2}$PF. Data were projected onto a $2$-dimensional
space using the Principal Component Analysis algorithm for visualization
purposes.

##  IV Methodology

This section describes the datasets used in the experiments. Further, the
experimental setup is outlined.

###  IV-A Datasets

Experiments were conducted over two sets of three databases each. The first
set comprises three datasets for breast cancer detection, i.e., the Wisconsin
Breast Cancer Database, which is composed of the datasets Prognostic,
Diagnostic I, and Diagnostic II. The second set is composed of general-purpose
datasets for medical issues. All of them are unbalanced, binary, and were
obtained from the UCI repository [25]. A brief description of each one follows
below:

  * •

Wisconsin Breast Cancer Database (WBCD) Prognostic111All considered versions
are available at
https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Prognostic).
[26]: Regards predicting a sample as recurrent or non-recurrent type of cancer
based on $32$ features. There are $198$ samples, being $151$ ($76.3\%$) non-
recurrent and $47$ ($23.7\%$) recurrent;

  * •

WBCD Diagnostic I: Consists of classifying a tumor as benignant or malignant
based on $32$ features as well. There are $569$ instances, from which $357$
($63.7\%$) are benign and $212$ ($37.3\%$) are malignant;

  * •

WBCD Diagnostic II: Corresponds to labelling each of the $699$ samples as
benign or malignant tumor. Each sample comprises $9$ features and each class
contains $458$ ($65.5\%$) and $241$ ($34.5\%$) examples, respectively;

  * •

Diabetic Retinopathy Debrecen (DRD)222Available at
https://archive.ics.uci.edu/ml/datasets/Diabetic+Retinopathy+Debrecen+Data+Set.
[27]: Regards predicting whether an image contains signs of diabetic
retinopathy or not based on $19$ variables. The dataset contains $1,151$
samples, from which $611$ ($53.1\%$) are positive and $540$ ($46.9\%$) are
negative;

  * •

Cervical Cancer (CC)333Available at
https://archive.ics.uci.edu/ml/datasets/Cervical+cancer+%28Risk+Factors%29.
[28]: For this task we predict the binary biopsy variable based on $32$
features for $858$ samples. Differently from other datasets, all variables in
this scenario are either integer or binary. Further, the dataset is
significantly skewed, with $55$ $(6.4\%)$ positive and $803$ ($93.6\%$)
negative samples;

  * •

Mammographic Mass (MM)444Available at
https://archive.ics.uci.edu/ml/datasets/Mammographic+Mass. [29]: Concerns
predicting if a mammographic mass is benign or malignant based on six
features. The dataset contains $516$ ($53.7\%$) benign and $445$ ($46.3\%$)
malignant samples, comprising $961$ examples.

###  IV-B Experimental setup

The experiments conducted in this paper considered pre-processing the data
such that missing features were replaced by their corresponding mean in the
training partition. All the features were normalized to have zero mean and
unitary standard deviation. Further, the datasets were randomly divided into
training, validation and testing sets, each containing $70\%$, $15\%$, and
$15\%$ of the data, respectively555Such percentages were obtained
empirically..

The validation set was employed to fine-tune the oversampling method
hyperparameters, i.e., finding the $k_{\max}$ for the unsupervised OPF and
$\kappa$ for the other methods that maximize the minority class recall.
Afterward, the augmented dataset is used to train the OPF classifier for
further computing the results over the testing sets. Notice that such a
procedure is repeated $20$ times for statistical analysis, and the results are
compared through the Wilcoxon signed-rank test [30] with $0.05$ significance
concerning recall values. Figure 2 depicts such a pipeline. Implementation-
wise, we rely on the supervised and unsupervised implementations provided by
Opfython [31]. Additionally, the source code was implemented using Python and
is available on GitHub.666The source code is available online at
https://github.com/Leandropassosjr/o2pf.

Figure 2: Experimental pipeline for each dataset partition.

##  V Experimental Results

This section is divided into four main steps: (i) datasets augmented using the
$\text{O}^{2}$PF are compared against the standard version, (ii) the proposed
approach is compared against three baselines for oversampling considering
three distinct versions of the Wisconsin Breast Cancer Database, i.e.,
Prognostic, Diagnostic I, and Diagnostic II, for the task of breast cancer
detection. In step (iii), a similar experiment is conducted over three
general-purpose medical issues datasets, and (iv) it provides a brief
discussion concerning the optimization of the proposed method hyperparameter,
i.e., the $k_{\max}$.

###  V-A $\text{O}^{2}$PF Data Augmentation Versus Standard Datasets

This section presents the results obtained by the Optimum-Path Forest
classifiers considering the datasets balanced through $\text{O}^{2}$PF
oversampling, i.e., minority classes are augmented such that both classes
present a similar number of samples, against the standard version of the
datasets. Table I presents the recall considering each dataset. Values in bold
denote the best results according to the Wilcoxon signed-rank test with $5\%$
of significance.

TABLE I: Evaluation of the proposed $\text{O}^{2}$PF against the standard
datasets versions.

Ds. Version | Recall | Prognostic | Diagnostic I | Diagnostic II | DRD | CC | MM
---|---|---|---|---|---|---|---
ORIGINAL | Avg. | $0.4945$ | $\bm{0.9184}$ | $0.8903$ | $0.4922$ | $\bm{0.6320}$ | $\bm{0.6180}$
Std. | $\pm 0.1872$ | $\pm 0.0346$ | $\pm 0.0550$ | $\pm 0.2017$ | $\pm 0.1002$ | $\pm 0.0480$
$\text{O}^{2}$PF | Avg. | $\bm{0.5739}$ | $\bm{0.9311}$ | $\bm{0.9104}$ | $\bm{0.5834}$ | $\bm{0.6292}$ | $0.6086$
Std. | $\pm 0.1368$ | $\pm 0.0331$ | $\pm 0.0452$ | $\pm 0.2308$ | $\pm 0.0924$ | $\pm 0.0434$

In this context, one can observe $\text{O}^{2}$PF obtained the best results in
five out of six datasets according to the Wilcoxon signed-rank test, obtaining
the best results alone in three of them.

###  V-B Results concerning the Breast Cancer datasets

Table II presents the average recall, accuracy, F1-measure and best $k_{\max}$
considering $\text{O}^{2}$PF or $\kappa$ considering the other techniques, as
well as their standard deviation. The results comprise a minority
oversampling, thus providing balanced datasets. The proposed approach is
compared against three baseline techniques, i.e., SMOTE, Borderline SMOTE, and
ADASYN.

TABLE II: Results considering WBCD Breast Cancer datasets.

Dataset | Statistics |  $\text{{O}}^{2}$PF | SMOTE | Borderline SMOTE | ADASYN
---|---|---|---|---|---
Prognostic | Recall | $\bm{0.5739\pm 0.1368}$ | $\bm{0.5803\pm 0.1253}$ | $\bm{0.5802\pm 0.1343}$ | $\bm{0.6311\pm 0.1283}$
Accuracy | $0.6317\pm 0.0654$ | $0.6183\pm 0.0532$ | $0.6317\pm 0.0619$ | $0.6300\pm 0.0547$
F1 | $0.4143\pm 0.1310$ | $0.4112\pm 0.1330$ | $0.4175\pm 0.1266$ | $0.4366\pm 0.1413$
Best $k$ | $37.2500\pm 27.0867$ | $6.4000\pm 1.5297$ | $6.0500\pm 1.4654$ | $6.1500\pm 1.4586$
Diagnostic I | Recall | $\bm{0.9311\pm 0.0331}$ | $\bm{0.9368\pm 0.0275}$ | $\bm{0.9347\pm 0.0322}$ | $\bm{0.9422\pm 0.0336}$
Accuracy | $0.9471\pm 0.0170$ | $0.9500\pm 0.0138$ | $0.9424\pm 0.0178$ | $0.9448\pm 0.0191$
F1 | $0.9285\pm 0.0257$ | $0.9330\pm 0.0198$ | $0.9231\pm 0.0278$ | $0.9264\pm 0.0285$
Best $k$ | $12.7500\pm 12.6960$ | $5.4000\pm 0.8602$ | $5.6500\pm 1.2359$ | $6.0000\pm 1.6432$
Diagnostic II | Recall | $\bm{0.9104\pm 0.0452}$ | $\bm{0.9075\pm 0.0541}$ | $0.8947\pm 0.0586$ | $\bm{0.9108\pm 0.0520}$
Accuracy | $0.9490\pm 0.0176$ | $0.9476\pm 0.0192$ | $0.9419\pm 0.0217$ | $0.9490\pm 0.0191$
F1 | $0.9195\pm 0.0294$ | $0.9170\pm 0.0331$ | $0.9080\pm 0.0353$ | $0.9196\pm 0.0315$
Best $k$ | $23.5000\pm 29.6268$ | $6.4500\pm 1.4992$ | $5.4000\pm 0.8602$ | $6.8500\pm 1.5580$

Results observed over WBCD Prognostic dataset show all techniques obtained
similar statistical results considering the recall. Regarding the accuracy,
one can observe the proposed approach obtained the highest average value,
together with the borderline SMOTE. Such a result suggests samples generated
by $\text{O}^{2}$PF fit better the class distribution, being less prone to
false negatives. A similar behavior is observed over the Diagnostic I dataset.
Concerning the Diagnostic II dataset, the proposed approach obtained the best
results, together with ADASYN and SMOTE, outperforming Borderline SMOTE.
Considering the accuracy, $\text{O}^{2}$PF obtained the highest averages.

Despite the good performance achieved by the oversampling approach using
$\text{O}^{2}$PF, the baseline algorithms have shown statistical similarity in
most of the cases. Sparse clusters with low density may be responsible for
introducing new samples that are distant from the original distribution of the
minority class, a situation that would be likely to produce outliers in the
new resample dataset. Such behavior may also influence in a moderate recall,
as observed in Tables II.

###  V-C General Purpose Medical Datasets Results

Table III presents the results obtained over the three general purpose medical
datasets, i.e., Diabetic Retinopathy Debrecen, Cervical Cancer and
Mammographic Mass.

TABLE III: Results considering General Purpose Datasets.

Dataset | Statistics |  $\text{{O}}^{2}$PF | SMOTE | Borderline SMOTE | ADASYN
---|---|---|---|---|---
DRD | Recall | $\bm{0.6086\pm 0.0434}$ | $\bm{0.5831\pm 0.0476}$ | $\bm{0.5855\pm 0.0498}$ | $0.5716\pm 0.0487$
Accuracy | $0.5934\pm 0.0327$ | $0.5983\pm 0.0353$ | $0.5974\pm 0.0343$ | $0.5957\pm 0.0354$
F1 | $0.6092\pm 0.0302$ | $0.5799\pm 0.0465$ | $0.5803\pm 0.0460$ | $0.5734\pm 0.0469$
Best $k$ | $26.2500\pm 26.9664$ | $6.8500\pm 1.6515$ | $7.5000\pm 1.7748$ | $5.0000\pm 0.0000$
CC | Recall | $\bm{0.5834\pm 0.2308}$ | $\bm{0.6287\pm 0.1505}$ | $0.5791\pm 0.1811$ | $\bm{0.6237\pm 0.1560}$
Accuracy | $0.9388\pm 0.0212$ | $0.9403\pm 0.0157$ | $0.9403\pm 0.0165$ | $0.9415\pm 0.0138$
F1 | $0.5330\pm 0.1548$ | $0.5673\pm 0.0900$ | $0.5414\pm 0.1109$ | $0.5675\pm 0.0905$
Best $k$ | $13.2500\pm 10.8714$ | $6.5500\pm 1.4654$ | $6.5500\pm 1.7168$ | $6.0000\pm 1.5166$
MM | Recall | $\bm{0.6292\pm 0.0924}$ | $\bm{0.6757\pm 0.0739}$ | $\bm{0.6876\pm 0.0608}$ | $\bm{0.6614\pm 0.0706}$
Accuracy | $0.6769\pm 0.0531$ | $0.6738\pm 0.0503$ | $0.6852\pm 0.0426$ | $0.6876\pm 0.0396$
F1 | $0.6439\pm 0.0639$ | $0.6591\pm 0.0545$ | $0.6710\pm 0.0479$ | $0.6631\pm 0.0567$
Best $k$ | $48.0000\pm 34.2199$ | $7.1000\pm 1.4799$ | $7.2500\pm 1.5772$ | $6.1500\pm 1.5898$

Considering Diabetic Retinopathy Debrecen, the proposed approach outperformed
the average recall overall techniques, although SMOTE and Borderline SMOTE
achieved similar results. Similar behavior is observed over the F1 metric. On
the other hand, $\text{{O}}^{2}$PF, SMOTE and ADASYN obtained the best results
regarding the Cervical Cancer dataset. Since both Borderline SMOTE and ADASYN
are variants of SMOTE, they are expected to perform differently over different
scenarios. However, as observed in most of the experiments, they generally are
outperformed by SMOTE technique itself, considering the average values.
Regarding Mammographic Mass datasets, all techniques performed in a very much
alike fashion, obtaining similar results.

One can notice that all three datasets present a challenging task since no
technique reached a $0.7$ recall. Unusual behavior is observed over the
Cervical Cancer dataset, whose all techniques obtained an approximate accuracy
of $94\%$, despite the recall below $0.63$. Such behavior may suggest samples
from the minority class are distributed among a subcluster from majority
class, therefore providing high accuracy despite the low recall.

###  V-D $\text{O}^{2}$PF Hyperparameter Selection

$\text{O}^{2}$PF requires a proper selection of a single hyperparameter, the
$k_{max}$, which is employed in the clustering process. Such a hyperparameter,
however, is way less sensitive when compared to a proper selection of the best
$k$, performed by the other techniques. Figure 3 depicts a grid search
considering a proper selection of those hyperparameters for each technique.
Notice the central line describes the average value over the validation
dataset, while the broader area describes the standard deviation. Notice even
though $\text{O}^{2}$PF considers a very wider interval, i.e., ranging from
$[5,100]$, most of the time, the results outperform the other techniques,
which assume a shorter interval between $[5,10]$.

(a) (b)

(c)

Figure 3: Grid searching for a proper selection of the techniques’
hyperparameter over the validation for WBCD (a) Prognostic, (b) Diagnostic I,
and (c) Diagnostic II datasets.

##  VI Conclusion

This paper presented an oversampling approach based on the unsupervised
Optimum-Path Forest Algorithm. The proposed $\text{O}^{2}$PF showed to be
capable of handling the class imbalance problem through a simple and effective
procedure that generates new synthetic samples based on the normal
distribution of the feature vectors inside each cluster. The experiments
performed in three datasets of breast cancer, apart from three complementary
medical issue datasets, showed that the $\text{O}^{2}$PF approach demonstrated
similar or superior results when compared to the baseline methods already
proposed in the literature.

Notwithstanding, the effectiveness of the proposed approach may still suffer
in synthesizing new samples based on low-density clusters, a situation that
may introduce noise samples in the training set and, consequently, affect
creating of the prediction model. Future studies will be conducted to overcome
the influence of sparse clusters with low density in the process of
synthesizing new outliers. Moreover, experiments with a multiclass problem
will also be performed in subsequent investigations.

## References

  * [1] D. S. Jodas, A. S. Pereira, and J. M. R. Tavares, “A review of computational methods applied for identification and quantification of atherosclerotic plaques in images,” _Expert Systems with Applications_ , vol. 46, pp. 1–14, 2016.
  * [2] L. C. Ribeiro, L. C. Afonso, and J. P. Papa, “Bag of samplings for computer-assisted parkinson’s disease diagnosis based on recurrent neural networks,” _Computers in biology and medicine_ , vol. 115, p. 103477, 2019\.
  * [3] N. I. Yassin, S. Omran, E. M. E. Houby, and H. Allam, “Machine learning techniques for breast cancer computer aided diagnosis using different image modalities: A systematic review,” _Computer Methods and Programs in Biomedicine_ , vol. 156, pp. 25–45, 2018.
  * [4] W. H. Organization. Breast cancer. [Online]. Available: https://www.who.int/cancer/prevention/diagnosis-screening/breast-cancer/en/
  * [5] M. Xian, Y. Zhang, H. Cheng, F. Xu, B. Zhang, and J. Ding, “Automatic breast ultrasound image segmentation: A survey,” _Pattern Recognition_ , vol. 79, pp. 340 – 355, 2018.
  * [6] W. Wieclawek, M. Rudzki, A. Wijata, and M. Galinska, “Preliminary development of an automatic breast tumour segmentation algorithm from ultrasound volumetric images,” in _Information Technology in Biomedicine_ , E. Pietka, P. Badura, J. Kawa, and W. Wieclawek, Eds. Cham: Springer International Publishing, 2019, pp. 77–88.
  * [7] L. Liu, K. Li, W. Qin, T. Wen, L. Li, J. Wu, and J. Gu, “Automated breast tumor detection and segmentation with a novel computational framework of whole ultrasound images,” _Medical & Biological Engineering & Computing_, vol. 56, pp. 183–199, 2017.
  * [8] A. F. M. Agarap, “On breast cancer detection: an application of machine learning algorithms on the wisconsin diagnostic dataset,” in _Proceedings of the 2nd International Conference on Machine Learning and Soft Computing_ , 2018, pp. 5–9.
  * [9] L. A. Passos, C. Santos, C. R. Pereira, L. C. S. Afonso, and J. P. Papa, “A hybrid approach for breast mass categorization,” in _ECCOMAS Thematic Conference on Computational Vision and Medical Image Processing_. Springer, 2019, pp. 159–168.
  * [10] P. B. Ribeiro, L. A. Passos, L. A. da Silva, K. A. da Costa, J. P. Papa, and R. A. Romero, “Unsupervised breast masses classification through optimum-path forest,” in _2015 IEEE 28th International Symposium on Computer-Based Medical Systems_. IEEE, 2015, pp. 238–243.
  * [11] L. M. Rocha, F. A. M. Cappabianco, and A. X. Falcão, “Data clustering as an optimum-path forest problem with applications in image analysis,” _International Journal of Imaging Systems and Technology_ , vol. 19, no. 2, pp. 50–68, 2009.
  * [12] L. C. S. Afonso, L. A. Passos, and J. P. Papa, “Enhancing brain storm optimization through optimum-path forest,” in _2018 IEEE 12th International Symposium on Applied Computational Intelligence and Informatics (SACI)_. IEEE, 2018, pp. 000 183–000 188.
  * [13] R. R. Guimarães, L. A. Passos, R. Holanda Filho, V. H. C. de Albuquerque, J. J. Rodrigues, M. M. Komarov, and J. P. Papa, “Intelligent network security monitoring based on optimum-path forest clustering,” _IEEE Network_ , vol. 33, no. 2, pp. 126–131, 2018.
  * [14] R. W. R. Souza, J. V. C. Oliveira, L. A. Passos, W. Ding, J. P. Papa, and V. H. Albuquerque, “A novel approach for optimum-path forest classification using fuzzy logic,” _IEEE Transactions on Fuzzy Systems_ , 2019.
  * [15] M. Zhu, J. Xia, X. Jin, M. Yan, G. Cai, J. Yan, and G. Ning, “Class weights random forest algorithm for processing class imbalanced medical data,” _IEEE Access_ , vol. 6, pp. 4641–4652, 2018.
  * [16] T. Razzaghi, I. Safro, J. Ewing, E. Sadrfaridpour, and J. D. Scott, “Predictive models for bariatric surgery risks with imbalanced medical datasets,” _Annals of Operations Research_ , vol. 280, no. 1-2, pp. 1–18, 2019.
  * [17] M. Rezaei, H. Yang, and C. Meinel, “Recurrent generative adversarial network for learning imbalanced medical image semantic segmentation,” _Multimedia Tools and Applications_ , pp. 1–20, 2019.
  * [18] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “Smote: synthetic minority over-sampling technique,” _Journal of Artificial Intelligence Research_ , vol. 16, pp. 321–357, 2002.
  * [19] H. Han, W.-Y. Wang, and B.-H. Mao, “Borderline-smote: a new over-sampling method in imbalanced data sets learning,” in _International conference on intelligent computing_. Springer, 2005, pp. 878–887.
  * [20] H. He, Y. Bai, E. A. Garcia, and S. Li, “Adasyn: Adaptive synthetic sampling approach for imbalanced learning,” in _2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelligence)_. IEEE, 2008, pp. 1322–1328.
  * [21] J. P. Papa, A. X. Falcão, and C. T. N. Suzuki, “Supervised pattern classification based on optimum-path forest,” _International Journal of Imaging Systems and Technology_ , vol. 19, no. 2, pp. 120–131, 2009.
  * [22] J. P. Papa, A. X. Falcão, V. H. C. De Albuquerque, and J. M. R. Tavares, “Efficient supervised optimum-path forest classification for large datasets,” _Pattern Recognition_ , vol. 45, no. 1, pp. 512–520, 2012.
  * [23] A. X. Falcão, J. Stolfi, and R. A. Lotufo, “The image foresting transform: theory, algorithms, and applications,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 26, no. 1, pp. 19–29, 2004.
  * [24] K. C. Ciesielski, A. X. Falcão, and P. A. V. Miranda, “Path-value functions for which dijkstra’s algorithm returns optimal mapping,” _Journal of Mathematical Imaging and Vision_ , vol. 60, no. 7, pp. 1025–1036, Sep 2018.
  * [25] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [26] O. L. Mangasarian and W. H. Wolberg, “Cancer diagnosis via linear programming,” University of Wisconsin-Madison Department of Computer Sciences, Tech. Rep., 1990.
  * [27] B. Antal and A. Hajdu, “An ensemble-based system for automatic screening of diabetic retinopathy,” _Knowledge-based systems_ , vol. 60, pp. 20–27, 2014\.
  * [28] K. Fernandes, J. S. Cardoso, and J. Fernandes, “Transfer learning with partial observability applied to cervical cancer screening,” in _Iberian conference on pattern recognition and image analysis_. Springer, 2017, pp. 243–250.
  * [29] M. Elter, R. Schulz-Wendtland, and T. Wittenberg, “The prediction of breast cancer biopsy outcomes using two cad approaches that both emphasize an intelligible decision process,” _Medical physics_ , vol. 34, no. 11, pp. 4164–4172, 2007.
  * [30] F. Wilcoxon, “Individual comparisons by ranking methods,” _Biometrics Bulletin_ , vol. 1, no. 6, pp. 80–83, 1945.
  * [31] G. H. de Rosa, J. P. Papa, and A. X. Falcão, “Opfython: A python-inspired optimum-path forest classifier,” 2020.


# Expected Validation Performance
and Estimation of a Random Variable’s Maximum

Jesse Dodge♣ Suchin Gururangan♡ Dallas Card♠
Roy Schwartz♢ Noah A. Smith♡♣
♠Stanford University
♢Hebrew University of Jerusalem
♡Paul G. Allen School of Computer Science & Engineering, University of
Washington
♣Allen Institute for Artificial Intelligence
<EMAIL_ADDRESS>
###### Abstract

Research in NLP is often supported by experimental results, and improved
reporting of such results can lead to better understanding and more
reproducible science. In this paper we analyze three statistical estimators
for expected validation performance, a tool used for reporting performance
(e.g., accuracy) as a function of computational budget (e.g., number of
hyperparameter tuning experiments). Where previous work analyzing such
estimators focused on the bias, we also examine the variance and mean squared
error (MSE). In both synthetic and realistic scenarios, we evaluate three
estimators and find the unbiased estimator has the highest variance, and the
estimator with the smallest variance has the largest bias; the estimator with
the smallest MSE strikes a balance between bias and variance, displaying a
classic bias-variance tradeoff. We use expected validation performance to
compare between different models, and analyze how frequently each estimator
leads to drawing incorrect conclusions about which of two models performs
best. We find that the two biased estimators lead to the fewest incorrect
conclusions, which hints at the importance of minimizing variance and MSE.

##  1 Introduction

Drawing robust conclusions when comparing different methods in natural
language processing is central to scientific progress. If two research groups
set up the same set of experiments, they should expect to get similar results.
One area that has high impact, but is often underreported, is hyperparameter
tuning (Reimers and Gurevych, 2017; D’Amour et al., 2020; Dodge et al., 2019;
Melis et al., 2018). Hyperparameter search is key to getting strong results;
for example, RoBERTa (Liu et al., 2019) found stronger results than BERT
(Devlin et al., 2019) partly due to an increased budget for hyperparameter
tuning. Often researchers only report the performance of the single best-found
model during a hyperparameter search Ethayarajh and Jurafsky (2020); Forde and
Paganini (2019); Sculley et al. (2018). What if a future researcher has a
smaller computational budget for training models? What performance should they
expect to find? One way of reporting such results is expected validation
performance (EVP).

What is EVP? Assume a budget to train $B$ models (e.g., $B$ rounds of
hyperparameter search), with resulting evaluation scores (e.g., accuracy) on
the validation set $X_{1}\ldots X_{B}$. Standard practice would report the
maximum result, $X_{max}$, but this effectively hides the experiments which
were required to achieve that maximum performance. Using all $B$ results, EVP
estimates what the maximum would have been if we had had a smaller budget $n$
(where $1\leq n<B$). This is estimating what the maximum of $n$ trials _would
be_ , in expectation; this is thus a statistical estimation problem. The
formulation was introduced by Dodge et al. (2019), who proposed a first
estimator (defined as $V_{n}^{B}$ in Equation 2). This estimator was later
shown to be biased by Tang et al. (2020), who introduced an unbiased estimator
(defined as $U_{n}^{B}$ in Equation 3) for the same expected maximum.

In Section 2 we use tools from combinatorics to derive both previously-
introduced estimators, relate them to each other, and show that they make two
opposing assumptions; we show that changing only one of these assumptions
instead of both leads to a third estimator, $W_{n}^{B}$, and prove that this
estimator is even more biased than $V_{n}^{B}$.

Unbiased estimators are generally preferred, all else equal, but only
analyzing the bias provides an incomplete picture of the quality of an
estimator. In Section 3 we also measure the variance and mean squared error of
these three estimators in synthetic experiments. We find that while
$U_{n}^{B}$ is unbiased (as expected) it has the highest variance, and that
$W_{n}^{B}$ is the most biased but has the lowest variance; $V_{n}^{B}$
strikes a balance between the bias and variance, leading to the lowest mean
squared error (so, the average squared distance to the true value being
estimated is smallest).111There is a long tradition of preferring biased
estimators over unbiased ones (Wasserman, 2004), such as when estimating the
population variance using the sample variance, or the James–Stein estimator
James and Stein (1961).

Finally, in Section 4 we explore how these estimators impact a common use case
of EVP: comparing the results of hyperparameter searches for two models.
Specifically, we examine how frequently the estimators lead to incorrectly
concluding that the worse model outperforms the better one (for a given
budget), and find that the high-variance (but unbiased) $U_{n}^{B}$ more
frequently leads to such incorrect conclusions than the other lower variance
(but biased) estimators.

##  2 Estimation of the Expected Maximum

#### Notation

We begin by defining some notation. Consider $n$ i.i.d. random variables,
$X_{1},\ldots,X_{n}\sim F$, for some unknown $F$.222For clarity, we dispense
with notation mapping into the use case of interest, as well as the
computational details; see Dodge et al. (2019) for a full discussion.

  * •

${Y_{n}}\,=\max\\{X_{1},\ldots,X_{n}\\}$, a random variable representing the
maximum of $n$ i.i.d. random variables.

  * •

${\theta}_{n}={\mathbb{E}}\,[{Y_{n}}\,]$, the true expected value of
${Y_{n}}\,$.

  * •

$\hat{{\theta}}_{n}$, an estimator of ${\theta}_{n}$ (the expected value).

  * •

${\textrm{Bias}}\,(\hat{{\theta}})={\mathbb{E}}\,[\hat{{\theta}}]-{\theta}$,
the bias of $\hat{{\theta}}$.

  * •

${\textrm{Var}}\,(\hat{{\theta}})$, the estimator’s variance due to sampling.

  * •

${\textrm{MSE}}\,(\hat{{\theta}})={\textrm{Bias}}\,(\hat{{\theta}})^{2}+{\textrm{Var}}\,(\hat{{\theta}})$,
the mean squared error of the estimator. MSE is the average squared difference
between the estimator and true value, or the expected value of the squared
error loss between the estimator and the true statistic.

#### Estimation of the Expected Maximum

We consider the estimation of ${\theta}$, the expected maximum. With a finite
sample of $B$ draws from $F$, we can estimate this quantity for $1\leq n\leq
B$. We begin with the definition of an expectation over a discrete set:
${\mathbb{E}}\,[{Y_{n}}\,]=\sum_{i=1}^{B}X_{i}P({Y_{n}}\,=X_{i})$. This can be
rewritten using order statistics. Let $X_{(i)}$ denote the $i$th largest
sample (distinct from $X_{i}$). Then,

$\displaystyle{\mathbb{E}}\,[{Y_{n}}\,]=\textstyle\sum_{i=1}^{B}X_{(i)}P({Y_{n}}\,=X_{(i)})$
(1) $\displaystyle=\textstyle\sum_{i=1}^{B}X_{(i)}\left(P({Y_{n}}\,\leq
X_{(i)})-P({Y_{n}}\,<X_{(i)})\right)$
$\displaystyle=\textstyle\sum_{i=1}^{B}X_{(i)}\left(P({Y_{n}}\,\leq
X_{(i)})-P({Y_{n}}\,\leq X_{(i-1)})\right)$

This estimation depends on $P({Y_{n}}\,\leq X_{(k)})$, the probability that a
sample of size $n$ has a maximum that is less than or equal to the $k$th order
statistic. We can estimate this probability by counting: from our $B$ points
how many sets of size $n$ are there which only include order statistics up to
$k$, out of the total number of sets of size $n$? We turn to combinatorics,
which provides tools for counting such sets. Two key assumptions must be made:
whether the sets will contain repetition or not and whether the items in the
sets will be ordered or unordered. These assumptions will lead to different
estimators.

Ordered subsets that allow repetition are known as strings, and there are
$B^{n}$ strings of size $n$ from $B$ points. With these assumptions, we now
have a closed form for $P({Y_{n}}\,\leq X_{(k)})$, and plugging this into
Equation 1 we define our first estimator:

$\begin{split}V_{n}^{B}&=\sum_{i=1}^{B}X_{(i)}\left(\frac{i^{n}}{B^{n}}-\frac{(i-1)^{n}}{B^{n}}\right).\end{split}$
(2)

This is exactly the estimator introduced in Dodge et al. (2019), derived using
the plug-in estimator for the CDF (the empirical CDF).

Making the opposite two assumptions, unordered subsets without repetition are
combinations, for which there are $\binom{B}{n}$ subsets of size $n$ from $B$
points. The corresponding estimator is

$\begin{split}U_{n}^{B}&=\sum_{i=1}^{B}X_{(i)}\left(\frac{\binom{i}{n}}{\binom{B}{n}}-\frac{\binom{i-1}{n}}{\binom{B}{n}}\right).\end{split}$
(3)

This is the estimator of Tang et al. (2020), which they derived as an unbiased
estimator.

What about changing only one of these assumptions? Ordered subsets without
repetition are permutations, for which there are ${}_{B}P_{n}$ subsets of size
$n$ from $B$ points. Though these assumptions are different, the corresponding
estimator is equivalent to $U_{n}^{B}$, since:

$\frac{{}_{k}P_{n}}{{}_{B}P_{n}}=\frac{\frac{k!}{(k-n)!}}{\frac{B!}{(B-n)!}}=\frac{\frac{k!}{n!\,(k-n)!}}{\frac{B!}{n!\,(B-n)!}}=\frac{\binom{k}{n}}{\binom{B}{n}}$
(4)

Finally, unordered subsets with repetition are multisets, the number of which
is denoted
$\mathchoice{\left(\\!{\binom{B}{n}}\\!\right)}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}=\binom{B+n-1}{n}$.
We introduce the corresponding estimator:

$\begin{split}W_{n}^{B}&=\sum_{i=1}^{B}X_{(i)}\left(\frac{\mathchoice{\left(\\!{\binom{i}{n}}\\!\right)}{\bigl{(}\\!{\binom{i}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{i}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{i}{n}}\\!\bigr{)}}}{\mathchoice{\left(\\!{\binom{B}{n}}\\!\right)}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}}-\frac{\mathchoice{\left(\\!{\binom{i-1}{n}}\\!\right)}{\bigl{(}\\!{\binom{i-1}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{i-1}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{i-1}{n}}\\!\bigr{)}}}{\mathchoice{\left(\\!{\binom{B}{n}}\\!\right)}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}}\right).\end{split}$
(5)

#### Comparing estimators

To compare these estimators we turn to the standard statistical tools of bias,
variance, and mean squared error. $U_{n}^{B}$ was shown to be unbiased, and
${\textrm{Bias}}\,(V_{n}^{B})\leq 0$ (Tang et al., 2020). We show that
${\textrm{Bias}}\,(W_{n}^{B})\leq{\textrm{Bias}}\,(V_{n}^{B})$, that is
$W_{n}^{B}$ has a larger negative bias than $V_{n}^{B}$.

###### Theorem 1

Assume $X_{1},\ldots,X_{B}\sim F$ are i.i.d. from unknown distribution $F$.
Let $1\leq k<B$, and $1\leq n\leq B$. Then,
${\textrm{Bias}}\,(W_{n}^{B})\leq{\textrm{Bias}}\,(V_{n}^{B})$.

Consider $V_{n}^{B}$ as defined in Equation 2. The sum of the coefficients of
the $X_{(i)}$ up to $k$ is $\frac{k^{n}}{B^{n}}$. It is sufficient to show
that, for a given $k$, this term is less than the sum of the coefficients for
$W_{n}^{B}$, which is
$\left.{\mathchoice{\left(\\!{\binom{k}{n}}\\!\right)}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}}\right/{\mathchoice{\left(\\!{\binom{B}{n}}\\!\right)}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}}$;
this implies that $V_{n}^{B}$ places less probability mass on the smaller
order statistics than $W_{n}^{B}$.

$\displaystyle\frac{k^{n}}{B^{n}}<\frac{\mathchoice{\left(\\!{\binom{k}{n}}\\!\right)}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{k}{n}}\\!\bigr{)}}}{\mathchoice{\left(\\!{\binom{B}{n}}\\!\right)}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}{\bigl{(}\\!{\binom{B}{n}}\\!\bigr{)}}}$
$\displaystyle\iff\frac{k^{n}}{B^{n}}<\frac{\binom{k+n-1}{n}}{\binom{B+n-1}{n}}$
(6)
$\displaystyle\iff\frac{\binom{B+n-1}{n}}{B^{n}}<\frac{\binom{k+n-1}{n}}{k^{n}}.$
(7)

The left side of Eq. 7 can be rewritten as:

$\displaystyle\frac{\binom{B+n-1}{n}}{B^{n}}$
$\displaystyle=\frac{\frac{(B+n-1)!}{n!\,B!}}{B^{n}}=\frac{1}{n!}\frac{\prod_{j=0}^{n-1}\left(B+n-1-j\right)}{B^{n}}$
$\displaystyle=\textstyle\left(\frac{1}{n!}\right)\prod_{j=0}^{n-1}\left(1+\frac{(n-1)-j}{B}\right).$
(8)

Rewriting the right side of Eq. 7 in a similar manner, we have

$\displaystyle\textstyle\prod_{j=0}^{n-1}\left(1+\frac{(n-1)-j}{B}\right)<\prod_{j=0}^{n-1}\left(1+\frac{(n-1)-j}{k}\right)$

since $B>k$. This completes our proof.

##  3 Simulation Experiment

In the previous section we proved that $W_{n}^{B}$ is at least as biased as
$V_{n}^{B}$, but such a bound tells us little about how these estimators
behave in practice. In this section we provide a simulation experiment which
allows us to measure the bias and variance of each estimator directly. We
assume a distribution for $X_{i}$, which allows us to draw many samples of
size $B$ so we can evaluate how these estimators behave. Recall that the
motivating application of our estimators is when $\\{X_{i}\\}_{i=1}^{n}$
represent the evaluations from different trials of hyperparameter
optimization, so designing a reasonable distribution for $X_{i}$ allows us to
evaluate the estimators with tens of thousands of simulated trials without
having to train that many models.

###  3.1 Synthetic Experiments Setup

To begin, we sample 100,000 random values from a Normal$(0.6,0.07)$
distribution (truncated to $[0,1]$). We then sample 10,000 values from this
set, resulting in 9536 unique values, with a true maximum of 0.854. Call this
bag of values $\mathcal{V}$. We then set $B=30$, and estimate the true EVP as
a function of $n$ for $n=1,...,30$, by drawing 50,000 samples of size $n$ from
$\mathcal{V}$, for each value of $n$, and reporting the average maximum for
each $n$ (“True EVP” in Figure 1, top). To estimate the mean and variance of a
given estimator we sample 10,000 $B$ values from $\mathcal{V}$ and compute the
value of the estimator for each, then calculate the mean and variance across
those 10,000 samples.

###  3.2 Bias, Variance, MSE

Figure 1 shows the estimated mean (top), variance (middle), and MSE (bottom)
of each estimator. As can be seen in the top figure,
${\textrm{Bias}}\,(W_{n}^{B})\leq{\textrm{Bias}}\,(V_{n}^{B})\leq{\textrm{Bias}}\,(U_{n}^{B})=0$
with a a difference that grows with $n$, confirming the proved bounds for
these estimators. In the middle figure we measure the variance of these
estimators, and we see that
${\textrm{Var}}\,(W_{n}^{B})\leq{\textrm{Var}}\,(V_{n}^{B})\leq{\textrm{Var}}\,(U_{n}^{B})$,
with the difference in variance again growing with $n$.

Figure 1: Expected value (top) variance (middle) and mean squared error (MSE;
bottom) of the three estimators, based on a 10,000 simulations for a large
random bag of possible validation scores. As expected, $U_{n}^{B}$ is unbiased
while $V_{n}^{B}$ and $W_{n}^{B}$ have negative bias. However, $W_{n}^{B}$ has
the lowest variance, and $V_{n}^{B}$ balances bias and variance, leading to
lowest MSE.

In the bottom of Figure 1 we plot the mean squared error (MSE); as a reminder,
${\textrm{MSE}}\,(\hat{{\theta}})={\textrm{Bias}}\,(\hat{{\theta}})^{2}+{\textrm{Var}}\,(\hat{{\theta}})$,
so lower is better. Although $U_{n}^{B}$ is unbiased, and $W_{n}^{B}$ has the
lowest variance, $V_{n}^{B}$ strikes the balance between bias and variance
that leads to the lowest MSE.

Thus we see that a higher variance estimator may, on average, be farther from
the true value than a biased but lower variance estimator. Again tying this
back to our motivating application of hyperparameter tuning, in this scenario
$V_{n}^{B}$ is more likely to underestimate than overestimate performance for
a given budget, but overall will have lower variance between researchers
running sets of experiments, and will on average have closer predictions to
the true value than the other two estimators.

##  4 Incorrect Conclusions

While analyzing how close each estimator is to the true expected maximum for
one model is important, in practice these curves are often used to compare two
or more different models. For example, NLP practitioners may run
hyperparameter searches for two different models, compute the expected
validation curves for each, and select the model which presents a higher
estimated maximum performance Zhang et al. (2021); Gehman et al. (2020). In
this section we examine the three estimators in such a scenario, asking how
frequently each estimator leads to drawing _incorrect_ conclusions about which
model performs best for a specific budget.

###  4.1 Experimental Setup

We proceed by performing a sensitivity analysis: we run 100 trials of random
hyperparameter search (far more than is typically necessary to establish that
one model outperforms another in current practice) for a CNN Kim (2014) and a
linear bag-of-embedding (LBoE) Yogatama and Smith (2015). These models are
trained on the Stanford sentiment treebank 5-way text classification task
Socher et al. (2013). We include details about the dataset (and a link to
download it) in Appendix B.

For all three estimators, the CNN has higher expected performance than the
LBoE, for all $n\leq B$.333See Appendix C for details. Figure 3 shows expected
validation curves for $B=100$ for all three estimators; with $B$ this large,
the three estimators are very similar. We then simulate a more practical
scenario where a practitioner runs $B\in\\{15,\ldots,30\\}$ rounds of
hyperparameter search for the two models and compares their estimated maximum
at $n=B$ (so, the estimated maximum of $B$ points) to conclude which is best
(that is, which estimator has lower error).

We are interested in the rate at which each estimator would draw an incorrect
conclusion about which model performs best. To evaluate this question we do
the following: for each value of $B$ we sample 50,000 times from the 100 real
experiments and compute the fraction for which the value of each estimator for
the CNN is less than for LBoE. For example, to estimate the proportion with
which $U_{B}^{B}$ draws an incorrect conclusion with $B=15$ we draw 50,000
samples of size 15 from the 100 real experimental results for each of the CNN
and LBoE, then compute the fraction of those samples for which $U_{B}^{B}$ for
the CNN is less than $U_{B}^{B}$ for LBoE. A stable estimator will make the
same prediction with small and large $B$.

###  4.2 Results

In Figure 2 we see the results of this experiment: $U_{B}^{B}$ more frequently
would lead a practitioner to incorrectly conclude that the LBoE outperforms
the CNN for budgets $B\in\\{15,\ldots,30\\}$ than $V_{B}^{B}$ or $W_{B}^{B}$.
This scenario models what we expect a practitioner would care about: the
frequency with which one draws conclusions that would be consistent with
conclusions drawn with a larger budget. Here the high variance of $U_{B}^{B}$
likely plays a role the stability of its predictions; while it may be
unbiased, the lower variance estimators are more reliable.

Figure 2: For a budget of $B$ trials, what fraction of the time does each
estimator _incorrectly_ predict that the expected maximum of those $B$ trials
(so, $n=B$) is higher for the LBoE than for the CNN? Lower is better. The
proportion of errors made by the unbiased estimator $U_{n}^{B}$ when $n=B$ is
higher than for either of the biased estimators, $V_{n}^{B}$ and $W_{n}^{B}$.
Confidence intervals around this proportion are not shown, as they are small.

##  5 Conclusion

Drawing reproducible conclusions from our experimental results is of paramount
importance to NLP researchers, practitioners, and users of language
technologies. Expected validation performance curves are tools for comparing
the results of hyperparameter searches; we showed how two previously-
introduced estimators are connected through combinatorial assumptions, and
introduced a third estimator by varying such assumptions. In synthetic
experiments, we analyzed the bias, variance, and mean squared error, and found
a classic example of a bias-variance tradeoff; the unbiased estimator
$U_{n}^{B}$ had the largest variance, and the most biased estimator
$W_{n}^{B}$ had the lowest variance, while $V_{n}^{B}$ struck a balance
leading to the lowest mean squared error. Finally, in realistic experiments we
found that the unbiased estimator led to incorrectly identifying the better of
two models at a higher rate than the lower variance estimator. Overall,
$V_{n}^{B}$ had the lowest MSE and the lowest rate of drawing incorrect
conclusions, so $V_{n}^{B}$ is our recommendation for estimating the expected
maximum.

## Acknowledgements

Dallas Card was supported in part by the Stanford Data Science Institute.

## References

  * D’Amour et al. (2020) Alexander D’Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D. Hoffman, Farhad Hormozdiari, Neil Houlsby, Shaobo Hou, Ghassen Jerfel, Alan Karthikesalingam, Mario Lucic, Yian Ma, Cory McLean, Diana Mincu, Akinori Mitani, Andrea Montanari, Zachary Nado, Vivek Natarajan, Christopher Nielson, Thomas F. Osborne, Rajiv Raman, Kim Ramasamy, Rory Sayres, Jessica Schrouff, Martin Seneviratne, Shannon Sequeira, Harini Suresh, Victor Veitch, Max Vladymyrov, Xuezhi Wang, Kellie Webster, Steve Yadlowsky, Taedong Yun, Xiaohua Zhai, and D. Sculley. 2020.  Underspecification presents challenges for credibility in modern machine learning.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proc. of NAACL_.
  * Dodge et al. (2019) Jesse Dodge, Suchin Gururangan, Dallas Card, Roy Schwartz, and Noah A. Smith. 2019\.  Show your work: Improved reporting of experimental results.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2185–2194, Hong Kong, China.
  * Ethayarajh and Jurafsky (2020) Kawin Ethayarajh and Dan Jurafsky. 2020.  Utility is in the eye of the user: A critique of nlp leaderboards.  In _Proc. of EMNLP_.
  * Forde and Paganini (2019) Jessica Zosa Forde and Michela Paganini. 2019.  The scientific method in the science of machine learning.
  * Gehman et al. (2020) Sam Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A Smith. 2020.  Realtoxicityprompts: Evaluating neural toxic degeneration in language models.  In _Findings of EMNLP_.
  * James and Stein (1961) W. James and C. Stein. 1961.  Estimation with quadratic loss.  _Proc. Fourth Berkeley Symp. Math. Statist. Prob._ , page 361–379.
  * Kim (2014) Yoon Kim. 2014.  Convolutional neural networks for sentence classification.  In _Proc. of EMNLP_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.
  * Melis et al. (2018) Gábor Melis, Chris Dyer, and Phil Blunsom. 2018.  On the state of the art of evaluation in neural language models.  In _Proc. of EMNLP_.
  * Reimers and Gurevych (2017) Nils Reimers and Iryna Gurevych. 2017.  Reporting score distributions makes a difference: Performance study of LSTM-networks for sequence tagging.  In _Proc. of EMNLP_.
  * Sculley et al. (2018) D. Sculley, Jasper Snoek, Ali Rahimi, and Alex Wiltschko. 2018.  Winner’s curse? On pace, progress, and empirical rigor.  In _Proc. of ICLR (Workshop Track)_.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proc. of EMNLP_.
  * Tang et al. (2020) Raphael Tang, Jaejun Lee, Ji Xin, Xinyu Liu, Yaoliang Yu, and Jimmy Lin. 2020.  Showing your work doesn’t always work.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2766–2772, Online.
  * Wasserman (2004) Larry A. Wasserman. 2004.  _All of Statistics: A Concise Course in Statistical Inference_.  Springer Texts in Statistics.
  * Yogatama and Smith (2015) Dani Yogatama and Noah A. Smith. 2015.  Bayesian optimization of text representations.  In _Proc. of EMNLP_.
  * Zhang et al. (2021) Tianyi Zhang, Felix Wu, Arzoo Katiyar, Kilian Q. Weinberger, and Yoav Artzi. 2021\.  Revisiting few-sample bert fine-tuning.  In _Proc. of ICLR_.

##  Appendix A Expected Validation Curves for two models, all three estimators

We include expected validation curves of the same data using all three
estimators in Figure 3. They look roughly the same.

Figure 3: $U_{n}^{B}$ (left), $V_{n}^{B}$ (middle) and $W_{n}^{B}$ (right)
curves of the same data, a CNN and a Linear Bag of Embeddings (LBoE),
evaluated on SST-5, with $B$=100. With such a large $B$ the three estimators
are very similar. For all three estimators, the CNN has higher expected
performance than the LBoE for all $n$.

##  Appendix B Training Data

The CNN and LBoE in Section 4 are trained on the Stanford sentiment treebank
5-way text classification task Socher et al. (2013). There are 8544 train
examples, 2210 test examples, and 1101 validation examples. It can be
downloaded here: http://nlp.stanford.edu/sentiment. We present label
distributions in Table 1.

Label | Train | Valid | Test
---|---|---|---
0 | 1092 | 139 | 279
1 | 2218 | 289 | 633
2 | 1624 | 229 | 389
3 | 2322 | 279 | 510
4 | 1288 | 165 | 399
Table 1: Label distributions for SST-5. 0 is “very negative”, 2 is “neutral”,
and 4 is “very positive”.

##  Appendix C Hyperparameter Ranges

The hyperparameter bounds for the CNN and LBoE in Section 4, which were
trained on SST-5 as described in Appendix B.

Computing infrastructure | GeForce GTX 1080 GPU
---|---
Number of search trials | 100
Search strategy | uniform sampling
Best validation accuracy | 41.3
Training duration | 77 sec

HP | number of epochs | patience | batch size | embedding | encoder | max filter size
---|---|---|---|---|---|---
Search space | 50 | 10 | 64 | GloVe (50 dim) | Convnet |  _uniform-integer_[1, 9]
Best assignment | 50 | 10 | 64 | GloVe (50 dim) | Convnet | 9

HP | number of filters | dropout | LR scheduler | patience | reduction factor
---|---|---|---|---|---
Search space |  _uniform-integer_[64, 512] |  _uniform-float_[0, 0.5] | reduce on plateau | 2 epochs | 0.5
Best assignment | 390 | 0.2 | reduce on plateau | 2 epochs | 0.5

HP | optimizer | LR
---|---|---
Search space | Adam |  _loguniform-float_[1e-6, 1e-1]
Best assignment | Adam | 0.0004

Table 2: SST (fine-grained) CNN classifier search space and best assignments.

Computing infrastructure | GeForce GTX 1080 GPU
---|---
Number of search trials | 100
Search strategy | uniform sampling
Best validation accuracy | 42.7
Training duration | 41 sec

Hyperparameter | number of epochs | patience | batch size | embedding | dropout
---|---|---|---|---|---
Search space | 50 | 10 | 64 | GloVe (50 dim) |  _uniform-float_[0, 0.5]
Best assignment | 50 | 10 | 64 | GloVe (50 dim) | 0.4

Hyperparameter | LR scheduler | patience | reduction factor | optimizer | LR
---|---|---|---|---|---
Search space | reduce on plateau | 2 epochs | 0.5 | Adam |  _loguniform-float_[1e-6, 1e-1]
Best assignment | reduce on plateau | 2 epochs | 0.5 | Adam | 0.044

Table 3: SST (fine-grained) BOE classifier search space and best assignments.