# Better Boosting with Bandits for Online Learning

Nikolaos Nikolaou  Joseph Mellor  Nikunj C. Oza  Gavin Brown  Department of
Physics & Astronomy, University College London, Gower Street, London, WC1E
6BT, UK
<EMAIL_ADDRESS>Usher Institute of Population Health Sciences and
Informatics, Old Medical School, Teviot Place, Edinburgh, EH8 9AG
<EMAIL_ADDRESS>NASA Ames Research Center, Moffett Field, CA 94035, USA
<EMAIL_ADDRESS>School of Computer Science, University of Manchester,
Kilburn Building, Oxford Road, Manchester, M13 9PL, UK
<EMAIL_ADDRESS>
###### Abstract

Probability estimates generated by boosting ensembles are poorly calibrated
because of the margin maximization nature of the algorithm. The outputs of the
ensemble need to be properly calibrated before they can be used as probability
estimates. In this work, we demonstrate that online boosting is also prone to
producing distorted probability estimates. In batch learning, calibration is
achieved by reserving part of the training data for training the calibrator
function. In the online setting, a decision needs to be made on each round:
shall the new example(s) be used to update the parameters of the ensemble or
those of the calibrator. We proceed to resolve this decision with the aid of
bandit optimization algorithms. We demonstrate superior performance to
uncalibrated and naively-calibrated on-line boosting ensembles in terms of
probability estimation. Our proposed mechanism can be easily adapted to other
tasks(e.g. cost-sensitive classification) and is robust to the choice of
hyperparameters of both the calibrator and the ensemble.

###### keywords:

Online learning, Boosting, Bandit optimization, Classifier calibration,
Probability estimation, Upper Confidence Bound, Thompson Sampling

††journal: ????

##  1 Introduction

AdaBoost [1] is an extensively studied ensemble learning method, with
connections to multiple theoretical frameworks like margin theory [2], game
theory [3], functional gradient descent [4], additive logistic regression [5],
probabilistic modelling [6], to name but a few. AdaBoost classifiers have been
very successful as evidenced by extensive experimental comparisons spanning
multiple datasets, such as the ones conducted in [7, 8], and applications like
face detection in phone cameras [9] and the Yahoo search engine for ranking
webpages [10]. The success of AdaBoost is further evidenced in numerous
machine learning competitions; indicatively, more than half of the winning
Kaggle entries have used gradient
boosting111https://github.com/dmlc/xgboost/tree/master/demo#machine-learning-
challenge-winning-solutions (incomplete list).

Yet despite its success in classification, ranking and regression tasks, the
probability estimates generated by AdaBoost have been known to be poorly
_calibrated_ , i.e. they deviate from _empirical class probabilities_ [5, 11,
12, 13]. When the goal is to generate probability estimates rather than just
to classify or rank examples, or when it is to solve a cost-sensitive
classification problem, the performance of AdaBoost suffers.

Previous work in _batch learning_ –tasks in which all data is available and
can be processed at once– has shown that applying some form of calibration to
the scores generated by AdaBoost considerably improves performance, in both
probability estimation [11] and cost-sensitive classification [14] tasks. In
batch learning scenarios calibration is achieved by _reserving part of the
training data_ to train a _calibrator function_ –usually a _logistic sigmoid_
or an _isotonic regression_ – to map uncalibrated raw scores to probability
estimates that _maximize the likelihood of the model_. This is done to avoid
_overfitting_ by training both the ensemble and the calibrator on the same
datapoints.

_Online learning_ deals with scenarios where data arrive _sequentially_
–either one datapoint at a time or in _minibatches_ – predictions are required
as soon as the new datapoints become available and the learner must update its
parameters using _only_ the previous datapoint (or minibatch). This way the
learner can _adapt to changing_ –even _adversarial_ – environments. Online
learning is also a preferable option when dealing with very large amounts of
data, when batch learning becomes expensive or even infeasible (due to
computational limitations or slow convergence of the _generalization error_)
[15, 16, 17]. Despite the increasing relevance of online learning given the
growth of _streaming_ and _big data_ applications and despite the success of
AdaBoost as a classifier and ranker, the probability estimation quality of
online boosting ensembles has not yet been studied in the literature.

In this paper we will demonstrate that online boosting ensembles [18] also
produce uncalibrated probability estimates under the most common _scoring
functions_ , i.e. ways of generating probability estimates. This motivates the
need for calibrating the probability estimates of online boosting ensembles.

However, calibration is less straightforward in the online setting. On each
round we need to _decide_ whether the new example(s) will be used to update
the parameters of the ensemble or those of the calibrator. A _naive approach_
is to use _a fixed policy of calibrating on every_ $N_{c}$ _rounds_. But how
do we set this _hyperparameter_ $N_{c}$? Different combinations of _problem_
(data, objective), _ensemble_ (base learner, ensemble size, scoring function
used) and _calibrator_ (calibration function, optimization method used) would
call for different values of $N_{c}$.

In this work we propose resolving this decision with the aid of _bandit
optimization algorithms_ [19, 20, 21]. Bandit algorithms allow us to choose
among a set of actions (here: ‘ _train on new minibatch_ ’ or ‘ _calibrate on
new minibatch_ ’) balancing _exploitation_ and _exploration_ in _stochastic_
or _adversarial_ , _stationary_ or _non-stationary_ settings. They do this by
_sampling the distribution of rewards of each of the actions_ (here: the
_increase in log-likelihood of the model following each action_) and
maintaining a model of said distribution that is updated upon each feedback.
The action to be taken in the next round is then chosen based on the models of
the reward distributions. The different bandit algorithms used –how they model
the reward distribution and how they decide which action to take next– are
discussed in Section 2.3.

Our bandit-based approach –more specifically UCB1-based policies [22, 23, 24],
and Thompson Sampling [25, 26, 27], especially in its discounted-rewards
version– shows _superior performance_ to uncalibrated and naively-calibrated
(i.e. employing fixed policies of calibrating on every $N_{c}$ rounds)
boosting ensembles in probability estimation. This approach is _very easy to
adapt to new objectives_ (e.g. cost-sensitive learning tasks). All we need to
do is change the reward function to the appropriate one for the task at hand
(e.g. decrease in classification risk after an action). Moreover, the method
is _very flexible and robust to the ensemble hyperparameter choices_ , as it
will learn an appropriate policy for alternating between the two actions
guided by the corresponding rewards of the two actions.

##  2 Background

This work focusses on binary learning tasks. The examples are considered to be
of the form $({\bf{x}}_{i},y_{i})$, where ${\bf{x}}_{i}$ is the feature vector
of the $i$-th example and $y_{i}\in\\{-1,1\\}$ is its class label. Extension
to the multiclass case is often handled by breaking down the problem into
multiple binary ones, so our analysis and its main results can carry over to
the multiclass case. We consider the online setting where examples are
presented to the learner in $M$ minibatches222The scenario where the examples
are arriving one at a time ($b=1$) is merely a common special case. of size
$b$. On the $n$-th iteration the learner performs the following steps:

  1. 1.

Receive new examples ${\bf{x}}_{i}$, $\forall{\bf{x}}_{i}\in minibatch_{n}$

  2. 2.

Predict the label $\hat{y_{i}}$ and/or
the probability estimate $\hat{p}(y_{i}=1|{\bf{x}}_{i})$, $\forall i\in
minibatch_{n}$

  3. 3.

Get true labels $y_{i}=f({\bf{x}}_{i})$, $\forall{\bf{x}}_{i}\in
minibatch_{n}$, where $f$ is the labelling function

  4. 4.

Update learner parameters accordingly

The steps above are intentionally left general enough to describe all learning
components encountered in the paper. Our goal is to study the quality of the
probability estimates generated by online boosting ensembles and strategies
for improving it. Online boosting ensembles consist of multiple base learners,
themselves also trained in an online fashion and –as we will see– the
techniques used for improving the probability estimates (both the calibrator
and the reward models of the bandits) are also learners trained in an online
fashion. All follow the same general approach defined above: they maintain a
model with a fixed number of parameters (i.e. memory and computational
complexity are constant w.r.t the number of examples seen so far), which they
update every time the labels of a new minibatch become available.

###  2.1 AdaBoost and Online Boosting

Adaptive Boosting (AdaBoost) [1] is a batch learning algorithm that constructs
an ensemble sequentially across multiple rounds. On each round, a new
component is added to the model. The principle behind it is to convert a weak
learner –a hypothesis whose predictions are marginally more accurate than
random guessing– into a strong one –one of error arbitrarily close to the
irreducible Bayes error rate. To achieve this, it focuses on each round on
correcting the mistakes of the previous model. This can be done either by
_reweighting_ or by _resampling_ the dataset on each round, putting more
emphasis on examples misclassified in the previous round and less on examples
correctly classified in it. Each weak learner is assigned a confidence
coefficient based on its predictive performance. Predictions are given by a
weighted majority vote among the weak learners, the weight of each learner’s
vote being its confidence coefficient.

The most popular algorithm for online boosting is the one proposed by Oza [18]
–henceforth _OnlineBoost_. The pseudocode is given in Algorithm 1. The
ensemble consists of a fixed number $T$ of components (weak learners). As in
batch AdaBoost, the idea is to increase the weight assigned to examples that
have been misclassified by previous models and decrease the weight assigned to
examples that have been classified correctly. In OnlineBoost, each example is
presented to each weak learner sequentially. If the $t$-th weak learner
misclassifies an example, the example’s weight for the purpose of updating the
parameters of the $(t+1)$-th weak learner will increase. Conversely, if the
$t$-th weak learner classifies an example correctly, the example’s weight for
the purpose of updating the $(t+1)$-th weak learner will decrease.

The (expected) weight of the current example is captured by the quantity
$\lambda$, which is used as the parameter of the _Poisson_ distribution from
which the ‘effective weight’ $k$ is drawn. A weight of $\lambda=1$ corresponds
to no particular emphasis (be it positive or negative) paid to the current
example333Here the _‘resampling’_ version of the algorithm is shown, and a
weight $k$ corresponds to training the weak learner $k$ times on the current
datapoint. If the weak learner accepts weighted instances, we can use a
_reweighting_ approach, i.e. train the classifier _once_ on the current
datapoint but assign it a weight of $k$. Moreover, since $k\sim
Poisson(\lambda)$, we have that $\lambda=\mathbb{E}[k]$, so $\lambda$ could be
used instead of $k$ when the reweighting approach is taken, leading to the
same updates, in expectation..

The base learner, _OnlineLearnAlg()_ , is called for updating the parameters
of the $t$-th weak learner on the $i$-th example. Finally, note that
$\lambda^{sc}_{t}$ is the sum of weights corresponding to correctly classified
examples so far by the $t$-th weak learner. Conversely, $\lambda^{sw}_{t}$ is
the sum of weights corresponding to examples misclassified by the $t$-th weak
learner so far.

Algorithm 1 OnlineBoost

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$ presented one at a time

For each $i$ do:

Set example weight $\lambda=1$

For each $t\in\\{1,2,\dots,T\\}$ do:

Set $k$ according to $Poisson(\lambda)$

Do $k$ times:

$h_{t}\leftarrow OnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}))$

If $h_{t}(\mathbf{x}_{i})=y_{i}$:

$\lambda^{sc}_{t}\leftarrow\lambda^{sc}_{t}+\lambda$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda\leftarrow\lambda\times\frac{1}{2(1-\epsilon_{t})}$

Else:

$\lambda^{sw}_{t}\leftarrow\lambda^{sw}_{t}+\lambda$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda\leftarrow\lambda\times\frac{1}{2\epsilon_{t}}$

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}$

In AdaBoost, an example’s weight is adjusted according to the base model’s
performance on the entire training set. Instead, in OnlineBoost, the weight
adjustment is based on the performance of a base model only on the examples
presented so far. This is of course something intrinsic to online learning. It
also means that the sequence of parameter updates will depend on the order in
which the examples are presented. Oza [18] showed that if a
lossless444Following the terminology of [18], we use the term _lossless online
learner_ to describe one whose output model for a given training set is
identical to that of the corresponding batch learner (e.g. online Naive
Bayes). online base learner is used, OnlineBoost converges to the same model
as an AdaBoost ensemble of the same size trained on the same dataset, as the
number of training examples $N\to\infty$.

To simplify the subsequent discussion we denote the confidence weight of the
$t$-th weak learner with

$\beta_{t}=\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}$ (1)

and the ensemble output –the quantity whose sign will equal the final
predicted class $H(\mathbf{x})$– with

$F(\mathbf{x})=\sum_{t=1}^{T}{\beta_{t}h_{t}(\mathbf{x})}.$ (2)

###  2.2 Probability Calibration

In many applications it is desirable to estimate the probability of a given
example belonging to each class. Quantifying the uncertainty about our
predictions allows us to capture the reliability of a classification, to
combine predictions from different sources or to make cost-sensitive decisions
e.g. by using _Bayesian Decision Theory_ principles as done in [14].

However, it is not always straightforward to obtain probability estimates from
the outputs of a classifier. Most classifiers allow their output to be treated
as a _score_ for each test example ${\bf{x}}$ that indicates ‘ _how positive_
’ ${\bf{x}}$ is deemed. The act of converting _raw scores_ to actual
probability estimates is called _calibration_.

Denoting with $N$ the total number of examples, $N_{s}$ the number of examples
with score $s\in\mathcal{S}$, were $\mathcal{S}$ is finite, and $N_{+,s}$ the
number of positives with score $s$, Zadrozny & Elkan [28] give the following
definition:

######  Definition: 1.

Calibrated classifier A classifier is said to be calibrated if the empirical
probability of an example with score $s(\bf{x})=s$ belonging to the positive
class, $N_{+,s(\bf{x})}/N_{s(\bf{x})}$, tends to the score value $s$, as
$N\to\infty,~{}\forall s$.

In practice, most classifiers generate uncalibrated scores, each learner
distorts them in its own way according to its inductive bias. We can improve
probability estimation by taking measures to correct these distortions, i.e.
by mapping the scores generated by the classifier to probability estimates,
that maximize the likelihood of the data –or some other measure of quality of
the probability estimation. The two most common approaches for doing this are
_logistic calibration_ (also known as _Platt scaling_) [29] and _isotonic
regression_ [30].

