Robust Bounds for Classification via Selective Sampling

Nicolò Cesa-Bianchi
DSI, Università degli Studi di Milano, Via Comelico 39, 20135 - Milano, Italy
Claudio Gentile
DICOM, Università dell’Insubria, Via Mazzini 5, 21100 - Varese, Italy
Francesco Orabona
Idiap, Rue Marconi 19, Case Postale 592, CH-1920 Martigny, Switzerland

Abstract
We introduce a new algorithm for binaryclassification in the selective sampling protocol. Our algorithm uses Regularized Least
Squares (RLS) as base classifier, and forthis reason it can be efficiently run in any
RKHS. Unlike previous margin-based semisupervised algorithms, our sampling condition hinges on a simultaneous upper boundon bias and variance of the RLS estimate under a simple linear label noise model. This
fact allows us to prove performance bounds
that hold for an arbitrary sequence of instances. In particular, we show that oursampling strategy approximates the marginof the Bayes optimal classifier to any desired
e d/ε2 queries (in theaccuracy ε by asking O
RKHS case d is replaced by a suitable spectral quantity). While these are the standard
rates in the fully supervised i.i.d. case, thebest previously known result in our hardere d3 /ε4 . Preliminary experisetting was O
ments show that some of our algorithms also
exhibit a good practical performance.

1. Introduction
A practical variant of the standard (fully supervised)online learning protocol is a setting where, at eachprediction step, the learner can abstain from observing the current label. If the learner observes the label,
which he can do by issuing a query, then the label
value can be used to improve future predictions. If
Appearing in Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009. Copyright 2009 by the author(s)/owner(s).

cesa-bianchi@dsi.unimi.it

claudio.gentile@uninsubria.it

forabona@idiap.ch

the label is predicted but not queried, then the learnernever knows whether his prediction was correct. Thus,
only queried labels are observed while all others remain
unknown. This protocol is often called selective sampling, and we interchangeably use queried labels andsampled labels to denote the labels observed by thelearner.
Given a general online prediction technique, like regularized least squares (RLS), we are interested in controlling the predictive performance as the query rate
goes from fully supervised (all labels are queried) to
fully unsupervised (no label is queried). This is motivated by observing that, in a typical practical scenario, one might want to control the accuracy of predictions while imposing an upper bound on the query
rate. In fact, the number of observed labels has usuallya very direct influence on basic computational aspectsof online learning algorithms, such as running time andstorage requirements.
In this work we develop semi-supervised variants of
RLS for binary classification. We analyze these variants under no assumptions on the mechanism generating the sequence of instances, while imposing a simple
linear noise model for the conditional label distribution. Intuitively, our algorithms issue a query whena common upper bound on bias and variance of thecurrent RLS estimate is larger than a given threshold.
Conversely, when this upper bound gets small, we infer
via a simple large deviation argument that the marginof the RLS estimate on the current instance is closeenough to the margin of the Bayes optimal classifier.
Hence the learner can safely avoid issuing a query onthat step.
In order to summarize our results, assume for thesake of simplicity that the Bayes optimal classifier —which for us is a linear classifier u— has unknown

Robust Bounds for Classification via Selective Sampling

margin |u⊤ xt | ≥ ε > 0 on all instances xt ∈ Rd .
Then, in our data model, the average (per-step) riskof the fully supervised RLS, asking NT = T labels in
T steps, is known to converge to the average risk of
−1excludthe Bayes optimal classifier at rate d ε2 T
ing logarithmic factors. In this work we show that,using our semi-supervised RLS variant, we can replace
NT = T with any desired query bound NT = d T κ (for0 ≤ κ ≤ 1) while achieving a convergence rate of order
−1
−1
d ε2 T+ ε2/κ T.

