On Multilabel Classification and Ranking with
Partial Feedback
Claudio Gentile
DiSTA, Università dell’Insubria, Italy
claudio.gentile@uninsubria.it

Francesco Orabona
TTI Chicago, USA
francesco@orabona.com

Abstract
We present a novel multilabel/ranking algorithm working in partial information
settings. The algorithm is based on 2nd-order descent methods, and relies on
upper-confidence bounds to trade-off exploration and exploitation. We analyze
this algorithm in a partial adversarial setting, where covariates can be adversarial,
but multilabel probabilities are ruled by (generalized) linear models. We showO(T 1/2 log T ) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting
against full-information baselines on real-world multilabel datasets, often obtaining comparable performance.

1

Introduction

Consider a book recommendation system. Given a customer’s profile, the system recommends a few
possible books to the user by means of, e.g., a limited number of banners placed at different positions
on a webpage. The system’s goal is to select books that the user likes and possibly purchases.
Typical feedback in such systems is the actual action of the user or, in particular, what books he hasbought/preferred, if any. The system cannot observe what would have been the user’s actions had
other books got recommended, or had the same book ads been placed in a different order within the
webpage. Such problems are collectively referred to as learning with partial feedback. As opposedto the full information case, where the system (the learning algorithm) knows the outcome of eachpossible response (e.g., the user’s action for each and every possible book recommendation placedin the largest banner ad), in the partial feedback setting, the system only observes the response tovery limited options and, specifically, the option that was actually recommended. In this and manyother examples of this sort, it is reasonable to assume that recommended options are not given thesame treatment by the system, e.g., large banners which are displayed on top of the page should
somehow be more committing as a recommendation than smaller ones placed elsewhere. Moreover,
it is often plausible to interpret the user feedback as a preference (if any) restricted to the displayedalternatives.
We consider instantiations of this problem in the multilabel and learning-to-rank settings. Learning
proceeds in rounds, in each time step t the algorithm receives an instance xt and outputs an ordered
subset Ŷt of labels from a finite set of possible labels [K] = {1, 2, . . . , K}. Restrictions might apply
to the size of Ŷt (due, e.g., to the number of available slots in the webpage). The set Ŷt corresponds
to the aforementioned recommendations, and is intended to approximate the true set of preferences
associated with xt . However, the latter set is never observed. In its stead, the algorithm receives
Yt ∩ Ŷt , where Yt ⊆ [K] is a noisy version of the true set of user preferences on xt . When we are
restricted to |Ŷt | = 1 for all t, this becomes a multiclass classification problem with bandit feedback– see below.
Related work. This paper lies at the intersection between online learning with partial feedback andmultilabel classification/ranking. Both fields include a substantial amount of work, so we can hardly
do it justice here. We outline some of the main contributions in the two fields, with an emphasis on
those we believe are the most related to this paper.
1