Logistic calibration finds a sigmoid mapping
$s({\bf{x}})\mapsto\hat{p}(y=1|{\bf{x}})$. Isotonic regression is non-
parametric and more general as it can be used to calibrate scores which
exhibit any form of monotonic distortion. It needs more data to avoid
overfitting and is less straightforward to adapt to the online setting.
A common measure used for evaluating probabilistic predictions, is the
_logarithmic loss_ 555Often referred to as ‘ _cross entropy_ ’, ‘ _logistic
loss_ ’ or simply ‘ _log-loss_ ’. A common alternative to the log-loss for
assessing probability estimates is the _Brier score_ , i.e. the mean squared
error of the probability estimates of the sample of size $N^{\prime}$ in
question,
$BS=\frac{1}{N^{\prime}}\sum_{i}(y_{i}-\hat{p}(y_{i}=1|{\bf{x}}_{i}))^{2}$,
denoting positive and negative labels with $y_{i}=1$ and $y_{i}=0$,
respectively. Both belong to the infinite family of measures known as _scoring
rules_ , for more information on which, we direct the reader to [31, 32].,
which is the _negative log-likelihood of the true labels given a probabilistic
classifier’s predictions_. Denoting positive examples’ labels with $y_{i}=1$
and negative examples’ labels with $y_{i}=0$, the log-loss over some set of
examples is given by

$\mathcal{L}=-\sum_{i}(y_{i}\log\hat{p}(y_{i}=1|{\bf{x}}_{i})+(1-y_{i})\log(1-\hat{p}(y_{i}=1|{\bf{x}}_{i})))\in\mathbb{R}.$
(3)

Another way to assess the calibration of a classifier’s probability estimates
is to use _reliability curves_ [33]. These are plots of probability estimates
versus empirical probabilities. For perfectly calibrated predictions, the
curve should be as close as possible to the diagonal as per the definition
above. In this paper we will be mainly using the running average of the log-
loss across all predictions so far to capture the progress of the quality of
the probability estimates generated by each ensemble. We will only
occasionally present reliability curves constructed across all predictions,
for illustrative purposes.

###  2.3 The multi-armed bandit problem

We will now introduce the basic principles of _bandit optimization_ and the
specific techniques we will use in the paper. In Section 5 we will adapt these
techniques to automate the process of calibrating probability estimates for
OnlineBoost.

The _multi-armed bandit problem_ is a simple model for sequential decision
making[19, 20, 21]. The name stems from the one-armed bandit machines found in
casinos. When the machine’s lever or ‘ _arm_ ’ is pulled, a cash reward is
received with some probability. In the multi-armed bandit problem we imagine
an _agent_ confronted with many such machines, all with differing
distributions for the rewards that the agent might receive by playing them.
The agent wishes to _cumulatively maximise their reward_ and can do this by
pulling the arm with highest reward in expectation. However, the _reward
distributions_ are unknown to the agent, and so must be _learned_. There is an
_exploration-exploitation tradeoff_ for the agent in this scenario. The agent
must balance exploiting the knowledge they have by pulling what they believe
is the best arm and exploring the arms to increase the _confidence_ in this
knowledge. There is a large literature on bandits which considers varying
assumptions about the reward distributions and the number of arms.

More formally, a general class of bandit problems is described by a set of
_arms_ $\mathcal{A}$ with an associated set of _reward distributions_
$\nu_{a,n}(\theta_{a,n})$ for $a\in\mathcal{A}$, denoting by $\theta_{a,n}$
the corresponding _distribution parameters_. The agent interacts with the
bandit in a series of rounds. At each _round_ $n$, the agent chooses an action
$a_{n}\in\mathcal{A}$ and then receives the _reward_
$X_{n}(a)\sim\nu_{a,n}(\theta_{a,n})$. We denote the _expected reward at round
$n$_ of an arm as $\mu_{n}(a)=\mathbb{E}\left[\nu_{a,n}(\theta_{a,n})\right]$
and so the _largest expected reward at time_ $n$ is given by
$\mu_{n}(*)=\max_{a}\mu_{n}(a)$. The _regret_ of a decision $a_{n}$ is given
by $r_{n}=\mu_{n}(*)-\mu_{n}(a_{n})$. The _cumulative regret_ after $M$ rounds
will be, $R_{M}=\sum_{n=1}^{M}r_{n}$. The goal of the agent is to _minimise
the expected cumulative regret_ , $\mathbb{E}\left[R_{M}\right]$.

In the standard problem, the reward distributions are assumed to be
_stationary_ and _Bernoulli_ such that
$\nu_{a,n}(\theta_{a,n})=\nu_{a,n^{\prime}}(\theta_{a,n^{\prime}})=\operatorname{Bernoulli}\left(\theta_{a}\right)$,
$\forall n,n^{\prime}$ and a _finite number of arms_ [19, 34]. There are many
variations of the problem, ranging from _bounded rewards_ [22], _adversarial
rewards_ [35], _non-stationary rewards_[36, 37, 38, 39], and _infinite number
of arms_ [40, 41, 42]. The bandit problem can be extended in many other ways;
for example there is much work on _contextual bandits_ [43, 44, 45], i.e.
policies that take a context, e.g. an example’s feature vector $\bf{x}$ into
account when deciding the next arm to pull.

In this work, we will assume that the rewards are _stochastic_ (i.e. non-
adversarial) but the reward distributions are _not_ necessarily stationary.
The non-stationarity will be handled by using _discounted rewards_ as will be
explained in Section 5. We will now discuss the specific bandit strategies
used in this paper.

####  2.3.1 Policies

##### Thompson Sampling

[25] is a popular strategy due to having both theoretical justification[26,
46, 34, 47] and strong empirical performance[27]. The strategy assumes a given
family of arm reward distributions $\nu$. A distribution is used to model
$P(\theta_{a}|H_{n})$ where $H_{n}$ is the _history of past actions and
associated rewards up to round_ $n$. After receiving a reward for a given
action $a$ the posteriors can be updated via Bayes rule. The agent chooses an
arm by first drawing a sample $\hat{\theta_{a}}(n)\sim P(\theta_{a}|H_{n})$
from each arm $a$. The agent chooses to pull arm
$a_{n}=\max_{a}\mathbb{E}\left[\nu(\hat{\theta_{a}}(n))\right]$. This is the
arm with the highest mean reward conditioned on the sampled parameters
$\hat{\theta_{a}}(n)$.

For the case of _Gaussian rewards with known variance_ $\sigma^{2}$, since
$\nu$ is Gaussian the unknown parameter $\theta_{a}=\mu_{a}$ is the mean
reward of the arm. Due to the _self-conjugacy of the Gaussian distribution_ ,
$P(\theta_{a}|H_{n})$ is also modelled as a Gaussian distribution with
parameters $\hat{\mu_{a}}(n)$ and $\hat{\sigma^{2}_{a}}(n)$, derived in
closed-form. The policy, henceforth ‘ _Gaussian Thompson Sampling_ ’, is shown
in Algorithm 2.

Algorithm 2 Gaussian Thompson Sampling (with known variance $\sigma^{2}$))

Let $\hat{\mu_{a}}(1)=0$,

$\hat{\sigma^{2}_{a}}(1)=1$ for $a\in\mathcal{A}.$

for $n=1,\dots,M$ do

Sample
$\hat{\theta}_{a}(n)\sim\mathcal{N}(\hat{\mu_{a}}(n),\hat{\sigma}^{2}_{a}(n))$,
for $a\in\mathcal{A}$.

Pull arm $a_{n}=\arg\\!\max_{a}\hat{\theta}_{a}(n)$

Let
$\hat{\mu}_{a_{n}}(n+1)=\frac{\hat{\mu}_{a_{n}}(n)\sigma^{2}+X_{n}(a_{n})\hat{\sigma}^{2}_{a_{n}}(n)}{\sigma^{2}+\hat{\sigma}^{2}_{a_{n}}(n)}$

$\hat{\sigma}^{2}_{a_{n}}(n+1)=\frac{\hat{\sigma}^{2}_{a_{n}}(n)\sigma^{2}}{\hat{\sigma}^{2}_{a_{n}}(n)+\sigma^{2}}$

Let $\hat{\mu_{a}}(n+1)=\hat{\mu_{a}}(n)$

$\hat{\sigma}^{2}_{a}(n+1)=\hat{\sigma}^{2}_{a}(n)$ for
$a\in\mathcal{A}\setminus\\{a_{n}\\}$.

##### Upper Confidence Bound (UCB) policies

refer to a particular class of bandit policy [22, 23, 24]. As the name
suggests such policies manage exploration through the use of _upper confidence
bounds on the estimates of mean arm rewards_. In this way UCB policies follow
a principle of _optimism in the face of uncertainty_. A UCB policy starts by
pulling each arm once. After this, for each arm the number of pulls of the arm
$k_{a}(n)$ and an estimate of the mean
$\hat{\mu}_{a}(n)=\frac{1}{k_{a}(n)}\sum_{j=1}^{n}X_{j}(a)I\left(a_{j}=a\right)$
is maintained. This is then combined with a _padding function_ $c(k_{a}(n),t)$
to give a upper confidence bound for the arm of
$U_{a}(n)=\hat{\mu}_{a}(n)+c(k_{a}(n),n)$. The agent chooses to pull arm
$a_{n}=\max_{a}U_{a}(n)$. As an example of a padding function, the one used by
_UCB1_ [22] is

$c(k_{a}(n),n)=\sqrt{\frac{2\ln n}{k_{a}(n)}}.$

Padding functions have been further improved with policies such as KL-UCB[23].
In the same paper an improved version of UCB1 was also introduced (see
Proposition 4 of [23]), to which we will henceforth refer as ‘ _UCB1-Improved_
’ .

##  3 Probability Estimates under Online Boosting Ensembles

It is straightforward to adapt the two most common _scoring functions_ , i.e.
ways of producing probability estimates for batch AdaBoost ensembles, to the
OnlineBoost case. The first choice, is to use the _weighed fraction of base
learners voting for the positive class_ [11].

$s({\bf{x}})=\frac{\sum_{t:h_{t}({\bf{x}})=1}\beta_{t}h_{t}({\bf{x}})}{\sum_{t=1}^{T}\beta_{t}h_{t}({\bf{x}})}\in[0,1].$
(4)

Another choice, motivated by the view of Boosting as an additive logistic
regression procedure [5] is666Eq. (5) differs from the one given in [5] by a
factor of $2$ that multiplies $F$ in the latter. This is simply because the
formulation of OnlineBoost of Algorithm 1 uses
$\beta_{t}=\log\frac{1-\epsilon_{t}}{\epsilon_{t}}$ as the confidence weight
of the $t$-th weak learner, while [5] uses
$\beta_{t}=\frac{1}{2}\log\frac{1-\epsilon_{t}}{\epsilon_{t}}$. Both forms
result in the same weight updates after normalizing the latter and to
equivalent predictions $H({\bf{x}})$.

$s^{\prime}({\bf{x}})=\frac{1}{1+e^{-F({\bf{x}})}}\in[0,1].$ (5)

Both scores of the form of Eq.(4) and of the form of Eq.(5) tend to values
close to $0$ and $1$. For the case of the former, this behaviour is connected
to the _margin maximization_ properties of boosting. The (normalized)
_hypothesis (a.k.a. voting) margin_ of a training example $({\bf{x}},y)$ under
the ensemble $F$ is defined as

$margin({\bf{x}},y)=\frac{yF({\bf{x}})}{\sum_{t=1}^{T}\beta_{t}}\in[-1,1].$
(6)

It is a combined measure of confidence and correctness of the classification
of the example under $F$. Its sign encodes whether the example was correctly
classified (positive) or misclassified (negative), while the magnitude of the
margin measures the _confidence of the final hypothesis_. AdaBoost _greedily
maximizes the margins of the training examples_ [5], promoting correct
classifications for which the ensemble is highly confident. In fact, this
margin maximizing behaviour of boosting algorithms has been connected to their
nice generalization properties as classifiers [2]. Theorem 1, given below,
shows that OnlineBoost –like AdaBoost– also greedily maximizes the margins of
the training examples. It allows much of the theory behind AdaBoost, including
the general form of the scoring functions and their properties, to carry over
to OnlineBoost.

######  Theorem 1.

OnlineBoost greedily minimizes the exponential loss of the margin
$L(y,F(\mathbf{x}))=e^{-yF(\mathbf{x})}$ via stochastic gradient descent steps
in the space of functions $F(\mathbf{x})$.

######  Proof Sketch.

See Appendix A.

The scores of the form of Eq.(4) assigned to the training examples can be
expressed [48] in terms of their corresponding margins as follows:

$s({\bf{x}})=\begin{cases}\frac{1}{2}(1+margin({\bf{x}},y))&\mbox{,~{}~{}~{}if
}y=1\\\ \frac{1}{2}(1-margin({\bf{x}},y))&\mbox{,~{}~{}~{}if
}y=-1.\end{cases}$ (7)

We see that as $margin({\bf{x}},y)\rightarrow 1$, the scores assume values
$s({\bf{x}})\rightarrow 0$ for negative examples and $s({\bf{x}})\rightarrow
1$ for positive examples. In other words, maximizing the margins –something
not only AdaBoost and OnlineBoost, but all boosting algorithms do, by virtue
of minimizing monotonically decreasing loss functions of the margin– forces
the ensemble to learn to assign scores that tend to $0$ and $1$.

As for scores of the form of Eq.(5), they can be expressed [6] as a _Product
of Experts (PoE)_ [49]

$\displaystyle
s^{\prime}({\bf{x}})=\frac{\prod_{t=1}^{T}\hat{p}_{t}(y=1|{\bf{x}})}{\prod_{t=1}^{T}\hat{p}_{t}(y=1|{\bf{x}})+\prod_{t=1}^{T}\hat{p}_{t}(y=-1|{\bf{x}})},$

_with experts’ probability estimates of the form_