One might wonder whether these results could also be
obtained just by running a standard RLS algorithmwith a constant label sampling rate, say T κ−1 , independent of the sequence of instances. If we could provefor RLS an instantaneous regret bound like d/T thenthe answer would be affirmative. However, the lack ofassumptions on the way instances are generated makes
it hard to prove any nontrivial instantaneous regretbound.
If the margin ε is known, or, equivalently, our goal
is to approximate the Bayes margin to some accuracy ε, then we show that the above strategies achieve,with high probability, any desired accuracy ε by querying only order of d/ε2 labels (excluding logarithmic
factors). Again, the reader should observe that thisbound could not be obtained by, say, concentrating all
queries on an initial phase of length O(d/ε2 ). In sucha case, an obvious adversarial strategy would be to
generate noninformative instances just in that phase.
In short, if we require online semi-supervised learningalgorithms to work in worst-case scenarios we need toresort to nontrivial label sampling techniques.
We have run comparative experiments on both artificial and real-world medium-sized datasets. These experiments, though preliminary in nature, reveal theeffectiveness of our sampling strategies even from apractical standpoint.
1.1. Related work and comparison
Selective sampling is a well-known semi-supervised online learning setting. Pioneering works in this areaare (Cohn et al., 1990) and (Freund et al., 1997).
More recent related results focusing on linear classification problems include (Balcan et al., 2006; Balcan
et al., 2007; Cavallanti et al., 2009; Cesa-Bianchi et al.,2006b; Dasgupta et al., 2008; Dasgupta et al., 2005;
Strehl & Littman, 2008), although some of these works
analyze batch rather than online protocols. Most previous studies consider the case when instances are
drawn i.i.d. from a fixed distribution, exceptions being
the worst-case analysis in (Cesa-Bianchi et al., 2006b)

and the very recent analysis in the KWIK learning
protocol (Strehl & Littman, 2008). Both of these papers use variants of RLS working on arbitrary instancesequences. The work (Cesa-Bianchi et al., 2006b) iscompletely worst case: the authors make no assumptions whatsoever on the mechanism generating labels
and instances; however, they are unable prove bounds
on the label query rate as we do here. The KWIK
model of (Strehl & Littman, 2008) —see also the moregeneral setup in (Li et al., 2008)— is closest to thesetting considered in this paper. There the goal is toapproximate the Bayes margin to within a given accuracy ε. The authors assume arbitrary sequences of instances and the same linear stochastic model for labelsas the one considered here. A modification of the linear
regressor in (Auer, 2002), combined with covering arguments, allows them to compete against an adaptive
adversarial strategy for generating instances. Their algorithm,however, yields the significantly worse bounde d3 /ε4 on the number of queries, and seems to workOin the finite dimensional (d < ∞) case only. In contrast, our algorithms achieve the better query bounde d/ε2 against oblivious adversaries. Moreover, ourOalgorithms can be easily run in any infinite dimensional
RKHS.

2. Preliminaries
In the selective sampling protocol for online binaryclassification, at each step t = 1, 2, . . . the learnerreceives an instance xt ∈ Rd and outputs a binary
prediction for the associated unknown label yt ∈{−1, +1}. After each prediction the learner may observe the label yt only by issuing a query. If no query isissued at time t, then yt remains unknown. Since one
expects the learner’s performance to improve if morelabels are observed, our goal is to trade off predictive
accuracy against number of queries.
All results proven in this paper hold for any fixed individual sequence x1 , x2 , . . . of instances, under thesole assumption that kxt k = 1 for all t ≥ 1. Given
any such sequence, we assume the corresponding labelsyt ∈ {−1, +1} are realizations of random variables Ytsuch that E Yt = u⊤ xt for all t ≥ 1, where u ∈ Rd isa fixed and unknown vector such that kuk = 1. Notethat sgn ∆t ), for ∆t = u⊤ x, is the Bayes optimalclassifier for this noise model.
We studyuse selective sampling algorithms thatb t to predict Yt . The quantity ∆b t = w⊤
sgn ∆
x
is
a
t t
margin computed via the RLS estimate
−1⊤
St−1 Y t−1(1)
wt = I + St−1 St−1
+ xt x⊤t ′defined over the matrix St−1 = x1 , . . . , x′Nt−1 of theRobust Bounds for Classification via Selective SamplingNt−1 queried instances up to timet − 1. The random
vector Y t−1 = Y1′ , . . . , YN′ t−1 contains the observedlabels (so that Yk′ is the label of x′k ), and I is the d × didentity matrix.
We are interested in simultaneously controlling the cumulative regret
RT =