A well-known and standard tool of facing the problem of partial feedback in online learning is totrade off exploration and exploitation through upper confidence bounds [16]. In the so-called bandit
setting with contextual information (sometimes called bandits with side information or bandits withcovariates, e.g., [3, 4, 5, 7, 15], and references therein) an online algorithm receives at each time
step a context (typically, in the form of a feature vector x) and is compelled to select an action(e.g., a label), whose goodness is quantified by a predefined loss function. Full information about
the loss function is not available. The specifics of the interaction model determines which pieces
of loss will be observed by the algorithm, e.g., the actual value of the loss on the chosen action,some information on more profitable directions on the action space, noisy versions thereof, etc. The
overall goal is to compete against classes of functions that map contexts to (expected) losses in aregret sense, that is, to obtain sublinear cumulative regret bounds. For instance, [1, 3, 5, 7] work ina finite action space where the mappings context-to-loss for each action are linear (or generalized
linear, as in [7]) functions of the features. They all obtain T 1/2 -like regret bounds, where T is
the time horizon. This is extended in [15], where the loss function is modeled as a sample froma Gaussian process over the joint context-action space. We are using a similar (generalized) linear
modeling here. Linear multiclass classification problems with bandit feedback are considered in,e.g., [4, 11, 13], where either T 2/3 or T 1/2 or even logarithmic regret bounds are proven, dependingon the noise model and the underlying loss functions.
All the above papers do not consider structured action spaces, where the learner is afforded to selectsets of actions, which is more suitable to multilabel and ranking problems. Along these lines are
the papers [10, 14, 19, 20, 22]. The general problem of online minimization of a submodular loss
function under both full and bandit information without covariates is considered in [10], achieving a
regret T 2/3 in the bandit case. In [22] the problem of online learning of assignments is considered,
where an algorithm is requested to assign positions (e.g., rankings) to sets of items (e.g., ads) withgiven constraints on the set of items that can be placed in each position. Their problem shares
similar motivations as ours but, again, the bandit version of their algorithm does not explicitly takeside information into account, and leads to a T 2/3 regret bound. In [14] the aim is to learn a suitableordering of the available actions. Among other things, the authors prove a T 1/2 regret bound in
the bandit setting with a multiplicative weight updating scheme. Yet, no contextual information isincorporated. In [20] the ability of selecting sets of actions is motivated by a problem of diverse
retrieval in large document collections which are meant to live in a general metric space. The
generality of this approach does not lead to strong regret guarantees for specific (e.g., smooth) loss
functions. [19] uses a simple linear model for the hidden utility function of users interacting with a
web system and providing partial feedback in any form that allows the system to make significant
progress in learning this function. A regret bound of T 1/2 is again provided that depends on the
degree of informativeness of the feedback. It is experimentally argued that this feedback is typicallymade available by a user that clicks on relevant URLs out of a list presented by a search engine.
Despite the neatness of the argument, no formal effort is put into relating this information to thecontext information at hand or to the way data are generated. Finally, the recent paper [2] investigatesclasses of graphical models for contextual bandit settings that afford richer interaction between
contexts and actions leading again to a T 2/3 regret bound.
The literature on multilabel learning and learning to rank is overwhelming. The wide attention thisliterature attracts is often motivated by its web-search-engine or recommender-system applications,and many of the papers are experimental in nature. Relevant references include [6, 9, 23], alongwith references therein. Moreover, when dealing with multilabel, the typical assumption is fullsupervision, an important concern being modeling correlations among classes. In contrast to that, thespecific setting we are considering here need not face such a modeling [6]. Other related references
are [8, 12], where learning is by pairs of examples. Yet, these approaches need i.i.d. assumptions on
the data, and typically deliver batch learning procedures. To summarize, whereas we are technicallyclose to [1, 3, 4, 5, 7, 15], from a motivational standpoint we are perhaps closest to [14, 19, 22].
Our results. We investigate the multilabel and learning-to-rank problems in a partial feedback
scenario with contextual information, where we assume a probabilistic linear model over the labels,
although the contexts can be chosen by an adaptive adversary. We consider two families of loss functions, one is a cost-sensitive multilabel loss that generalizes the standard Hamming loss in several
respects, the other is a kind of (unnormalized) ranking loss. In both cases, the learning algorithm ismaintaining a (generalized) linear predictor for the probability that a given label occurs, the ranking
being produced by upper confidence-corrected estimated probabilities. In such settings, we prove2T 1/2 log T cumulative regret bounds — these bounds are optimal, up to log factors, when the label
probabilities are fully linear in the contexts. A distinguishing feature of our user feedback model isthat, unlike previous papers (e.g., [1, 10, 15, 22]), we are not assuming the algorithm is observing anoisy version of the risk function on the currently selected action. In fact, when a generalized linear
model is adopted, the mapping context-to-risk turns out to be nonconvex in the parameter space.
Furthermore, when operating on structured action spaces this more traditional form of bandit model
does not seem appropriate to capture the typical user preference feedback. Our approach is based on
having the loss decouple from the label generating model, the user feedback being a noisy version of
the gradient of a surrogate convex loss associated with the model itself. As a consequence, the algorithm is not directly dealing with the original loss when making exploration. Though the emphasis ison theoretical results, we also validate our algorithms on two real-world multilabel datasets w.r.t. a
number of loss functions, showing good comparative performance against simple multilabel/ranking
baselines that operate with full information.

2

Model and preliminaries