$\displaystyle\hat{p}_{t}(y=1|{\bf{x}})=\begin{cases}\epsilon_{t}~{}~{}~{}~{}~{},&\mbox{
if }h_{t}({\bf{x}})=-1\\\ 1-\epsilon_{t},&\mbox{ if
}h_{t}({\bf{x}})=1,\end{cases}$
$\displaystyle\hat{p}_{t}(y=-1|{\bf{x}})=\begin{cases}1-\epsilon_{t},&\mbox{
if }h_{t}({\bf{x}})=-1\\\ \epsilon_{t}~{}~{}~{}~{}~{},&\mbox{ if
}h_{t}({\bf{x}})=1,\end{cases}$

_where
$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$ is
the weighted error of the $t$-th weak learner on the examples seen so far, and
$h_{t}({\bf{x}})\in\\{-1,1\\}$ its prediction on example ${\bf{x}}$._

In larger ensembles, the outputs tend to be more and more distorted. One
reason for this is that the PoE assumes that the experts produce independent
estimates and the more experts we add to the ensemble, the more likely we are
to deviate from such an assumption. Another reason is that a single expert
producing a score of $\hat{p}_{t}(y=1|{\bf{x}})=0$ or
$\hat{p}_{t}(y=1|{\bf{x}})=1$ to a given example ${\bf{x}}$ suffices to
dominate the ensemble’s score $s^{\prime}({\bf{x}})$ on that example. This was
discussed in the case of batch AdaBoost in [14] and holds for the OnlineBoost
ensembles as well.

In our experiments we use scores of the form of Eq. (4), motivated by previous
work in batch boosting [11, 10, 14]. Indeed, as we see in Figure 1, the scores
tend to be skewed towards $0$ or $1$, and OnlineBoost ensembles tend to be
very poorly calibrated. Note that poor probability estimation does not
necessarily lead to poor classification. In fact, as we discussed, the very
reason that makes boosting a successful classifier, namely its margin
maximization property, is also responsible for its poor performance as a
probability estimator, since it forces the ensemble to produce probability
estimates skewed towards $0$ or $1$.

Figure 1: [TOP] Reliability diagrams for OnlineBoost ensembles on two sample
datasets. The main diagonal corresponds to the ideal (perfectly calibrated)
probability estimator. We can see that the probability estimates generated by
OnlineBoost are far from ideal. [BOTTOM] Histogram of the probability
estimates (scores) assigned by the boosting ensemble. We see the scores tend
to values close to $0$ and $1$. The results shown here are averages and $95\%$
confidence intervals calculated across $10$ runs of training an ensemble of
$T=10$ online Naive Bayes classifiers using minibatch sizes of $b=50$.

##  4 Naive Calibration of Online Boosting

In the previous section, we saw theoretical and empirical evidence that
suggests that the probability estimates generated under OnlineBoost ensembles
are distorted and need to be properly calibrated. To our knowledge, the
calibration of online boosting ensembles has not been studied before in the
literature. In this section we present a simple calibration policy, which
directly draws from previous work on batch learning [11, 14]. In the next
section we will further refine this approach.

###  4.1 Online Platt Scaling

As a calibration method we choose Platt-scaling (logistic calibration). This
was done in part because OnlineBoost will tend to generate probability
estimates that tend towards $0$ or $1$ as discussed above -i.e. amenable to
sigmoid correction- and in part because the adaptation of the method in the
online scenario is easy and efficient. Platt-scaling consists of finding a
logistic sigmoid mapping of scores to probability estimates. The probability
estimates are thus given by:

$\hat{p}(y=1|{\bf{x}})=\frac{1}{1+e^{w_{1}s({\bf{x}})+w_{0}}},$ (8)

where $s({\bf{x}})$ are the uncalibrated scores of the form of Eq. (4) and
$w_{0}$ and $w_{1}$ are the parameters to be fitted.

We update the parameters of the sigmoid on one minibatch at a time (provided
said minibatch is used for calibration –see next subsection), such that the
log-loss of Eq. (3) is minimized777In the paper we use log-loss to assess
probabilistic predictions. Had we been using some other scoring rule (e.g.
Brier score), it would be sensible to minimize the same loss (e.g. squared
loss) to train the parameters of the sigmoid.. To account for class imbalance,
the Bayesian prior correction proposed by Platt [29] was applied. Rather than
using $y_{i}=1$ for positive labels and $y_{i}=0$ for negative labels, in Eq.
(3), we use respectively

$y_{i}=\frac{N_{+}+1}{N_{+}+2}\quad\text{and}\quad y_{i}=\frac{1}{N_{-}+2}.$
(9)

On every minibatch (be it used for calibration or for training), we update
$N_{+}$ and $N_{-}$, the current numbers of positive and negative examples
respectively encountered in the dataset so far. If the data distribution is
non-stationary, this also allows the predictions to adapt to prior probability
shift.

Hence the calibrator always keeps track of $4$ quantities: $N_{+}$ and $N_{-}$
mentioned above and $w_{0}$ and $w_{1}$, the current sigmoid parameters to be
updated on the next iteration.

###  4.2 A Naive Calibration Policy

A simple strategy is to use every $N_{c}$-th example to calibrate (update
$w_{0}$ and $w_{1}$) and the remaining ones to train the ensemble888The first
round is always used to train the ensemble.. As the calibrator function has
only two parameters, it is reasonable to expect that in the long term using
most minibatches to train the ensemble would yield better results. We
experiment with values $N_{c}\in\\{2,4,6,8,10,12,14\\}$, corresponding to
fractions of $\\{50\%,25\%,16.7\%,12.5\%,10\%,8.3\%,7.1\%\\}$ of the data,
respectively. Figure 2 shows reliability diagrams for uncalibrated OnlineBoost
and naively-calibrated OnlineBoost with $N_{c}=2$ on two sample datasets. We
see that even this most naive calibration policy considerably improves the
probability estimation behaviour of online boosting. In the next section we
will refine the naive calibration proposed here.

Figure 2: Reliability diagrams for uncalibrated OnlineBoost (green) and
naively-calibrated OnlineBoost with $N_{c}=2$ (blue) on two sample datasets.
The main diagonal corresponds to the ideal (perfectly calibrated) probability
estimator. We can see that some calibration –even of the most naive form–
considerably improves the probability estimation behaviour of online boosting.
The results shown here are averages and $95\%$ confidence intervals calculated
across $10$ runs of training an ensemble of $T=10$ online Naive Bayes
classifiers using minibatch sizes of $b=50$.

For completeness we should mention another obvious candidate naive policy of
calibration: On each minibatch, we can construct two models, one by performing
each of the two actions (train, calibrate). We then retain the model that
leads to the greatest decrease in log-loss. This approach is computationally
costlier, but as we only have two possible actions the increase in
computational cost is constant and potentially affordable. However, when
processing large amounts of data even a constant increase in computational
cost can matter. Another flaw is that this approach is less amenable to
extensions; in the next section we will discuss a bandit-based approach that
can scale to an arbitrary number of other actions besides the two discussed
here, or that can easily be adjusted to deal with non-stationary data,
adversarial environments or incorporate contextual information.

Most importantly, however, the policy is memoryless and greedy. It does not
encourage exploration and only exploits the action that reduced the log-loss
the most on the last minibatch. Considering that unlike updating the ensemble
parameters (which are geared towards reducing the classification error,
leaving the final estimate poorly calibrated), the update of the calibrator
parameters is explicitly performed with the objective of minimizing the log-
loss, that action is almost guaranteed to be ‘calibrate’. Indeed, in our
experiments with this technique, we saw that it reduced to always choosing to
update the parameters of the calibrator. This caused the final probability
estimates generated by this policy to be far worse than those produced by the
other policies discussed here. We will therefore exclude it from further
consideration.

##  5 Bandit Algorithms for Calibrated Online Boosting

Our results showed that employing a naive calibration policy is preferable to
not calibrating the probability estimates at all. It is clear however, that
the success of such a policy will depend on many factors: (1) the
characteristics of the dataset, (2) the evaluation measure used (log-
likelihood or Brier score for probability estimation, empirical risk for cost-
sensitive classification, etc.), (3) the hyperparameters of the ensemble (weak
learner, number of weak learners, scoring function), (4) the hyperparameters
of the calibrator (choice of calibration function, optimization algorithm to
train it). The interplay of these will determine the best value of $N_{c}$ for
a fixed policy of the type discussed in the previous section.

Ideally, we would like to _automate_ the process of learning a good policy of
alternating between the two actions. This is already an issue in batch
learning, where determining the correct fraction of the training data that
will be used for calibration is not obvious and will depend on all the factors
mentioned in the previous paragraph. But in an online setting, it becomes even
more important. The value of $N_{c}$ cannot be determined by cross-validation
as predictions need to be made on the fly. Moreover, the optimal value of
$N_{c}$ might _change_ during execution due to possible non-stationarity of
the data (be it stochastic or adversarial).

To solve this problem we employed the different bandit optimization algorithms
described in Section 2.3. The general methodology is described in Algorithm 3.
Each of the two actions (train, calibrate) is associated with a reward
distribution. After each action is taken, the parameters of its corresponding
reward distribution are updated accordingly.

Algorithm 3 Deciding when to calibrate under a given $BanditPolicy$

For each round $n$ do:

1 Receive unlabelled examples of $Minibatch_{n}$

2 Make predictions on examples of $Minibatch_{n}$

3 Receive labels of examples of $Minibatch_{n}$

4 Evaluate performance on $Minibatch_{n}$

5 If $n<2$ do:

6 Update ensemble parameters on examples of $Minibatch_{n}$ (Sec. 2.1)

7 Else:

8 Use reward $X_{n}$ to update the parameters of $BanditPolicy$

9 Use $BanditPolicy$ to decide action $a_{n}$ (Sec. 2.3)

10 If $a_{n}==$ _‘TRAIN’_ do:

11 Update ensemble parameters on examples of $Minibatch_{n}$ (Sec. 2.1)

12 Else:

13 Update calibrator parameters on examples of $Minibatch_{n}$ (Sec. 4.1)

14 Compute reward $X_{n}$ of performing action $a_{n}$ (Sec. 5)

The reward for each action is defined as the resulting _relative decrease in
log-loss after the action is taken_ :

$X_{n}(a_{n})=-\frac{\mathcal{L}_{n}-\mathcal{L}_{n-1}}{\mathcal{L}_{n-1}}=\frac{\mathcal{L}_{n-1}-\mathcal{L}_{n}}{\mathcal{L}_{n-1}}=1-\frac{\mathcal{L}_{n}}{\mathcal{L}_{n-1}}\in\mathbb{R},$
(10)

where $\mathcal{L}_{n-1}$ is the log-loss of round ${n-1}$, i.e. before
performing action $a_{n}$ and $\mathcal{L}_{n}$ is the log-loss of round
${n}$, i.e. after performing action $a_{n}$.

For the cases of UCB1, UCB1-Improved and Gaussian Thompson Sampling, we also
implemented versions employing discounted rewards to deal with the potentially
non-stationary nature of online learning. More specifically, on each update,
the cumulative rewards are multiplied by a discounting factor $\gamma<1$, i.e.
$R_{n}=\gamma R_{n-1}+r_{n}$. The result is that the influence of past rewards
decays geometrically.

We should note here that the non-stationarity can be due to the distribution
of the data changing, but also due to the actions performed, which might lead
to the reward distributions of the two actions changing. For example, after
many rounds of only performing one action (e.g. ‘training’), we would
intuitively expect that the reward distributions of the two actions have
changed considerably, the rewards for training becoming smaller and smaller
and the actual reward of calibrating having increased considerably since last
sampled. Especially the model we have for an action not taken for many rounds
(‘calibrate’, in this example) is expected to be poor. Discounting can protect
us to some extent from such behaviours.

##  6 Empirical Evaluation

###  6.1 Experimental Setup

In our experiments we compared uncalibrated OnlineBoost to its naively
calibrated version –i.e. a fixed policy of calibrating every $N_{c}$ rounds–
with $N_{c}\in\\{2,4,6,8,10,12,14\\}$, as well as to calibration under UCB1,
UCB1-Improved and Gaussian Thompson Sampling policies and their discounted
counterparts.

The uncalibrated probability estimates were of the form of Eq. (4). In the
calibrated variants, logistic calibration was applied, by minimizing the loss
of Eq. (3), with incremental BFGS steps999Although BFGS is not typically a
very popular choice for online learning, as the calibration step here always
consists of updating the two parameters of a sigmoid, the computational and
memory cost of BFGS is constant and low..

We experimented with different choices of weak learners, both lossless
(Gaussian Naive Bayes) and lossy (logistic regression, linear SVM, perceptron
–all trained with stochastic gradient descent)101010In the case of Gaussian
Naive Bayes we used the resampling version of OnlineBoost given in Algorithm 1
–i.e. the original from [18]. For all other learners, we used the faster
reweighting version described in Footnote $3$ as they supported it.. We also
examined the effect of different ensemble sizes ($T\in\\{10,25,50\\}$) and
explored different degrees of regularization on the weak learner
($\ell_{1}$-regularized logistic regression with a regularization parameter
$\lambda\in\\{10^{-1},10^{-2},10^{-3},0\\}$). Unless otherwise specified the
default parameters of _scikit-learn_ 111111http://scikit-learn.org/stable/
were used.

The hyperparameters of the bandit algorithms were fixed, as the purpose of
using these algorithms is to circumvent hyperparameter tuning. The Gaussian
prior for Thompson Sampling was set to $\mathcal{N}(0,1)$. Discounted reward
versions used a discount factor $\gamma=0.95$.

The experiments were carried out on $10$ real-world datasets, the
characteristics of which are given in Appendix $B$. The examples in _krvskp_ ,
_landsat_ , _splice_ , _waveform_ , _spambase_ , _mushroom_ , _musk2_ are
considered i.i.d., so they are used for simulating situations where online
learning is employed to generate good predictions faster than a batch learning
algorithm. For these, the minibatch size was set to $b=50$. The datasets
_weather_ , _electricity_ and _forest_ were considered non-stationary. As
these three datasets are also considerably larger than the other $7$, the
minibatch size was set to $b=100$ for faster processing.