T 
X
t=1


b t < 0) − P(Yt ∆t < 0)P(Yt ∆(2)and the number NT of queried labels, uniformly overT.
⊤+ xt x⊤Let At = I + St−1 St−1
t . We introduce thefollowing relevant quantities: −1−1
rt = x⊤Bt = u⊤ I + xt x⊤
t At xtt At xt ,st = A−1t xt⊤
q t = St−1
At−1 xt ,.

The following properties of the RLS estimate (1) havebeen proven in, e.g., (Cesa-Bianchi et al., 2006a).
Lemma 1 For each t = 1, 2, . . . the following inequalities hold:b t = ∆t − Bt ;1. E ∆
2. |Bt | ≤ st + rt ;√3. st ≤ rt ;2

4. kq t k ≤ rt ;5. For all ε > 0,b t + Bt − ∆t ≥ ε ≤ 2 exp −
P ∆

ε2
2

2 kq t k!

;

6. If NT is the total number of queries issued in thefirst T steps, thenX

1≤t≤T
Yt queried

rt ≤



NT
ln(1 + λi ) ≤ d ln 1 +
d
i=1

d
X

where λi is the i-th eigenvalue of the (Gram) matrix ST⊤ ST defined on the queried instances.

3. A new selective sampling algorithm
Our main theoretical result provides bounds on the
cumulative regret and the number of queried labels
for the selective sampling algorithm introduced in Figure 1. We call this algorithm the BBQ (Bound on

Algorithm 1 The BBQ selective sampler
Parameters: 0 ≤ κ ≤ 1
Initialization: Weight vector w = 0
for each time step t = 1, 2, . . . do
Observe instance xt ∈ Rd ;predict label yt ∈ {−1, +1} with sgn(w⊤ xt );if rt > t−κ thenquery label yt ,update wt using (xt , yt ) as in (1).
end ifend forBias Query) algorithm. BBQ queries xt wheneverrt is larger than a threshold vanishing as t−κ , where0 ≤ κ ≤ 1 is an input parameter. This simple query
condition builds on Property 5 of Lemma 1. This propb t is likely to be close to the margin
erty shows that ∆∆t of the Bayes optimal predictor when both the bias
2
Bt and the variance bound kq t k are small. Since thesequantities are both bounded by (functions of) rt (seeProperties 2, 3, and 4 of Lemma 1), this suggests that
one can safely disregard Yt when rt is small.
According to our noise model, the label of xt is harder
to predict if |∆t | is small. For this reason, our regret bound is split into a cumulative regret on “bigmargin” steps t, where |∆t | ≥ ε, and “small margin”
steps, where |∆t | < ε. On one hand, we bound theregret on small margin steps simply by ε Tε , whereTε = {1 ≤ t ≤ T : |∆t | < ε} . On the other hand, weshow that the overall regret can be bounded in termsof the best possible choice of ε with no need for thealgorithm to know this optimal value.
Theorem 1 If BBQ is run with input κ ∈ [0, 1] thenits cumulative regret RT after any number T of steps
satisfies 1/κ
8
RT ≤ min ε Tε + (2 + e) ⌈1/κ⌉! 2
0<ε<1
ε




NT
2 8d
.
ln 1 ++ 1+e ε2dThe number of queried labels is NT = O (d T κ ln T ) .
It is worth observing that the bounds presented here
hold in the finite dimensional (d < ∞) case only.
One can easily turn them to work in any RKHS after switching to an eigenvalue representation of the
cumulative regret —e.g., by using the middle boundin Property 6 of Lemma 1 rather than the rightmost
one, as we did in the proof below. This essentially corresponds to analyzing Algorithm 1 in a dual variable
representation. A similar comment holds for Remark 1
and Theorem 2 below.

Robust Bounds for Classification via Selective Sampling

In the rest of the paper we denote by {φ} the indicatorfunction of a Boolean predicate φ.
Proof: [of Theorem 1] Fix any ε ∈ (0, 1). As in (Cavallanti et al., 2009), we first observe that our label
noise model allows us to upper bound the time-t reb t < 0) − P(Yt ∆t < 0) as
gret P(Yt ∆b t < 0) − P(Yt ∆t < 0)P(Yt ∆b t ∆t ≤ 0, |∆t | ≥ ε≤ ε{|∆t | < ε} + P ∆
b t − ∆t ≥ ε .
≤ ε{|∆t | < ε} + P ∆Hence the cumulative regret (2) can be split as follows:RT ≤ ε Tε +TXb t − ∆t ≥ ε .
P ∆

(3)

t=1

b t − ∆t ≥We proceed by expanding the indicator of ∆ε with the introduction of the bias term Btono nb t − ∆t ≥ ε ≤ ∆b t + Bt − ∆t ≥ ε∆2nεo+ |Bt | >.
2

Note that




n
ε2
ε2
εo
≤ rt >≤ e exp −|Bt | >
2
8
8rt

the first inequality deriving from a combination of
Properties 2 and 3 in Lemma 1 and then overapproximating, whereas the second one uses {b < 1} ≤e1−b ∀ b. Moreover, by Properties 4 and 5 in Lemma 1,
we have that




2
b t + Bt − ∆t ≥ ε ≤ 2 exp − ε
P ∆
.
2
8rt
We substitute this back into (3) and single out thesteps where queries are issued. This gives


X
ε2
exp −
RT ≤ ε Tε + (2 + e)
8rt
t : rt ≤t−κ


X
ε2
exp −
+ (2 + e).
8rt−κt : rt >tThe second term is bounded as follows: 2 κ
 X
T
ε2
ε t
exp −
exp −
≤
8rt
8
−κ
t=1

X

≤

0



ε2 xκ
exp −
8



1
dx = Γ(1/κ)κ

1
The first step uses the inequality e−x ≤ ex
for x > 0,
while the second step uses Property 6 in Lemma 1.
Finally, in order to derive a bound on the number NTof queried labels, we have
X
X
rt
κ
rt
≤
T
NT ≤
t−κ
t : rt >t−κ
t : rt >t−κNTκ≤ d T ln 1 +dwhere for the last inequality we used, once more, Property 6 in Lemma 1. Hence, NT = O (d T κ ln T ) , andthis concludes the proof.
It is important to observe that, if we disregard themargin term ε Tε (which is fully controlled by the adversary), the regret bound depends logarithmically on
T for any constant κ > 0:


d
1
+
ln
T
.
RT ≤ ε Tε + O
ε2ε2/κIf κ is set to 1 then our bound on the number of queries
NT becomes vacuous, and the selective sampling algorithm essentially becomes fully supervised. This recovers the known regret bound for RLS
 in the fully
supervised case, RT ≤ ε Tε + O (d ln T ) ε2 .

Remark 1 A randomized variant of BBQ exists that(1−κ)/κ
queries label yt with independent probability rt∈[0, 1]. Through a similar bias-variance analysis as
the one in Theorem 1 above, one can show thatin expectation (over the internal randomization ofthis algorithm) the cumulative
 regret RT is boundedLby min0<ε<1 ε Tε + O ε2/κwhile the number ofqueried labels NT is O T κ L1−κ , being L = d ln T .
This bound is similar (though generally incomparable)
to the one of Theorem 1.

4. A parametric performance guaranteet : rt ≤tZ ∞Γ(·) is the Euler’s Gamma function Γ(x) =Rwhere∞ −t x−1etdt. We further bound κ1 Γ(1/κ) ≤ ⌈1/κ⌉!
0
using the monotonicity of Γ. For the third term we
write


X
X
ε2
8
exp −
≤ 2
rt
8rt
eε
t : rt >t−κ
t : rt >t−κ


8d
NT
.
≤ 2 ln 1 +
eε
d



8
ε2

1/κ

In the proof of Theorem 1 the quantity ε acts as a
threshold for the cumulative regret, which is split intoa sum over steps t such that |∆t | < ε (where the regret

Robust Bounds for Classification via Selective Sampling

Algorithm 2 The parametric BBQ selective sampler
Parameters: 0 < ε, δ < 1
Initialization: weight vector w = 0
for each time step t = 1, 2, . . . doobserve instance xt ∈ Rd ;⊤predict label yt ∈ {−1, +1}
r with sgn(w xt )t(t + 1)then
if ε − rt − st + < kq t k 2 ln
2δquery label yt
update wt using (xt , yt ) as in (1)end ifend forgrows by less than ε) and a sum over the remaining
steps. Most technicalities in the proof are due to thefact that the final bound depends on the optimal choiceof this ε, which the algorithm need not know. On theother hand, if a specific value for ε is provided in input
to the algorithm, then the cumulative regret over steps
t such that |∆t | ≥ ε can be bounded by any constantδ > 0 using only order of (d/ε2 ) ln(T /δ) queries. In
particular, when mint |∆t | ≥ ε, the above logarithmic
bound implies that the per-step regret vanishes exponentially fast as a function of the number of queries.
As we stated in the introduction, this result cannot be
obtained as an easy consequence of known results, due
to the adversarial nature of the instance sequence.
We now develop the above argument for a practicallymotivated variant of our BBQ selective sampler. Let
us disregard for a moment the bias term Bt . In orderb t − ∆t ≤ ε holds when no queryto guarantee that ∆is issued, it is enough to observe thatqProperty 5 ofb t − ∆t ≤Lemma 1 implies that ∆2rt ln 2 with
δ

probability at least 1 − δ. This immediately delivers arule prescribing that no query be issued at time t whenq

2rt ln 2δ ≤ ε. A slightly more involved condition,
one that better exploits the inequalities of Lemma 1,
allows us to obtain a significantly improved practical
performance. This results in the algorithm describedin Figure 2. The algorithm, called Parametric BBQ,
takes in input two parameters ε and δ, and issues aquery at time t whenever1r2t(t + 1).
(4)
ε − rt − st + < kq t k 2 lnδ
Theorem 2 If Parametric BBQ is run with inputε, δ ∈ (0, 1) then:b t − ∆t ≤ ε holds
1. with probability at least 1 − δ, ∆on all time steps t when no query is issued;1ˆHere and throughout x]+ = max{0, x}.