We consider a setting where the algorithm receives at time t the side information vector xt ∈ Rd ,is allowed to output at a (possibly ordered) subset Ŷt ⊆ [K] of the set of possible labels, then thesubset of labels Yt ⊆ [K] associated with xt is generated, and the algorithm gets as feedback Ŷt ∩Yt .
The loss suffered by the algorithm may take into account several things: the distance between Yt
and Ŷt (both viewed as sets), as well as the cost for playing Ŷt . The cost c(Ŷt ) associated withŶt might be given by the sum of costs suffered on each class i ∈ Ŷt , where we possibly take into
account the order in which i occurs within Ŷt (viewed as an ordered list of labels). Specifically,
given constant a ∈ [0, 1] and costs c = {c(i, s), i = 1, . . . , s, s ∈ [K]}, such that 1 ≥ c(1, s) ≥c(2, s) ≥ . . . c(s, s) ≥ 0, for all s ∈ [K], we consider the loss function
P`a,c (Yt , Ŷt ) = a |Yt \ Ŷt | + (1 − a) i∈Ŷt \Yt c(ji , |Ŷt |),where ji is the position of class i in Ŷt , and c(ji , ·) depends on Ŷt only through its size |Ŷt |. In theabove, the first term accounts for the false negative mistakes, hence there is no specific ordering oflabels therein. The second term collects the loss contribution provided by all false positive classes,
taking into account through the costs c(ji , |Ŷt |) the order in which labels occur in Ŷt . The constanta serves as weighting the relative importance of false positive vs. false negative mistakes As a
specific example, suppose that K = 10, the costs c(i, s) are given by c(i, s) = (s − i + 1)/s, i =1, . . . , s, the algorithm plays Ŷt = (4, 3, 6), but Yt is {1, 3, 8}. In this case, |Yt \ Ŷt | = 2, andPi∈Ŷt \Yt c(ji , |Ŷt |) = 3/3 + 1/3, i.e., the cost for mistakingly playing class 4 in the top slot of Ŷt ismore damaging than mistakingly playing class 6 in the third slot. In the special case when all costs
are unitary, there is no longer need to view Ŷt as an ordered collection, and the above loss reduces toa standard Hamming-like loss between sets Yt and Ŷt , i.e., a |Yt \ Ŷt | + (1 − a) |Ŷt \ Yt |. Notice thatthe partial feedback Ŷt ∩ Yt allows the algorithm to know which of the chosen classes in Ŷt are goodor bad (and to what extent, because of the selected ordering within Ŷt ). Yet, the algorithm does notobserve the value of `a,c (Yt , Ŷt ) bacause Yt \ Ŷt remains hidden.
Working with the above loss function makes the algorithm’s output Ŷt become a ranked list ofclasses, where ranking is restricted to the deemed relevant classes only. In our setting, only a relevance feedback among the selected classes is observed (the set Yt ∩ Ŷt ), but no supervised ranking
information (e.g., in the form of pairwise preferences) is provided to the algorithm within this set.
Alternatively, we can think of a ranking framework where restrictions on the size of Ŷt are set by anexogenous (and possibly time-varying) parameter of the problem, and the algorithm is required toprovide a ranking complying with these restrictions. More on the connection to the ranking settingwith partial feedback is in Section 4.
The problem arises as to which noise model we should adopt so as to encompass significant real-world settings while at the same time affording efficient implementation of the resulting algorithms. For any subset Yt ⊆ [K], we let (y1,t , . . . , yK,t ) ∈ {0, 1}K be the corPK
responding indicator vector.
Then it is easy 
to see that `a,c (Yt , Ŷt ) = a i=1 yi,t + (1 −Paa) i∈Ŷt c(ji , |Ŷt |) − 1−a+ c(ji , |Ŷt |) yi,t . Moreover, because the first sum does not de3

pend on Ŷt , for the sake of optimizing over Ŷt we can equivalently define



X
a
c(ji , |Ŷt |) − 1−a`a,c (Yt , Ŷt ) = (1 − a)+ c(ji , |Ŷt |) yi,t .

(1)

i∈Ŷt

Let Pt (·) be a shorthand for the conditional probability Pt (· | xt ), where the side information vector xt can in principle be generated by an adaptive adversary as a function of the past. ThenPt (y1,t , . . . , yK,t ) = P(y1,t , . . . , yK,t | xt ), where the marginals Pt (yi,t = 1) satisfy1
Pt (yi,t = 1) =g(−u>i xt ),>
g(ui xt ) + g(−u>i xt )

i = 1, . . . , K,(2)

for some K vectors u1 , . . . , uK ∈ Rd and some (known) function g : D ⊆ R → R+ . The modeldis well defined if u>
i x ∈ D for all i and all x ∈ R chosen by the adversary. We assume for thesake of simplicity that ||xt || = 1 for all t. Notice that the variables yi,t need not be conditionally independent. We are only definining a family of allowed joint distributions Pt (y1,t , . . . , yK,t ) throughthe properties of their marginals Pt (yi,t ).
The function g above will be instantiated to the negative derivative of a suitable convex and nonincreasing loss function L which our algorithm will be based upon. For instance, if L is the squareloss L(∆) = (1 − ∆)2 /2, then g(∆) = 1 − ∆, resulting in Pt (yi,t = 1) = (1 + u>
i xt )/2, under theassumption D = [−1, 1]. If L is the logistic loss L(∆) = ln(1 + e−∆ ), then g(∆) = (e∆ + 1)−1 ,>>and Pt (yi,t = 1) = eui xt /(eui xt + 1), with domain D = R.
Set for brevity ∆i,t = u>i xt . Taking into account (1), this model allows us to write the (conditional)
expected loss of the algorithm playing Ŷt as