###  6.2 Experimental Results

We present the negative log-likelihood across the entire dataset as an overall
measure of performance of each variant. We present the best and worst result
attained on average by fixed policies (in the sense of final log-loss
attained) and specify in each case the corresponding $N_{c}$ that produced it.
Only some characteristic results are presented here. The remaining ones are
given in Appendix $C$.

We also provide some characteristic learning curves on the negative log-
likelihood (average negative log-likelihood across all past predictions versus
number of minibatches seen). This allows us to observe how fast each algorithm
can generate good probability estimates. In each case, we report average
values and $95\%$ confidence intervals across $10$ runs121212Datasets that are
i.i.d. are shuffled on each run, thus changing the order in which examples are
presented to the learner. On non-stationary datasets, we respect the order in
which the examples arrive to preserve their non-stationary nature..

####  6.2.1 Experiments on stationary datasets.

We shall first present the results under various choices of weak learners on
stationary datasets. The results for varying ensemble size and degree of
regularization can be found in Appendix $C$, as they are qualitatively
similar. Tables 1–4 show the log-loss across the entire dataset. Figures 3 & 4
show the evolution of average log-loss during training for some selected
combinations of dataset, base learner and policy.

Table 1: Log-loss across the entire dataset. Lowest average value shown in bold. Results for Naive Bayes, $T=10$ on stationary datasets. Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.138$ | $0.081$ | $0.131$ | $0.072$ | $\mathbf{0.071}$ | $0.074$ | $0.129$ | $0.123$ | $0.073$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.002$ | $0.002$ | $0.004$ | $0.001$ | $\mathbf{0.001}$ | $0.002$ | $0.010$ | $0.011$ | $0.002$
_splice_ | $0.444$ | $0.280$ | $0.410$ | $0.234$ | $\mathbf{0.229}$ | $0.282$ | $0.353$ | $0.376$ | $0.232$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.034$ | $0.014$ | $0.014$ | $0.007$ | $\mathbf{0.009}$ | $0.022$ | $0.024$ | $0.037$ | $0.008$
_musk2_ | $0.723$ | $0.343$ | $0.427$ | $\mathbf{0.320}$ | $0.332$ | $0.397$ | $0.711$ | $0.441$ | $0.345$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.027$ | $0.008$ | $0.013$ | $\mathbf{0.006}$ | $0.003$ | $0.008$ | $0.025$ | $0.049$ | $0.008$
_krvskp_ | $1.252$ | $0.488$ | $0.720$ | $0.474$ | $0.472$ | $0.486$ | $0.627$ | $0.767$ | $\mathbf{0.468}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.154$ | $0.014$ | $0.075$ | $0.019$ | $0.012$ | $0.016$ | $0.114$ | $0.114$ | $\mathbf{0.020}$
_waveform_ | $0.824$ | $0.361$ | $0.466$ | $0.335$ | $\mathbf{0.334}$ | $0.342$ | $0.458$ | $0.492$ | $0.344$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.005$ | $0.009$ | $0.002$ | $\mathbf{0.004}$ | $0.007$ | $0.015$ | $0.024$ | $0.006$
_spambase_ | $2.37$ | $0.532$ | $0.735$ | $0.493$ | $0.483$ | $\mathbf{0.481}$ | $0.536$ | $0.540$ | $0.489$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.026$ | $0.006$ | $0.017$ | $0.006$ | $0.005$ | $\mathbf{0.008}$ | $0.028$ | $0.037$ | $0.005$
_mushroom_ | $0.770$ | $0.358$ | $0.503$ | $0.375$ | $0.335$ | $\mathbf{0.318}$ | $0.570$ | $0.570$ | $0.327$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$
$0.057$ | $0.011$ | $0.017$ | $0.018$ | $0.020$ | $\mathbf{0.006}$ | $0.036$ | $0.072$ | $0.010$
Table 2: Log-loss across the entire dataset. Lowest average value shown in bold. Results for logistic regression, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.330$ | $\mathbf{0.106}$ | $0.158$ | $0.107$ | $0.108$ | $0.108$ | $0.173$ | $0.203$ | $0.127$
$\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.011$ | $\mathbf{0.002}$ | $0.004$ | $0.003$ | $0.004$ | $0.004$ | $0.019$ | $0.018$ | $0.013$
_splice_ | $1.779$ | $0.626$ | $0.895$ | $\mathbf{0.506}$ | $0.554$ | $0.636$ | $0.711$ | $1.155$ | $0.584$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.059$ | $0.023$ | $0.034$ | $\mathbf{0.029}$ | $0.020$ | $0.068$ | $0.117$ | $0.169$ | $0.034$
_musk2_ | $1.276$ | $0.331$ | $0.398$ | $0.321$ | $0.330$ | $\mathbf{0.318}$ | $0.536$ | $0.514$ | $0.322$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.015$ | $0.003$ | $0.008$ | $0.004$ | $0.004$ | $\mathbf{0.003}$ | $0.049$ | $0.038$ | $0.006$
_krvskp_ | $1.151$ | $0.633$ | $0.881$ | $\mathbf{0.519}$ | $0.528$ | $0.645$ | $0.825$ | $0.733$ | $0.555$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.073$ | $0.041$ | $0.042$ | $\mathbf{0.037}$ | $0.017$ | $0.048$ | $0.074$ | $0.041$ | $0.033$
_waveform_ | $1.700$ | $0.444$ | $0.596$ | $\mathbf{0.427}$ | $0.429$ | $0.428$ | $0.503$ | $0.519$ | $0.464$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.037$ | $0.004$ | $0.019$ | $\mathbf{0.003}$ | $0.007$ | $0.006$ | $0.026$ | $0.030$ | $0.016$
_spambase_ | $1.182$ | $0.409$ | $0.572$ | $0.390$ | $0.395$ | $0.407$ | $0.540$ | $0.477$ | $\mathbf{0.389}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.018$ | $0.006$ | $0.010$ | $0.005$ | $0.006$ | $0.007$ | $0.029$ | $0.024$ | $\mathbf{0.006}$
_mushroom_ | $1.001$ | $0.343$ | $0.454$ | $0.322$ | $0.315$ | $\mathbf{0.312}$ | $0.531$ | $0.592$ | $0.330$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.023$ | $0.007$ | $0.017$ | $0.007$ | $0.006$ | $\mathbf{0.007}$ | $0.026$ | $0.026$ | $0.006$
Table 3: Log-loss across the entire dataset. Lowest average value shown in bold. Results for linear SVM, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.245$ | $0.130$ | $0.184$ | $0.118$ | $0.121$ | $0.127$ | $0.250$ | $0.243$ | $\mathbf{0.111}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.019$ | $0.009$ | $0.010$ | $0.008$ | $0.008$ | $0.010$ | $0.025$ | $0.034$ | $\mathbf{0.004}$
_splice_ | $1.391$ | $0.663$ | $0.922$ | $0.622$ | $\mathbf{0.586}$ | $0.609$ | $0.816$ | $0.666$ | $0.640$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.064$ | $0.018$ | $0.040$ | $0.031$ | $\mathbf{0.022}$ | $0.020$ | $0.105$ | $0.088$ | $0.038$
_musk2_ | $0.953$ | $\mathbf{0.385}$ | $0.432$ | $0.400$ | $0.390$ | $0.406$ | $0.639$ | $0.622$ | $0.386$
$\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.020$ | $\mathbf{0.008}$ | $0.007$ | $0.006$ | $0.007$ | $0.008$ | $0.061$ | $0.066$ | $0.005$
_krvskp_ | $1.081$ | $0.671$ | $0.897$ | $\mathbf{0.608}$ | $0.648$ | $0.677$ | $0.706$ | $0.811$ | $0.667$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.050$ | $0.022$ | $0.027$ | $\mathbf{0.021}$ | $0.027$ | $0.029$ | $0.047$ | $0.041$ | $0.030$
_waveform_ | $1.156$ | $0.487$ | $0.615$ | $0.453$ | $\mathbf{0.451}$ | $\mathbf{0.451}$ | $0.611$ | $0.603$ | $0.464$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.045$ | $0.013$ | $0.015$ | $0.005$ | $\mathbf{0.004}$ | $\mathbf{0.005}$ | $0.021$ | $0.076$ | $0.005$
_spambase_ | $0.893$ | $0.440$ | $0.551$ | $0.411$ | $\mathbf{0.410}$ | $0.418$ | $0.560$ | $0.612$ | $0.414$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.019$ | $0.008$ | $0.010$ | $0.005$ | $\mathbf{0.007}$ | $0.009$ | $0.028$ | $0.053$ | $0.0037$
_mushroom_ | $0.673$ | $0.374$ | $0.489$ | $0.359$ | $0.363$ | $\mathbf{0.352}$ | $0.506$ | $0.573$ | $0.357$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.015$ | $0.006$ | $0.015$ | $0.006$ | $0.006$ | $\mathbf{0.005}$ | $0.036$ | $0.039$ | $0.007$
Table 4: Log-loss across the entire dataset. Lowest average value shown in bold. Results for perceptron, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.258$ | $0.120$ | $0.190$ | $0.125$ | $\mathbf{0.103}$ | $0.115$ | $0.164$ | $0.198$ | $0.120$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.005$ | $0.009$ | $0.013$ | $\mathbf{0.004}$ | $0.005$ | $0.014$ | $0.028$ | $0.008$
_splice_ | $1.453$ | $0.683$ | $0.879$ | $\mathbf{0.566}$ | $0.624$ | $0.642$ | $0.759$ | $0.651$ | $0.607$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.037$ | $0.033$ | $0.050$ | $\mathbf{0.021}$ | $0.028$ | $0.025$ | $0.105$ | $0.022$ | $0.027$
_musk2_ | $0.945$ | $0.392$ | $0.443$ | $0.390$ | $\mathbf{0.385}$ | $0.419$ | $0.591$ | $0.648$ | $0.408$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.030$ | $0.006$ | $0.012$ | $0.006$ | $\mathbf{0.006}$ | $0.014$ | $0.044$ | $0.067$ | $0.013$
_krvskp_ | $1.021$ | $0.745$ | $0.909$ | $0.632$ | $\mathbf{0.609}$ | $0.777$ | $0.812$ | $0.811$ | $0.611$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.042$ | $0.031$ | $0.043$ | $0.037$ | $\mathbf{0.022}$ | $0.079$ | $0.069$ | $0.062$ | $0.017$
_waveform_ | $1.106$ | $0.498$ | $0.589$ | $0.468$ | $0.492$ | $0.486$ | $0.573$ | $0.686$ | $\mathbf{0.456}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.027$ | $0.010$ | $0.021$ | $0.010$ | $0.034$ | $0.026$ | $0.029$ | $0.066$ | $\mathbf{0.008}$
_spambase_ | $0.885$ | $0.430$ | $0.575$ | $\mathbf{0.400}$ | $0.415$ | $0.415$ | $0.521$ | $0.620$ | $0.418$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.006$ | $0.010$ | $\mathbf{0.004}$ | $0.004$ | $0.007$ | $0.027$ | $0.043$ | $0.008$
_mushroom_ | $0.670$ | $0.383$ | $0.489$ | $0.359$ | $\mathbf{0.350}$ | $0.367$ | $0.502$ | $0.599$ | $0.355$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.006$ | $0.011$ | $0.003$ | $\mathbf{0.006}$ | $0.004$ | $0.032$ | $0.033$ | $0.006$

In Tables 1–4 we show on bold the best policy on average for each dataset.
Note that in many situations the confidence intervals overlap, in which
situation no clear winning policy can be determined.

We see that regardless of the weak learner used, it is almost always the case
that applying some calibration (even under the worst fixed policy) produces
significantly better probability estimates than applying no calibration. This
is in vein with results batch boosting [11, 14] and agrees with both our
theoretical intuitions and the empirical analysis of Section 3.

Moreover, it is almost always the case that certain bandit policies –more
specifically the non-discounted versions of UCB1 and UCB1-Improved closely
followed by Gaussian Thompson Sampling, especially in its discounted version–
significantly outperform the best fixed calibration policy. Even when they
don’t, the best fixed calibration policy does not significantly outperform
them. We can conclude that these policies are producing at least as good
probability estimates as the best fixed policy in each case.

To get a clearer picture of this, and see how fast the log-loss reduces under
each policy, in Figures 3 & 4 we provide some characteristic learning curves.
As the bandit policies produce comparably good results, to prevent cluttering,
we only include one bandit policy per figure (UCB1-Improved or discounted
Gaussian Thompson Sampling), compared against the best and worst fixed policy
and the uncalibrated online boosting ensemble. We specifically chose to
visualize the results on the datasets for which the best fixed policy is
competitive –for some choice of weak learner– with bandit policies when its
predictions are evaluated across the entire dataset. In other words, we only
provide learning curves for the datasets in which the confidence intervals of
the best fixed policy overlap with those of the winning policy in at least one
of the Tables 1–4.

Figure 3: Log-loss versus number of minibatches seen. Lower values correspond
to better probability estimation. The best and worst fixed calibration
policies are compared against uncalibrated OnlineBoost and to calibration
under the non-discounted UCB1-Improved policy. UCB1, discounted Gaussian
Thompson Sampling performed similarly. Results for Naive Bayes, $T=10$ on
stationary datasets. Only datasets for which the best fixed policy is
competitive with bandit policies are shown. Note how fast the log-loss reduces
under the bandit policies.

Figure 4: Log-loss versus number of minibatches seen. Lower values correspond
to better probability estimation. The best and worst fixed calibration
policies are compared against uncalibrated OnlineBoost and calibration under
the non-discounted UCB1-Improved policy. UCB1, discounted Gaussian Thompson
Sampling performed similarly. Results for logistic regression, $T=10$ on
stationary datasets. Only datasets for which the best fixed policy is
competitive with bandit policies are shown. Note how fast the log-loss reduces
under the bandit policies.

####  6.2.2 Experiments on non-stationary datasets.