2. the number NT of queries issued after any number
T of steps is bounded as ln(T /δ)
T
d
ln
.
ln
NT = Oε2
δεThis theorem has been phrased so as to make it easier to compare to a corresponding result in (Strehl& Littman, 2008) for the KWIK (“Knows What It
Knows”) framework. In that paper, the authors use
a modification of Auer’s upper confidence linear regression algorithm for associative reinforcement learning (Auer, 2002). This modification allows them tocompete against any adaptive adversarial strategy generating instance vectors xt , but it yields the signifie d3 /ε4 on NT (in the KWIK
cantly worse bound O
setting NT is the number of times the prediction algorithm answers “I don’t know”). Besides, their strategy
seems to work in the finite dimensional (d < ∞) caseonly. In contrast, Parametric BBQ works against an
oblivious adversary
only, but it has the better bound
e d/ε2 , with the Oe notation hiding a mild
NT = O(logarithmic) dependence on T . Moreover, Parametric BBQ can be readily run in infinite (d = ∞) dimensional RKHS —recall the comment before the proof of
Theorem 1. In fact, this is a quite important feature:
the real-world experiments of Section 5 needed kernels
in order to either attain a good empirical performance(on Adult) or use a reasonable amount of computational resources (on RCV1).
Remark 2 The bound on the number of queried labels in Theorem 2 is optimal up to logarithmic factors.
In fact, it is possible to prove that there exists a sequence x1 , x2 , . . . of instances and a number ε0 > 0such that: for all ε ≤ ε0 and for any learning algorithm that issues N = O(d/ε2 ) queries there exists
 atarget vector u ∈ Rd and a time step t = Ω d/ε2 forb t computed by the algorithm forwhich the estimate ∆⊤b t − ∆t | > ε = Ω 1 .