X
a
Et [`a,c (Yt , Ŷt )] = (1 − a)c(ji , |Ŷt |) − 1−a+ c(ji , |Ŷt |) pi,t ,
(3)
g(−∆

)

i∈Ŷt

i,t
, and the expectation Et above is w.r.t. the generation of labels Yt ,where pi,t = g(∆i,t )+g(−∆i,t )conditioned on both xt , and all previous x and Y . A key aspect of this formalization is that theBayes optimal ordered subset Yt∗ = argminY =(j1 ,j2 ,...,j|Y | )⊆[K] Et [`a,c (Yt , Y )] can be computed
efficiently when knowing ∆1,t , . . . , ∆K,t . This is handled by the next lemma. In words, this lemmasays that, in order to minimize (3), it suffices to try out all possible sizes s = 0, 1, . . . , K for Yt∗∗
that minimizes (3) over all sequences of size
and, for each such value, determine the sequence Ys,t∗s. In turn, Ys,t can be computed just by sorting classes i ∈ [K] in decreasing order of pi,t , sequence∗
being given by the first s classes in this sorted list.2
Ys,tLemma 1. With the notation introduced so far, let pi1 ,t ≥ pi2 ,t ≥ . . . piK ,t be the sequence of pi,t∗)], where
sorted in nonincreasing order. Then we have that Yt∗ = argmins=0,1,...K Et [`a,c (Yt , Ys,t∗∗
Ys,t = (i1 , i2 , . . . , is ), and Y0,t = ∅.

Notice the way costs c(i, s) influence the Bayes optimal computation. We see from (3) that placingclass i within Ŷt in position ji is beneficial (i.e., it leads to a reduction of loss) if and only if pi,t >ac(ji , |Ŷt |)/( 1−a+ c(ji , |Ŷt |)). Hence, the higher is the slot ij in Ŷt the larger should be pi,t in orderfor this inclusion to be convenient.3 It is Yt∗ that we interpret as the true set of user preferences onxt .
We would like to compete against the above Yt∗ in a cumulative regret sense, i.e., we would like toPTbound RT = t=1 Et [`a,c (Yt , Ŷt )] − Et [`a,c (Yt , Yt∗ )] with high probability. Inspired by [4], we
devise an online second-order descent algorithm whose updating rule makes the comparison vector
U = (u1 , . . . , uK ) ∈ RdK defined through (2) be Bayes optimal w.r.t. a surrogate convex loss
L(·) such that g(∆) = −L0 (∆). Observe that the expected loss function (3) is, generally speaking,nonconvex in the margins ∆i,t (consider, for instance the logistic case g(∆) = e∆1+1 ). Thus, wecannot directly minimize this expected loss.
1

The reader familiar with generalized linear models will recognize the derivative of the function p(∆) =g(−∆)
as the (inverse) link function of the associated canonical exponential family of distributions [17].
g(∆)+g(−∆)
2

Due to space limitations, all proofs are given in the supplementary material.
Notice that this depends on the actual size of Ŷt , so we cannot decompose this problem into K independentproblems. The decomposition does occur if the costs c(i, s) are constants, independent of i and s, and thecriterion for inclusion becomes pi,t ≥ θ, for some constant threshold θ.
34

Parameters: loss parameters a ∈ [0, 1], cost values c(i, s), interval D = [−R, R], function g :D → R, confidence level δ ∈ [0, 1].
Initialization: Ai,0 = I ∈ Rd×d , i = 1, . . . , K, wi,1 = 0 ∈ Rd , i = 1, . . . , K;
For t = 1, 2 . . . , T :1. Get instance xt ∈ Rd : ||xt || = 1;0b 0i,t = x>
2. For i ∈ [K], set ∆t w i,t , wherewi,t >
w0i,t =
w>
i,t xt −R sign(w i,t xt )
wi,t −A−1
−1
i,t−1 xt>
xt Ai,t−1 xt

if w>
i,t xt ∈ [−R, R],
otherwise;

3. Output
P




a
Ŷt = argminY =(j1 ,j2 ,...j|Y | )⊆[K]c(ji , |Y |) − 1−a+ c(ji , |Y |) pbi,t
,
i∈Y
b0
g(−[∆

+i,t ])

Di,twhere : pbi,t = g([∆b 0 +i,t ]D )+g(−[∆b 0 +i,t ]D ) ,
i,t
i,t



 12  c0L
d c0L
−1
2
2i,t = x>
;
A
x
U
+
+ c00 c00 + 3L(−R) ln K(t+4)
ln
1
+ t−1
t
i,t−1 tdδ(c00 )2
L

L

L

4. Get feedback Yt ∩ Ŷt ;−1
01
5. For i ∈ [K], update Ai,t = Ai,t−1 + |si,t |xt x>
t , w i,t+1 = w i,t − c00 Ai,t ∇i,t , whereL
If i ∈ Yt ∩ Ŷt1
si,t = −1 If i ∈ Ŷt \ Yt = Ŷt \ (Yt ∩ Ŷt )0otherwise;b 0i,t ) si,t xt .
and ∇i,t = ∇w L(si,t w> xt )|w=w0i,t = −g(si,t ∆Figure 1: The partial feedback algorithm in the (ordered) multiple label setting.

3

Algorithm and regret bounds

In Figure 1 is our bandit algorithm for (ordered) multiple labels. The algorithm is based on replacing
the unknown model vectors u1 , . . . , uK with prototype vectors w01,t , . . . , w0K,t , being w0i,t the timet approximation to ui , satisying similar constraints we set for the ui vectors. For the sake of brevity,b 0 = x> w0 , and ∆i,t = u> xt , i ∈ [K]. The algorithm uses ∆b 0 as proxies for the unwe let ∆
t
i,t
i,t
i
i,t
b 0 + i,t ]D ,derlying ∆i,t according to the (upper confidence) approximation scheme ∆i,t ≈ [∆i,twhere i,t ≥ 0 is a suitable upper-confidence level for class i at time t, and [·]D denotes theclipping-to-D operation, i.e., [x]D = max(min(x, R), −R). The algorithm’s prediction at time
t has the same form as the computation of the Bayes optimal sequence Yt∗ , where we replaceg(−∆i,t )the true (and unknown) pi,t = g(∆i,t )+g(−∆with the corresponding upper confidence proxyi,t )b 0 +i,t ]D )
g(−[∆
i,t
. Computing Ŷt can be done by mimicking the computation ofb0]
i,t D )+g(−[∆i,t +i,t ]D )i,t∗
the Bayes optimal Yt (just replace pi,t by pbi,t ), i.e., order of K log K running time per prediction.

pbi,t = g([∆b 0 +

Thus the algorithm is producing a ranked list of relevant classes based on upper-confidence-correctedb0scores pbi,t . Class i is deemed relevant and ranked high among the relevant ones when either ∆i,tis a good approximation to ∆i,t and pi,t is large, or when the algorithm is not very confident on its
own approximation about i (that is, the upper confidence level i,t is large).
The algorithm receives in input the loss parameters a and c(i, s), the model function g(·) and theassociated margin domain D = [−R, R], and maintains both K positive definite matrices Ai,t ofdimension d (initially set to the d × d identity matrix), and K weight vector wi,t ∈ Rd (initially
set to the zero vector). At each time step t, upon receiving the d-dimensional instance vector xt
the algorithm uses the weight vectors wi,t to compute the prediction vectors w0i,t . These vectors
can easily be seen as the result of projecting wi,t onto the space of w where |w> xt | ≤ R w.r.t.
the distance function di,t−1 , i.e., w0i,t = argminw∈Rd : w> xt ∈D di,t−1 (w, wi,t ), i ∈ [K], where
di,t (u, w) = (u − w)> Ai,t (u − w) . Vectors w0i,t are then used to produce prediction values
b 0 involved in the upper-confidence calculation of Ŷt ⊆ [K]. Next, the feedback Yt ∩ Ŷt is∆i,tobserved, and the algorithm in Figure 1 promotes all classes i ∈ Yt ∩ Ŷt (sign si,t = 1), demotes
5all classes i ∈ Ŷt \ Yt (sign si,t = −1), and leaves all remaining classes i ∈/ Ŷt unchanged (signsi,t = 0). The update w0i,t → wi,t+1 is based on the gradients ∇i,t of a loss function L(·) satisfying
L0 (∆) = −g(∆). On the other hand, the update Ai,t−1 → Ai,t uses the rank one matrix4 xt x>t .
In both the update of w0i,t and the one involving Ai,t−1 , the reader should observe the role playedby the signs si,t . Finally, the constants c0L and c00L occurring in the expression for 2i,t are related tosmoothness properties of L(·) – see next theorem.
Theorem 2. Let L : D = [−R, R] ⊆ R → R+ be a C 2 (D) convex and nonincreasing functionof its argument, (u1 , . . . , uK ) ∈ RdK be defined in (2) with g(∆) = −L0 (∆) for all ∆ ∈ D, andsuch that kui k ≤ U for all i ∈ [K]. Assume there are positive constants cL , c0L and c00L such that:
000(−∆)+L00 (∆) L0 (−∆)
i. L (∆) L≥ −cL and ii. (L0 (∆))2 ≤ c0L , and iii. L00 (∆) ≥ c00L hold for all(L0 (∆)+L0 (−∆))2∆ ∈ D. Then the cumulative regret RT of the algorithm in Figure 1 satisfies, with probability atleast 1 − δ,qRT = O (1 − a) cL K T C d ln 1 + Td ,  c0d c0KT
where C = O U 2 + (c00 L)2 ln 1 + Td + (c00L)2 + L(−R)
.
ln
00
c
δ
L

L

L

It is easy to see that when L(·) is the square loss L(∆) = (1 − ∆)2 /2 and D = [−1, 1], wehave cL = 1/2, c0L = 4 and c00L = 1; when L(·) is the logistic loss L(∆) = ln(1 + e−∆ ) andx−x
1
D = [−R, R], we have cL = 1/4, c0L ≤ 1 and c00L = 2(1+cosh(R)), where cosh(x) = e +e.
2
Remark 1. A drawback of Theorem 2 is that, in order to properly set the upper confidence levels i,t , we assume prior knowledge of the norm upper bound U . Because thisinformation is often unavailable, we present here a simple modification to the algorithm
that copes with this limitation. We change the definition of 2i,t in Figure 1 to 2i,t =
)
(



 12  c0
2 d c0L
K(t+4)
t−1
2> −1, 4 R . This immedimax x Ai,t−1 x (c00 )2 ln 1 + d + c00 cL00 + 3L(−R) ln δL

L

L

ately leads to the following result.
Theorem 3. With the same assumptions and notation as in Theorem 2, if we replace 2i,t as explained
above we have that, with probability at least 1 − δ, RT satisfiesq 00 2 2 (cL ) URT = O (1 − a) cL K T C d ln 1 + Td + (1 − a) cL K R d exp
−
1
.
0
c d
L

4

On ranking with partial feedback

As Lemma 1 points out, when the cost values c(i, s) in `a,c are stricly decreasing then the Bayes
optimal ordered sequence Yt∗ on xt can be obtained by sorting classes in decreasing values of pi,t ,and then decide on a cutoff point5 induced by the loss parameters, so as to tell relevant classesg(−∆)
is increasing in ∆, this ordering
apart from irrelevant ones. In turn, because p(∆) = g(∆)+g(−∆)
corresponds to sorting classes in decreasing values of ∆i,t . Now, if parameter a in `a,c is very close6
to 1, then |Yt∗ | = K, and the algorithm itself will produce ordered subsets Ŷt such that |Ŷt | = K.
Moreover, it does so by receiving full feedback on the relevant classes at time t (since Yt ∩ Ŷt =Yt ). As is customary (e.g., [6]), one can view any multilabel assignment Y = (y1 , . . . , yK ) ∈{0, 1}K as a ranking among the K classes in the most natural way: i preceeds j if and only if
yi > yj . The (unnormalized) ranking loss function `rank (Y, fb) between the multilabel Y and aranking function fb : Rd → RK , representing degrees of class relevance sorted in a decreasingorder fbj1 (xt ) ≥ fbj2 (xt ) ≥ . . . ≥ fbjK (xt ), countsin the number of class pairs that disagree 
P
1 b
b
b
b
b
the two rankings: `rank (Y, f ) ={fi (xt ) < fj (xt )} + {fi (xt ) = fj (xt )} ,i,j∈[K] : yi >yj

2

2
Notice that A−1
i,t can be computed incrementally in O(d ) time per update. [4] and references therein alsouse diagonal approximations thereof, reporting good empirical performance with just O(d) time per update.
5This is called the zero point in [9].
6
If a = 1, the algorithm only cares about false negative mistakes, the best strategy being always predictingŶt = [K]. Unsurprisingly, this yields zero regret in both Theorems 2 and 3.
4

6

where {. . .} is the indicator function of the predicate at argument. As pointed out in [6], the ranking
function fb(xt ) = (p1,t , . . . , pK,t ) is also Bayes optimal w.r.t. `rank (Y, fb), no matter if the classlabels yi are conditionally independent or not. Hence we can use this algorithm for tackling ranking
problems derived from multilabel ones, when the measure of choice is `rank and the feedback isfull.
In fact, a partial information version of the above can easily be obtained. Suppose that at eachtime t, the environment discloses both xt and a maximal size St for the ordered subset Ŷt =(j1 , j2 , . . . , j|Ŷt | ) (both xt and St can be chosen adaptively by an adversary). Here St might be
the number of available slots in a webpage or the number of URLs returned by a search engine in
response to query xt . Then it is plausible to compete in a regret sense against the best time-t offline
ranking of the form f (xt ) = (f1 (xt ), f2 (xt ), . . . , fh (xt ), 0, . . . , 0), with h ≤ St . Further, theranking loss could be reasonably restricted to count the number of class pairs disagreeing within Ŷtplus the number of false negative mistakes. E.g., if fbj1 (xt ) ≥ fbj2 (xt ) ≥ . . . ≥ fbj|Ŷ | (xt ), we can
t
set


P
`rank,t (Y, fb) = i,j∈Ŷt : yi >yj {fbi (xt ) < fbj (xt )} + 21 {fbi (xt ) = fbj (xt )} + |Yt \ Ŷt | .
It is not hard to see that the Bayes optimal ranking for `rank,t is given by f ∗ (xt ; St ) =(pi1 ,t , . . . , piSt ,t , 0, . . . , 0). If we put on the argmin (Step 3 in Figure 1) the further constraint|Y | ≤ St (notice that the computation is still about sorting classes according to decreasing values of pbi,t ), one can prove the following ranking counterpart to Theorem 2.
Theorem 4. With the same assumptions and notation as in Theorem 2, let the cumulative regret RT
w.r.t. `rank,t be defined as
PT
RT = t=1 Et [`rank,t (Yt , (bpj1 ,t , ..., pbjSt ,t , 0, ..., 0))] − Et [`rank,t (Yt , (pi1,t , ..., piSt ,t , 0, ..., 0))],where pbj1 ,t ≥ . . . ≥ pbjSt ,t ≥ 0 and pi1 ,t ≥ . . . ≥ piSt ,t ≥ 0. Then, with probability at least 1 − δ, qwe have RT = O cL S K T C d ln 1 + Td , where S = maxt=1,...,T St .
The proof (see the appendix) is very similar to the one of Theorem 2. This suggests that, to someextent, we are decoupling the label generating model from the loss function ` under consideration.
Notice that the linear dependence on the total number√of classes K (which is often much larger
than S in a multilabel/ranking problem) is replaced by SK. One could get similar benefits out of
Theorem 2. Finally, one could also combine Theorem 4 with the argument contained in Remark 1.

5

Experiments and conclusions

The experiments we report here are meant to validate the exploration-exploitation tradeoff implemented by our algorithm under different conditions (restricted vs. nonrestricted number of classes),loss measures (`a,c , `rank,t , and Hamming loss) and model/parameter settings (L = square loss, L =logistic loss, with varying R).
Datasets. We used two multilabel datasets. The first one, called Mediamill, was introduced in avideo annotation challenge [21]. It comprises 30,993 training samples and 12,914 test ones. The
number of features d is 120, and the number of classes K is 101. The second dataset is Sony CSL
Paris [18], made up of 16,452 train samples and 16,519 test samples, each sample being describedby d = 98 features. The number of classes K is 632. In both cases, feature vectors have beennormalized to unit L2 norm.
Parameter setting and loss measures. We used the algorithm in Figure 1 with two different
loss functions, the square loss and the logistic loss, and varied the parameter R for the latter. The
setting of the cost function c(i, s) depends on the task at hand, and for this preliminary experiments
we decided to evaluate two possible settings only. The first one, denoted by “decreasing c” isc(i, s) = s−i+1, i = 1, . . . , s, the second one, denoted by “constant c”, is c(i, s) = 1, for all i andss. In all experiments, the a parameter was set to 0.5, so that `a,c with constant c reduces to half
the Hamming loss. In the decreasing c scenario, we evaluated the performance of the algorithm on
the loss `a,c that the algorithm is minimizing, but also its ability to produce meaningful (partial)
rankings through `rank,t . On the constant c setting, we evaluated the Hamming loss. As is typicalof multilabel problems, the label density, i.e., the average fraction of labels associated with the7Sony CSL Paris − Hamming loss and constant c

Final Average Hamming loss

50

100

50

33

OBR
SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)