Next, we present experiments on the non-stationary datasets for Naive Bayes
with $T=25$ in Table 5 and Figure 5. The general pattern we observed in the
previous set of experiments also appears here. Inspecting the largest dataset
used in our study, _forest_ , we can see that the different calibration
policies produce similar results with one another. This appears to be because
ample datapoints are available and the feature space is relatively small (the
dataset consists of $581,012$ datapoints and only $54$ features) to allow
learning both good ensemble parameters and calibrator parameters regardless of
the relative amount of data used for each of these learning tasks.

Table 5: Log-loss across the entire dataset. Lowest average value shown in bold. Results for Naive Bayes, $T=25$ on nonstationary datasets. The low variance is due to (i) not shuffling the datapoints on each run, respecting the order in which they appear & (ii) the larger ratio of datapoints to features compared to the stationary datasets used. Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_weather_ | $1.599$ | $0.583$ | $0.683$ | $0.579$ | $0.578$ | $0.585$ | $0.760$ | $0.739$ | $\mathbf{0.572}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.062$ | $0.002$ | $0.008$ | $0.001$ | $0.001$ | $0.007$ | $0.083$ | $0.036$ | $\mathbf{0.002}$
_electricity_ | $4.662$ | $0.604$ | $0.631$ | $0.599$ | $\mathbf{0.594}$ | $0.608$ | $0.612$ | $0.601$ | $0.609$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.126$ | $0.001$ | $0.004$ | $0.001$ | $\mathbf{0.002}$ | $0.002$ | $0.002$ | $0.009$ | $0.002$
_forest_ | $5.618$ | $0.645$ | $0.660$ | $0.645$ | $\mathbf{0.643}$ | $0.647$ | $0.677$ | $0.648$ | $0.657$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.010$ | $0.001$ | $0.001$ | $0.002$ | $\mathbf{0.001}$ | $0.001$ | $0.015$ | $0.006$ | $0.004$

Figure 5: Log-loss versus number of minibatches seen. Lower values correspond
to better probability estimation. The best and worst fixed calibration
policies are compared against calibration under the non-discounted
UCB1-Improved policy [LEFT] or the discounted Gaussian Thompson Sampling
policy [RIGHT]. Results for Naive Bayes, $T=25$ on nonstationary datasets.
Uncalibrated OnlineBoost curves were omitted due to their large log-loss (see
Table 5).

###  6.3 General observations

Overall, calibration under any policy almost always improves the probability
estimation w.r.t. uncalibrated OnlineBoost. As far as fixed policies are
concerned, the policy with $N_{c}=2$ and that with $N_{c}=4$ dominated the
rest in our experiments, while $N_{c}=12$ and $N_{c}=14$ were the values that
led to the poorest probability estimates. This was to be expected, as it
suggests that the more frequently we calibrate, the better the resulting
probability estimates will be (averaged across all rounds).

Moreover, we saw that certain bandit policies (UCB1 policies without reward
discounting and discounted-reward Gaussian Thompson Sampling) consistently
exceed or at least match the probability estimation performance of the best
fixed calibration policy. These results are robust to the choice of weak
learner and the presence or absence of non-stationarity in the dataset but
also to the ensemble size and degree of weak learner regularization (see
Appendix $C$).

It should also be noted that the computational cost of the bandit policies is
the same as that of the fixed ones (assuming a given value of $N_{c}$ for the
latter) and that finding the best fixed policy requires a search over the
possible values of $N_{c}$, something impossible in an online setting without
parallelization or increasing the computational cost. Finally, bandit policies
allow the ratio of training over calibrating steps to be adaptive, unlike,
fixed policies. All these reasons make bandit policies superior to naive
calibration.

Overall, discounting rewards –at least as applied to our experiments–
considerably improves Thompson Sampling, but greatly deteriorates UCB-based
policies. In Thompson Sampling, discounting increases the variance of the
reward posteriors. This increases the probability of the currently non-optimal
arm being pulled. On the other hand, we observed that discounted UCB policies
tended to get ‘trapped’ to situations where only one action (either ‘train’ or
‘calibrate’) was taken. In discounted UCB policies, the padding function’s
value for an action shrinks with the number of times it has been performed. It
appears that in the situations examined, the padding function’s value for the
action performed shrinks more and more slowly and never gets to the point
where it eventually allows the upper confidence bound of the other action to
overtake its own.

##  7 Conclusion and Future Work

We examined probability estimation in online boosting ensembles and found that
the scores they generate are distorted in a systematic fashion. We saw that
–as in the case of batch boosting– calibration can greatly improve the
probability estimates. We resolved the problem of deciding when to train the
ensemble and when to calibrate with the use of bandit optimization. More
specifically, UCB1 policies[22, 23, 24] without reward discounting and
Thompson Sampling[25, 26, 27], especially with reward discounting were found
to perform at least as well as the best naive calibration policy in terms of
probability estimation in every experiment.

The merits of using bandit policies over naive calibration are manifold. Not
only is the overall probability estimation performance superior, but it also
converges much faster than the latter (in terms of minibatches seen).
Moreover, to find the best naive calibration policy (i.e. fixed policy of
calibrating on every $N_{c}$ rounds), we need to either determine the value of
$N_{c}$ in advance, which is not possible in an online –possibly non-
stationary– setting. Furthermore, a fixed policy would be unable to adapt to
non-stationarity: the optimal ratio of train and calibration actions might
need to change during the course of training. The memory and computational
complexity of the Bandit policies we examine here is constant w.r.t. the
number of examples seen (as is required for online learning) and is the same
as that of the fixed policies. We found that the superiority of these policies
is robust to the choice of weak learner, ensemble size, degree of
regularization and across datasets –both stationary and non-stationary.
Finally, it would be straightforward to apply the same techniques to other
types of learning tasks e.g. cost-sensitive or imbalanced class learning
(situations in which good probability estimates are necessary for making
decisions), simply by changing the reward function.

The purpose of this work was not to determine the best calibration method for
an online boosting ensemble, but rather to identify fast, flexible and
successful policies for balancing between training the ensemble and the
calibrator (regardless of their specifics) in a hyperparameter-free fashion.
In future work, to improve probability estimation, we can use the online
version of isotonic regression [50], or produce online adaptations of spline
calibration [51] or beta calibration [52] to calibrate the scores of the
ensemble. Isotonic regression is a non-parametric method that can capture
score distortions of any non-decreasing form. It is prone to overfitting in
the presence of small samples, but is expected to outperform logistic
calibration as the number of available data grows. Spline calibration is a
smoothed version of the –piecewise-linear– former. Beta calibration is an
improvement over logistic calibration, especially when score distributions are
heavily skewed or when the scores happen to already be calibrated.

An alternative direction for future work could be to explore different bandit
policies based on more relaxed learning assumptions. These could include the
use of contextual bandits [53] that take into account the feature vector
${\bf{x}}$ of new instances when selecting the next action. Another family of
bandit policies worth exploring is that of adversarial bandits [35], which can
handle environments that adapt to our actions.

## References

  * [1] Y. Freund, R. E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55 (1) (1997) 119–139.
  * [2] R. E. Schapire, Y. Freund, P. Bartlett, W. S. Lee, Boosting the margin: a new explanation for the effectiveness of voting methods, The Annals of Statistics 26 (5) (1998) 1651–1686.
  * [3] Y. Freund, R. E. Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior 29 (1999) 79–103.
  * [4] L. Mason, J. Baxter, P. Bartlett, M. Frean, Boosting algorithms as gradient descent, Neural Information Processing Systems (2000) 512–518.
  * [5] J. Friedman, T. Hastie, R. Tibshirani, Additive logistic regression: a statistical view of boosting, Annals of Statistics 28 (2000) 337–407.
  * [6] N. U. Edakunni, G. Brown, T. Kovacs, Boosting as a product of experts, Uncertainty in Artificial Intelligence.
  * [7] R. Caruana, A. Niculescu-Mizil, An empirical comparison of supervised learning algorithms, in: International Conference on Machine Learning, 2006, pp. 161–168.
  * [8] M. Fernández-Delgado, E. Cernadas, S. Barro, D. Amorim, Do we need hundreds of classifiers to solve real world classification problems?, Journal of Machine Learning Research 15 (2014) 3133–3181.
  * [9] P. Viola, M. Jones, Fast and robust classification using asymmetric AdaBoost and a detector cascade, in: Neural Information Processing Systems, 2002.
  * [10] D. Cossock, T. Zhang, Statistical analysis of Bayes optimal subset ranking, IEEE Transactions on Information Theory 54 (11) (2008) 5140–5154.
  * [11] A. Niculescu-Mizil, R. Caruana, Obtaining calibrated probabilities from boosting, in: Uncertainty in Artificial Intelligence, 2005.
  * [12] D. Mease, A. J. Wyner, A. Buja, R. Schapire, Boosted classification trees and class probability/quantile estimation, Journal of Machine Learning Research 8 (2006) 2007.
  * [13] D. Mease, A. J. Wyner, Evidence contrary to the statistical view of boosting, Journal of Machine Learning Research 9 (2008) 131–156.
  * [14] N. Nikolaou, N. Edakunni, M. Kull, P. Flach, G. Brown, Cost-sensitive boosting algorithms: Do we really need them?, Machine Learning 104 (2) (2016) 359–384.
  * [15] D. R. Wilson, T. R. Martinez, The general inefficiency of batch training for gradient descent learning, Neural Networks 16 (10) (2003) 1429–1451.
  * [16] O. Bousquet, L. Bottou, The tradeoffs of large scale learning, in: Advances in neural information processing systems, 2008, pp. 161–168.
  * [17] Y. Bengio, Practical recommendations for gradient-based training of deep architectures, in: Neural networks: Tricks of the trade, Springer, 2012, pp. 437–478.
  * [18] N. C. Oza, Online bagging and boosting, in: Systems, man and cybernetics, 2005 IEEE international conference on, Vol. 3, IEEE, 2005, pp. 2340–2345.
  * [19] T. L. Lai, H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics 6 (1) (1985) 4 – 22.
  * [20] D. Bergemann, J. Valimaki, Bandit problems, Cowles Foundation Discussion Papers 1551, Cowles Foundation for Research in Economics, Yale University (Jan. 2006).
  * [21] V. Kuleshov, P. Doina, Algorithms for the multi-armed bandit problem, Journal of Machine Learning Research.
  * [22] P. Auer, N. Cesa-Bianchi, P. Fischer, Finite-time analysis of the multiarmed bandit problem, Mach. Learn. 47 (2-3) (2002) 235–256.
  * [23] A. Garivier, O. Cappé, The kl-ucb algorithm for bounded stochastic bandits and beyond, in: Conference On Learning Theory, Jul. 2011, pp. 359–376.
  * [24] E. Kaufmann, O. Cappé, A. Garivier, On bayesian upper confidence bounds for bandit problems, Journal of Machine Learning Research - Proceedings Track 22 (2012) 592–600.
  * [25] W. R. Thompson, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika 25 (1933) pp. 285–294.
  * [26] S. Agrawal, N. Goyal, Analysis of thompson sampling for the multi-armed bandit problem, in: COLT, 2012, pp. 39.1–39.26.
  * [27] O. Chapelle, L. Li, An empirical evaluation of thompson sampling, in: J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, 2011, pp. 2249–2257.
  * [28] B. Zadrozny, C. Elkan, Transforming classifier scores into accurate multiclass probability estimates (2002).
  * [29] J. C. Platt, Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods, in: Advances in Large Margin Classifiers, MIT Press, 1999, pp. 61–74.
  * [30] T. Robertson, F. Wright, R. Dykstra, Order Restricted Statistical Inference, Probability and Statistics Series, Wiley, 1988.
  * [31] R. L. Winkler, Scoring rules and the evaluation of probability assessors, Journal of the American Statistical Association 64 (327) (1969) 1073–1078.
  * [32] M. Kull, P. Flach, Novel decompositions of proper scoring rules for classification: score adjustment as precursor to calibration, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2015, pp. 68–85.
  * [33] M. H. DeGroot, S. E. Fienberg, The comparison and evaluation of forecasters, The statistician (1983) 12–22.
  * [34] S. Agrawal, N. Goyal, Further optimal regret bounds for thompson sampling, CoRR abs/1209.3353.
  * [35] P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, The nonstochastic multiarmed bandit problem, SIAM J. Comput. 32 (1) (2003) 48–77.
  * [36] P. Viappiani, Thompson sampling for bayesian bandits with resets, in: P. Perny, M. Pirlot, A. Tsoukiàs (Eds.), ADT, Vol. 8176 of Lecture Notes in Computer Science, Springer, 2013, pp. 399–410.
  * [37] J. Mellor, J. Shapiro, Thompson sampling in switching environments with bayesian online change detection, in: AISTATS, Vol. 31 of JMLR Proceedings, JMLR.org, 2013, pp. 442–450.
  * [38] O. C. Granmo, S. Berg, Solving non-stationary bandit problems by random sampling from sibling kalman filters, in: Proceedings of the 23rd international conference on Industrial engineering and other applications of applied intelligent systems - Volume Part III, IEA/AIE’10, Springer-Verlag, Berlin, Heidelberg, 2010, pp. 199–208.
  * [39] A. Garivier, E. Moulines, On upper-confidence bound policies for switching bandit problems, in: J. Kivinen, C. Szepesvári, E. Ukkonen, T. Zeugmann (Eds.), ALT, Vol. 6925 of Lecture Notes in Computer Science, Springer, 2011, pp. 174–188.
  * [40] R. Kleinberg, A. Slivkins, E. Upfal, Multi-armed bandits in metric spaces, in: Proceedings of the 40th annual ACM symposium on Theory of computing, STOC ’08, ACM, New York, NY, USA, 2008, pp. 681–690.
  * [41] A. Slivkins, Multi-armed bandits on implicit metric spaces, in: Advances in Neural Information Processing Systems, 2011, pp. 1602–1610.
  * [42] N. Srinivas, A. Krause, K. S. M., M. Seeger, Gaussian process bandits without regret: An experimental design approach, CoRR abs/0912.3995.
  * [43] L. Li, W. Chu, J. Langford, X. Wang, Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms., in: I. King, W. Nejdl, H. Li (Eds.), WSDM, ACM, 2011, pp. 297–306.
  * [44] K. Lloyd, D. S. Leslie, Context-dependent decision-making: a simple bayesian model, Journal of The Royal Society Interface 10 (82).
  * [45] B. C. May, N. Korda, A. Lee, D. S. Leslie, Optimistic bayesian sampling in contextual-bandit problems 13(1), Journal of Machine Learning Research 98888 (2012) 2069–2106.
  * [46] E. Kaufmann, N. Korda, R. Munos, Thompson sampling: An optimal finite time analysis, CoRR abs/1205.4217.
  * [47] N. Korda, E. Kaufmann, R. Munos, Thompson sampling for 1-dimensional exponential family bandits, in: C. J. C. Burges, L. Bottou, Z. Ghahramani, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, 2013, pp. 1448–1456.
  * [48] N. Nikolaou, Cost-sensitive boosting: A unified approach, PhD Thesis, Manchester University.
  * [49] G. E. Hinton, Training products of experts by minimizing contrastive divergence, Neural Computation 14 (2002) 1771–1800.
  * [50] W. Kotłowski, W. M. Koolen, A. Malek, Online isotonic regression, arXiv preprint arXiv:1603.04190.
  * [51] A. Goldstein, A. Kapelner, J. Bleich, E. Pitkin, Peeking inside the black box: Visualizing statistical learning with plots of individual conditional expectation, Journal of Computational and Graphical Statistics 24 (1) (2015) 44–65.
  * [52] M. Kull, T. De Menezes E Silva Filho, P. Flach, Beta calibration: a well-founded and easily implemented improvement on logistic calibration for binary classifiers, Journal of Machine Learning Research, 2017.
  * [53] A. Krause, C. S. Ong, Contextual gaussian process bandit optimization, in: Advances in Neural Information Processing Systems, 2011, pp. 2447–2455.
  * [54] J. H. Friedman, Greedy function approximation: A gradient boosting machine, Annals of Statistics 29 (2000) 1189–1232.
  * [55] V. Losing, B. Hammer, H. Wersing, Dedicated Memory Models for Continual Learning in the Presence of Concept Drift, in: Continual Learning Workshop of the Conference on Neural Information Processing Systems (NIPS), 2016.