∆t = u xt has the property
P |∆
Hence, at least Ω d/ε2 queries are needed to learn any
target hyperplane with arbitrarily small accuracy andarbitrarily high confidence.
Proof: [Theorem 2] Let I ⊆ {1, . . . , T } be the setof time steps when a query is issued. Then, using
Property 2 of Lemma 1 we can writeoXnb t − ∆t > ε
∆
t∈I
/

≤

≤

Xn
t∈I
/

Xn
t∈I
/

o
b t + Bt − ∆t > ε − |Bt |∆b t + Bt − ∆t > [ε − rt − st ]+∆o.

Robust Bounds for Classification via Selective Sampling

t∈I
/

≤

≤
≤


X 
b t + Bt − ∆t > [ε − rt − st ]+
P ∆
t∈I
/

X
t∈I
/

X
t∈I
/

2 exp −

|ε − rt − st |+2

2 kq t k

In order to derive a bound on the number NT ofqueried labels, we proceed as follows. For every stept ∈ I in which a query was issued we can write√
ε − rt − rt ≤ ε − rt − st ≤ ε − rt − st +rr
2t(t + 1)
2t(t + 1)≤ kq t k 2 ln
≤ 2 rt lnδδ
where we used Properties 3 and 4 of Lemma 1. Solving
for rt and overapproximating we obtain(5)