32
31
Final Average Rank loss

SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)
Running average la,cSony CLS Paris − Ranking loss

55

Sony CSL Paris − Loss(a,c) and decreasing c
150

45

40

30
29
28
27
OBR
SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)

26

35

25
0 0
10

1

10

2

3

4

10
10
Number of samples

10

30 0
10

5

10

1

24

2

10

10

5

10

15

S

20
S

25

30

35

Figure 2: Experiments on the Sony CSL Paris dataset.
2

7

Final Average Hamming loss

6.5

15

10

6

OBR
SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)

1.9

OBR
SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)

1.8
Final Average Rank loss

SquareLogistic (R=1.5)
Logistic (R=2.0)
Logistic (R=2.5)
Logistic (R=3.0)

20
Running average la,cMediamill − Ranking loss

Mediamill − Hamming loss and constant cMediamill − Loss(a,c) and decreasing c
25

5.5
5
4.5
4

1.7
1.6
1.5
1.4
1.3
1.2

5

1.1

3.5

1
0 0
10

1

10

2

3

10
10
Number of samples

4

10

5

10

3 0
10

1

10
S

2

10

5

10

15
S

20

25

Figure 3: Experiments on the Mediamill dataset.
examples, is quite small. For instance, on Mediamill this is 4.3%. Hence, it is clearly beneficial
to impose an upper bound S on |Ŷt |. For the constant c and ranking loss experiments we tried out
different values of S, and reported the final performance.
Baseline. As baseline, we considered a full information version of Algorithm 1 using the squareloss, that receives after each prediction the full array of true labels Yt for each sample. We callthis algorithm OBR (Online Binary Relevance), because it is a natural online adaptation of thebinary relevance algorithm, widely used as a baseline in the multilabel literature. Comparing to
OBR stresses the effectiveness of the exploration/exploitation rule above and beyond the details of
underlying generalized linear predictor. OBR was used to produce subsets (as in the Hamming losscase), and restricted rankings (as in the case of `rank,t ).
Results. Our results are summarized in Figures 2 and 3. The algorithms have been trained bysweeping only once over the training data. Though preliminary in nature, these experiments allow
us to draw a few conclusions. Our results for the avarage `a,c (Yt , Ŷt ) with decreasing c are containedin the two left plots. We can see that the performance is improving over time on both datasets, aspredicted by Theorem 2. In the middle plots are the final cumulative Hamming losses with constantc divided by the number of training samples, as a function of S. Similar plots are on the right withthe final average ranking losses `rank,t . In both cases we see that there is an optimal value of S thatallows to balance the exploration and the exploitation of the algorithm. Moreover the performanceof our algorithm is always pretty close to the performance of OBR, even if our algorithm is receiving
only partial feedback. In many experiments the square loss seems to give better results. Exception
is the ranking loss on the Mediamill dataset (Figure 3, right).
Conclusions. We have used generalized linear models to formalize the exploration-exploitation
tradeoff in a multilabel/ranking setting with partial feedback, providing T 1/2 -like regret bounds under semi-adversarial settings. Our analysis decouples the multilabel/ranking loss at hand from thelabel-generation model. Thanks to the usage of calibrated score values pbi,t , our algorithm is capableof automatically inferring where to split the ranking between relevant and nonrelevant classes [9],the split being clearly induced by the loss parameters in `a,c . We are planning on using more general label models that explicitly capture label correlations to be applied to other loss functions (e.g.,
F-measure, 0/1, average precision, etc.). We are also planning on carrying out a more thorough experimental comparison, especially to full information multilabel methods that take such correlations
into account. Finally, we are currenty working on extending our framework to structured output
tasks, like (multilabel) hierarchical classification.
8

References[1] Y. Abbasi-Yadkori, D. Pal, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In 25th NIPS, 2011.
[2] K. Amin, M. Kearns, and U. Syed. Graphical models for bandit problems. In UAI, 2011.
[3] P. Auer. Using confidence bounds for exploitation-exploration trade-offs. JMLR, 3, 2003.
[4] K. Crammer and C. Gentile. Multiclass classification with bandit feedback using adaptive
regularization. In 28th ICML, 2011.
[5] V. Dani, T. Hayes, and S. Kakade. Stochastic linear optimization under bandit feedback. In
21th Colt, 2008.
[6] K. Dembczynski, W. Waegeman, W. Cheng, and E. Hullermeier. On label dependence and loss
minimization in multi-label classification. Machine Learning, to appear.
[7] S. Filippi, O. Cappé, A. Garivier, and C. Szepesvári. Parametric bandits: The generalized
linear case. In NIPS, pages 586–594, 2010.
[8] Y. Freund, R. D. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for
combining preferences. JMLR, 4:933–969, 2003.
[9] J. Furnkranz, E. Hullermeier, E. Loza Menca, and K. Brinker. Multilabel classification via
calibrated label ranking. Machine Learning, 73:133–153, 2008.
[10] E. Hazan and S. Kale. Online submodular minimization. In NIPS 22, 2009.
[11] E. Hazan and S. Kale. Newtron: an efficient bandit algorithm for online multiclass prediction.
In NIPS, 2011.
[12] R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers. MIT Press, 2000.
[13] S. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms for online multiclassprediction. In 25th ICML, 2008.
[14] S. Kale, L. Reyzin, and R. Schapire. Non-stochastic bandit slate problems. In 24th NIPS, 2010.
[15] A. Krause and C. S. Ong. Contextual gaussian process bandit optimization. In 25th NIPS,
2011.
[16] T. H. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math,
6, 1985.
[17] P. McCullagh and J.A. Nelder. Generalized linear models. Chapman and Hall, 1989.
[18] F. Pachet and P. Roy. Improving multilabel analysis of music titles: A large-scale validationof the correction approach. IEEE Trans. on Audio, Speech, and Lang. Proc., 17(2):335–343,
February 2009.
[19] P. Shivaswamy and T. Joachims. Online structured prediction via coactive learning. In 29th
ICML, 2012, to appear.
[20] A. Slivkins, F. Radlinski, and S. Gollapudi. Learning optimally diverse rankings over large
document collections. In 27th ICML, 2010.
[21] C. G. M. Snoek, M. Worring, J.C. van Gemert, J.-M. Geusebroek, and A. W. M. Smeulders.
The challenge problem for automated detection of 101 semantic concepts in multimedia. In
Proc. of the 14th ACM international conference on Multimedia, MULTIMEDIA ’06, pages
421–430, New York, NY, USA, 2006.
[22] M. Streeter, D. Golovin, and A. Krause. Online learning of assignments. In 23rd NIPS, 2009.
[23] G. Tsoumakas, I. Katakis, and I. Vlahavas. Random k-labelsets for multilabel classification.
IEEE Transactions on Knowledge and Data Engineering, 23:1079–1089, 2011.

9