## Appendix A: Proof sketch of Theorem 1

######  Theorem.

OnlineBoost greedily minimizes the exponential loss of the margin
$L(y,F(\mathbf{x}))=e^{-yF(\mathbf{x})}$ via stochastic gradient descent steps
in the space of functions $F(\mathbf{x})$.

######  Proof Sketch.

In Algorithm 4, we repeat the OnlineBoost algorithm for convenience.

Algorithm 4 OnlineBoost (Original version)

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$ presented one at a time

For each $i$ do:

Set example weight $\lambda=1$

For each $t\in{1,2,\dots,T}$ do:

Set $k$ according to $Poisson(\lambda)$

Do $k$ times:

$h_{t}\leftarrow OnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}))$

If $h_{t}(\mathbf{x}_{i})=y_{i}$:

$\lambda^{sc}_{t}\leftarrow\lambda^{sc}_{t}+\lambda$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda\leftarrow\lambda\times\frac{1}{2(1-\epsilon_{t})}$

Else:

$\lambda^{sw}_{t}\leftarrow\lambda^{sw}_{t}+\lambda$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda\leftarrow\lambda\times\frac{1}{2\epsilon_{t}}$

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}$

In Algorithm 5 we rewrite OnlineBoost in such a way that the weight assigned
to each example $i\in\\{1,\dots,N\\}$ for the purposes of updating the
parameters of each base learner $t\in\\{1,\dots,T\\}$ is stored in a separate
variable $\lambda_{t}(i)$, rather than overwritten on each update on the
variable $\lambda$. Storing so many variables is –of course– prohibitive in
the online setting, but here we do this merely for illustrative purposes.

The equivalence of Algorithm 5 to Algorithm 4 is trivial, thus we will not
give an explicit proof. It is based on the fact that $\lambda$ in Algorithm 4
will equal to $\lambda_{t-1}(i)$ of Algorithm 5 before updating the weights of
the $t$-th weak learner according to the $i$-th datapoint and to
$\lambda_{t}(i)$ after. Once all $T$ weak learners are trained on the $i$-th
datapoint, $\lambda$ will become equal to $\lambda_{t}(i)$ and so on.

Algorithm 5 OnlineBoost (storing all weights)

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$ available one at a time

For each $i$ do:

Set example weight $\lambda_{0}(i)=1$

For each $t\in\\{1,2,\dots,T\\}$ do:

Set $k$ according to $Poisson(\lambda_{t-1}(i))$

Do $k$ times:

$h_{t}\leftarrow OnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}))$

If $h_{t}(\mathbf{x}_{i})=y_{i}$:

$\lambda^{sc}_{t}\leftarrow\lambda^{sc}_{t}+\lambda_{t-1}(i)$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda_{t}(i)\leftarrow\lambda_{t-1}(i)\times\frac{1}{2(1-\epsilon_{t})}$

Else:

$\lambda^{sw}_{t}\leftarrow\lambda^{sw}_{t}+\lambda_{t-1}(i)$

$\epsilon_{t}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}$

$\lambda_{t}(i)\leftarrow\lambda_{t-1}(i)\times\frac{1}{2\epsilon_{t}}$

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}$

Using the notation introduced in Algorithm 5, we can denote the sums of
weights corresponding to correctly and incorrectly classified examples by the
$t$-th weak learner so far, respectively, as

$\lambda^{sc}_{t}=\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})=y_{j}\\\
j\leq
i\end{subarray}}{\lambda_{t-1}(j)}\quad\text{and}\quad\lambda^{sw}_{t}=\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq i\end{subarray}}{\lambda_{t-1}(j)}$ (11)

Algorithm 6 OnlineBoost (Reformulated –resampling version)

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$ available one at a time

For each $i$ do:

Set example weight $\lambda_{0}(i)=1$

For each $t\in{1,2,\dots,T}$ do:

Set $k$ according to $Poisson(\lambda_{t-1}(i))$

Do $k$ times:

$h_{t}\leftarrow OnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}))$

$\epsilon_{t}=\frac{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}}{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}+\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})=y_{j}\\\
j\leq i\end{subarray}}{\lambda_{t-1}(j)}}$

$\beta_{t}=\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}$

$\lambda_{t}(i)=\frac{1}{Z_{t}}\lambda_{t-1}(i)e^{-y_{i}\beta_{t}h_{t}(\mathbf{x}_{i})}$,
where $Z_{t}=\frac{2(1-\epsilon_{t})}{e^{\beta_{t}}}$ (constant w.r.t. $i$)

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{\beta_{t}h_{t}(\mathbf{x})}\Big{]}$

We now claim that Algorithm 6 is another reformulation of OnlineBoost, thus
equivalent to Algorithm 5. This is less straightforward to see, so we shall
prove that the steps of the two algorithms are equivalent. Notice that the
changes w.r.t. Algorithm 5 occur in the weight update rule, the calculation of
the confidence coefficients, and the final decision rule. Let us inspect these
to verify that the two algorithms are equivalent.

##### Confidence coefficients:

Algorithm 5, does not explicitly store the confidence coefficients (i.e. the
voting weights $\beta_{t}$) of the weak learners. It does not need to, as
$\beta_{t}$ is calculated based on $\epsilon_{t}$, which in turn only requires
$\lambda^{sc}_{t}$ and $\lambda^{sw}_{t}$. However, as we will see, in
Algorithm 6, we can define the quantity,

$\beta_{t}=\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}},$ (12)

where –as we will see– $\epsilon_{t}$ is the same in both algorithms, and use
it to produce equivalent weight update and prediction rules.

##### Weight updates:

In Algorithm 6, the weight of the $i$-th example for the purposes of updating
the parameters of the next weak learner is given by the equation

$\lambda_{t}(i)=\frac{1}{Z_{t}}\lambda_{t-1}(i)e^{-y_{i}\beta_{t}h_{t}(\mathbf{x}_{i})},\quad\text{where}\quad
Z_{t}=\frac{2(1-\epsilon_{t})}{e^{\beta_{t}}}$ (13)

is used for normalization. This weight update rule can be rewritten as

$\begin{split}\lambda_{t}(i)&\stackrel{{\scriptstyle\text{Eq.(\ref{eq:lambda_t_i_A})}}}{{=}}\frac{e^{\beta_{t}}}{2(1-\epsilon_{t})}\lambda_{t-1}(i)e^{-y_{i}\beta_{t}h_{t}(\mathbf{x}_{i})}\stackrel{{\scriptstyle\text{Eq.(\ref{eq:beta_A})}}}{{=}}\\\
&=\frac{e^{\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}}{2(1-\epsilon_{t})}\lambda_{t-1}(i)e^{-y_{i}\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}h_{t}(\mathbf{x}_{i})}=\\\
&=\frac{e^{\log{\big{(}\frac{1-\epsilon_{t}}{\epsilon_{t}}\big{)}^{\frac{1}{2}}}}}{2(1-\epsilon_{t})}\lambda_{t-1}(i)e^{\log{\big{(}\frac{1-\epsilon_{t}}{\epsilon_{t}}\big{)}}^{-\frac{1}{2}y_{i}h_{t}(\mathbf{x}_{i})}}=\\\
&=\lambda_{t-1}(i)\frac{\big{(}\frac{1-\epsilon_{t}}{\epsilon_{t}}\big{)}^{\frac{1}{2}}\big{(}\big{(}\frac{1-\epsilon_{t}}{\epsilon_{t}}\big{)}^{\frac{1}{2}}\big{)}^{-y_{i}h_{t}(\mathbf{x}_{i})}}{2(1-\epsilon_{t})}=\\\
&=\begin{cases}\lambda_{t-1}(i)\frac{1}{2(1-\epsilon_{t})},&h_{t}(\mathbf{x}_{i})=y_{i}\\\
\lambda_{t-1}(i)\frac{1}{2\epsilon_{t}}~{}~{}~{}~{}~{},&h_{t}(\mathbf{x}_{i})\neq
y_{i}.\end{cases}\end{split}$

And from Eq. (11), we have that

$\epsilon_{t}=\frac{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}}{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}+\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})=y_{j}\\\
j\leq
i\end{subarray}}{\lambda_{t-1}(j)}}=\frac{\lambda^{sw}_{t}}{\lambda^{sw}_{t}+\lambda^{sc}_{t}}.$
(14)

Therefore, the weight update rules of the two algorithms are identical.

##### Prediction Rule:

In the new formulation of Algorithm 6, the predictions are given by

$\begin{split}H(x)&=sign\Big{[}\sum_{t=1}^{T}{\beta_{t}h_{t}(\mathbf{x})}\Big{]}\stackrel{{\scriptstyle\text{Eq.(\ref{eq:beta_A})}}}{{=}}sign\Big{[}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}=\\\
&=sign\Big{[}\frac{1}{2}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}=sign\Big{[}\sum_{t=1}^{T}{h_{t}(\mathbf{x})\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}}\Big{]}.\end{split}$

So, from Eq. (14), we have that Algorithm 5 and Algorithm 6 use the same
prediction rule. Therefore all the steps of Algorithm 5 and Algorithm 6 are
equivalent, and since Algorithm 5 is a reformulation of OnlineBoost, so is
Algorithm 6.

Algorithm 7 is a final reformulation of OnlineBoost.
$WeightedOnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}),\lambda_{t-1}(i))$ is a
weighted online learning algorithm updates the parameters of the weak learner
$h_{t}$ on example $(\mathbf{x}_{i},y_{i})$ using a weight of
$\lambda_{t-1}(i)$. The rationale is that instead of training the new
classifier $k$ times on the $i$-th example, we can train it once with a weight
$k$ (i.e. taking the reweighting rather than the resampling approach to
boosting). Moreover, as each time $k\sim Poisson(\lambda_{t-1}(i))$, for the
purposes of updating the parameters of the $t$-th weak learner on the $i$-th
example, we have that $\lambda_{t-1}(i)=\mathbb{E}[k]$. So by training the
$t$-th weak learner on the $i$-th example with a weight of $\lambda_{t-1}(i)$
we get –in expectation– the same updates. This is the only change w.r.t.
Algorithm 6131313This step of the proof is somewhat redundant as simply
establishing the equivalence of OnlineBoost to AdaBoost-by-reweighting would
have been sufficient for the purposes of this paper..

Algorithm 7 OnlineBoost (Reformulated –reweighting version using expected
weights $\lambda_{t-1}(i)$)

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$ available one at a time

For each $i$ do:

Set example weight $\lambda_{0}(i)=1$

For each $t\in{1,2,\dots,T}$ do:

$h_{t}\leftarrow
WeightedOnlineLearnAlg(h_{t},(\mathbf{x}_{i},y_{i}),\lambda_{t-1}(i))$

$\epsilon_{t}=\frac{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}}{\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})\neq
y_{j}\\\ j\leq
i\end{subarray}}{\lambda_{t-1}(j)}+\sum_{\begin{subarray}{c}j:h_{t}(\mathbf{x}_{j})=y_{j}\\\
j\leq i\end{subarray}}{\lambda_{t-1}(j)}}$

$\beta_{t}=\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}$

$\lambda_{t}(i)=\frac{1}{Z_{t}}\lambda_{t-1}(i)e^{-y_{i}\beta_{t}h_{t}(\mathbf{x}_{i})}$,
where $Z_{t}=\frac{2(1-\epsilon_{t})}{e^{\beta_{t}}}$ (constant w.r.t. $i$)

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{\beta_{t}h_{t}(\mathbf{x})}\Big{]}$

Finally, in Algorithm 8 we present (the reweighting version of) batch AdaBoost
with a fixed ensemble size $T$. It uses a batch learning algorithm to train
the weak learner $h_{t}$ on the full dataset using weights $\lambda_{t-1}(i)$,
$\forall i$, denoted as
$WeightedBatchLearnAlg(\\{(\mathbf{x}_{i},y_{i})|,\forall
i\\},\\{\lambda_{t-1}(i)|,\forall i\\})$.