Similarly to the proof of Theorem 1, we then writeXNTNT min rt ≤rt ≤ d ln 1 +
.
t∈I
d
t∈I

Using (5) we get NT = O



d
ε2



ln Tδ ln ln(Tε/δ) .

0.4

0.6

0.3

0.4

0.2

0.2

0.1

0.2

0.3

0.4

0.5

0.6
ε

0.7

0.8

0.9

0
1

Figure 1. Maximum error (jagged blue line) and number ofqueried labels (decreasing green line) on a synthetic dataset
for Parametric BBQ with δ = 0.1 and 0.15 ≤ ε ≤ 1. The
straight blue line is the theoretical upper bound on the
maximum error provided by the theory.

∞
X
δ
δ
≤
=δ .
t(t + 1)
t(t
+
1)
t=1

ε2
rt ≥
2 .

q
2t(t+1)2ε + 1 + 2 ln δ

Theoretical maximum error
Measured maximum error
Fraction of queried labels

0.8

0

2 !

0.5

Fraction of queried labels

This givesX 
b t − ∆t > εP ∆1Maximum error

We first take expectations on both sides, and then apply Property 5 of Lemma 1 along with condition (4)rewritten as follows
2 !
[ε − rt − st ]+δ≤.
2 exp −
2t(t+1)
2 kq t k

5. Experiments
In this section we report on preliminary experimentswith the Parametric BBQ algorithm. The first test
is a synthetic experiment to validate the model. We
generated 10,000 random examples on the unit circle
in R2 . The labels of these examples were generated
according to our noise model (see Section 2) using arandomly selected hyperplane u with unit norm. We
then set δ = 0.1 and analyzed the behavior of the algorithm with various settings of ε > 0 and using alinear kernel. In Figure 1 the jagged blue line represents the maximum error over the example sequence,b t − ∆t . (Although we stopped the plot ati.e., maxt ∆ε = 1, note that the maximum error√ is dominated byb t |, which can be of the order of Nt .) As predicted|∆by Theorem 2, the maximum error remains below thestraight line y = ε (the maximum error predicted by
the theory). In the same plot, the decreasing green
line shows the number of queried labels, which closely
follows the curve ε−2 predicted by the theory.
This initial test reveals that the algorithm is dramatically underconfident, i.e., it is a lot more precise thanit thinks. Moreover, the actual error is rather insensitive to the choice of ε. In order to leverage on this, we
ran the remaining tests using Parametric BBQ witha more extreme setting of parameters. Namely, wechanged the query condition (the “if” condition in Algorithm 2) tor2for 0 < δ < 1 .
1 − rt − st + < kq t k 2 lnδThis amounts to setting the desired error to a default
value of ε = 1 while making the number of queriedlabels independent of T .