Algorithm 8 AdaBoost (Fixed ensemble size $T$)

Input: Number of weak learners $T$, training examples
$\\{(\mathbf{x}_{i},y_{i})|i=1,\dots,N\\}$

Set example weight $\lambda_{0}(i)=1$, $\forall i$

For each $t\in\\{1,2,\dots,T\\}$ do:

$h_{t}\leftarrow WeightedBatchLearnAlg(\\{(\mathbf{x}_{i},y_{i})|,\forall
i\\},\\{\lambda_{t-1}(i)|,\forall i\\})$

$\epsilon_{t}=\frac{\sum_{i:h_{t}(\mathbf{x}_{i})\neq
y_{i}}{\lambda_{t-1}(i)}}{\sum_{i:h_{t}(\mathbf{x}_{i})\neq
y_{i}}{\lambda_{t-1}(i)}+\sum_{i:h_{t}(\mathbf{x}_{i})=y_{i}}{\lambda_{t-1}(i)}}$

$\beta_{t}=\frac{1}{2}\log{\frac{1-\epsilon_{t}}{\epsilon_{t}}}$

$\lambda_{t}(i)=\frac{1}{Z_{t}}\lambda_{t-1}(i)e^{-y_{i}\beta_{t}h_{t}(\mathbf{x}_{i})}$,
$\forall i$, where $Z_{t}$ is constant w.r.t. $i$

Prediction: On example $(\mathbf{x},y)$, predict
$H(\mathbf{x})=sign\Big{[}\sum_{t=1}^{T}{\beta_{t}h_{t}(\mathbf{x})}\Big{]}$

Comparing Algorithm 8 to Algorithm 7 (equivalent to OnlineBoost), we see that
the only difference is that all parameters estimated in the latter are updated
only on the examples seen so far, rather than on the entire dataset (something
natural for the online setting).

Since the steps of AdaBoost can be derived as (batch) gradient descent on an
exponential loss of the margin $L(y,F(\mathbf{x}))=e^{-yF(\mathbf{x})}$ in the
space of functions $F(\mathbf{x})$ [54, 4], and since OnlineBoost uses the
same steps, but updates all parameters based on one example at a time, we can
conclude that OnlineBoost minimizes the same loss function as AdaBoost (i.e.
the exponential loss), but taking stochastic gradient descent steps in the
space of functions $F(\mathbf{x})$.

## Appendix B: Datasets used

Table 6: Characteristics of the datasets used in our experiments; number of instances used, number of features, number of classes and presence or not of dataset shift. All stationary datasets can be found in the UCI repository. The non-stationary datasets were taken from [55]. Dataset | # | # | # | Considered
---|---|---|---|---
Instances | Features | Classes | Stationary
_landsat_ | $1,252$ | $36$ | $6$ | Yes
_splice_ | $1,524$ | $60$ | $3$ | Yes
_musk2_ | $2,034$ | $166$ | $2$ | Yes
_krvskp_ | $3,054$ | $36$ | $2$ | Yes
_waveform_ | $3,306$ | $40$ | $3$ | Yes
_spambase_ | $3,626$ | $57$ | $2$ | Yes
_mushroom_ | $7,832$ | $21$ | $2$ | Yes
_weather_ | $18,159$ | $8$ | $2$ | No
_electricity_ | $45,312$ | $8$ | $2$ | No
_forest_ | $581,012$ | $54$ | $7$ | No

## Appendix C: Additional results

Here we provide tables of log-loss across all examples, for each method, for
all the experiments mentioned in the paper, along with learning curves of log-
loss versus number of minibatches seen.

### Effect of weak learner choice

We provide results on the stationary datasets for ensembles of size $T=10$ for
four different types of weak learners: Gaussian Naive Bayes, logistic
regression, linear SVM and perceptron.

Table 7: Log-loss across the entire dataset. Lowest average value shown in bold. Results for Naive Bayes, $T=10$ on stationary datasets. Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.138$ | $0.081$ | $0.131$ | $0.072$ | $\mathbf{0.071}$ | $0.074$ | $0.129$ | $0.123$ | $0.073$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.002$ | $0.002$ | $0.004$ | $0.001$ | $\mathbf{0.001}$ | $0.002$ | $0.010$ | $0.011$ | $0.002$
_splice_ | $0.444$ | $0.280$ | $0.410$ | $0.234$ | $\mathbf{0.229}$ | $0.282$ | $0.353$ | $0.376$ | $0.232$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.034$ | $0.014$ | $0.014$ | $0.007$ | $\mathbf{0.009}$ | $0.022$ | $0.024$ | $0.037$ | $0.008$
_musk2_ | $0.723$ | $0.343$ | $0.427$ | $\mathbf{0.320}$ | $0.332$ | $0.397$ | $0.711$ | $0.441$ | $0.345$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.027$ | $0.008$ | $0.013$ | $\mathbf{0.006}$ | $0.003$ | $0.008$ | $0.025$ | $0.049$ | $0.008$
_krvskp_ | $1.252$ | $0.488$ | $0.720$ | $0.474$ | $0.472$ | $0.486$ | $0.627$ | $0.767$ | $\mathbf{0.468}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.154$ | $0.014$ | $0.075$ | $0.019$ | $0.012$ | $0.016$ | $0.114$ | $0.114$ | $\mathbf{0.020}$
_waveform_ | $0.824$ | $0.361$ | $0.466$ | $0.335$ | $\mathbf{0.334}$ | $0.342$ | $0.458$ | $0.492$ | $0.344$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.005$ | $0.009$ | $0.002$ | $\mathbf{0.004}$ | $0.007$ | $0.015$ | $0.024$ | $0.006$
_spambase_ | $2.37$ | $0.532$ | $0.735$ | $0.493$ | $0.483$ | $\mathbf{0.481}$ | $0.536$ | $0.540$ | $0.489$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.026$ | $0.006$ | $0.017$ | $0.006$ | $0.005$ | $\mathbf{0.008}$ | $0.028$ | $0.037$ | $0.005$
_mushroom_ | $0.770$ | $0.358$ | $0.503$ | $0.375$ | $0.335$ | $\mathbf{0.318}$ | $0.570$ | $0.570$ | $0.327$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$
$0.057$ | $0.011$ | $0.017$ | $0.018$ | $0.020$ | $\mathbf{0.006}$ | $0.036$ | $0.072$ | $0.010$
Table 8: Log-loss across the entire dataset. Lowest average value shown in bold. Results for logistic regression, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.330$ | $\mathbf{0.106}$ | $0.158$ | $0.107$ | $0.108$ | $0.108$ | $0.173$ | $0.203$ | $0.127$
$\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.011$ | $\mathbf{0.002}$ | $0.004$ | $0.003$ | $0.004$ | $0.004$ | $0.019$ | $0.018$ | $0.013$
_splice_ | $1.779$ | $0.626$ | $0.895$ | $\mathbf{0.506}$ | $0.554$ | $0.636$ | $0.711$ | $1.155$ | $0.584$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.059$ | $0.023$ | $0.034$ | $\mathbf{0.029}$ | $0.020$ | $0.068$ | $0.117$ | $0.169$ | $0.034$
_musk2_ | $1.276$ | $0.331$ | $0.398$ | $0.321$ | $0.330$ | $\mathbf{0.318}$ | $0.536$ | $0.514$ | $0.322$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.015$ | $0.003$ | $0.008$ | $0.004$ | $0.004$ | $\mathbf{0.003}$ | $0.049$ | $0.038$ | $0.006$
_krvskp_ | $1.151$ | $0.633$ | $0.881$ | $\mathbf{0.519}$ | $0.528$ | $0.645$ | $0.825$ | $0.733$ | $0.555$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.073$ | $0.041$ | $0.042$ | $\mathbf{0.037}$ | $0.017$ | $0.048$ | $0.074$ | $0.041$ | $0.033$
_waveform_ | $1.700$ | $0.444$ | $0.596$ | $\mathbf{0.427}$ | $0.429$ | $0.428$ | $0.503$ | $0.519$ | $0.464$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.037$ | $0.004$ | $0.019$ | $\mathbf{0.003}$ | $0.007$ | $0.006$ | $0.026$ | $0.030$ | $0.016$
_spambase_ | $1.182$ | $0.409$ | $0.572$ | $0.390$ | $0.395$ | $0.407$ | $0.540$ | $0.477$ | $\mathbf{0.389}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.018$ | $0.006$ | $0.010$ | $0.005$ | $0.006$ | $0.007$ | $0.029$ | $0.024$ | $\mathbf{0.006}$
_mushroom_ | $1.001$ | $0.343$ | $0.454$ | $0.322$ | $0.315$ | $\mathbf{0.312}$ | $0.531$ | $0.592$ | $0.330$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.023$ | $0.007$ | $0.017$ | $0.007$ | $0.006$ | $\mathbf{0.007}$ | $0.026$ | $0.026$ | $0.006$
Table 9: Log-loss across the entire dataset. Lowest average value shown in bold. Results for linear SVM, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.245$ | $0.130$ | $0.184$ | $0.118$ | $0.121$ | $0.127$ | $0.250$ | $0.243$ | $\mathbf{0.111}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.019$ | $0.009$ | $0.010$ | $0.008$ | $0.008$ | $0.010$ | $0.025$ | $0.034$ | $\mathbf{0.004}$
_splice_ | $1.391$ | $0.663$ | $0.922$ | $0.622$ | $\mathbf{0.586}$ | $0.609$ | $0.816$ | $0.666$ | $0.640$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.064$ | $0.018$ | $0.040$ | $0.031$ | $\mathbf{0.022}$ | $0.020$ | $0.105$ | $0.088$ | $0.038$
_musk2_ | $0.953$ | $\mathbf{0.385}$ | $0.432$ | $0.400$ | $0.390$ | $0.406$ | $0.639$ | $0.622$ | $0.386$
$\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$\mathbf{0.020}$ | $0.008$ | $0.007$ | $0.006$ | $0.007$ | $0.008$ | $0.061$ | $0.066$ | $\mathbf{0.005}$
_krvskp_ | $1.081$ | $0.671$ | $0.897$ | $\mathbf{0.608}$ | $0.648$ | $0.677$ | $0.706$ | $0.811$ | $0.667$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.050$ | $0.022$ | $0.027$ | $\mathbf{0.021}$ | $0.027$ | $0.029$ | $0.047$ | $0.041$ | $0.030$
_waveform_ | $1.156$ | $0.487$ | $0.615$ | $0.453$ | $\mathbf{0.451}$ | $\mathbf{0.451}$ | $0.611$ | $0.603$ | $0.464$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.045$ | $0.013$ | $0.015$ | $0.005$ | $\mathbf{0.004}$ | $\mathbf{0.005}$ | $0.021$ | $0.076$ | $0.005$
_spambase_ | $0.893$ | $0.440$ | $0.551$ | $0.411$ | $\mathbf{0.410}$ | $0.418$ | $0.560$ | $0.612$ | $0.414$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.019$ | $0.008$ | $0.010$ | $0.005$ | $\mathbf{0.007}$ | $0.009$ | $0.028$ | $0.053$ | $0.0037$
_mushroom_ | $0.673$ | $0.374$ | $0.489$ | $0.359$ | $0.363$ | $\mathbf{0.352}$ | $0.506$ | $0.573$ | $0.357$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.015$ | $0.006$ | $0.015$ | $0.006$ | $0.006$ | $\mathbf{0.005}$ | $0.036$ | $0.039$ | $0.007$
Table 10: Log-loss across the entire dataset. Lowest average value shown in bold. Results for perceptron, $T=10$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.258$ | $0.120$ | $0.190$ | $0.125$ | $\mathbf{0.103}$ | $0.115$ | $0.164$ | $0.198$ | $0.120$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.005$ | $0.009$ | $0.013$ | $\mathbf{0.004}$ | $0.005$ | $0.014$ | $0.028$ | $0.008$
_splice_ | $1.453$ | $0.683$ | $0.879$ | $\mathbf{0.566}$ | $0.624$ | $0.642$ | $0.759$ | $0.651$ | $0.607$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.037$ | $0.033$ | $0.050$ | $\mathbf{0.021}$ | $0.028$ | $0.025$ | $0.105$ | $0.022$ | $0.027$
_musk2_ | $0.945$ | $0.392$ | $0.443$ | $0.390$ | $\mathbf{0.385}$ | $0.419$ | $0.591$ | $0.648$ | $0.408$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.030$ | $0.006$ | $0.012$ | $0.006$ | $\mathbf{0.006}$ | $0.014$ | $0.044$ | $0.067$ | $0.013$
_krvskp_ | $1.021$ | $0.745$ | $0.909$ | $0.632$ | $\mathbf{0.609}$ | $0.777$ | $0.812$ | $0.811$ | $0.611$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.042$ | $0.031$ | $0.043$ | $0.037$ | $\mathbf{0.022}$ | $0.079$ | $0.069$ | $0.062$ | $0.017$
_waveform_ | $1.106$ | $0.498$ | $0.589$ | $0.468$ | $0.492$ | $0.486$ | $0.573$ | $0.686$ | $\mathbf{0.456}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.027$ | $0.010$ | $0.021$ | $0.010$ | $0.034$ | $0.026$ | $0.029$ | $0.066$ | $\mathbf{0.008}$
_spambase_ | $0.885$ | $0.430$ | $0.575$ | $\mathbf{0.400}$ | $0.415$ | $0.415$ | $0.521$ | $0.620$ | $0.418$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.006$ | $0.010$ | $\mathbf{0.004}$ | $0.004$ | $0.007$ | $0.027$ | $0.043$ | $0.008$
_mushroom_ | $0.670$ | $0.383$ | $0.489$ | $0.359$ | $\mathbf{0.350}$ | $0.367$ | $0.502$ | $0.599$ | $0.355$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.006$ | $0.011$ | $0.003$ | $\mathbf{0.006}$ | $0.004$ | $0.032$ | $0.033$ | $0.006$

###  7.1 Effect of ensemble size