With the above setting, we compared Parametric BBQ
to the second-order version of the label-efficient classifier (SOLE) of (Cesa-Bianchi et al., 2006b). This isa mistake-driven RLS algorithm that queries the labelb t |),of the current instance with probability 1/(1 + b |∆b t is the RLS marwhere b > 0 is a parameter and ∆gin. The other baseline algorithm is a vanilla sampler(called Random in the plots) that asks labels at random with constant probability 0 < p < 1. Recall that
SOLE does not come with a guaranteed bound on theRobust Bounds for Classification via Selective Sampling
0.62

0.75

0.6

0.7

0.65

0.56

F−measureF−measure

0.58

0.54
0.52

0.6

0.55
0.5
SOLE
RandomParametric BBQ

0.48
0.46
0

0.01

0.02
0.03
0.04
Fraction of queried labels

0.05

0.06

0.5

0.45
0.05

SOLE
RandomParametric BBQ
0.1

0.15
0.2
0.25
0.3
Fraction of queried labels

0.35

0.4

Figure 2. F-measure against fraction of queried labels on
the a9a dataset (32,561 examples in random order). The
plotted curves are averages over 10 random shuffles.

Figure 3. F-measure against fraction of queried labels averaged over the 50 most frequent categories of RCV1 (first
40,000 examples in chronological order).

number of queried labels. Random, on the other hand,
has the simple expectation bound E[NT ] = p T .

plotted against the average fraction of queried labels,
where averages are computed over the 50 classifiers.
Here the algorithms need over 35% of labels to saturate. Moreover, Parametric BBQ performs worse than
SOLE, although still better than Random.

For each algorithm we plot the F-measure (harmonicmean of precision and recall) against the fraction ofqueried labels. We control the fraction of queried labels by changing the parameters of the three algorithms (δ for Parametric BBQ, b for SOLE, and p for
Random).
For the first real-world experiment we chose a9a2 , a
subset of the census-income (Adult) database with
32,561 binary-labeled examples and 123 features. In
order to bring all algorithms to a reasonable performance level, we used a Gaussian kernel with σ 2 = 12.5.
The plots (Figure 2) show that less than 6% queries
are enough for the three algorithms to saturate theirperformance. In the whole query range Parametric
BBQ is consistently slightly better than SOLE, while
Random has the worst performance.
For our second real-world experiment we used the first
40,000 newswire stories in chronological order fromthe Reuters Corpus Volume 1 dataset (RCV1). Eachnewsstory of this corpus is tagged with one or morelabels from a set of 102 classes. A standard TF-IDF
bag-of-words encoding was used to obtain 138,860 features. We considered the 50 most populated classes
and trained 50 classifiers one-vs-all using a linear
kernel. Earlier experiments, such as those reportedin (Cesa-Bianchi et al., 2006b), show that RLS-basedalgorithms perform best on RCV1 when run in a mistake driven fashion. For this reason, on this dataset
we used a mistake-driven variant of Parametric BBQ,
storing a queried label only when it is wrongly predicted. Figure 3 shows the (macro)average F-measure2

www.csie.ntu.edu.tw/∼cjlin/libsvmtools/

Since SOLE and Parametric BBQ are both based on
the mistake-driven RLS classifier, any difference ofperformance is due to their different query conditions:
SOLE is margin-based, while Parametric BBQ uses
kq t k and related quantities. Note that, unlike themargin, q t does not depend on the queried labels,
but only on the correlation between their corresponding instances. This fact, which helped us a lot in
the analysis of BBQ, could make a crucial difference
between domains like RCV1 (where instances are extremely sparse) and Adult (where instances are relatively dense). More experimental work is needed inorder to settle this conjecture.

6. Conclusions and ongoing research
We have introduced a new family of online algorithms,
the BBQ family, for selective sampling under (oblivious) adversarial environments. These algorithms naturally interpolate between fully supervised and fully
unsupervised learning scenarios. A parametric variant(Parametric BBQ) of our basic algorithm is designed
to work in a weakened KWIK framework (Li et al.,2008; Strehl & Littman, 2008) with improved bounds
on the number of queried labels.
We have made preliminary experiments. First, we validated the theory on an artificially generated dataset.
Second, we compared a variant of Parametric BBQ toalgorithms with similar guarantees, with encouraging
results.

Robust Bounds for Classification via Selective Sampling

A few issues we are currently working on are the following. First, we are trying to see if a sharper analysis
of BBQ exists which allows one to prove a regret boundTwhen NT = O(d ln T ). Thisof the form ε Tε + d lnε2bound would be a worst-case analog of the bound Cavallanti et al. (2009) have obtained in an i.i.d. setting.
This improvement is likely to require refined bounds
on bias and variance of our estimators. Moreover, we
would like to see if it is possible either to remove theln T dependence on the bound on NT in Theorem 2 or
to make Parametric BBQ work in adaptive adversarial
environments (presumably at the cost of looser bounds
on NT ). In fact, it is currently unclear to us how a direct covering argument could be applied in Theorem 2
which avoids the need for a conditionally independent
structure of the involved random variables.
On the experimental side, we are planning to perform
a more thorough empirical investigation using additional datasets. In particular, since our algorithms
can also be viewed as memory bounded procedures,
we would like to see how they perform when compared
to budget-based algorithms, such as those in (Weston
et al., 2005; Dekel et al., 2007; Cavallanti et al., 2007;
Orabona et al., 2008).
Finally, since our algorithms can be easily adapted tosolve regression tasks, we are planning to test the BBQ
family on standard regression benchmarks.

Acknowledgments
We would like to thank the anonymous reviewers fortheir helpful comments. The third author is supportedby the DIRAC project under EC grant FP6-0027787.
All authors acknowledge partial support by the PASCAL2 NoE under EC grant FP7-216886. This publication only reflects the authors’ views.

References
Auer, P. (2002).
Using confidence bounds for
exploitation-exploration trade-offs. Journal of Machine Learning Research, 3, 397–422.
Balcan, M., Beygelzimer, A., & Langford, J. (2006).
Agnostic active learning. Proc. of the 23rd International Conference on Machine Learning (pp. 65–72).
Balcan, M., Broder, A., & Zhang, T. (2007). Marginbased active learning. Proceedings of the 20th Annual Conference on Learning Theory (pp. 35–50).
Cavallanti, G., Cesa-Bianchi, N., & Gentile, C. (2007).
Tracking the best hyperplane with a simple budget
Perceptron. Machine Learning, 69, 143–167.

Cavallanti, G., Cesa-Bianchi, N., & Gentile, C. (2009).
Linear classification and selective sampling under
low noise conditions. In Advances in Neural Information Processing Systems 21 (pp. 249–256).
Cesa-Bianchi, N., Gentile, C., & Zaniboni, L. (2006a).
Incremental algorithms for hierarchical classification. Journal of Machine Learning Research, 7, 31–
54.
Cesa-Bianchi, N., Gentile, C., & Zaniboni, L. (2006b).
Worst-case analysis of selective sampling for linear classification. Journal of Machine Learning Research, 7, 1025–1230.
Cohn, R., Atlas, L., & Ladner, R. (1990). Training connectionist networks with queries and selective sampling. In Advances in Neural Information
Processing Systems 2 (pp. 566–573).
Dasgupta, S., Hsu, D., & Monteleoni, C. (2008). A
general agnostic active learning algorithm. In Advances in Neural Information Processing Systems 21(pp. 353–360).
Dasgupta, S., Kalai, A. T., & Monteleoni, C. (2005).
Analysis of perceptron-based active learning. Proceedings of the 18th Annual Conference on Learning
Theory (pp. 249–263).
Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2007).
The Forgetron: A kernel-based Perceptron on a budget. SIAM Journal on Computing, 37, 1342–1372.
Freund, Y., Seung, S., Shamir, E., & Tishby, N. (1997).
Selective sampling using the query by committee algorithm. Machine Learning, 28, 133–168.
Li, L., Littman, M., & Walsh, T. (2008). Knows
what it knows: a framework for self-aware learning.
Proceedings of the 25th International Conference on
Machine Learning (pp. 568–575).
Orabona, F., Keshet, J., & Caputo, B. (2008). The
Projectron: a bounded kernel-based Perceptron.
Proceedings of the 25th International Conference on
Machine Learning (pp. 720–727).
Strehl, A., & Littman, M. (2008). Online linear regression and its application to model-based reinforcement learning. In Advances in Neural Information
Processing Systems 20 (pp. 631–638).
Weston, J., Bordes, A., & Bottou, L. (2005). Online(and offline) on an even tighter budget. Proceedingsof the 10th International Workshop on Artificial Intelligence and Statistics (pp. 413–420).