Next we examined the effect of different ensemble sizes, using
$T\in\\{10,25,50\\}$. For this experiment we picked logistic regression as the
weak learner. We present results on the stationary datasets.

Table 11: Log-loss across the entire dataset. Lowest average value shown in bold. Results for logistic regression, $T=25$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.323$ | $0.120$ | $0.182$ | $0.118$ | $\mathbf{0.113}$ | $0.124$ | $0.202$ | $0.251$ | $0.120$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.009$ | $0.003$ | $0.001$ | $0.004$ | $\mathbf{0.004}$ | $0.004$ | $0.030$ | $0.029$ | $0.004$
_splice_ | $1.553$ | $0.684$ | $0.975$ | $0.607$ | $0.607$ | $0.723$ | $0.667$ | $0.747$ | $\mathbf{0.594}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.064$ | $0.021$ | $0.042$ | $0.016$ | $0.018$ | $0.073$ | $0.058$ | $0.121$ | $\mathbf{0.021}$
_musk2_ | $1.515$ | $0.343$ | $0.401$ | $0.343$ | $\mathbf{0.342}$ | $0.344$ | $0.565$ | $0.461$ | $\mathbf{0.342}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.020$ | $0.003$ | $0.007$ | $0.003$ | $\mathbf{0.002}$ | $0.005$ | $0.037$ | $0.037$ | $\mathbf{0.002}$
_krvskp_ | $1.155$ | $0.698$ | $0.895$ | $0.605$ | $\mathbf{0.583}$ | $0.667$ | $0.774$ | $0.765$ | $0.603$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.060$ | $0.020$ | $0.040$ | $0.039$ | $\mathbf{0.023}$ | $0.030$ | $0.037$ | $0.042$ | $0.030$
_waveform_ | $1.427$ | $0.470$ | $0.572$ | $\mathbf{0.441}$ | $0.457$ | $0.453$ | $0.517$ | $0.551$ | $0.453$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.047$ | $0.009$ | $0.011$ | $\mathbf{0.006}$ | $0.019$ | $0.011$ | $0.042$ | $0.048$ | $0.009$
_spambase_ | $1.226$ | $0.430$ | $0.590$ | $0.410$ | $\mathbf{0.407}$ | $0.412$ | $0.519$ | $0.524$ | $\mathbf{0.407}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.019$ | $0.007$ | $0.010$ | $0.006$ | $\mathbf{0.003}$ | $0.005$ | $0.035$ | $0.033$ | $\mathbf{0.007}$
_mushroom_ | $1.043$ | $0.362$ | $0.457$ | $\mathbf{0.324}$ | $0.333$ | $0.353$ | $0.431$ | $0.547$ | $0.347$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.013$ | $0.005$ | $0.012$ | $\mathbf{0.004}$ | $0.004$ | $0.010$ | $0.031$ | $0.043$ | $0.007$
Table 12: Log-loss across the entire dataset. Lowest average value shown in bold. Results for logistic regression, $T=50$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.296$ | $0.132$ | $0.176$ | $0.133$ | $\mathbf{0.122}$ | $0.129$ | $0.151$ | $0.180$ | $0.125$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.005$ | $0.006$ | $0.005$ | $\mathbf{0.005}$ | $0.007$ | $0.017$ | $0.014$ | $0.004$
_splice_ | $1.637$ | $0.647$ | $0.907$ | $\mathbf{0.548}$ | $0.577$ | $0.607$ | $0.698$ | $0.652$ | $0.587$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.069$ | $0.023$ | $0.050$ | $\mathbf{0.010}$ | $0.026$ | $0.034$ | $0.066$ | $0.030$ | $0.038$
_musk2_ | $1.520$ | $0.350$ | $0.403$ | $0.350$ | $\mathbf{0.346}$ | $0.353$ | $0.452$ | $0.550$ | $0.348$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.013$ | $0.004$ | $0.008$ | $0.003$ | $\mathbf{0.004}$ | $0.003$ | $0.036$ | $0.045$ | $0.003$
_krvskp_ | $1.224$ | $0.675$ | $0.844$ | $\mathbf{0.582}$ | $0.658$ | $0.616$ | $0.701$ | $0.715$ | $0.597$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.045$ | $0.024$ | $0.032$ | $\mathbf{0.010}$ | $0.033$ | $0.029$ | $0.024$ | $0.020$ | $0.009$
_waveform_ | $1.439$ | $0.470$ | $0.591$ | $0.482$ | $0.444$ | $0.482$ | $0.556$ | $0.563$ | $\mathbf{0.441}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.033$ | $0.005$ | $0.015$ | $0.031$ | $0.005$ | $0.028$ | $0.030$ | $0.027$ | $\mathbf{0.005}$
_spambase_ | $1.241$ | $0.429$ | $0.584$ | $\mathbf{0.397}$ | $0.399$ | $0.410$ | $0.527$ | $0.527$ | $0.414$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.018$ | $0.005$ | $0.011$ | $\mathbf{0.006}$ | $0.006$ | $0.007$ | $0.028$ | $0.032$ | $0.005$
_mushroom_ | $1.082$ | $0.363$ | $0.481$ | $0.345$ | $0.344$ | $\mathbf{0.340}$ | $0.464$ | $0.529$ | $0.345$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.017$ | $0.004$ | $0.010$ | $0.005$ | $0.006$ | $\mathbf{0.009}$ | $0.040$ | $0.044$ | $0.008$

###  7.2 Effect of weak learner regularization

We now investigate different degrees of regularization on the weak learner. We
used $\ell_{1}$-regularized logistic regression with a regularization
parameter $\lambda\in\\{10^{-1},10^{-2},10^{-3},0\\}$, with $T=10$. We present
experiments on the stationary datasets.

Table 13: Log-loss across the entire dataset. Lowest average value shown in bold. Results for $\ell_{1}$-regularized logistic regression, $T=10$ and $\lambda=10^{-3}$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.335$ | $0.105$ | $0.153$ | $\mathbf{0.101}$ | $0.103$ | $0.105$ | $0.150$ | $0.172$ | $0.118$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.006$ | $0.003$ | $0.004$ | $\mathbf{0.003}$ | $0.002$ | $0.003$ | $0.015$ | $0.027$ | $0.005$
_splice_ | $1.761$ | $0.604$ | $0.885$ | $0.520$ | $0.576$ | $\mathbf{0.502}$ | $0.720$ | $0.707$ | $0.517$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.093$ | $0.024$ | $0.040$ | $0.022$ | $0.070$ | $\mathbf{0.013}$ | $0.135$ | $0.076$ | $0.019$
_musk2_ | $1.334$ | $0.335$ | $0.424$ | $0.320$ | $\mathbf{0.319}$ | $0.317$ | $0.480$ | $0.683$ | $0.324$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.022$ | $0.006$ | $0.008$ | $0.004$ | $\mathbf{0.004}$ | $0.004$ | $0.048$ | $0.122$ | $0.003$
_krvskp_ | $1.126$ | $0.592$ | $0.805$ | $\mathbf{0.479}$ | $0.605$ | $0.546$ | $0.781$ | $0.823$ | $0.581$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.036$ | $0.007$ | $0.029$ | $\mathbf{0.016}$ | $0.051$ | $0.039$ | $0.075$ | $0.077$ | $0.055$
_waveform_ | $1.879$ | $0.457$ | $0.609$ | $0.440$ | $0.440$ | $\mathbf{0.437}$ | $0.523$ | $0.642$ | $0.459$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.044$ | $0.007$ | $0.012$ | $0.007$ | $0.006$ | $\mathbf{0.007}$ | $0.032$ | $0.135$ | $0.011$
_spambase_ | $0.994$ | $0.406$ | $0.567$ | $\mathbf{0.373}$ | $0.375$ | $0.383$ | $0.506$ | $0.556$ | $0.386$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.024$ | $0.006$ | $0.005$ | $\mathbf{0.006}$ | $0.006$ | $0.005$ | $0.024$ | $0.034$ | $0.009$
_mushroom_ | $0.891$ | $0.317$ | $0.461$ | $\mathbf{0.305}$ | $0.312$ | $0.314$ | $0.462$ | $0.590$ | $0.319$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.009$ | $0.005$ | $0.014$ | $\mathbf{0.005}$ | $0.006$ | $0.008$ | $0.045$ | $0.033$ | $0.006$
Table 14: Log-loss across the entire dataset. Lowest average value shown in bold. Results for $\ell_{1}$-regularized logistic regression, $T=10$ and $\lambda=10^{-2}$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.345$ | $0.110$ | $0.157$ | $0.103$ | $0.106$ | $0.107$ | $0.144$ | $0.147$ | $\mathbf{0.102}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.009$ | $0.003$ | $0.004$ | $0.003$ | $0.005$ | $0.002$ | $0.012$ | $0.017$ | $\mathbf{0.003}$
_splice_ | $1.483$ | $0.572$ | $0.806$ | $0.529$ | $\mathbf{0.489}$ | $0.528$ | $0.556$ | $0.704$ | $0.517$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.054$ | $0.025$ | $0.033$ | $0.015$ | $\mathbf{0.011}$ | $0.041$ | $0.022$ | $0.076$ | $0.013$
_musk2_ | $1.501$ | $0.352$ | $0.455$ | $0.348$ | $0.349$ | $\mathbf{0.347}$ | $0.481$ | $0.693$ | $0.360$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.016$ | $0.004$ | $0.003$ | $0.004$ | $0.004$ | $\mathbf{0.002}$ | $0.038$ | $0.145$ | $0.006$
_krvskp_ | $1.357$ | $0.756$ | $1.007$ | $0.658$ | $0.628$ | $0.654$ | $0.782$ | $0.776$ | $\mathbf{0.583}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.071$ | $0.05$ | $0.05$ | $0.039$ | $0.027$ | $0.029$ | $0.064$ | $0.07$ | $\mathbf{0.023}$
_waveform_ | $1.491$ | $0.456$ | $0.629$ | $\mathbf{0.434}$ | $\mathbf{0.434}$ | $0.444$ | $0.494$ | $0.515$ | $0.441$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.031$ | $0.006$ | $0.020$ | $\mathbf{0.006}$ | $\mathbf{0.006}$ | $0.006$ | $0.024$ | $0.035$ | $0.007$
_spambase_ | $0.887$ | $0.405$ | $0.553$ | $0.383$ | $0.380$ | $0.400$ | $0.475$ | $0.556$ | $\mathbf{0.379}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.026$ | $0.007$ | $0.007$ | $0.004$ | $0.006$ | $0.009$ | $0.024$ | $0.063$ | $\mathbf{0.004}$
_mushroom_ | $0.743$ | $0.330$ | $0.465$ | $\mathbf{0.310}$ | $\mathbf{0.310}$ | $0.318$ | $0.790$ | $0.495$ | $0.320$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.012$ | $0.003$ | $0.011$ | $\mathbf{0.005}$ | $\mathbf{0.004}$ | $0.007$ | $0.031$ | $0.037$ | $0.012$
Table 15: Log-loss across the entire dataset. Lowest average value shown in bold. Results for $\ell_{1}$-regularized logistic regression, $T=10$ and $\lambda=10^{-1}$ on stationary datasets.  Dataset |  | Best | Worst |  | UCB1 |  | Disc. | Disc. | Disc.
---|---|---|---|---|---|---|---|---|---
Uncalibrated | Fixed | Fixed | UCB1 | Improved | GTS | UCB1 | UCB1 | GTS
|  |  |  |  |  |  | Improved |
_landsat_ | $0.308$ | $0.113$ | $0.153$ | $0.100$ | $0.100$ | $\mathbf{0.099}$ | $0.141$ | $0.142$ | $0.106$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.010$ | $0.002$ | $0.006$ | $0.003$ | $0.002$ | $\mathbf{0.002}$ | $0.013$ | $0.017$ | $0.004$
_splice_ | $3.703$ | $0.930$ | $1.607$ | $0.778$ | $\mathbf{0.770}$ | $0.927$ | $1.187$ | $0.988$ | $0.883$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.119$ | $0.037$ | $0.080$ | $0.022$ | $\mathbf{0.023}$ | $0.091$ | $0.288$ | $0.267$ | $0.098$
_musk2_ | $2.244$ | $0.510$ | $0.794$ | $\mathbf{0.462}$ | $0.466$ | $0.503$ | $0.664$ | $0.492$ | $0.466$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.038$ | $0.006$ | $0.012$ | $\mathbf{0.008}$ | $0.007$ | $0.035$ | $0.161$ | $0.009$ | $0.013$
_krvskp_ | $2.857$ | $1.109$ | $1.483$ | $0.775$ | $0.797$ | $\mathbf{0.749}$ | $0.924$ | $0.923$ | $0.786$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$
$0.263$ | $0.044$ | $0.084$ | $0.053$ | $0.037$ | $\mathbf{0.030}$ | $0.143$ | $0.149$ | $0.030$
_waveform_ | $1.198$ | $0.557$ | $0.698$ | $0.500$ | $0.552$ | $0.488$ | $0.569$ | $0.639$ | $\mathbf{0.486}$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$
$0.050$ | $0.014$ | $0.025$ | $0.011$ | $0.030$ | $0.005$ | $0.023$ | $0.030$ | $\mathbf{0.007}$
_spambase_ | $0.639$ | $0.563$ | $0.671$ | $\mathbf{0.491}$ | $0.516$ | $0.511$ | $0.597$ | $0.593$ | $0.515$
$\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.014$ | $0.007$ | $0.015$ | $\mathbf{0.008}$ | $0.008$ | $0.011$ | $0.020$ | $0.015$ | $0.008$
_mushroom_ | $0.521$ | $0.428$ | $0.564$ | $0.394$ | $\mathbf{0.378}$ | $0.404$ | $0.553$ | $0.628$ | $0.400$
$\pm$ | $\pm$ | $\pm$ | $\pm$ | $\mathbf{\pm}$ | $\pm$ | $\pm$ | $\pm$ | $\pm$
$0.009$ | $0.005$ | $0.007$ | $0.007$ | $\mathbf{0.005}$ | $0.007$ | $0.018$ | $0.021$ | $0.009$